However, I found that not very useful when it comes to 2D and tile map kind of games. It is of course possible to use it if you decide to utilize quads and planes, but I wanted to implement my own path finding system.
It turns out, it is not really hard, especially when there are algorithms out there that have been tested and used for years. For this project, I will show you how I wrote my "own version" of the Dijkstra algorithms. No, not the guy from The Witcher 3.
I will not post the whole project code as it is extensive and rather messy at this stage, however, I will put the main functions and classes needed.
First of all, we need a map, a simple grid of objects and our player of course.
In my experiment I created a small "level editor" by coding a custom editor so it would be easier to layout an awesome map.
And this is the awesome map itself:
Awesome indeed.
As you can see, I have 3 types of tiles: the "grass" tile, green color, the "sand" tile, yellow(ish) color and the "wall" tile, grey color.
The reason is to show how smart this algorithm can be. Every type of tile has a "cost": the grass tile costs 1 to move in to, the sand tile 15 and the wall is pretty much set to infinity.
When calculating the path you will see that the player (the little capsule on the bottom left corner) will attempt to avoid the sand when possible as it is "too expensive" to move in to. In simple words, it will try to find the least expensive path, which is not necessarily the shortest.
Here's a picture which illustrates this:
The player is trying to get to the tile in the red circle. It could very well cross the "sand field" by walking straight down south, instead, the calculated path would rather go around it. Each sand tile costs 15 action points (let's call them such) to move in to, and the player would have 5 sand tiles in front of him to reach the target tile, which makes a total of 75. By going around it as shown by the line, he would have to traverse 10 grass tiles, which cost 1 AP each, for a total of 10. So, 10 APs are much cheaper than 75.
The first class we need is the Node class:
public class Node { public List<Node> tileNeighbors; public Map mapReference; public int x, y; public float distanceFromSource; public Node previousNode; public Node() { tileNeighbors = new List<Node>(); //Debug.Log ("List initialized"); } public float DistanceTo(Node n) { float d = 0; Vector3 current = mapReference.GetTilePositionAt(x, y); Vector3 to = mapReference.GetTilePositionAt(n.x, n.y); d = Vector2.Distance(current, to); return d; } }
This class represents each tile on the map. The most important parameters in this class are: the list of nodes, which will contain all the neighbors tiles, the float distanceFromSource, which is the tile's physical distance form the source and a reference to the previous Node with the shortest path.
As part of the Dijkstra algorithm, we need to generate a so called "graph" with this Node class.
A graph is nothing but a two dimensional array of nodes.
void GeneratePathGraph() { graph = new Node[mapWidth, mapHeight]; //Populate neighbours list for (int x = 0; x < mapWidth; x++) { for (int y = 0; y < mapHeight; y++) { graph[x, y] = new Node(); graph[x, y].mapReference = this; graph[x, y].x = x; graph[x, y].y = y; } } for (int x = 0; x < mapWidth; x++) { for (int y = 0; y < mapHeight; y++) { if (x > 0) { graph [x, y].tileNeighbors.Add (graph [x - 1, y]); //Diagonals /* if (y < mapHeight - 1) { graph [x, y].neighbours.Add (graph [x-1, y + 1]); } if (y > 0) { graph [x, y].neighbours.Add (graph [x-1, y - 1]); }*/ } if (x < mapWidth - 1) { graph [x, y].tileNeighbors.Add (graph [x + 1, y]); //Diagonals /* if (y < mapHeight - 1) { graph [x, y].neighbours.Add (graph [x+1, y + 1]); } if (y > 0) { graph [x, y].neighbours.Add (graph [x+1, y - 1]); }*/ } if (y > 0) { graph [x, y].tileNeighbors.Add (graph [x, y - 1]); } if (y < mapHeight - 1) { graph [x, y].tileNeighbors.Add (graph [x, y + 1]); } } } }
With this function I generate this array and populate it with nodes. Also, through a second iteration, I populate the list of neighbors of each node with the neighbors tiles. As you can see, I commented out the diagonal tiles, and that is simply because I do not want diagonal movement. If you wish to have it, simply uncomment those lines.
Now, to the path generating function.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | public void GeneratePath() { List<Node> uncheckedNodes = new List<Node>(); List<Node> currentPath = new List<Node>(); Node sourceNode = graph[unitToMove.GetComponent<Unit>().currentTileX, unitToMove.GetComponent<Unit>().currentTileY]; Node targetNode = graph[targetX,targetY]; sourceNode.distanceFromSource = 0; sourceNode.previousNode = null; foreach (Node n in graph) { if (n != sourceNode) { n.distanceFromSource = Mathf.Infinity; n.previousNode = null; } uncheckedNodes.Add (n); } while (uncheckedNodes.Count > 0) { Node nodeWithMinDistance = GetNodeWithMinDistance (uncheckedNodes); if (nodeWithMinDistance == targetNode) break; uncheckedNodes.Remove (nodeWithMinDistance); foreach (Node n in nodeWithMinDistance.tileNeighbors) { float distance = nodeWithMinDistance.distanceFromSource + n.DistanceTo(nodeWithMinDistance)+ GetTileMovementCost (n.x, n.y); if (distance < n.distanceFromSource) { n.distanceFromSource = distance; n.previousNode = nodeWithMinDistance; } } } // Close while if (targetNode.previousNode == null) { Debug.Log ("No Path foud"); line.SetVertexCount (0); } else { Node current = targetNode; while (current != null) { currentPath.Add (current); current = current.previousNode; } currentPath.Reverse (); unitToMove.GetComponent<Unit> ().currentPath = currentPath; DrawPath (currentPath); } } |
Declare 2 lists of nodes, one for the unvisited nodes and the other one which will hold the generated path.
After that, create 2 node, the source node and the target node. The source node coordinates are taken from the Unit script, which is attached to the player. The script simply raycast downwards and detect the tile underneath and retrieves its coordinates, so it is constantly updated.
Similar thing for the target node, this time the mouse will update the coordinates, again, by raycast.
We then initialize the source node: its distance from the source is 0 (that node IS the source) and there's no previous node before it.
Next, we initialize every node in the our graph array: set their distance to infinity and the previous node reference to null. Also, add every node to the list of unvisited nodes.
On line 28 we start iterating inside this list. We create a temporary node object (nodeWithMinDistance ) and we set it to the node in the list with the least distance from the source. That's what the method GetNodeWithMinDistance(...) does, simply iterates inside the list and return the one with the minimum distance. In the first iteration, it should return the source node, as it has a distance of 0 and all the others have infinity.
This is the point where we check if we have reached our target node, in that case we break out of the while loop.
Also, very impostant, we remove the returned node from the list of unvisited nodes.
If not, we iterate inside the neighbor list of the returned node.
For each neighbr node we assign it a value to the distanceFromSource parameter. This value, temporarily stored in the distance parameter, is calculated by adding the value of the same parameter of the current node (the one containing the neighbor list we are iterating in. In the first iteration of the while loop, is the source node), added to the physical distance between the tiles and also the movement cost.
Here is what's happening:
Let's assume that we are considering diagonals too. Starting from the source node on the bottom left, we have 3 neigbors tiles. The one above will have a distance from the source of 2. That is because the distance of the source node (which is 0) is added to the physical distance of the 2 tiles (which is 1 in this case as the tiles are nothing but 1x1 cubes) and its movement cost is added as well, which is 1 (because it's a grass tile). The total is 2.
For the diagonal tile, the distance is 2.4 because the physical distance between that tile and the source node is 1.4 (square root of 2 basically), plus its movement cost of course.
It is important to consider the physical distance for diagonal tiles for one reason: if diagonal tiles are considered at the same distance as adjacent tiles, this could happen:
Going frm tile A to tile B, the path generated has no reason to prefer adjacent tile to diagonal tiles, as they are mathematically at the same distance. So rather than going through a straight line, it might decide to act like in the picture above.
By calculating the physical distance of each tile, diagonals will have a value of distance from the source a little higher, which makes them a less favorable path to follow.
Continuing with our script, if the distance calculated is smaller than the current distance, that means that a shorter path has been found and the distanceFromSource parameter is updated.
This process will continue for each node until we reach the target node.
When we do, the program will exit the while loop.
At this point, if the previousNode of the target node is null means that no path was found, so the while loop iterated through the whole list of nodes without finding a route.
If not, we simply populate the currentPath list by grabbing the previousNode node in each previousNode reference of each node starting from the target node. This is a linked list technique, you can find plenty of tutorials on it online.
At this point the currentPath list contains all the nodes, from target to source. After reversing it, we can assign it to the player (called unitToMove) so it has a path to follow and we can draw the path using line renderers.
It is important to kow that with this system, the player will still be able to travers WALL tiles if no other path is found. That is because the value assigned is not (obviously) infinity, so it can be calculated. To avoid that we can simply detect if the path goes through tiles of type wall and break it when it happens.
Nonetheless, this is one of the ways we can implement path finding for tile based games.
Example scene here.
