[MUD-Dev] Room Searching

[Hans-Henrik Staerfeldt]

On Sun, 1 Apr 2001, Jared 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

   bool can_walk (ROOM *origin, ROOM *destination);

Others have described mark and sweep algorithms for finding shortest
path in a network.

If youre using a DikuMud derivative, you can easily precompute all
shortest paths for the static environment and store them. The reason
why this information does not explode is that for each room, you
simply need to state which rooms / areas are reached thru wich
direction. Since rooms with similar identifiers are often grouped
together geographically, and thus most often are reached through a
path that start with the same direction from a given point. Most
common instance of this is the fact that most rooms in a single area
in another area often have the same path. Thus you can store this
information as 'ranges' of rooms and areas than can be reached by the
shortest path by a given direction.

This scheme of precomputing does not deal well with dynamic
environments and user dependable acessibility however, and if you need
this you may need to recompute a path for each use(r).

Another way is to make a hybrid; You can pre-index the static parts of
the game (roads and open countryside, etc.) Then when you try to find
your way from A to B, try to find the shortest path to a static part
from each point, and then use the precomputed 'roadmap' for connecting
the rest.

This may give rise to odd movements :-) But it would probably do well
in most cases.

Hans Henrik Stærfeldt   |    bombman at diku.dk    | work:  hhs at cbs.dtu.dk      |
Address:                |___  +45 40383492    __|__       +45 45252425     __|
DTU, Kemitorvet,        | Scientific programmer at Center for Biological     |
bygn 208, CBS.          |  Sequence Analysis, Technical University of Denmark|

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