» 您尚未登录:请 登录 | 注册 | 标签 | 帮助 | 小黑屋 |


发新话题
打印

[新闻] 最近Square Enix代理的PC游戏挺不错啊

SC2用的找路算法相当的牛逼,用到的思想是把找路算法流体化(思想使用continuum dynamics),而不是直接使用游戏中的几何数据矩阵化之后做线性搜索(Dijkstra算法),Dijkstra算法的缺点就是如果障碍物是移动,那么会效率低下

SC2用到的找路算法的网页在这里
http://grail.cs.washington.edu/projects/crowd-flows/
是华盛顿大学,NSF,微软研究院,索尼,EA的联合研究项目

思想是把每个个体看成是流体中的点,每一点有一个类似“势能”的量,准确的说是相对于移动障碍物距离的势(potential,一个描述物体运动的驱动力大小的物理量),然后沿着势能梯度减小的方向自动流动(虽然还是要使用几何顶点,但是避开了线性搜索);和最优化路径里面的时间正方向解Hamilton-Jacobi-Bellman方程(好鸡吧方程),反方向解Fokker-普朗克方程的思想类似,就是要最小化相对势能(看你怎么定义势能,或者说效用函数)

是个好公司,可惜大家都是暴雪饭


TOP

发新话题
     
官方公众号及微博