北大侠客行MUD论坛

 找回密码
 注册
搜索
热搜: 新手 wiki 升级
楼主: maper

地图区域遍历算法求助

[复制链接]
发表于 2009-8-7 22:53:04 | 显示全部楼层
为啥不适用,具体原因?
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2009-8-7 23:13:13 | 显示全部楼层
我也没学好图,感觉上,那个动画很直观,对于无向图,广度优先,使遍历时经过的很多定点。对于咱们来说,同一个房间跑很多次
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2009-8-7 23:19:25 | 显示全部楼层
广度优先遍历:
1)先确定遍历范围
2)再基于范围寻找遍历路径
目标是希望遍历路径尽量短,在明确遍历范围前,是无法知道先走哪个方向后走哪个方向会比较短
广度优先遍历是用于确认遍历范围的,并不直接生成遍历顺序
有了范围后,简陋一点的,可以每走一步浏览整个范围,查找尚未被遍历的最近的房间,也是通过广度优先来查找最近的房间

深度优先遍历:
就如上面所说的按一定方向顺序走(如总是先east,然后顺时针,先up然后down),这样可以直接得出遍历路径,无需先确定遍历范围
但因为遍历过程中,并不预先确知当前的方向选择顺序是否合适,所以有时候比较没谱

小范围4、5步以内的,因为基数小,差别不大,深度优先遍历更简单直接
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2009-8-7 23:20:57 | 显示全部楼层
重复路过问题,需要另加辅助项
如一个 PassedRoom列表,或直接在房间上打标记
基本算法只是组成部分,存在意义就是让大家拼装的
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2009-8-7 23:26:07 | 显示全部楼层
因为实际上,我们是制定一个地图作为范围的,如果npc和房间位置无关系,那么深度优先比较好,一条道跑完了,然后跑别的。
如果npc在一定的房间范围,广度优先效率高。
因为这2个都有成熟的程序可以借鉴,比自己定义规则实现起来更方便。
都做一下,同时记录跑过的数量,也能对比出哪个好。(duno作压力测试恐怕比较难)
还有个问题就是地图的外联出口房间,怎么忽略那个外联路径。
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2009-8-8 03:57:22 | 显示全部楼层
一眼看出来了,岳王墓和苏州

广度深度的啥,7,8年前读书的时候学到过,汗一下,忘的差不多了
你们继续
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
 楼主| 发表于 2009-8-8 08:37:00 | 显示全部楼层
原帖由 duno 于 2009-8-7 11:19 PM 发表
广度优先遍历是用于确认遍历范围的,并不直接生成遍历 ...

明白了,谢谢!
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
 楼主| 发表于 2010-2-28 11:19:12 | 显示全部楼层
回头看看也蛮有意思的!想当年可是琢磨了好几天啊!
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2010-2-28 11:46:26 | 显示全部楼层
原帖由 maper 于 2010-2-28 11:19 AM 发表
回头看看也蛮有意思的!想当年可是琢磨了好几天啊!

现有轮到我头疼呀头疼..头疼个100000遍了
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2010-2-28 11:50:38 | 显示全部楼层
这个很好解决的。我对环状路径就是记日志,不计日志没法弄,不过我觉得遍历还是用深度优先原则比较好。每走一步四周看看实在比较麻烦。对于大范围区域搜索还是要预先制定路线,路线计算好了很快的。
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|北大侠客行MUD ( 京ICP备16065414号-1 )

GMT+8, 2024-11-11 02:24 PM , Processed in 0.010792 second(s), 13 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表