纳金网

标题: A*算法学习 [打印本页]

作者: 烟雨 时间: 2016-1-18 04:41
标题: A*算法学习

听说寻路算法中A*算法最好.贴上超级完美的A*博客,作为深究用,此博客主要阐述原理与优化,所以看完表示我还是不知道怎么写A*,但学会A*后再看此博客后面几篇相信会很大收益.

刚接触A*我建议看前3篇就行了,等你能自己尝试写一下A*再重新看这个博客.

http://blog.jobbole.com/71044/

这是我好不容易写出来的,因为bug,已疯,所以再写没有规避障碍物,也没有逐步移动,控制栏里输出的是路径的总步数.
关于寻路算法在Script里的Tile,Board,PlayAction.(代码有点恶劣)

Tile:次要 Board:主要 PlayAction:只是调用鼠标点击事件.
http://pan.baidu.com/s/1o6AIzXK

下面是理解A*的主要信息,看完这个再看我的代码

(很重要,Tile中使用)函数: f=g+h g:已走路径的总消耗 h:预计到达目标的总消耗
直接把A*怎么写先放上来. (开启列表:待检测列表关闭列表:已检测列表)

1，把起始格添加到开启列表。

2，重复如下的工作：

a) 寻找开启列表中F值最低的格子。我们称它为当前格。

b) 把它切换到关闭列表。

c) 对相邻的格中的每一个？

* 如果它不可通过或者已经在关闭列表中，略过它。反之如下。

* 如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。

* 如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。

d) 停止，当你

* 把目标格添加进了关闭列表(注解)，这时候路径被找到，或者

* 没有找到目标格，开启列表已经空了。这时候，路径不存在。

3.保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。这就是你的路径。

我的建议是看懂后,完完全全自己写一次,你也可以添加障碍物规避等等完善编程真正的A*算法.

此次学习我最大的收获是...当使用While的时候...测试时丢个if(a>200){break;}和print(a)进去..防死循环导致unity崩溃!

出了一点大bug... 寻找此处代码更改就行了..就是2行代码调转了

int a = 0;

while (openHeap.Count > 0)

{

currentTile = openHeap.pop();

parentTile = currentTile;

if (currentTile.pos == goalTile.pos)

{

while (currentTile != null)

{

作者: 毛毛虫 时间: 2016-1-18 13:58
这是什么？字数限制麽？后面怎么没有了？

欢迎光临纳金网 (http://go.narkii.com/club/)