文档章节

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

放个屁
 放个屁
发布于 2015/06/08 20:15
字数 2777
阅读 62
收藏 1
点赞 0
评论 0

继续搜索

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]

(待续)


© 著作权归作者所有

共有 人打赏支持
放个屁
粉丝 123
博文 176
码字总数 285078
作品 0
日本
程序员
A*算法之烂片整理

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

壶漏子 ⋅ 2015/06/14 ⋅ 5

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

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

壶漏子 ⋅ 2015/06/11 ⋅ 0

再译《A *路径搜索入门》之流畅版??

A 路径搜索入门 帕特里克·莱斯特发表于2003年10月8日下午8点33人工智能 如果您发现文中有错误或问题(丢失的影像或文件,受损代码,不正确的文本格式等),导致无法阅读它时,请联系编辑,以...

壶漏子 ⋅ 2015/06/17 ⋅ 0

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

※※※ 外语不好凑合着看吧,呵呵 ※※※ A 路径搜索入门 A Pathfinding for Beginners 帕特里克·莱斯特发表于2003年10月8日下午8点33人工智能 By Patrick Lester Published Oct 08 2003 08...

壶漏子 ⋅ 2015/06/07 ⋅ 0

《鸡啄米C++编程入门系列》系列技术文章整理收藏

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

开元中国2015 ⋅ 2015/05/26 ⋅ 0

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

■延伸阅读 Further Reading 好了,现在你已具备了基础知识和一些先进的概念感。在这一点上,我建议你到涉水我的源代码。该软件包包含两个版本,一个是C ++的,一个是Blitz Basic的。两个版本...

壶漏子 ⋅ 2015/06/10 ⋅ 0

两层A *路径搜索之草译

两层A 路径搜索 Two-Tiered A Pathfinding 作者:帕特里克·莱斯特(更新2003年1月9日) By Patrick Lester ( Updated January 9, 2003) 在我的主打文章A 路径搜索入门(http://my.oschina.n...

壶漏子 ⋅ 2015/06/18 ⋅ 0

《鸡啄米VS2010/MFC编程入门》系列技术文章整理收藏

《鸡啄米VS2010/MFC编程入门》系列技术文章整理收藏 1VS2010/MFC编程入门之前言 http://www.lai18.com/content/410337.html 2VS2010/MFC编程入门之二(利用MFC向导生成单文档应用程序框架) ...

开元中国2015 ⋅ 2015/06/27 ⋅ 0

【掘金小报】第八期 怎么用 Python 实现每秒百万级的请求?

掘金小报主打分享优质深度技术内容,技术内容分:前端、后端、Android、iOS、产品设计、工具资源和一些有趣的东西。 注意:与标题的相关的文章在后端分类下的:《[译] 用 Python 实现每秒百万...

膜法小编 ⋅ 2017/05/05 ⋅ 0

VS2010/MFC编程入门教程之目录和总结(鸡啄米)

鸡啄米的这套VS2010/MFC编程入门教程到此就全部完成了,虽然有些内容还未涉及到,但帮助大家进行VS2010/MFC的入门学习业已足够。以此教程的知识为基础,学习VS2010/MFC较为深入的内容已非难事...

weixin_40647819 ⋅ 05/23 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

熊掌号收录比例对于网站原创数据排名的影响[图]

从去年下半年开始,我在写博客了,因为我觉得业余写写博客也还是很不错的,但是从2017年下半年开始,百度已经推出了原创保护功能和熊掌号平台,为此,我也提交了不少以前的老数据,而这些历史...

原创小博客 ⋅ 51分钟前 ⋅ 0

LVM讲解、磁盘故障小案例

LVM LVM就是动态卷管理,可以将多个硬盘和硬盘分区做成一个逻辑卷,并把这个逻辑卷作为一个整体来统一管理,动态对分区进行扩缩空间大小,安全快捷方便管理。 1.新建分区,更改类型为8e 即L...

蛋黄Yolks ⋅ 今天 ⋅ 0

Hadoop Yarn调度器的选择和使用

一、引言 Yarn在Hadoop的生态系统中担任了资源管理和任务调度的角色。在讨论其构造器之前先简单了解一下Yarn的架构。 上图是Yarn的基本架构,其中ResourceManager是整个架构的核心组件,它负...

p柯西 ⋅ 今天 ⋅ 0

uWSGI + Django @ Ubuntu

创建 Django App Project 创建后, 可以看到路径下有一个wsgi.py的问题 uWSGI运行 直接命令行运行 利用如下命令, 可直接访问 uwsgi --http :8080 --wsgi-file dj/wsgi.py 配置文件 & 运行 [u...

袁祾 ⋅ 今天 ⋅ 0

JVM堆的理解

在JVM中,我们经常提到的就是堆了,堆确实很重要,其实,除了堆之外,还有几个重要的模块,看下图: 大 多数情况下,我们并不需要关心JVM的底层,但是如果了解它的话,对于我们系统调优是非常...

不羁之后 ⋅ 昨天 ⋅ 0

推荐:并发情况下:Java HashMap 形成死循环的原因

在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障,并且这个事发生了很多次,原因是在Java语言在并发情况下使用HashMap造成Race Condition,从而导致死循环。这个事情我4、5年前也经历...

码代码的小司机 ⋅ 昨天 ⋅ 1

聊聊spring cloud gateway的RetryGatewayFilter

序 本文主要研究一下spring cloud gateway的RetryGatewayFilter GatewayAutoConfiguration spring-cloud-gateway-core-2.0.0.RC2-sources.jar!/org/springframework/cloud/gateway/config/G......

go4it ⋅ 昨天 ⋅ 0

创建新用户和授予MySQL中的权限教程

导读 MySQL是一个开源数据库管理软件,可帮助用户存储,组织和以后检索数据。 它有多种选项来授予特定用户在表和数据库中的细微的权限 - 本教程将简要介绍一些选项。 如何创建新用户 在MySQL...

问题终结者 ⋅ 昨天 ⋅ 0

android -------- 颜色的半透明效果配置

最近有朋友问我 Android 背景颜色的半透明效果配置,我网上看资料,总结了一下, 开发中也是常常遇到的,所以来写篇博客 常用的颜色值格式有: RGB ARGB RRGGBB AARRGGBB 这4种 透明度 透明度...

切切歆语 ⋅ 昨天 ⋅ 0

CentOS开机启动subversion

建立自启动脚本: vim /etc/init.d/subversion 输入如下内容: #!/bin/bash## subversion startup script for the server## chkconfig: 2345 90 10# description: start the subve......

随风而飘 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部