SC2 – Match ups and Me (TvT)

For those unfamiliar with SC2, a “match up” is just a fancy was of saying “Race A vs Race B.” For a Terran player in SC2, there are three match ups:  Terran vs Terran (TvT), Terran vs Protoss (TvP), and Terran vs Zerg (TvZ).  I’d like to start here by talking a bit about my experience in each match up, my strengths, and my weaknesses.  I’ll be addressing basic early thought, my standard build orders for each, and where I know I falter.  Additionally, I know that I’ll be describing these in a simplified fashion, but I’ll talk about each in more detail at a later time.

 

TvT

Terran vs Terran, probably my best match up.  Most TvT games come down to two things: 

- Who wins the siege tank war

- Does the person who loses the siege tank war abuse their better mobility?

Obviously that isn’t the end all way to describe TvT.  There are plenty of ways to counter siege tanks (early pressure, for example, can be very effective as a way to stifle the siege tank count of your opponent) but in the current state of the game where marines and marauders make of the majority of a Terran army it’s hard to argue that siege tanks aren’t a major part of a TvT.

I’ve found that, on my way up the ladder, these three strategies prevail:

1) Mass marine timing push.

2) Fast siege mode timing push

3) Banshee rush (both 1 and 2 port)

The old fall back for many starting players is the 2-3 rax mass marine push.  With some micro and a very short ground distance this can be a pretty effective start.  It also helps set players up for a heavy MMM build in the mid to late game.  However, getting three barracks is both expensive and time consuming, as well as being easy to scout.  Early siege tanks will shut down a marine only push without much issue.

Siege tank rushing is a very common strategy, relying on the fact that siege tanks shut down almost all early ground aggression by another Terran, as well as prove to be extremely useful in the late game.  The biggest downside is that siege tanks make you VERY immobile later, but at the start you can defend your main and natural without much issue with only a couple tanks.

Finally, my personally favorite, the early banshee pressure.  Early banshee provides an easy way to safely harass an opponents mineral line and prevent counter pressure, similar to mutalisks.  With the ability to cloak and a high damage shot, banshees can decimate an early mineral line.  If scouted, it forces the opponent to either waste money on turrets, or to pull back marines to defend (effectively taking pressure off of you).  However, fast banshee suffers from a few drawbacks.  To have the money/gas to throw down a banshee/cloak as fast as possible, you take a large hit to your marine count.  Early pressure can be a real issue, and you’re almost forced to wall off in some fashion. 

Of course, there are merits and issues I haven’t talked about in these builds, as well as other builds you’ll see (marine fast drop, hellion harass/drop, fast thor push, early ghosts, to name a few).  From my experience though, I’ve seen these three far more often than the others (though hellion and marine drops come up a decently close 4th).

 

As I mentioned early, my TvT opening tends to favor early 1 starport banshee with cloak when the map is either very small (Steppes of War, Desert Oasis, for example) or closed positions on 4 player maps (Lost Temple, Metalopolis, Kulas Ravine, etc).  Beyond that, I like the early siege tank builds, they provide a good way to move out against a terran as well as allowing you to keep up your marine count a bit more, which is great against banshee and fast marine drops.  As a rule of thumb, I tend to like to get my EBay quickly, not so much for the 1 attack, but for the sensor tower.  I’m a HUGE fan of the sensor tower.  While not as good as an observer, the sensor tower as a whole I think is very underused by most Terran players.

Certain conditions as Terran do make me uncomfortable though, and I’m working on that.  If I’m losing the siege tank race (that is to say, I’m behind in my tank count) I find it hard to find a good time to move out.  I need to work on getting my drop play up in those situations and abuse the fact that I’m more mobile than my opponent.  Also, like many players, I need to work on my timing for a third base. 

SC2 – That one game

(This is cross-posted with my primarily FFXI-centric blog, located at dantpup.livejournal.com)

Hi. I’m Dantaro. I play Starcraft 2. A lot of Starcraft 2. Not like "Holy crap, all he does is play SC2," but enough. In the past this blog has focused on FFXI, and it still will, but SC2 has a major place in my gaming life right now so I’d like to talk about it too. This wont be ultra-high level analysis, I am not Day9, but I am a big fan of the game and of talking about it.
Most of what is going to go here will be replays of myself, analysis of my game play, and will provide me a permanent record of both my ladder games and my private 1v1s. Additionally, once I work out the kinks, I’ll be posting my shoutcasts of professional SC2 games and providing background on the players.
So yeah. For those who like SC2, I hope you’ll get a kick out of reading what I put here.

