GKGraph错误地计算了带有GKGraphNode2D子类化节点的路径 [英] GKGraph Incorrectly Calculates Path with GKGraphNode2D-Subclassed Nodes

问题描述

我开始使用此问题调查此问题，其中已在iOS 9.2 SDK中得到部分解决.

I started investigating this issue with this question which was partially resolved in the iOS 9.2 SDK.

但是，在进一步调查后，我意识到该框架仍然无法按预期工作.

However, upon further investigation, I realized that this framework was still not working as expected.

总而言之，可以使用节点(GKGraphNode及其子类)构造GKGraph，在这些节点之间可以计算寻路成本和路径. GKGraphNode2D只是GKGraphNode，它位于并将其坐标封装在二维网格中.可以将GKGraphNode子类化，并且可以覆盖方法costToNode(_:)和estimatedCostToNode(_:)以提供节点之间的成本.将这些自定义节点添加到图形后，图形应使用这些方法来确定连接的节点之间的成本最低的路径.

In summary, a GKGraph can be constructed with nodes (GKGraphNode and its subclasses), between which pathfinding costs and paths can be calculated. A GKGraphNode2D is simply a GKGraphNode that sits on and encapsulates its coordinates in a two-dimensional grid. GKGraphNode can be subclassed, and the methods costToNode(_:) and estimatedCostToNode(_:) can be overridden to provide costs between nodes. Once these custom nodes are added to a graph, the graph should use these methods to determine the lowest-cost path between connected nodes.

我正在构造称为"c7"的节点，其中节点之间的成本只是两个节点之间的距离(在二维坐标空间中).节点连接到2D空间中的所有邻居，包括对角邻居.即，特定节点的左上，右下的相邻节点的距离为1，而对角相邻的节点的距离为sqrt(2) ~ 1.414.这些成本是通过覆盖的方法costToNode(_:)和estimatedCostToNode(_:)计算的.

I am constructing nodes that I'll call GeometricNode, where the cost between nodes is simply the distance (in two-dimensional coordinate space) between two nodes. Nodes are connected to all their neighbors in 2D space, including their diagonal neighbors. I.e., neighboring nodes above, below, to the left and right of a particular node are a distance of 1 away, while diagonally-neighboring nodes are sqrt(2) ~ 1.414 away. These costs are calculated in the overridden methods costToNode(_:) and estimatedCostToNode(_:).

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

Unfortunately, even though these connections are appropriately set up, and the costs are appropriately calculated, GKGraph does not always calculate the correct path when invoking findPathFromNode(_:toNode:).

@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

推荐答案

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

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

这篇关于GKGraph错误地计算了带有GKGraphNode2D子类化节点的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！