This is based on an email I send my .NET team at work
Happy Friday,
It’s sad I haven’t been able to make it into the office most of the week, but this tile install should finally be done early tomorrow morning. It will be nice to put our kitchen back together and stop hiding out in a living room full of appliances and dishes.
Anyway, I’ve been looking at some pathfinding algorithms this week. These are techniques you can use to find the shortest path between two points on a map, accounting for obstacles and different costs in terrain. The obvious application is in game development: you have some NPC character that needs to move from one point to another in a sensible and not random path.
I think there could be some uses cases in other situations: maybe navigating the shortest connection between two nodes in some sort of graph dataset, like playing six degrees of Kevin Bacon.
Or maybe you work for amazon and you’re building a tablet app that their pickers can use to go right to the correct place in the shelves to fetch a particular item. Assuming amazon’s warehouse is poorly designed to look like a maze that is…
Sometimes I want to participate in one of those coding challenges where you have two bots on a map and they battle to find items and attack the other. I’ve never given one a try because I wasn’t sure how to make a pathfinding algorithm.
But now I know!
Introduction to Pathfinding
https://www.raywenderlich.com/4946/introduction-to-a-pathfinding
This was a really helpful explanation of the A* pathfinding algorithm.
A* is typically the introductory algorithm and makes a good trade off
between time and complexity: it’s not too difficult to implement and
works reasonably quickly in non-pathological cases.
Basically A* involves considering all the possible adjacent places on
the map grid, and calculating the cost to get to that place, plus an
estimated cost from that place to the target location. There are a bunch
of techniques for estimating the cost to the target, but the easiest is
the “Manhattan distance” which is just a count of vertical and
horizontal steps to get there. Think city blocks.
You just keep analyzing the lowest costing node and adding the places adjacent to that location until you eventually get there or run out of possible locations to check.
This article walks through a simple path to help visualize, and then gives some pseudo code in objective C. No one can read objective C, so I have a demo in C# here: https://github.com/akatakritos/PathfinderDemo. Check out the AStarPathFinder class. I hope you’ll find it reasonably well commented.
Heuristics
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
Recall that in A* you have to estimate the distance from each location
you’re considering to the target. There are a bunch of different
heuristics to do that: I mentioned the Manhattan distance earlier. But
in more complex grids you can use different heuristics to get better
results. For example, if your path can move along the diagonal, you use
a heuristic that takes that into account.
Pathfinding.js
https://qiao.github.io/PathFinding.js/visual/
If you are using javascript, there’s an npm module for pathfinding, because there’s an npm module for literally everything. But I really like this demo. You can draw some obstacles on the graph and see a visualization of how the algorithm considers nodes. You can use different algorithms and heuristics to see how it changes the path and the search time.
As it draws, the light blue squares are locations it considered and
discarded. This is the “closed list” in the A* algorithm. The green
squares are locations the algorithm is still wanting to investigate.
That’s the “open list” in A*. You can watch it pick the green square
with the lowest cost sum of “distance from start” + “guess of distance to
target” and keep spreading out from there.
It’s kind of mesmerizing to be honest.
Bot challenge
Anyway, Brad showed me this bot challenge the other day that sparked my curiosity into Pathfinding. Now hopefully we’re all armed with enough knowledge to go do battle!
Have a great weekend, see you Monday!