Video Games – Beat Hazard and Audiosurf

Ah music games.  Always a place in my heart will they have, with their combining of two of my favorite things, high-octane videogames and music.  To that point, two have been getting more play time out: Audiosurf and Beat Hazard.  For those who haven’t ever heard of these games, spend more time on Steam!  Both are built around using the players own music collection to create the action in the game, but both are otherwise not-similar.

Audiosurf is a game where you do just what the title suggests:  Surf audio.  Ok, well maybe that doesn’t make that much sense, so I’ll break it down for you.  The game casts the player as one of a variety of characters, each with their own special style, and tasks them with navigating a song.  The game play itself is a puzzle style racer where the player matches colored tiles in sets of three or more (touching in any non-diagonal fashion) in a field of 3×8 (24 total) .  Once a set of 3 is made, it has a small cool down time before it vanishes granting points, additionally getting another block of the same color extends the period the group exists as well as resetting the timer before it vanishes.

Overloading any given column destroys all blocks in the field as well preventing the player from picking up more blocks until a timer finishes and they “Respawn,” though the song itself does not stop.  The game is broken into two styles, with 90% of the characters on fields with multiple colors at once (such as with the picture of the left).  The “Mono” characters follow the same general rules but have only 1 color block and grey blocks, with the idea being to not get the grey blocks (which don’t activate or grant points).  The game play in Audiosurf varies between fast and frantic, and dulll, depending not only on the song the player uses, but the character as well.  Mono characters are the easiest, but can be frustrating and boring if songs slow down to often.  Other characters are generally far more frantic but are unbelievably hard to play well with an extremely high learning curves.

The music decoder is pretty solid but unsurprisingly unable to decode protected iTunes files.  What’s especially nice is that there is no DLC needed to play normal itunes music as there is with Beat Hazard.

Overall the game is (generally) fast and fun, with options to use keyboard or mouse.  The puzzle characters are hard (some might call them “Challanging” but honestly they’re just straight up hard) but fun to learn. Mono characters are easier to learn but just as fun to play.  In the end, the game is a ton of fun to play and people will often want to watch as the colors are eye catching and fun. The biggest issues are the non-intuitive keyboard controls and occasional crash bugs on start-up.

Overall: 8/10.

Beat Hazard is another action-music game that relies on the player’s music collection to create it’s game play.  Originally a Xbox Arcade game, it was released on via Steam later.  The game is an asteroids-inspired space shooter where the player fights against hoards of enemies as well as actual asteroids and bosses.  The player scored points for each thing destroyed, and accumulates score multipliers either by getting multiplier bonus drops (from enemies) or other bonuses (Going long enough without firing, for example).  Additionally, the game allows ranking up depending on how well you do on songs.  As you rank up the player gains additional bonuses (weapon power-ups at the start, lower death penalties, etc) which in turn leads to higher scores and higher ranks.

Graphically, the game uses sprites for player and enemies and highly stylized weapon fire.  So stylized is the weapon fire that I need to spend a minute talking about it specifically.  We’ve all seen flashy weapons before.  Blue balls of plasma scorching aliens in Doom, pink fuzzy doom from the needler in Halo, those annoying fucking bouncing balls of DEATH that you can somehow grab and throw at shit to make them cease to exist from Half-Life 2 and Portal, but all of these flashy effects?  They’re child’s play compared to the shit that goes down in Beat Hazard.   The colors are SO extreme and there is so much flashing going on any time you fire the damn weapon that they needed to put a seizer warning at the start of the game.  Everything from the balls of energy to the explosions of ships and the resulting few seconds afterwards flashes like a lightning bug on crack.  Imagine if someone was to put you in a room full of strobe lights and run them all at different speeds, that’s almost half as flashy as Beat Hazard.

Why am I making such a big deal about these?  Well, it’s because it leads to the first major issue with the game.  So extreme is the light show that it’s more than possible to simply not be able to see your own ship, leading to countless cheap deaths.  Some might call this a feature (“Clearly it makes the game harder, and was thus a design choice!”) but these people are stupid.  Even if it WAS a design choice, it was a poor one.  The player should never be punished for performing the primary goal in the game, that would be like Pac-Man getting leprosy after eating a power pill.

