在寻路二维数组 [英] 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 :)

至于你提到使用节点的/ etc评论，这已经是一个曲线图，虽然一个稍微akward的再presentation。每个数组的值是一个节点，而边缘是通过邻接阵列中给出。被阻止的瓷砖可以通过抑制邻接来完成（即查找堵塞瓷砖的列表来确定另一个节点是否是考虑当前的可达），或约塞连上述建议，只是设置瓷砖的东西成本，让大到在实际上是无限的。但是，如果采取后一种方式，你要确保这些砖永远不会在非故意的溶液中结束了！

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屋！