page2.asp.html

实现人工智能中的AI自动寻找路径

      <p>F is calculated by adding G and H. The results of the first
step in
our search can be seen in the illustration below. The F, G, and H
scores are written in each square. As is indicated in the square to the
immediate right of the starting square, F is printed in the top left, G
is printed in the bottom left, and H is printed in the bottom right.<br>
G和H相加就算出了F。第一步搜索的结果见下图的描述。F，G，和H值都写入了每个方块。如开始方块相邻右边的方块，F显示在左上方，G显示在左下方，而
H显示在右下方。<br>
      </p>
      <p class="caption"><img border="0" width="362" height="256"
 src="page2.asp_files/image003.jpg"> <br>
[图 3][Figure 3]</p>
      <p>So let's look at some of these squares. In the square with the
letters in it, G = 10. This is because it is just one square from the
starting square in a horizontal direction. The squares immediately
above, below, and to the left of the starting square all have the same
G score of 10. The diagonal squares have G scores of 14.<br>
好，让我们来观察某些方块。在有字母的方块中，G =
10。这是由于在水平方向上从开始点（到那里）只有一个方块（的距离）。开始点相邻上方，下方和左边的方块都具有同样的G值：10。斜角的方块G值为
14。<br>
      </p>
      <p>The H scores are calculated by estimating the Manhattan
distance to
the red target square, moving only horizontally and vertically and
ignoring the wall that is in the way. Using this method, the square to
the immediate right of the start is 3 squares from the red square, for
a H score of 30. The square just above this square is 4 squares away
(remember, only move horizontally and vertically) for an H score of 40.
You can probably see how the H scores are calculated for the other
squares.<br>
H的计算通过估算Manhattan距离而得，即：水平/垂直移动，忽略途中的障碍，到达红色的目标方块的距离。用这种方法，开始点相邻右边的方块和红色
方块相距3个方块，那么H值就是30。其上的方块距离为4（记住，只能水平或者垂直移动），H就是40。你也许可以看看其他方块的H值是如何算出的。<br>
      </p>
      <p>The F score for each square, again, is simply calculated by
adding G and H together.<br>
每个方块的F值，再说一下，不过就是G和H相加。<br>
      </p>
      <h1>持续的搜索Continuing the Search</h1>
      <p>To continue the search, we simply choose the lowest F score
square
from all those that are on the open list. We then do the following with
the selected square:<br>
为了继续搜索，我们简单的选择开放列表里具有最小F值的方块。然后对选定的方块做如下操作：<br>
      </p>
      <ol start="4">
        <li>Drop it from the open list and add it to the closed list.</li>
        <li>将他从开放列表取出，并加入封闭列表。</li>
        <li>Check
all of the adjacent squares. Ignoring those that are on the closed list
or unwalkable (terrain with walls, water, or other illegal terrain),
add squares to the open list if they are not on the open list already.
Make the selected square the "parent" of the new squares.</li>
        <li>测试所有的相邻方块。忽略封闭列表内的和不可行走的（墙，水及其它非法地形）方块，如果方块不在开放列表中，则添加进去。将选定
方块作为这些新加入方块的父亲。</li>
        <li>If an adjacent square is already on the open list, check
to see if this path to that square is a better one. In other words,
check to see if the G score for that square is lower if we use the
current square to get there. If not, don't do anything. <br>
On the other hand, if the G cost of the new path is lower,
change the parent of the adjacent square to the selected square (in the
diagram above, change the direction of the pointer to point at the
selected square). Finally, recalculate both the F and G scores of that
square. If this seems confusing, you will see it illustrated below.</li>
        <li>如果一个相邻方块已经存在于开放列表，检查到达那个方块的路径是否更优。换句话说，检查经由当前方块到达那里是否具有更小的G
值。如果没有，不做任何事。<br>
相反，如果新路径的G值更小，把这个相邻方块的父亲改为当前选定的方块（在上图中，修改其指针方向指向选定方块）。最后，重新计算那个方块的F和G值。如
果这样还是很迷惑的话，后面还会有图解说明。</li>
      </ol>
      <p>Okay, so let's see how this works. Of our initial 9 squares,
we have
8 left on the open list after the starting square was switched to the
closed list. Of these, the one with the lowest F cost is the one to the
immediate right of the starting square, with an F score of 40. So we
select this square as our next square. It is highlight in blue in the
following illustration.<br>
好了，让我们看看它是怎样工作的。在初始的9个方块中，当开始方块被纳入封闭列表后，我们的开放列表就只有8个方块了。在这些块中，具有最小F值的是开始
方块相邻右边的那个，其F值为40。所以我们选定这个块作为下一个方块。在随后的图例中，它以高亮的蓝色表示。<br>
      </p>
      <p class="caption"><img border="0" width="357" height="256"
 src="page2.asp_files/image004.jpg"> <br>
[图 4][Figure 4]</p>
      <p>First, we drop it from our open list and add it to our closed
list
(that's why it's now highlighted in blue). Then we check the adjacent
squares. Well, the ones to the immediate right of this square are wall
squares, so we ignore those. The one to the immediate left is the
starting square. That's on the closed list, so we ignore that, too.<br>
首先，我们把它从开放列表取出，并加入到封闭列表（这就是它现在是高亮的蓝色的原因）。然后我们检查相邻的方块。然而，这个方块相邻右边的是代表墙的方
块，所以忽略它们。其相邻左边是开始方块。它处于封闭列表内，所以也忽略它<br>
      </p>
      <p>The other four squares are already on the open list, so we
