• Advertisement

Archived

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

Natural Looking Pathfinding

This topic is 4974 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
Hi again,

Adjusting the diagonal cost helped a lot with the initial path - I feel really dumb for not thinking of that! The final path looks MUCH better now using the new heuristic and cutting out unnecessary nodes like Mark suggested. I''m also looking into splines to help smooth out the turns.

If anyone else is interested, both of the AI Game Programming Wisdom books have some excellent articles on pathfinding too.

Thanks for all the help and suggestions.

Share this post


Link to post
Share on other sites
It seems to me that the path could be even shorter. If it is not too expensive then you could, when creating your white final path, have the program try moving the points further along the blue line - all the time testing if it still has line of sight. This would shorten your path from node 5 (counting in the start node) on the white path.
Dont know if the other solutions already solved your problem - if so: could you post an image of the new path? Anywho. Just thought I''d post this suggestion.
Now don''t slap me - I have no experience in pathfinding at all

Emil Johansen
- SMMOG AI division
http://smmog.com

Share this post


Link to post
Share on other sites
Ok, firstly, I am aware that there is possibly a bug in my own path optimisation code, it doesn''t always seem to work right (although I believe the principle is sound, which is why I posted the pic)

Secondly, I did originally allow diagonal movement in my A* algorithm, but I realised that it created a lot more work, and resulted in what was basically the same path after optimisation. So I removed the diagonals, hence the "zig-zag" of the blue path. My characters don''t actually use the blue path for walking around anyway.

What I did do, was left in the diagonal rule in the heuristic calculation, which causes it to zig-zag.

Mark

Share this post


Link to post
Share on other sites
It''s not quite that easy because the line-of-sight path may be much more costly than the computed path. For example, the line of sight path may require you to cross rough terrain, while the computed path follows a road.


John Bolton
Page 44 Studios
Current project: NHL Faceoff 2005 PS2

Share this post


Link to post
Share on other sites
I did consider that, I think the line-of-sight can work as long as you''re going across the same sort of ground.

The A* output should provide the least expensive route, then you apply the line-of-sight afterwards. If you only use the line-of-sight across consistent ground, it shouldn''t make the route any more expensive ever.

Mark

Share this post


Link to post
Share on other sites

  • Advertisement