Additionally, it is hard to tell sometimes what is debris that can kill you is and what is just aesthetic debris.  If you play the game for big points, waiting until many enemies are on screen before tossing your super bomb you’ll know what I’m talking about when you hit 3-5 asteroids at the same time and get face raped by the tiny debris that looks remarkably like the debris from the larger ships you just blew up with the same bomb.

The only other issue with the game is that you need to buy the DLC to play non-protected iTunes files.  This, however, was an understandable design choice, as the codex is expensive.  Additionally the DLC is only $1, so it wont put a big hole in your pocket (if it does, why the hell are you buying games?!).

All in all, the game is engaging and fun.  The upper difficulty levels are hard, and require a lot of patients to get good at.  The games flaws are generally overlookable, but the more-occasional-than-it-should-be death can get very tiresome, very quickly.  Regardless, I highly recommend this game if you like asteroid-esque space shooters.

Overall: 7/10.

Video Games – Command & Conquer 4: Tiberium Twilight

Oh the C&C franchise.  It’s hard to believe that my first experience with C&C was well over 10 years ago now (I started with C&C Red Alert, actually.  So 14 years, give or take).  You could say I’ve been a long time fan, and I wont pretend for a minute that I haven’t bought every game, even after Westwood went belly up and was absorbed by EA.  I’ll never forget my LAN sessions of RA1 with friends, or my afternoons spent destroying Nod stealth tanks with my sonic ones (For the record?  Tiberium Sun was the best of all the games.)  Needless to say that when I heard that they changed the formula for C&C4, I was very skeptical.

For those unfamiliar with the franchise, C&C is one of the grandpapies of the RTS genre (In fact, the original developer Westwood redefined modern RTS games with Dune 2) and was the straight up competitor to Blizzard’s Warcraft and Starcraft series.  The standard formula for an RTS (That Westwood established) is as follows:

- Each player is given a starting location/base with a limited supply of funds.

- Players are tasked at the start to create and sustain an economy as well as begin construction of forces.

- The game revolves around the expansion of each player, which leads to conflict over resources.  This generally creates a game of look-in-two-directions-at-once, where players are forced to not only watch their forward expansions, but be able to spot and react to attacks on their back positions.

- The overall objective is either the destruction of all enemy forces or of all enemy buildings (barring custom scenarios and campaigns).

The general rule of thumb in an RTS is “He who controls the spice, controls the universe” (Baron Vladmir Harkonnen, Dune).  That is to say, if you get the commanding lead in resources, you should have a commanding lead in production, and a commanding lead of the game.

Well, EA Los Angeles decided to take this standard formula and throw it out the window.  In it’s place is a system built on controlling various towers on a map, where each point generates points and first to cap points wins.  Furthermore, the idea of building up a base and gathering resources has been completely scrapped.  Instead, each player is given a mobile base and limited power/supply slots to work with.  Each unit/building takes up various amounts of one kind of slot, and the player regains that slot when the unit dies, the building is destroyed, or the building is sold.  There are three style of MCV, Support, Offense, and Defense, each with it’s own set of units which always conform to a game play style.  If a player uses their MCV, they are able to respawn in one of the drop points that their team controls. This new style of unit management, in addition with the new game mode and hour time limit cap, creates an frantic and action filled multiplayer that tasks players to learn their role and know how to interact with their team.

Sound good so far?  Well it is, but the game does suffer from a few major drawbacks.  The first thing any veteran will notice when they first start the game is the distinct lack of units and seemingly no way to fix that.  However, as it turns out this is a design choice by EALA.  The ability to earn more units comes with the earning of “ranks” (Think CoD4:MW2).  Each unit kill nets you a small amount of experience, and each rank nets you new units and unit upgrades.  This creates a serious issue when you start as you will be limited to only basic units to begin with.  Worse, until many hours have been put in upgrading one’s rank, the factions feel interchangeable and superficial.  Furthermore, gone are the days of GDI vs GDI and Nod vs Nod.  Due to the gameplay’s need for defined teams, there is no longer any mixing of factions per team.  Additionally, the single player is. . . less than inspiring.  Consisting of two paths (both cannon) that the player can walk to help various sides of the conflict, the story is bland and the removal of one of the greatest villains in gaming is disappointing (Hmmm, I guess I should have spoiler’d that).  However, the addition of a more integrated co-op campaign is appreciated.

