3.3. Create GameplayKit Graphs Document

Previous: 3.2. Scroll Layers - Next: 3.4. Create Physics and other ShapesReturn to Index


If your app’s Minimum Deployment Target is iOS 9 or OS X 10.11 you can use the built-in GameplayKit features, mainly to create graphs for pathfinding.

Types of Graphs

Grid graphs are generated from tile layers and associated tile GID properties. Obstacle graphs are generated from objects on an object layer.

You can create graphs using one of these techniques:

  1. Grid graph based on empty vs non-empty tiles.
  2. Grid graph based on walkable vs blocked tile GIDs.
  3. Grid graph based on pathing cost assigned to individiual tiles in a tileset via tile properties.
  4. Obstacle graph based on (polygon, rectangle or tile) objects on object layers.

The first two grid graphs assume all nodes to have equal cost. The third grid graph allows you to specify node cost, where any tile with a cost greater than 0 will be walkable, all other tiles are considered blocking.

All graphs work on all map orientations: ortho, iso, staggered iso, hex.

The types of graph also influences the workflow and they have different pros and cons explained next.

The DiagonalsAllowed Parameter

You’ll find this parameter in all grid graph functions. This is the same parameter as in the GameplayKit API. For orthogonal and isometric maps diagonalsAllowed determines whether nodes of diagonal tiles will be connected or not.

Note that on isometric maps a “diagonal” direction is in the horizontal and vertical axis, due to the fact that isometric maps are kind of like orthogonal maps rotated by 45 degrees.

For hexagonal maps this parameter has no effect (it is ignored). Hexagonal tiles always have to be able to connect in exactly 6 directions with their 6 neighbor tiles.

Grid Graph without diagonals Grid Graph with diagonals

Non-Empty Tile Graphs

  • Pros: Easy to use. Flexible.
  • Cons: Error-prone, time-consuming to edit. Potentially confusing for players. No pathing costs.

The first type of graph is best used for maps where there is no clear correlation between tile graphics and its walkability.

You would create your tilemap normally, then you’ll add another “collision” tile layer on which you place a single tile for every grid location that should be walkable. You can set this collision layer to be semi-transparent in Tiled so that you can leave it enabled and see which areas are walkable.

Note that while this graph type is very easy to get started with, it can quickly become tedious and error prone to edit. Every time you change the map graphically you will have to check if you also need to update the collision layer. Not being meticulous about that workflow can lead to pathfinding bugs.

Furthermore, “walkability” in this workflow is not automatically tied to a tile’s graphics. For example, at one coordinate a rock tile might be blocked, at another coordinate the same rock tile might be walkable. This could confuse players as they typically have to rely on visual information only to anticipate collisions (“walkability”).

On the other hand this workflow enables “hidden areas” without having to have copies of the same tile in the tileset.

Creating Non-Empty Tile Graphs

You’ll need a list of TKTileLayer names whose tiles should be checked. For every coordinate, a graph node is created when one of the layer contains any tile (is not empty) at that coordinate.

NSArray* layers = @[@"coll1", @"coll2"];
GKGridGraph* graph = [map gridGraphForTileLayersNamed:layers diagonalsAllowed:YES];

// Swift
let layers = ["coll1", "coll2"]
let graph = map.gridGraphForTileLayersNamed(layers, diagonalsAllowed: true)

Walkable/Blocked Tile Graphs

  • Pros: Flexible. Still relatively simple to edit if you stick to either walkable or blocked lists.
  • Cons: Considering and debugging multiple layers and the combined effect of both walkable and blocked GIDs can be confusing. No pathing costs.

For this type of graph you specify a list of walkable or blocked tiles. Alternatively you can specify both walkable and blocked tiles, so that from the given list of layers the last one to either set the coord as walkable or blocked will be used.

Multiple layers can be provided which have a cumulative effect, ie if two layers are given and a coordinate is considered walkable on one layer but not the other, the last layer to change the walkable/blocked attribute of the coordinate “wins”. That way, you can override the information by providing additional layers. For instance to expand the walkable area of the existing collision layer with additional walkable (or blocked) tiles for other types of units (ie flying units, large units, or those with Hastenburaphobia: fear of grass).

It’s best to use one main layer that either specified the walkable or blocked tiles. Then only make (small) alterations by providing additional layers. Otherwise, it can become confusing to understand how the multiple layers alter the walkable/blocking information of a tile. On the other hand, if thought through carefully and thoroughly, this approach will prove powerful and flexible.

Creating Walkable/Blocked Tile Graphs

You’ll need a list of TKTileLayer names as before.

You’ll also need either an array of walkable or blocked tile GIDs (as NSNumber), or both. The TKMap helper function [TKMap tilesForPropertyNamed:value:] allows you to get such a list of GIDs for all tiles that have a property of the corresponding name and value.

If both walkable and blocked lists are provided (not nil, not empty), then the list of layers is enumerated in reverse (ie starting with “coll2”). The first layer to have either a walkable or blocked tile for a given coordinate determines if there will be a graph node at that coordinate.

NSArray* layers = @[@"coll1", @"coll2"];
NSArray* walkable = [map tilesForPropertyNamed:@"walkable" value:@1];
NSArray* blocked = [map tilesForPropertyNamed:@"blocked" value:@1];
GKGridGraph* graph = [map gridGraphForTileLayersNamed:layers
                                        walkableTiles:walkable
                                         blockedTiles:blocked
                                          diagonalsAllowed:YES];

