THE DEAD TIMES

DEAD ARE COMING...

The way forward: A pathfinding conundrum

I started this dev diary with the idea of having entries for particular topics such as one for Romans, describing troops and troop abilities, and another entry for Zombies, describing how they work in the game. I still plan to do that. However, I expected development to be fairly swift - after all, the basic 2-dimensional turn-based strategy gameplay appeared quite straightforward - allowing these 'one topic' entries to be released after each topic was implemented in the game; maintaining a timely, and regular, flow of information. Unfortunately, things have... not gone according to plan.

I was making excellent progress in my first dabble in the world of game creation but then I hit a stumbling block, a bump in the road. I was semi-prepared for it; pathfinding - getting a troop from tile A to tile B, and, because this is a strategy game like XCOM, highlighting the tiles that a troop can move to, taking into account obstacles and other units. Still, pathfinding has a "go-to solution"; ask anyone who knows about this stuff and they'll simply state A* (A star) before walking away, a smug look on their face at an amateur programmer correctly schooled. So, diligently, I implemented a custom A* algorithm for my game. I've struggled with the implementation before (in fact, my failure to get A* working led to the abandonment of an earlier game project) though after a few days fiddling around with open lists, heuristics and adjacency lists, I finally had things set up.

Now, troops can only move a certain number of tiles away from their current position, denoted by action points (AP). So my plan was simple, check each tile within the area limited by the number of AP a troop had, apply A* to determine the path to it, and only if the path to that tile was equal to or shorter than a troop's remaining AP would it be shaded. This would have been fine except for one property of A*; it does not always return the shortest path to a tile. You see, A*, starting from the destination tile, picks a direction which it "thinks" is the optimal way to go and starts generating a path back to the source tile using that initial direction. This gives the advantage of high speed (something game developers love) but the disadvantage that, although rare, the path returned - and a path will always be returned if there is one - may not be the shortest. Basically, what that meant for my game was that a few tiles that could easily be moved to, were incorrectly considered too far away because A* simply chose the wrong starting direction. In other words, A* was out and it was back to the proverbial drawing board.

I then had another concept but, again, after many days of furious keyboard tapping, this too, had to be abandoned. The future was dark and it was anything but orange. I tried the forums, both asking the question and searching for similar problems. However, the answers were always the same while never being clear; "It's simple graph-traversal, dude. Use Dijkstra's algorithm.", "Easy, 8-way floodfill - give me something difficult next time ya mook.". Obviously, I'm being flippant for humour but, to someone as unintelligent as me, these non-explained answers were not helpful. Then, after many more hours of frustrating Internet searches, I found the ideal solution - or if not an ideal one, a solution that had the enormous advantage of being likely to work. The concept, which I'll explain below for anyone who may be interested, came from an obscure publication, hidden in the bowels of the Internet (not really, "the bowels", that is maybe an exaggeration) titled Strategy2D: Turn-based Strategy Video Game Engine for Mobile Devices.

The 'all possible paths' algorithm

First, I took a basic setup - a troop that could move freely in all directions, limited only by that troop's AP.

All below screenshots are using programmer art which will be replaced with proper artist graphics for the final release of the game.

The setup

© Screenshot from Project Rome (my game)

Step 1

Then, the source tile (the tile the troop is on) is added to a queue, It is also added to a grid storing; it's coordinates, those coordinates paired into a single number for easy comparison, it's parent tile's coordinates (the coordinates of the tile moved from to reach this tile, -1, -1 in this case) and the cost in AP to reach that tile (again, 0 in this case).

Grid:

sourceTile_x sourceTile_y sourceTile_paired -1 -1 0

Queue:

sourceTile_x sourceTile_y

Tiles shaded light blue are currently in the queue.

It begins...

© Screenshot from Project Rome (my game)

Step 2

Next, the tile at the front of the queue is removed and all tiles adjacent to that tile are examined. If the following criteria are met by any of those adjacent tiles, that tile is added to the back of the queue. The tiles added to the queue are also added to the grid.

  • The tile is not a obstacle or unit
  • The tile has not been examined before (it is not already in the grid)
  • The tile is not outside the playable area of the game (the map)
  • Adding the AP needed to reach that tile from the tile that was removed from the front of the queue is less than the AP of the troop

It costs 2 AP to move to an adjacent tile, in any direction.

The parent of these newly added tiles is the tile removed from the front of the queue (the source tile). The cost to reach these tiles is the cost to reach the parent tile (0 as the troop does not need to move to the source tile - he is already there) plus the cost to move from the parent tile to any of its adjacent tiles (2).

Tiles shaded dark brown have been explored - they were previously on the queue and have been removed.

