2

假设我有这个 2D Array map

{ 0,0,0,0,7,1,1,1,1,1,1,1,1 },
{ 0,7,7,7,7,1,1,1,24,1,1,1,1 },
{ 0,7,24,24,24,24,24,24,24,1,1,3,1 },
{ 0,7,23,23,23,23,23,23,24,1,1,3,1 },
{ 0,7,24,23,23,23,23,23,23,1,1,1,1 },
{ 0,7,24,23,23,23,23,23,23,1,1,1,1 },
{ 0,7,23,23,23,23,23,23,24,1,3,1,1 },
{ 0,7,24,24,24,24,24,24,24,1,3,1,1 },
{ 0,0,0,0,1,1,1,1,1,1,1,1,1 },

我有 HashSet 充满了定义被阻止的瓷砖的整数。什么是一种好方法,以便当我从我的玩家站立的位置单击地图的一部分时进行良好的寻路?A*(使用节点/等)?你有什么建议?

谢谢。

4

1 回答 1

6

如果图的大小实际上与您描述的示例的顺序相同,那么您可以安全地使用Dijkstra 算法,因为它比 A* 实现起来稍微简单一些,并且如果可以的话,实际上不需要启发式算法几乎在同一时间进行详尽的搜索:)

至于您对“使用节点/等”的评论,这已经是一个图表,尽管它是一个有点尴尬的表示。每个数组值都是一个节点,“边”由数组中的邻接关系给出。阻塞的图块可以通过抑制邻接来完成(即查找阻塞图块的列表以确定是否可以从当前正在考虑的节点访问另一个节点),或者如 Yossarian 上面建议的那样,只需将该图块的成本设置为大到实际上是无限的。但是,如果您采用后一种方法,您将希望确保这些图块永远不会无意中最终成为解决方案!

于 2010-07-21T15:30:02.777 回答