Starcraft 1 Pathfinding: A technical analysis

Imagine a Starcraft map as one big grid which is divided into hundreds of little squares. Most units, the smaller units (like marines and zerglings) occupy a single square while the larger units (such as dragoons and ultralisks) occupy multiple squares.

Starcraft 1 pathfinding grid

When a unit is issued a move command, the parameters of that command (the current location and destination in the grid) are run through the pathfinding algorithm which spits out an array of path coordinates. The unit then moves along the path, but it only goes 1 square at a time, one set of coordinates at a time. Each time it travels to a new square, it asks “is the next square along the path occupied?” If the answer is “no,” the unit keeps moving along the path. If the answer is “yes,” the unit waits a fraction of a second, and checks again. If the path is still unoccupied after a certain time increment, a new path is generated from the algorithm and the unit walks around the square that was unwalkable.

Another circumstance in which the path is re-calculated is when a new move command is issued while the unit is en route. This behavior has given rise to spam-clicking. The path is literally re-calculated each time you click, so technically a unit is finding the most efficient path at the point of time closest to the click. Because the grid (remember the starcraft map is just 1 big grid) which marks the walkable and unwalkable areas is constantly changing, so also are the results of the pathfinding algorithm. And the older those results are, the less efficient they will be. Hence: spam-clicking!

If you clicked your marine to go across the map, and a building gets placed in the middle of the map while the marine was en route, the original path calculated can no longer be considered accurate (because it was generated before the building was placed). A helper function detects when a path is no longer “accurate”. It asks “is the square in front of me occupied?” If no, it will continue along the path. If yes, it will wait, check again, and generate a new path if it is still occupied. All of this happens very quickly between animation frames.

At one point in the development of Strike Tactics, I utilized this same technique for pathfinding.

Notice how the units stop when they detect an object in front and politely wait for the object to move before continuing along the path? This is Starcraft 1 pathfinding. Units always remain visually separated at the expense of pathfinding efficiency. In other words, units take longer to get from point A to point B but they do so without walking on top of each other.

Here's a look at what the "helper function" which asks "is this node in front of me occupied?" looks like in Javascript. Each time a new node is walked to, the next node in the path is checked. If it's occupied, an interval begins (unit.waitInt) which waits for the node to become un-occupied. If it takes too long, the path is thrown out and a new one is calculated (in my game, setting the unit.goToTarget will cause the unit to find a new path). 

