When A star fails

Smjert · 2009-03-06T03:16:23

Here's a situation where A star fails (sorry for the horrible image xD): The black line is an obstacle. Lets call A the starting node, B the bestnode among the expanded nodes and C the real bestnode (better F cost value than A). What i thought is to expand the adiacent nodes of A and to make B the node with the best F cost value among the other, even if it's not better than A value. Do this until you find a C node, from there use A* algorithm with C as the starting point. The only thing is that i think it will create a path like this (the blue one): There's a way to make it look as the green one? Also if you imagine a narrower "exit".. the blue paths could be very long. I add that i'm using A* in a tile based game and the algorithm don't know how is the map, where's the obstacle etc etc, it's all calculated at runtime.

Artificial Intelligence Programming

Started by Smjert February 21, 2009 03:19 PM

20 comments, last by Trandafira 15 years, 8 months ago

mfawcett

374

February 26, 2009 12:54 PM

Quote: Original post by Codeka
Quote: Original post by Smjert
I call the F, G and H because these are their names.
If you read articles (standford, polymaniac (or something like that) wikipedia.. also university if i remember well :P).

Yeah, I know, that's what I meant [smile]. It seems to be a common thing with academics to name variables with a single letter...

Well, they have a perfectly good reason here...

f = final
g = given
h = heuristic

f = g + h

--Michael Fawcett