I don't have much experience with A* and I have some problems. The AI ship is the top one, target is bottom ship. The first image shows the path, denoted by the green squares, my implementation of A* found, it doesn't seem to be the shortest path, not by a long shot. The second one shows a situation where instead of trying to go all the way around the obstacle the A* search simply goes straight down and gets stuck. Problems My current implementation of A* is quite simple so I guess I must be missing stuff. -Find the triangle containing the ship. -Check the triangle's unconstrained edges(Nodes are the edges). -Gcost = distance from current node/edge to target node/edge. -Hcost = distance from current node/edge to target. -Fcost = Gcost + Hcost. -Set our current node/edge to the one with the lowest cost. -Add previous triangle to a closed list to not check again. -Repeat until triangle containing target is added to closed list or all available edges are either constrained or in the closed list.

for each new node you must also check if it is already on the openlist. You must update the cost and resort the openlist if that node is present in the openlist already.

Try looping the astar-progress one cycle at a time and see what the function does, since it is probably not doing what you think it is?


pseudo:

openlist.insert(first node)

while (!openlist.empty() )
{
sort openlist
current = cheapest node from openlist.

for each neighbour of current
{
calculate cost from each neigbour node to target
node.from = current

is it on openlist?
recalculate cost
else
insert into openlist.
}

done with this node (insert into closed list)
}


get path:

node = target
while (node != start)
{
path.insert(node.from)
node = node.from
}




You get the point.. :)

Quote: Original post by Antonym
-Gcost = distance from current node/edge to target node/edge.
-Hcost = distance from current node/edge to target.
-Fcost = Gcost + Hcost.

In A* Gcost != Hcost.
Gcost should be sum of costs to reach current location.(Note this should be the lowest cost to reach the current node)
Hcost should be distance to goal.

Exactly, G would be :

neighbour.G = current.G + distance(current,neighbour);