请教一下地图的遍历问题

ltblue

想学mush，但只有思路，甚至有算法，就是不会代码......
曾经自己随便写过随机迷宫及其破解走法，但那是别的游戏，跟mud没关系


看了一些帖子，貌似寻找地图最短径路的问题，如果所有房间同时计算，好像速度跟不上，尤其过江过河的，几千个节点算进去......
看了1个算法，是计算支路的，这个感觉挺难的，没太看懂，大体意思明白，就是一个支路的预先算好路径，其他支路的都直接进支路口。
不过我觉得可行的还是区域算法吧，就是每个地区一个中心点，先到中心点，然后再计算中心点之间的距离（城市级的算法），然后再算到达区域的具体位置。
这种算法就跟zmud的寻路其实是一样的了，我觉得基本体现不出什么优势来


另外，有时候会出现，知道某npc在某个区域里，但完全不知道具体位置，需要遍历整个区域。
zmud的办法是每个区域写一个遍历路径，沿着路径遍历。
想知道mush目前大家是怎么做的？


ps：lua真心看不下去，所以代码完全不会写，唉

北大侠客行MUD，中国最好的MUD

bbz

顶一下，我也在琢磨遍历，现在正在学习A*算法，打算以这个算法为基础来做遍历

ltblue

其实寻路最简单的算法本来是递归，不过太吃系统
不过所有递归都可以用循环来代替，所以我觉得这就是所谓的深度算法吧
对我来说，我的想法就是，按步数算
初始设置所有节点都为0，起点为1
第一步，从起点开始，计算起点的所有可用出口，找到之后标记为1，记录所有为1点的路径，由于起点的所有出口已经标记，所以标记为2。如果这时候标记点中没有终点，那么继续下一步
第二步，寻找所有标记为1的点，找他们的出口。如果他们的出口有为0的，变成1，并记录路径。当一个标记为1的点的所有出口都遍历结束后，把自己标记为2。
第三布，循环第二步，直到将终点变成1，这样最短路径就出来了
这是我的算法，不知道对不对

当然，理论上可以从两端往回算，但有个问题：有些地方是单向的，能走过去未必能走回来，所以恐怕不行啊......

但有个问题：我希望这个“图”，是带边长的。换句话说，每一步的距离应该是不同的，这样怎么算最短距离？请教

bbz

计算最短路径可以参考  dijkstra算法，在遍历的时候同时计算起点到当前点的最短路径，不过感觉对于mud来说，计算量有点大

zipcht

好贴，希望继续讨论

ltblue

回复 4# bbz


    恩，大概看了一下你说的d什么的算法，基本是跟我的想法一致。
    其实计算量应该未必很大，由于地图的块比较少，应该也就1000个左右，找到一个点的时间应该不长。
我怕的是反复计算，那就麻烦了
比如：某任务说，在扬州有XXX，要干掉
这我就要遍历整个扬州。可是怎么生成路径呢？现算吗？
那我就要走到第一个点，然后再计算从第一个点到第二个点的最短径路，再计算第二个点到第三个点的最短径路......城市要是有100个点，就得计算100次，虽然一般比较近，但我怕这个太慢

bbz

回复 6# ltblue


    如果只是在扬州找人的话，用最简单的广度优先的遍历就行了，人物一个房间一个房间的找。
但如果是到扬州的某个房间的话，首先得有房间的表，然后在这个表里遍历，遍历完成时最短路径也生成好了，然后人物就按路径走过去

xxxcc

1，分区域较好，后期维护方便，因为用A*算法，所以我的房间是带坐标的，分区域的话，每个城市都是独立的坐标系，当地图发生改变的时候，重画地图非常方便。
2，寻路直接套用A*算法即可，只需要0和1两个标记，当前节点的周围不存在0节点，且不存在目标节点的时候，就返回上一个节点，重新搜索和标记，具体实现的话，100行代码都不用。
3，遍历的话，以当前房间为起始位置，用广度或者深度优先生成需要遍历的房间列表，然后用寻路算法依次计算路径并行走就行。
4，分区域的话，用递归完全没问题，我这边最多的内存占用率也有100M不到。
5，遍历时候，每个房间重新生成路径，也不存在速度问题，未发现丝毫顿卡。