Hi, As the title says, I am currently reading up on implementing A* path finding, in a non-tile based world, using points of visibility but right now I am struggling with the concept of rejecting nodes in this situation. I should point out that there are no external weightings such as varying terrain, or avoidance/acceptance of certain areas, this is mearly a shortest-route search. An obvious (and possibly a noob) choice would be rejecting/accepting nodes by distance. I''ve made lots of sketches to try and determine the outcome of the searches with randomly placed objects, and it''s obvious that in a lot of circumstances some nodes that were previously rejected in favour of closer ones, will eventually form part of the final path. Apart from evaluating several layers deep before rejecting ANY nodes, what other options are there? Thanks in advance, Matt Main site | Free source | Email

If you prune the tree (reject nodes) before you have finished evaluating the path, then you are no longer guaranteed to find a solution no matter what the environment is. This applies equally to the textbook 2d tile-based RTS game as it does to your nonuniform 3D world.

Thanks TerranFury. That seems contrary to my initial understanding of the use of A* so I guess I''ll go and read some more

- Matt


Main site | Free source | Email

If you''re using A* then you shouldn''t have to reject nodes explicitly, it will be done implicitly by the A* search.

Thanks AP, I was starting to wonder about that. These two replies have helped a lot my brain gets fuzzled after too much reading while I have some basic concept unanswered, and then I tend to try and read looking for an answer, instead of listening to what I''m reading does that make sense? No, ok, just me then!

Cheers!

Matt

quote:

---

Original post by 3dModelMan
Thanks AP, I was starting to wonder about that. These two replies have helped a lot my brain gets fuzzled after too much reading while I have some basic concept unanswered, and then I tend to try and read looking for an answer, instead of listening to what I''m reading does that make sense? No, ok, just me then!

---

I do exactly the same thing. I end up reading lots of different materials. Then I move onto other things; then I come back to the first subject (often with a new perspective because of unrelated papers), reread what''s there, find new information, and then understand it a little bit better. It''s kind of like downloading a progressive JPEG - I don''t get one line, then the next, then the next; instead I get get the whole blurry image, and it slowly gets clearer.

Perhaps this little summary will help you with A*:

- You start with just the beginning node in the OPEN list. Then, you start the algorithm:

- If the first item in the OPEN list is the destination, trace back through that node''s parents to get the path and you''re done.
OTHERWISE
- Remove that first item from the OPEN list, add it to the CLOSED list, and add its neighbors to the OPEN list. Insert into the OPEN list using an insertion sort based on that node''s cost(+the cost of its parent) - so the nodes that you expect to be cheapest end up being evaluated first.
- Repeat

That''s it!

Thanks again!

I think I almost have this, but I have some issues to think through (or the algorithm is not as optimal as I thought).

When does a route terminate? As far as I can see, it is either; a) when it reaches the destination, or b) when all it''s neighbours are on the CLOSED list. Now I''m dealing with a lot of P.O.V. here, and this leaves me open to scrutinisng the whole set, assuming they are all possibly (discreetly) inter-connected.

Here''s another circumstance I''m uncomfortable with.. Supposing one route eventually reaches a particular node and opens it, (assigning it''s f value), but later in the search another route reaches the same node - but could have done so with a lesser f value. Obviously the algo will never detect this if the OPEN/CLOSED lists are correctly implemented, but is there anything that can or should be done in this case? I could store this information, thus encoding "the quickest route back to the root node from this node", if "this node" eventually forms part of the solution then so will the shortest route.

I appreciate that A* is attempting to avoid this situation with the heuristic weighting, but I can''t conceive a heuristic that would satifactorily navigate concave arrangments of obstacles, leaving brute force as the only option.

Thankyou to anyone that takes the time read this, and even better, post a reply!

Cheers

Matt


Main site | Free source | Email

The router terminates when either the target is found or the open list is empty.

I recently developed an A* demo in a language called Blitz Basic. If you are interested, you can find it at a site called Blitz Coder in the showcase section under Functions, but it requires use of the free Blitz Basic language/program.

http://www.blitzbasic.com/
http://www.blitzcoder.com/

Assuming you use some other language, I recommend Bryan Stout''s article and demo program found at

http://www.gamasutra.com/features/19970801/pathfinding.htm



Patrick Lester - Blitz Basic User
Compaq Laptop
AMD-K6(tm)-2/ at 350 MHz : Memory 160 Megabytes
Video = ATI RAGE LT PRO AGP Graphics Controller

quote:

---

Original post by 3dModelMan
When does a route terminate?

---

A* guarantees that it returns the lowest cost path before returning any other path, so long as that path exists! If it doesn't, then it will exhaust the search tree (empty the OPEN list) and hence end. There's another way to think about it... and I'll explain that below.

quote:

---

Original post by 3dModelMan
Here's another circumstance I'm uncomfortable with.. Supposing one route eventually reaches a particular node and opens it, (assigning it's f value), but later in the search another route reaches the same node - but could have done so with a lesser f value. Obviously the algo will never detect this if the OPEN/CLOSED lists are correctly implemented, but is there anything that can or should be done in this case?

---

Actually, if you correctly implement the algorithm, you should be checking for this. Any time you expand a node to generate leaf nodes in the tree, you must check to see if these nodes already exist in BOTH the OPEN list AND the CLOSED list. This is checking for loops in the search tree. If you find such a situation, then you need to check which path to the node has the lowest cost and set the parent of the node accordingly. That way, when you trace your way back up the tree, you'll follow the lower cost path back to the start node.

quote:

---

Original post by 3dModelMan
I appreciate that A* is attempting to avoid this situation with the heuristic weighting, but I can't conceive a heuristic that would satifactorily navigate concave arrangments of obstacles, leaving brute force as the only option.

---

As I said above, A* WILL return the lowest cost path if there is at least one path from the start to the goal.

There is a better way to visualise what A* does rather than thinking of an open and a closed list of nodes. Read this and consider it carefully...

A* guarantees to expand all nodes within a given contour of the cost space BEFORE considering any nodes in the next highest contour.

Remember that we require an admissable heuristic for A*. We require that the heuristic underestimate the actual cost to get from a node to the goal. We ALSO require that the cost function be monotonically increasing. Taken together, these two constraints mean that as we expand nodes out from the start node, then 1) the cost of each node increases (or at least doesnt decrease) with distance from the start; and, 2) that the estimate of that cost will never be greater than the actual cost of a path through that node to the goal. Since we choose to expand the lowest estimated cost path first, then every iteration, the level of cost considered increases. The algorithm therefore MUST - if it finds a path to the goal - have found the lowest cost path. This can be proven mathematically, but I'll spare you the grim details!

Cheers,

Timkin



[edited by - Timkin on April 15, 2002 1:12:08 AM]

Thanks again everyone. I''m sure I have enough of a grip on this subject now to actually begin coding so I''ll keep you informed of the results, and I''ll be back if I have any more queries

I''ve been visiting GD for quite a while now, but this is my first proper venture into this forum and I''m impressed by the depth of knowledge available here.

In case you were wondering, this is the game I''m currently working on and I''ve decided to add some enemy bots that track down the player.

Cheers all!

Matt


Main site | Free source | Email