文档章节

再译《A *路径搜索入门》之三

如比如比
 如比如比
发布于 2015/06/08 20:15
字数 2777
阅读 76
收藏 1

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

继续搜索

Continuing the Search

 

继续搜索,我们简单选择在开启列表中具有最小F的方。然后,我们用选择以下事情

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:

 

1.它从开启列表取出,并加入到列表

1.Drop it from the open list and add it to the closed list.

 

2.检查所有的相。忽略那些列表或不可行走的(,水或其他非法地形),如果它们还不在开启列表中加方开启列表。将定方块作为新方块的“父”。

2.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.

 

3.如果相的方开启列表条路那个是否是一个更好的。话说检查,看看方G是否是低,如果我使用当前方到那里。如果没有,什么也不做。

3.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.

 

另一方面,如果新路径的G值较低,改方格的父到定方格(中上方,改的方向指向在所选择方格)。最后,重新算那个方的两个FG。如果似乎令人困惑,你会看到它所示。

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.

 

好吧,看看是如何工作的。我最初的9个方格,在起始到关列表8个在开启列表。其中,具有最低F的是一个起点方紧邻右侧的,其F值为40。因此,我们选择这个方们的下一个方。如下所示高亮的的部分

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.

 

[4]

[Figure 4]

 

首先,从开启列表中除它,并把它添加到关列表(就是它以高亮的原因)。然后检查的方。好了,个方的相的是上的方,忽略。一个眼前的左是开始方是关的名上,所以忽略

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.

 

其他四个方格已在开启列表中,所以我需要检查如果使用那些方块作为是否比使用个方到那里更好,将G的参照点。来看看选择的这个块吧G14,如果由当前方到达那里,G将等于2010现在G,再加上10垂直到它的上面)。G2014高,所以不是一个更好的路径。如果你看一下图能更好的理解这些。从开始方格方沿线一个方格到那里更直接,而不是水平移一个方,再垂直移一个方

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.

 

在开启列表中4个相方格重复程,我们发现没有路径比当前的方块有提高,因此我不会改任何西。所以,在,我看了所有的相,我都与个方块作,并准到下一个方

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.

 

那么开启列表,减到7方格的列表,我们选择了一个具有最小F。有趣的是,在种情况下,有两个方F值是54,那么们选择哪个并不重要。为了快速的目的,它可以更快地选择您添加到开启列表中最后一个。得到后来发现在搜索你更接近目标时。但它其并不重要。 (不同的理造成了两个版本的A *可能找到不同的等路径。)

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 last 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.)

 

因此,们选择一个下方,并开始方的右,如下所示。

So let's choose the one just below, and to the right of the starting square, as is shown in the following illustration.

[5]

[Figure 5]

 

一次,当我们检查的方,我们发现,一到右立即是一堵,所以我忽略。适用于一个刚刚上面。我们还忽略略低于上的方什么呢?因你不能得到直接从当前方没有穿越附近的角切割。你真的需要往下走,然后再动过那个方围绕程中角落移 (注:上工减料规则是可的它的使用依于你的点如何放置。)

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.)

 

那剩下5个方。另外两个方格低于当前尚未开启列表中,所以我将它添加并把当前方块变成他的父。其他三个平方,有两个已在关列表(开始方,和一个略高于目前的方上,在色突出两个中),所以我忽略他。而最后的方,眼前的当前方检查,看是否G低了,如果你去通过当前方块到那里。没有方块了。所以,我就大功告成了,并准备检查开启列表中的下一个方

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.

 

重复程,直到我添加目列表,此它看起来像下面的插

We repeat this process until we add the target square to the closed list, at which point it looks something like the illustration below.

 

[6]

[Figure 6]

 

需要注意的是从上低于初始方格两格父方格已。之前,它的G值为28,指向回它右上的方在它有一个20分,并指向它上面方这发生在我的搜索,G检查那里的方式,它竟然采用了要低一些的作为路径- 这样的父被切GF也重新算。在个例子中化似乎并不太重要,有很多可能的情况下,种持检查将会使所有的差异在确定目的最佳路径。

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 – so the parent was switched and the G and F scores were recalculated. While this change doesn't seem too important in this example, there are plenty of possible situations where this constant checking will make all the difference in determining the best path to your target.

 

