[MUD-Dev] Tech: Pathfinding with Rooms

[Christopher Kohnert]

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 at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev