SpriteKit - getting closest nodes

Question

Is there a way of getting the closest nodes to a node?

I'm just about to write a method to iterate all nodes and calculate distances etc... but wondered if there is a better way?

I have 30 nodes and need the 2 nearest nodes to each of the 30 nodes (if that makes sense).

Answer 1

As of iOS 10, you can use the Spatial Partitioning features of GampelayKit. In 2D either GKQuadtree or GKRTree depending on your needs.

From the docs:

Quadtrees and R-trees have different performance tradeoffs for different tasks: quadtrees can be faster when objects are more uniformly distributed in space or when their positions change frequently, and R-trees can be faster when searching for all objects in a given region.

Add your enemies to the tree:

    let minX = Float(enemy.frame.minX)
    let minY = Float(enemy.frame.minY)
    let maxX = Float(enemy.frame.maxX)
    let maxY = Float(enemy.frame.maxY)

    var enemiesRTree = GKRTree(maxNumberOfChildren: 3)
    enemiesRTree.addElement(enemy,
                             boundingRectMin: vector2(minX, minY),
                             boundingRectMax: vector2(maxX, maxY),
                             splitStrategy: GKRTreeSplitStrategy.linear)

Then you can search by area.

    let enemiesInProximity = enemiesRTree.elements(
       inBoundingRectMin: vector2(0, 0),
       rectMax: vector2(100, 100))

You can then create the search area e.g. relative to the player's position.

Answer 2

I believe that your approach is the most appropriate for this situation. If you stored all the nodes in an array style there may be a relatively efficient way to do what you mentioned above.

In any situation, you still may be tasked with having three nodes closest. If this is not a problem, you use a method that takes a nodes position and then use for loop to project "invisible circles" of increasing radius until a circle finally contains exactly 2 nodes. Then just return those nodes.