Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Blackheart

Natural Looking Pathfinding

This topic is 5153 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

Not sure if I should have posted this here or in the AI forum, but anyway on to the problem! I''m working on a 2D, 4 player RPG and just yesterday I implemented a version of A* for pathfinding. After the initial "woah...it actually works" excitement wore off, I noticed the paths it produced didn''t look all that natural. I think it''s because of the way my search space is setup; it''s just a rectangular grid where units can only move in 8 directions (horizontally, vertically, and diagonally). What I''d really like to have is a way for units to move in any direction to reach goals and intermediate nodes along the path, but I''m not sure how to setup the search space to allow that. I''ve looked at other games like Diablo and Baldur''s Gate, and they don''t seem to suffer from the same problem, so there must be another way! Anyone have any ideas or suggestions? Do you think A* might not be the right algorithm for my problem?

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
It could be possible to put only some points around the blocking objects and the actual target point into the search space.

That way, you would walk a direct line, or, if that is blocked, a tight line around the blocking objects.

Never implemented it, though ;-)

Share this post


Link to post
Share on other sites
Use different "cost" modifiers to the various pieces of terrain (nodes) etc, so that a character will follow a road if there´s any - since the cost for roads are less than mud etc...

Then add modifiers if the character is walking downhill or uphill... obviously a character would want to walk a less steep path if it''s available etc...

Try to think what a human would do, and analyse - break it down into tiny bits and then incorporate this into your programming. =)

Share this post


Link to post
Share on other sites
I''ve done exactly that.

What I''ve done, is find the path using an A* algorithm, then remove steps which are adjacent and have line of sight, so that I only have remaining waypoints which are around obstructions.

So for example, if a character walks into a room through one door, and there is another diagonally opposite (but not exactly diagonal), he should walk in a straight line towards the opposite door and go through.

It''s sort of difficult to explain. See the picture below. The blue path is the original A* path, and the white the "optimised" path.



Mark

Share this post


Link to post
Share on other sites
Thanks Mark! That''s exactly what I was looking for, your blue A* path looks the way my paths look now, and your white path is how I want them to look. Ironically, I already have the line of sight information available for another part of the monster AI too.

Now to try my hand at implementing it.

Thanks again!

Share this post


Link to post
Share on other sites
Another suggestion is after doing line of site, you can create splines to move around the object using the remaining waypoints, so that the characters move smoothly rather than always turning at sharp angles.

Share this post


Link to post
Share on other sites
quote:
Original post by kevmo
Another suggestion is after doing line of site, you can create splines to move around the object using the remaining waypoints, so that the characters move smoothly rather than always turning at sharp angles.


Yep.

Share this post


Link to post
Share on other sites
Given your situation, A* should not generate rigid paths like the blue line in the diagram provided anyhow. It seems you are searching in four directions when you tilemap provides eight. If you are searching eight ways, be sure that your diagonal cost is around 1.4 times the cost of vertical or horizontal movement (seems that you may have set diagonal cost to double that of normal). Obviously A* should regard the direct diagonally from one cell to another as lower costing than moving a sum of two cells to achieve the same destination.

Share this post


Link to post
Share on other sites
You could also use path refinement. What you do is get your basic path down, then pick a few points along that path and re-find the path from A->B, then B->C, and so on, then splice them all back together. You''ll find the path looks a bit "smarter" although it''s not trivial to do.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!