Jump to content
  • Advertisement
Stocke

Some questions about flow/vector field pathfinding on non RTS games

Recommended Posts

I looked into flow field pathfinding(after reading about steering behaviours) and it seems that it's mostly used for RTS games. I understand why, but wouldn't it also work for an action game with a single player character? It wouldn't be efficient, sure but it makes using steering behaviours easier to use. I could precalculate obstacles based on static colliders in the scene. And I can calculate the a vector towards the player for seek behaviours every frame. And reuse that for every enemy.

I could then use inverse of the vectors for flee behaviours and make that avoid obstacles as well. 

If I wanted to steer a character perpendicular to the player, maybe I could rotate the vector in the field 90 degrees to obtain that? 

Of course this approach would not be valid for other behaviours. Like for pursuit you would need to calculate another vector field for the future position of the player. Unless there is some mathematical way to shift a flow field if the center(where the arrows converge) moves.

I dunno how you would add local avoidance. Maybe keep track of enemy positions on another vector field and take that into consideration.

A* is no doubt efficient and popular. But it does not work well if the agent has target velocities instead of target positions (like from using steering behaviours). And A* also has the problem of being too good(perfect paths => too robotic). 

Anyways, that's enough rambling from me. What do you think?

Share this post


Link to post
Share on other sites
Advertisement

I proposed something like this recently, and did not know it's already used in games and has name :)

Some thoughts:

3 hours ago, Stocke said:

It wouldn't be efficient,

It can be efficient, especially if number of enemies is large.

Personally i use the approach for geometry processing, so on the surface of a triangle mesh, simialr to this: https://www.cs.cmu.edu/~kmcrane/Projects/HeatMethod/ (I have only little experience with game AI)

But for path finding via local maxima search you do not need exact distance, just direction. So only the first equation system of the two from the paper, which is basically a diffusion of energy from the target. So this approach is scalar energy, not a vector. To find a path just look for the highest value in the neighborhood.

The fastest way to calculate this diffusion is backwards euler integration using something like gradient decent solver or better, so not realtime.

But for realtime a simple forward integration step per frame would work. Cost would be constant and only depend on the world size, but it it would take some time until paths onverge to the shortest (could even look nice and give more natural movement maybe).

(... very similar to averaging vectors with their neighbours - i guess that's what you have in mind already, but the scalar vs. vector idea might be new for you.)

3 hours ago, Stocke said:

I dunno how you would add local avoidance. Maybe keep track of enemy positions on another vector field and take that into consideration.

If the goal is enemies avoiding to run into each other, you could build a graph over the enemies, color the vertices, and using a fast apporximate algorithm for this you get maybe 5-6 colors at max. So you would need only 6 fields to support any number of enemies.

The problem would be: Graph colors would change per enemy form one frame to the next, which breaks the field integration from above :(

Not sure if this could be solved somhow acceptably, but maybe it's worth to mention...

 

Share this post


Link to post
Share on other sites
4 hours ago, JoeJ said:

I proposed something like this recently, and did not know it's already used in games and has name :)

Some thoughts:

It can be efficient, especially if number of enemies is large.

Personally i use the approach for geometry processing, so on the surface of a triangle mesh, simialr to this: https://www.cs.cmu.edu/~kmcrane/Projects/HeatMethod/ (I have only little experience with game AI)

But for path finding via local maxima search you do not need exact distance, just direction. So only the first equation system of the two from the paper, which is basically a diffusion of energy from the target. So this approach is scalar energy, not a vector. To find a path just look for the highest value in the neighborhood.

The fastest way to calculate this diffusion is backwards euler integration using something like gradient decent solver or better, so not realtime.

But for realtime a simple forward integration step per frame would work. Cost would be constant and only depend on the world size, but it it would take some time until paths onverge to the shortest (could even look nice and give more natural movement maybe).

(... very similar to averaging vectors with their neighbours - i guess that's what you have in mind already, but the scalar vs. vector idea might be new for you.)

If the goal is enemies avoiding to run into each other, you could build a graph over the enemies, color the vertices, and using a fast apporximate algorithm for this you get maybe 5-6 colors at max. So you would need only 6 fields to support any number of enemies.

The problem would be: Graph colors would change per enemy form one frame to the next, which breaks the field integration from above :(

Not sure if this could be solved somhow acceptably, but maybe it's worth to mention...

 

That bunny model sure is famous. It seems to pop everywhere. In any case, wasn't this covered in a GDC talk about PDEs?

The method I came across didn't mention solving Differential Eqns at all. It simply ran a Djisksta/ BFS on the grid to calculate Distance to goal directly. Then just finds the direction from a tile where the distance from goal decreases. Ultimately, it still gives the gradient of sorts and agents can follow that direction after normalizing the vector.

This was the link:https://simoncoenen.com/downloads/ai_paper.pdf

No doubt it's efficient for an RTS game. But I'm talking about an action game where thre is one target(player) and a small amount of enemies.

There's also an article about using it for particle simulation somewhere.

I didn't think about using graph coloring algos to seperate entities at all before. 

 

Share this post


Link to post
Share on other sites
3 hours ago, Stocke said:

The method I came across didn't mention solving Differential Eqns at all. It simply ran a Djisksta/ BFS on the grid to calculate Distance to goal directly. Then just finds the direction from a tile where the distance from goal decreases. Ultimately, it still gives the gradient of sorts and agents can follow that direction after normalizing the vector.

Sounds exactly what i meant.

On the bunny (or a navigation mesh) it is more difficult becasue you need laplacian calculated from triangle cotangent weights to diffuse the energy (or heat) equally in all directions. Using a regular grid this is trivial i guess (or has acceptable error). But the main reason for their differential equation solver is to calculate the diffusion over any given duration (or distance) in one step, which would be too slow for realtime games.

3 hours ago, Stocke said:

But I'm talking about an action game where thre is one target(player) and a small amount of enemies.

Hard to say what's faster when. I use Dijkstra too on the meshes, but working on a offline tool i can't say much about performance. Only this: If you would switch to navmesh, it is important to have good triangles avoiding small angles and area. Otherwise the cotangent weights become tiny and so the maximum timestep for stable diffusion per frame becomes tiny too. It would be worth to lie about the shape / area of bad triangles to trade accuracy vs. performance.

With small amount of enemies it may be more the options of the flow method that are interesting than performance, like strafing around the target in a circle by rotationg the flow vector as you suggest. Likely target velocity can be handled in a similar way by rotating with angle related to distance, but A* can do this too by predicting the target offset.

So i can not really help, but i see similar potential advantages you have mentioned. Worth to try :)

 

 

Share this post


Link to post
Share on other sites

Okay, so it didn't go as well as I hoped. Seek behavior works right off the bat. But you can't get flee behavior simply by using inverted vectors. Unless you don't care about getting stuck on corners.

LWl6H5P.png

Still, Having easy access to player distance at all times is useful. I could query player distance for each tile and come up with a decent flee behavior by looking at nearby tiles. If that doesn't work then I'd need to have separate flow field arrays for everything and that'd suck.

Edited by Stocke

Share this post


Link to post
Share on other sites

Didn't have time to read all the above responses, but a common use in many types of games is combining pathfinding and steering. With pathfinding, you are figuring your way through a world of fixed objects. Steering helps you avoid dynamic objects that might be in the way. Think about your own life. You know how to get from your desk to the bathroom but you have to adjust along the way when another person or the dog is in your way. The coarse path doesn't change, just your following of it.

Put another way, when traversing a large poly on the navmesh in the middle of the room, A* simply says, "go to the middle of that edge over there". However, if something dynamic is standing directly on your vector to the middle of that edge, you are kind of stuck. Steering at that point kicks in and allows you to slide around these objects while still targeting the middle of that edge on the far side of the poly.

Remember, this isn't an "either/or" situation. Use each tech for their strengths and put them in combination.

Share this post


Link to post
Share on other sites

Hey I read an article in the summer about using flowfields to direct troop movement in RTS games. I was intrigued and had to try it out for myself. Making the flowfield was easy, implementing it not so easy. I made it into a unity asset and had a lot of optimizing to do. I got discouraged when I was lagging at moving 300 units at once, then I did some research on RTS and none of them move that many units at once except supreme commander, so then I introduced and max unit selection of 36 and I'm able to move 10 troops of 36 units with ease! I since made the flowfields more dynamic is would be efficient for a single unit, I have the flowfields spawning, resizing and repositioning dynamically, so the flowfield can be relatively small and operate just where the unit is. My implementation is not for solving mazes and stuff tho.. but basic object avoidance and direction, I'm sure a flowfield could be made to use fro a single unit and be quite efficient, but as others stated another system may be needed as well.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • 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!