地图区域遍历算法求助

maper

                 图一


                             图二

       最近在写地图区域遍历，碰到一些困难，像各位大大求助。
       用zmud画好地图后我已经可以得到各个房间的出口信息，比如房间1通往房间2的方向是west。现在想写个地图区域遍历，就是从任意一个房间开始自动遍历一定距离内的所有房间。
       现在对于图一这样的没有相互连通的房间已经可以搞定了，从红色房间开始可以走遍周边所有的房间。思路是进入一个房间后检索这个房间没有走过的方向，从没有走过的方向中选一个再走下去，如果该房间的所有的方向都走过了或者遍历距离到了就返回。
       但是对于图二这种有些房间相互连通的就会出现漏掉某些房间的现象，不知道像这种情况应该采用什么样的算法进行遍历？要求重复经过某个房间的次数不要太多，不能漏掉某些房间。

ddid

顶一下。

等着看答案。

ddid

考虑对回环路径单独建立数据模型，毕竟这里回环路径比较少。

maper

原帖由 ddid 于 2009-8-7 04:45 PM 发表
考虑对回环路径单独建立数据模型，毕竟这里回环路径比较少。

就是把环路改成不是环路的？这样是很容易做到的，但这样在遍历找npc时貌似不大好啊！

whuan

右手原则？比如设定一个顺序east，southeast，south，southwest，west，northwest，north

遇到岔路口就先走east，走到尽头返回，返回后走south，走到尽头再返回
能保证所有的地方都走完，但不一定是最优的

littlexi

这是什么…………………………

ddid

想了半天，没想到什么好办法……

个人感觉，问题的关键是，无法在一进入房间时，就判断出是否处在回环路径中。除非用数据库，但每走一步查询一次数据库，对计算速度影响较大。

duno

广度优先遍历

maper

原帖由 whuan 于 2009-8-7 05:59 PM 发表
右手原则？比如设定一个顺序east，southeast，south，southwest，west，northwest，north

遇到岔路口就先走east，走到尽头返回，返回后走south，走到尽头再返回
能保证所有的地方都走完，但不一定是最优的

比划了一下这个貌似可以，不过右手是相对于进入该房间的方向而言的，比如进入房间是east，那下一个应该走southwest，再是south

maper

原帖由 duno 于 2009-8-7 07:06 PM 发表
广度优先遍历

对这个不熟悉，不过我看了这个演示动画，似乎不大适用于地图遍历吧？http://218.65.59.6/xinwen3/news/kj/flash/2004/0426/1300.htm