关于寻路算法的模糊搜索

木头人

寻路算法可以说是游戏中毕不可少的一个算法模块.但传统广度优先寻路算法在地图较大的情况下再怎么优化细节也没办法满足日常需求, 例如: 3000 * 2000 的扩阔地图(极少不可达的地域块), 速度让人无法接受(大于10秒). 只要原因是深度达到300维后, 每次需要遍历(每增加一维需要进行判断是否可行的坐标数量)几十k 甚至至 几百k次的运算.

于是思考了几种模糊搜索.

一、预定路径寻路
预先为地图建设多条固定路径与结点, 在搜索开始时事先用 abs(src - des) 的方式求出最近的结点距离, 再由固定路径结点作为出发点搜索至目标最近的结点, 最后再拼构成完整的路径.
优点和缺点都很明显, 搜索绝对非常快, 额外的工作量也非常多, 万一地图改了些什么的话更加麻烦.

二、缩放地图寻路
将原有地图坐标以一定的比例进行缩小, 例如每2*2个坐标当作成1个坐标进行计算寻路, 判断2*2个坐标中是否均是可达, 则否定为不可达.然后再用搜值将寻路路径拉好,这样的方式可以将速度提高近4倍. 当然, 把级数设计为3*3可以将效率提高得更多, 级数当然可以灵活调节, 寻路时可以从 5级开始寻路, 如果失败即向下逐渐调整更细的级数. 直到不可忍耐的 1*1.
优点: 不用预先设置路径, 可随意调节寻路级数.
缺点: 性能不均衡, 波动幅度较大.

三、网格式定点寻路
这是第二种解决方案引出的加强版,仍然拥有可调节的指数, 以指数作为长度, 每单位长度作为一个结点, 以结点作为基本搜索路径, 判断结点与结点之间是否可达由第二方案决定是否可达的条件改为缩小版的地图, 由第一方案的原始寻路方式决定两结点之间是否可达并计算权值, 借以此减少由广度优先所增加的遍历长度, 而且极大提高寻路成功率. 结点并不是一定从x0 y0开始, 可以是 x2 y3, 寻路前进行一个随机计算结点的偏移量, 借以每次寻路可以将网格定点在不同的位置, 以免其它玩家寻路时都跑在同一个路径上.
优点: 具有方案二的优点, 并且相同的起点到相同的目标点寻路, 每次路径可能都不一样(路径相差不大)
缺点: 还是存在路径不可达, 相对方案二有较大的改善, 性能更加均衡

[ 本帖最后由 木头人 于 2010-2-10 01:22 编辑 ]

freeeyes

支持一下，可以一起讨论一下。寻路算法集结点采用的方式较多。