假设我有一个二维网格。寻路是我的问题的第二步。
我的事情是，假设我在网格中间有一个单元。我希望能够告诉用户“这些都是您可用的目的地。”。
根据单位可以走多少个方格，我想告诉用户，“这些都是你可以到达的方格。” 然后寻找用户选择的目的地。
进行第一次搜索以显示可到达目的地的最佳方式是什么？
根据地形，地形也可以有限制 och 奖励。
我不知道这被称为什么，因此将不胜感激在哪里寻找或谷歌什么的指针。
干杯! :)
/E
问问题
1580 次
3 回答
4
最好的方法可能是深度优先搜索（http://en.wikipedia.org/wiki/Depth_first_search），限制您可以走多远。
于 2011-02-04T21:49:39.043 回答
2
对于网格中的每个点，存储：
- 单位到该点的最小距离。
- 以最短路径迈向单位的下一步。
为了计算这个，做一个广度优先搜索：
- 将单位的点距离成本设置为 0，并且它的“路径指针”无关紧要/为空。
- 创建一个队列并将初始点放入其中。
- 当队列不为空时：
- 取下一个点并传播它（查看所有邻居。如果通过当前点到达它们是有利可图的，则设置它们的距离/路径并将它们添加到队列的末尾）
记住要注意，如果您有限制，请在正确的步数后停止搜索。
如果您正确执行此操作，您可以找到所有可到达的点，找出它们的距离有多长，并且还有可用的最短路径（尽管它是“向后”存储的）
不要对最短路径问题进行深度优先搜索！您可能会一遍又一遍地进行许多重复计算。（除非您使用更高级的启发式算法，例如 A* - 但是您应该已经知道自己在做什么）
于 2011-02-05T02:11:38.737 回答
0
用相同的数字标记连接的单元格，而不是不同的连接单元格。您可以在http://en.wikipedia.org/wiki/Connected_Component_Labeling找到用于标记单元格的两遍算法。如果单元格的数量不同，则玩家无法到达该位置。
于 2011-02-04T21:52:48.060 回答