[MUD-Dev] Room Searching

[Daniel.Harman at barclayscapital.com]

-----Original Message-----
From: Jared [mailto:jared81 at jps.net]
Sent: 01 April 2001 17:25
To: mud-dev at kanga.nu
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.
 
> 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.

I may have missed the point here, but if not, you may have and I can
save you some time...

If you can assume that you are only trying to find rooms that can't be
reached from a given known to be good point (one of them!), then you
really can cut the computation down to one pass. You merely
recursively explore every room starting at this point, marking them
off on a list as good as you reach them. This single pass will spot
any hit any room thats accessible from the known to be good room.

If thats what you are looking for, its not going to take any time.

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