0

我正在重新制作一个旧的魔兽争霸 3 自定义游戏，我曾经在 iPhone 上玩过该游戏。基本上，您有一定的时间从一定数量的块中构建迷宫，并且爬行者运行迷宫所需的时间越长，您获得的积分就越多。

我正在使用 cocos2d 进行这一切，现在我正在使用 a* 寻路算法。我正在使用Justin Heyes-Jones 的实现并正在处理节点类。

但是，有几件事让我感到困惑。该类如下所示：

class MapSearchNode
{
public:
    unsigned int x;  // the (x,y) positions of the node
    unsigned int y; 


    MapSearchNode() { x = y = 0; }
    MapSearchNode( unsigned int px, unsigned int py ) { x=px; y=py; }

    bool IsGoal( MapSearchNode &nodeGoal ) { return (x == nodeGoal.x && y == nodeGoal.y); }
    bool IsSameState( MapSearchNode &rhs ) { return (x == rhs.x && y == rhs.y); }

    float GoalDistanceEstimate( MapSearchNode &nodeGoal );
    float GetCost( MapSearchNode &successor );
    bool GetSuccessors( AStarSearch<MapSearchNode> *astarsearch, MapSearchNode *parent_node );

    //void PrintNodeInfo();
};

我只是不确定 GetCost 是什么意思。在这个示例迷宫中，X 是墙壁，_ 是可步行区域，从 (3, 1) 到 (3, 2) 的成本是否为 0？那么从 (3, 1) 到 (4, 1) 的成本是多少，因为这是不可能的？

X X _ X X
X _ _ X X
X _ X X X
X _ _ _ _
X X X X X

然后我想我可以通过使用距离公式来实现 GoalDistanceEstimate，对吗？

4

2 回答 2

1

据我了解，成本是确定“最快路径”的“总和”。他们必须去的每个广场或节点都会增加成本。这还可能包括诸如地形限制（例如减慢您的速度等）之类的东西。

于 2011-04-27T16:56:51.500 回答
1

一般的 A* 是基于加权图的。在实际的迷宫求解应用中，所有边对于可通行的地形具有相同的有限权重（通常为 1），而对于不可通行的地形，所有边具有相同的权重（写成一个非常大的数字，只需使用 100000 或其他东西）。

于 2011-04-27T16:58:02.380 回答