当前位置: 首页 > 编程语言 > VC.NET > 正文

C++游戏开发十七 游戏中的寻路算法(三):A*算法原理

时间:2014-11-04

A*算法路径的评价公式为F=G+H

其中H为某个已达格子到目的地的估算距离,估算的方法有很多种,比如:

1、曼哈顿距离:即两点水平距离加上竖直距离。比如(x1,y1)到(x2,y2)的曼哈顿距离就是

|x2-x1|+|y2-y1|。

2、欧式距离:即两点之间的真实距离。(x1,y1)到(x2,y2)的欧式距离就是

sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))。

3、切比雪夫距离:水平方向和竖直方向上的距离最大值。(x1,y1)到(x2,y2)的切比雪夫距离就是 max(|x2-x1|,|y2-y1|)。

下面采用曼哈顿距离来说,因为上一节提到的雾央学习的那篇文章是用这个的,有很多图,说起来方便。

首先准备一个开放列表和一个封闭列表。

开放列表用来保存待检验方格,封闭列表保存已经检验过的方格,即不再需要考虑的方格。

看这张图,绿色为出发点。

首先将绿色方格加入开放列表中,然后考察它周围的八个方格。我们将绿色方格从开放列表中删除掉,加入封闭列表中,因为我们不再需要检验它。同时把八个方格加入到开放列表中,他们将会是下一步考察的对象。

图中每个格子中有三个数字和一把钥匙形状的东东。

钥匙把指向的格子表示该格子的父节点,也即表示经过父节点来到该节点,它的作用是记录下路径。

我们的路径评估函数式F=G+H。

格子中的三个数字左上角的是F,左下角的是G,右下角的是H。

在绿色方格的上下左右四个格子的G值都是10,这是假定一个格子的路径长度是10,而它的四个对角的格子的G值是14,因为是通过对角线斜着到达的,所以是10的根号2倍,取14以方便计算。

看看绿色格子的右边的格子,清楚的标出了F,G,H。其中H=30,因为它离目的地红色格子只有三个格子的距离。注意,在估算距离的时候,是不用考虑障碍物什么的。

这时开放列表中有的格子就是绿色格子周围的那八个方格。

更多精彩内容:http://www.bianceng.cn/Programming/VC_NET/