[MUD-Dev] Room Searching

[Derek Licciardi]

> -----Original Message-----
> From: mud-dev-admin at kanga.nu [mailto:mud-dev-admin at kanga.nu]On Behalf Of
> Jared
> Sent: Sunday, April 01, 2001 12:25 PM
> To: mud-dev at kanga.nu
> Subject: [MUD-Dev] Room Searching

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

On the NET and inside many algorithm books there are graph traversal
algorithms.  One of the things that you will have to decide upon is
the shape of your graph.  Does your room structure typically have each
exit available in all rooms or are many of your rooms configured with
only one or two exits.  From my experience this is usually the case
and therefore would recommend a depth first travesal of the list.  You
can further optimize the code by making sure that your map of rooms
does not do crazy things, like connect arbitrary points on one side of
the world to other points on another side of the world.  If you map is
organized like a specific shape (ie a cylinder, square, donut,
rectangle...) then you have the ability to make assumptions about the
location of your target from the destination before you even begin the
traversal.

If you are trying to get from a target that is known to be east of you
then start the depth traversal in the east direction.  There is a good
chance that you can eliminate much of the overhead in room
searching/pathfinding by logically ordering your map and applying a
good algorithm to it.

The last things you can do is limit the iterations of the depth
traversal.  Limit just how far a single depth can go.  Limiting your
depth to say 8 nodes would mean that your search would be within a box
16x16x16 and if the destination you are looking for is not within that
box then it can not be walked to from that origin. (In this case 0x0x0
is the center of the box or the origin) If you combine this with the
last thought, then you could make it so that mobs would walk in the
general direction of the destination by moving towards the outermost
limit of the depth limited traversal in the known direction of the
target.

Expanding upon this could be waypoints.  If a string of rooms is a
path through the mountains, then incorporate waypoints into the
algorithm and make sure that each room understands where the next
waypoint is.  The waypoints can be a method of breaking the search
algorithm before it searches all rooms, thus increasing performance.
If the current node in the search is equal to one of the origins
defined waypoints then you can get to that waypoint in route to your
destination and skip the rest of the searching algorithm. (this is of
course unless you want to find the optimal way of getting there which
requires you evaluate all paths, weight them and compare) Be careful
using these everywhere, as you players will learn the pathing of the
mobs and easily defeat mobs that happen to run from them.(ie
EverQuest)

Anyway, I hope this helps.

Sincerely
Derek Licciardi

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