A*寻路算法与它的速度 - 设计与修改 - 轩辕春秋文化论坛 20周年


	《苍狼白鹿传》

组别	士兵
级别	牙门将军
功绩	6
帖子	571
编号	321756
注册	2009-5-10

#1

发表于 2010-8-5 17:13 资料短消息看全部作者

假设从（0,0）到（40,40）有1600个单位，假设每单位有三个值 0 可移动 1不可移动 2已经移动过
首先可移动只有两个方向（算正方向，斜向算两步）
然后对四个方向编号，1上 2左 3下 4右，运动路径就被一串数字记录
当前坐标 2字节
先计算横纵坐标差值之和，就是走三角形两条直角边的距离
然后以这个距离作为最小值
横轴优先纵轴其次，先测试能否直接通过直角边到达

遇到障碍然后转变方向，只有两个选择向上向下
向上的话距离在增加，所以优先的还是向下，上一个单位优先测试向右（注意最开始不可能回头的）

比方达到（25,0）的时候，（26,0）是障碍
那么就尝试往（25,1）走遇到障碍尽量往目的地最近的点靠近

像这样的走直线在RPG中比较常见，然后遇到障碍物停住的现象也有

[ 本帖最后由《苍狼白鹿传》于 2010-8-5 17:19 编辑 ]

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	《苍狼白鹿传》

组别	士兵
级别	牙门将军
功绩	6
帖子	571
编号	321756
注册	2009-5-10

#2

发表于 2010-8-5 17:24 资料短消息看全部作者

当然被障碍物卡住只能说明AI太弱智

一般最优先的假设就是没有障碍

每一步都检测最靠近的走法

O  A
A  X 就想这样从（0，0）到（40，40）只有这两个方向是接近的，所以优先考虑着两个方向
O是假设弟N步所在 A是N+1步的CASE

内存存储空间比较多
第一步就有两个CASE 所以到障碍物之前就有2的N次方作为存储空间
但是 3 4 和 4 3是同样的结果，先下后右先右后下
所以每一步方向记录的数字会对比，那么34443和33444是一样的最后只统计每个数字的个数

如果到了死角
O A B
A B X
B X X B是障碍 A是预计的下一步，那么经过两个case以后返回结果是进入死角
这时候开始返回
返回也是先横坐标再纵坐标

不论向左还是向上都可以算远离了目标
所以在这种情况下马上继续按照最近原则找

考虑不回头原则

那么路径有可能是

A----
   | X
   |  X
C-BX
| X
D

A-D

这样的测试是优先横坐标

比方从 0 0 到 5 5
有一排障碍
AOOOX
OOOXO
OOXOO
OXOOO
OOOOB
优先走到 3 0（准确的说还只是测试，不是真的走）
两个方向不能走，不能回头
然后在 2 0 拐弯
因为从 2 0 到 2 1 和到3 0 效果一样
但是优先横坐标

到了2 1 又被卡死然后左走（最后1234四个方向相加减得出最近的结果）

这时候到了 1 1 ，优先考虑往最近方向向下到了1 2 于是根据这个原则，一直走到0 4然后又回到最初原则，横坐标
这样的话实际路程是11 而最近是8
这时候尝试缩减路程

最明显的是 A B
            D C这样的路径直接变成 A
                                             B
但是像
O O O
X X O
O O O
的路径可能难以发现
这时候就尝试变换横纵坐标走法
比方3 4 变成4 3

于是可以变成
O O X
X O O
O O O
这就缩短为

O O X
X O X
O O X
利用循环从开始到最后变换以后测试（前提是不撞上障碍）

实际上也有些路径计算就想这样的，比方贴着墙走，然后走到了门口进去

[ 本帖最后由《苍狼白鹿传》于 2010-8-5 17:44 编辑 ]

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	《苍狼白鹿传》

组别	士兵
级别	牙门将军
功绩	6
帖子	571
编号	321756
注册	2009-5-10

#3

发表于 2010-8-5 17:53 资料短消息看全部作者

图挂了？不知道怎么回事都没看到

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！