A* problem with heuristic

This topic is 2101 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Well met!

I managed to fix the performaceproblem regarding my A*-implementation, thanks to you guys!

However, that made a new problem appear. When I use a heuristic value for my pathing, it becomes incorrect while skipping it returns the correct path but of corse takes a longer time (WAY longer on larger maps).

Illustration (left one is using heuristic):

The heuristic is computed like this:

hCost = 10*(abs(checkingNode->pos.x - goal->pos.x) + abs(checkingNode->pos.y - goal->pos.y))
finalCost = hCost + gCost;
// with 10 beeing the G-cost for moving one square (in only left/right/top/bot direction), and 14 for diagonal


The next sqaure to be put on my openlist is the one with the lowest cost, of corse. I can see why this is happening, but I can't think of a way to fix this. The tutorials I checked all where using this exact heuristic.

If you can help me out here again, I'd greatly appreciate it!

Greetings

-gnomgrol

Share on other sites

Just a guess, but your heuristic function doesn't take into account the reduced cost of diagonal movement. From this page:

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

• If h(n) is sometimes greater than the cost of moving from n to the goal, then A* is not guaranteed to find a shortest path, but it can run faster.

Consider the case where you move from (0, 0) to (1, 2). Your heuristic will return (10 * (1 + 2)), or 30. But your cost of moving there will be 10 + 14, or 24.

How about trying a heuristic that uses the euclidean distance between the two points? e.g. something like:

10*(sqrt((checkingNode->pos.x - goal->pos.x) ^2 + (checkingNode->pos.y - goal->pos.y) ^2))

Edited by phil_t

Share on other sites

You're only looking at the distance to the goal, and not the distance that it would take to get to the current node.

you could have something like:

heuristic = lengthGoalToCurrentNode + lengthOfCurrentPath

EDIT: Silly me, you have costs already, so it should be:

heuristic = cost to get to current node + (estimated) cost to get to goal

ie your gCost should be the total cost to get to that square, not just the cost to move a single square.

Edited by ferrous

Share on other sites

You were absolutely right! Using euclidean distance fixed it.

The downsite of it is, that the computation now takes over 20 seconds on a 512 * 512 map.

Do you have something on the top of your mind to make it faster?

Share on other sites

Perhaps you want to use the diagonal movement heuristic (Chebyshev distance) from that same page.  That way you won't have to compute the square root as in Euclidean heuristic.

You may also want to look at the way you are representing your open and closed sets.  Using better data structures can help a lot.  Your open set wants to be some kind of a priority queue, which would classically be a binary heap, while the closed set is a good fit for something like a hashset.

Share on other sites

100% right. Avoiding the sqrt() was what had to be done.

EDIT: OK, I was wrong. The speed is fine now, but the path doesn't appear to be the shortest anymore. I used


int h;
int dx = abs(currentNode->pos.x - goal->pos.x);
int dy = abs(currentNode->pos.y - goal->pos.y);
h = 10 * (dx + dy) + (14 - 2 * 10) * min(dx, dy);


and it looks like this:

Edited by gnomgrol

Share on other sites

you just doing wrong when implement the algorithm.

according to A*, f = g+h, where f = decision function, g = cost, h = heuristic function.
but your g function, i think something wrong here.

take a look at that example

Start = 0-0 goal = 4,0

[attachment=19410:1.png]

Go to 1-0

1-0 has neighbor 1-1, 0-1

Update 1-1, G(1,1) = min(G(1,1), G(1,0) + 1) = 1.4

Update 0-1, G(0,1) = min(G(0,1),G(1,0) + 1.4) = 1

[attachment=19411:2.png]

Go to 0-1

0-1  has neighbor 1-1, 0-2, 1-2

Update 1-1, G(1,1) = min(G(1,1),G(0,1)+ 1) = 1.4

Update 0-2, G(0,2) = min(G(0,2),G(0,1)+1) = 2

Update 1-2, G(1,2) = min(G(1,2), G(0,1)+1.4) = 2.4

[attachment=19412:3.png]

Go to 1,1

1-1 has 3 neighbor 0-2, 1-2, 2-2

Update 0-2, G(0,2) = min(G(0,2),G(1,1)+1.4) = 2

Update 1-2, G(1,2) = 2.4

G(2,2) = 2.8

[attachment=19413:4.png]

Go to 2,2

G(3,1) = 4.2; G(3,3) = 4.2; G(2,3) = 3.8;G(1,3) = 4.2;

[attachment=19414:5.png]

Go to 1,3

G(3,0) = 5.2; G(4,0) = 5.6; G(4,1) = 5.2; G(4,2) = 5.6

[attachment=19415:6.png]

Go to 4,0 => finish

Trace path 4-0, 1-3, 2-2,1-1,0-0

p/s: sorry, no step "Go to 0-1"

Edited by ngoaho91

Share on other sites

Thanks, that was finally it! I had used 10 and 14 flat for Gcost, instead of using the parents + 10 or 14.

Works perfectly now, much love to you guys for helping me out!

Share on other sites

512x512 is quite large for A*. If u cant reach it, u will search all map! (nearly 500x500 node to be processed)

And it will be too slow. What is your test result (milisecond)  in unReachable case ?

Edited by greenpig83

Share on other sites

I didn't think of that, you are right. It takes about 10 secs for worst-case-no-path on a 512*512 map. Much too slow, obviously.

So, I somehow need to make the maps that needs to be computed smaller. First thing I would think of is subdividing the map in like 16*16 chunks.

But I have no clue on how to implement that with A*.

I would need to have information if one chunk can be accessed from his neighbours or something like that ... but I can't think of a way to make that work properly :(

Do you know any articles on that question? I couldn't find anything with googleing over an hour now.

• Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 13
• 18
• 15
• 10
• 9