• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 19:30
CEST 01:30
KST 08:30
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Maestros of the Game: Week 1/Play-in Preview5[ASL20] Ro24 Preview Pt2: Take-Off7[ASL20] Ro24 Preview Pt1: Runway132v2 & SC: Evo Complete: Weekend Double Feature4Team Liquid Map Contest #21 - Presented by Monster Energy9
Community News
Weekly Cups (Aug 18-24): herO dethrones MaxPax6Maestros of The Game—$20k event w/ live finals in Paris36Weekly Cups (Aug 11-17): MaxPax triples again!13Weekly Cups (Aug 4-10): MaxPax wins a triple6SC2's Safe House 2 - October 18 & 195
StarCraft 2
General
#1: Maru - Greatest Players of All Time Maestros of the Game: Week 1/Play-in Preview Greatest Players of All Time: 2025 Update BoxeR's Wings Episode 2 - Fan Translation A Eulogy for the Six Pool
Tourneys
Kirktown Chat Brawl #8 - 4.6K max Tonight Maestros of The Game—$20k event w/ live finals in Paris LiuLi Cup - August 2025 Tournaments $5,000 WardiTV Summer Championship 2025 $5,100+ SEL Season 2 Championship (SC: Evo)
Strategy
Custom Maps
External Content
Mutation # 488 What Goes Around Mutation # 487 Think Fast Mutation # 486 Watch the Skies Mutation # 485 Death from Below
Brood War
General
Post ASL20 Ro24 discussion. BGH Auto Balance -> http://bghmmr.eu/ Easiest luckies way to get out of Asl groups BW General Discussion No Rain in ASL20?
Tourneys
Cosmonarchy Pro Showmatches [ASL20] Ro24 Group F [IPSL] CSLAN Review and CSLPRO Reimagined! [ASL20] Ro24 Group E
Strategy
Simple Questions, Simple Answers Muta micro map competition Fighting Spirit mining rates [G] Mineral Boosting
Other Games
General Games
Path of Exile General RTS Discussion Thread Mechabellum Nintendo Switch Thread Stormgate/Frost Giant Megathread
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
US Politics Mega-thread Russo-Ukrainian War Thread YouTube Thread Things Aren’t Peaceful in Palestine Canadian Politics Mega-thread
Fan Clubs
INnoVation Fan Club SKT1 Classic Fan Club!
Media & Entertainment
Anime Discussion Thread Movie Discussion! [Manga] One Piece [\m/] Heavy Metal Thread
Sports
2024 - 2026 Football Thread Formula 1 Discussion TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread High temperatures on bridge(s) Gtx660 graphics card replacement
TL Community
The Automated Ban List TeamLiquid Team Shirt On Sale
Blogs
Lemme tell you a thing o…
JoinTheRain
How Culture and Conflict Imp…
TrAiDoS
RTS Design in Hypercoven
a11
Evil Gacha Games and the…
ffswowsucks
INDEPENDIENTE LA CTM
XenOsky
Customize Sidebar...

Website Feedback

Closed Threads



Active: 1110 users

Patrick Wyatt: The StarCraft path-finding hack

Forum Index > BW General
Post a Reply
1 2 3 4 Next All
Heyoka
Profile Blog Joined March 2008
Katowice25012 Posts
Last Edited: 2013-02-20 19:08:44
February 20 2013 19:02 GMT
#1
Patrick Wyatt was a programmer of Brood War who has shared a few awesome stories about the development of the game here and here. He’s back with a third installment, this time regarding an issue we’re all extremely close to: the pathfinding AI. It gives some amusing insight into the strange behavior of ramps and why workers have no collision size, among other things.

It’s a great read as always. Go read the whole thing here.

Code of Honor

The StarCraft path-finding hack


February 20, 2013 By Patrick Wyatt

Game-unit path-finding is something that most players never notice until it doesn’t work quite right, and then that minor issue becomes a rage-inducing, end-of-the-world problem. During the development of StarCraft there were times when path-finding just didn’t work at all.

As the development of StarCraft dragged on it seemed like it would never be done: the game was always two months from launch but never seemed to get any closer to the mythical ship date. “Fortunately” — and I use that term advisedly — Blizzard had previous experience shipping games late.

