3d Game Walkman

3d图形渲染,网络引擎 — tonykee's Blog
随笔 - 45, 文章 - 0, 评论 - 309, 引用 - 0
数据加载中……

最近把地形障碍编辑做出来了,A*算法自己也写了一遍

障碍图的矩阵编辑搞定了,编辑起来非常方便,发个图鉴赏鉴赏。


下午写了A*算法的实现,原以为很复杂,其实也还算有点复杂
不过基本上很顺利,一下午就封装出来了
只是其效率还很不满意,特别是要不停的创建释放内存Open列表和Close列表操作太频繁

我选择了MuiltSet编制了评估路径损耗的排序规则,set的内部树结构,用来做这些恰到好处。
但就是对不停的创建和释放对象这方面感觉很不满意,或许考虑用Memory pool来解决这个问题

下面是A*算法的实现,也发出来如果你需要的话,可以拿来用用,尽管网上的例子已经有很多实现了
每个人都有自己的风格,这么经典的算法不自己写一遍似乎说不过去,再说将来还要改进和扩展呢

明天把写好的算法加入到地形编辑器中去,角色就能自己去找路径移动了。


0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 9 9 9 9 9 9 0 0 0 0 0 0
0 0 0 0 9 1 1 1 1 0 9 0 0 0 0 0
0 0 0 0 9 1 0 0 0 1 0 9 9 0 0 0
0 0 0 0 9 1 0 0 0 0 1 1 9 0 0 0
0 0 0 0 9 1 0 0 0 0 0 1 9 0 0 0
0 0 0 9 0 1 0 0 0 0 0 1 9 0 0 0
0 0 9 0 1 0 0 0 0 0 0 1 9 0 0 0
0 9 0 1 0 0 9 9 0 0 1 0 9 0 0 0
0 9 1 0 0 0 9 1 1 0 1 9 0 0 0 0
0 9 1 0 0 0 9 9 0 1 1 9 0 0 0 0
0 9 1 0 0 0 0 0 9 0 1 9 0 0 0 0
9 0 1 0 0 0 0 0 0 9 9 9 0 0 0 0

 AStar astar;
 vector<PathPoint> path;
 //astar.FindPath(buf8x8, 8, 8, PathPoint(7, 0), PathPoint(7, 7), path, true);
 astar.FindPath(buf16x16, 16, 16, PathPoint(15, 0), PathPoint(11, 7), path, true);
 for(DWORD i = 0; i < path.size(); i ++)
 {
  printf("%d %d \r\n", path[i].i, path[i].j);
 }


算法实现源码



posted on 2008-07-10 18:37 李侃 阅读(3839) 评论(13)  编辑 收藏 引用 所属分类: 室外场景编辑器

评论

# re: 最近把地形障碍编辑做出来了,A*算法自己也写了一遍  回复  更多评论   

我师弟在高二那年也做了一个大型的LOD地图
参考www.graphixer.com.cn
2008-07-10 19:05 | 陈梓瀚(vczh)

# re: 最近把地形障碍编辑做出来了,A*算法自己也写了一遍[未登录]  回复  更多评论   

A*可以考虑用二叉堆来优化。
2008-07-11 23:16 | christanxw

# re: 最近把地形障碍编辑做出来了,A*算法自己也写了一遍  回复  更多评论   

楼主算法有错误,没有G优化,这个只是启发式广度有限,不是真正的A*
2008-07-13 20:16 | w2001

# re: 最近把地形障碍编辑做出来了,A*算法自己也写了一遍  回复  更多评论   

是啊,H做了判定,G没有考虑,需要改进一下评估函数
2008-07-13 20:44 | 李侃

# re: 最近把地形障碍编辑做出来了,A*算法自己也写了一遍  回复  更多评论   

初识A*算法

f(n) = g(n) + h(n)

  其中f(n)是节点n的估价函数,g(n)实在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息,因为g(n)是已知的。如果说详细点,g(n)代表了搜索的广度的优先趋势。但是当h(n)>>g(n)时,可以省略g(n),而提高效率。

主要是看了这段介绍

2008-07-13 20:57 | 李侃

# re: 最近把地形障碍编辑做出来了,A*算法自己也写了一遍  回复  更多评论   

上面的介绍也是一知半解的人写的。加Openlist的时候还要判别能否优化已有位点的G,你源码中也无,再仔细看看。
2008-07-14 13:39 | w2001

# re: 最近把地形障碍编辑做出来了,A*算法自己也写了一遍  回复  更多评论   

不管咋样,对我还有有点用,谢了
2008-07-16 03:08 | 放屁阿狗

# re: 最近把地形障碍编辑做出来了,A*算法自己也写了一遍  回复  更多评论   

你好,你的MSN和QQ是多少啊。想问问你地形混合的一些技术
2008-07-21 10:34 | 一般

# re: 最近把地形障碍编辑做出来了,A*算法自己也写了一遍  回复  更多评论   

感觉网格索引有些诡异。。。
是为了特殊的要求么?
2008-07-21 16:15 | 月隐

# re: 最近把地形障碍编辑做出来了,A*算法自己也写了一遍  回复  更多评论   

原先看了游戏精粹2介绍的就是这样的索引形势,没什么诡异的啊?
2008-07-21 19:06 | 李侃

# re: 最近把地形障碍编辑做出来了,A*算法自己也写了一遍  回复  更多评论   

侃哥挺牛的啊,我是阿华哦。嘿嘿。
2008-08-03 01:01 | v.la

# re: 最近把地形障碍编辑做出来了,A*算法自己也写了一遍  回复  更多评论   

398514515 你好 加下 请教你一些问题 关于地形障碍你是怎么想的
2010-03-21 22:30 | black0592

# re: 最近把地形障碍编辑做出来了,A*算法自己也写了一遍  回复  更多评论   

你这个好像是2d吧 我想请教你一些3d的地形障碍
2010-03-21 22:32 | black0592

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理