文档章节

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

放个屁
 放个屁
发布于 2015/06/09 05:31
字数 1258
阅读 66
收藏 6
点赞 0
评论 0

A *方法总结

Summary of the A* Method

 

好了,在你通走了,奠定了一步一步的方法,在同一个地方:

Okay, now that you have gone through the explanation, let's lay out the step-by-step method all in one place:

 

添加开始方(或点)到开启列表。

Add the starting square (or node) to the open list.

 

重复以下操作

Repeat the following:

 

a) 找开启列表上最小F方块。我将此作当前方

  1. Look for the lowest F cost square on the open list. We refer to this as the current square

 

b) 到关列表。

  1. Switch it to the closed list.

 

c)  当前方块的8个方块的...

c) For each of the 8 squares adjacent to this current square …

 

如果不能走,或者如果它是关的名上,忽略它。否请执以下操作。

If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.

 

如果不在开启列表中,将其添加到开启列表。使当前方块成为这个方记录的方FGH

If it isn't on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.

 

如果开启列表了,检查,看看个路径,否是更好的,采用G衡量。更低的G意味着是一个更好的路径。如果是这样方格的父改当前方,并重新算方GF。如果你保持开启列表排序F由于这个化你可能需重存列表。

If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

 

d)当你停止:

d) Stop when you:

 

添加到关列表,在种情况下,路径已发现下面的注),或无法找到目,并且开启列表是空的。在种情况下,不存在路径。

Add the target square to the closed list, in which case the path has been found (see note below), or Fail to find the target square, and the open list is empty. In this case, there is no path.

 

保存路径。从目往回走,从每个方块移到其父,直到你到达开始是你的路径。

Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.

 

注:在早期版本的文章中,有人建,当目(或点)已添加到开启列表,而不是关的列表,你可以停下来。这样做会更快,它几乎是会你的最短路径,但并非是如此。有些情况下,这样做可能产生差异当从第二移到最后一个点到最后的(目成本可能有明显 -例如,在河流交叉两个点之的情况下

Note: In earlier versions of this article, it was suggested that you can stop when the target square (or node) has been added to the open list, rather than the closed list. Doing this will be faster and it will almost always give you the shortest path, but not always. Situations where doing this could make a difference are when the movement cost to move from the second to the last node to the last (target) node can vary significantly -- as in the case of a river crossing between two nodes, for example.

 

小咆哮

Small Rant

 

我的,但得指出的是,当你在网上阅读A *路径搜索,并在各类论坛上的各种讨论时,你偶会看到有人提到某些代不是A *A *使用方法,你需要包含上面讨论到的元素 -- 是开放列表和关列表和路径采用FGH值。有很多其他的路径搜索算法,但是其它的通常被认为是最好的方法不是A *。在篇文章的末尾布莱恩斯托特讨论,包括他的一些利弊引用的文章很多。有替代品在某些情况下更好,但你应该明白你正在入。好了,爽了。回到话题

Forgive me for digressing, but it is worth pointing out that when you read various discussions of A* pathfinding on the web and in assorted forums, you will occasionally see someone refer to certain code as A* when it isn't. For the A* method to be used, you need to include the elements just discussed above -- specifically open and closed lists and path scoring using F, G, and H. There are lots of other pathfinding algorithms, but those other methods are not A*, which is generally considered to be the best of the lot. Bryan Stout discusses many of them in the article referenced at the end of this article, including some of their pros and cons. Sometimes alternatives are better under certain circumstances, but you should understand what you are getting into. Okay, enough ranting. Back to the article.

 

(待续)


© 著作权归作者所有

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

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

壶漏子 ⋅ 2015/06/14 ⋅ 5

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

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

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

再译《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

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

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

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

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

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

weixin_40647819 ⋅ 05/23 ⋅ 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

Spring Security

重拾后端之Spring Boot(四):使用JWT和Spring Security保护REST API 重拾后端之Spring Boot(一):REST API的搭建可以这样简单重拾后端之Spring Boot(二):MongoDb的无缝集成重拾后端之...

掘金官方 ⋅ 01/04 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java Web如何操作Cookie的添加修改和删除

创建Cookie对象 Cookie cookie = new Cookie("id", "1"); 修改Cookie值 cookie.setValue("2"); 设置Cookie有效期和删除Cookie cookie.setMaxAge(24*60*60); // Cookie有效时间 co......

二营长意大利炮 ⋅ 今天 ⋅ 0

【每天一个JQuery特效】淡入淡出显示或隐藏窗口

我是JQuery新手爱好者,有时间就练练代码,防止手生,争取每天一个JQuery练习,在这个博客记录下学习的笔记。 本特效主要采用fadeIn()和fadeOut()方法显示淡入淡出的显示效果显示或隐藏元...

Rhymo-Wu ⋅ 今天 ⋅ 0

Spring JDBC使用方法

普通实现: 1、创建数据表customer。 可以使用任何数据库实现,在项目中要引入相应数据库驱动包并配置相应数据库连接。 2、创建Customer pojo。 Customer类的属性对应数据库的属性,除了为每...

霍淇滨 ⋅ 今天 ⋅ 0

Contos 7 安装Jenkins

Jenkins是一款能提高效率的软件,它能帮你把软件开发过程形成工作流,典型的工作流包括以下几个步骤 开发 提交 编译 测试 发布 有了Jenkins的帮助,在这5步中,除了第1步,后续的4步都是自动...

欧虞山 ⋅ 今天 ⋅ 0

revel

revel install go get github.com/revel/revelgo get github.com/revel/cmd create new app revel new git.oschina.net/zdglf/myapp run app revel run git.oschina.net/zdglf/myapp ot......

zdglf ⋅ 今天 ⋅ 0

49. Group Anagrams - LeetCode

Question 49. Group Anagrams Solution 思路:维护一个map,key是输入数组中的字符串(根据字符排好序) Java实现: public List<List<String>> groupAnagrams(String[] strs) { Map<Strin......

yysue ⋅ 今天 ⋅ 0

spring Email

使用spring发Email其实就是使用spring自己封装携带的一个javamail.JavaMailSenderImpl类而已。这个类可以当一个普通的java对象来使用,也可以通过把它配置变成spring Bean的方式然后注入使用...

BobwithB ⋅ 今天 ⋅ 0

spark 整理的一些知识

Spark 知识点 请描述spark RDD原理与特征? RDD全称是resilient distributed dataset(具有弹性的分布式数据集)。一个RDD仅仅是一个分布式的元素集合。在Spark中,所有工作都表示为创建新的...

tuoleisi77 ⋅ 今天 ⋅ 0

思考

时间一天天过感觉自己有在成长吗?最怕的是时光匆匆而过,自己没有收获!下面总结下最近自己的思考。 认识自己 认识另一个自己,人们常说要虚心听取别人意见和建议。然而人往往是很难做到的,...

hello_hp ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部