寻路在Java中

比方说，我使用数组以此来绘制出我的游戏地图：寻路在Java中

{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, 
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 }, 
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 }, 
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 }, 
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 }, 
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 }, 
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 }, 
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 }, 
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 }, 
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 }, 
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

我有，而其他未被阻止被阻塞片号的ArrayList<>。我可以通过检查blocked(X,Y)进行检查，它将通过检查当前地图上该图块的X和Y来返回true或false，然后它会查看该图块是否在BLOCKED ArrayList<>中。无论如何，这里寻找最好的方法是什么？

来源

2011-03-03 nn2

您可以使用图搜索算法，例如Breadth-first search。你可以在谷歌找到的实现，有很多例子。

来源

2011-03-03 05:04:47

我认为通过寻路你的意思是你想找到从细胞（x1，y1）到细胞（x2，y2）的最短路径。这里需要一些更多的信息。如何定义相邻小区 - 即，我可以从一个小区移动到4个neighbours还是6个邻居，包括对角线移动？移动到任何单元的成本是否相同，还是根据单元类型或是行/列移动还是对角线移动而变化？

假设移动的成本对于所有单元格都是相同的，并且每个单元格与它共享边缘的4个单元格相邻，但这基本上是一个在简单的未加权图表中找到最短路径的简单问题。为此，您可以使用breadth first search。图形的节点是单元格，每个单元格（顶部行&以及左和右最低着色区域除外）具有四条边（每个相邻单元格各一条）。当我们访问每个节点时，我们只是跳过被阻止的节点。

伪代码：

shortest path(start,end, blocked): 
    cost=map of node:int 
    visited=set of nodes 
    dx=array {0,1,0,-1} 
    dy=array {1,0,-1,0} 
    Q=queue of nodes 
    cost[start]=0 
    add start to Q 
    while Q is not empty: 
     node=remove top from Q 
     for i=0 until 4: 
      next=new node with next.x=node.x+dx[i], next.y=node.y+dy[i] 
      if (next is a valid node) and (next is not in visited) and (next is not in blocked): 
       cost[next]=cost[node]+1 
       add next to visited 
       add next to Q 
    if end is in visited: 
     return cost[end] 
    else: 
     return -1

来源

2011-03-03 05:07:49 MAK

寻路在Java中

回答

相关问题