mlange-42 / arche Goto Github PK

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?

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.

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.

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.

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.

Currently, type alignment is not considered when storing components.

Clarify whether alignment needs to be considered!

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

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

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.

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

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

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.

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.

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.

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

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.

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.

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

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

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

I want to preallocate the filters and put them into a generic struct member. This works as long as I don't add .Without() or something similar to the filter:

package main

import (
	"math/rand"

	"github.com/mlange-42/arche/ecs"
	"github.com/mlange-42/arche/filter"
	"github.com/mlange-42/arche/generic"
)

type Position struct {
	X float64
	Y float64
}

type Velocity struct {
	X float64
	Y float64
}

type Transparent struct {
	DoDamage bool
}

func main() {
	world := ecs.NewWorld()

	monsters := generic.NewMap2[Position, Velocity](&world)
	ghosts := generic.NewMap3[Position, Velocity, Transparent](&world)

	for i := 0; i < 10; i++ {
		e := monsters.New()
		pos, vel := monsters.Get(e)
		pos.X = rand.Float64() * 100
		pos.Y = rand.Float64() * 100

		vel.X = rand.NormFloat64()
		vel.Y = rand.NormFloat64()
	}

	for i := 0; i < 10; i++ {
		e := ghosts.New()
		pos, vel, trans := ghosts.Get(e)
		pos.X = rand.Float64() * 100
		pos.Y = rand.Float64() * 100

		vel.X = rand.NormFloat64()
		vel.Y = rand.NormFloat64()

		trans.DoDamage = true
	}

	posid := ecs.ComponentID[Position](&world)
	veloid := ecs.ComponentID[Velocity](&world)
	transid := ecs.ComponentID[Transparent](&world)

	monsterselector := filter.All(posid, veloid)
	ghostselector := filter.All(posid, veloid).Without(transid)

	selectors := []ecs.Mask{}

	selectors = append(selectors, monsterselector)
	selectors = append(selectors, ghostselector)

	// do stuff...
}

Go crys:

./main.go:64:32: cannot use ghostselector (variable of type ecs.MaskFilter) as ecs.Mask value in argument to append

So it would be good (for me at least 😁) if they would be of the same type or there were a way to encapsulate the ecs.MaskFilter into a ecs.Mask (or vice versa).

best,
Tom

If World.Exchange et al. some (or all) components to add and to remove are the same, what would happen?

We should probably make this panic, for safety and as it is obviously a mistake on the user's side.

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 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

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, 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.

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

WorldStats need to be adapted for the new structure.

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?

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.

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

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?

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

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

Howdy,

before I start: I am pretty new to this kind of business - I'm trying to build my first game using the arche ECS framework which seemed to be one of the more mature ones (from what I could tell).

Ok, sofar I have 7 different components in my world. Here are the stats:

World -- Components: 7, Nodes: 10, Filters: 0, Memory: 42.0 kB, Locked: false
  Components: Position, Velocity, Player, Collectible, Renderable, Tilish, Solid
Entities -- Used: 300, Recycled: 0, Total: 300, Capacity: 384
Node -- Components:  0, Entities:      0, Capacity:      1, Memory:     0.0 kB, Per entity:    0 B
  Components: 
Node -- Components:  4, Entities:     85, Capacity:    128, Memory:     6.0 kB, Per entity:   40 B
  Components: Position, Renderable, Tilish, Solid
Node -- Components:  2, Entities:    212, Capacity:    256, Memory:    10.0 kB, Per entity:   32 B
  Components: Position, Tilish
Node -- Components:  4, Entities:      1, Capacity:    128, Memory:    11.0 kB, Per entity:   80 B
  Components: Position, Velocity, Player, Renderable
Node -- Components:  3, Entities:      2, Capacity:    128, Memory:     6.0 kB, Per entity:   40 B
  Components: Position, Collectible, Renderable

However, when I start it and move the player around a little bit, after a while the game crashes:

panic: run out of the maximum of 256 bits

goroutine 48 [running]:
github.com/mlange-42/arche/ecs.(*bitPool).getNew(0xaa0e28?)
        /home/scip/go/pkg/mod/github.com/mlange-42/[email protected]/ecs/pool.go:120 +0x94
github.com/mlange-42/arche/ecs.(*bitPool).Get(0xb673a0?)
        /home/scip/go/pkg/mod/github.com/mlange-42/[email protected]/ecs/pool.go:109 +0x1c
github.com/mlange-42/arche/ecs.(*lockMask).Lock(0xc0000a4638)
        /home/scip/go/pkg/mod/github.com/mlange-42/[email protected]/ecs/util.go:111 +0x25
github.com/mlange-42/arche/ecs.(*World).lock(...)
        /home/scip/go/pkg/mod/github.com/mlange-42/[email protected]/ecs/world_internal.go:865
