文档章节

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

放个屁
 放个屁
发布于 2015/06/07 21:29
字数 2212
阅读 140
收藏 6
点赞 0
评论 0

路径

Path Scoring

算出的路径时,确定要使用的方格的关下面的公式

The key to determining which squares to use when figuring out the path is the following equation:

 

F = G + H

 

where

 

G =从起点A沿着生成的路径到一个定的方形网格上运行成本

G = the movement cost to move from the starting point A to a given square on the grid, following the path generated to get there.

 

H =格子中方块到最目的地,B的运行成本通常称式,可有点混乱。因是一个猜所以这样称呼找到路径之前,真的不知道实际的距离,因各种各的事情都在途中,水等)。在本教程中给出一个H的方法,但在网计算H方法其他文章

H = the estimated movement cost to move from that given square on the grid to the final destination, point B. This is often referred to as the heuristic, which can be a bit confusing. The reason why it is called that is because it is a guess. We really don't know the actual distance until we find the path, because all sorts of things can be in the way (walls, water, etc.). You are given one way to calculate H in this tutorial, but there are many others that you can find in other articles on the web.

 

反复遍开启列表,选择具有最小F的方块来生成的路径。在本文中程将一步更详细描述。首先来仔看看如何算公式。

Our path is generated by repeatedly going through our open list and choosing the square with the lowest F score. This process will be described in more detail a bit further in the article. First let's look more closely at how we calculate the equation.

 

如上所述,G从起始点移定点所生成路径的成本。在个例子中,我将指每个移水平或垂直方成本10线成本14们使用这些数字为斜角移动2的平方根(不要害怕),水平或垂直的大1.414倍。我使用1014简单。比例大致是正确的,又能避免算平方根和小数。这不只是因为我们是愚笨的,不喜欢数学。采用些数字是让计算机更快,太快了。你很快就会发现,如果你不使用些捷径路径搜索能会很慢的。

