文档章节

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

放个屁
 放个屁
发布于 2015/06/07 11:47
字数 2080
阅读 132
收藏 2
点赞 0
评论 0

※  外语不好凑合着看吧,呵呵  

A *路径搜索

A* Pathfinding for Beginners

 

帕特里克·莱斯特表于2003108日下午833人工智能

By Patrick Lester Published Oct 08 2003 08:33 PM in Artificial Intelligence

 

如果您发现本文中包含错误或问题,导致无法读取它(丢失的影像或文件,受损代码,不正确的文本格式等),请联系编辑,以便能更正。感谢您帮助我们改善此资源。

If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource.

 

更新2005718

Updated July 18, 2005

 

篇文章已被翻成阿巴尼亚语,中文,法,德,葡萄牙,俄和西班牙。其他的翻迎的。篇文章的底部件地址。

This article has been translated into Albanian, Chinese, French, German, Portuguese, Russian, and Spanish. Other translations are welcome. See email address at the bottom of this article.

 

于初学者 A *A-,译者注:老外读A-star)算法可能有些在网上有很多解A *的文章,大多数写给有A *础的篇文章是真正的初学者。

The A* (pronounced A-star) algorithm can be complicated for beginners. While there are many articles on the web that explain A*, most are written for people who understand the basics already. This article is for the true beginner.

 

本文并不试图成为一主威著作。相反,它描述的基本原并准你去阅读所有其他材料和明白他什么。在篇文章的末尾提接到一些最好的来一步阅读

This article does not try to be the definitive work on the subject. Instead it describes the fundamentals and prepares you to go out and read all of those other materials and understand what they are talking about. Links to some of the best are provided at the end of this article, under Further Reading.

 

最后,篇文章不是具体方案。你应该里的任何算机言。正如你所期望的,然而, 篇文章的末尾,我有一个接到本文的示例程序。例子包中包含两个版本:一个是C++,一个Blitz Basichttp://www.blitzbasic.com/Home/_index_.php。它包含可行文件,如果你只是想看看A *的行

Finally, this article is not program-specific. You should be able to adapt what's here to any computer language. As you might expect, however, I have included a link to a sample program at the end of this article. The sample package contains two versions: one in C++ and one in Blitz Basic. It also contains executables if you just want to see A* in action.

 

但是我越来越提前。从开始......

But we are getting ahead of ourselves. Let's start at the beginning ...

 

介:搜索区域

Introduction: The Search Area

 

假设有想要A点到达B点。设有墙把AB点隔开示,绿表示起点A,用表示B并用填充的表示中间的那面

Let's assume that we have someone who wants to get from point A to point B. Let's assume that a wall separates the two points. This is illustrated below, with green being the starting point A, and red being the ending point B, and the blue filled squares being the wall in between.

[1]

[Figure 1]

 

首先,我搜索区域分割方形网格。这叫简化搜索区域,是路径搜索的第一步。种方法搜索区域简化一个二。数中的每一个元素代表网格里的一个方块,它的地位被记录为行走和不可行走。从AB经过的方块叫路径一旦路径被找到发现就可以从一个正的中心到下一个中心,直到到达目

The first thing you should notice is that we have divided our search area into a square grid. Simplifying the search area, as we have done here, is the first step in pathfinding. This particular method reduces our search area to a simple two dimensional array. Each item in the array represents one of the squares on the grid, and its status is recorded as walkable or unwalkable. The path is found by figuring out which squares we should take to get from A to B. Once the path is found, our person moves from the center of one square to the center of the next until the target is reached.

 

些中心点被称点”。在看别的路径搜索资料时常会看到讨论节点。什么不叫它们方格呢?因有可能路径搜索积不分割成方格。可以是矩形,六形,三角形或任何形状,真的。点可以任何形状表示- 在中心或者沿着边缘,或其他任何地方。不,我使用,因它是最简单的。

These center points are called "nodes". When you read about pathfinding elsewhere, you will often see people discussing nodes. Why not just call them squares? Because it is possible to divide up your pathfinding area into something other than squares. They could be rectangles, hexagons, triangles, or any shape, really. And the nodes could be placed anywhere within the shapes – in the center or along the edges, or anywhere else. We are using this system, however, because it is the simplest.

 

