Search code examples
sprite-kitgameplay-kit

GKGraph GKGraphNode GKGridGraphNode, what's relationship for them?

I've read the document but still confused of them, could any guy can give me a clearly explaining, e.g.any image comparison? Thanks.

Solution

  • The Wikipedia article on Pathfinding might help, as might the related topics on graphs and graph search algorithms linked from there. Beyond that, here's an attempt at a quick explainer.

    Nodes are places that someone can be, and their connections to other nodes define someone can travel between places. Together, a collection of (connected) nodes form a graph.

    GKGraphNode is the most general form of node — these nodes don't know anything about where they are in space, just about their connections to other nodes. (That's enough for basic pathfinding, though... if you have a graph where A is connected to B and B is connected to C, the path from A to C goes through B regardless of where those nodes are located, like below.)

    enter image description hereenter image description here

    GKGraph is a collection of nodes, and provides functions that work the graph as a whole, like the important one for finding paths.

    GKGridGraphNode and GKGraphNode2D are specialized versions of GKGraphNode that add knowledge of the node's position in space — either integer grid space (like a chessboard) or open 2D space. Once you've added that kind of information, a GKGraph containing these kinds of nodes can take distance into account when pathfinding.

    For example, look at this image:

    enter image description here

    If we're just using GKGraphNode, all we're talking about is which nodes are connected to which. So if we ask for the shortest path from A to D, we can get either ACD or ABD, because it's an qual number of connections either way. But if we use GKGridGraphNode or GKGraphNode2D, we're looking at the lengths of the lines between nodes, in which case ACD is the shortest path.

    Once you start locating your nodes in (some sort of coordinate) space, it helps to be able to operate on the graph as a whole in that space. That's where GKGridGraph and GKObstacleGraph come in.

    • GKGridGraph works with GKGridGraphNodes and lets you do things like create a graph to fill a set of dimensions (say, a 10x10 grid, with diagonal movement allowed) instead of making you create and connect a bunch of nodes yourself.
    • GKObstacleGraph adds more to free-2D-space graphs by letting you mark areas as impassable obstacles and automatically managing the nodes and connections to route around obstacles.

    Hopefully this helps a bit. For more, besides the reference docs and guide, Apple also has a WWDC video that shows how this stuff works.