This site uses strictly necessary cookies. More Information

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

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** 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);
}
}
```

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** by AceVanCleef
·
Jul 17, 2018 at 02:08 AM

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;
}
```

I have a question. If I wanted to limit this code so that moving diagonally would be 2 move points. How would I go about doing that?

### Your answer

### Welcome to Unity Answers

The best place to ask and answer questions about development with Unity.

To help users navigate the site we have posted a site navigation guide.

If you are a new user to Unity Answers, check out our FAQ for more information.

Make sure to check out our Knowledge Base for commonly asked Unity questions.

If you are a moderator, see our Moderator Guidelines page.

We are making improvements to UA, see the list of changes.