Pathfinding is widely used as a method for navigating from one point to another. The practice of finding paths is used in many different situations where obtaining a minimal number of connections is desired at little cost. This is particularly useful for studying networks as it enables us to find valuable connections between nodes.
For example, let’s say I generate a random network and I want to get from node A to J. The network below shows an example of a potential path to get there. In this case, the nodes A, I, E, H and J forms the shortest possible path to reach my destination.
Examples of Pathfinding
Pathfinding can be found in several different applications many of which are found in our day-to-day lives. Here are just two examples of where pathfinding can be applied.
Games
Anything from maze solving to MMORPG, pathfinding has a role to play. Often enough, maze solving involves navigating an agent through virtual space without colliding with solid surfaces or other people. Because computers are so good at finding paths, game developers have to add a little bit of artificial stupidity just to make the game more realistic and humanlike. This involves adding a little bit of random noise to make it look as if the computer is making minor mistakes.
Sat-navs (GPS)
Pathfinding has an obvious application in sat navs (also known as GPS to our American friends) as a way of routing people through a map from their current location to a destination. In this case, nodes can represent things like junctions and roundabouts and edges as roads. Sat-nav routing is going to be far more complicated than this but most of these devices likely use some form of pathfinding algorithms.
Implementations
There are many different ways in which pathfinding can be achieved but the general idea is to find the shortest possible path between two nodes. For simplicity, this blog post lists the two main algorithms. These are as follows:
Dijkstra
Dijkstra serves as the basis for almost all pathfinding algorithms out there. The general idea is that to find the shorted possible path to the destination, we start with the source node and move to a neighbouring node providing that it brings us closer to the destination. This is done recursively until the destination has been reached.
Using networkx, this can be implemented in a number of different ways but the simplest approach is to use the following ensuring that method explicitly states ‘dijkstra’…
>>> path = nx.shortest_path(G, source, target, method='dijkstra')A* (A star)
A star is a variation of Dykstra, however, it is widely used in game development to improve speed and reduce complexity by analysing fewer nodes. The distinction is based upon a specified heuristic to better approximate the distance (also known as cost or weight) between nodes. This may reflect some complex in-game metric or a simpler calculation such as the Manhattan or Euclidean distance between two nodes.
To use A start in networkx you have to specify your distance heuristic function. The documentation on the networkx website provides a very good example of using the Euclidean distance to calculate the cost.
>>> path = nx.astar_path(G, source, target, heuristic=dist)Conclusions
It’s fair to say that pathfinding is a universal practice and is not just limited to network analysis. InIt’s fair to say that pathfinding is a universal practice and is not just limited to network analysis. In this blog post, we’ve only just scratched the surface of pathfinding. There is a lot of decent work out there which explains this topic better than I can. It’s fair to say that pathfinding is not my area of expertise.