Path-finding: For players, for AI, and … part of game design?

Where does this fit in the game?

I desperately needed path-finding for two places:

  1. Moving AI across the map without them getting stuck the moment a sea or mountain lies in their way
  2. Automatically moving the player’s units long distances without them having to micro-manage every step

These are almost the same problem, except that the AI needs to also do some strategising, and the player’s moves have to be “not stupid” (i.e. don’t walk an unaccompanied Civilization-game Settler straight onto an enemy fortress; Suicide-by-Barbarian is never pretty).

But there were some surprises in store for me…

The secrets of Path-finding: A* for non-programmers

Many thousands of tutorials, book-chapters, presentations, etc have been written explaining the A-star / A* algorithm. But for the last 5 or so years, AmitP has been the king of explainers. Not only has he written the simplest, clearest explanations yet – with clear, concise source code – but he keeps going back and upgrading his years-old blog posts.

So … now you can read a webpage where every diagram is interactive. Go! Try it! You’ll soon find you understand A*, without any prior experience in programming needed.

A few years ago, I used Amit’s webpages as a guide to implementing A* myself. I’d used the algorithms plenty of times in the past, but had forgotten the precise details. Embarassingly, it took me most of a weekend to get it fully working inside Unity (Unity version 3! Long ago now…) with some basic debugging support.

Path-finding in half an hour

Today, with all his updates over the years … Amit’s pages have example source code for multiple languages, including C#. So I wondered how quickly I could get it up and running.

Here’s one of those times when I do something that makes me powerfully aware of a difference been “good” and “great” programmers. My process for adding this code to my game:

  1. Create a new Unity Scene
  2. Clone the “landscape generator” object-group, refactor the class to allow a “simple mode”
  3. Check that I can generate small landscapes with a lot of data removed: only position and height remain
  4. Clone my code for hovering over hexes, and use it to make something that shows the mouse hovering
  5. Build a simple UX system: Add code to draw a line between last-clicked-point and current-hover point
  6. Finally: copy/paste Amit’s algorithm
  7. Examine the compiler errors, and assess them
  8. Examine the code, and assess the quickest way to make it work in my game
  9. Modify the code, some minor improvements (change some restrictive “int” vars to “float”)
  10. Test it: works first time

Which of those steps was/were the most important? What did I actually do here – and where in the process did I type / download the code I was going to use? Why? … Exercises for the reader.

Step by step, with pics…

Simple landscape

Here I used my simplified landscape-generator to give me a small rolling landscape. Look how small it is – deliberately so that if anything went wrong, I could print out every single hex / map location to the screen, read through them all, and debug step-by-step in my head (or with pen and paper) what exactly had happened:

Screen Shot 2016-06-09 at 20.43.48

I cloned the code for mouse hovering, and made a white sphere appear embedded in whichever hex the mouse was over.

This is nothing new: this is adapting code I already had. It ought to work first time; that’s the point: I started by making sure it did, indeed, work before moving on to the new stuff. I also made sure I had simplified and isolated it, so I wouldn’t e.g. need to worry about “terrain types” (hills, plains, water) for the rest of this integration.

Drawing lines from start to current

Using Unity’s built-in Debug.DrawLine, I checked that I had the correct co-ords for start and finish:

Screen Shot 2016-06-11 at 00.00.23

Note: the green line only appears on left-hand side. It’s not present in the game itself, only in the internal debugging view. This is OK for me, but useless for players and playtesting. Let’s move swiftly on…

Implement Amit’s code and use it to find a path

Now I added in-game cubes along the line of the “path found by A*”, and used a different system to draw an in-game green line from start to finish:

Screen Shot 2016-06-09 at 20.44.11

This lets me debug if the path finding is going nuts, or using wrong co-ords due to a typo, or … or … etc. In fact, nothing was wrong at this point, and the debug lines confirmed it.

More ambitious: test more complex scenarios

So I increased the size and made sure there was a bigger range of bumpy land, give it something to pathfind around:

Screen Shot 2016-06-09 at 20.54.31

