二维数组中的寻路 [英] Pathfinding in 2D Arrays

问题描述

假设我有这个二维数组地图

Let's say I have this 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*(使用节点/等)?你有什么建议?

and I have HashSet full of Integers that define blocked tiles. What would be a good way so that when I click on one part of the map from where my player is standing to do a good pathfinding? A* (using nodes/etc)? What do you suggest?

谢谢.

推荐答案

如果你的图的大小实际上是你描述的例子的顺序，那么你可以安全地使用 Dijkstra 的算法，考虑到它比 A* 更容易实现，如果可以的话，实际上不需要启发式算法几乎同时进行详尽的搜索:)

If the size of your graph is actually in the order of the example you've described, then you can safely use Dijkstra's algorithm, given that it's somewhat simpler to implement than A*, and there is no real need for heuristic algorithms if you can do an exhaustive search in almost the same time :)

至于您关于使用节点/等"的评论，这已经是一个图表，尽管对一个图表的表示有点尴尬.每个数组值都是一个节点，边"由数组中的邻接关系给出.被阻止的瓦片可以通过禁止邻接来完成(即查找被阻止的瓦片列表以确定另一个节点是否可以从当前正在考虑的节点到达)，或者正如 Yossarian 上面建议的那样，只需将该瓦片的成本设置为某个东西大到几乎无限.但是，如果您采用后一种方法，您需要确保这些图块永远不会无意中最终出现在解决方案中！

As for your comment about "using nodes/etc", this already is a graph, albeit a slightly akward representation of one. Every array value is a node, and "edges" are given by adjacency in the array. The blocked tiles can either be done by inhibiting adjacency (i.e. look up the list of blocked tiles to determine whether another node is reachable from the current one under consideration), or as Yossarian suggested above, just set the cost of that tile to something so large as to be practically infinite. However, if you take the latter approach, you'll want to ensure that those tiles never inadvertently end up in a solution!

这篇关于二维数组中的寻路的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！