开始搜索

Starting the Search

 

一旦搜索区域化成管理数量的点,就像上面所说的网格布局,下一步就是行搜索找到最短路径。A开始检查方块并向外普及搜索,直到找到目

Once we have simplified our search area into a manageable number of nodes, as we have done with the grid layout above, the next step is to conduct a search to find the shortest path. We do this by starting at point A, checking the adjacent squares, and generally searching outward until we find our target.

 

们执行以下操作开始搜索:

We begin the search by doing the following:

 

1.起点A开始,并将添加到 “开列表”。开列表有点像一张购物清尽管列表里只有一个目,但以后会有更多。它包含了可能是你想要的,也可能不是。基本上,是需要被检查的方的列表。

1.Begin at the starting point A and add it to an "open list" of squares to be considered. The open list is kind of like a shopping list. Right now there is just one item on the list, but we will have more later. It contains squares that might fall along the path you want to take, but maybe not. Basically, this is a list of squares that need to be checked out.

 

2.寻找起点所有到达或可行走的方,忽略有,水或其他非法地形。添加到开列表。于每一个方,保存A点作它们的“父方”。当要追溯路径时父方格西是很重要的。稍后会解它。

2.Look at all the reachable or walkable squares adjacent to the starting point, ignoring squares with walls, water, or other illegal terrain. Add them to the open list, too. For each of these squares, save point A as its "parent square". This parent square stuff is important when we want to trace our path. It will be explained more later.

 

3.从开列表删除开始A,并将添加到不需要再次寻找的“关闭列表”。

3.Drop the starting square A from your open list, and add it to a "closed list" of squares that you don't need to look at again for now.

 

一点上,你应该下面插形象。在该图中,位于中心的深绿色方就是开始方。它是色,以指示已被添加到封列表。在开启列表的所有相块进检查,并且绿来框记它们。每个方格都有一个灰色的指指回它们的父方格,也就是开始方

At this point, you should have something like the following illustration. In this illustration, the dark green square in the center is your starting square. It is outlined in light blue to indicate that the square has been added to the closed list. All of the adjacent squares are now on the open list of squares to be checked, and they are outlined in light green. Each has a gray pointer that points back to its parent, which is the starting square.

 

[2]

[Figure 2]

 

下一步,我们选择了开启列表上的一个,并或多或少重复前面的,如下所述。但是,我们选择哪方?一个与最小F

Next, we choose one of the adjacent squares on the open list and more or less repeat the earlier process, as described below. But which square do we choose? The one with the lowest F cost.

 




© 著作权归作者所有

共有 人打赏支持
放个屁
粉丝 123
博文 177
码字总数 285078
作品 0
日本
程序员
再译《A *路径搜索入门》之五

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

放个屁
2015/06/11
0
0
再译《A *路径搜索入门》之流畅版??

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

放个屁
2015/06/17
0
0
再译《A *路径搜索入门》之六

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

放个屁
2015/06/10
0
0
【掘金小报】第八期 怎么用 Python 实现每秒百万级的请求?

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

膜法小编
2017/05/05
0
0
再译《A *路径搜索入门》之四

■在A 方法总结 Summary of the A Method 好了,现在你通过解释已经走了,让我们奠定了一步一步的方法,在同一个地方: Okay, now that you have gone through the explanation, let's lay ...

放个屁
2015/06/09
0
0
Scala 技术周刊 | 第 22 期

这里有最新的 Scala 社区动态、技术博文。 微信搜索 「scalacool」关注我们,及时获取最新资讯。 深度阅读 Status of the Collections Scala 集合重构进展 Akka 系列(十):Akka 集群之 Ak...

ScalaCool
2017/09/22
0
0
再译《A *路径搜索入门》之三

■继续搜索 Continuing the Search 要继续搜索,我们简单地选择在开启列表中具有最小F值的方块。然后,我们用选择方块作以下事情: To continue the search, we simply choose the lowest F ...