While we always had launch-date “goals” (though “wishes” might be a better term) we tried not to announce publicly until there was a good chance that the game would be ready at that point. Blizzard’s “when it’s done” policy for game launch was as much an admission that no one had any idea when we would finish as it was a commitment to releasing quality products.

In any event, towards the end of the project we had a set of problems that prevented launching. Like any game in the latter stages of the development process there were defects galore that needed to be found and repaired and the bug count still numbered in the thousands.

Many of those bugs were trivial, and needed only a little attention to fix. Too bad they weren’t all like that.

Others, like a multiplayer synchronization bug, would pop up and require dedicated attention from several members of the programming team — sometimes weeks of effort for a single problem. Other game developers have reported similar experiences with their sync bugs: Ages of Empires and Supreme Commander.

Some bugs were related to the development process itself. The Protoss Carrier regularly lagged behind other units because it had its own way of doing … everything. At some point in time the code for the Carrier was branched from the main game code and had diverged beyond any hope of re-integration. Consequently any time a feature was added for other units, it had to be re-implemented for the Carrier. And any time a bug was fixed for other units, a similar bug would later be found in the Carrier code too, only more devious and difficult to fix.

But the biggest thing holding back StarCraft was unit path-finding.

It wasn’t that the path-finding was totally broken; in most cases it worked quite well. But there were enough edge-cases that the game was un-shippable.

Game units would get stuck and stop on the battlefield. Often they would go through elaborate efforts to find paths, inching forward or looping around but not making progress, and sometimes getting wedged and unable to move further. Entire task forces would get bogged down in what looked like the afternoon commute.

The problem was frustrating for players, but also made the AI weak and consequently made it impossible to balance the missions, wasting design time.

Though I was never a top-tier RTS player, before the game launched I was good at the game because I discovered that Goliaths were overpowered to make up for their poor path-finding abilities. Because they were larger than other ground units they needed wider spaces for path-finding, and so by carefully shepherding Goliaths around obstacles I was able to bring their firepower to bear in crucial situations to overcome “macro” players who would otherwise tear me to shreds. Sadly my skills only lasted a short while until the Goliaths were rebalanced. sigh

Early path-finding was rough — while there were well-chosen algorithms driving unit movement they were handicapped by some poor development decisions made during the course of the project.

***


Read the rest at Patrick's site
@RealHeyoka | ESL / DreamHack StarCraft Lead
Sayle
Profile Joined October 2010
United Kingdom3685 Posts
February 20 2013 19:06 GMT
#2
Oh man I thought this would be a thread about a new hack to give BW units good path-finding. Was hoping for Pucca vs the world in yet another thread.

This is much less entertaining :/
amazingxkcd
Profile Blog Joined September 2010
GRAND OLD AMERICA16375 Posts
February 20 2013 19:07 GMT
#3
so basically, everything is higher res of warcraft engine for pathing?
The world is burning and you rather be on this terrible website discussing video games and your shallow feelings
andiCR
Profile Blog Joined March 2008
Costa Rica2273 Posts
February 20 2013 19:11 GMT
#4
Thanks. This blog is beyond awesome, and any programmer, specially a games programmer, will enjoy this series inmensely. I can only imagine what the Carrier code was like, and this bugs are directly correlated with the old inheritance model being adapted to games. If this game was made in components, they would've had wayyyy less code copypaste syndrome, and a much more dynamic model to approach bugs.
Nightmare1795 wrote: I played a guy in bronze who said he was Japanese. That was the only game I ever dropped a nuke, which was purely coincidental.
okum
Profile Blog Joined February 2009
France5778 Posts
February 20 2013 19:17 GMT
#5
To handle all the tricky edge-cases, the pathing code exploded into a gigantic state-machine which encoded all sorts of specialized “get me out of here” hacks.

This explains everything.
Flash fan before it was cool | Coiner of "jangbang"
PassiveAce
Profile Blog Joined February 2011
United States18076 Posts
February 20 2013 19:18 GMT
#6
Sadly my skills only lasted a short while until the Goliaths were rebalanced. sigh

I found this very funny aha!

