Whenever an object in a game should move from A to B, pathfinding is involved. This is a dreaded topic, but I want to shed light on how to tackle creating a proper and fast pathfinding algorithm. This is an ab initio approach, so you don't have to know anything about pathfinding.

As an easy example I will relate to square tiles, but the method described here can be used for any sort of map and is not even limited to 2D. You can find a Haxe implementation on gamejolt and the relevant part of the source code on pastebin. This method is called A* and you can also find many lots of code examples on google or wikipedia. I encourage you to try this for your own and create your own pathfinding. It is not that hard! :)

Processing Info

As a first step, the information from the map needs to be processed to a set of variables so the algorithm can work with it in an efficient way. The x and y position of each tile is enough to continue. What is needed is a representation of the map as a graph. A graph is a set of nodes that are connected to each other. The absolute positions are not that important. What the algorithm is interested in is the local neighborood of each node. The graph for the square tiles example can be build by spawning nodes on the center of each passable square tile. Any tile that is not passable (like any obstacle) will not spawn a node. To connect the nodes, we want to use the nearest neighbors. For the 2d square tiles all 8 neighboring tiles. If you do not want to have diagonal movement, simply omit these tiles.

Each node needs to have three variables: The travelling distance (which should just be the distance between two nodes. 1 for horizontal and vertival connections, sqrt(2) for diagonal ones.) and the node offset. Normally the offset is 0, but it can be used to tag areas that should be avoided (like if they are in the range of enemy turrets => positive values) or that should be very likely to pass (e.g. to punish going up or down a hill => negative value). Finally the node value will be set by the algorithm and should be initialized to -1.

With that we have our graph ready to be processed by the algorithm. From here on, it is safe to forget about the underlying map, as the graph contains everything needed.

Initial Search

The A algorithm requires a list of connected nodes, with one start and one end node. The algorithm checks all neighboring nodes of the start node and sets the respective node values to the node's offset plus the travelling distance. The algorithm will then do a heuristic search (for everyone who is intersted: this is what sets A apart from dijkstra). Use the straight line distance to the end node as a rough estimate. The node with the lowest heuristic value will be examined next. Then start with this new node as the next start node. Every time the node value will be set. The heuristic map will continue to be used over all iterations. It is worth mentioning, that the node value must only be calculated if the node has not been visited previously.

This continues until the end node is hit. If all tiles have been visited and the end this has not been found, there is no connection.

There and back again

The algorithm has found one or multiple paths from start to end. To get a valid succession of tiles as a usable path from that, it must perform a downhill search. Start at the end, which should be the node with the highest node value. From there on, search the neighbouring node with the lowest node value. This will be your next node to visit. Then do this over and over again, until you reach the start node again, which is the node with the lowest node value.

Then the last thing to do is to inverse the ordering.

... also worth mentioning

Since we use a heuristic, it can (and will happen) that not the optimal path will be found. An example would be if there is an obstacle in the way. Then the algorithm might take the long way around it, instead of the short one.

One easy trick to handle this is to swap start and end and calculate the path also the other way round. Then just use the path with the lower summed up node values.

If you are tempted to do pathfinding on a large map, there are many tricks on how to speed this up. One might be to divide your map into large regions and calculating a coarse grained travel map. Then you can use this as a starting point for a refined version.

There is also a dynamic version, which can handle events like a bridge that is no longer passable. This is useful, since you don't have to recalculate the whole path again.

As mentioned above, it is also possible to use any kind of graph, not just square tiles. This will allow for any type of layout, e.g. on hex tiles or on a map, which is not created by tiles at all.