As described above, G is the movement cost to move from the starting point to the given square using the path generated to get there. In this example, we will assign a cost of 10 to each horizontal or vertical square moved, and a cost of 14 for a diagonal move. We use these numbers because the actual distance to move diagonally is the square root of 2 (don't be scared), or roughly 1.414 times the cost of moving horizontally or vertically. We use 10 and 14 for simplicity's sake. The ratio is about right, and we avoid having to calculate square roots and we avoid decimals. This isn't just because we are dumb and don't like math. Using whole numbers like these is a lot faster for the computer, too. As you will soon find out, pathfinding can be very slow if you don't use short cuts like these.

 

由于我们计G值是沿特定的路径定的平方,该办找出那个方的父G,然后加1014取决于它从父方正交(非线还是线需要种方法将在本施例一步上得明一点,因得到一个以上的方

Since we are calculating the G cost along a specific path to a given square, the way to figure out the G cost of that square is to take the G cost of its parent, and then add 10 or 14 depending on whether it is diagonal or orthogonal (non-diagonal) from that parent square. The need for this method will become apparent a little further on in this example, as we get more than one square away from the starting square.

 

H各种方式。我里使用的方法被称曼哈方法,在计算从当前方块到目标方水平和垂直方向移动方块的总数忽略角运,忽略可能在程中的任何障碍。然后,我数乘以10,我的成本水平或垂直移一格。是(可能)被称曼哈方法,因它像算城市街区的数量从一个地方到另一个地方,在那里你不能穿过块对角。

H can be estimated in a variety of ways. The method we use here is called the Manhattan method, where you calculate the total number of squares moved horizontally and vertically to reach the target square from the current square, ignoring diagonal movement, and ignoring any obstacles that may be in the way. We then multiply the total by 10, our cost for moving one square horizontally or vertically. This is (probably) called the Manhattan method because it is like calculating the number of city blocks from one place to another, where you can't cut across the block diagonally.

 

阅读明,您可能已猜到了启仅仅是当前方与目的剩余距离的一个乌鸦飞似的”粗略的估。不是种情况。我们实际试图沿路径的剩余距离(通常是更)。越接近我的估实际剩余距离,快的算法。如果我高估了个距离,但是,它不能保证给的最短路径。在这样的情况下,我有所的“不可接受启式”。

Reading this description, you might guess that the heuristic is merely a rough estimate of the remaining distance between the current square and the target "as the crow flies." This isn't the case. We are actually trying to estimate the remaining distance along the path (which is usually farther). The closer our estimate is to the actual remaining distance, the faster the algorithm will be. If we overestimate this distance, however, it is not guaranteed to give us the shortest path. In such cases, we have what is called an "inadmissible heuristic."

 

从技,在个例子中,曼哈方法是不可接受的,因它稍稍高估了剩下的距离。但是我会用也无妨,因它是一个更容易理解我的目的,因它只是一个微的高估。在极少的情况下,得到的路径不是最短的,这将是近短。想了解更多?你你可以在http://www.policyalmanac.org/games/heuristics.htm找到方程和附加明启式。

Technically, in this example, the Manhattan method is inadmissible because it slightly overestimates the remaining distance. But we will use it anyway because it is a lot easier to understand for our purposes, and because it is only a slight overestimation. On the rare occasion when the resulting path is not the shortest possible, it will be nearly as short. Want to know more? You can find equations and additional notes on heuristics here.

 

FGH中的和。搜索的第一个步果可以下面的明中看出。在FGH的分数被写入在每个方格。正如在紧挨着开始方块右侧上,F被打印在左上角,G印在左下方,而H示在右下方。

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.

 

[3]

[Figure 3]

 

所以,来看看其中的一些方。在字母上,G = 10是因它是在一个水平方向的距离起始方块仅。正方形紧邻上方,下方,及在起始的左10相同的G线14G

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.

 

H是通计到红色目的曼哈距离,水平和垂直方向,而忽略上那就是在算方式。使用种方法,方上开始的直接右3格是红格30。那么高于个方的方块的H4格距离(住,只能水平移和垂直)的一个H40.你也可以看到其他方块计H值的方法

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.

 

每个方格的F,再次,只是通GH一起算。

The F score for each square, again, is simply calculated by adding G and H together.

(待续)

© 著作权归作者所有

共有 人打赏支持
放个屁
粉丝 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

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

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

壶漏子 ⋅ 2015/06/10 ⋅ 0

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

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

开元中国2015 ⋅ 2015/05/26 ⋅ 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

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

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

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

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

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

壶漏子 ⋅ 2015/06/09 ⋅ 0

JNI 开发指南

Android JNI编程提高篇之二 Android JNI编程提高篇之一 Android JNI开发入门之二 Android JNI开发入门之一

zungyiu ⋅ 2011/12/18 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

table eg

user_id user_name full_name 1 zhangsan 张三 2 lisi 李四 `` ™ [========] 2018-06-18 09:42:06 星期一½ gdsgagagagdsgasgagadsgdasgagsa...

qwfys ⋅ 29分钟前 ⋅ 0

一个有趣的Java问题

先来看看源码: public class TestDemo { public static void main(String[] args) { Integer a = 10; Integer b = 20; swap(a, b); System.out......

linxyz ⋅ 33分钟前 ⋅ 0

十五周二次课

十五周二次课 17.1mysql主从介绍 17.2准备工作 17.3配置主 17.4配置从 17.5测试主从同步 17.1mysql主从介绍 MySQL主从介绍 MySQL主从又叫做Replication、AB复制。简单讲就是A和B两台机器做主...

河图再现 ⋅ 今天 ⋅ 0

docker安装snmp rrdtool环境

以Ubuntu16:04作为基础版本 docker pull ubuntu:16.04 启动一个容器 docker run -d -i -t --name flow_mete ubuntu:16.04 bash 进入容器 docker exec -it flow_mete bash cd ~ 安装基本软件 ......

messud4312 ⋅ 今天 ⋅ 0

OSChina 周一乱弹 —— 快别开心了,你还没有女友呢。

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子 :分享吴彤的单曲《好春光》 《好春光》- 吴彤 手机党少年们想听歌,请使劲儿戳(这里) @clouddyy :小萝莉街上乱跑,误把我认错成...

小小编辑 ⋅ 今天 ⋅ 8

Java 开发者不容错过的 12 种高效工具

Java 开发者常常都会想办法如何更快地编写 Java 代码,让编程变得更加轻松。目前,市面上涌现出越来越多的高效编程工具。所以,以下总结了一系列工具列表,其中包含了大多数开发人员已经使用...

jason_kiss ⋅ 昨天 ⋅ 0

Linux下php访问远程ms sqlserver

1、安装freetds(略,安装在/opt/local/freetds 下) 2、cd /path/to/php-5.6.36/ 进入PHP源码目录 3、cd ext/mssql进入MSSQL模块源码目录 4、/opt/php/bin/phpize生成编译配置文件 5、 . ./...

wangxuwei ⋅ 昨天 ⋅ 0

如何成为技术专家

文章来源于 -- 时间的朋友 拥有良好的心态。首先要有空杯心态,用欣赏的眼光发现并学习别人的长处,包括但不限于工具的使用,工作方法,解决问题以及规划未来的能力等。向别人学习的同时要注...

长安一梦 ⋅ 昨天 ⋅ 0

Linux vmstat命令实战详解

vmstat命令是最常见的Linux/Unix监控工具,可以展现给定时间间隔的服务器的状态值,包括服务器的CPU使用率,内存使用,虚拟内存交换情况,IO读写情况。这个命令是我查看Linux/Unix最喜爱的命令...

刘祖鹏 ⋅ 昨天 ⋅ 0

MySQL

查看表相关命令 - 查看表结构    desc 表名- 查看生成表的SQL    show create table 表名- 查看索引    show index from  表名 使用索引和不使用索引 由于索引是专门用于加...

stars永恒 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部