I’m trying to create a pathfinding AI using the A* algorithm. Now I’ve got a little question. All the explanations are with grid stuff, but I’m working in 3d with pathpoints. So on every corner in a level, there’s a pathpoint. So the nodes are pathpoints. If I start with pathpoint A, I search for other available pathpoints, let’s say it comes up with 2 available ppoints, B and C. Now I need to pick out the best one. This is done by costs. But the only cost I can come up with is wether the one point is closer to the target then the other point. Let’s say B is closer to the target than C, this won’t say I need to pick B, for B could lead to nothing, while C could. What would be the good equalation? Or what would be the heretic function for this? Am I clear, or not?

Write a recursive function that "walks" every possible path and remembers the distance he had to walk until he reached the target.

The path with the shortest distance is the path you should take.

It''s not the fastest way, i think, but it''s a way

greetings,
Lord Skeletor

If you implement A* correctly, it will figure out that B leads nowhere because it will never find the goal/target along that pathway/branch. A* doesn''t decide at each level where it should go, it decideds which branch to follow (based on cost so far + heuristic, in your case distance to target) to decide which node will more likely give a short path, and continues until you either stop the search, or until it finds a goal node. Generally in pathfinding you will continue A* (possibly over several frames if it is extra large search space) until you reach the goal, the you start the character moving along the path that A* found.
You already have found quite a reasonable heuristic for this, closeness to the target (straight line distance). You must remember (don''t worry, a lot of people have trouble with this in the beginning) a heuristic is only supposed to give an estimate of the distance to the goal, it is NOT supposed to solve the whole problem, if it did you wouldn''t need to search!!!

To Anonymous poster:

quote: Original post by Anonymous Poster
If you implement A* correctly...

I didn''t realy implement it yet. I''m figuring out the theory, so I can fully understand it.

quote: Original post by Anonymous Poster
You already have found quite a reasonable heuristic for this, closeness to the target (straight line distance).

I tought I knew what a heuristic realy was, but I think I''m a bit confused on this now.
f = g + h
g = the depth in the graph
h = the cost, am I right?
So H estimates the cost, is this true?

quote: Original post by Anonymous Poster
a heuristic is only supposed to give an estimate of the distance to the goal

hmmm, but I can calculate the distance between the AI-point and the goal, so why do I need to suppose it, or am I totaly misstaken on this scentence?

To skeletor:
You''re right, it''s away, but shouldn''t it take away a lot of memory and time?

ok
f(n) = g(n) + h(n)
f(n) is the total cost you use to decide which node to follow next. You follow the node with the least f(n) value until you reach the goal (or other specified cutoff point).
g(n) is the path cost so far to node n. When you are at the root node (beginning point) the g(n) is 0 because you are already there. Then say you get to B, the g(B) may be equivalent to the distance between the root and B.
h(n) is the heuristic function. This is an estimate of the (distance, time, whatever you decide to use to measure) between the current node, and the goal. You may decide to use a straight line distance heuristic that gets the distance between the current node, and the goal node "as the crow flies". There may be obstacles in the way of that straight line, but thats ok, because the heuristic doesn''t have to be exact, just an estimate. (Also for optimal A* you should make sure your heuristic never overestimates. Straight line distance is fine for this because unless there is, some way to jump through time you should be ok)
So, when you expand a new node you: Look through all the nodes you have avaialable for expansion. Find the one with the cheapest f(n). You do this by calculating the current path cost (the addition of the path costs of it''s parent, it''s parents parent etc.) and then estimate the distance to the goal. The node with the cheapest path cost plus estimated distance to go is then expanded.
Any lengthy search process will take a lot of memory and time, but thats just the way it is.
I hope that helps your understanding, i can only suggest you do some more reading on the A* algorithm.

Hey, I was a bit confused with my last post.
In the maintime I understood A* correctly.
I've already created a code, would you mind looking at it?
THX for your help already.

EDIT:
By the way, the code is only 1 page large, it's in C++/Pseudo Code. I haven't got it here, but I could post it here if you want.

[edited by - rubenm on June 14, 2002 5:49:03 AM]

A* is a lot like a flood-fill algorithm. Thinking in these terms while you reread the documents at gameai.com may help you. I''ve also summarized the algorithm in response to many A* posts on this forum; if you search for them they should help.

If you''re still stumped in a little while, I''ll post with more detail.

Thanx terranfury.

I''ve implemented my code a little, and the enemy can find the player if the player is 2 pathpoints away, if it''s three pathpoints away, it''ll crash, but I''m still debugging. Going nice.

Still, it might be handy if someone looked at my code, it''s very easy to understand, and it only contains one page (lettersize = 11, much spaces)

Is it alright with the forum rules to post it here?

YES!!!!!!!!!
MY CODE IT WORKS!!!!!!!!!!!!!!!!
AAAARRRGGGHHHH I''VE IMPLEMENTED A*!!!!!!!!!!!!

Why do you say I''m happy??

Anyone wants me to write an article about it?