z***e
发帖数: 5393 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: zlike (最终幻想), 信区: Programming
标 题: 求问：游戏中比较自然的路径寻找算法有啥简单方案？
发信站: BBS 未名空间站 (Sun Jul 14 02:00:54 2013, 美东)
做塔防游戏，但是因为设计的道路比较宽，又是多路径，相当于说是地图全开的RTS游
戏，寻路算法没找到个合适的方案，求指点。
嗯嗯，A* path finding这个我知道。
问题是，那是最短path，我不想一堆兵走两步最后就全部到一条线（shortest path）
上去了啊，看起来太假了。
在A*上修改，比如变向就增加权重什么的，貌似也没啥明显效果。实际上比较能接受的
效果是每一步的cost是一个范围内的随机数，然后士兵基本就不会都跑到一条线上去，
而是一边走一边左晃右晃。。。看起来还是不爽。。。
理想状况是比如一排兵出来，除非是遇到障碍物才变向，不然就是一直沿着初始方向往
前走，假设道路宽度始终不变。
解决方法目前想了两种，一种是设置路标waypoint，把路标设在转弯处，然后每次找下
一个路标，但是这个如果道路复杂了，设置起来很麻烦，因为坐标点要数，数起来麻烦
死了。
另一种是在地图上把行走道路固定死，反正就是几种路线，全部固定下来，士兵随机选
一条路线走就是了，这个思路简单，但是路线多了也麻烦。
any idea? thx. |
p*****2
发帖数: 21240 | |
g*******s
发帖数: 2963 | 3 塔防和即时战略类游戏大部分用到A*， 而且是每次update（比如你新造了一个物体堵住
了原来的最优路径）都要重新计算一遍A*。
给一个比喻，你要从湾区开车到纽约。有两个问题要解决，第一是选一条路线，第二是
开车的时候要避开其他车辆，换道等等。A*只是解决了第一个global问题（类似google
map），第二个local问题一般可以用多种steering behavior的算法解决。最简单快速
的是Craig Reynolds提出的Boid算法。其他算法大多是其变种。总之最后的velocity是
各级force的weighted combination。从整个系统来看，其实A*的计算量不大，不断
query nearest neighbors才是performance bottleneck，可以用kd-tree或者grid优化。 |
w**********o
发帖数: 140 | |
z***e
发帖数: 5393 | 5 问题在于。。。我不要最优路径。。。我要兵按直线走，没碰到底就不转弯，如果是一
条路的塔防那根本不必用A*，因为不用寻路，但是如果是多路的塔防，如果不在地图上
做路标，就得A*，而A*始终是找shortest path...
堵住
google
化。
【在 g*******s 的大作中提到】
: 塔防和即时战略类游戏大部分用到A*， 而且是每次update（比如你新造了一个物体堵住
: 了原来的最优路径）都要重新计算一遍A*。
: 给一个比喻，你要从湾区开车到纽约。有两个问题要解决，第一是选一条路线，第二是
: 开车的时候要避开其他车辆，换道等等。A*只是解决了第一个global问题（类似google
: map），第二个local问题一般可以用多种steering behavior的算法解决。最简单快速
: 的是Craig Reynolds提出的Boid算法。其他算法大多是其变种。总之最后的velocity是
: 各级force的weighted combination。从整个系统来看，其实A*的计算量不大，不断
: query nearest neighbors才是performance bottleneck，可以用kd-tree或者grid优化。
|
n******n
发帖数: 567 | 6 dijkstra, 需要内存比较大，precalculate存在db里 |