放个屁
2015/06/08
0
0
再译《A *路径搜索入门》之二

■路径评分 Path Scoring 计算出的路径时,确定要使用的方格的关键是下面的公式: The key to determining which squares to use when figuring out the path is the following equation: F ...

放个屁
2015/06/07
0
0
编程零基础应当如何开始学习 Python ?

提前说一下,这篇福利多多,别的不说,直接让你玩回最有手感的怀旧游戏,参数贴图很方便自己可以根据喜好修改哦。 本篇通过以下四块展开,提供大量资源对应。 【选一个好版本 有没有看过《在...

崔斯特呀
2017/09/14
0
0
ASP.NET 学习历程

[注意我不推荐高级技术的书,因为你如果是个高手了就可以自己选择甄别书了, 此文只对初学者,因为他们此时没有辨别好快的能力,本人几乎买尽所有的.NET书,有好有坏。] 你所看的第一本书对你...

晨曦之光
2012/03/09
141
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

【RocketMQ】Message存储笔记

概述 消息中间件存储分为三种,一是保存在内存中,速度快但会因为系统宕机等因素造成消息丢失;二是保存在内存中,同时定时将消息写入DB中,好处是持久化消息,如何读写DB是MQ的瓶颈;三是内...

SaintTinyBoy
15分钟前
0
0
Android应用Context详解及源码解析

Android应用Context详解及源码解析 本文定位:优质文章收集 本文转载 1 背景 今天突然想起之前在上家公司(做TV与BOX盒子)时有好几个人问过我关于Android的Context到底是啥的问题,所以就马...

lichuangnk
46分钟前
0
0
PostgreSQL的昨天今天和明天

PostgreSQL 是一种非常复杂的对象-关系型数据库管理系统(ORDBMS), 也是目前功能最强大,特性最丰富和最复杂的自由软件数据库系统。有些特性甚至连商业数据库都不具备。 这个起源于伯克利(...

闻术苑
51分钟前
0
0
Mysql对自增主键ID进行重新排序

1,删除原有主键: ALTER TABLE `table_name` DROP `id`; 2,添加新主键字段: ALTER TABLE `table_name` ADD `id` MEDIUMINT( 8 ) NOT NULL FIRST; 3,设置新主键: ALTER TABLE `table_nam......

niithub
56分钟前
0
0
福利篇:免费csdn vip账号分享

分享一个发布免费csdn vip账号的网站:啰嗦vip www.lostvip.com , 各种软件开发类的视频教程:慕课网、动脑学院、黑马各大培训机构VIP视频教程,非常不错!

在水一方发盐人
今天
0
0
Nginx+Tomcat搭建高性能负载均衡集群

一、 工具   nginx-1.8.0   apache-tomcat-6.0.33 二、 目标   实现高性能负载均衡的Tomcat集群:    三、 步骤   1、首先下载Nginx,要下载稳定版:      2、然后解压两个Tom...

码代码的小司机
今天
0
0
Centos7编译安装ntp-4.2.8p11

Centos7编译安装ntp-4.2.8p11 背景 因公司做等保评级,在进行安全漏洞检测时发现ntp需要升级到ntp-4.2.7p25以上版本,经过一番搜索,没有该版本及新版本ntp的yum安装包,所以只能编译安装了,...

阿dai
今天
0
0
antd pro 新增模块的步骤

index.js是整个项目的入口文件。 // 1. Initializeconst app = dva({ history: createHistory(),});// 2. Pluginsapp.use(createLoading());// 3. Register global modelapp.model......

灯下草虫鸣_
今天
0
0
Cisco VPN在win10下报Error 56的解决办法

问题描述 Cisco VPN在win10下报Error 56: The Cisco Systems, Inc. VPN Service has not been started 解决方案 方案一:在计算机管理-》服务 查看Cisco Systems, Inc. VPN Service服务是否存...

chenfj_fer
今天
0
0
Weblogic问题解决记录

问题:点击登录,页面刷新但是不进去管理界面。解决:删除cookies再登录。

wffger
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部