🔒 Locked

Natural Looking Pathfinding

Started by Blackheart Jun 10, 2004 at 3:43 PM 13 replies 2.2k views

Original Post

Jun 10, 2004 at 3:43 PM

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?

Rasmadrak

Jun 10, 2004 at 4:32 PM

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. =)

markr

159

markr

Jun 10, 2004 at 5:00 PM

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

Blackheart

Author

Blackheart

Jun 10, 2004 at 5:32 PM

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!

kevmo

Jun 10, 2004 at 5:39 PM

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.

ChronosVagari

Jun 10, 2004 at 7:14 PM

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.

jacksaccountongamedev

186

jacksaccountongamedev

Jun 10, 2004 at 9:37 PM

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.

leiavoia

129

leiavoia

Jun 10, 2004 at 10:13 PM

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.

Zipster

511

Zipster

Jun 10, 2004 at 11:31 PM

I agree with jack_1313. It sounds as though you simply need to adjust your heuristic a bit.

Blackheart

Author

Blackheart

Jun 11, 2004 at 1:22 AM

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.

emileej

Jun 11, 2004 at 8:08 AM

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

markr

159

markr

Jun 11, 2004 at 1:36 PM

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

JohnBolton

132

JohnBolton

Jun 11, 2004 at 6:39 PM

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

markr

159

markr

Jun 12, 2004 at 4:16 AM

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

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.