[Home] [Groups] - Message: [Prev in Group] [Next in Group]

nu.kanga.list.mud-dev

21563: Re: [MUD-Dev] Tech: Pathfinding with Rooms

[Full Header] [Plain Text]
From: Christopher Kohnert <chris@achaea.com>
Newsgroups: nu.kanga.list.mud-dev
Date: Thu, 29 Nov 2001 13:15:10 -0700
References: [1]
Organization: Kanga.Nu
Sanxion wrote:
 
> So whats the best way to pathfind in a MUD Room model? In a grid
> system you can estimate the cost, but without being able to
> estimate the distance between starting and ending point the
> pathfinding just spreads in all directions ending up searching
> alot of rooms.
 
> Do you start pathfinding from Starting and Ending point until they
> meet?  Is there a smart way to get a good heuristic
> (i.e. manhattan distance) with MUD rooms?

Looking at the rooms and their connections as a graph of nodes and
edges, you can apply any sort of graph traversal techniques. For
blind shortest path type stuff, a nice BFS (breadth first search) is
typically a decent route. You can get more fancy if you want to
precompute some things or provide some sort of hints regarding flow
of exits (think: does this exit lead to a large area which I know my
destination room is inaccessible from (such as a cul-de-sac)).

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