Really cool! How would you approach spatial partitioning in an ECS system?

[jugglingjsons]

Sorry, I have no issue with the code. I have actually used to to create boids simualtion.

Numbers above:

• full 4 k screen
• 15 k boids all rendered + modulated
• avg lookup per boids 10-15 other members
• stable 60 fps & tps

I've used basic grid partitioning and in memory caching for the cell lookups. Depending on the grid size, map size it can go to much higher numbers, but then the sim is less dynamic as it's too spread in space.

My main question is:
How would you approach spatial partitioning in an ECS system? Curios to hear your thoughts on the subject.

Thanks for a great tool :)

It would be nice to provide some examples of sub fetches or group fetching optimisation.

[ragoune]

Hi, I am glad to see my tool in action, awesome work ! If you have a video of the boid in movement to share, please do.

If I understand correctly your question, I have the same problem to resolve in my own 3D game engine : my 3D space is divided in an octree, so I only want to fetch some entities in a given space partition (the visible one, from the camera point of view). I speak of this in the README.md "What is to come next ?".

Unfortunately Volt does not give any feature to fetch the entities pre-filtered without an additional cost.

I have searched multiple solutions on my side, none is perfect for the performances:

• Using the filterFn argument in Query.Foreach, you can check its entity position and manipulate only the entities on the space division you are interested to work on. This filterFn is applied on every entities though, so it has more or less the same cost as if you added the check in the Query loop.
• On my project, to simplify my method: I have a structure Octree containing OctreeRegions, and each OctreeRegions has a slice of all the EntityIds in it (updated only if an entity moves, but in Games most of the entities are statics so the cost is not as high as it would be for a simulation like yours). Each Entity has a TransformComponent, with a boolean flag "is visible" if the OctreeRegion is visible from the Camera. Then when rendering, in my Query loop I can use this flag in the filterFn without complex computation.
• Another (good?) solution might be to use Tags. E.g. tags "space1", "space2" [...] added/removed when an Entity moves. So that we could fetch these from our Queries without additional cost, because the data would be already "fragmented" in the internal memory storage of the ECS. But Volt does not implement this yet.

This last solution gets me to think: this probably needs to be designed in the ECS for correct performances. The goal is to have "partitions", for a given Archetype. If you have any thoughts about it, you're welcome to try to contribute.

[jugglingjsons]

Screen.Recording.Feb.13.2025.mp4

Github won't accept bigger file recordings for now this will have to do.

For now I have implemented a simple grid similarly to what you're describing here:

each OctreeRegions has a slice of all the EntityIds

Fragmentation on tags sounds amazing, but it brings it's own complexities with it.
I think this would be a good approach though. Like at what point to refresh the data - if I am not mistaken for moving entities one loop will always be necessary to warm the lookups.

Perhaps combining it with debug.SetGCPercent(x) and in memory cache per frame on first full loop in a given frame could work.

I mean that if you queried :

	queryChannel := query.ForeachChannel(g.count/g.workers, func(qr volt.QueryResult1[T]) bool {
		return qr[tagName] === tagValue
	})

you would not only get the data for the cell you're looking to fetch, but also populate all the other filters on given partition

Sorry these are just quick thoughts , will come back to it from Monday, maybe I can cook something in the spirit of the above.

One more feature I would like to see is to add a segmenter for the query.ForeachChannel so that you could deterministically control which channel will be processing which entity.

Quick addition - if tags were to be refreshed by the Ecs engine through slice ordering it could get expensive fast.

I would rather depend on post mutation replace . I guess I am coming to the conclusion that with fast moving environments it would be better to solve the spatial partitioning problem on the implementation level not on Ecs itself. Especially considering the updates / inserts of volt.

This however in no way undermines the utility of tag types / subtypes and optimising their fetching.

[ragoune]

I really like the recording, it's nice to see Volt in action :)

My previous answer was indeed more useful in the case of a less dynamic scenario. You having more moving entities than not, it would require to write/move data a lot with the current ECS implementation. But it is a real problem I have been thinking a few months ago, so I need to get back on it.
I keep this issue open, and will reach to you if I find something acceptable.

About the segmenter to control which channel returns which entity, how would you see this in term of implementation ?

[jugglingjsons]

Re the segmenter, I was naively assuming it would somehow enable me to make the routine processing more deterministic.
As in making sure the routines get processed in order, but it's not the case. I guess to fix the problem I am describing it would be ok to keep a reference to a sequential id with atomic and update it on each progression - this would however defeat the purpose of concurrency.
Don't dwell to much on this, it's my problem which I was hoping to solve in a lazy way with a segmenter. It was only good when I was driving in the real of logic aka the real world :P
What I was trying to achieve is cross platform determinism order of execution guarantee.

Another way to achieve this would be a version of double buffer. Where I can replace the actual memory of the world with a freshly created one. Haven't played with this much as of yet though.

---

Here's a naive approach for fetching & caching lookups I've been using:

type boidCacheEntry struct {
	boids     []*boid // the fetched result
	frameUsed int     // which frame we last updated it
}

type boidCacheEntry struct {
	boids     []*boid // the fetched result
	frameUsed int     // which frame we last updated it
}

func (bs *BoidSystem) fetchFromMap(x, y int, currentFrame int) []*boid {
	// If the cache entry is valid for this frame, return it
	entry := boidMapCache[x][y]
	if entry.frameUsed == currentFrame {
		return entry.boids
	}

	// Otherwise, actually build the slice of boid pointers
	cellContent := BoidMap3d[x][y] // slice of entity IDs
	entities := make([]*boid, 0, len(cellContent))
	for _, entId := range cellContent {
		ent := volt.GetComponent[boid](bs.world, entId)
		entities = append(entities, ent)
	}

	// Store in the cache
	boidMapCache[x][y] = boidCacheEntry{
		boids:     entities,
		frameUsed: currentFrame,
	}

	return entities
}

// in update
func (g *Game) Update() error {
...
	for x := 0; x < MapWidth; x++ {
		for y := 0; y < MapHeight; y++ {
			g.bs.fetchFromMap(x, y, physicsFrame)
		}
	}
...
}

I do it before most of the logic to warm it up. From what I've checked it's faster despite the empty logic pass for the cache warmup. I bet it could be optimised though.

[ragoune]

Hello,

I am taking advantage of today's v1.5.0 release to inform you that the Tag system we discussed is available since a few weeks ago (see the README.md). Although it does not really address your issue of spatial partionning, perhaps you can experiment with it and find it useful.

Since our last exchange, there have been some optimization improvements, between 10% to 30% on write operations (CreateEntity/AddComponent).

Have a great day!