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

## Recommended Posts

After studying many tutorials on the net I got a pathfinding algorithm to work in my game. But there seems to be one problem ( besides its slow as hell ). As you can see in the image below, it takes a path like an L shape and doesn't zig zag diagonally to the target square like most games I see do. In my game you can only move up down left right no diagonal moves. However it would look a lot better if the guy went down one, then left one then down one then left one to reach the target instead of going waaaaay left and then waaaay down ( if you know what I mean ). What is the best way to do this? The red squares are the "path" nodes that were searched.

##### Share on other sites
your valuing function is probably borked. You also did not specify which algorithm you are using. The movement mechanics make no real difference and most pathfinding algs are really just graph traversal algs.

When you decide which square to move to, you might just try the simplest things and ask "which square gets me closer to the target?" using good ol' A^2 + B^2 = C^2. Although you can save cycles by just comparing the C^2 between nodes tested. There is no need to compute the actual value of C.

if you want actual code, i would recommend this which i have used in the past:

##### Share on other sites
Oh ya, i am using A* BTW.

##### Share on other sites
what are you using for your heuristic? Have print the cost and heuristic values for each square or watch them get calculated in the debugger. Just looking at it I would say you might be doing it right if you consider vertical moves before horizontal and don't consider diagonal moves. If you look at that triangle there are the same number of moves weather you go in straight lines or stair step the diagonal. If you want diagonal paths to be generated allow the A* to make diagonal moves costed out at 1.5 a regular move cost even if you don't allow the character to take the diagonal path.

##### Share on other sites
Stonemetal: He doesn't need to modify his A* implementation to consider diagonal moves.

Chris: It looks as if you are using the Manhattan distance as your heuristic (abs( goalx - nodex ) + abs( goaly - nodey )). This is logically correct in your game because there are no diagonal moves, and thus, as Stonemetal noted, the L shaped path is just as short as a "stair-stepping" path. You get an L shape by default because your A* loop processes neighboring nodes in a fixed order.

Solution:
If you instead use the true distance as your heuristic ( sqrt(( goalx - nodex )^2 + ( goaly - nodey )^2 )), or the true distance squared, your path will approximate a more natural line.

[Edited by - jack_1313 on February 5, 2008 8:19:12 PM]

##### Share on other sites
Are you sorting the openlist as you push new nodes into it?
It could be that your heuristic is correct, but the most efficient node is never used...

##### Share on other sites
Quote:
 Original post by jack_1313Stonemetal: He doesn't need to modify his A* implementation to consider diagonal moves.Solution:If you instead use the true distance as your heuristic ( sqrt(( goalx - nodex )^2 + ( goaly - nodey )^2 )), or the true distance squared, your path will approximate a more natural line.

Nope A* is guarantied to generate the shortest path if there are two equivalent paths then the order of node processing and heuristic will determine which path is followed. straight line distance will come up with the same path since there is no difference between (x distance of 4, a y distance of 3) and (x distance of 3, y distance of 4) a step in either the x or y direction from the current location will produce a distance that is 1 unit closer no matter how you measure distance. considering the diagonal when computing the distance will give you a sqrt(2) distance advantage over moving in a non diagonal direction hence the reason looking in the diagonal direction will generate a stair step pattern, or you could use a heuristic that favors changing direction such as distance/2 for any direction not taken last time(this will make your search space swell as you check wrong moves because of the discount it won't generate the wrong path though).

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 9
• 9
• 11
• 11
• 23
• ### Forum Statistics

• Total Topics
633678
• Total Posts
3013290
×