Grid:

sourceTile_x sourceTile_y sourceTile_paired -1 -1 0
adj1_x adj1_y adj1_paired sourceTile_x sourceTile_y 2
adj2_x adj2_y adj2_paired sourceTile_x sourceTile_y 2
adj3_x adj3_y adj3_paired sourceTile_x sourceTile_y 2
adj4_x adj4_y adj4_paired sourceTile_x sourceTile_y 2
adj5_x adj5_y adj5_paired sourceTile_x sourceTile_y 2
adj6_x adj6_y adj6_paired sourceTile_x sourceTile_y 2
adj7_x adj7_y adj7_paired sourceTile_x sourceTile_y 2
adj8_x adj8_y adj8_paired sourceTile_x sourceTile_y 2

Queue:

adj1_x adj1_y
adj2_x adj2_y
adj3_x adj3_y
adj4_x adj4_y
adj5_x adj5_y
adj6_x adj6_y
adj7_x adj7_y
adj8_x adj8_y

First expansion

© Screenshot from Project Rome (my game)

Step 3

The general loop is then repeated for the next tile at the front of the queue - ie. that tile is removed and all tiles adjacent to that tile are examined. If the following criteria are met by any of those adjacent tiles, that tile is added to the back of the queue. The tiles added to the queue are also added to the grid.

  • The tile is not a obstacle or unit
  • The tile has not been examined before (it is not already in the grid)
  • The tile is not outside the playable area of the game (the map)
  • Adding the AP needed to reach that tile from the tile that was removed from the front of the queue is less than the AP of the troop

The parent of these newly added tiles is the tile removed from the front of the queue (tile adj1). The cost to reach these tiles is the cost to reach the parent tile (2) plus the cost to move from the parent tile to any of its adjacent tiles (also 2).

You can see that tiles adj1.4, adj1.5 and adj1.6 have not been added to the queue or grid. This is because they are already in the grid as tiles adj2, the source tile and adj8 - the path to these tiles is already known.

Grid:

sourceTile_x sourceTile_y sourceTile_paired -1 -1 0
adj1_x adj1_y adj1_paired sourceTile_x sourceTile_y 2
adj2_x adj2_y adj2_paired sourceTile_x sourceTile_y 2
adj3_x adj3_y adj3_paired sourceTile_x sourceTile_y 2
adj4_x adj4_y adj4_paired sourceTile_x sourceTile_y 2
adj5_x adj5_y adj5_paired sourceTile_x sourceTile_y 2
adj6_x adj6_y adj6_paired sourceTile_x sourceTile_y 2
adj7_x adj7_y adj7_paired sourceTile_x sourceTile_y 2
adj8_x adj8_y adj8_paired sourceTile_x sourceTile_y 2
adj1.1_x adj1.1_y adj1.1_paired adj1_x adj1_y 4
adj1.2_x adj1.2_y adj1.2_paired adj1_x adj1_y 4
adj1.3_x adj1.3_y adj1.3_paired adj1_x adj1_y 4
adj1.7_x adj1.7_y adj1.7_paired adj1_x adj1_y 4
adj1.8_x adj1.8_y adj1.8_paired adj1_x adj1_y 4

Queue:

adj2_x adj2_y
adj3_x adj3_y
adj4_x adj4_y
adj5_x adj5_y
adj6_x adj6_y
adj7_x adj7_y
adj8_x adj8_y
adj1.1_x adj1.1_y
adj1.2_x adj1.2_y
adj1.3_x adj1.3_y
adj1.7_x adj1.7_y
adj1.8_x adj1.8_y

Second expansion

© Screenshot from Project Rome (my game)

Step 4

The general loop is then repeated again for the next tile at the front of the queue - ie. that tile is removed and all tiles adjacent to that tile are examined. If the following criteria are met by any of those adjacent tiles, that tile is added to the back of the queue. The tiles added to the queue are also added to the grid.

  • The tile is not a obstacle or unit
  • The tile has not been examined before (it is not already in the grid)
  • The tile is not outside the playable area of the game (the map)
  • Adding the AP needed to reach that tile from the tile that was removed from the front of the queue is less than the AP of the troop

The parent of these newly added tiles is the tile removed from the front of the queue (tile adj2). The cost to reach these tiles is the cost to reach the parent tile (2) plus the cost to move from the parent tile to any of its adjacent tiles (also 2).

You can see that tiles adj2.1, adj2.2, adj2.4, adj2.5, adj2.6, adj2.7 and adj2.8 have not been added to the queue or grid. This is because they are already in the grid as tiles adj1.2, adj1.3, adj3, adj4, the source tile, adj8 and adj1 - the path to these tiles is already known.

