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 GKGraphNode:

@interface GKGridGraphNode : GKGraphNode

+ (instancetype)nodeWithGridPosition:(vector_int2)position;
- (instancetype)initWithGridPosition:(vector_int2)position;

@property (assign, nonatomic) vector_int2 position;

@end

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 GKGraphNode to GKGridGraphNode is the updated -estimatedCostToNode: method:

- (float)estimatedCostToNode:(GKGraphNode *)node
{
    NSAssert([node isKindOfClass:[GKGridGraphNode class]], @"GKGridGraphNode -estimatedCostToNode: Only works with grid graph nodes, not general graph nodes.");
    GKGridGraphNode *goal = (GKGridGraphNode *)node;

    float dx = abs(self.position.x - goal.position.x);
    float dy = abs(self.position.y - goal.position.y);
    return (dx + dy) - 1 * MIN(dx, dy);
}

Two things of note here:

  1. 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.
  2. 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 GKGridGraphNode whether 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:

Initial fully connected graph

Then you remove the nodes that you don’t want reachable (e.g. walls):

Removing nodes

And there’s your pathfinding graph. Notice that you can end up with orphaned nodes. It’s not really important, but it does happen.

Here’s GKGridGraph’s interface:

@interface GKGridGraph : GKGraph

+ (instancetype)graphFromGridStartingAt:(vector_int2)position
                                  width:(int)width
                                 height:(int)height
                       diagonalsAllowed:(BOOL)diagonalsAllowed;

- (instancetype)initFromGridStartingAt:(vector_int2)position
                                 width:(int)width
                                height:(int)height
                      diagonalsAllowed:(BOOL)diagonalsAllowed;

@property (readonly, nonatomic) BOOL diagonalsAllowed;
@property (readonly, nonatomic) vector_int2 gridOrigin;
@property (readonly, nonatomic) NSUInteger gridWidth;
@property (readonly, nonatomic) NSUInteger gridHeight;

- (GKGridGraphNode *)nodeAtGridPosition:(vector_int2)position;
- (void)connectNodeToAdjacentNodes:(GKGridGraphNode *)node;

@end

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 -removeNodes: (from GKGraph) to take those nodes out. So building the graph diagrammed above would look like:

GKGridGraph *graph = [GKGridGraph graphFromGridStartingAt:(vector_int2){0, 0} width:3 height:4 diagonalsAllowed:YES];

NSMutableArray *walls = [NSMutableArray array];
[walls addObject [graph nodeAtGridPosition:(vector_int2){1, 0}]];
[walls addObject [graph nodeAtGridPosition:(vector_int2){0, 1}]];
[walls addObject [graph nodeAtGridPosition:(vector_int2){1, 2}]];
[walls addObject [graph nodeAtGridPosition:(vector_int2){2, 2}]];
[walls addObject [graph nodeAtGridPosition:(vector_int2){2, 3}]];

[graph removeNodes:walls];

Interestingly (and surprising to me), removing a node removes it from the grid entirely: you can’t retrieve it later and re-connect it.

GKGraphNode *node = [graph nodeAtGridPosition:(vector_int2){0, 0}];
[graph removeNodes:@[node]];

GKGraphNode *nodeAgain = [graph nodeAtGridPosition:(vector_int2){0, 0}];
// nodeAgain will be nil here in the real GameplayKit!

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:

@interface GKGridGraph ()
@property (strong, nonatomic) NSMutableArray *gridNodes;
@end

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:

NSUInteger numNodes = width * height;
NSMutableArray *gridNodes = [NSMutableArray arrayWithCapacity:numNodes];

int minX = origin.x;
int minY = origin.y;
int maxX = minX + width;
int maxY = minY + height;
for (int y = minY; y < maxY; y++) {
    for (int x = minX; x < maxX; x++) {
        [gridNodes addObject:[GKGridGraphNode nodeWithGridPosition:(vector_int2){x, y}]];
    }
}

/// ... self = [super initWithNodes:gridNodes], blah blah blah

// A freshly created grid graph starts out fully connected.
for (GKGridGraphNode *node in gridNodes) {
    [self connectNodeToAdjacentNodes:node];
}

-connectNodeToAdjacentNodes: takes the node position and uses it to look up all of the nodes nearby and add connections to them using GKGraphNode -addConnectionsToNodes:bidirectional:.

- (void)connectNodeToAdjacentNodes:(GKGridGraphNode *)node
{
    vector_int2 pos = node.position;

    NSMutableArray *newConnections = [NSMutableArray arrayWithCapacity:8];

    // addToArrayIfNotNil is just a static function that does exactly what it says it does
    addToArrayIfNotNil(newConnections, [self nodeAtGridPosition:(vector_int2){pos.x - 1, pos.y}]);
    addToArrayIfNotNil(newConnections, [self nodeAtGridPosition:(vector_int2){pos.x + 1, pos.y}]);
    addToArrayIfNotNil(newConnections, [self nodeAtGridPosition:(vector_int2){pos.x, pos.y - 1}]);
    addToArrayIfNotNil(newConnections, [self nodeAtGridPosition:(vector_int2){pos.x, pos.y + 1}]);

    if (self.diagonalsAllowed) {
        addToArrayIfNotNil(newConnections, [self nodeAtGridPosition:(vector_int2){pos.x - 1, pos.y - 1}]);
        addToArrayIfNotNil(newConnections, [self nodeAtGridPosition:(vector_int2){pos.x + 1, pos.y - 1}]);
        addToArrayIfNotNil(newConnections, [self nodeAtGridPosition:(vector_int2){pos.x - 1, pos.y + 1}]);
        addToArrayIfNotNil(newConnections, [self nodeAtGridPosition:(vector_int2){pos.x + 1, pos.y + 1}]);
    }

    [node addConnectionsToNodes:newConnections bidirectional:YES];
}

Then finally, 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 gridNodes:

- (GKGridGraphNode *)nodeAtGridPosition:(vector_int2)position
{
    if (position.x < self.gridOrigin.x) return nil;
    if (position.y < self.gridOrigin.y) return nil;
    if (position.x >= self.gridOrigin.x + self.gridWidth) return nil;
    if (position.y >= self.gridOrigin.y + self.gridHeight) return nil;

    int idx = (position.y - self.gridOrigin.y) * (int)self.gridWidth + (position.x - self.gridOrigin.x);
    return self.gridNodes[idx];
}

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.