Easily the worst part of the game is the DRM.  Requiring a constant internet connection means you can’t play this game when visiting those relatives you hate who don’t have internet (or at least wont share with you, you dirty gamer! You’ll clog their precious internet tubes!!!!).

In conclusion, C&C4 is all about the multiplayer, though you’ll find yourself being forced to play the single player to really enjoy the multiplayer.  The game definitely isn’t for everyone, and hard core fans of the series are going to feel gipped by the style change. If you can, get a friend to buy C&C4 too so you can go through the game on co-op.  While the game leaves the nostalgia at home, it makes up for it with a frantic and fast multiplayer that will keep you coming back for more.

Overall: 7.5/10

Video Games – Final Fantasy XIII: First Six Hours

It’s rare to fine me playing a game that isn’t Final Fantasy XI or an FPS with friends these days.  I adore RPGs, but barring FFXI I haven’t found one lately that can really hold my interest (admittedly, FFXI may be to blame for this).  However, FFXIII is doing a pretty damn good job at keeping me occupied.

I bought the game on release day (yesterday, actually) for the 360 and after a series of unfortunate, events and some chipotle, I finally got to sit down and play it.  Similarly, following work today I also played, taking advantage of my break.

So far the game has been outstanding.  The combat is fresh, the story is engaging, and the characters are both likable and interesting.  Moreover, the game LOOKS fantastic.  Visually stunning is a proper way to describe the game, though “Really Fucking Pretty” has also been used.

The combat feels like a natural starting place to talk about.  Unlike previous FF titles, the battles happen in real time. . . almost.  The ATB makes a return as a way to regulate how often you attack, and with what skills.  Furthermore, direct control of allies is removed in favor of the “Paradigm” system, which itself is an extension of the Crystarium system.  Every character has a collection of roles, a set of jobs one might say.  You set Paradigms for party setups outside of battle, depending on your party setup, and can swap between them at any time.  Each role fulfills a different roll: medics heal, sentinels tank, commandos are melee DPS, ravagers are magic DPS, synergists buff, and saboteurs debuff.  Thus, a typical balanced Paradigm may look something like “Commando, Ravager, Medic,” though since you can swap between them at any time during battle, you may find yourself with a setup involving Synergists at the start, and moving to another setup once you’re ready to fight.  With out getting too much further into it, this system keeps the battles interesting, as you find yourself having to change tactic not only fight to fight, but party to party.  It takes a bit of getting used to, but once you figure it out it’s very fun and very entertaining.

The Crystarium system is also pretty interesting.  Each fight earns you CP (Crytarium Points) which you can use to increase whatever role your character has access too.  You have to pick and choose which role the CP goes into, and which orbs to go to in each role, but it’s all very intuitive.

The game itself starts off. . . slow.  Not the various CSs, which are all action packed and interesting to listen too, but the combat.  For the first hour/hour and a half you have access to only basic commands.  Gradually the game introduces you to new combat mechanics, but it’s pretty slow.  Even after you first get the paradigm system they start you with a crazy broken setup, making it hard to really get a handle for how the system feels.  Furthermore, some of the common encounters take entirely too long, without any risk of losing.  For example, with Suzh and Vanille it takes me roughly 7 minutes to kill some enemies in a 2v1 fight with both attacking.  It gets a bit tedious some times, but since you can avoid many of the fights you can choose to simply stay out of their way many times. Luckily, the story and characters make up for this shortcoming.  Once you make it past that portion, the game keeps things interesting by swapping in and out party members, giving you a chance to see feel out the combat system and to see how the computer treats each job.

In addition to standard battles, there are also summon fights, which are a whole different can of fish.  Each summon has a different trick to beating it, and the only way to figure that out is to Libra the summon.  They can be pretty difficult it seems, so expect to lose every now and then.  I personally lost twice to Odin before I figured out the trick.

All in all, the first 6 hours have been a blast.  I was unsure at first about the combat system, but after the paradigm system got into full swing I was able to really get into it.  The game is going to be long, as the game comes on THREE disks, and I’m extremely excited to see it all the way through.  I’ll post a final review once I finish it.

F#/C# – Scrabble Word Generator

Our most recent project in my Programming Languages class was to combine both C# and F# code to create a small program that generates all permissible words one can create with a scrabble hand.  That is to say, given 7 tiles (which are repeat in value) what are all legal scrabble words one can make with them?

