[MUD-Dev] [TECH] Preloading path information

[Kevin Mack]

<EdNote: Top posting fixed and quote trimmed.  Please place new text
below the quote it refers to and trim the quote as per
http://www.kanga.nu/listslistinfo/mud-dev/ -- claw>

From: William Murdick

> I've been working with shortest path algorithms such as Djikstra's
> and Bellman's. However, I recently came across an article on the
> MUD-DEV list from April 2001

>  http://www.kanga.nu/archives/MUD-Dev-L/2001Q2/msg00028.php

> in which Hans-Henrik Staerfeldt suggested preloading parts or all
> of the possible paths in the mud as long as your mud was static.

This is fundamentally the approach taken by Unreal Tournament and
several other games.  Level designers place path nodes about the
level during design, and when a bot then needs to find its way
around during gameplay, it simply chooses a destination, selects the
optimal node chain to get there, and then approaches the nearest
node from its present location.  A bit of processor overhead is
still required to select the appropriate node path, but it's a
significantly less onerous task than that of attempting to discern a
path from scratch amid complex geometry.  Downsides are that a bit
of designer expertise is required to devise effective paths;
otherwise, certain areas will simply never be visited by the bots,
or bots may become hung up on geometry when trying to follow badly
placed nodes.  Another downside is that node-following behavior is
often noticable to players who know to look for it - they learn
where the 'rails' are and exploit that knowledge.  In certain
instances, a combination of approaches - nodes to help with
difficult terrain, simple pathfinding in simple terrain, can produce
believable, but still economical behavior.  If you're willing to
mess around a bit with UnrealEd 2, you'll get a fairly good idea of
the pluses and minuses of pathnode networks.

In all cases, should you choose to employ full-field pathfinding,
I'd favor A* over Djikstra's algorithm simply because Djikstra
distance-maps the entire board equally, without regard for
early-discernable optimal solutions.  A*, by contrast, attempts to
walk the euclidian distance between source and destination first,
and if it fails, tries successively less optimal paths until it
arrives at a workable solution.  A*, therefore, will generally find
an optimal path in a fraction of the time required by Djikstra, and
in a real-time 3d environment with several bots, you'll feel the
hit.

- Kevin Mack
- <kevinmack at earthlink.net>
- www.inclusiveimages.com
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev