I already downloaded that cool AI demo thingy, and I saw it in action, so I know the basic idea, but now i guess implementation is the problem. Watch this:

IMPLEMENTATION!

That was tight yo!!

Zipster--you remind me of a young kid who is not such a little kid anymore--myself! I, captain freedom, when I was eight, went to classes at MIT to learn more on A*, Djkistra, and other such path-finding algorithms to find my path through life (easily). However, they all pointed to one thing--Super hero! Thus, I became the super hero as you see me today!

As you might know, I am the bird, the plane, the super hero that watches over all my superbuddies to make sure they get their share of Snickers, and the Freedom DancE! So, my point is that the Freedom BLASTER needs fixing--so, if you could fix it, come over to the High COMMANDER Plaza in Supercity, Freedomland, USA ASAP!!

My hobbies include eating snickers, doing the freedom dance, drinking coffee, and using super powers.

May freedom help you cope with life...
Captain FREEDOM!!
Destroyer of evil, bringer of good news...
(More good news to come)...

quote:Original post by Zipster

I already downloaded that cool AI demo thingy, and I saw it in action, so I know the basic idea, but now i guess implementation is the problem. Watch this:

IMPLEMENTATION!

IMPLEMENTATION boils down to a list of questions completely answered one

after

another.

1) What sort of space do you have: Tiles, Hexes, Flat-Space 3-D ??

it is THE question because, while the priciples of A* remain the same, the implementation changes drastically with the space type. You usually end up adapting either the space or the search by their interactions. Implementation also uses your collisions detection methods.

ZoomBoy
A 2D RPG with skills, weapons, and adventure.
See my character editor, Tile editor and diary at
Check out my web-site

In a step-by-step process, maybe you should build a quick-path generator 1st. It would just give you a list of tiles or hexes or points but didn''t worry about any obstacles. This would set up: path-storage for the object moving and help you choose how to implement A*

So I built a path creator 1st for my hex-surface. From, tada, the Starting Point, it looks at the nearest 6 hexes and, using a squares-of-the-distance( [(TargetX - CurrentX)^2 + (TargetY - CurrentY)^2] chooses the lowest cost hex). I store that direction(0 to 5) on my list( actually a string of 70 chars like "00011222332212xxxxxxxx")
I then chose too examine that "best" hex(the six hexes around it and keep repeating until the CurrentX+Y are the target.

With a flatspace it''s like you have to draw a line to a point and check to see if it intersects any thing. So you''ve got to build a line intersection function.

ZoomBoy
A 2D RPG with skills, weapons, and adventure.
See my character editor, Tile editor and diary at
Check out my web-site

Can someone please send me a link to his "PathDemo" program? I can''t seem to find it. Thanks.

jmbianchi@yahoo.com

Find a link for his path-demo at Amit P''s AI web-site, under shortest path It''s my favorite for all types of missions.

ZoomBoy
A 2D RPG with skills, weapons, and adventure.
See my character editor, Tile editor and diary at
Check out my web-site

Heh, I guess I can just ask my senior programmer friend at Westwood Studios for some AI tips...

*DISCLAIMER*:
The above information is 100% true. Zipster (whoever he may be)DOES know a senior programmer at Westwood Studios.)

A* is somewhat related to the Djikstra algorithm -- the difference being that A* uses a heursitic (i.e. an estimate of the cost) to help speed along the algorithm.

Djikstra''s is easier to explain (firstly). Basically it blindly searches from a start point: it checks every path recursively until it finds a path that happens to have the end point (or destination) in the path. As it iterates through the paths, should it ever find a path to a place it''s already been, and this new path is shorted than the existing one, it replaces the old path. Therefore Djikstra''s will eventually find the shortest path to every place on a map (of course you''ll stop when you reach the desired destination).

Note that Djikstra always searches the shortest path first, which leads to a kind of breadth-first search.

A* is a modification that effects the breadth-first approach. Basically each location is also assigned an estimate of how far from the destination it is (on a simple grid this can be as simple as the length of the line from the location to the end point). A* then basically rules out estimated costly paths in favour of less costly shorter paths.

This produces the same result (albeit) quicker, if the estimate is never greater than the actual cost from that location. If you start increasing the estimate above the actual cost, your algorithm will likely start to find paths quicker and quicker, but they are no longer guaranteed to be the "best" path.

Chosing the estimate is the most difficult part of the A* algorithm.