GKGraph使用GKGraphNode2D-Subclassed节点错误地计算path
我开始调查这个问题，在iOS 9.2 SDK中部分解决了这个问题 。
然而，经过进一步的调查，我意识到这个框架还没有按预期工作。
总之， GKGraph可以用节点（ GKGraphNode及其子类）构造，在这些节点之间可以计算寻路成本和path。 一个GKGraphNode2D就是一个简单的GKGraphNode ，它坐落在一个二维网格中并将其坐标封装起来。 GKGraphNode可以被子类化，并且方法costToNode(_:)和estimatedCostToNode(_:)可以被覆盖以在节点之间提供成本。 一旦这些自定义节点添加到图中，图应该使用这些方法来确定连接节点之间的最低成本path。
我正在构build节点，我将称之为GeometricNode ，其中节点之间的代价仅仅是两个节点之间的距离（在二维坐标空间中）。 节点连接到二维空间的所有邻居，包括他们的对angular邻居。 即，在特定节点的左侧和右侧上方，下方的相邻节点距离为1 ，而对angular相邻节点为距离sqrt(2) ~ 1.414 。 这些成本是在重写的方法costToNode(_:)和estimatedCostToNode(_:) 。
不幸的是，即使这些连接设置恰当，并且成本也得到了适当的计算， GKGraph并不总是在调用findPathFromNode(_:toNode:)时计算正确的path。
代码（ 示例项目 ）
@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
而失败的testing：
@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
从Xcode 8.0 beta 1（8S128d）和iOS 10 beta 1（14A5261v）开始，这个问题似乎已经解决了。