A* Pathfinding Project

Integration with Easy Character Movement


#1

Hi, I just started to use A* as my procedural world’s pathfinding solution.
I’m using Easy Character Movement (ECM) for my agents. This is a rigidbody based controller, so gravity simulation is not needed in controller scripts.
The ECM asset comes with a Navmesh Agent implementation. And I don’t find Base AI from A* useful for it uses unity’s Character Controller component (I don’t intend to use it).
What I want to do is to write my own implementation between ECM and A*, but don’t know where to start. Any suggestions on which class should I take as reference or which fields should I use during implementing?

Another question: I have agents does not require grounding (like fishes) but has a y position limit in world space, and they should be able to avoid rocks or corals in my under water scene. Is there any solution for them to find a safe path when following to or escaping from locations? Any help can A* provide with these kinds of agents?

Thanks!


#2

Hi

There is a tutorial for how to write your own movement script here: https://arongranberg.com/astar/docs/custom_movement_script.html
However it is rather simple and does not have particularly good movement.
If you want a reference, the AIPath script is the best to use.

You could also subclass the AIPath script and override the FinalizeMovement method as all the code specific for the CharacterController class happens in that method (see AIBase.FinalizePosition more specifically).

Note that the AIPath script supports movement not only using CharacterControllers, but also with rigidbodies or just a raw Transform (using raycasting for grounding).

That sounds like it requires full 3D pathfinding. This is something that this package does not provide (well, technically you can do it with a point graph) because it is so ridiculously memory and CPU heavy so it is not practical in most use cases. Some kind of local avoidance is usually better suited for fishes (take a look at boids for example).


#3

Thanks for the reply! I’ll derive a class from AIPath then override the FinalizeMovement methed and use my own controller to move the characters.

Regard to the fishes pathfinding, I don’t intend to use a true 3D pathfinding method for them, they’ll still search for routes in 2D, but I’ll override the height for them (instead of snapping to ground, I’ll lerp their y position from the start pos to the destination, these character’s destinations will be generated above terrain height).
The issue I’m having here is that I want to restric all fishes under sea level, and make them ignore positions higher than sea level. But still I’ll have ground animals which should ignore positions under sea level. And bird like animals which can walk on ground(using land animal logic and pathfinding) can fly in air (using only local avoidance) and swim on sea surface(they’ll got snapped to sea level but still need to know where a rock is poking through water, need to avoid them).
Just don’t know how can I achieve such complex behaviours with A*. I’m quite new to pathfinding. Any suggestions?

BTW, what does boids mean? Don’t quite understand it.


#4

Hi

Ah, I see. The easiest way to separate them is to simply create two graphs and then set the Seeker settings so that they can only traverse the relevant graph (see https://arongranberg.com/astar/docs/multipleagenttypes.html)
The other approach is to use a script to mark all nodes below sea level with a particular tag (see https://arongranberg.com/astar/docs/tags.php) and then set the Seeker settings so that the agents ignore some tags.

I would recommend a custom movement script for the fishes. Firstly because you will likely have a lot of them (might not be true, but usually there is a lot of fish) so performance is important, and because that would make it easier for you to add your y coordinate adjustment. You could tweak the AIPath script as well if you want though.

Boids: https://en.wikipedia.org/wiki/Boids, https://www.red3d.com/cwr/boids/


#5

I considered to use two graphs, but since I’ll need to update graph in runtime, fear having two of them may cause significant spike. I tried to only update one graph every 10 meter movement with 200*200 nodes, 0.5f node size. I run it on multithreaded high priority(uses 24 threads on my pc) still will cause 10ms spike every time it refreshes the graph. Can’t imagine the cost when updating two graphs.

About marking nodes with tags, is this method faster than using two graphs?


#6

Yes, it is faster. Using two graphs will be approximately twice as slow.

Note that having 24 cores does nothing to improve the performance unfortunately as the physics code (which the grid graph uses) has to be run in the main thread (possibly in the future this could be handled using the Unity job system though).

I’m not sure what you mean by ‘every 10 meter movement’ though. Weren’t your tags static? (just above/below sea level).


#7

By 10 meter movement, its a setting in your sample script in Procedural Example scene that allow me to choose how often the grids to get updated.

If I want to tag nodes according to their world position’s y value in runtime, should I mark them in the grid mover script or just set them up in the settings?