[MUD-Dev] Tech: Pathfinding with Rooms

[vognsen at post10.tele.dk]

On 29 Nov 2001, at 3:50, Sanxion wrote:

> I'm new to this list. I have a questions about pathfinding in
> MUDs. I know how to handle pathfinding on a grid, but from what I
> understand most MUD rooms do not have a X and Y position as a
> tile/cell would have on a grid.  MUD rooms have a series of
> connections to surrounding rooms. 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.

You have several options. One is to augment exits with a distance
metric. Then you can build a weighted digraph based on the topology
and distances and use e.g. Dikjstra's algorithm. You have to be
careful about inconsistencies though. It is sometimes possible to go
around a loop and get back to the starting point with a net negative
distance. So some sort of sanity checking is almost certainly
required.

The other option is a (simpler) special case of the first. Assume
that all exits have the same distance associated with them. Then
it's simply an unweighted digraph and you can use a Breadth First
Search (BFS) or Depth First Search (DFS) -- likely the former.

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

You don't have to but bidirectional BFS is definitely possible and
has a lower worst-case complexity IIRC. You might also consider
iterative deepening BFS. One of the problems with BFS is that it has
very large memory requirements compared to DFS. Iterative deepening
BFS might be called a BFS/DFS hybrid. You first DFS to depth 1, then
depth 2, and so on ad libitum. You might want to look into A* and
other informed search algorithms. They're almost certainly even
harder to apply to room topologies but there might be a relatively
simple way I haven't thought about yet.

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.

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