[MUD-Dev] Tech: Pathfinding with Rooms

David Bennett ddt at discworld.imaginary.com
Thu Nov 29 17:37:19 CET 2001

On Fri, 29 Jun 2001 vognsen at post10.tele.dk wrote:

> If you really need realistic path finding and the like I don't
> think the standard room model is up to the task. As you mention
> yourself, positioning everything on a grid simplifies the problem.

Discworld uses a Depth first search, with weighting based on
pseudo-coordinates.  The co-ordinates are calculated using the exit
directions, every exit has a direction associated with them and an
offset from the current rooms co-ordinates.  This works quite well.

We then 'cluster' the rooms together into blobs and do route finding
on the clustered blobs.  Then find routes through the blobs
themselves, caching the results.  It is relatively efficent for
finding quite long routes.  We cache the routes too.  We don't load
all the rooms either, all the room data is stored in a database
which we use for the route finding.


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

More information about the mud-dev-archive mailing list