[MUD-Dev] Room Searching

[Eli Stevens]

----- Original Message -----
From: "Jared" <jared81 at jps.net>
To: <mud-dev at kanga.nu>
Sent: Sunday, April 01, 2001 11:25 AM
Subject: [MUD-Dev] Room Searching

> 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.

Perhaps you could start with one room known to be public (starting
from, say, a Midgard-esque town center) and make a list of all the
rooms that can be traveled to from it using only two-way exits.  I
would suggest using a breadth-first search and keeping duplicates out
of the list of pending rooms to check.  Along the way, keep note of
the one-way exits you find, but don't follow them (why is explained
later).  Once you have the connected room list (which should be all of
the rooms that anyone can walk to from public areas), use that however
you want to get all the rooms still in question.  Hopefully, this
remainder will be much smaller than 8000 (I am imagining that there
might be recall areas with one way exits, areas under construction or
somesuch).  From there, you can do the same search on each, looking to
see if the rooms in question ever has a path to your larger blob of
public rooms.

Aside, I would not reccommend using recursion.  Instead, use a stack
and a loop for depth first search, or a queue and loop for breadth
first.  I don't really know if most modern compilers can detect and
optimize tail recursion, but the stack/queue-loop solution is pretty
trivial to implement, and you can be assured that you will not run out
of space on your function call stack.  ;) I would also reccomend the
standard template library (STL), if you are using C++.  Of course, I
could be wrong here...  So take it all with a grain of salt and a
decent profiler.  ;)

The end result that I envision is a directed graph, but instead of
each node being a room, it is a collection of rooms that are all
accessible from each other.  Unless your mud has a lot of interesting
geography, this graph should be fairly small (at least in terms of
what a computer can handle quickly).

The can_walk function would then check if the two rooms were in the
same node (I think that a decent hash table might be your best bet for
storing the list of rooms in a node, because most likely one node will
have the majority of rooms and having to do a O(log n) binary search
on that too often might bog down).  If they are, it returns true
(accessibility being the definition of two rooms in the same node).
If not, then it searches the graph to see if it can get from the
origin's node to the destination's node.  Again, unless you have
interesting geography, your graph will most likely look like a bunch
of small nodes with a single edge pointing in to the larger set of
public rooms.

So, computationally, on average, finding the node in the graph for
each room (r being the number of rooms, n being the number of nodes, h
being the number of hash indicies):

 (nodes to search / 2) * (time to search node 
 = hash function + collision funciton)

 (n / 2) * O(constant + log(r / h))

Hopefully, the hash table will be well behaved enough to offer O(1)
i.e.  constant time.  If the nodes are searched for the rooms starting
from the nodes with the most rooms, then even the O(n) nature of the
overall search will tend toward constant time (since most rooms will
be found on the first search).  In the worst case, it would be O(n +
log(r / h)).  Hopefully, r would not be too many orders of magnitude
above h and the geography of your mud is not too fragmented (leading
to a large n) so this isn't too bad.  :)

Of course, this all assumes that your room connectivity does not
fundamentally change often (I am not talking about opening and closing
a door here).  Adding a two-way exit would be pretty simple to handle,
because you would just need to add the rooms behind the new exit to
whatever node the first room belongs to.  A one way exit would be
adding an edge to the graph, assuming that the two rooms were in
different nodes to start with.  Making a one-way exit two-way would
combine the two nodes into one, keeping all the other edges the same.
Removing an exit would most likely mean that you would have to
recompute the whole durn thing (I cannot see any shortcuts to
detecting if a given exit isolated the rooms, or just cut a loop, but
that doesn't meant they don't exist).  A decent book on graph theory
would probably be your best friend here, if you care that much.  ;)

> 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.

Yup, that would be bad.  :) Assuming all my assumptions (hmm...) are
correct, then what's above should work out.  Of course, if anyone sees
any flaws in my thinking, pleasepleaseplease point them out.  I like
to know when I am wrong, so I can make sure it doesn't happen again...
;)

Good luck,
Eli




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