From:	Brett Leslie Porter <blp01 AT uow DOT edu DOT au>
Message-Id:	<199708040630.QAA29179@banshee.cs.uow.edu.au>
Subject:	Path finding algorithm
To:	djgpp AT delorie DOT com (DJGPP)
Date:	Mon, 4 Aug 1997 16:30:22 +1000 (EST)
Cc:	blp01 AT banshee DOT cs DOT uow DOT edu DOT au (Brett Leslie Porter)
MIME-Version:	1.0

Okay, please don't flame me if this is the WRONG place to put this 
question, just point it out nicely and tell me where to go (where to go 
on the 'net to find out, that is).

I'm writing a Sierra style game. It was getting there with Borland, but 
pretty slowly. Now I have DJGPP and I am going to start from scratch 
trying to implement better algorithms/coding styles (using my previous 
effort as a reference).

My problem was with the algorithm that let the character walk from one 
point to another, avoing obstacles on the way. Effectively, this can be 
thought of as having a 320x156 grid with each pixel on or off, depending 
on whether it is the boundary of an object in the room, and then finding 
a path from one point to another, without crossing over a pixel that is 
"on". The path is defined by a specified amount of lines, each line with 
a start and end point (obviously).

I already have a solution that works, but it is VERY slow (if you click 
in a place that is inaccessible it takes about 30 seconds to figure this 
out on my 486DX2/66 - not very playable). "Optimizing" the code will not 
help as the algorithm is just bad.

Any help would _greatly_ appreciated (including a mention in the credits 
of the game, if it gets finished :). I'm not really aiming at selling the 
game or anything, just building up and engine to work on with better 
projects.

If you think you might be able to help but would like to see the source 
to my original routine, just e-mail me and we'll figure something out.

I am _desperate_ to finally figure this one out. It has been driving me 
crazy for at least a year (I have done much work on other parts of the 
game in the meantime!)

Thanks in advance,

Brett Porter.

- Raw text -