[MUD-Dev] [TECH] Shortest-Path

[Richard A. Bartle]

On 8th April 2002, Amos Wetherbee wrote:

> This is also of interest to me. One thing that I am interested in
> is instead of generating the entire path, I want to be able to
> make one call to find the next room closer to where I am trying to
> get too

This is only going to work if the topology of the network can be
exploited in some way. For example, if you were trying to plot a
course from A to B on a co-ordinate graph where there were no
obstacles, you could use the same kind of approach that line-drawing
algorithms use.

In the general case, though (which is the one you have), this isn't
going to work.

> This solves two problems: NPCs can walk slowly to their
> destination, and their path won't get screwed up if a door locks
> or an area blips out of existance.

If you want to do this, you have to generate the shortest path each
iteration (or, if you want to be less inefficient, each time the NPC
finds its path blocked). Otherwise, were you merely to approximate
the direction in which you believe the shortest path lies, you could
end up cycling: node X tells you to move to adjacent node Y, and
node Y tells you to move to node X. This is basically what happened
in Civilization II, where they had to put in a count to stop units
from cycling between two points indefinitely. Civilization III has a
shortest path algorithm that works (based on A*), but it's called so
often that it can mean a 5 minute delay between turns on a big map.

> Perhaps generating the whole path first is more efficient?

Given that you have to generate the whole path each time if you're
to "know" which is the shortest route, it's something you'll be
doing anyway, whether you like it or not.

Richard

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