Jump to content
  • Advertisement
Sign in to follow this  
Gf11speed

Dynamic Pathfinding/Pathfollowing

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

I am trying to figure out what is the best method for pathfinding in a dynamic world. For instance, I am developing a horse racing simulation where horses are trying to find the shortest path from their location to the finish line, while at the same time avoiding other horses. Right now I have an A* pathfinding implementation that works ok for the pathfinding part, but it doesn't seem to do well with dynamic obstacle avoidance. I'm not sure exactly where to go from here. Maybe I'm just not implementing it correctly. Is A* ideal for dynamic pathfinding and obstacle avoidance by itself or would I need something other than this? Are there any good (simple!) engines available that would handle this? Could anybody shed some insight on this issue or show me in the right direction? Any help is appreciated. Thanks.

Share this post


Link to post
Share on other sites
Advertisement
This could be cheating, or implausible depending on the requirements of the simulation, but have you thought of mixing your pathfinding with a flocking algorithm, to ensure your horse stays a certain distance away from the others?

Share this post


Link to post
Share on other sites
I believe pathfinding and obstacle avoidance are not the same things. A* is a great method for finding the shortest path ...but you will need a subsystem to deal with dynamic obstacles. As entitydev mentioned a flocking algorithm might be usefull.

Share this post


Link to post
Share on other sites
I see, that is good to know then. So what I am looking for in addition to A* is "obstacle avoidance"?

I'll check out flocking algorithms as well. Anybody know anything else about obstacle avoidance then?

Share this post


Link to post
Share on other sites
just a thought... you could add the other horses and their paths to the A* map as 'unwalkable' nodes and find a path around that towards some arbitrary distance along the track. Compute the time it will take the horse to move along that path and then compare that with the time it would take to decrease speed and follow the horse infront of it the same distance. Now you don't need to do this check each frame/gametick. There are some strategic spots on a track where this could be usefull. Just before the exit of a wide turn is one of these spots for example. Other spots might be meaningless to do this check. In the beginning or middle of a wide turn and your horse is on the outer side (making its turn longer than the horse on the inner side).

You could also ignore other horses infront with higher or equal velocity than the horse you are currently doing pathfinding with.

Now I don't know much about your game ,so this might not be good for you at all ...but hopefully you could work with this

Share this post


Link to post
Share on other sites
I've tried making other horse's unwalkable but that didn't seem to solve the problem. I was updating the walkability regions every frame making horse regions unwalkable and the regions they had come from walkable again. This didn't work though, It produced some funny results (horses trying to take shortcuts and clipping the track railing, horses stopping and going at different parts of the race, etc).

I'm not sure if the flocking algorithm would work either, since it seems as if the speeds of the "herd" is somewhat the same. I have to have different horse speeds and horses overtaking other horses. I'm not sure how this could be done using a flocking algorithm, or perhaps there is something I'm missing.

I don't understand why, if I update every frame, the A* algorithm wouldn't work by itself if I made the other horses 'unwalkable'? Perhaps I could be making a mistake in my code, but I don't see where.

Share this post


Link to post
Share on other sites
Quote:
Original post by Gf11speed
I was updating the walkability regions every frame making horse regions unwalkable and the regions they had come from walkable again.


This was not what I ment ...do your pathfinding without including other horses.
As a part of the subsystem "obstacle avoidance" you could add not only the other horses regions, but also an arbitray number of steps along their path, to the unwalkable list. Then try to aproximate what would be the best for your horse ...trying to run past the horse infront of it, or keep an even pace behind it, waiting for a better opportunity.

Quote:
Original post by Gf11speed
It produced some funny results (horses trying to take shortcuts and clipping the track railing, horses stopping and going at different parts of the race, etc).


Well, clipping the track railing is not an ai problem is it =) ...and as for making horses come to a complete stop. When something is preventing your horse from following its path, you could assume that abstacle is another horse (or are there any other entities running the track?), and as long as that other horse is not injured it should be running. So, instead of making your horse stop, set its speed to the same as its "obstacle". If you move on to another horse sideways then you have three choices (as long as your horse is not armed =p).
1. Just keep running forward side by side with that other horse
2. Increase speed momentarily and run past it.
3. decrease speed to save enery and fall back behind that other horse, and wait for a good oppertunity to run past it.

Share this post


Link to post
Share on other sites
Actually, you can pretty much take out pathfinding all together.

Flocking is one way to put it, but its also known as potential/gradient fields

So basically, all the horses try to go in one general direction. Horse B will exert a repelling force on Horse A which is exponentially proportional to their distance apart. The fences surrounding the track will also exert repelling forces on the horses so they won't get too close to the fence. So, all you need to do is keep track of the motion vector for each horse and each time cycle update it based on attractive force of the direction the horse is trying to go and the repelling forces its getting from all the horses around it and the fences. This way, horses shouldn't really run into each other. To cut down on calcultion, you can just have horses close enough exert repelling forces.

I did this once to create an evacuation simulation and it looked fairly nice and chaotic. You might need to play around with the strength of the forces, but it shouldn't be too hard. Throw in some randomness with direction and speed and you'll get something fairly interesting.

Share this post


Link to post
Share on other sites
I'm in agreement with WeirdoFu. This is a very appropriate domain for a potential field method, because it's highly constrained spatially with simple boundaries.

A few things to consider:

1) To avoid clipping the rail, determine the width of a horse and set a threshold distance of half that width from the inner and outer rail. At that threshold, the repulsive force should be such that it is impossible to move any closer to the railing. This follows into the next point...

2) Given that the inside run is the shortest distance, horses should, in isolation, prefer to run close to the inner rail. Thus, your potential function should have a cross section (across the track) that looks something like:

where
r1 = horse width
r2-r1 = 'safe distance' to run from rail
r3-r2 = horse width
R-r4 = horse width

Now, you can make the horses fun forward by either using an attractive force ahead of the horse or a repulsive force behind the horse. The gradient of the local potential field should be such that the horse moves toward the finishing line. You could actually implement this on a per horse basis as a 'jockey potential function'. That is, a 2D potential directed along the track with a gradient that varies depending on how far from the finish line the horse is. Thus, early on the gradient might be low for a horse that starts slow and builds up toward the end. For a horse that bolts out of the gate, its gradient of its 'jockey potential function' would be initially steep but maybe flatten out later on. Make sense?

There is a lot you could do with this domain based on very simple movement behaviours and individual customisation per horse and per jockey.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
All very interesting. I never thought about anything like that. I wonder if it would be wise to combine the two ideas, perhaps use the pathfinding algorithm in addition to a potential/gradient field. The horses would attempt to follow the best path, but the field from the other horses would propel each horse away from the others and att the same time the pathfinding would not allow it to touch the railings. Wouldn't this seem more realistic than having a field/gradient only, or no?

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.

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!