Hey Ph0t0n
Did you manage to get the A star pathfinding working on and entity?
Is so would you give and example of how you changed the A* to work with Entitys?
Regards
Well… yes and no. The only changes to APFP are what I wrote about in my previous post, which allows it to calculate paths in threads other than the main thread. Although I would love to use more of the APFP with ECS, I was not able to get any of the AI classes working (AIPath, RichAI, AILerp, etc). I think if one had enough time, he/she could rewrite those classes to be burst/ECS compatible.
The only part of A*PFP I’m using is the static method for calculating a path. So in my “SpawnSystem”, I spawn enemies and give them a path. Each enemy entity stores their own path in a PathData component that contains a FixedList4096. The spawner calls this function:
// calculates a path and copies it from A*PFP's vectorPath to a FixedList4096
protected static void MakePath(ref FixedList4096<float3> destPath, float3 spawnerPos, float3 destPos)
{
ABPath path = null;
path = ABPath.Construct(spawnerPos, destPos);
AstarPath.StartPath(path);
path.BlockUntilCalculated();
for (int i = 0; i < path.vectorPath.Count; i++) { destPath.Add(path.vectorPath[i]); }
}
This will break if paths have more than 340 points (because of FixedList4096). You could use a DynamicBuffer if your map is huge and you need more points, but the fixed list method is super easy to use.
Then, I have a PathMovementSystem that queries for any entities with a path and uses a movement script very similar to the one Aaron talked about here: https://arongranberg.com/astar/docs/custom_movement_script.html , except instead of using CharacterController, it just sets the rotation and translation component values (example: position.Value += velocity * deltaTime; rotation.Value = lookRotation; ) It’s kinda crappy compared to AIPath or RichAI, but it runs really fast with Burst and for my simple purposes it does the trick.
If you need entities to repath because something blocks their path, then you can call MakePath() again. I don’t have it implemented yet, but when I have some time, I’m hoping to find a way to query the grid/navmesh and determine which enemy paths were affected by the obstacle so that paths only need to be recalculated for affected enemies instead of all enemies. I don’t know if that’s even possible though. If you have moving targets that the enemies are heading towards, you’ll need to periodically recalculate paths for each enemy (in my case the targets are fixed so I don’t need to do that).
Maybe in the future when I have some spare time I’ll look into getting RVO local avoidance working with ECS… I think some other people may have gotten it working. Currently I’m using unity.physics for local avoidance, but I suspect it’s a lot more expensive than A*PFP’s RVO.
3 Likes
So your not using obstacles that will be placed?
I mean are you pathfinding just a road the AI should follow?
I cant seem to get my head around this ECS, only thing i know is when i convert my Enemys to Entitys, then i lose the A Star Pathfinding cause its not optimized for ECS/DOTS.
I actually just wanted the Seeker and AI DestinationSetter to work with IAstarAI.
Then everything would be nice and work just as i have it now :D!
1 Like
Yeah, some of my obstacles are placed by the user (I haven’t added that functionality yet though), and others are hand placed on the map and static. Currently all of my enemies get spawned, but it would be trivial to place them manually if I wanted to.
I too wanted to use Seeker and AI DestinationSetter, but without converting all of those scripts, I couldn’t find a way. It would take me months to figure out how to convert them and I can’t afford to do that right now.
So… yes, like you said, you can’t attach any A* Pathfinding stuff to your enemies. I’m not an expert by any means, but perhaps if I list the steps I took it might help you:
-
First I created a terrain with roads, static obstacles, etc. Just like any normal non-ECS project.
-
I added an empty game object called A* and added the PathFinder script to it and setup my navigation grid just like you would in an non-ECS project.
-
I converted my terrain to a mesh and gave it a static physics body+shape and convert-to-entity script. This step is optional. I had to do this because I want to use unity.physics - it does things like allowing you to put physics bodies on enemies and detect bullet collisions with the ground.
-
I made enemy prefabs and added a convert-to-entity script to them. They’re similar to any normal monobehaviour prefab with a mesh renderer + material. I also added a MoveSpeedData component and a few other things like HealthData or whatever.
-
The only unique thing about these enemy prefabs is that when they get spawned, I add two extra components WaypointIndexData, and PathData. If you’re not spawning enemies, you could use [GenerateAuthoringComponent] and add them to your prefab instead of doing it in the spawner. They look like this:
public struct PathData : IComponentData
{
public FixedList4096<float3> path;
}
public struct WaypointIndexData : IComponentData
{
public int index; // current waypoint index
}
Notice that there is nothing in these components that use A*PFP code. The paths are there in an ECS appropriate form though… so the movement system can propel the enemies forward.
- I made a spawning system, that spawns the prefabs (there are lots of tutorials on this). Right before it spawns them, it uses that MakePath() function I mentioned earlier to find the path from the newly spawned enemy to the destination. This is the only place that I use A*PFP. My spawn system’s query roughly like this:
Entities.ForEach((ref PathData spawnPath, in SpawnOptionsData spawnOpts, in LocalToWorld spawnLtw) => { }).Run();
- Then I made a PathMovementSystem that sets the velocity and rotation of the enemy to the next point in the path until the path completes (the path was precomputed in the spawner). (See my previous comment about the PathMovementSystem) The query looks something like this:
Entities.WithNone<DeathData>().ForEach((ref Translation pos, ref Rotation rot, ref WaypointIndexData waypoint, in MoveSpeedData speed, in PathData path) => { }).ScheduleParallel();
- For games with moving targets (like ones that chase the player for example), you would need to create another system that would query all entities with path and waypoint data components and recalculate the path. I wouldn’t suggest doing it every frame because it’ll likely be way to slow… maybe every 1/2 to a couple of seconds depending on how many enemies there are.
2 Likes
I’ve begun implementing this as well, in a relatively complex environment. I am curious if you have tried running hybrid gameobjects for the pathfinding. I know that “pure-ecs” GOs would be best, but maybe to ease the transition a little the GO that is converted to ecs could remain with just the pathfinding component, and then a system that syncs the gameobject to the entity position and running the pathfinding updates through to the entity. This way the unity.physics or havok system can still be used.
It may be a terrible idea but I will update on what I find out, just wanted to see if you have tried this at all.
Most of the performance used for my game is from rendering and physics so I’m thinking this might be okay.
I have not tried it, but I think it might be possible to do that (use pathfinding with hybrid objects)… but I can’t say for sure. The only thing I’ve used hybrid objects for so far are to allow particles and audio clips to follow agents. I know that if you move an entity, the GO automatically moves with it (there must be a built in system that does it), but I don’t know if that is automatic the other way around.
If your bottleneck is physics and rendering, I think the hybrid approach would help - as long as you make sure all the rendering and physics are done on the entity and not the gameobject. If you get it working, let me know - If it works, I might have to try it!
1 Like
I built a quick prototype in HDRP using the RVO example.
The RVO agent quad mesh was replaced with a complex LOD mesh.
This picture is the stats from 3 runs:
- base scene non DOTS
- non DOTS with custom mesh (3 meshes: body, spinning blade right and spinning blade left. total: LOD0: ~ 5000 triangles
- DOTS
Obviously, the non-DOTS with custom lod mesh example could be improved by combining all of the LODs into either a skinned mesh or some type of custom batching, but the ECS with physics is promising. Also, HDRP has a lot of overhead, but that’s what I’m using so I used it for the test. Keep in mind all of this is with the entity viewer and profiler running at the same time.
System
- Threadripper 3970x (32 core/64 thread)
- Geforce rtx 2080 ti
- 64 GB DDR4
RVO EXAMPLE DOTS TEST (IN HDRP)
Base: 122.4 fps
Non-DOTS w LOD mesh: 98.6 fps
DOTS: 98.7 fps
The time saved from the entity batching on the renderers is offset by roughly the same amount of the added overhead from the physics engine running. And I still need to investigate the physics workflow because it seems high to me at the moment.
There wasn’t much modification to the code:
RVOExampleAgent: at the start of Update I set the rvoagent transform to the entity translation and capture the starting translation before the calculations. At the end of the update, I assign the change in position to an entity component. In an ECS system, I add this offset to the translation of the entity.
I will continue to update as I test bullet collisions and other things.
So I’ve rewritten a lot of the rvo controller and created agent movement scripts using DOTS/ECS and am finally getting to the point where I see really good results. At 10,000 units with pathfinding/local avoidance, I am running at above 60fps and that is with all units touching each other.
This is with all rvo agents as entities, not just inside the rvo simulator. The positional data is getting assigned as a parallel scheduled job in an ECS system.
Not sure how to post a video on here, but I put it up on twitter, check it out: https://twitter.com/BigRookGames/status/1335360569235427328
This is really promising, as even at 10,000 there is very little time spent in calculation for the pathfinding system, and even the movement system of the agents. I will continue to update as I progress (there is still a lot of room for optimization)
5 Likes
Whoa! That’s awesome! Nice job!
I almost do that for my game too, 10K with AIPath movement is so smooth.
I have test 30K too but Astar logic doesn’t match performance of ECS so it’s laggy.
I need to add RVO as @HeroSyndromeTheGame but his work confirms me this the good way for my project ( thank 
)
@aron_granberg Waiting A* pathdinfing 5 based on ECS even if I have to repay the package!
2 Likes
That’s cool man! So you rewrote the RVO controller to use ECS instead of needing to be attached to game objects and you’re not using hybrid entities anymore? If so… any chance you could share it?
Has anyone figured out how to do a navmesh cut in ECS? All the examples use the NavmeshClipper class, but it is a monobehaviour that needs to be attached to the object to be cut… which would normally be a gameobject, but for me, all the models that I need to cut around are entities. I traced it to the function call public void ForceUpdateAround(NavmeshClipper clipper), but again, the problem is that clipper needs to be a gameobject. Maybe there is a low-level API function to specify a bounds to cut? I suppose I could try attaching a hybrid game-object, but I’d rather not have a gameobject hanging around all my entities.
Yep, exactly.
I had to rewrite a lot of the scripts so that they could run in DOTS such as path modifiers but the overall concept is pretty simple.
I used the rvo controller as a base and take the output from that and inject it into the positions of the entities. When an agent is created I add and link a reference to the rvo controller, then no more game objects needed.
So I am running AstarPath.StartPath in a job and take the OnPathComplete and apply a component to tag the entity to apply the path modifiers. Right now I just use a start end modifier and a funnel modifier, but any of the modifiers could be used.
I will try to write up a high level summary of the main code pieces so you can use it if you need. Currently though I am very happy with the performance. I can get a few thousand units before performance becomes an issue. These are pretty heavy mesh models too so lots of room for improvement still:
For the navmesh cuts, I would assume you could do that without the need for gameobjects, and I will probably do that sometime soon because my plan is to get as much over to ECS as possible. Currently the objects I have that effect navmeshcuts are gameobjects anyways (the turrets and buildings) so I’ve been okay so far.
2 Likes
I will have to look into rewriting the scripts such as path modifiers so they can run in DOTS. I’ve gone over this thread a few times: LightweightRVO in ECS but I don’t quite see the big picture… not sure if I still need to rewrite a bunch of the scripts to be ECS compatible.
I tried running AstarPath.StartPath() in a job, but it fails if the job is bursted. ABPath.Construct complains that “Burst error BC1032: Using function pointers/delegates is not supported” and StartPath() complains that “get_isPlaying can only be called from the main thread”). A lot of the functions in A*PFP weren’t really developed for burst from the start so I suppose that’s to be expected. I had to move the path constructor and start-path functions to the main thread.
As for navmesh cutting, I finally gave up trying to figure it out… it seems like everything ties back to reliance on that NavmeshClipper game-object. I couldn’t find anything lower-level than that. Maybe there is a way to do it without game-objects, but I spent a long time searching and didn’t find anything.
I was able to get something working just by using UpdateGraph() and setting the boundary area to non-walkable. After setting the nodes to non-walkable, I walked through all the paths of existing agent and called a function DoesLineSegmentIntersectSphere() to determine if the particular agent intersects the building the player just dropped. If the agent’s current path intersects the new building, then I tell the agent to find another path (StartPath) and it routes around it. It seems to work okay.
One thing that I don’t like is that I’m using a grid graph, and I had the erosion value set to 1, but at 1, it leaves a large area around the newly placed building where the agents can’t go. If I set the erosion to 0, that cuts closer to the new building, which is good, but then the rest of the graph has problems because it places walking areas so close to the edge of cliffs that my agents fall off of them. I think I may try the recast graph again, although back when I first started, I wasn’t having much luck with it.
So… yeah… without the ability to navmesh cut, the recast graph is completely worthless.
I was able to get navmesh cutting “working”. Since there is no low-level API (most things are built-around and tied-to game objects and inheritance), I had to create a dummy gameobject. So whenever the player places a building onto the terrain, I create the dummy gameobject like this:
GameObject navMeshCutter = new GameObject("dummy");
Pathfinding.NavmeshCut cut = navMeshCutter.AddComponent<Pathfinding.NavmeshCut>();
// setup rectangle or circle cut here
// since I have force updates turned off, I force an update here
AstarPath.active.navmeshUpdates.ForceUpdate();
AstarPath.active.FlushGraphUpdates();
// since I have periodic path updates disabled, I reroute my entities here.
It’s hacky because now I have these game objects hanging around doing nothing. I tried deleting them, but doing that causes the graph to go back to normal (without the cuts). If a building gets destroyed, I’ll have to figure out which game-object to destroy to “undo” the navmesh cut (haven’t implemented this yet).
I figured out how to get the recast graph working so I don’t have to use the grid graph anymore. I had to take the functions for path modifiers for funnel, smooth, and radius and put them into a static class with static functions and form an “API” that doesn’t rely on gameobjects or OOP. Then whenever I calculate a new path, I apply the modifiers right after the path is returned, (mainly the funnel and radius ones). One benefit of navmesh vs grid graph is that each path calculation is much faster now <1ms vs 2-3ms. The main benefit is that the navmesh cuts fit perfectly around the dropped buildings.
I’m currently using physics to keep agents from occupying the same space, which is cool, and I like the fact that there is gravity so agents can fall off cliffs when there is an explosion or something. Unfortunately, it has some really bad side-effects: the agents get stuck on corners, slide down inclines, and accidentally fall off cliffs. I spent hours trying to tweak the physics parameters (friction, gravity, mass, damping, etc) to find a solution, but wasn’t able to find a combination that worked. The only thing that seems to work is giving the agents a high velocity to power up hills and avoid sliding down things or getting stuck, but I need my agents to walk slowly, so that is not a good solution.
I think the problem is because my movement script is too simple - I just took the “Writing a movement script” tutorial and put it in a system. It has a small loop to skip waypoints that are really close to each other, a couple of lines to rotate the agent in the direction of motion, and “pos.Value += vel * deltaTime;” to move it. I think my next step is to try and extract some of the code from AIPath (or RichAI), AIBase, Seeker, and Interpolator. Unfortunately, this won’t be easy… there is a lot of complicated code in those classes. RichAI is the most complicated of all, relies on UnityEngine.Transform, and could take a very long time to convert. AIPath looks like the best bet at this point. I’ll also need to create a CharacterControll equivalent, or figure out how to move rigid-bodies. It will probably take me a several days to convert it and get all the bugs worked out.
The only reason I was looking into RVO and Physics is because I want to keep agents from occupying the same space. From what I can tell, RVO will require everything I mentioned previously, AND converting RVOController to ECS. Because the data flow in RVO mode is even more complicated and requires even more classes to be rewritten to use ECS, I’m going to try the physics method first. If that doesn’t work, I’ll circle back to RVO.
My conclusion is that using APFP with ECS in the most basic of ways is fairly easy, but it’s very limited and doesn’t work very well. Using more advanced features like the AI classes, RVO, Navmesh cutting, etc requires a large amount of rewriting, reorganization, and hacking that is almost equivalent to starting from scratch. It requires becoming and expert in A-star navigation and could take months to implement a robust comprehensive ECS solution.
…EDIT…
I made a little bit of progress… I found out that one of the main reasons entities were getting stuck is because after applying the modifiers, the paths would go slightly underground in some places (the terrain has hills and valleys). With physics enabled, the path movement system was trying to set velocity or position to force the entities to go to an underground location that couldn’t be reached.
The solution was to make a new path modifier called “clamp-to-ground” which uses a physics raycast to make the path a specified offset above the terrain. It works quite well.
Before:
After:
I gave up on RVO… I’m not sure how you did it @HeroSyndromeTheGame , but it looks to me like rewriting the rvo controller, AIPath, AIBase, Seeker, Interpolator, and all that other stuff would take forever.
@Ph0t0n Sorry for the delay, I don’t get notifications about replies to this unless I am tagged, so I saw the last one.
For navmesh cutting I haven’t fully converted that piece yet, so I am doing the same thing as you, creating a simple dummy GO to cut out the area. For my use case this is fine because the only thing that cuts navmeshes are buildings and player walls, which won’t be more than a couple hundred, and don’t create any noticeable impact on performance.
Yeah, I feel your pain on getting the system as a whole over to ECS. I went through the same steps as you did. Ultimately I rewrote all of the pieces that I would be using: AIPath, funnel modifier, a few other modifiers. I also wanted the bots to have real time physics so I implemented it so that could happen. It’s actually really cool and I’ve had a ton of fun just messing around with the volume of enemies and how the system reacts with injecting more, adding explosion forces, etc. I can get a couple thousand with collision and pathfinding together all under a few ms.
another clip here of them with collision in big groups (neighbors turned way down so that they intentionally collide with each other) https://twitter.com/BigRookGames/status/1345884251061940229
I am in a crunch right now, trying to get into playtesting in the next two weeks, but after that, I can walk you through some of the code if you would like.
The clamp to ground is a good solution. I use mostly hovering robots so I haven’t encountered that issue yet, but I will have walking units so thanks for posting about that.
1 Like
@Ph0t0n Hey how is the project going? Any further progress on ecs side?
I’ve been using the implementation I discussed prior and the dots side of it hasn’t failed me yet (a few tweaks here and there). I also implemented other classes to use straight pathfinding calls for things like harvesters and the bots that don’t need rvo, and it works pretty well.
Would love to hear how your project is going though.
@HeroSyndromeTheGame . I was unable to get RVO working… it just seemed like too much work to rewrite everything. That RichAI/AIPath classes have their hands in a messy spider-web of classes. What I have right now works so-so… I’m moving entities by setting their physics velocity (using unity.physics). They still get stuck now and then when the terrain is uneven. On uneven terrain, the movement looks unnatural. Unless I can find a better path navigation method, I’ve resigned myself to the fact that I will need to keep the terrain mostly flat.
I hope your game is going well!
@HeroSyndromeTheGame How’re things going so far with your pathfinding? Did you ever try to convert the navmesh cutter or are you still using gameobjects for that? I saw some of your videos on reddit - awesome stuff! Our games are pretty similar - combination of base defending, factorio-style automation, and TD, except yours is first person and way cooler.
I’ve been working on other stuff… animation, weapons, damage, AI, etc., but in a few weeks I’ll be going back into pathfinding and trying to get something acceptable running.