From:	"Ben Davis" <ben AT vjpoole DOT freeserve DOT co DOT uk>
Newsgroups:	comp.os.msdos.djgpp
Subject:	Re: Programming DOS Games
Date:	Sun, 23 Apr 2000 15:07:40 +0100
Organization:	Customer of Planet Online
Lines:	25
Message-ID:	<8dv061$jei$1@newsg3.svr.pol.co.uk>
References:	<0b90d704 DOT 0b83a6cd AT usw-ex0108-062 DOT remarq DOT com>
NNTP-Posting-Host:	modem-78.crixivan.dialup.pol.co.uk
X-Trace:	newsg3.svr.pol.co.uk 956498945 19922 62.136.87.78 (23 Apr 2000 14:09:05 GMT)
NNTP-Posting-Date:	23 Apr 2000 14:09:05 GMT
X-Complaints-To:	abuse AT theplanet DOT net
X-Newsreader:	Microsoft Outlook Express 4.72.3110.5
X-MimeOLE:	Produced By Microsoft MimeOLE V4.72.3110.3
To:	djgpp AT delorie DOT com
DJ-Gateway:	from newsgroup comp.os.msdos.djgpp
Reply-To:	djgpp AT delorie DOT com

>I need information about AI, path finding algorithms.

Here's one pathfinding algorithm:

Let A be the object doing the pathfinding, and let B be the object you're
trying to find.
Do a floodfill, starting from B. This spreads in all directions, and will
eventually find A (assuming there is a path).
Create a separate array, shaped like the level, for these purposes. We'll
call this 'flood-fill space'.
Initialise the floodfill space to -1. When you start the floodfill, store 0
in the starting square. Each time you spread to the next square, increment
the number. Make sure you detect when the floodfill finds object A.
Then object A can follow the path of decreasing numbers.

If you have multiple B objects, you can do a floodfill from A first to
determine which one is nearest.

I refer to squares above, but this will work with any level units.

Hope this helps,

Ben Davis

- Raw text -