Let's build GameplayKit - Grid Based Pathfinding
Building on top of the arbitrary directed graph pathfinding code, pathfinding based on a grid adds the spatial information we need to provide a good heuristic to A*. The algorithm stays the same (we don’t touch
GKGraphNode -findPathToNode:), but we can do something useful with
-estimatedCostToNode: now, so A* can more intelligently evaluate nodes. Let’s dig in!
GKGridGraphNode adds a 2D position property to the
vector_int2 is a SIMD type, which I know almost nothing about, and I’m really not sure how far back they’re available. They’re working for me on iOS 8 and Mac OS X Yosemite. ¯\_(ツ)_/¯
The only other change from
GKGridGraphNode is the updated
Two things of note here:
- It only makes sense to estimate costs to other grid graph nodes, so we have to downcast. This is a common pitfall for using inheritance to model this sort of thing. Swift 2.0 has a much better answer for this kind of thing: if you haven’t already watched Protocol Oriented Programming in Swift I really suggest you do.
- I’m using Chebyshev distance as the heuristic function here. Amit’s A* heuristics page has more detail, but it gives a good estimate when moving diagonally costs the same as moving up or down. We don’t know within
GKGridGraphNodewhether diagonals are supported, so we can’t use the more specific octile distance function.
That’s it for
GKGridGraphNode, the rest is in
GKGridGraph, which amounts mostly to helper methods for building up the grid in the first place.
GKGridGraph works by first creating a fully connected graph of nodes. If you ask for a 3x4 graph, it’ll create 12 nodes, assign positions to them, and connect them up like this:
Then you remove the nodes that you don’t want reachable (e.g. walls):
And there’s your pathfinding graph. Notice that you can end up with orphaned nodes. It’s not really important, but it does happen.
Using it is pretty straightforward: create an instance using
+graphFromGridStartingAt:width:height:diagonalsAllowed: (or the initializer), gather references to the nodes you want to remove with
-nodeAtGridPosition:, then use
GKGraph) to take those nodes out. So building the graph diagrammed above would look like:
Interestingly (and surprising to me), removing a node removes it from the grid entirely: you can’t retrieve it later and re-connect it.
I’d have thought those nodes would still be retrievable: you might want to remove a node representing a door when it’s closed, and re-connect it to the graph when it’s opened.
So, there’s a difference here between my implementation and Apple’s: I leave the ability to retrieve the original grid nodes later, even if they’ve been removed. It made for a simpler implementation, and it was what I expected on reading through the docs.
Speaking of, let’s take a look at how I implemented this. First, there’s a private
NSMutableArray that holds the grid nodes created when the graph is initialized:
In hindsight, that array doesn’t need to be mutable: I never muck with it after the graph is created. Creating that array is straightforward:
-connectNodeToAdjacentNodes: takes the node position and uses it to look up all of the nodes nearby and add connections to them using
nodeAtGridPosition: just checks that the incoming position is within the right range based on the graph’s origin, width, and height and returns the appropriate element out of
And that’s it. We don’t need to touch the original A* implementation in
GKGraphNode -findPathToNode:; the solution for a general directed graph works exactly the same here. It’s just a bit more efficient since we have a useful heuristic to use now.
(That said, I did come across a bug in the original implementation of
GKGraph -removeNodes: while working on this. I wasn’t removing connections appropriately in the first place.)
As always, the code for this us up on Github, and the code as of this particular entry is tagged as part4-grid-pathfinding. There’s a new demo in there named PathfindingDemo2 that shows the grid graphs in use: it generates a little random forest for a guy to bounce around in:
I’ve also added a Cocoapods podspec this time around. I’m not going to try to get this into Cocoapods proper yet (if ever) since it doesn’t implement the full GameplayKit, but if people want to use this stuff, I thought I’d make it easy. That said, it’s all straightforward dependency-free code anyway, so you could just pull the
JLFGameplayKit directory into a project and be good to go.