GKGraph 使用 GKGraphNode2D 子类节点错误地计算路径

Question

我开始用调查这个问题，这个问题在 iOS 9.2 SDK 中得到了部分解决。

然而，经过进一步调查，我意识到这个框架仍然没有按预期工作。

综上所述，可以用节点（GKGraphNode及其子类）构造一个GKGraph，在节点之间可以计算寻路成本和路径。 GKGraphNode2D 只是一个 GKGraphNode，位于二维网格中并将其坐标封装起来。 GKGraphNode 可以被子类化，方法 costToNode(_:) 和 estimatedCostToNode(_:) 可以被覆盖以提供节点之间的成本。一旦将这些自定义节点添加到图形中，图形应使用这些方法来确定连接节点之间的最低成本路径。

我正在构建我称之为 GeometricNode 的节点，其中节点之间的成本只是两个节点之间的距离（在二维坐标 space 中）。节点连接到 2D space 中的所有邻居，包括它们的对角线邻居。即，特定节点上方、下方、左侧和右侧的相邻节点距离 1，而对角线相邻节点距离 sqrt(2) ~ 1.414。这些成本是在覆盖方法 costToNode(_:) 和 estimatedCostToNode(_:).

中计算的

不幸的是，即使正确设置了这些连接，并且正确计算了成本，GKGraph 在调用 findPathFromNode(_:toNode:) 时并不总是计算出正确的路径。

代码 (Sample project)

@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

失败的测试：

@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 A-B-C, at a cost of
     2, to be chosen over a path of A-E-C, 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 A-B should be 1");
    XCTAssertEqualWithAccuracy([nodeB costToNode:nodeC], 1, 0.001, @"Cost from B-C should be 1");

    XCTAssertEqualWithAccuracy([nodeA costToNode:nodeE], sqrt(2), 0.001, @"Cost from A-E should be sqrt(2) ~ 1.414");
    XCTAssertEqualWithAccuracy([nodeE costToNode:nodeC], sqrt(2), 0.001, @"Cost from E-C 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: A-B-C
    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: A-E-C
    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 A-B-C");
    XCTAssert(![actualPath isEqualToArray:incorrectPath], @"Actual found path should not be equal to A-E-C");
    XCTAssertGreaterThan(totalIncorrectCost, totalActualCost);
    XCTAssertLessThanOrEqual(totalActualCost, totalExpectedCost);
}

@end

Answer 1

从 Xcode 8.0 beta 1 (8S128d) 和 iOS 10 beta 1 (14A5261v) 开始，此问题似乎已解决。

GKGraph 使用 GKGraphNode2D 子类节点错误地计算路径

GKGraph Incorrectly Calculates Path with GKGraphNode2D-Subclassed Nodes

ios

objective-c

gamekit

gameplay-kit

代码 (Sample project)