The project itself wasn’t hard, though it was interesting to see how one combines different .NET languages.  For those unaware of how .NET languages work, the system is designed to compile to the Common Language Runtime (CLR) which creates an application virtual machine, thus allowing the language to remain platform neutral (well, as platform neutral one can get with a framework that ONLY runs on Windows at the moment, barring the Linux initiative to build a Linux- version).  In the CLR, all code from all languages of .NET are compiled into one single language, which allows the interaction of the languages.

Of course, this is not without it’s issues.  The primary one in this project was that F# lists are not C# lists, and thus you cannot mix them.  To get around this issue one typically uses generic IEnumerable objects when passing to/from F#/C#, converting the generic structure to the language specific structure once in the language.  Similarly, strings in C# are not strings in F#, nor are tuples.

Normally, this is about where I would post the code for how I solved the problem, but this time I decided that I would simply upload the entire project solution, since it would be hard to properly format all the code for the blog post.  Please forgive that I uploaded to rapidshare, as at the moment I do not have server space anywhere to host the file. 

About the file: 348kB, .RAR format

The solution was created in the Visual Studios 2010 Release Candidate using the .NET 4 Framework Release Candidate.  This will NOT open in VS2008 or under.  If there is a request for it I’ll create a 2008 compatible version and post it.

Download Here

 

“If you think you are worth what you know, you are very wrong.  Your knowledge today does not have much value beyond a couple of years.  Your value is what you can learn and how easily you can adapt to the changes this profession brings so often.”
– Jose M. Aguilar

F# – Merge Sort

More working in F#.  I’m getting the hang of functional programming, though I still don’t want to spend my life coding in it.  Its definitely has some cool uses, but I’ll take my imperative model for most things!

We had to write Merge Sort in F#, which was fun.  This was a quick and dirty solution that I wrote pretty quick.  It works, but its slow.  I’m sure there is a faster way to do it, but its kind of pointless in my mind since you can write a faster imperative merge sort. Meh, whatever.

 

let rec splitter org_list new_list half counter =
    if(counter < half) then
        let head = List.head org_list
        splitter (List.tail org_list) (head :: new_list) half (counter + 1)
    else
        new_list,org_list

let split list =
    match list with
    | [] -> ([], [])
    | a::[] -> ([a], [])
    | a::b::[] -> ([a], [b])
    | _ ->
        splitter list [] (list.Length / 2) 0

let rec merge_helper list_left list_right list_final =
    match list_left with
    | [] -> list_final @ list_right
    | head::tail ->
        if(list_right.Length > 0)then
            if(head < list_right.Head)then
                let head_list = [head]
                merge_helper tail list_right (list_final @ head_list)
            else
                let head_list = [list_right.Head]
                merge_helper list_left (List.tail list_right) (list_final@head_list)
        else
            list_final @ list_left

let merge list_left list_right =
    merge_helper list_left list_right []

let rec merge_sort list =
    match list with
    | [] -> []
    | e::[] -> [e]
    |_ ->
        let (l,r) = split list
        let ll = merge_sort l
        let rr = merge_sort r
        merge ll rr

 

“In a room full of top software designers, if two agree on the same thing, that’s a majority.”
– Bill Curtis

F# – Impressions

This semester I’m taking a class on programming languages (aptly named “Programming Languages”).  As any CompSci major will tell you, it’s either extremely interesting, or extremely confusing.

The first language we’re dealing with is F#, Microsoft’s (now) in house functional programming language, for use with the .NET framework.  This is my first entry into the world of functional programming and I find it. . . interesting.  At first, switching mind sets from imperative to functional was extremely hard.  My first program (to calculate standard deviations of lists) was 8 functions using mutable variables (though I avoided using for loops).  After we talked more about the language and how functional programming is supposed to work in class, I was  able to condense it down to a few lines in 1 function in a truly function fashion.

On the whole, I can understand why functional programming is powerful.  I like that I can right quick sort in 4 lines of code (5 including the function declaration statement).  Being able to make powerful recursive methods in small and efficient methods is invaluable.  However, I wouldn’t want to ever try doing this kind of programming for the whole of projects.  It may simply be because I “grew up” on imperative programming in Java, C, and C#.  The language makes the most sense to me as a supplement in the .NET framework, writing methods in F# and calling them from a C# program (When we talked about this idea in class, I was probably a bit more excited that I should have been about the prospect).  I may see the light at some point, but for now I’ll enjoy my tenure in the world of imperative programming.

 