Thanks for sharing this!
Call me Marge Simpson cuz I love you homie
thezanursic
Profile Blog Joined July 2011
5488 Posts
February 20 2013 19:28 GMT
#7
Finally I enjoyed his last two so much!
http://i45.tinypic.com/9j2cdc.jpg Let it be so!
Patton3D
Profile Joined March 2011
United States65 Posts
February 20 2013 19:40 GMT
#8
This entire blog series is incredibly interesting to read.
You are never defeated until you admit it.
mierin
Profile Joined August 2010
United States4943 Posts
February 20 2013 19:50 GMT
#9
On February 21 2013 04:40 Patton3D wrote:
This entire blog series is incredibly interesting to read.


It really is! I wonder why just now these blogs are starting to come out...in any case, hope for many more!
JD, Stork, Calm, Hyuk Fighting!
sabas123
Profile Blog Joined December 2010
Netherlands3122 Posts
February 20 2013 19:53 GMT
#10
awsome read

thanks for sharing
The harder it becomes, the more you should focus on the basics.
Antisocialmunky
Profile Blog Joined March 2010
United States5912 Posts
February 20 2013 19:53 GMT
#11
So he's responsible for this:
[゚n゚] SSSSssssssSSsss ¯\_(ツ)_/¯
Marine/Raven Guide:http://www.teamliquid.net/forum/viewmessage.php?topic_id=163605
shaftofpleasure
Profile Blog Joined December 2011
Korea (North)1375 Posts
February 20 2013 19:55 GMT
#12
AWESOME! bw forever!
It's either the holes of my nose are getting smaller or my fingers are getting bigger. /// Always Rooting for the Underdog. Hyuk/Sin/Jaehoon/Juni/Hyvva/Hoejja/Canata //// Hiding in thread somewhere where BW is still in it's pure form here on TL.
Pimpmuckl
Profile Joined March 2011
Germany528 Posts
February 20 2013 20:02 GMT
#13
On February 21 2013 04:11 iPAndi wrote:
Thanks. This blog is beyond awesome, and any programmer, specially a games programmer, will enjoy this series inmensely. I can only imagine what the Carrier code was like, and this bugs are directly correlated with the old inheritance model being adapted to games. If this game was made in components, they would've had wayyyy less code copypaste syndrome, and a much more dynamic model to approach bugs.


Couldn't agree more, pure awesomesauce right there
twitter.com/pimpmuckl
Nerevar
Profile Joined January 2013
547 Posts
February 20 2013 20:03 GMT
#14
[image loading]Patrick Wyatt: 1

(P)BeSt: 0
Wohmfg
Profile Blog Joined January 2009
United Kingdom1292 Posts
February 20 2013 20:06 GMT
#15
I love how these little quirks in games add so much to the top level of play.

How a game can be so perfect without being engineered that way.
BW4Life!
dRaW
Profile Blog Joined January 2010
Canada5744 Posts
February 20 2013 20:19 GMT
#16
On February 21 2013 04:06 Sayle wrote:
Oh man I thought this would be a thread about a new hack to give BW units good path-finding. Was hoping for Pucca vs the world in yet another thread.

This is much less entertaining :/



I was just thinking this, so I went offline and punched in all the cheat codes and smashed 7 PCs in frustration.
I don't need luck, luck is for noobs, good luck to you though
Andre
Profile Blog Joined August 2009
Slovenia3523 Posts
February 20 2013 20:33 GMT
#17
On February 21 2013 05:06 Wohmfg wrote:
I love how these little quirks in games add so much to the top level of play.

How a game can be so perfect without being engineered that way.

There's a lot of cool stuff that wasn't intended to be as the developers imagined it.

Besides all the cool tricks there are in BW, Quake had bunnyhopping( i think it was first "introduced" in doom..not sure), GunZ has a bunch of animation-based tricks. Like Wall cancelling etc.

You must gather your party before venturing forth.
SpeaKEaSY
Profile Blog Joined December 2010
United States1070 Posts
February 20 2013 20:36 GMT
#18
On February 21 2013 04:53 Antisocialmunky wrote:
So he's responsible for this:
http://www.youtube.com/watch?v=d1bPv8JI6zY


ahahahaha classic bisu face

