我一直在Unity玩游戏，我已经在2D方形网格上实现了A *算法来寻找路径 . 从那以后，我将路径搜索扩展到3D节点网格，所以我基本上有一个2D网格节点用于地面，其上面有另一个2D网格节点作为天空 .
计划是使用A *创建机场和航空旅行 . 到目前为止，我的两个网格通过机场连接在一起 . 例如，当我在作为机场的节点的地面网格上搜索邻居节点时，我还将天空网格中的相邻节点添加到列表中 . 这允许从机场“起飞”到天空中的相邻节点 . 此外，在天空中，我搜索相邻的节点，如果其中一个相邻的地面节点是机场，我将其添加到邻居列表 . 这允许飞机从天空“降落”到机场 .
到目前为止，我有与地面旅行的各种地形相关的运动成本，我的航空旅行目前是0，但是在“起飞”和“着陆”运动中往返于天空的运动成本很高 . 这是希望在天空中创造一条更快的路径，使其变得有 Value ，但是增加一次大的运动成本来 balancer ，所以在两个机场之间说4个节点就没有意义了 .
这一切都很好 . 如果旅行成本低于空中，如果他必须在地面上行走，那么这家伙选择乘飞机去 . 然而，我的问题是，有时候地面路径，以及因此与机场相关的任何成本的路径有时会在机场上选择，而很明显有更多的地面节点可以覆盖这样做而不是乘坐飞机 .
我有一种感觉，这可能是由于路径搜索目标，而不是机场，这可能是另一个方向，因此机场不是任何搜索节点的邻居节点，因此甚至没有考虑即使它可能是一个更快的路径解决方案 .
听起来这可能是我遇到的问题吗？如果我想做这样的事情，我是否使用了错误的算法类型？有什么办法可以帮助附近的机场进行检查或给予更多关注吗？我想我可以通过降低运动成本或其他东西来增加通往他们的道路......
谢谢你的帮助！
3 回答
您可以通过修改启发式来获得所需的结果 . 例如，如果基于从该节点到最近机场的距离来减少节点处的启发式值，则会偏向A *算法以搜索前往机场的路径 .
例如，假设您正在使用特定的启发式算法，例如曼哈顿 . 因此，在计算任何节点的启发式值时，请采用以下方法中的较小者：
到目标节点的曼哈顿距离
距离目的地机场到目标的曼哈顿目标距离最近的机场飞往机场的曼哈顿距离 .
建议谨慎一些 . 调整启发式以偏置算法以测试某些路径可能最终会在这些路径不是正确的最短路径时给出差的结果 . 这只是野兽在做这件事时的本质 .
其他几个答案都表明A *是一种启发式方法，因此并不总是能给出最佳结果 . 这是不正确的 . A *使用启发式算法，但它本身不是启发式的 . 它总能给出最佳结果 .
假设，就是你正确使用它 . 启发式传递给A * must never overestimate the cost of reaching the destination . 因此，如果附近的机场以50的成本到达您的目的地，并且您的启发式测试表示成本为~100，则A *将无法正常工作 . 鉴于你给出的描述，我认为这是最可能的罪魁祸首 .
（是的，这意味着您可以将启发式设置为始终为0.在这种情况下，A *将转换为Dijkstra's algorithm）
A *基于启发式 . 因此，除非仔细选择启发式以具有某些可接受性质，否则不能保证产生全局最优解 . 如果没有这个，A *就会放松成一种产生局部最优解的形式（因此有时在你的帖子中） .
如果您希望您的算法始终找到保证的最佳路径，那么您可以考虑改进启发式或不同的算法 .