论坛 › 技术园地 › 地图区域遍历算法求助

duno 发表于 2009-8-7 22:53:04

为啥不适用，具体原因？

chengsan 发表于 2009-8-7 23:13:13

我也没学好图，感觉上，那个动画很直观，对于无向图，广度优先，使遍历时经过的很多定点。对于咱们来说，同一个房间跑很多次

duno 发表于 2009-8-7 23:19:25

广度优先遍历：
1）先确定遍历范围
2）再基于范围寻找遍历路径
目标是希望遍历路径尽量短，在明确遍历范围前，是无法知道先走哪个方向后走哪个方向会比较短
广度优先遍历是用于确认遍历范围的，并不直接生成遍历顺序
有了范围后，简陋一点的，可以每走一步浏览整个范围，查找尚未被遍历的最近的房间，也是通过广度优先来查找最近的房间

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

小范围4、5步以内的，因为基数小，差别不大，深度优先遍历更简单直接

duno 发表于 2009-8-7 23:20:57

重复路过问题，需要另加辅助项
如一个 PassedRoom列表，或直接在房间上打标记
基本算法只是组成部分，存在意义就是让大家拼装的
囧

chengsan 发表于 2009-8-7 23:26:07

因为实际上，我们是制定一个地图作为范围的，如果npc和房间位置无关系，那么深度优先比较好，一条道跑完了，然后跑别的。
如果npc在一定的房间范围，广度优先效率高。
因为这2个都有成熟的程序可以借鉴，比自己定义规则实现起来更方便。
都做一下，同时记录跑过的数量，也能对比出哪个好。（duno作压力测试恐怕比较难）
还有个问题就是地图的外联出口房间，怎么忽略那个外联路径。

sghjjj 发表于 2009-8-8 03:57:22

一眼看出来了,岳王墓和苏州

广度深度的啥,7,8年前读书的时候学到过,汗一下,忘的差不多了
你们继续

maper 发表于 2009-8-8 08:37:00

原帖由 duno 于 2009-8-7 11:19 PM 发表 http://www.pkuxkx.com/forum/images/common/back.gif
广度优先遍历是用于确认遍历范围的，并不直接生成遍历 ...
明白了，谢谢！ttk_04

maper 发表于 2010-2-28 11:19:12

回头看看也蛮有意思的！想当年可是琢磨了好几天啊！ttk_09

lzkd 发表于 2010-2-28 11:46:26

原帖由 maper 于 2010-2-28 11:19 AM 发表 http://www.pkuxkx.com/forum/images/common/back.gif
回头看看也蛮有意思的！想当年可是琢磨了好几天啊！ttk_09
现有轮到我头疼呀头疼..头疼个100000遍了

seagate 发表于 2010-2-28 11:50:38

这个很好解决的。我对环状路径就是记日志，不计日志没法弄，不过我觉得遍历还是用深度优先原则比较好。每走一步四周看看实在比较麻烦。对于大范围区域搜索还是要预先制定路线，路线计算好了很快的。

查看完整版本: 地图区域遍历算法求助