I love this series, hope we can see more, it's been very insightful and nostalgic
Aim for perfection, settle for mediocrity - KawaiiRice 2014
ProMeTheus112
Profile Joined December 2009
France2027 Posts
February 20 2013 20:41 GMT
#19
:D this is awesome
<3 bw
BigFan
Profile Blog Joined December 2010
TLADT24920 Posts
Last Edited: 2013-02-20 20:44:44
February 20 2013 20:44 GMT
#20
These blogs are always amazing to read. Seems like they didn't rewrite path finding after changing the tileset, someone correct me if I'm wrong. On the bright side, we got a lot of cool tricks like drone drills and such so win win? That best vs. July game though, the look on Bisu's face was priceless XD
Former BW EiC"Watch Bakemonogatari or I will kill you." -Toad, April 18th, 2017
1 2 3 4 Next All
Please log in or register to reply.
Live Events Refresh
Next event in 12h 30m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Nathanias 156
StarCraft: Brood War
Shuttle 457
sSak 146
NaDa 12
Counter-Strike
fl0m1648
Stewie2K525
Super Smash Bros
AZ_Axe155
Other Games
tarik_tv29874
gofns17858
summit1g8715
FrodaN2571
Grubby2403
JimRising 399
KnowMe173
Livibee89
ViBE29
Organizations
Other Games
gamesdonequick1639
BasetradeTV20
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 19 non-featured ]
StarCraft 2
• davetesta94
• musti20045 41
• Kozan
• sooper7s
• AfreecaTV YouTube
• Migwel
• intothetv
• LaughNgamezSOOP
• IndyKCrew
StarCraft: Brood War
• iopq 5
• STPLYoutube
• ZZZeroYoutube
• BSLYoutube
Dota 2
• masondota22576
• Ler48
League of Legends
• Doublelift4004
Counter-Strike
• imaqtpie968
• Shiphtur152
Other Games
• Scarra299
Upcoming Events
SC Evo League
12h 30m
Maestros of the Game
16h 30m
SHIN vs Creator
Astrea vs Lambo
Bunny vs SKillous
HeRoMaRinE vs TriGGeR
BSL Team Wars
19h 30m
Team Bonyth vs Team Sziky
BSL Team Wars
19h 30m
Team Dewalt vs Team Sziky
Afreeca Starleague
1d 10h
Soulkey vs BeSt
Snow vs Light
Monday Night Weeklies
1d 16h
Replay Cast
2 days
Sparkling Tuna Cup
2 days
PiGosaur Monday
3 days
LiuLi Cup
3 days
[ Show More ]
Replay Cast
4 days
The PondCast
4 days
RSL Revival
4 days
Maru vs SHIN
MaNa vs MaxPax
RSL Revival
5 days
Reynor vs Astrea
Classic vs sOs
BSL Team Wars
5 days
Team Bonyth vs Team Dewalt
CranKy Ducklings
6 days
RSL Revival
6 days
GuMiho vs Cham
ByuN vs TriGGeR
Cosmonarchy
6 days
TriGGeR vs YoungYakov
YoungYakov vs HonMonO
HonMonO vs TriGGeR
[BSL 2025] Weekly
6 days
Liquipedia Results

Completed

Acropolis #4 - TS1
WardiTV Summer 2025
HCC Europe

Ongoing

Copa Latinoamericana 4
BSL 20 Team Wars
KCM Race Survival 2025 Season 3
BSL 21 Qualifiers
ASL Season 20
CSL Season 18: Qualifier 2
Maestros of the Game
SEL Season 2 Championship
Sisters' Call Cup
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
FISSURE Playground #1
BLAST.tv Austin Major 2025

Upcoming

CSL 2025 AUTUMN (S18)
LASL Season 20
2025 Chongqing Offline CUP
BSL Season 21
BSL 21 Team A
Chzzk MurlocKing SC1 vs SC2 Cup #2
EC S1
BLAST Rivals Fall 2025
Skyesports Masters 2025
IEM Chengdu 2025
PGL Masters Bucharest 2025
Thunderpick World Champ.
MESA Nomadic Masters Fall
CS Asia Championships 2025
ESL Pro League S22
FISSURE Playground #2
BLAST Open Fall 2025
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2025 TLnet. All Rights Reserved.