mlange-42 / arche Goto Github PK

Relation archetypes that are in the same node (same component set) could be recycled to speed up the creation of new archetypes.

Could be solved in conjunction with #240.

TODO:

• Nodes need a list of archetype pointers Relation nodes store their archetypes
• Nodes need a list of free archetypes, or their world indices
• Free archetypes are tracked separately for relation vs non-relation
  • Non-relation archetypes are never removed and don't require tracking
• Take free archetype from the node if it has a relation

Add benchmarks ECS performance comparison for access to components via the world instead of queries (i.e. by entity ID).

• Generic access with Map[T] (#95)
• Event listeners (#83)
• Delaying modifications that are not possible in a locked world (#83)
• Initilization with components Used in most examples anyway
• World stats (#95)

Currently, all archetypes of relation nodes are iterated if the node matches.

For plain RelationFilter, this could be improved by just accessing the single matching archetype throught the node's archetype map.

Batch-removing entities by a filter (or optionally an exact mask) could be very efficient by just clearing the matching archetypes.

Entity relations were implemented in #231.

Benchmarks are required for getting and setting the relation target.

Until now, most of the optimization went into pure iteration and random access speed.

The weak point of an archetype-base ECS, component changes and resulting archetype transfer, are rarely benchmarked or profiled.

Generic queries could be speed up by up to approx. 20% by:

• caching archetype column layout (updated when traversing to next archetype)
• using different layout types for mandatory vs. optional components, to avoid nil check branching

To keep the API clean, this would probably require to merge package generic into package ecs. Otherwise, methody not relevant for the user would need to be exposed.

Not sure if a maximum of 20% speedup if worth it.

Arche has no dependencies, except testify for unit tests. Would be great to get rid of them for normal module users.

Maybe go_test.mod is an option? See https://dev.to/wallyqs/introducing-gotest-mod-18a1

Back again!

I managed to get a panic out of arche and wanted to get some advice on how I should be holding onto entities.

I have a simple tracking system that looks for entities with a Target component. It takes that target component out, which contains an *ecs.Entity value. It then gets the Position of the target to update its own Velocity towards the target.

While doing those checks I do an initial sanity check to assert that the entity is alive. And I managed to get:

panic: runtime error: index out of range [1326464512] with length 3070

goroutine 14047 [running]:
github.com/mlange-42/arche/ecs.(*entityPool).Alive(...)
        /home/co/go/pkg/mod/github.com/mlange-42/[email protected]/ecs/pool.go:74
github.com/mlange-42/arche/ecs.(*World).Alive(...)
        /home/co/go/pkg/mod/github.com/mlange-42/[email protected]/ecs/world.go:430
gameserver/game/systems.(*TrackingSystem).Update(0xc00065a6e0, 0xc0000fe9d8)
        /home/co/code/towerdefensegame/gameserver/server/game/systems/tracking.go:53 +0x3f0
github.com/mlange-42/arche-model/model.(*Systems).updateSystems(0xc0000fe900)

My code looks like:

	query := s.filter.Query(w)
	for query.Next() {
		// Get the speed and target of the projectile
		id, pos, velocity, speed, target := query.Get()

		// If the target has no entity ignore it
		if target.Entity == nil {
			continue
		}

                // If the entity is dead, handle retargeting...
		if !w.Alive(*target.Entity) {
			target.Entity = nil
			continue
		}

I'm assuming that the entity is getting deleted after being killed, but another entity is still holding onto it as a target and somehow, it's getting recycled into non-zero memory? I've already footguned myself a few times here holding onto entities after they've been deleted thinking the value should be safe, but it seems not?

Caching nodes instead of archetypes coule be more efficient, now that iterating archetypes of a node is more efficient (see #272).

Try and benchmark it!

Benchmarks for relation queries with a low number of children show sub-par performance.
This is probably due to the initial overhead of creating a query for every parent.

Identify where the overhead comes from, and try to optimize it!

Functionality for batch-creation of entities of a certain component combination could make entity creation more efficient.

Flecs has very robust relationships. https://www.flecs.dev/flecs/md_docs_Relationships.html

One feature is a relationship can be transitive to
A IsA B IsA C IsA D therefore, A IsA D, Is that possible in arche?

Add a test that zero-sized labels cause no bugs.

In earler versions, allocating storages with zero elements caused something like shared pointers between storage buffers.

Check/test that this does not cause problems with zero-sized label components.

Currently, on archetype transition the engine searches for the matching archetype by brute force using the components bitmask.

This could be improved by constructing an archetype graph. Each archetype would hold a list of which archetypes are reached by adding or removing a certain component type.

Image source: ajmmertens.medium.com

Hello!

I'm finding as I add more and more complexity to my ECS that I'm frequently adding Entities that have more than 8 components. And it can feel strange to have compMapper1 compMapper2, etc...

I know there's nothing stopping me from just chaining generic.NewMap's together. But is there anything that lets me group components into bundles kind of like how bevy does it? Or should I just add them all to an exchange or something?

Arche does not (and will not) support adding or removing components or entire entities during query iteration. However, nothing prevents the user from trying it, with undefined behaviour.

As a first measure, lock the world when a query is created, and hand it back to unlock.

Later, add/remove operations could be buffered and executed at unlock.

Flecs has "entity relationships", which is a neat feature for efficient queries over hierarchies. Sander Mertens wrote a great explanation of it here.

It probably is worth thinking about whether and how this is possible in Arche.

Flecs-like implementation

Would require at least these changes:

• Component types must be entities, and the component ID is the entity ID
  • Reserved first (e.g. 128) entities for regular components
• Get rid of the limit of 128 component IDs (each relationship combination produces a new ID, so this explodes quickly)
  • How to implement this without slowing down access to archetype/table columns?
  • To avoid the overhead on each entity, queries would probably need to get "column accessors" for the queried components/IDs on each transition to the next table.
  • But how to access by ID then? IDs would need to hold the accessors, like in Donburi
  • ⚠️ Would still slow down access of components through the world (lookup of archetype column in a map[int]int, close to 20ns)
    • 💡 Or, maybe not? Regular components would have the reserved usual 128 IDs... and the query syntax that makes use of relationship targets (i.e. non-component entities) does probably not apply here

Simplified alternative

There is a way to identify/mark components as relationship. Relationship components have an property Entity (the target).

• When a relationship component is added, separate tables are created for different targets
• There is only a single column required for a certain relationship component type
• Within each table, the targets of all relationships are the same
  • How to keep track of that?
• Tables expose their relationship targets (potentially just using simple (Get(idx, compID)))
• Query.nextArchetype() (or the filter cache) check for the mask as well as the target

Relationship components

They could be required to embed a Relationship struct. This embed...

• ...is used by the component registry to identify relationship component types
• ...has a private field entity (or target)
• ...requires a call to the world to set the entity (causing move to another table)

Open questions

• How to handle relationshpis in the archetype graph?
• Empty archetypes are currently not removed. Empty archetypes with a relation probably should.
  • But no swap-remove possible here!

Entity should have a zero value singleton, and possibly a method Zero() bool.

This is useforfor storing entity IDs with the possibility for zero/nil/unset.

Add a method that allows for adding and removing components in a single step, to avoid archetype transitions.

Arche itself has no dependencies. However, there are dependencies for tests and profiling.
Try to get rid of them!

Is it possible to have Arche without dependencies in a sub-directory without having the repo in go.mod?
If not:

• Implement assert stuff to get rid of testify
• Move profiling and benchmarks against other implementations to a separate repository

Currently, a component type must be added to an entity, then is can be queried from the world, and initialized.

As we currently can't modify entities during query iteration, things like component addition must be postponed by the user. It would be useful to e.g. create a list of entity-component pairs to add already initialized component objects.

Hello!

First off, thanks for making this great library!

I've observed 100% cpu usage from the goroutine handling the *Systems.Run() even while the system is paused. I looked into it a bit, and it seems like while the system is paused s.nextUpdate is not set to anything. Such that the sleep in *Systems.wait():

	t := time.Now()
	wait := nextUpdate.Sub(t)

	if wait > 0 {
		time.Sleep(wait)
	}

Is always negative and causes the wait to return immediately. I'm trying to use this as a runtime for a game server, so Ideally, I can run as many systems in parallel as possible. Which makes this functionality less than ideal as I'm spending an entire core on per system even if it only is using a fraction of the core normally.

Upcoing v0.8.0 features entity relations (see milestone 1).
However, each entity can only have one relation to a single other entity.

This issue is for collecting thoughts on extending to multiple relations per entity.

Required

• Map-like data structure for mapping multiple entities (targets) to a node archetype, including wildcard/nil
• Filters that support multiple relation targets

Hi @mlange-42, hope you are well.

I'm looking to be able to save/export the state of a World to storage, and then to be able to load/import it at a later time. Is this something you've ever found the need to be able to do?

I've had a look through the current and past issues, and examples and can't see anything that suggests this is something that has been suggested previously, or that Arche currently supports.

Is it something that you think would be straightforward to implement? Is it something you would be interested in adding to the package? If not, would you have any suggestions or a direction to point me in as to how I might achieve this?

Thanks very much,
Paul

As of #248, nodes manage (relation) archetypes.

WorldStats need to be adapted for the new structure.

As of #231, entites with relations can only be created with a zero target.
This requires to move the entity to another archetype after creation.

Provide an way to create entities with relation targets.

Arche is designed for the use in individual-based models. This comes with some design choices that may differ what would be expected for an ECS for game development.

Document them!

• Limited to 64 128 component types for each World (#78)
• Panics instead of letting the user handle errors, e.g. on:
  • Accessing a dead/removed entity
  • Adding already present component
  • Removing missing component
  • Trying to change components in a locked world
  • Trying to iterate beyond the end of a query

Modification of entities (add/remove components) could be passible in batches, using a filter.

Advantages:

• Modify many entities without the need to do it outside of a query
• Potential speedup as with entity creation

Currently, archetypes are only chreated and never removed. This is ok for usual archetypes.

However, entity relations were implemented in #231. This splits archetypes by relation target. With dynamic targets (i.e. targets are removed and added during the simulation), this can lead to accumulation of a large number of archetypes.

Archetypes for entity relations should be removed when the target entity dies/is dead.

Hello, I want to add more test for competition, please tell, what the tool to use in order to generate results.csv for plot.py

The code needs profiling for memory allocations that could be reduced.

Safe component access is around 30% slower than unchecked access (no World.Alive check). With generics, however, checked access takes twice as long.

cpu: Intel(R) Xeon(R) Platinum 8272CL CPU @ 2.60GHz
BenchmarkArcheIterWorldID_1_000-2                	  426333	      2815 ns/op	       0 B/op	       0 allocs/op
BenchmarkArcheIterWorldID_10_000-2               	   41562	     29032 ns/op	       0 B/op	       0 allocs/op
BenchmarkArcheIterWorldID_100_000-2              	    4036	    293517 ns/op	       0 B/op	       0 allocs/op
BenchmarkArcheIterWorldGeneric_1_000-2           	  240807	      5195 ns/op	       0 B/op	       0 allocs/op
BenchmarkArcheIterWorldGeneric_10_000-2          	   23683	     49716 ns/op	       0 B/op	       0 allocs/op
BenchmarkArcheIterWorldGeneric_100_000-2         	    2416	    495585 ns/op	       0 B/op	       0 allocs/op
BenchmarkArcheIterWorldIDUnchecked_1_000-2          	  593316	      1907 ns/op	       0 B/op	       0 allocs/op
BenchmarkArcheIterWorldIDUnchecked_10_000-2         	   61190	     19616 ns/op	       0 B/op	       0 allocs/op
BenchmarkArcheIterWorldIDUnchecked_100_000-2        	    5505	    209547 ns/op	       0 B/op	       0 allocs/op
BenchmarkArcheIterWorldGenericUnchecked_1_000-2     	  445701	      2564 ns/op	       0 B/op	       0 allocs/op
BenchmarkArcheIterWorldGenericUnchecked_10_000-2    	   49465	     24185 ns/op	       0 B/op	       0 allocs/op
BenchmarkArcheIterWorldGenericUnchecked_100_000-2   	    4786	    248773 ns/op	       0 B/op	       0 allocs/op

Currently, there is only a minimal example in the README, as well as doc domments, tests and benchmarks to explore the usage of the library.

Write a documentation that explains all classes functions. There are not to many.

Entity relations were implemented in #231. However, they need to be documented better.

• Extend docstrings
• Add examples
• Add it to the feature list

Currently, normal (uncached) queries iterate all archetypes. Relation archetypes for the same component set, however, are in the same archetype grapf node.

This could be used to optimize iteration over archetypes.
See also #246

TODO:

• Relation nodes store their own archetypes
• Rework query to iterate nodes and inner archetypes
• Filters ignore target when it is nil

Currently, each storage consists of a single large buffer. This causes re-allocation and garbage connection on growth.

Implement chunked/paged allocation, as in marioolofo/go-gameengine-ecs.

With entity relations (#231), a lot of archetypes with the same properties might be created when targets are dynamic.

More archetype data could be stored in nodes instead of archetypes, to speed up creation for relations.

Currently, type alignment is not considered when storing components.

Clarify whether alignment needs to be considered!

Currently, the archetype graph sits in the archetypes themself. This means that arechetypes are created for component combinations that don't appear in the model.

This should be split.

Currently, Arche is limited to 64 component types per world due to the use of uint64 for bit masks.

This could be extended to 128 types by using a pair of uint46, or ti an unlimited number by using some BitSet implementation.

Performance overhead should not be too big, as bit masks are mainly used for archetype handling.

• Implement it
• Test performance impact

Performance impact is around 20% for 1024 archetypes and 2 entities in each. For more entities per archetype, it is negligible.

Performance of queries could be improved by registering them to the world, and updating their list of archetypes when new archetypes are created.

Currently, queries check archetypes using the filter on every iteration pass. Basically, this check is required only when new archetypes are created.

Currently, archetypes are only added and only grown.

Removing archetypes is probably not worth it.
It might, however, be useful to let users set a shrinking policy.

A potential place of optimization could be to let the user pre-allocate/reserve memory for a planned number of new entites with a certain component set, i.e. for a certain archetype.

world.Alloc(100, posID, velID)

mapper := NewMap2[Pos, Vel](world)
mapper.Alloc(100)

On the other hand, CapacityIncrement already allows for some user control.

Currently, Arche prevels addition and removal of components or entire entites when the world is locked by queries.

Instead, or optionally, the the world could collect changes and apply them when unlocked.