github.com/mlange-42/arche/ecs.(*World).Query(0xc0000a4480, {0x870858?, 0xc0107d6160})
        /home/scip/go/pkg/mod/github.com/mlange-42/[email protected]/ecs/world.go:368 +0x67
openquell/game.(*Level).Update(0xc000492000)
        /home/scip/dev/openquell/game/levels.go:67 +0x125
openquell/game.(*LevelScene).Update(0xc0003abbe8?)
        /home/scip/dev/openquell/game/levelscene.go:43 +0x27
openquell/game.(*Game).Update(0xc0003abc70?)
        /home/scip/dev/openquell/game/game.go:40 +0x59
github.com/hajimehoshi/ebiten/v2.(*gameForUI).Update(0xc0004ca690)
        /home/scip/go/pkg/mod/github.com/hajimehoshi/ebiten/[email protected]/gameforui.go:142 +0x23
github.com/hajimehoshi/ebiten/v2/internal/ui.(*context).updateFrameImpl(0xc0001cf580, {0x8773c0, 0xc00011bb00}, 0x1, 0x4084000000000000, 0x407e000000000000, 0x7f5d6065ef18?, 0xb36f60, 0x0?, 0xc010adb040)
        /home/scip/go/pkg/mod/github.com/hajimehoshi/ebiten/[email protected]/internal/ui/context.go:145 +0x3ea
github.com/hajimehoshi/ebiten/v2/internal/ui.(*context).updateFrame(0xc000193220?, {0x8773c0, 0xc00011bb00}, 0xc1690b221d5d1bd3?, 0x11bad77a7?, 0xb365e0?, 0xc000112eb0?, 0xc000112eb0?)
        /home/scip/go/pkg/mod/github.com/hajimehoshi/ebiten/[email protected]/internal/ui/context.go:75 +0x89
github.com/hajimehoshi/ebiten/v2/internal/ui.(*userInterfaceImpl).updateGame(0xb36f60)
        /home/scip/go/pkg/mod/github.com/hajimehoshi/ebiten/[email protected]/internal/ui/ui_glfw.go:1231 +0x1da
github.com/hajimehoshi/ebiten/v2/internal/ui.(*userInterfaceImpl).loopGame(0xb36f60)
        /home/scip/go/pkg/mod/github.com/hajimehoshi/ebiten/[email protected]/internal/ui/ui_glfw.go:1199 +0xac
github.com/hajimehoshi/ebiten/v2/internal/ui.(*userInterfaceImpl).Run.func2()
        /home/scip/go/pkg/mod/github.com/hajimehoshi/ebiten/[email protected]/internal/ui/run_glfw_notsinglethread.go:60 +0x37
golang.org/x/sync/errgroup.(*Group).Go.func1()
        /home/scip/go/pkg/mod/golang.org/x/[email protected]/errgroup/errgroup.go:75 +0x56
created by golang.org/x/sync/errgroup.(*Group).Go in goroutine 1
        /home/scip/go/pkg/mod/golang.org/x/[email protected]/errgroup/errgroup.go:72 +0x96

I'm not sure how to create a small example to reproduce the problem. Basically I use the generic aproach to build the world. I could show you the source if that helps?

The crash happens here:
https://repo.daemon.de/scip/openquell/src/branch/master/game/levels.go#L67

The filters (I call them selectors) are being intantiated once per level in NewLevel() here:
https://repo.daemon.de/scip/openquell/src/branch/master/game/levels.go#L32

Entity + component creation happens in NewGrid() here (based on a map):
https://repo.daemon.de/scip/openquell/src/branch/master/game/grid.go#L27

The ecs.World object is a member of the Game struct, so it's not global but always the same.

The crash first occurred after I added the Collectibles component, I did not have the problem as long as I only had solids and the player components.

What's also interesting: if I only use 1 entity using the Collectibles component, then the crash occurs much later (but it happens anyway). It'd probably happen without any collectibles anyway but I didn't fiddle long enough around in the game. So it seems to me, these components add up somewhere with every loop the game goes in. But I have no clue where to look at, to be honest.

Would be great if you'd have an idea (or it might also be a bug, dunno).

Thanks in advance,
Tom

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!

In some places we rely on panicing by Go or standard library code to avoid checks that would cost precious nanoseconds in hot code. E.g., Query.Next() and Query.Get(...) panic with index out of range [-1] when called on a closed queries.

This should be better documented in the respective methods/functions.

Generally, error messages could be improved in some places in order to point users to potential mistakes or unintended use.

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, 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.

• 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)

Entity relations were implemented in #231.

Benchmarks are required for getting and setting the relation target.

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

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.

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!

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.

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!

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.

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

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

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

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.