寻找建筑物（A *有多个坐标）？

1）我想到一个游戏，我们可以建造建筑物，其中有许多瓷砖，例如3x3。寻找建筑物（A *有多个坐标）？

所以之前开始构建的，我需要角色移动到相邻的瓷砖。那么有一种算法可以找到建筑区域的最短路径？

我们是否有义务对使用面积的建筑物的每瓦A *，并选择最短？

编辑，为例：

地图：

对于本例，（0，0）坐标是在上留下这一具有里程碑意义的形象：想象你的角色是在（0; 0）

我寻找算法来字符cloest向左移动BULDING上的图像。 [坐标：（1; 2），（8,2），（1,10），（8，10）]

目标不是像“正常”情况的单个坐标，而是一个aera点）。

那么，什么是找到最接近的位置（不包括对角线）从单一的起始坐标[这里，（0,0）]的最佳途径的地区[点击这里：（1; 2），（8,2），（1,10），（8,10）]？

我想要algo返回数组的解决方案，所以在多种情况下，如在这个例子中：[（0,2），（1,1）]，没有选择一个解决方案，理由给我所有等价的解决方案。

2）地图的无瓦的系统同样的问题，只是坐标？

来源

2017-09-04 Matrix

，如果你有瓷砖你有2D/3D数组/网格/地图，所以我会使用'A *'的网格变体而不是图形版本（你建议），它更适合于矢量数据。请参阅[如何在大空间尺度下加速A *算法？]（https://stackoverflow.com/a/23779490/2521214）和[算法Trax获胜条件]（https://stackoverflow.com/a/29765542/ 2521214）如果通过多个坐标来表示更多的目的地点，那么这是完全不同的问题提示TSP（旅行商问题） – Spektre

我用一个例子编辑，最清楚？ – Matrix

我们是否有义务在区域建筑物的每个区块上使用A *并选择最短？

否，A *可以采取目标谓语，这并不一定是“在当前坐标等于这个坐标”，它可以很容易地“时，当前坐标在某些包含集/地区”。这并没有改变算法的全局结构，只是退出测试。

当然，你必须保持你的启发式受理。

为了澄清，而不是这种 “窄” 的伪代码为A *（从维基复制）

current := the node in openSet having the lowest fScore[] value 
    if current = goal 
     return reconstruct_path(cameFrom, current)

你可以有这样的：

current := the node in openSet having the lowest fScore[] value 
    if current ∈ goals 
     return reconstruct_path(cameFrom, current)

或者这样：

current := the node in openSet having the lowest fScore[] value 
    if satisfiesGoalCondition(current) 
     return reconstruct_path(cameFrom, current)

这可以是一些测试，如“当前坐标是在目标矩形内”。

来源

2017-09-04 13:24:44 harold

对不起，我不真正了解，你的方法是获得一个坐标，最接近面积目标？ – Matrix

@Matrix你是什么意思？ – harold

我用一个例子编辑 – Matrix

那么array/grid version of A*可以在目标区域的任何命中时停止，所以从起点开始直到命中任何目标坐标，然后backtrack。

是的，你也可以使用图形/矢量版本，你可以将任何障碍物设置为节点。

如果你的瓷砖是（半）步行，那么网格版本A*是更好的，因为你可以利用它。您只需制作2D即可展示您的每个瓷砖标记可行走和墙壁区域。事情是这样的：

Algorithm Trax Winning Condition

，这将允许您通过楼宇导航太...我不但是你的建筑物内看到，所以我敢打赌，你没有想到这直到现在。看一看：

2D Diamond (isometric) map editor一些内部的建设思路

我使用3D网格，所以我就3D地形和建筑物也可以有水平......你只需要调整视图任选切割成上述球员的东西水平是这样的：

来源

2017-09-05 09:23:46 Spektre

我有相同版本的A *（但在JavaScript中用于我的用例）。 “问题”是A *只需要一对坐标就可以开始和达到'A_star :: compute（int x0，int y0，int x1，int y1）'。所以我必须在属于建筑物的每对坐标上尝试A *（你说我们可以在找到解决方案时打破循环，但如果我们不尝试所有方法，怎么能确定它是不可能的）？ – Matrix

@Matrix您可以在地图上测试特定网格值（如建筑物的标记区域），而不是将每个单元格坐标传递给A *，并在每次迭代中测试匹配单元格的位置。我通常将所有内容都编码为32位的DWORD单元格，所以我只得到了单个二维数组，其中包括展位世界地图，A *填充，特定标志...... – Spektre

@Matrix迭代A *填充顺序排列，所以第一次击中目标是最短路径并不重要多少单元格被标记为目标...除非你使用了一些奇怪的递归A *，其中这将是一个问题 – Spektre

寻找建筑物（A *有多个坐标）？

回答

相关问题