From: "Alan McFarlane" <amcfarlane AT bigfoot DOT com>
Subject: Re: Movement AI
Newsgroups: comp.os.msdos.djgpp
References: <35d3acf5 DOT 0 AT news DOT provide DOT net>
Message-ID: <01bdc82a$4ce50120$12c522c3@xx5828>
NNTP-Posting-Host: 195.34.197.18
Date: 15 Aug 1998 08:58:42 GMT
Lines: 73
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

Hi Sean,

I wrote a routine once that was so good at path finding, I had to use god
mode all the time!
Basically, if I'm right, you are looking at moving a character (NPC) around
a maze.
What you need is a simple bit of recursion. Take a copy of the maze area,
using an int for location.
Assign a very big number 0xffffffff to walls and 0x0 to everything else.
From the NPC position, assign a 0x1 in each cell around them, and then for
each of those cells
unless it's a wall, increment the number. Keep doing this recursively, then
all you have to do is know
where you want to go. Your NPC will now "solve" the maze, by sometimes
going away from you, but
he will always catch you in the end. The trick is to limit the depth of
recursion to say 50 moves, so
if the NPC is further than 50 units from the PC he might move in a random
way.

Hope it works, any trouble give me a shout and I'll see if I can find the
source code
--
Alan McFarlane
amcfarlane AT bigfoot DOT com


Sean Middleditch <aweplay AT hotmail DOT com> wrote in article
<35d3acf5 DOT 0 AT news DOT provide DOT net>...
> Dear AI Programmers,
> 
>[snip]
> 
>  This problem is the movement AI.  I can easily make an NPC move towards
a
> point ( at this time only the PC, or Player Character ).  However, this
> movement is very simple.  Although I could make a tad bit more advanced,
I
> could never pull off what I've seen in modern games.  Basically I need
> path-finding code.
> 
>  Consider the following example:
> 
>     N *
>         *      *
>      *****   *
>                         *
> *************     *
>                          *
>                     ****
>                          X
> 
>  N is an NPC, *'s are walls, and X is the target destination.
> 
>  I need a way to get N to find the most direct route to X.  The best code
I
> can come up with either simple moves towards its target ( the N would get
> stuff in the first corner it encountered ) or to keep all walls to its
right
> ( or left ), though that would often be very inderect, or take it far
from
> its destination.
> 
>[snip]
> 
>  Sean Middleditch
>   of
>  AwesomePlay Productions
>  http://www.angelfire.com/biz/aweplay
>  aweplay AT hotmail DOT com
> 
>