[MUD-Dev] Room Searching

[shren]

On Sun, 1 Apr 2001, Jared wrote:

> The dilemma is that I don't know how to find if "room B" can be
> walked to from "room A". That is to say, if a room cannot be walked
> to in the game, and it isn't a clan or guild headquarters, then it's
> illegal to be in. I need some function like:
 
>   bool can_walk (ROOM *origin, ROOM *destination);
 
> Which would return true if 'destination' can be walked to from
> 'origin'. The rooms all have the four cardinal directions in
> addition to up and down as their exits, and the only solution I've
> found thus far is to treat the situation like searching a tree with
> at most six branches, over the course of 8000 rooms.

> However, this solution of mine seems computationally expensive and
> if I'm running through this traversal for each room, that's an 8000
> node tree traversed 8000 times- which makes me think I'm going to
> bring the server to its' knees. I don't have any real idea of how
> hardcore this is gonna be, but I'd like some input on it before I
> try using the
> tree-approach.

You can do this "and a whole lot more" with graph theory algorithms,
many of which you should be able to find on the net.

  1 --- 2 --- 4 --- 5
  
        3 --- 6

If you want to work it out yourself, however, then consider marking
each node as you visit it.  If you start at node 1 and seek outwards,
marking each node "a" as you visit it, then when you scan again from
node 2, if node 2 is marked "a", then you know that node 2 is in the
same set as node 1 (because node 1 reached it), and you can skip the
node 2 scan.  If you scan from 3 and find that 3 is not marked "a",
you know that 3 is in a different "sub-net", and scan outwards from 3
marking nodes "b".

Thus, you should visit each node about twice.  Once because you're
iterating through all the nodes, and once because you are scanning and
marking all of the nodes.  16000 is better than 8000 * 8000.

  a     a     a     a
  1 --- 2 --- 4 --- 5
  
        3 --- 6
        b     b

For the above tree, you'd start at 1 and mark 2, 4, and 5.  Then you'd
start at 2 and quit (because 2 was marked in one's scan.)  Scanning
from 3 you'd mark 3 and 6, and then when you scan from 4, 5, and 6,
you don't scan at all, because 4, 5, and 6 are already marked.  Thus,
you visit 1 and 3 once, and 2,4,5 and 6 twice, for a total of 10 node
visits instead of, uh, 18.  (The savings are bigger on bigger trees,
of course.)

If I didn't just give you a splitting headache, then that should set
you up.

--

x
xxx
 x

_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev