[MUD-Dev] Room Searching

[Travis Casey]

Sunday, April 01, 2001, 12:25:15 PM, Jared <jared81 at jps.net> wrote:

> I'm new to the list as of about nine minutes ago, and I joined
> because I have a question to which I have only one answer but would
> like to have as many answers as is conveniently possible.

> I'm the head coder on a mud called Cursed Lands (mudbox.net 6969)
> which is a heavily modified GodWars codebase (originally based upon
> Merc, for those unfamiliar with GW) and I've recently run into a
> small dilemma. Before the dilemma, we have some background
> information. The world of CL is in a state of incredible disrepair
> right now, and I have no real way of knowing what is and isn't a
> work in progress, etc. The immortal communication scheme before my
> arrival was nonexistant, but as of the past few months, they've gone
> through some changes and I want to push those changes further.

> 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 don't say what use you're going to put this to, beyond mentioning
that you want to know if it's illegal to be in a room.  Is this
something that you plan to use "on the fly"?  Or would a solution that
you can run once and then keep the data from around work?

If you just want to know which rooms should be illegal for characters
to be in, then a graph-coloring scheme should work.  Something like:

 - Pick a starting room.  Mark it as legal.

 - Find all the rooms attached to it.  Add them to the list of rooms
 to check.

 - For each room in the list of rooms to check:
 
   - Mark it as legal (you got here, after all).

   - Find all the rooms attached to it.  Check each of them to see if
   they're already maked as legal.  If they are not, check if they're
   in the list of rooms to check.  If they're not, add them to the
   list.

   - Remove this room from the list of rooms to check.

This method will find all of the rooms that can be reached from your
starting point, and will run in a much shorter time than what you're
describing.  Of course, it will also use more memory, since you're
remembering what rooms you've already managed to reach, but there are
always tradeoffs.

You can then save the info about what rooms are legal, and re-run the
algorithm periodically -- either on a regular schedule, or whenever a
new area is added, or whatever.

One last thought -- is there any reason why this has to be done on the
server?  If you can run it and save the results, you could copy all
the data files it needs to another machine, run it there, then upload
the results back to the server.

--
       |\      _,,,---,,_    Travis S. Casey  <efindel at earthlink.net>
 ZZzz  /,`.-'`'    -.  ;-;;,_   No one agrees with me.  Not even me.
      |,4-  ) )-,_..;\ (  `'-'
     '---''(_/--'  `-'\_)   


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