使用A*寻路小记
前几天做另一个DEMO 要用实现自动寻路功能,看到普遍都是A* 学习了下
我的主循环代码:
isFindEndPoint = false;
//主循环
do
{
CreateOutSkirtsNode(currpoint);//创建外围点
auto temppoint =SelectNextNode(currpoint);//从外围中选出下一个当前点
currpoint = temppoint;
SetNodeToSelection(currpoint);//将选定的当前点添加入_SelectCollection,并将其从_unSelectionCollection删除
} while (!isFindEndPoint/*如果终点出现在当前点的外围*/);
算法是封装在一个算法类中,使用时传入 几个参数就可以随意调用.
主循环就3件事:
1、创建外围点,即A点周围8个点,使用其坐标创建一个自定义类型MapNodeClass 这个类型存储算用到的一些关键信息。
比如 f g h x y Ispass parent ,H就是简单的用了 xy位移差, 相信看过A*的都懂,我的做法是当需要检测路径时才创建MapNodeClass 。
2、 从外围中选出下一个当前点
很好理解 根据f值 选定,其中牵扯到F值得更新问题,这个方法已经包装在MapNodeClass 中了
3、将选定的当前点添加入_SelectCollection,并将其从_unSelectionCollection删除
_SelectCollection 就是算法中的colseList 表示 不用再检索
_unSelectionCollection 就是openlist 表示待检索
都很好理解
---------------------
看上去差不多了,但是运行起来有问题。因为我的瓦片地图测试中 起点周围是一个胡同,所以会出现 指针为空的报错,一看都是出现在SelectNextNode()中的错误。
即第二个环节中,寻找到的当前点currpoint 为空。其原因就是算法陷入死路之后currpoint 外围并不存在openlist中的点,即找不到可以选择的点。
这种情况我看网上大多数A*介绍都没提到,没有说明死路状况。
其实一想,解决也简单,无非是倒退一步,从currpoint父节点执行一次SelectNextNode().所以要修改SelectNextNode()。
在其检测不到currpoint 外围节点时,直接把检测范围变成openlist,为什么不是父节点外围,主要是考虑到如果死胡同比较深的情况下检测父节点外围所检测的范围太大。
这里面需要注意的是:如果currpoint 存在外围节点时,会更新外围节点F值(主要是更新G值) ,而检测范围扩大时,则不能执行更新F值.
最新文章
- c++适配器
- mysql字符串函数(转载)
- iOS适配https详解
- ASP 发送邮件
- gitlab的搭建和linux客户端的连接
- MyBatis Mapper 文件例子
- POST 一张 图像的调试来认识 http post
- 怎样在自己的网站上做自动生成当前url的二维码
- (四)boost库之正则表达式regex
- poj3206(bfs+最小生成树)
- char *详细指针
- 读Zepto源码之集合操作
- 在windows下使用Qt5开发GTK3图形界面应用程序
- Python爬虫入门教程 37-100 云沃客项目外包网数据爬虫 scrapy
- 图片与Base64的转换
- js-new、object.create、bind的模拟实现【转载备忘】
- python面向对象和面向过程介绍与区别
- go 切片的 插入、删除
- Use of exceptionless, 作全局日志分布式记录处理
- 什么是延展性(Malleability,可鍛性)
热门文章
- nginx 4 win10
- json转换时区问题-------前端展示时间少8小时--解决方法
- jsp内置对象(转)
- Hackerrank manasa-and-combinatorics(数学推导)
- CH上的Think Bear#1模拟赛
- Oracle创建表空间、用户名、密码步骤教程
- Spring实现封装自定义注解@Trimmed清除字符串前后的空格
- C 基础 全局变量
- POJ 3683 Priest John&;#39;s Busiest Day (2-SAT+输出可行解)
- 【树剖求LCA】树剖知识点