How do I highlight all available paths with Dijkstra's algorithm on a tile based map?

Questions & Answers
1

When I click on a character I want to see how far it can move on a square tile based map, with x amount of movement points that it has got (like Fire Emblem games). 1 movement point allows you to move one tile to the right, left, top or bottom.

I can highlight any tile I want, it’s simple, but the problem is that I can’t manage to create a list/array of all tile positions that the character can move on for me to highlight them all. I could do it if all characters had a constant amount movement points, but I feel that my game would benefit from having different units with different amounts of movement points.

My map has a graph and every tile has a list of other tile positions it is connected to. I tried making a function which finds those neighboring tiles, but it gets a bit crazy when you try to find the neighboring tiles of the neighboring tiles that I’ve found before and it saves the same tile positions more than once and it felt like there had to be a much more efficient way to do this.

On top of that, I would like it to take into account the cost to enter the tile ( e.g. swamp terrain costs 2 movement points to enter), but I feel like I’ll have to drop this.

Any help would be appreciated.

2

You’re on the right track with the tile objects and the graph of connecting tiles but I have a feeling you’re making the function harder than it needs to be. In a case like this where you need to chain through a relationship of child to parent in succession recursive functions are often the way to go. Assuming you have a Tile class that looks like this:

public class Tile {
	public int moveCost;
	public List<Tile> connected;
}

Then you can implement a recursive function to get the connected Tiles like this:

private List<Tile> validMoves;

void Start()
{
	validMoves.Clear();
	//Tiles initialized and startTile is the current Tile
	GetValidMoves(startTile, 42);
}

private void GetValidMoves(Tile startTile, int movePoints)
{
	validMoves.Add(startTile);
	for (int i = 0; i < startTile.connected.Count; i++)
	{
		int nextMoveCost = movePoints - startTile.connected*.moveCost*

_ if (nextMoveCost >= 0 && !validMoves.Contains(startTile.connected*))_
_ GetValidMoves(startTile.connected, nextMoveCost);
 }
}*_

3

I implemented a solution using Breadth First Search (BFS) in order to avoid the following two issues of the previous suggested solution:

  • !validMoves.Contains(startTile.connected* prevented from visiting all valid tiles a unit should be able to move onto.*
    - After removing !validMoves.Contains(startTile.connected*, tiles get visitied multiple times and duplicates will be added to List<Tile> validMoves.*
    ## BFS Concept ##
    Before showing my solution, I recommend watching this video explaining the concept of BFS in a short and simple manner:
    [Breadth First Search Algorithm][1]
    ## Get all tiles in a unit’s walking range ##
    Units have a certain amount of movePoints they can use to walk around. Tiles in the otherhand have topographical features such as grassland, forests and mountains. A forest is more expensive to walk on ( MovementCost ) than grassland. A mountain even more thus influencing how far a unit can actually walk.
    public List GetValidMoves(int startPosX, int startPosY, int movePoints)
    * {*
    * List validTiles = new List();*
    * int[,] distance = new int[BoardSizeX, BoardSizeY];*
    * for(int x = 0; x < BoardSizeX; ++x) {*
    * for (int y = 0; y < BoardSizeY; ++y) {*
    * distance[x, y] = Int32.MaxValue;*
    * }*
    * }*
    * distance[startPosX, startPosY] = 0;*
    * Queue queue = new Queue();*
    * queue.Enqueue( graph[startPosX, startPosY] );*
    * while (queue.Count > 0) {*
    * Node current = queue.Dequeue();*
    * foreach(Node neighbour in current.Neighbours) {*
    * if( distance[neighbour.x , neighbour.y] > movePoints) {*
    * int movementCost = GetTileTypeAt(neighbour.x , neighbour.y).MovementCost;*
    * distance[neighbour.x , neighbour.y] = movementCost + distance[current.x, current.y];*
    * if (distance[neighbour.x , neighbour.y] <= movePoints) {*
    * queue.Enqueue(neighbour);*
    * }*
    * }*
    * }*
    * if (distance[current.x, current.y] > 0 && distance[current.x, current.y] <= movePoints) {*
    * validTiles.Add(current);*
    * }*
    * }*

* return validTiles;*
* }*
## Attack Range ##
Here is a variation for getting all tiles that are attackable within a units maxAttackRange
public List GetTilesInAttackRange(int startPosX, int startPosY, int maxAttackRange, int minAttackRange)
* {*
* if (minAttackRange < 0) {*
* minAttackRange = 0;*
* Debug.LogError(“minAttackRange was below 0 and got corrected to 0”);*
* }*
* if (minAttackRange >= maxAttackRange) {*
* throw new System.ArgumentException(“MinAttackRange can’t be larger than or equal to MaxAttackRange.”);*
* }*

* List validTiles = new List();*
* int[,] distance = new int[BoardSizeX, BoardSizeY];*
* for(int x = 0; x < BoardSizeX; ++x) {*
* for (int y = 0; y < BoardSizeY; ++y) {*
* distance[x, y] = Int32.MaxValue;*
* }*
* }*
* distance[startPosX, startPosY] = 0;*
* Queue queue = new Queue();*
* queue.Enqueue( graph[startPosX, startPosY] );*
* while (queue.Count > 0) {*
* Node current = queue.Dequeue();*
* foreach(Node neighbour in current.Neighbours) {*
* if( distance[neighbour.x , neighbour.y] == Int32.MaxValue) {*
* distance[neighbour.x , neighbour.y] = 1 + distance[current.x, current.y];*
* if (distance[neighbour.x, neighbour.y] <= maxAttackRange) {*
* queue.Enqueue(neighbour);*
* }*
* }*
* }*
* if (distance[current.x, current.y] > minAttackRange && distance[current.x, current.y] <= maxAttackRange) {*
* validTiles.Add(current);*
* }*
* }*

* return validTiles;*
* } *
_*[1]: Breadth First Search Algorithm - YouTube