Consider implementing landmass with bevy_ecs.

[andriyDev]

A lot of landmass is just juggling mutability of various things. If this was implemented in Bevy we could much more easily handle mutability.

[lain-dono]

I'm doing this in my private fork. It's not very hard, but it's extremely time consuming. Especially because I have code quality as an additional goal. Lots of refactoring and stuff.

The main goal is performance and ergonomics for Bevy users. This means that Bevy becomes a mandatory dependency. But there is still an opportunity to make a wrapper world.

There are some other ideas I'd like to try. For example, instead of the current NavMesh representation, maybe use HalfEdge or BMesh. Plus embed an ORCA implementation (dodgy). After merging everything into one crate, you can unmerge them again. As part of the refactoring.

I think I can publish the results in a week or two. However, due to the way I initially approach my work, you should expect a single commit that changes everything (almost every line in the project). It might make sense to develop what I do as an independent project for this reason.

Any thoughts?

[andriyDev]

I want the end result to allow have landmass not expose Bevy. Bevy should be a private dependency so that upgrading Bevy is a minor version bump for landmass.

bevy_landmass on the other hand should obviously expose Bevy.

I am fine changing the nav mesh definition if there are performance improvements to be made. It's definitely not in any optimal state.

I don't think we need to embed dodgy (maybe I'm not understanding what you mean by embed). dodgy is pretty self contained, and I am fairly confident we can't squeeze out much more performance by moving the implementation into this crate. The main reason being each entity needs to determine its obstacles on the fly to ensure they only consider nav mesh borders "on their level". So at best, we can store the dodgy agents, but that's a very small struct, which I don't think will be the limiting factor.

Oh boy, a single commit to change everything seems really hard to review 😅 I think I'll give the refactor a try myself and see how far I get before I lose my mind though. Definitely I think the first version of this should just be shuffling around code: no "actual" improvements. Tackling each improvement after the fact is a ton easier than changing everything all at once.

[lain-dono]

I want the end result to allow have landmass not expose Bevy.

An example of what it looks like. Not an exact copy, but I use this to get tests working.

As you can see, some of the Bevy types are exposed. The user actually has three options. Don't care about Bevy existing at all. Get the advanced API (integration with bevy_ecs only). Use the full Bevy integration.

pub struct ArchipelagoWorld<T: CoordinateSystem> {
    world: World, // storage for actors/islands/characters
    agents: QueryState<(Entity, &'static mut Agent<T>)>,
    marker: std::marker::PhantomData<T>,
}

impl<T: CoordinateSystem> ArchipelagoWorld<T> {
    pub fn new() -> Self {
        let mut world = World::new();
        world.register_component::<Agent<T>>();
        Self {
            agents: world.query(),
            world: World::new(),
            marker: std::marker::PhantomData,
        }
    }

    pub fn update(&mut self, delta_time: f32) { ... } // some SystemParam shenanigans inside

    pub fn agent(&mut self, AgentId(entity): AgentId) -> &Agent<T> {
        self.world.get_mut(entity).unwrap() // unwrap because its for tests
    }

    // it's okay to expose Mut?
    pub fn agent_mut(&mut self, AgentId(entity): AgentId) -> Mut<Agent<T>> {
        self.world.get_mut(entity).unwrap()
    }

    // advanced api
    pub fn agents_mut(&mut self) -> Query<(Entity, &'static mut Agent<T>)> {
        self.agents.query_mut(&mut self.world)
    }

    // simplified api
    pub fn agents_iter_mut(&mut self) -> impl Iterator<Item = (AgentId, Mut<Agent<T>>)> {
        self.agents
            .query_mut(&mut self.world)
            .into_iter()
            .map(|(entity, agent)| (AgentId(entity), agent))
    }
}

I don't think we need to embed dodgy

I'm worried about reallocations every frame. It's not a big deal when you have 10 agents, but it's a problem when you have 10,000 (still tricky but possible). Additionally, some parts can be done in parallel. For example, filling the spatial hash separately for agents and characters. In addition, a way can be found to separate static obstacles from dynamic ones.

Also, it looks like dodgy doesn't have integration with Bevy. Merging would help create integration between landmass and doggy at Bevy level. After that, you can separate them if needed. However, all this is something that can be done after transferring landmass to bevy. And after reworking the internal structure of NavMesh.

What's my motivation? I want a fully simulated open world. landmass/dodgy have enough features, but not enough performance. I'm sure I know enough dark magic to make it work. Bevy is a necessary element of dark magic. Because of bevy_ecs and its automatic parallelism.

[andriyDev]

An example of what it looks like.

This is almost what I'd want. Though we can just make our own Mut type to wrap Bevy's and then we are fine to upgrade Bevy without problems. Similar reasoning goes for the others.

I'm worried about reallocations every frame.

I don't think this is a significant issue. There are many things we can do to mitigate this like making dodgy accept a "Content" which just holds any Vecs we may need to avoid reallocation and reusing that context for every agent. This doesn't seem like we need to integrate these at all still.

---

I took an initial stab at this and realized I was going the complete wrong direction. The bevy-only version doesn't really need the CoordinateSystem trait for the most part. I'm going to try to split the crate into a LandmassCorePlugin with all the stuff in a generic, standard coordinate system and a LandmassPlugin<T> which just converts in and out of the standard coordinate system for user convenience. I think that will simplify a lot of stuff.

[lain-dono]

Well, since you want to do this refactoring yourself, I just shared a private repository. It's a bit messy, but...

This is almost what I'd want.

As you can see, I'm moving the implementation itself inside bevy_landmass. So the landmass crate becomes a wrapper. Most of the breaking changes will be in bevy_landmass, not landmass.

[lain-dono]

I think the last commit (prepare for systems) might be a good one to illustrate.

I removed the redundant HashMaps and moved what they store directly into Agent/Character. This splits update naturally into 6 separate functions:

• Update NavMesh state.
• Update Agent and Agent::target projection onto NavMesh.
• Update Character projection onto NavMesh.
• Perform pathfinding.
• Update Agent internal state.
• Perform avoidance.

In fact, for the general case, I reduced the memory requirements. HashMap has its own overhead and there is no need to store keys. The dependency between parts of the code has decreased, which allows these parts to be transformed into autonomous systems. Some of these systems can be executed in parallel with each other.

In addition, NavMesh reconstruction and actor avoidance can be split into several parts. The same can be said about dodgy if you move it inside the bevy world.

Reducing the dependency between parts of the code makes it possible to make the implementation more flexible and customizable. For example, you can have other implementations of pathfinding. Which may be necessary when you have a lot of very simple Actors. For example, this is used in Project Zomboid, They Are Billions, Factorio, and many strategy games.

[lain-dono]

The next step (move to systems) is quite simple and obvious. I renamed NavigationData to Archipelago and make it a Resource. Along with AgentOptions. After that, functions are converted to systems.

As a next step I chose the hierarchy of volumes. At its core it uses a binary tree. Which has some very nice properties, especially when it is full. Why not make it perfect.

Each level of such a tree contains twice as many as the previous one. And the whole tree contains N*2-1 elements, where N is the number of elements on the last level. All these elements can be stored in a linear array. And we only need to allocate memory once. A truly perfect tree.

You can find out more here: https://en.wikipedia.org/wiki/Binary_tree

Note: You can copy-paste whatever you want from my private repository that I showed you, without any attribution.