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.

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.

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

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

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

... 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.

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.

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.

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.

DIARY:

The Real Dev Diary of the Dead

DIARY WRITTEN BY:

ZombieTom

ENTRY DESCRIPTION:

Development of Project Rome has been steaming ahead at an almost unmanageable rate. However, recently I hit a snag. In this second episode of the great game dev diary I explain, as best I can without being boring (I probably failed), the problem and how I solved it. If you're an amateur game maker yourself, you might want to read this one - it could get you out of a pickle.

DATE ENTRY UPLOADED:

02/07/2017

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