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

Question

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.

Answer 1

Best Answer

Answer by cjdev · Sep 09, 2015 at 08:07 PM

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[i].moveCost
         if (nextMoveCost >= 0 && !validMoves.Contains(startTile.connected[i]))
             GetValidMoves(startTile.connected[i], nextMoveCost);
     }
 }

Add comment · Show 1 · Share

AceVanCleef · Jul 17, 2018 at 12:31 AM 0

Share

While working on my own tile map based project, I noticed an issue in this suggested solution. "!valid$$anonymous$$oves.Contains(startTile.connected[i]" prevents the code from aquiring all valid$$anonymous$$oves. For example, the root tile R has its neighbours A (top), B (right), C (left) and D (bottom/below) around it, the algorithm will first go to A. A's neighbours will be now added. I call them A_1 to the right, A_2 to the top and A_3 to the left (A_4 is R and already included in validTiles). Sooner or later, A_3's neighbour will be processed. It's neighbour below is actually Tile C. Now because you check "!valid$$anonymous$$oves.Contains(startTile.connected[i])"), C can no longer be used to check for its own neighbours. The path from R to all its left neighbour is blocked.

I suggest to draw a 5x5 array on paper and emulate my steps I explained. This will help visualizing the issue.

Technically, you can easily fix this by removing "&& !valid$$anonymous$$oves.Contains(startTile.connected[i]" from the code, but this comes with the downside of adding duplicates to "List"valid$$anonymous$$oves. I suggest using the Breath first search algorithm.

Answer 2

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[i] prevented from visiting all valid tiles a unit should be able to move onto.
After removing !validMoves.Contains(startTile.connected[i], 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

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<Node> GetValidMoves(int startPosX, int startPosY, int movePoints)
     {
         List<Node> validTiles = new List<Node>();
         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<Node> queue = new Queue<Node>();
         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<Node> 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<Node> validTiles = new List<Node>();
         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<Node> queue = new Queue<Node>();
         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;
     }

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

2 Replies

BFS Concept

Get all tiles in a unit's walking range

Attack Range

Your answer

Follow this Question

Related Questions