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?

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

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. 

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

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.

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.

Any-angle pathfinders for less robotic pathfinding (I can provide implementation of Lazy Theta* if you want):
https://en.wikipedia.org/wiki/Theta*
or
influence maps/potential fields (may not have local extrema issue) with steering behaviours.

For more details please see:
https://www.hindawi.com/journals/ijcgt/2018/5184605/
https://ieeexplore.ieee.org/document/8812974
 

On 11/8/2019 at 7:40 PM, IADaveMark said:

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.

I discovered Steering behaviors after messing with pathfinding. I haven't tried combining the two actually. I could use pathfollowing behavior once I get a path from Pathfinding Algos and combine with nearby enemy repulsion behaviour to get some nice effects. But it's hard to get decent fleeing behaviour from pathfinding. My game doesn't have any cover points that I can use as target points for flee pathfinding. I just want the fleeing enemy to move away and not get stuck on obstacles. Normal obstacle avoidance behavior works to an extent but it is still possible to get stuck when combining the steering forces.

On 11/11/2019 at 6:01 PM, GNPA said:

Any-angle pathfinders for less robotic pathfinding (I can provide implementation of Lazy Theta* if you want):
https://en.wikipedia.org/wiki/Theta*
or
influence maps/potential fields (may not have local extrema issue) with steering behaviours.

For more details please see:
https://www.hindawi.com/journals/ijcgt/2018/5184605/
https://ieeexplore.ieee.org/document/8812974
 

 

 Don't have an IEEE account so I can't read that link. I did read through the other one. It's pretty similar to what I'm doing but I don't use a gaussian function for the values in the potential field. I didn't think about using the potential field for pathfinding costs.  Since I don't really have multiple goal points I can just use the flow field itself for pathfinding. 

On 11/20/2019 at 8:03 AM, logicandchaos said:

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.

I never actually tried having 300 moving gameobjects in unity so I ca't speak about performance. I don't think the number of agents should matter much(out side of the load of having 300 gameobjects in a scene) if the all use the same flowfield. It may be due to how you are evaluating the move direction. Or

Anyways, I'm sorry for the late replies. I was kinda busy with studies and couldn't work on the code. I did realize that the fleeing behavior in the flow field can be improved by choosing the highest distance tile instead of inverting the direction towards the target. That way I could avoid moving into an obstacle. But it would still be possible to get stuck in a corner that has walls on 3 sides.

 I happened to do some digging around the internet. it seems that lots of people have used flow maps/influence maps in different times in different names. I found a roguebasin article that talks about the AI in Brogue and it also uses influence/flow maps but calls them Djikstra maps.

http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps

It outlines an interesting approach to flee behavior by taking the original flow field/djikstra map , multiplying the distances by -1.2 and rerunning djikstra to calculate the distance again. I was kind of amazed to see fleeing enemies in Roguelikes steer out of corners when the player got close and this might be how it was done. I'll try implementing this to see how it goes.