勤能补拙,Expter

成都游戏Coder,记录游戏开发过程的笔记和心得!

3D游戏寻路算法(A*)

        关于游戏寻路,网络上也有很多相关的文章,一般都是已A*为主,他只是一种启发式搜索,最开始写A*是在大三,主要还是做一个路径搜索的算法。 

        关于游戏中A*的算法优化,由于在搜索的过程中会通过open表和close保存一些结点,为了加快查找效率一般采用对维护的方式,利用map的最小堆(按照估价值的大小排序)来构架数据结构。其实还可以利用线性的hash_map来创建维护。
       
         而3D中游戏寻路也是采用同样的方法,只是在不同于2D的8个方向搜索而是3*8个方向的搜索。所以他的复杂度之高,在对于一个3维的N*N*N的空间,他的搜索运算为n^3*24,就需要考虑算法中的优化。

        总之一句3D寻路费时又费空间!
       下面是我总结的优化       
       1.总体还是利用a*和堆维护。
       2.由于点是实心,可以直接进行对角线的行走,也就是对角线行走一步后x,y,z的坐标都会改变,从而降低通过2次二维变换的过程。二步变一步!
       3.利用凸包的方式来优化。

       4.把一个场景的3D地图全部细分,利用多叉树进行管理。

       关于凸包的优化可以通过这样一个例子说明(因为在2D中更好的描述通过2维的地图):
       A、假设1要到2的,通过A*的搜索,他会先到0然后发现不能通过在回溯,重新寻找新的路径,这样可能浪费一些搜索时间。
                
       B.   可以通过多边形的最小矩形凸包的方式,这样就可以减少不必要的搜索,如图所示。
                  
                     那么1到2就不会经过0点。。因为次区域设置为不可通过。

       C.   如果我们要查找的点在我们凸包内,所以我们在寻路最开始应该验证点是否在凸包内,如果在此区域内,在行走时不能过滤这个矩形空间。


      注:游戏中地图一般是不变的,所以这些都是不变,凸包已知,验证点在凸包中也是线性的。
     
     
      由于在计算3D的凸包的时候计算量大,最开始采用静态的方式来记录数据。

      简单的3D寻路算法源码(不包含凸包优化):

         /Files/expter/3DAStar.rar

posted on 2009-10-10 22:50 expter 阅读(7063) 评论(1)  编辑 收藏 引用 所属分类: 算法与数据结构Ai

评论

# re: 3D游戏寻路算法(A*) 2009-10-12 11:04 请输入你的姓名

强  回复  更多评论   


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