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

}

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 = possibleU;
}
}

if(u == target) {
break;	// Exit the while loop!
}

unvisited.Remove(u);

foreach(Node v in u.neighbours) {
//float alt = dist + u.DistanceTo(v);
float alt = dist + 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][1]
[Part 2][2]
[Part 3][3]
[Part 4][4]
[Part 5][5]
[Part 6][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?
[1]: Civilization/Dungeon Tile Movement & Pathfinding #1 - YouTube
[2]: Civilization/Dungeon Tile Movement & Pathfinding #2 - YouTube
[3]: Civilization/Dungeon Tile Movement & Pathfinding #3 - YouTube
[4]: Civilization/Dungeon Tile Movement & Pathfinding #4 - YouTube
[5]: Civilization/Dungeon Tile Movement & Pathfinding #5 - YouTube
[6]: Civilization/Dungeon Tile Movement & Pathfinding #6 - YouTube

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.

Hello. I know this is an old post but I’ve been having this same problem with quill18creates tutorial and just recently discovered the solution, partially through the help of Bunny83’s post here. It was kind of difficult for me to parse exactly what he was saying (I’m pretty dumb, and only an amateur programmer) but eventually I got the code below to work. I have no idea if it’s optimal or not:

(Note, if it’s not obvious:

-“MoveSpeed” is an integer I’ve attached to all units that determines how far they can move in a single turn.

-The returned “validMoves” variable is a Node list that I use outside of this function to highlight movable tiles.)

``````public List<Node> dijkstraGetValidMoves()
{
Dictionary<Node, float> dist = new Dictionary<Node, float>();
Dictionary<Node, Node> prev = new Dictionary<Node, Node>();

//"Unvisited" is every node we have not visited
List<Node> unvisited = new List<Node>();
validMoves = new List<Node>();

Node source = graph[selectedUnit.tileX,
selectedUnit.tileY];

dist[source] = 0;
prev[source] = null;

foreach (Node node in graph)
{
if (node != source)
{
dist[node] = Mathf.Infinity;
prev[node] = null;
}
}

//While there are uncounted nodes, do stuff below
while (unvisited.Count > 0)
{
//**From QillCreates** Not fast but short,
//consider having "unvisited" be a priority queue or some other self-sorting data structure

//Node in list of "Unvisited" Node list with the minimum distance to the source
Node u = null;

foreach (Node possibleU in unvisited)
{
if (u == null || dist[possibleU] < dist)
``````

{
u = possibleU;
}
}
unvisited.Remove(u);
foreach (Node v in u.neighbours)
{
float alt = dist + CostToEnterTileAllUnits(v.x, v.y);
if (alt < dist[v] && alt <= selectedUnit.moveSpeed)
{
dist[v] = alt;
prev[v] = u;