- Home /

# How do you use Dijkstra's Algorithm to show which tiles characters can get to each turn?

Hello. I am trying to make a turn-based strategy RPG like Fire Emblem, Shining Force, etc., in which the players move their characters on a tile-based battlefield, but the characters can only move a limited distance (a limited number of tiles) each turn, and typically the tiles they can move to become tinted or highlighted. I have read that Dijkstra's algorithm, and some others, can be implement in a way that will allow the player to see this movement range indicator, but I can't figure out how to implement it in such a way. Here is the algorithm-relevant part of a code I got from a tutorial video series by quill18creates:

```
public void GeneratePathTo(int x, int y) {
// Clear out our unit's old path.
selectedUnit.GetComponent<Unit>().currentPath = null;
if( UnitCanEnterTile(x,y) == false ) {
// We probably clicked on a mountain or something, so just quit out.
return;
}
Dictionary<Node, float> dist = new Dictionary<Node, float>();
Dictionary<Node, Node> prev = new Dictionary<Node, Node>();
// Setup the "Q" -- the list of nodes we haven't checked yet.
List<Node> unvisited = new List<Node>();
Node source = graph[
selectedUnit.GetComponent<Unit>().tileX,
selectedUnit.GetComponent<Unit>().tileY
];
Node target = graph[
x,
y
];
dist[source] = 0;
prev[source] = null;
// Initialize everything to have INFINITY distance, since
// we don't know any better right now. Also, it's possible
// that some nodes CAN'T be reached from the source,
// which would make INFINITY a reasonable value
foreach(Node v in graph) {
if(v != source) {
dist[v] = Mathf.Infinity;
prev[v] = null;
}
unvisited.Add(v);
}
while(unvisited.Count > 0) {
// "u" is going to be the unvisited node with the smallest distance.
Node u = null;
foreach(Node possibleU in unvisited) {
if(u == null || dist[possibleU] < dist[u]) {
u = possibleU;
}
}
if(u == target) {
break; // Exit the while loop!
}
unvisited.Remove(u);
foreach(Node v in u.neighbours) {
//float alt = dist[u] + u.DistanceTo(v);
float alt = dist[u] + CostToEnterTile(u.x, u.y, v.x, v.y);
if( alt < dist[v] ) {
dist[v] = alt;
prev[v] = u;
}
}
}
// If we get there, the either we found the shortest route
// to our target, or there is no route at ALL to our target.
if(prev[target] == null) {
// No route between our target and the source
return;
}
```

Here are the videos, which each contain a link to his website in the description, which contains a link to the complete project: Part 1 Part 2 Part 3 Part 4 Part 5 Part 6

So, how would I modify the code so that I could click on a character, and highlight all the tiles it can get to?

**Answer** by Bunny83
·
Apr 12 at 01:39 AM

Well, Dijkstra usually counting up the distance you already travelled in order to determine the shortest path. If you revisit a tile with a shorter route you will replace the value of that tile with the better score. If you want a limited distance you usually doing the same thing upside down. So you start with your limited amount of moves. Each move you subtract the cost from one tile to the next. This time if you revisit a tile with a larger value you prefer the larger value (since we want to get as far as possible). Once the value reaches 0 you reached the max distance you can travel. You simply highlight every tile with a non zero value. How you setup your tiles and how much a single move between two tiles cost is up to you and if you want to implement some kind of different terrain types (rocky mountains are more difficult to travel than flat terrain for example). We also don't know what kind of tiles you talk about (square grid, hex grid, some other non-symetric graph) and what moves are allowed (only horizontal/vertical or also diagonal on a square grid).

Anyways Dijkstra works the same for any kind of node graph. You just have to decide how your graph looks like.

Your break condition is no longer your target tile since we don't have one. Instead you stop once the open list is empty. Keep in mind that tiles which reach a score of 0 or below must not add their neighbors to the open list since we run out of moves. When you use a "closed list" (a list of visited nodes) you essentially got all the tiles you want to highlight. If you also pushed the border nodes (those with a value smaller than 0) onto the closed list, you may want ti filter them out.

Note that the implementation you have posted in your question is based on the first pseudo code example on the wiki. However it's one of the worst implementations possible. For each node you check you iterate through all remaining nodes. Since you are only interested in a few nodes that are in reach of the start node, it makes more sense to add the neigbors to the open list when a node is processed. Of course when a node is already on the closed list you don't add it again.

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

### Follow this Question

### Related Questions

Generating Triangles Given a Set of Points 1 Answer

Trail renderer algorithm? 0 Answers

Tile to Sphere world algorithm 1 Answer

Path finding algorithm for 2d game 2 Answers

Foreach with where with 2 lists 0 Answers