Pathfinding/Movement

This is part of a series on how this game was implemented technically, as part of the Game Jam it was developed for. It is recommended to read them roughly in-order as later blog entries may refer to earlier ones.

Technical:

1. State Machine
2. Pathfinding/Movement
3. Isometric Rendering
4. API
5. Control Sources
6. AI
7. Networking
8. Fog of War
9. Bit Packing
10. Palette Shifting

Other:

• Portraits
• Scrapped Ideas

----

Pathfinding/Movement

In order to implement the game, a core mechanic is needed that can generate the movement/attack grid. 

The movement grid is similar to many strategy games of a similar genre. Characters have a base movement amount that specifies how many tiles they can traverse, and then tiles have a terrain cost that may hinder movement. 

To fill the movement, we use a Breadth First Search. Essentially this does a flood-fill traversing outwards from the character's starting position. This can be done in two ways, using recursion or using a queue. For this implementation, the queue was preferable. Below is a cleaned-up version of the code used to fill movement for a character:

It's very short! only ~30 lines of code.

So, how does this work?

To start with, you need a queue that's appropriately sized to hold the movement information. For this implementation, the queue is just set to the grid area (Area = Width x Height) and is defined statically so it can be re-used.

------------------------------

For the diagram above, all cells have a 'cost' of 1. But in practice, they can have a cost >1. This algorithm will effectively take this into consideration and navigate "around" cells of high cost.

------------------------------

Filling Attack

The attack grid is much simpler to implement, given a source cell, it always fills the same pattern (in this game, it's always a diagonal square from min-range to max-range). Attack is not affected by terrain, so its shape is always the same.

Once movement is filled, the corresponding attack grid needs to be filled. This could be done by scanning across the whole game grid and checking "if cell is blue" and then filling in attack at that point.

But that involves scanning every cell, regardless of if they are filled or not. There's a much simpler way. We already have a complete list of all blue cells, the movement queue above!

Instead of discarding the movement queue after filling the grid, we return it. 

By looping over this queue, and calling "fillAttack()" we can populate the attack grid with no overhead. (one additional check is needed to make sure the blue cells are not occupied by an ally)

------------------------------

Pathfinding

In general, as long as you choose a source and destination that both land on a "blue" cell, you can be guaranteed there's a path from source->destination. This means for the majority of cases, no pathfinding is actually needed. Checking the "colour" of cell is sufficient to tell if it's valid.

(with the exception that the destination cell must not be occupied by a player character, you can move through ally units, but not on top of them)

That being said, there is one use-case for pathfinding. When the player is moving their mouse across the grid, a character will preferentially follow the path traced by the mouse. 

This is initially seeded by generating a path when the player moves their mouse. If the mouse is moved over neighbouring blue cells, the path will be progressively stored. But if the path gets too long (or is broken by moving the mouse off the grid) then it needs to be refreshed.

To generate a path, there's two potential approaches. The first is to simply scan the grid from small->big. Movement is guaranteed to be highest at the starting position. So just following the tiles from small->big will yield a valid path. The second approach (which is what was used) is to repeat the fill algorithm above, but store neighbours at each fill step. The final list of neighbours will be the path from source-destination.

 Pathfinding is (almost) completely cosmetic. For gameplay purposes, it doesn't matter how the character moves from source-destination. There's one exception, that's Fog of War. This will be explained in a later blog post, but Fog is revealed based on how a character moves. Allowing the user to specify which movement path to take allows them fine-grained control of how to move in fog.