[MUD-Dev] Room Searching

Adam Martin amsm2 at cam.ac.uk
Thu Apr 5 14:20:56 New Zealand Standard Time 2001

----- Original Message -----
From: "Derek Licciardi" <kressilac at home.com>
To: <mud-dev at kanga.nu>
Sent: Monday, April 02, 2001 9:55 PM
Subject: RE: [MUD-Dev] Room Searching

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

When looking to do dynamic-best-path-finding (ie finding an optimal
route from A to B, with frequent-re-evaluation necessary) as opposed
to doing path-existence (ie is there any route from A to B), howabout
arranging locations in your game hierarchically in a tree - e.g. every
room along a street is a child of the street, every street in a town
is a child of that town, etc?

This would enable you to climb up the tree from the destination until
you reached a node for which IsSubnode( source ) was true, which gives
an approximation to an optimal route in very short time (you then
climb from the source up the tree until you reach the same node,
giving the other half of the path). The actual route requires that you
define a relationship between nodes/sub-branch or
(same-node)branch/branch, such that given two branches of one node,
there is a statically-defined method of travel from one to the other.

Adam M

MUD-Dev mailing list
MUD-Dev at kanga.nu

More information about the MUD-Dev mailing list