function checkGoToNextNode(unit) {

    if (unit.path[0] != undefined) {

        var grid = staticGrid;
        var findPathMatrixNodeSize = matrixNodeSize;

        if (unitDefinitions[unit.unitName].size == 'lg') {
            var findPathMatrixNodeSize = matrixNodeSizeLG;
            var grid = getGridCloneOfStaticLGFromStatic(unit);

        // lg units should reserve all 9 rather than just center 1
        var gridX = fnRound((unit.path[0] - (findPathMatrixNodeSize / 2)) / findPathMatrixNodeSize);
        var gridY = fnRound((unit.path[1] - (findPathMatrixNodeSize / 2)) / findPathMatrixNodeSize);

        // check if next path is walkable, if not, wait till it is
        if (grid.nodes[gridY][gridX].walkable || smoothPaths) {

            if (unit.nextWalkToNode != undefined) {
                var goToNodeCopy = [unit.nextWalkToNode.x, unit.nextWalkToNode.y];

      , (function(goToNodeCopy) {
                    return function() {
                })(goToNodeCopy), this);


            if (unitDefinitions[unit.unitName].size == 'lg') {
                // large units must reserve a node in the staticGrid to prevent other large units from going there
                var gridXInStatic = fnRound((unit.path[0] - (matrixNodeSize / 2)) / matrixNodeSize);
                var gridYInStatic = fnRound((unit.path[1] - (matrixNodeSize / 2)) / matrixNodeSize);

                staticGrid.nodes[gridYInStatic][gridXInStatic].walkable = false;

                unit.nextWalkToNode = staticGrid.nodes[gridYInStatic][gridXInStatic];

            } else {
                grid.nodes[gridY][gridX].walkable = false;

                unit.nextWalkToNode = grid.nodes[gridY][gridX];

        } else {

            if (unit.unitName != 'drone') {
                stopAnimationsNetwork(unit, false, 0);
            unit.waitInt = setInterval(function() {

                var distanceFromEnd = Phaser.Math.distance(unit.x, unit.y, unit.goingX, unit.goingY);

                if ((distanceFromEnd <= 100) && (unit.timesWaited > 3)) {
                } else if ((distanceFromEnd >= 100) && (unit.timesWaited > 20)) {
                    // find a new path
                    unit.goToTarget = {
                        'x': unit.goingX,
                        'y': unit.goingY


                if (grid.nodes[gridY][gridX].walkable) {
                    if (unit.nextWalkToNode != undefined) {
                        unit.nextWalkToNode.walkable = true;
                    unit.timesWaited = 0;
                    grid.nodes[gridY][gridX].walkable = false;
                    unit.nextWalkToNode = grid.nodes[gridY][gridX];




            }, 50);




If you think that's complicated and messy, consider that this is just one small component of the system. That to me, was a big red flag. The more complicated a system is, the more likely it will fail. Simpler systems work better because there are fewer things in them that can fail. 

I discovered this technique on my own through experimentation and had no idea Starcraft used it until I saw Day9’s video. Although Day9 doesn't appear to understand what is going on under the hood, he explains what the pathfinding system feels like to the player and what the gameplay implications are - it just made me think hard about what the units were doing when looking for a path. I came to realize the units were constantly stopping and going because they were asking "is this square occupied?" just like in my own implementation.

At some point in pre-alpha, I ditched this entire approach and revamped pathfinding to something much simpler. Instead of units constantly checking if the node they are about to walk to is occupied, the units simply maintain relative distance from each other when they walk. The only nodes which are marked as unwalkable are the start and end destinations. Even though the same grid structure is used, units don't move like they are playing hopskotch because a second algorithm (independent of the pathfinding algorithm) smooths the paths. This is the system currently used in Strike Tactics.

Early feedback from alpha testers was the impetus to overhaul pathfinding in this way, and as soon as I made the change, “pathinding” ceased to even be a topic of discussion among alpha testers. That to me proved the new pathfinding was good, because it did its job unnoticed. My reasoning is that If players notice your pathfinding, that’s when you know it’s bad. The contrapositive is that you don’t get praise for good pathfinding, because no one notices it. SC2 pathfinding is probably the best pathfinding system ever devised for a dynamic world. Units of all sizes miraculously find their way to destinations, without overlapping each other and without stopping. Despite this, the only discussions surrounding SC2 pathfinding are in relation to brood war pathfinding, and how it just doesn’t have the same charm to it. Brood War pathfinding is considered "fun" for some players, because it requires more micro-management to move your units effectively. 

Anyway, I don’t recall the last time someone complained about pathfinding in Strike Tactics, so I like to think it’s a solved problem at this point. The units simply go directly to their destination in the fastest way mathematically possible. It might not look as good as the original system where units always remain visually separated, but it certainly feels better. And if there’s anything I’ve learned, feel is much more important than looks. Players prefer more efficient unit movement and pathfinding over all else. They don't care how it looks. Truthfully, I don’t think anyone (other than me) has noticed that units occasionally walk on top of each other in Strike Tactics. Yet that was one of my greatest fears and where i spend 99% of my energy writing pathfinding. Funny, the things developers feel are important don’t always align with the things players feel are important.

In Starcraft 1, you will also notice that units move in grid-fashion. In simpler terms, units move like they are playing one giant game of hop scotch. A unit can move to the square in front, the square to the left, the square behind, etc. But what units can’t do is move forward 1 degrees, back 2 degrees, left 3 degrees, etc. Movement is strictly limited to cardinal direction: N, S, E, W and NE, NW, SE, SW, etc. This is why the movement feels so “blocky.” Units need to move like this because they need to be able to ask "is this node i am walking to occupied?" If they moved outside the grid (like in sc2), they would not be able to ask that question. 

If the path the algorithm spits out is most accurate when it is newly created, why didn’t Blizzard automatically recalculate the path instead of only recalculating it on click or when a unit bangs into another?

Because these calculations are expensive, even by modern computing standards. Depending on the size of the grid, and the algorithm used calculating hundreds of paths for hundreds of units 10 times a second adds up. Thus algorithms like A* are only run when needed, on click or when a unit gets stuck.

The difficulties in implementing pathfinding is never a simple as “determining the quickest route to get from point a to point b,” although gamers - and people who have never worked on pathfinding - probably assume it as such. A lot of devs seem to think good pathfinding is all about choosing good pathfinding algorithms, but that's an oversimplification. It's sort of like assuming Chevy can design the best car by simply realizing they need to use wheels to move the car. The wheel part is already a solved problem. The algorithm part is already a solved problem. The difficulty is in implementation. 

Since in an RTS game, the world is constantly changing, the problem is never as simple as determining the fastest route to get from point a to point b. In a changing world, the problem is determining the fastest route from point a to point b  while not bumping into objects c, d, e, f, g, etc, which are  by the way, constantly moving at various speeds an in various directions. The difference between solving dynamic world pathfinding and static world pathfinding is the difference between shooting a moving target and one which stands still.

Many modern RTS games avoid the problem altogether by simply doing overlap/collision checks on every frame and separating units which get too close (think of it like bumper cars). Starcraft 2 uses this technique to some extent, but the technique is CPU intensive. With SC1 pathfinding, the only real CPU-heavy stuff (computing the path with the algorithm) happens when you issue a click command or when a unit gets stuck and needs to generate a new path. But with collision detection, the CPU intensive stuff is happening every millisecond. It absolutely would not be possible with 1999 tech.


If anyone is interested in reading one of the original Starcraft developer's writing on this very subject you can read the article at:

Generic Cialis Soft Periactin Otc Where To Buy Tab Isotretinoin Visa <a href=>viagra</a> Cialis 20mg Effets Secondaires Glucotrol Antibiotics Without A Script

Generic Viagra From Us Pharmacy <a href=>cheapest cialis 20mg</a> Cialis Giornaliero Generico Cialis English

Levitra Fertilita Comparatif Cialis Viagra <a href=>achat viagra forum</a> Buy Diflucan No Prescription

Pillola Viagra Senza Ricetta Cytotec In South Africa <a href=>cialis without a doctor's prescription</a> Buy Isotretinoin Without Perscription

Cialis Alcool <a href=>cialis online</a> Buy Lasix 100mg Cephalexin Dog No Prescriptions Hydrochlorothiazide 25 Mg Without An Rx

Kamagra Alcohol Cialis 2 Day Delivery [url=]tadalafil cialis from india[/url] Is Cephalexin Good For Celulitis Propecia Direct Cialis Online

Order Now Amoxicilina Price Discount Pharmacy <a href=>generic viagra</a> Canadian Pharmacy Online Cialis Propecia Side Effects Temporary Zithromax For Tooth Abscess

Cytotec En Pharmacie Cialis Tablets For Sale Au <a href=>buy viagra online</a> All Day Chemist Retin A

Rezept Fur Viagra Cialis Sirve Para Diabeticos Pfizer Viagra Tablets <a href=>antabuse</a> Online Propecia Prescription Drugs Chewable Visgra

Online cialis generika kaufen <a href=>viagra</a> Achat Viagra Cialis Cialis Viagra Levitra Comparaison Amoxicillin Vs Strep Throat

Amazing loads of useful tips!
pharmacie canadienne
<a href="">canadian pharmacies</a>
pharmacy on line
<a href="">canadian pharmacy online</a>
drugstore online shopping -

<a href=""> pharmacy Bib</a> f6b3cb1

Superb data. With thanks.
canada pharmacies online prescriptions
<a href="">canadian online pharmacies</a>
canadian pharmacies that ship to us
<a href="">canadian online pharmacies legitimate by aarp</a>
online pharmacy without prescription -

<a href=" pharmacies-247 Si</a> 1a34e5e

You said it nicely..
<a href="">canadian drugs</a>
international pharmacies that ship to the usa -

<a href=>canadian online pharmacy reviews vect</a> a34e5eb

Wow lots of great data.
canada rx
<a href="">online pharmacies of canada</a>
canada prescription drugs
<a href="">online drugstore</a>
canada pharmacies prescription drugs -


Nicely put, Appreciate it!
legal canadian prescription drugs online
<a href="">canada pharmacy online</a>
canadian pharmacy online
<a href="">ed meds online without doctor prescription</a>
best canadian online pharmacy -

<a href="">pharmacies in canada Ker</a> b1a34e5

Nicely put. Thanks a lot!
prescription discount
<a href="">canada pharmaceutical online ordering</a>
canadian online pharmacies legitimate by aarp
<a href="">canadian pharmacy world</a>
canada prescriptions drugs -

<a href="">viagra from canada nef</a> b1a34e5

Wow plenty of beneficial material!
<a href="">london drugs canada</a>
canadian pharcharmy online fda approved -

[url=]canadian rx con[/url] e5ebdcb

Incredible tons of excellent data.
canada drugs online pharmacy
<a href="">londondrugs</a>
canadian drugs
<a href="">northwest pharmacy</a>
canadian pharmacies online -

<a href="">cheap prescription drugs Hism</a> 1af6b3c

Seriously a lot of excellent material!
ordering prescriptions from canada legally
<a href="">canadian pharmacy</a>
prescription drugs online without doctor
<a href="">canada pharmaceutical online ordering</a>
pharmacy online -

<a href=" meds online Ma</a> 66ead55

Nicely put. Many thanks!
top rated online canadian pharmacies
<a href="">canadian pharmacy viagra</a>
canadian drug store
<a href="">london drugs canada</a>
online pharmacy no prescription needed -

<a href="">prescription drugs prices et</a> af6b3cb

Cheers. Fantastic information!
<a href="">canadian pharmacies that ship to us</a>
drugstore online shopping -

[url=]canadian pharmacies-24h jast[/url] 2_69056

Nicely put, With thanks.
online discount pharmacy
<a href="">online canadian pharmacy</a>
best online pharmacies no prescription
<a href="">canadian pharcharmy</a>
online pharmacy without prescription -

<a href="">canadapharmacy com Jen</a> af6b3cb

Nicely put. Regards.
drugstore online
<a href="">canadian pharmaceuticals online</a>
list of approved canadian pharmacies
<a href="">canadian pharmacies</a>
canadian viagra -

<a href=" drug pharmacy ml</a> 6b3cb1a

Wonderful info. Cheers.
canadian pharmacy online canada
<a href="">london drugs canada</a>
canadian prescriptions online
<a href="">canadian drugs</a>
discount pharmacy online -

<a href=" canada Sort</a> 1af6b3c

Reliable material. Thanks a lot!
online pharmacy no prescription
<a href="">canada drugs</a>
canadian pharcharmy online
<a href="">canadian drugs</a>
safe canadian online pharmacies -

<a href="">canadapharmacy com Jen</a> ebdcb3a

You said this terrifically!
<a href="">canadian pharmacy king</a>
pharmacy prices -

[url= pharmacy online ml[/url] cb3a4c2

Seriously all kinds of great tips.
canadian pharmacy certified canada pharmacy online
<a href="">canadian online pharmacy</a>
compare prescription prices
<a href="">canadianpharmacy</a>
canadian drugs -

<a href=" canada drug database Si</a> 6066ead

Really lots of beneficial material!
prescription drugs online without
<a href="">canadian drug</a>
<a href="">canada pharmaceuticals online</a>
canadian pharmacies without an rx -

<a href=",-comprim%D0%93%C...(244-mg)_7680456820136.html">candrugstore com Ma</a> a4c0_50

You explained it fantastically.
canada pharmacy
<a href="">best 10 online canadian pharmacies</a>
canada pharmacy online reviews
<a href="">canadian pharcharmy</a>
drug stores near me -

<a href="">meds online without doctor prescription Jen</a> 6066ead

Nicely put. Regards.
prescription pricing
<a href="">legal canadian prescription drugs online</a>
northwest pharmacy/com
<a href="">health canada drug database</a>
mexican pharmacies -

<a href="">doctor prescription Oa</a> af6b3cb

Really a good deal of amazing data!
best canadian mail order pharmacies
<a href="">canadian pharmacy</a>
discount prescription drug
<a href="">canadian pharmacy king</a>
canadian pharcharmy online -

<a href="">safe canadian online pharmacies ki</a> 34e5ebd

Regards, Fantastic stuff.
<a href="">canadian pharmacy</a>
northwest pharmacy/com -

[url= pharmacy Kn[/url] 3_69056

Really a good deal of superb info!
discount pharmacy online
<a href="">online pharmacies</a> pharmacy
<a href="">canadian pharmaceuticals online</a>
list of legitimate canadian pharmacies -

<a href="">ed meds online Wame</a> e5ebdcb

Awesome info. Kudos.
canadian pharmacy world
<a href="">canada pharmacy</a>
mexican pharmacy online
<a href="">cvs pharmacy online</a>
pharmacy on line -

<a href="">online pharmacies in usa mn</a> 066ead5

Nicely put, Thank you!
<a href="">canada pharmacy online</a>
top rated online canadian pharmacies -

[url= of legitimate canadian pharmacies disp[/url] d551af6

Superb knowledge. Regards.
legitimate canadian mail order pharmacies
<a href="">london drugs canada</a>
best online canadian pharcharmy
<a href="">canada rx</a>
legitimate online pharmacies -

<a href="">londondrugs caf</a> dcb3a4c

Thank you! Plenty of facts!

online pharmacy
<a href="">canadian pharmacies</a>
prescription drugs prices
<a href="">online pharmacies</a>
mexican pharmacies shipping to usa -

<a href=" order pharmacies jepe</a> bdcb3a4

Appreciate it, Lots of write ups.

<a href="">canada pharmacy online</a>
cheap drugs online -

[url=]discount prescription drugs online Pi[/url] b1a34e5

Valuable data. Many thanks.
canadian prescription drugs
<a href="">canadian pharmaceuticals online</a>
prescription drug cost
<a href="">canadian online pharmacies legitimate</a>
canadapharmacyonline com -

<a href=" drugs pharmacy Nib</a> 66ead55

This is nicely put. !
board of pharmacy
<a href="">pharmacy online</a>
<a href="">canadian pharmacy online</a>
drugs without prescription -

<a href=" drugs</a> 551af6b

Cheers! Loads of knowledge.

no prior prescription required pharmacy
<a href="">ed meds online without doctor prescription</a>
rx price comparison
<a href="">canada pharmacy</a>
canadapharmacy com -

<a href="">canada drugs pharmacy Lom</a> ebdcb3a

Thanks a lot. I value it!
<a href="">canadian drug store</a>
overseas pharmacies -

[url=]pharmacies near me Sn[/url] 066ead5

Superb content. Thanks a lot.
overseas pharmacies
<a href="">canadian pharmacies</a>
<a href="">canadian pharmaceuticals online</a>
best canadian online pharmacies -

<a href=" pharmacies-247 Bumn</a> 6ead551

Kudos, Terrific information!
canada prescription plus pharmacy
<a href="">canadian pharmacies online</a>
buy prescription drugs canada
<a href="">canada pharmaceuticals online</a>
drug costs -

<a href="">canadian rx nex</a> 4e5ebdc

Kudos! I appreciate this.
canada prescription drugs
<a href="">ordering prescriptions from canada legally</a>
canadian meds
<a href="">canadian pharmacies that ship to us</a>
canadian pharmacies top best -

<a href="">viagra from canada ea</a> 1a34e5e

With thanks, Valuable information.
buy prescription drugs without doctor
<a href="">canadian pharmacy king</a>
canada prescription plus pharmacy
<a href="">pharmacy online</a>
rx price comparison -

<a href="">order prescriptions online without doctor vect</a> ead551a

Thanks! I value it!
<a href="">pharmacy online</a>
canada drugs pharmacy
<a href="">canadian online pharmacies</a>
global pharmacy canada -

<a href="">drugs from canada online Jen</a> 8_5ac9f

Nicely put, Thanks a lot!
canadian online pharmacies
<a href="">london drugs canada</a>
buy prescription drugs from canada
<a href="">ed meds online without doctor prescription</a>
pharmacy on line -

<a href=" king pharmacy Foes</a> 066ead5

You actually said this superbly.
canada rx
<a href="">canadian pharmaceuticals online</a>
safeway pharmacy
<a href="">canadian pharmacies online</a>
canadadrugstore365 -

<a href=" meds online en</a> 4c6_508