那么,我如何确定路径?简单开始在红色的,并努力从一格向后移到它的父,下面的箭你回到开始方就是你的路径。它应该看起来像下面的插。移从开始方A到目B就是从路径上每一个方点)的中心移动到下一个方的中心的问题,直到到达目

So how do we determine the path? Simple, just start at the red target square, and work backwards moving from one square to its parent, following the arrows. This will eventually take you back to the starting square, and that's your path. It should look like the following illustration. Moving from the starting square A to the destination square B is simply a matter of moving from the center of each square (the node) to the center of the next square on the path, until you reach the target.

 

[7]

[Figure 7]

(待续)


如比如比
粉丝 126
博文 178
码字总数 286951
作品 0
日本
程序员
私信 提问
加载中
请先登录后再评论。
A*算法之烂片整理

把A算法的几个烂片整理一下。 缘起于 是Google对开源中国有意见,还是我们"非著名" http://www.oschina.net/question/660460238919 其实事情的经过是这样地☜☜☜☜☜☜英文的原篇地址在这里...

放个屁
2015/06/14
392
5
Qt相关博客总览

一、Qt快速入门 Qt快速入门之一:开始学习Qt 与Qt Creator Qt快速入门之二:Qt Creator简介 Qt快速入门之三:Qt程序编译和源码详解 Qt对话框之一:标准对话框 二、Qt窗口部件与布局 Qt窗口部...

osc_869quh0r
2019/07/24
6
0
《鸡啄米C++编程入门系列》系列技术文章整理收藏

《鸡啄米C++编程入门系列》系列技术文章整理收藏 收藏整理鸡啄米C++编程入门系列文章,供个人和网友学习C++时参考 1鸡啄米:C++编程入门系列之前言 2鸡啄米:C++编程入门系列之一(进制数) ...

开元中国2015
2015/05/26
132
0
《鸡啄米C++编程入门系列》系列技术文章整理收藏

《鸡啄米C++编程入门系列》已整理成PDF文档,点击可直接下载至本地查阅 https://www.webfalse.com/read/201812.html 文章 鸡啄米:C++编程入门系列之前言 鸡啄米:C++编程入门系列之一(进制...

开元中国2015
2015/06/27
126
0
再译《A *路径搜索入门》之五

■实施上的注意事项 Notes on Implementation 现在您了解了基本的方法,当你编写自己的程序时,有一些额外的事情要考虑。下面给出我用C ++和Blitz Basic编写的程序,用其他语言也同样有效。 ...

放个屁
2015/06/11
76
0

没有更多内容

加载失败,请刷新页面

加载更多

插入,在PostgreSQL中重复更新吗? - Insert, on duplicate update in PostgreSQL?

问题: Several months ago I learned from an answer on Stack Overflow how to perform multiple updates at once in MySQL using the following syntax: 几个月前,我从关于堆栈溢出的答案......

技术盛宴
15分钟前
20
0
互联网的寒冬下各大一线互联网公司还在用SpringBoot这是为什么?

引言 现在各大技术社区 Spring Boot 的文章越来越多,Spring Boot 相关的图文、视频教程越来越多,使用 Spring Boot 的互联网公司也越来越多; Java 程序员现在出去面试, Spring Boot 已经成...

北柠Java
18分钟前
8
0
vue+elementui实现简易的列筛选功能实现。

一、简易效果图: 二、需求背景 大家都知道,后管类系统当中,有时一个列表可能有很多列需要展示,如下图所示,但是用户在使用系统的时候,往往会需要针对其中某几列进行数据提取,在展示列比...

一生懸命吧
21分钟前
42
0
批处理问题记录——数字实验bat

记录学习批处理时的问题 批处理为输入一个数字,如果大于等于一百,直接输出输入数字,如果小于一百会重复+1,直到100后输出。 问题是,如果不输入数字,直接空格的话,批处理会出错。 寻求一...

愤怒的乌老大
27分钟前
6
0
算法题汇总

计算两个字符串中的最大的相同字符串

佳幂小煜
37分钟前
27
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部