Just a couple things we’ve done in F# so far.  The first is quick sort, and the second generates lists of random integers.

Quicksort:

let rec quick_sort list =
    match list with
    |[] -> []
    |pivot::tail ->
        quick_sort (List.filter(fun x -> x < pivot) list)@ [pivot] @ quick_sort(List.filter(fun x -> x > pivot) list)

 

 

#light

open System

let ran = System.Random()
let rec do_gen n cur_length in_list =
    if(cur_length < n) then
        do_gen n (cur_length + 1) (ran.Next() :: in_list)
    else
        in_list
let gen_list n =
    do_gen n 0 []

let rec printfnList list =
    match list with
        | [] -> printfn ""
        | head::tail ->
            printf "%A; " head
            printfnList tail
printfn "Enter a number: "
let in_length = Int32.Parse(Console.ReadLine())

printfnList (gen_list in_length)

let ignore = Console.ReadKey true

 

“The best way to predict the future is to implement it.”
– David Heinemeier Hansson

PHP – Online Time Card Application

As a senior double majoring in Music and CompSci, I’m stressed for class time between the two subjects.  This came to a head when deciding on classes for this semester between taking my music senior seminar (to allow me to graduate with my Music major) or taking Cryptography, as they both fell into the same time slot.  Luckily, being at a small school has a distinct advantage in this kind of situation, and the chair of the Math/CS department decided to allow me to do a creative study under him for the semester instead, with a focus in PHP/JavaScript/Web Programming (his specialty).  I was tasked with designing and building an Online Time Card system that will be used by the department to track tutor hours (as well as track if they log in/out on a department computer).

Luckily, I’ve been able to rip most of the code from my senior seminar class project (a voting application) and rewrite it for the time card system.  This has let me keep all the old cosmetic design, as well as given me class definitions and the functions that go along with them (not to mention the security stuff, what a life saver there for me!).  I’ve got the bulk of the program working now, though I still need to create a few admin side pages, but all in all the basics of the project are all in place. 

The whole project itself has been fantastic for me.  I left my senior seminar with an OK grasp on things like PHP and SQL queries, but I’m far more comfortable working in both now.  It’s been a blast (as frustrated as I get now and then) working out all the problems, and I look forward to learning how to use AJAX and JQuery once I finish the last few admin pages.  The fact that it is going to get used by the school makes the whole project feel more legitimate to me, and will look fantastic on my resume as I apply to jobs.

I’ve also come across some really cool functions when trying to solve issues with my own code, and one of the cooler ones I’ve seen is a way to convert seconds to a time in Hour:Minute:Second form.  It’s a creative use of the mktime() PHP function mixed with the PHP date() function, date("H:i:s",mktime(0,0,$seconds,0,0,0)).  The $total_time is the number of seconds you’re trying to convert.  For me, I have two unix time stamps from when the user logged in vs when they log out, so I take the difference between the two and plug it into the function.  Works like a charm, and credit goes to “Warz” on the Dev102 post http://www.dev102.com/2008/03/18/how-to-convert-minutes-to-hours-with-php/ .

 

“Mostly, when you see programmers, they aren’t doing anything.  One of the attractive things about programmers is that you cannot tell whether or not they are working simply by looking at them.  Very often they’re sitting there seemingly drinking coffee and gossiping, or just staring into space.  What the programmer is trying to do is get a handle on all the individual and unrelated ideas that are scampering around in his head.”
– Charles M. Strauss

C# – Closest Points on a 2-D graph

For my final project of Algorithm and Algorithm Analysis, I had to pick and write and non-trivial algorithm.  I choose to find the two points with the shortest distance on a 2-D plane.  That is two say, given a finite number of points in a 2-D space, which pair are the closest together?

There were three steps to the project:

1) Brute Force

The brute force of this algorithm is very simple.  Take the first point, check the distance between it and all others saving the lowest.  Take the second point, check it against all others saving the lowest.  Etcetera etcetera, on and on, until you go through all points, ending with the lowest.  Obviously the smarter version of the brute force would be to only check against those who haven’t already been checked, but that’s a trivial change code wise (which admittedly saves a lot of time).

The brute force looks like this:

public string closestBrute()
{
DateTime startTime = DateTime.Now;
double curDist;
double minDist = Double.MaxValue;
string point1 = “”;
string point2 = “”;
for (int i = 0; i < xCoor.Length -1; i++)
{
for (int j = i + 1; j < xCoor.Length; j++)
{
curDist = distance(xCoor[i], yCoor[i], xCoor[j], yCoor[j]);
if (curDist < minDist)
{
minDist = curDist;
point1 = pointList[i].getVal();
point2 = pointList[j].getVal();
}
}
}
DateTime stopTime = DateTime.Now;
TimeSpan duration = stopTime – startTime;

return “The closest points on this line are ” + point1 + ” and ” + point2 + ” at a distance of ” + minDist + ” and took ” + duration;
}

The distance method calculates using the standard sqrt((x2 – x1)^2 + (y2 – y1)^2) formula

2) Smart algorithm

The brute force is slow.  VERY slow.  Too slow to use if there are any sizable amount.  Thus, I had to figure out a way to cut the time down from n^2.  As it turns out, you can do pretty damn well.

My smart algorithm uses what’s known as the Plane Sweet method, the information of which I got from the fantastic site about this problem set up by a McGill student (http://www.cs.mcgill.ca/~cs251/ClosestPair/index.html).  The idea is to make a rectangle with sides d and 2d, where d is the current shortest value, from the point you’re checking and check only the points that fall into it.  There is a proof as to why this works at the website listed above, its pretty interesting.

The algorithm looks like this:

public string closestSmart()
{
DateTime startTime = DateTime.Now;
int xVertIndex;
double minDist = distance(xCoor[0], yCoor[0], xCoor[1], yCoor[1]);
double curDist;
bool check = true;
List<int> xHold = new List<int>();
List<int> yHold = new List<int>();
int i;
string point1 = “”;
string point2 = “”;

int index = 0;

while (index < xCoor.Length – 1)
{
xVertIndex = xCoor[index + 1];
i = index;
while (check)
{
int xCheck = 0;
int yCheck = 0;
try
{
xCheck = xCoor[i];
yCheck = yCoor[i];
}
catch
{
break;
}
i–;
if ((xCheck >= (xVertIndex – minDist)))
{
if ((yCheck <= yCoor[index + 1] + minDist) && (yCheck >= yCoor[index + 1] – minDist))
{
xHold.Add(xCheck);
yHold.Add(yCheck);
}
}
else //if(xCheck > xVertIndex)
{
check = false;
}
}//while(check)

for (int j = 0; j < xHold.Count; j++)
{
curDist = distance(xHold[j], yHold[j], xCoor[index + 1], yCoor[index + 1]);

if (curDist < minDist)
{
minDist = curDist;
point1 = “” + xHold[j] + “,” + yHold[j];
point2 = pointList[index + 1].getVal();
}
}
check = true;
xHold.RemoveRange(0, xHold.Count – 1);
yHold.RemoveRange(0, yHold.Count – 1);
index++;
}//while(index < xCoor.Length – 1)
DateTime stopTime = DateTime.Now;
TimeSpan duration = stopTime – startTime;

return “The closest points on this line are ” + point1 + ” and ” + point2 + ” at a distance of ” + minDist + ” and took ” + duration;
}

3) Threaded

This part was to simply make the smart algorithm into a multi-threaded process to speed it up.  I achieved this by splitting the list of points in half, with the right most point of the first half overlapping the left most of the second half, and running the algorithm on both halves, and then comparing the result.  There isn’t any real reason to post this code. . . so I wont!

Setting up the code:

This part should probably be mentioned.  I created a program which would generate a non-repeating coordinate pairs within a user defined limit and output them to a text file.  When the main program starts up, it takes these text files, reads each line into a coorPair object, and places that object into a list until the file is empty.  The list is then sorted by the list’s built in sort method. To allow this sorting, coorPair implements IComparable, as seen below.  Originally, I wrote a variation of merge sort that sorted all lists by only their X coordinates, but I realized later that I need them sorted by x and y. Thus I created the coorPair class and simplified the whole thing.

class coorPair : IComparable
{
CompareTo(Object o)
{
coorPair inCP = (coorPair)o;

if (x < inCP.getX())
return -1;
else if (x > inCP.getX())
return 1;
else
{
//This is the portion that determines the sort by subset
if (y < inCP.getY())
return 1;
else if (y > inCP.getY())
return -1;
else
return 0;
}
}
}

“From a programmer’s point of view, the user is a peripheral that types when you issue a read request.”
– P. Williams