Grid:

sourceTile_x sourceTile_y sourceTile_paired -1 -1 0
adj1_x adj1_y adj1_paired sourceTile_x sourceTile_y 2
adj2_x adj2_y adj2_paired sourceTile_x sourceTile_y 2
adj3_x adj3_y adj3_paired sourceTile_x sourceTile_y 2
adj4_x adj4_y adj4_paired sourceTile_x sourceTile_y 2
adj5_x adj5_y adj5_paired sourceTile_x sourceTile_y 2
adj6_x adj6_y adj6_paired sourceTile_x sourceTile_y 2
adj7_x adj7_y adj7_paired sourceTile_x sourceTile_y 2
adj8_x adj8_y adj8_paired sourceTile_x sourceTile_y 2
adj1.1_x adj1.1_y adj1.1_paired adj1_x adj1_y 4
adj1.2_x adj1.2_y adj1.2_paired adj1_x adj1_y 4
adj1.3_x adj1.3_y adj1.3_paired adj1_x adj1_y 4
adj1.7_x adj1.7_y adj1.7_paired adj1_x adj1_y 4
adj1.8_x adj1.8_y adj1.8_paired adj1_x adj1_y 4
adj2.3_x adj2.3_y adj2.3_paired adj2_x adj2_y 4

Queue:

adj3_x adj3_y
adj4_x adj4_y
adj5_x adj5_y
adj6_x adj6_y
adj7_x adj7_y
adj8_x adj8_y
adj1.1_x adj1.1_y
adj1.2_x adj1.2_y
adj1.3_x adj1.3_y
adj1.7_x adj1.7_y
adj1.8_x adj1.8_y
adj2.3_x adj2.3_y

Third expansion

© Screenshot from Project Rome (my game)

... and on to completion

This process of removing tiles from the front of the queue, examining their adjacent tiles and adding those suitable to the back of the queue, continues until the queue is empty. At this point, the grid contains all tiles that a troop can move to and the paths needed to reach those tiles. I call this the troop's MMR (Maximum Move Range).

The tiles in the selected troop's MMR (apart from the source tile) are shaded to inform the player where that troop can move to, as shown in the screenshot below.

All your base are belong to us

© Screenshot from Project Rome (my game)

As an aside, the same algorithm works when obstacles or other units are inside a troop's movement range. I won't bore readers with another example here, I'll just put up a screenshot of the results.

Note that DEBUG mode is enabled so the wall tiles appear as flat grey tiles with a large W on them. This is only to make things clearer - the end game will not look like this.

Walls can be such assholes, blocking your movement!

© Screenshot from Project Rome (my game)

Constructing the path

The path to a destination tile can then by generated simply by grid lookups on paired tile coordinates. Firstly, the grid is searched for the paired destination tile coordinates and, from this row, the coordinates of the parent tile extracted. Then, pairing those parent tile coordinates, you find the coordinates of that parent tile's parent tile. This process is repeated until you come to the parent tile coordinates of -1, -1 marking the source tile and the end of the path.

The tiles that form the path are marked with special graphics to show how the selected troop would move in order to reach the chosen tile, as shown in the screenshot below.

The path ahead is clear

© Screenshot from Project Rome (my game)

Displaying the generated path before the move "order" is confirmed is of vital importance in Project Rome. Since each tile has different properties, moving over certain tiles, instead of others, can have consequences for the player's troops. For example, if they move over shingle, they may fall or break their ankle whereas moving over plain grass has no such hindrance. It will therefore be up to the player if they want to move a troop along the generated path or, taking the more cautious approach, move the troop individual tiles to avoid rough areas. There will, of course, be an undo move action in case a mistake was made but this is still to be implemented.

That is not the only thing left to implement for the movement system either. A big concern is layering; how will troops move between individual layers? How can a troop move from a tile on layer 1 to a tile on layer 2? Do you simply select a troop, switch to show the higher layer and draw the path as normal? This would be reasonable but what if the troop is in a building and switching to layer 2 hides the troop on layer 1? What about moving from a tile on layer 1 to a tile on layer 1 where the shortest path moves over a tile on layer 2 - how is this shown to the player? Clearly, more design work is required. Perhaps those passionate few who have bothered to read to this point, have some suggestions - I'd love to hear them.

Made with Kompozer

The Dead Times © Tom Clark 2013 onwards

'Universal Fruitcake' font sourced from www.fontsquirrel.com

Members

The Dead Times © Tom Clark 2013 onwards

Made with Kompozer

'Universal Fruitcake' font sourced from www.fontsquirrel.com