Question Using A Star Pathfinding And Having Forces At The Same Time

Hi there, I'm trying to figure out if I can use the A Star Pathfinding system to set paths and targets for AI entities while still using forces to move them and handle collisions.

I'm working on a top down 2D game, so the agents should be able to move on a plane.

Right now I'm using the Seeker, AIPath, and AI Destination Setter scripts to handle the movement. Then I have a script I made which basically just finds target and then calls

SearchPath()

in the

IAstarAI

class.

This moves the agents really well, but the issue I'm having is that even though the agents have colliders and rigidbody 2Ds, they just move overtop each other and end up overlapping.

I don't need them to avoid each other, I just don't want them to overlap, I want them to bump into each other and be able to move one another with forces.

I imagine what I need to do to get this to work would be using Unity's force system to move them, but I'm not sure how to do that alongside using the actually pathfinding methods from A Star.

So I guess what I want is to find the path the agent wants to take using A Star, and then move along that path using something like

rb.AddForce()

.

Any help with this would be really appreciated!

 

Of course you can, the pathfinding is for "where to go", the controller is for the actual movement, you can get the move direction from any source.

One problem I encountered with this type of stuff is if the controller is all over the place (strays too far from the path) it can get stuck on stuff (a good example is the AI in prison architect).
Depending on your world and AI this may or may not be a problem.


as for the how, you basically just go in the direction of something like this

Code (CSharp):

1. (path[current].position - path[current+1].position).normalized * speed * deltaTime * etc * etc * etc

You'll need to do an edge case for either the start or the end, I prefer to do it on the end path where you have some kind of arrive behavior.

 

Hey thanks for the fast reply, glad to know what I'm trying to do isn't something too crazy.

The problem you described; am I to understand that what you're saying is the ai has issues when pushed too far from their set path? Could you just update and calculate a new path?

 

This might be a great start to getting this going. But you could also still do it with driving the position directly.

Keep in mind, you do NOT want to set

transform.position

when moving Rigidbody objects.

The reason: doing so bypasses the physics so they won't bump, but they might glitch and jitter badly.

When moving rigidbodies, always use the .MovePosition() method on the rigidbody.

This informs the physics system of your intent to move, and lets it resolve collisions, such as bumping other agents or obstacles.

 

Yep.

You can recalculate the path whenever you want... just knowing that said recalculation takes cpu power.

This may often times be necessary since a map might change (doors open/close for instance) which alter the map.

Usually what I do is recalculate anytime something changes. Say a path gets blocked/open, I trigger an event that tells all AI agents to recalculate (you can even make some agents ignore it if they're too far away simulating that they are unaware of the change). This also goes for a retrigger if the agent gets too far off track.

You can get very creative with it. A* supports weights on nodes to make them more/less favorable. You could create a localized graph for an agent so that it is well aware of its local area but generalized in the far away areas. And other stuff.

 

Thanks for all the responses, trying it out and so far it's looking promising but I'm running into the following issue:



The path seems to calculate correctly around obstacles, but when I'm pushing the agent with a force, it get's stuck on all the other colliders it gets close to in the scene.

Here is the code I'm using for movement:

Code (CSharp):

1. Vector2 direction = ((Vector2)path.vectorPath[currentWaypoint] - rb.position).normalized;
2.  
3. Vector2 force = direction * speed * Time.deltaTime;
4.  
5. rb.AddForce(force);

I guess the force is being added in the right direction but since there's a collider in the way it's pushing against something immovable.

It might be worth noting that I wasn't having this issue when just using the A Star methods such as

SearchPath()

.

Any thoughts on this? Maybe my force direction needs to be more precise somehow?

 

I'm using Aron Granberg's A* project for pathfinding but I move my units using Steering Behaviors. (https://gamedevelopment.tutsplus.com/series/understanding-steering-behaviors--gamedev-12732)

Basically what I do when I want to move a unit is I raycast to determine if there are any obstacles in the way (static obstacles like buildings) or if the destination point is above some distance threshold.

When I move my units it's simply a matter of Seeking the next waypoint on the path + whatever steering behavior I want, usually separation and local avoidance. When the unit is within a certain distance of the path waypoint it then seeks the next position in the path until it reaches the end.

If a unit strays too far from the path then I recalculate it. This works fine for most cases but I run into some issues where units get stuck. One of the things on my roadmap is to add an ability for units to push others out of the way.

I'm not using physics I'm calculating the forces myself.

Example here:

 

@ensiferum888

Thanks for the reply, I'll have to look more into this!

So I did some more testing and it seems like what my current issue boils down to is the path chosen for the agent is not wide enough to account for the agent's collider.

Not sure what the best way to resolve this is. I thought that in the AIPath script of the A Star Pathfinding Project the Radius was supposed to do that but it doesn't seem to be working for me so maybe I'm wrong.

Any tips on solving this issue?

 

The AStar stuff is just a graph saying "you can or cannot go from here to here" and let me tell you how to get there.

It knows nothing about radii.

If you prepared that graph and considered the radii, it might be that there is a bug in that code and the radius was mis-considered and a link was created in the graph that isn't really possible.

 

Fair enough, just to be clear though, I'm talking about this: https://assetstore.unity.com/packages/tools/ai/a-pathfinding-project-pro-87744

Not just a generic A* implementation. I could have sworn this had something along the lines of what you see in Unity's Navmesh system where you can set the space an agent occupies in the Navmesh (or A* grid in this case).

I could be wrong for sure, but I'm thinking there has to be some way to increase the sort of turning space or the buffer between agents and obstacles.

 

I imagine it would take about 60 seconds to prove if that radius stuff works or not with a simple test scene and a given agent.

 

This is a few months old, but in the Pathfinder component, you need to set Erosion Iterations to 1, and this will add a a buffer around your objects/obstacles.

To make this buffer fairly small, you should increase the number of cells in your grid, say a quarter of your tilemap size and likewise decrease the node size to compensate. So my cell size is usually 2.56, so if I multiply my width and depth nodes by 4 (so a 10 x 10 Tilemap because 40 x 40 width and depth), then my node size becomes 0.64.

This works for well for handling fairly small objects in your scene too, if you put them on a layer that you add to Pathfinder's Obstacle Layer Mask selection, though you might have to manoeuvre their positions slightly to make sure they are sufficiently inside a grid to get caught in the scan.

One other thing you can do is add a 'slippery' physics material to your sprites (friction = 0, bounce = 0). That will make your character sprite slide of colliders better.