need to
check if the paths to those squares are any better using this square to
get there, using G scores as our point of reference. Let's look at the
square right above our selected square. Its current G score is 14. If
we instead went through the current square to get there, the G score
would be equal to 20 (10, which is the G score to get to the current
square, plus 10 more to go vertically to the one just above it). A G
score of 20 is higher than 14, so this is not a better path. That
should make sense if you look at the diagram. It's more direct to get
to that square from the starting square by simply moving one square
diagonally to get there, rather than moving horizontally one square,
and then vertically one square.<br>
其它4个已经在开放列表中了，所以我们需要检查经由当前方块到达他们是否是更优的路径，使用G值为参考点。我们来看看这个选定方块上面右边的那个方块。它
的当前G值是14。如果我们经由当前方块到达那里，G值将是20（10，到达当前方块的G值，再加上10垂直移动到它上面的方块）。20 &gt;
14，所以这不是一个好的路径。看看图解能更好的理解这些。从开始方块斜向移动到那个方块更直接，而不是水平移动一个方块，再垂直移动一个方块。<br>
      </p>
      <p>When we repeat this process for all 4 of the adjacent squares
already on the open list, we find that none of the paths are improved
by going through the current square, so we don't change anything. So
now that we looked at all of the adjacent squares, we are done with
this square, and ready to move to the next square.<br>
当我们对已经存在于开放列表的所有4个相邻方块都重复这个过程，我们发现经由当前方块没有更佳的路径，所以什么也不用改变。现在看看所有的相邻方块，我们
已经处理完毕，并准备移动到下一个方块。<br>
      </p>
      <p>So we go through the list of squares on our open list, which
is now
down to 7 squares, and we pick the one with the lowest F cost.
Interestingly, in this case, there are two squares with a score of 54.
So which do we choose? It doesn't really matter. For the purposes of
speed, it can be faster to choose the <u>last</u> one you added to the
open list. This biases the search in favor of squares that get found
later on in the search, when you have gotten closer to the target. But
it doesn't really matter. (Differing treatment of ties is why two
versions of A* may find different paths of equal length.)<br>
现在，我们再遍历开放列表，它只有7个方块了，选择具有最小F值的那个。有趣的是，此时有两个方块都有值54。那么我们选择哪个？实际上这不算什么。为了
速度的目的，选择你最后加入到开放列表的那个方块更快。当你更接近目标的时候，它倾向于后发现的方块。但这真的没什么关系。（不同的处理造成了两
个版本的A*可能找到不同的等长路径。）<br>
      </p>
      <p>So let's choose the one just below, and to the right of the
starting square, as is shown in the following illustration.<br>
我们选择下面的那个，位于开始方块的右边，如下图所示。<br>
      </p>
      <p class="caption"><img border="0" width="357" height="254"
 src="page2.asp_files/image005.jpg"> <br>
[图 5][Figure 5]</p>
      <p>This time, when we check the adjacent squares we find that the
one
to the immediate right is a wall square, so we ignore that. The same
goes for the one just above that. We also ignore the square just below
the wall. Why? Because you can't get to that square directly from the
current square without cutting across the corner of the nearby wall.
You really need to go down first and then move over to that square,
moving around the corner in the process. (Note: This rule on cutting
corners is optional. Its use depends on how your nodes are placed.)<br>
这一次，当检查相邻的方块时，我们相邻右边的是一个墙方块，所以忽略它。对那个方块上面的块同样忽略。我们也忽略墙下面的方块。为什么？因为你不把临近墙
的角切开就无法直接到达那个方块。实际上你需要先向下走，然后越过那个方块，在这个过程中都是围绕角在移动。（说明：切开角的规则是可选的。它的使用依赖
于你的节点如何放置。）<br>
      </p>
      <p>That leaves five other squares. The other two squares below
the
current square aren't already on the open list, so we add them and the
current square becomes their parent. Of the other three squares, two
are already on the closed list (the starting square, and the one just
above the current square, both highlighted in blue in the diagram), so
we ignore them. And the last square, to the immediate left of the
current square, is checked to see if the G score is any lower if you go
through the current square to get there. No dice. So we're done and
ready to check the next square on our open list.<br>
这样就剩下5个方块了。当前方块下的两个方块不在开放列表中，所以要添加他们，并把当前方块作为它们的父亲。在另外三个方块中，有两个已经在封闭列表中了
（开始方块，和当前方块上面的那个，它们都用高亮的蓝色在图中标出来了），所以忽略它们。最后一个方块，当前方块相邻左边的那个，检查经由当前方块到达那
里是否得到更小的G值。没有。所以处理完毕，并准备检查开放列表中的下一个方块。<br>
      </p>
      <p>We repeat this process until we add the target square to the
open
list, at which point it looks something like the illustration below.<br>
我们重复这个过程，直到把目标点添加到开放列表，此时的情形如下图所示。<br>
      </p>
      <p class="caption"><img border="0" width="404" height="307"
 src="page2.asp_files/image006.jpg"> <br>
[图 6][Figure 6]</p>
      <p>Note that the parent square for the square two squares below
the
starting square has changed from the previous illustration. Before it
had a G score of 28 and pointed back to the square above it and to the
right. Now it has a score of 20 and points to the square just above it.
This happened somewhere along the way on our search, where the G score
was checked and it turned out to be lower using a new path