箴理

一个追求技术和内涵的求学者

  • 主页
  • 所有文章
所有文章 友链 关于我

箴理

一个追求技术和内涵的求学者

  • 主页
  • 所有文章

A*算法游戏中需要考虑的几点

2017-04-22

在实际游戏开发过程中采用A*算法,考虑清楚以下几点并采取适当的策略,那么必然可以得到一种高效美观合适的优化算法。

  • 空间的划分:
    矩形栅格;四叉树;凸多边形;可见点;广义圆柱体

  • 相邻状态:
    取决于地图表示和量化方式。比如在正方形栅格中,量化方式是只选择相邻位置-取周围8个还是4个,还有量化方式是取周围一定量的点(跟定义的规则有关),还要考虑地形(障碍物或者陆军不能过海)

  • 代价:
    可以是距离,时间,花费点数等。这里还要考虑地形(穿越某种地形对应不同的代价)或者审美(看起来更直,更平滑。比如正方形栅格走对角比直线运动代价高)。甚至具有不对称性,从a-b代价比从b-a代价高(上坡等)

  • 估价:
    到目标点的估价不要太高估(会导致找不到路径),但也不要太低(比如取两点间欧式距离,会导致效率降低,虽然一定可以找到最短路径)。所以估价函数的建立既要考虑最终结果不能太高估,又要考虑速度适当放大,甚至冒着取一条“次优路径”的风险进行高估。

  • 目标:
    可能是多个目标点(比如一个角色在远处有多个攻击目标),所以需要首先获得这些目标,然后对一个新节点计算到每一个目标的cost,取最小的作为costToGoal。

另外,A算法一定不要用在判断两点是否有路径。因为假如无路径,会使一个大型地图几乎所有的点被搜索,效率最低。此时最好使用地图预分析,比如当两个点在两个隔离的岛上,则直接不调用A*。

赏

谢谢你请我吃糖果

支付宝
微信
  • 游戏编程

扫一扫,分享到微信

微信分享二维码
Cocos2d-x基础知识
人民网解析池简单分析
© 2017 箴理
Hexo Theme Yilia by Litten
  • 所有文章
  • 友链
  • 关于我

tag:

  • 游戏编程
  • 设计模式
  • python 爬虫
  • cocos2d

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录(注意不是yilia根目录)执行以下命令:
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置:

      jsonContent:
        meta: false
        pages: false
        posts:
          title: true
          date: true
          path: true
          text: false
          raw: false
          content: false
          slug: false
          updated: false
          comments: false
          link: false
          permalink: false
          excerpt: false
          categories: false
          tags: true
    

  • 军
  • 友情链接2
  • 友情链接3
  • 友情链接4
  • 友情链接5
  • 友情链接6
LZ