// Swift
let layers = ["coll1", "coll2"]
let walkable = map.tilesForPropertyNamed("walkable", value: 1)
let blocked = map.tilesForPropertyNamed("blocked", value: 1)
let graph = map.gridGraphForTileLayersNamed(layers, walkableTiles: walkable, blockedTiles: blocked,
                                            diagonalsAllowed: true)

Tile-Cost Graphs

  • Pros: Only graph type that provides pathfinding costs.
  • Cons: Balancing (and testing) the relative costs. All walkable tiles must have a positive, non-zero cost value.

A tile coordinate is considered walkable if a tile GID has a positive, non-zero cost value associated with it. This allows you to have units favor roads and avoid forest and swamp terrain tiles, but they might still pass over them if the total cost is lower than possible alternative routes. This makes for the most “sensible” pathfinding behavior if cost values are well balanced.

Still, it can be quite difficult to balance the relative costs between tiles. Especially when tiles and their costs have not been specified from the beginning. Re-balancing tiles' costs can lead to quite different pathfinding behavior in the game, and requires careful testing of various situations.

An artificial test map that provides all sorts of pathfinding scenarios in isolation will help with balancing - consider this test map to be the equivalent of unit-testing code, only that you’ll be unit-testing pathfinding. Quite literally.

It is recommended to define a “default” (neutral) cost for tiles that should not have a specific pathfinding advantage/disadvantage (eg grass tiles). It is also recommended to consider these costs as percentages rather than absolute values, so you may want to stick to a certain range like 0.0 to 1.0 or 0 to 100 with a default cost that’s right in the middle (0.5 or 50). Having such a pre-defined (arbitrary) value range makes it easier to think about relative costs of tiles.

For instance, you may end up bumping the cost for grass to 80 but then you’ll notice that this is now higher than roads which used to have 75, so you may want to bump roads as well (perhaps to 90) so that units still prefer to walk over roads compared to grass but they would still happily consider grass as enjoyable to walk on.

Well, except for those units with Hastenburaphobia.

Tip: Record and update these tiles' costs in a spreadsheet, so that you can see the costs of all tiles at once, because Tiled makes it difficult to compare tile properties.

Creating Tile-Cost Graphs

You’ll need a list of TKTileLayer names as before.

You’ll also need a dictionary of tile costs, where tile GID (NSNumber) are used as keys and float values (NSNumber) are used as value and specify the pathing cost of the tile GID. If pathing cost of a tile is 0 or negative, or a tile GID has no cost associated with it, any coordinate with such a tile is considered blocked and will not have a graph node.

The TKMap helper function [TKMap tileValuesForPropertyNamed:] helps you create a dictionary of tile GIDs with cost values from tiles which have a corresponding property.

NSArray* layers = @[@"coll1", @"coll2"];
NSDictionary* costs = [map tileValuesForPropertyNamed:@"pathingCost"];
GKGridGraph* graph = [map gridGraphForTileLayersNamed:layers costs:costs diagonalsAllowed:YES];

// Swift
let layers = ["coll1", "coll2"]
let costs = map.tileValuesForPropertyNamed("pathingCost")
let graph = map.gridGraphForTileLayersNamed(layers, costs: costs, diagonalsAllowed: true)

Obstacle Graphs

  • Pros: Free-form pathfinding graph. Straightforward to use.
  • Cons: Limited to a (few) hundred objects per map. Number of connections and thus time to create the graph grows exponentially with number of objects and polygon vertices!

Obstacle graphs provide free-form pathfinding for maps. Unit movement would not (necessarily) be restricted to tile coordinates. For example, this could be the pathfinding solution that works well with classic adventure games (eg Monkey Island style) or top-down racing games, where graphics may be tile-based but collision/pathfinding is not.

However you have to consider that the number of connections grows nearly exponentially, so a couple dozen objects may be fine but 200+ objects may already take several seconds to create the graph. If you add too many objects (or vertices) the app might freeze for minutes or simply crash.

You should cautiously check the map after adding obstacles, and design maps so they can rely on fewer objects, but also polygons with fewer vertices.

It’s recommended to make a prototype before development in order to test how many collision objects you’ll need, and how long it’ll take to create these on the oldest supported device. Test on a real device, not the Simulator - the Simulator is using your computer’s CPU and memory which is most likely several times faster/larger than any iPhone/iPad.

Creating Object-Based Obstacle Graphs

You’ll need a list of TKObjectLayer names and you need to specify the buffer radius (same parameter as in GameplayKit’s GKObstableGraph).

Each individual object on all provided object layers will create a GKPolygonObstacle and will add it to the GKObstacleGraph.

NSArray* layers = @[@"coll1", @"coll2"];
GKObstacleGraph* graph = [map obstacleGraphForObjectLayersNamed:layers bufferRadius:10];

// Swift
let layers = ["coll1", "coll2"]
let graph = map.obstacleGraphForObjectLayersNamed(layers, bufferRadius: 10)

Note: Only rectangle, tile and polygon objects are considered. Ellipse and polyline objects are ignored.


Previous: 3.2. Scroll Layers - Next: 3.4. Create Physics and other ShapesReturn to Index