Screen Shot 2016-06-09 at 20.54.23

Note: in the second screenshot above, the path veers a long way to the left before coming to the finish. But if you think about it, it hasn’t gone out of its way at all: the number of steps is the minimum possible, but the nature of hex grids is that some directions give many different paths all with the same total distance travelled. It’s like travelling between two points in Manhattan, New York: you can take many different routes wiggling among the blocks, and they all end up the same distance, because you cannot take the short cut of flying in a straight line.

Penalties for climbing hills

If you only ever use A* for asking “how do my AI units walk around impassable mountains and seas?” then you’re wasting it. You’re making the CPU do tonnes more work than necessary. The power of A* is being not only very fast but also adaptive to very complex competing pressures on “best” route.

I added a penalty for going uphill, and a smaller boost for going downhill. Look what happens…

Screen Shot 2016-06-09 at 20.54.04

Screen Shot 2016-06-09 at 20.53.53

Now the computer is desperately trying to avoid changes in height, because of the inevitable uphill penalty.

But … if it absolutely has to go uphill anyway, it then tries to maximize its use of downhill slopes to win something back.

And in every case, it’s comparing it to “how far out of the way is this taking me? Is the gain in flatness worth the cost in extra walking distance?”

Impact on Game Design

Back to the start: has this solved my initial problems?

Well, yes, but … it’s also thrown up some very interesting game-design questions:

  • With small hexes, there’s a lot of room for tactical moves by units using the terrain for advantage
  • The more radical paths show how much auto-movement there could be
  • …and it’s controlled by a few simple numbers – no complex programming needed!

The expressive power here is enormous! As a game-designer, I get to setup the conditions (hills slow you down, unless you’re a Barbarian or have the hill-climber promotion, but going downhill speeds you up, more-so if you’re cavalry, unless you’re starting on a mountain slope, because cavalry can’t traverse mountains, but infantry and melee units can, and … and … and … and …).

…and the computer auto-generates some very complex behaviour, almost miraculously, out of that, with a tiny amount of programming. The core algorithm (courtesy of Amit) is barely 10 lines of code in total. Wow.

Civ games and micro-management

I recently read a quote from Sid Meier (original game designer for the first Civilization) where he said he’d added some of the core features to the game specifically to increase the amount of micro-management “so that players have something to keep them occupied”.

For me, that explained a lot. The micro-management is one of the most fun parts of the game – at the start, when its simple. Late on in the game, it’s boring, verging on soul-destroying for most people. I’ll keep coming back to this, but the balance of how much micro-management there is at any given moment in a Civ game is, in my opinion, one of the most important things to get right in gameplay terms.

What about path-finding?

This advanced auto-tactical movement system that’s emerging suggests I can gradually decrease the amount of micro-management as the player plays the game. Tier 1 units will have no path-finding, or very simplistic pathfinding that can merely walk around impassables (sea, for instance), but has no other optimizations.

As units become more advanced – Tier 2, Tier 3 – I’ll let the UX use a more nuanced pathfinder, taking into account more of the terrain. At this point in the game, the player has more units, and more to juggle – so they want to spend less time pathfinding by hand. If they want to do each tile one by one, they can of course still do this, the UX allows them to go one step at a time.

Ultimately, one of my desires with the game-design is to reach a point where whole armies can be automated. In the very late game I’d like to have it so that you can point at an enemy city and say “take it!”, and know that your existing units will automatically do so in an efficient and effective manner. This then frees up the player to spend more time on late-game activities – such as advanced diplomacy (missing from all Civ games since … well, forever), or designing those spaceships for the end-game…

Current implementation

Here’s the latest Progress video (by the way: the “latest” video is always available from the menu bar above), with many notes and overlays explaining what’s going on and why.

(NB: the video also has a sneak-peak of the “in-game tweaking” interface that playtesters will have access to when I finally launch the alpha-test; I want you guys changing the rules as you play, and sending me your discoveries of which tweaks are the most fun.)

I highly recommend watching through and seeing how the small tweaks affect the actual paths being discovered by A*.