GKGraph incorrectly calculates path with GKGraphNode2D-Subclassed nodes

Question

I began to study this question with this question , which was partially resolved in the iOS 9.2 SDK.

However, after further study, I realized that this structure still does not work properly.

Thus, a GKGraph can be constructed with nodes ( GKGraphNode and its subclasses) between which you can calculate the costs of the path and the path. A GKGraphNode2D is simply a GKGraphNode that sits and encapsulates its coordinates in a two-dimensional grid. GKGraphNode can be subclassed, and the costToNode(_:) and estimatedCostToNode(_:) methods can be overridden to provide costs between nodes. When these user nodes are added to the graph, the graph should use these methods to determine the least cost route between the linked nodes.

I create nodes, which I will call GeometricNode , where the cost between nodes is just the distance (in a two-dimensional coordinate space) between two nodes. The nodes are connected to all their neighbors in 2D space, including their diagonal neighbors. Ie, the neighboring nodes above, below, to the left and to the right of a particular node are at a distance of 1 , and the diagonally neighboring nodes are sqrt(2) ~ 1.414 . These costs are calculated in the overridden methods costToNode(_:) and estimatedCostToNode(_:) .

Unfortunately, even though these connections are properly configured and costs are properly calculated, GKGraph does not always calculate the correct path when calling findPathFromNode(_:toNode:) .

Code ( Project Example )

 @import UIKit; @import Foundation; @import GameplayKit; @interface GeometricNode : GKGraphNode2D @end @implementation GeometricNode - (float)estimatedCostToNode:(GKGraphNode *)node { NSAssert(([node isKindOfClass:[GeometricNode class]]), @"Must Use GeometricNode"); return [self geometricDistanceToNode:(GeometricNode *)node]; } - (float)costToNode:(GKGraphNode *)node { NSAssert(([node isKindOfClass:[GeometricNode class]]), @"Must Use GeometricNode"); return [self geometricDistanceToNode:(GeometricNode *)node]; } - (CGFloat)geometricDistanceToNode:(GeometricNode *)node { return sqrtf( powf(self.position[0] - node.position[0], 2) + powf(self.position[1] - node.position[1], 2) ); } @end 

And the failed test:

 @import XCTest; #import "GeometricNode.h" @interface Graph_Node_TestTests : XCTestCase @property (nonatomic, strong) GKGraph *graph; @property (nonatomic, strong) NSArray <GeometricNode *>* nodes; @end @implementation Graph_Node_TestTests - (void)setUp { /* This is the graph we are creating: A---B---C | X | X | F---E---D where all of the nodes are `GeometricNode` objects. The nodes' cost to each other is determined by simple geometry, assuming the nodes are spaced in a grid all one unit away from their top-left-bottom-right neighbors. Diagonal nodes are spaced sqrt(2) ~ 1.414 away from one another. */ GeometricNode *nodeA = [[GeometricNode alloc] initWithPoint:(vector_float2){0, 0}]; GeometricNode *nodeB = [[GeometricNode alloc] initWithPoint:(vector_float2){1, 0}]; GeometricNode *nodeC = [[GeometricNode alloc] initWithPoint:(vector_float2){2, 0}]; GeometricNode *nodeD = [[GeometricNode alloc] initWithPoint:(vector_float2){2, 1}]; GeometricNode *nodeE = [[GeometricNode alloc] initWithPoint:(vector_float2){1, 1}]; GeometricNode *nodeF = [[GeometricNode alloc] initWithPoint:(vector_float2){0, 1}]; [nodeA addConnectionsToNodes:@[ nodeB, nodeF, nodeE ] bidirectional:YES]; [nodeC addConnectionsToNodes:@[ nodeB, nodeD, nodeE ] bidirectional:YES]; [nodeE addConnectionsToNodes:@[ nodeF, nodeD, nodeB ] bidirectional:YES]; [nodeB addConnectionsToNodes:@[ nodeF, nodeD ] bidirectional:YES]; self.nodes = @[ nodeA, nodeB, nodeC, nodeD, nodeE, nodeF ]; self.graph = [GKGraph graphWithNodes:self.nodes]; } - (void)testNodeCosts { /* A---B---C | X | X | F---E---D We would expect, for example, the path from A to C to be ABC, at a cost of 2, to be chosen over a path of AEC, at a cost of 2.828. Instead, GKGraph chooses this latter incorrect path. */ GeometricNode *nodeA = self.nodes[0]; GeometricNode *nodeB = self.nodes[1]; GeometricNode *nodeC = self.nodes[2]; GeometricNode *nodeE = self.nodes[4]; XCTAssert([nodeA.connectedNodes containsObject:nodeB], @"Node A is connected to Node B"); XCTAssert([nodeB.connectedNodes containsObject:nodeC], @"Node B is connected to Node C"); XCTAssert([nodeA.connectedNodes containsObject:nodeE], @"Node A is connected to Node E"); XCTAssert([nodeE.connectedNodes containsObject:nodeC], @"Node E is connected to Node C"); XCTAssertEqualWithAccuracy([nodeA costToNode:nodeB], 1, 0.001, @"Cost from AB should be 1"); XCTAssertEqualWithAccuracy([nodeB costToNode:nodeC], 1, 0.001, @"Cost from BC should be 1"); XCTAssertEqualWithAccuracy([nodeA costToNode:nodeE], sqrt(2), 0.001, @"Cost from AE should be sqrt(2) ~ 1.414"); XCTAssertEqualWithAccuracy([nodeE costToNode:nodeC], sqrt(2), 0.001, @"Cost from EC should be sqrt(2) ~ 1.414"); // The actual path calculated by GKGraph, and the expected and actual (incorrect) paths NSArray <GeometricNode *>* actualPath = [self.graph findPathFromNode:nodeA toNode:nodeC]; NSArray <GeometricNode *>* expectedPath = @[ nodeA, nodeB, nodeC ]; NSArray <GeometricNode *>* incorrectPath = @[ nodeA, nodeE, nodeC ]; // We would expect GKGraph to choose this lowest-cost path: ABC CGFloat totalExpectedCost = [nodeA costToNode:nodeB] + [nodeB costToNode:nodeC]; XCTAssertEqualWithAccuracy(totalExpectedCost, 2, 0.001, @"Lowest cost path cost should be 2"); // GKGraph is actually choosing this more costly path: AEC CGFloat totalIncorrectCost = [nodeA costToNode:nodeE] + [nodeE costToNode:nodeC]; CGFloat totalActualCost = 0; for (NSInteger i = 0; i < actualPath.count - 1; i++) { totalActualCost += [((GeometricNode *)actualPath[i]) costToNode:actualPath[i + 1]]; } XCTAssert([actualPath isEqualToArray:expectedPath], @"Actual found path should be equal to ABC"); XCTAssert(![actualPath isEqualToArray:incorrectPath], @"Actual found path should not be equal to AEC"); XCTAssertGreaterThan(totalIncorrectCost, totalActualCost); XCTAssertLessThanOrEqual(totalActualCost, totalExpectedCost); } @end 

Answer 1

Like Xcode 8.0 beta 1 (8S128d) and iOS 10 beta 1 (14A5261v), this problem seems to be resolved.