Friday Links 0.0.16 - Pathfinding

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

https://booking.riddles.io/

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!

Comments