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

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.

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?

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:

you just doing wrong when implement the algorithm.

according to A*, f = g+h, where f = decision function, g = cost, h = heuristic function.
your h function is right
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"

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!

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 ?

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.