Jump to content
  • Advertisement
Sign in to follow this  
Chris_6713

Need advice with pathfinding

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

If you intended to correct an error in the post then please contact us.

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? Photobucket The red squares are the "path" nodes that were searched.

Share this post


Link to post
Share on other sites
Advertisement
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:

http://www.geocities.com/jheyesjones/astardownloads.html

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by jack_1313
Stonemetal: 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).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!