How to construct GKGridGraph using only traversable nodes

Question

Created Mar ’22

Replies 3

Boosts 0

Views 1.1k

Participants 2

I am trying to use GameplayKit's GKGridGraph for a turn-based strategy game. A typical way of using this data structure seems to be to initialize a new GKGridGraph by passing it the grid dimensions, plus a few other params. This results in a fully constructed and connected grid graph of nodes. Then the technique I have seen is to manually remove the nodes that you don't want your agent to be able to traverse, for later usage of findPath().

However, I have found the remove() method to be really bad on performance, for example it takes around 100x longer to call the remove() method than to add a node to the grid graph. I do not know if this is a bug in the framework or not. That performance is going to be a show-stopper for me, so using that technique is not going to be an option for me.

I can post all requisite code if there is anyone out there who knows anything about how to use GKGridGraph.

Does anyone know how to construct a grid-aware, fully connected GKGridGraph correctly using only the nodes that you want to be in the graph?

Also, if there are any Apple support/engineers out there reading this, wow it is hard to get started with GameplayKit due to lack of documentation/tutorials/project samples that are anything more than just the most basic simple use cases. I do believe that GameplayKit is a very well designed framework, but any examples beyond the basics seem to be non-existent anywhere on the internet (March 2022), and the API docs are woefully too little information to get started beyond a Flappy Bird clone. I am attempting to build a professional game.

For example, I was not able to find a single example anywhere of how to use a GKGridGraph with a sub-classed GKGridGraphNode class, and then to prep the grid for traversal and usage of findPath(). This technique is only vaguely hinted at in the Apple-supplied Pathfinding sample project at Pathfinding Sample Project.

Any help would be greatly appreciated. I am considering abandoning GameplayKit simply due to lack of documentation at this point, but I do believe underneath it is a really good framework, if you know things about it beyond what the API docs tell you.

Boost

Answer 1

MobileTen OP

Mar ’22

Quadtrees?

0

Answer 2

jsclev OP

Mar ’22

Quadtrees could potentially be an option (I'd have to research those more to know for sure), thanks for that idea. But I thought that what I was trying to do with GameplayKit was pretty much the exact use case for why the GKGridGraph is provided by Apple, to construct a grid-aware graph of nodes that can be walked by A*, which is I am assuming what is used behind GKGraph.findPath(). So...to some extent, if GKGridGraph cannot efficiently do what I've described above, I really don't know what the purpose is of the GKGraph classes other than to build very simple games, ones that have very small grids. In my tests it took 2,000 milliseconds to remove 20% of the nodes in a 50x50 grid, which is a couple orders of magnitude too slow for my purposes.

I am fine coding my own data structures from scratch to power my game engine, but I really thought that GKGridGraph was supposed to provide the exact functionality that I'm trying to use it for, so I am very reluctant to just start coding my own data structures. Really I would just love to get some sample code from Apple/anyone showing how to add a specific array of subclassed GKGridGraphNodes to a GKGridGraph and have the resulting graph be self-aware of the underlying grid structure that resulted from adding the nodes.

This page: jonathanfischer.net/lets-build-gameplaykit-grid-pathfinding shows a close example to what I am trying to do, but Apple's GK API docs suggest that their GKGridGraph implementation should be able to do what I'm wanting to do. What am I missing?

0

Answer 3

jsclev OP

Mar ’22

For anyone who might have any thoughts, here is a page that shows how to create a subclass of GKGridGraphNode and construct a GKGridGraph using your custom node:

github.com/thesecretlab/iOSGameDevCookbook3rdEd/blob/master/01-layingout.playground/Pages/Graphs.xcplaygroundpage/Contents.swift

That is from the book iOS Game Development Cookbook, and it was the only actual code example I was able to find on the internet showing how to subclass GKGridGraphNode for usage in a GKGridGraph. Theoretically that technique sounds fine: create a GKGridGraph using the main constructor, then remove nodes in the grid and replace with your custom nodes using connectToAdjacentNodes. The problem is that GKGraph.remove() method takes around 1,000x times longer to remove a node than it does to add a node. I don't know why.

I wanted to create an on-the-fly ephemeral grid graph for each agent that needs pathfinding per turn in my game, and use the graph to find an optimal path using GKGraph.findPath() then just throw away the graph once the path was found, then rinse and repeat. That idea will not be possible due to the performance of the remove() method as it takes way too long to create the grid graph.

If anyone has any ideas, please let me know. I am stumped and pretty much totally roadblocked at this point from using GameplayKit, as usage of the grid graph is a fundamental part of my game engine.

1