.................think better! i just downloaded the src from Amit's game programming site and found it a little irritating. well it finds its path at any situation,but..... boy it sure sucks up on intelligence! I just create a "V" shaped obstacle where the entrance is blocked at the left side. it traces the boundary completely (on the inner side of the "V" too) run it and find out.if there is any ambiguity present,just let me know,i'll put a pic. is it something to do with the Heuristic? Edited by - Raptor on 7/26/00 1:53:18 PM

My guess is that you are not using a higher cost for diagonal movement. If you don''t then the path returned is perfectly legal.

The cost for moving diagonally should be sqrt(2) times the normal cost.

Anyway, I''m moving this thread out of the DX/OGL/Glide... forum as it doesn''t belong there.

- WitchLord

I think it''s the heuristic. Depending on the flavor of A*you are using, the cost estimation doesn''t take into account REAL distance, but rather the maximum between horizontal/vertical cost. I am sure if you had the costs appearing on the map, you would see that straight line costs as much as diagonals.

I''ll try to find a link I have where they show different heuristics. The differences are blindlingly obvious.

But Amit Patel is still the best source I know of on the Net for this topic

youpla :-P

It looks like your lookahead is too short. It can''t see that the path switches back far enough ahead. If you increase the lookahead, the algorithm becomes slower, but you''ll get the horizontal cut (that is about 2 squares from the bottom of the V) much higher in the V.

Making the diagonal more expensive is accurate, but shouldn''t change the resulting path. If you make it too expensive (2x+), you''ll get stairstepping, which is not an ideal path, but (sqrt(2)x) shouldn''t change this path.


Pax

Actually, increasing the cost for diagonal moves will change the path. As it is now the path could zig-zag as much as it wants without costing more.

*------*

has the same cost as

*      * \    /  \  /    \/

because it has the same amount of steps



- WitchLord

thnx all u guys!

well i tried something else -
I used the distance formula as the heuristic.
d = sqrt(dx^2 + dy^2)
even this gives the same result!
as far as i see it , the diagonal is also taken into consideration.why is it that this is wrong?

the pathdemo i have downloaded from one of Gamasutra''s articles does not fall for this.(from oct96.zip->pathdemo.zip->pathdemo.exe)

has anyone else tried running Amit''s Spath demo under this circumstance?


The only way around it is Through it!!

quote: Original post by Raptor

the pathdemo i have downloaded from one of Gamasutra''s articles does not fall for this.(from oct96.zip->pathdemo.zip->pathdemo.exe)

Doesn''t this suggest to you, that you may have some problem in your implementation of Astar? After all, if Bryan''s Astar in the pathdemo.exe solves it (and I know Bryan''s Astar is correctly implemented because I''ve seen his code) then it could be?

I would suggest making sure you have actually implemented Astar correctly too.

Eric

I think you (Raptor) already understand what your error is from our talk in ICQ, but for the rest of the guys here I''ll say this.

The heuristic formula will not change the returned path (unless it overestimates the cost left to the goal, in which case the returned path is not the optimal one). The only thing the heuristic formula affects is the speed of the search, the better the heuristic is at estimating the cost the faster the search will be.

In your screenshot above the path drawn is actually one of many optimal paths, for your implementation. This because you don''t penalize the search algorithm for moving diagonally. If you increase the cost for moving diagonally to sqrt(2) as it should be then you will see a much more logical path.

- WitchLord

WitchLord - Domination!!

well WL,u were perfect!as usual
i increased the heuristic for diagonals and i got it working!
u sure r coooooool WL!

for those of u who want the corrected code which was downloaded from Amit''s page u can catch it here

Thanks again to all of u!
-Raptor