[MUD-Dev] Tech: Pathfinding with Rooms

[Hans-Henrik Staerfeldt]

On Thu, 29 Nov 2001, Nicholas E. Walker wrote:

> You'd probably be best off using a spanning-tree algorithm.
 
There may be problems with a MST approach, if you try to use it for
a large MUD that is location based.

Either, you may need to potentially traverse every room when you
want to find a path, which for a large number fo locations can be
CUP intensive.

Using statically created MST's for your game may also pose problems;

  - you may need to store MST's reflecting paths to all other
  locations in each node, and you could end up with quite alot of
  data on your hands. (there are ways to compress this though, given
  a strongly clustered topology of your game)

  - a path may be valid only for some characters (only wizards may
  pass certain exits) which means that your pathfinder would break
  down for some characters.

  - a fixed MST could not take into account changing exit status.
  If a door is locked and your fixed path goes through it, youre
  lost.

just a few thoughts.

Hans Henrik Stærfeldt   |    bombman at diku.dk    | work:  hhs at cbs.dtu.dk      |
Address:                |___  +45 40383492    __|__       +45 45252425     __|
DTU, Kemitorvet,        | Scientific programmer at Center for Biological     |
bygn 208, CBS.          |  Sequence Analysis, Technical University of Denmark|

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