a* 寻路——继任者的成本
我正在重新制作一款旧的《魔兽争霸 3》自定义游戏，我以前玩过这款游戏，并将其放在 iPhone 上。基本上，你有一定的时间用一定数量的方块建造一个迷宫，并且小兵运行迷宫所需的时间越长，你获得的分数就越多。
我正在使用 cocos2d 在airplay 中完成这一切，现在我正在放入 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，对吗？
I'm remaking an old warcraft 3 custom game that I used to play way back when and putting it on the iphone. Basically, you have a set amount of time to build a maze out of a set amount of blocks, and the longer it takes the creep to run the maze, the more points you get.
I'm doing this all in airplay with cocos2d, and right now I'm putting in the a* pathfinding algorithm. I'm using Justin Heyes-Jones' implementation and working on the node class right now.
However, a couple things are confusing me. The class looks like this:
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();
};
I'm just not sure what GetCost means. In this example maze, where X's are walls and _'s are walkable areas, would the cost of going from (3, 1) to (3, 2) be 0? And then what would the cost of going from (3, 1) to (4, 1), since it's impossible?
X X _ X X
X _ _ X X
X _ X X X
X _ _ _ _
X X X X X
And then I guess I can just implement GoalDistanceEstimate by using the distance formula, correct?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
一般的A*是基于加权图的。在实际的迷宫求解应用中，对于可通行的地形，所有边都具有相同的有限权重（通常为 1），对于不可通行的地形，所有边具有无限权重（写为一个非常大的数字，只需使用 100000 或其他值）。
The general A* is based on a weighted graph. In practical maze solving applications, all edges have the same finite weight (usually 1) for passable terrain and infinite (written as a very large number, just use 100000 or something) for impassable terrain.
据我了解，成本是确定“最快路径”的“总和”。他们必须前往的每个方格或节点都会添加成本。这还可以包括诸如地形限制（例如减慢速度等）之类的事情。
To my understanding, the cost was the "combined total" that determined the "fastest path". The cost is added to for every square or node that they have to go to. This can also include things such as terrain limitations (such as slowing you down etc.).