Path planning, the noble art of getting from A to B, is an integral part of many games and has been the subject of a huge amount of research, not to mention wailing and gnashing of teeth. Like so many things though, pathing is something that the player will only notice when it fails – when it works it’s just another part of the game. There is more to path planning than work/fail however, and in fact the algorithms used, the decisions taken and the hacks compromises made can have a profound effect on gameplay.
From A To B
…via C, while avoiding D, minimising E, before F but not until G, unless H, while I.
For an introduction to path planning (or, more properly, motion planning) read Matt Klingensmith’s Overview of Motion Planning, quite possibly the most well-written and interesting article on the subject I’ve come across. Take it from me – I wrote a dissertation on the subject so I’ve read a frankly distressing number of papers and articles on the field.
Up to speed? Good. Now to gameplay.
Four ghosts and a pizza walk into a bar…
Let’s start with a really simple example, one that’s older than I am (only just). Pac-Man, as you know, features a simple maze patrolled by four ghosts – Blinky, Inky, Pinky and Clyde – who chase you down as you aim to eat all the delicious pellets. Given the extremely basic – by modern day standards at least – processing power and hardware available, there was a surprising amount going on with the ghosts. For one thing, they didn’t just chase you down, which would have quickly resulted in a cluster of four ghosts behind you, easily avoided. No, two of them chased you, a third aimed at a point a little ahead of you and the last followed you, but then switched to heading for the bottom-let corner when it got close. Three simple behaviours combined to form a much more elaborate game, where to the average player the ghosts seemed unpredictable and hard to avoid. To the masters of Pac-Man, the rules are exploitable and people have played perfect games, going through level after level until the counter runs out.
So, one of the first games to popularise path planning AI, over thirty years ago, did so by making decisions that directly affected gameplay.
Known Unknowns
As a concept, the fog of war is well established in strategy games, and in many ways can be considered “done”. But say you’re making a game, fog of war presents you with many design and gameplay decisions. the fog of war is intended to restrict your information about the state of the game outside of your immediate view, but that raises some issues with the way your units interact with it. For example, you’ve just started a game, you have a scout. You select your scout and send her across to the far side of the map by clicking on an unexplored area. Now your scout does one of two things: ignore the order because it was in unexplored ground, or try to get there. The first option is daft, negating the idea of a scout and leading to a painful level of micromanagement to move units around. The second is far more sensible, but… How does she get there. In theory, the scout has no more idea of what’s out there than you do. She could go as far as she could with the information she has, building up a map as she goes, or she could cheat and use information not available to you as the player.
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.
The latter makes for smoother gameplay, but then information intended to be hidden from you can leak out. If you click to the east and she heads north, you know immediately that there’s an obstacle in the way. Not a big deal in itself, but imagine a game where the terrain isn’t static – destructible rocks, closable gates, and so on. The path a unit takes can tell you a lot about a map’s state.
So again we see that the design of the path planning algorithms have a direct impact not just on the feel of the game, but on the actual mechanics themselves. Never was this more evident than in StarCraft…
Glitches and Hacks, Oh My
StarCraft, Brood War and StarCraft 2 form the most intense and online play in the genre, possibly the industry. Certainly no other games have tournaments, prizes, communities and personalities to match Blizzard’s masterpieces. It’s hard to believe that the designers and creators of the original StarCraft, a follow-on from the success of WarCraft 2, could have forseen, or even imagined, the culture that would form around it. It’s fascinating then to read about how during the game’s creation, resources and time led to some decisions, hacks and compromises that led to features that defined not only the game itself, but how it is compared with its successors.
Broodwar is more than just 1 or 2 of the aspects that people remember here and there. At its base level, Broodwar was about being able to control individual units better than the other guy could.
One of the game’s developers, Patrick Wyatt, wrote a wonderful piece giving a great insight into how the game’s path planning mechanics came – or often didn’t come – together.
Read that, then read this TeamLiquid forum post on how differences between Brood War’s and StarCraft 2’s path planning mechanism have led to not only different micro-management but also the entire feel and thrust of the game itself. These two paragraphs sum the whole thing up perfectly:
A lot of what was loved about Broodwar came from the fact that one needed to overcome the game itself. This need for proper execution meant that players would always make mistakes creating holes in their play that could be exploited by the opponent. The best players were the ones who either made the least mistakes (like Flash) or the ones who punished mistakes the most severely (like Hyvaa).
Players, for the most part, do not make execution mistakes in Starcraft 2. They do make strategic mistakes; and it is these strategic mistakes that are most taken advantage of. When you scout wrong, when you position wrong, or when you become too predictable—you suddenly get routed. This means that the best players are the ones who either make the fewest strategic blunders (Innovation) or are the ones who punish strategic mistakes the most severely (Soulkey).
…until it doesn’t work quite right
Path planning is hard, frustrating, complex, under-appreciated and far, far more important to a game than most people give it credit for. Which is why it remains one of the most interesting aspects of game development. It’s easy to imagine that path planning is “done”, but far from it. Never mind the increasing size and complexity of maps – Supreme Commander, or Left 4 Dead, for extreme examples – there is a depth and subtlety to the subject that can have a profound effect on a game, far beyond “can these units get from A to B without looking like morons”. Even though StarCraft 2 has demonstrably superior path planning than its predecessors, the changes this superiority made to the core gameplay have polarised fans. We’re at the stage now where you can’t just “improve” something, you have to assess how those improvements impact gameplay. More than that, what you as a developer see as an improvement might not be taken the same way by your players.
Getting from A to B without looking like morons helps, of course.