Commit graph

43 commits

Author SHA1 Message Date
Bill Currie
698ce157b3 [ecs] Move correct number of subpool ranges
Fixes yet another segfault when deleting the last range in the subpool.
Also, initialize the subpool's next index.
2023-07-11 00:06:21 +09:00
Bill Currie
76b6d3141b [ecs] Use correct index when deleting subpool ranges
Coming up with tests is hard. Breaking code with real code is easy.
2023-07-09 11:52:11 +09:00
Bill Currie
c32ffce886 [ecs] Add a function to move a subpool to be the last
This has use when the order of components in the pool affects draw order
(or has other significance), especially at the subpool level. I plan to
use it for fixing overlapping windows in imui.
2023-07-08 19:55:37 +09:00
Bill Currie
0360e33a00 [ecs] Add "tree mode" to hierarchies
As I had long suspected, building large hierarchies is fiendishly
expensive (at least O(N^2)). However, this is because the hierarchies
are structured such that adding high-level nodes results in a lot of
copying due to the flattened (breadth-first) layout (which does make for
excellent breadth-first performance when working with a hierarchy).

Using tree mode allows adding new nodes to be O(1) (I guess O(N) for the
size of the sub-tree being added, but that's not supported yet) and
costs only an additional 8 bytes per node. Switching from flat mode to
tree mode is very cheap as only the additional tree-related indices need
to be fixed up (they're almost entirely ignored in flat mode). Switching
from tree to flat mode is a little more expensive as the entire tree
needs to be copied, but it seems to be an O(N) (size of the tree).

With this, building the style editor window went from about 25% to about
5% (and most of that is realloc!), with a 1.3% cost for switching from
tree mode to flat mode.

There's still a lot of work to do (supporting removal and tree inserts).
2023-07-07 14:42:49 +09:00
Bill Currie
7e338b7e29 [ecs] Delay calculation of last index
Removing a hierarchy from an entity can result in a large number of
component removes in the same pool, thus changing index of the lest
element of the pool. This *seems* to fix the memory corruption I've been
experiencing with the debug UI.
2023-07-04 16:37:09 +09:00
Bill Currie
71bc708030 [ecs] Use nullindex for hierarchy indices
Even though nullindex and nulent have the same value, they have very
different meanings (and I might shift to 0 for nulent).
2023-07-04 14:43:20 +09:00
Bill Currie
0b6e8b60bd [ecs] Add a component rotation function
This allows rotation of components within the array. I'm not sure if
it's what I want, but it was an interesting exercise anyway.
2023-07-03 01:40:26 +09:00
Bill Currie
e2464ed879 [build] Fix some library install issues
Removed a bogus dependency from libQFecs, and fixed the order of ui
libraries. This takes care of some first-time make install issues.
Libtool needs the libraries to be specified in dependency order.
2023-04-20 15:15:12 +09:00
Bill Currie
a8efde1dd3 Fix some mxe build issues 2023-03-25 21:36:45 +09:00
Bill Currie
00d1ae0b91 [ecs] Invalidate entity in hierarchy before removal
I'm not sure just what was going on other than *other* components were
getting double-removed when the hierarchy reference component was
removed when the entity was being deleted. This might even prevent
issues with removing the hierarchy from an entity that's not being
deleted as the pre-invalidation prevents the removal from deleting the
entity.
2023-03-07 02:00:19 +09:00
Bill Currie
488ccdc512 [glsl] Be more null-safe for free/destroy functions 2023-03-06 18:21:13 +09:00
Bill Currie
e19e7cad0c [ecs] Invalidate entity before removing components
It turns out that the fixes for other problems related to removing
hierarchy reference components fixed the problem moving the entity
invalidation fixed, and invalidating the entity late somehow broke the
sprite renderer (at least in glsl).
2023-03-05 23:31:20 +09:00
Bill Currie
8efe8e63d3 [ecs] Plug a bunch of memory leaks
The hierarchy leak was particularly troublesome to fix, but now the
hierarchies get updated (and freed) automatically just by removing the
hierarchy reference component from the entity. I suspect there will be
issues with entities that are on multiple hierarchies, but I'll sort
that out later.
2023-03-05 22:03:01 +09:00
Bill Currie
28226ac75c [ecs] Handle indices beyond the subpools
It turns out that the bsearch bug was hiding incorrect handling of
indices in the subpool beyond the last tracked subpool. In which case, a
correctly working bsearch correctly fails to find the range, but the
search can be skipped entirely.
2023-03-05 18:53:33 +09:00
Bill Currie
254fcff8ff [ecs] Find correct correct sub-pool range
Returning -1 for key > value doesn't work too well for bsearch.
2023-01-22 01:04:23 +09:00
Bill Currie
3d52caadec [ecs] Avoid shuffling components in empty ranges
When bubbling a component past an empty range, there's no need for any
actual movement other than adjusting the range itself, and doing so
corrupts the sparse/dense array relationship. Fixes a segfault when
hiding the deathmatch overlay (that resulted from the change to using
canvases).
2023-01-21 13:58:43 +09:00
Bill Currie
9384442834 [ecs] Remove a debug print 2023-01-21 03:14:27 +09:00
Bill Currie
8833518826 [ecs] Support sorting subpools
Sorting the whole pool when subpools are in use could break the
subpools (very high probability, depending on the sort criteria and
subpool criteria).
2023-01-16 11:32:12 +09:00
Bill Currie
3a2877dd9a [ecs] Adjust subpool range type to return start,end
I found I needed the subrange start as well as the end, but I liked that
the subpools themselves used only the end of the range, so switching to
just a unint32_t for the value and adding a function to return a tuple
made sense. I had kept the struct because I thought I might want to
store additional information (eg, the entity "owning" the subpool), but
found that I didn't need such information as the systems using subpools
that way would have access to the entity by other means.

Interestingly, the change found a bug in subpool creation: I really
don't know why things worked before, but they work better now :)
2022-12-20 17:56:08 +09:00
Bill Currie
34930ba195 [ecs] Fix a bit of white space 2022-12-20 10:59:26 +09:00
Bill Currie
d67b8cdf05 [ecs] Add support for subpools
Subpools are for grouping components by some criterion. Any component
that has a rangeid callback will be grouped with other components that
return the same render id. Note that the ordering of components within a
group will be affected by adding a component into a group that comes
before that group (or removing a component).

Component pools can have multiple groups, added and removed dynamically,
but removing a group should (currently) be done only when empty.
2022-12-18 21:11:21 +09:00
Bill Currie
b230fe18ce [ecs] Split component registration from pool creation
While this does require an extra call after registering components, it
allows for multiple component sets (ie, sub-systems) to be registered
before the component pools are created. The base id for the registered
component set is returned so it can be passed to the subsystem as
needed.
2022-12-13 22:58:44 +09:00
Bill Currie
3c4dccf801 [ecs] Organize headers and code
There's now a main ecs.h file that includes the sub-system headers,
removing the need to explicitly include several header files, but the
sub-systems are a less cluttered.
2022-12-13 15:31:35 +09:00
Bill Currie
bb677a1a7c [ecs] Move href_comp into hierarchy_t
This means that the component id used for hierarchy references must be
passed to Hierarchy_New and Hierarchy_Copy, but does all an entity to
have more than one hierarchy, which is useful for canvases (hierarchies
of views) in the 3d world (the canvas root would have a 3d hierarchy
reference and a 2d (view) hierarchy reference).
2022-12-12 00:20:20 +09:00
Bill Currie
ac0079f872 [ecs] Add a function to remove a component from all entities
While simple component pools can be cleared simply by zeroing their
counts, ones that have a delete function need that function to be called
for all the components in the pool otherwise leaks can happen.
2022-11-17 21:49:38 +09:00
Bill Currie
24d8d864a2 [ecs] Optionally delete entities on hierarchy removal
Useful for deleting an entire sub-hierarchy of entities.
2022-11-08 00:16:29 +09:00
Bill Currie
ddd6c958a9 [ecs] Fix parent index updates when removing sub-hierarchies
In the end, it was removal of the old entries that corrupted the parent
indices. Very nicely, most of the fixes involved removing code. Taking
advantage of the ECS to debug the hierarchies was fun, and the resulting
colorized entity names helped no end.
2022-11-06 23:04:40 +09:00
Bill Currie
1130919049 [ecs] Add a simplified test of the sbar hierarchy
Even 37 objects is a lot, but it's a whole lot better than 180. Most
importantly, it reproduces the problem, which seems to be not all parent
indices getting updated. The child indices seem to be working nice, as
do the reference object indices (ie, the entity components). I suspect
its the parent indices getting corrupted that cause problems on the
second switch of the hud/sbar cvar as the parent indices are used to
find the child indices that need to be updated.
2022-11-06 20:04:34 +09:00
Bill Currie
cf6b4efe5d [ecs] Colorize hierarchy test output
Just the tiniest bit of color goes a long way to spotting issues.
2022-11-06 20:03:29 +09:00
Bill Currie
97a6ce833e [ecs] Adjust the source root during self insertions
This improves the behavior of hierarchies when self-inserting, but nq's
sbar still crashes when trying to do so. However, its tree is a fair bit
more complex than the test case (that does pass now), so I need to try
to replicate the important parts of the tree with fewer objects (180 is
too many to work with).
2022-11-06 17:36:49 +09:00
Bill Currie
ecf59c8141 [ecs] Add failing same-hierarchy parenting test
As expected, reparenting a sub-hierarchy such that it (and possibly its
children) move up the arrays fails (this is why sbar needs to first
remove the sub-hierarchy then insert it).
2022-11-06 17:36:33 +09:00
Bill Currie
05947c8ac4 [ecs] Rework new hierarchy test for same-hierarchy
Since test_build_hierarchy2 already tested removal of a sub-hierarchy
(once fixed), it seems test_build_hierarchy3 testing parenting within
the same hierarchy would be a good idea. Reparenting such that
everything moves to later in the arrays works nicely (not very
surprising).
2022-11-06 08:36:43 +09:00
Bill Currie
b91568d234 [ecs] Improve the behavior of Hierarchy_RemoveHierarchy
Its updates to the various indices were out, but this was missed due to
the tests being wrong. I wonder if I got interrupted while working on
them last and just assumed the removals were correct. This improves
sbar's behavior, but it's still wrong when pulling the armory view out
of the inventory. Very unsure what's going on, but the various indices
look ok, as do the view positions.
2022-11-06 02:38:59 +09:00
Bill Currie
01c67a345f [ecs] Fix some more hierarchy tests
Ugh, things were quite bad, it turns out. It seems a lot of trouble
would have been saved if these tests had worked (however, something is
still not quite right as views are out of place).
2022-11-06 00:30:55 +09:00
Bill Currie
f89fbf9724 [ecs] Fix a child miscount in the test case
Heh, that was a bit funny, actually, but it makes me wonder just how
broken sub-hierarchy deletion was.
2022-11-05 23:44:01 +09:00
Bill Currie
26438848ce [ecs] Add a failing hierarchy test
This is the bug that sbar found when pulling a sub-hierarchy out of a
larger hierarchy: child indices not getting updated correctly for later
siblings and any niece objects.
2022-11-05 22:23:46 +09:00
Bill Currie
10037927ea [ecs] Add hierarchy-only tests
The hierarchy-specific tests from the transform tests have been moved
into the ecs tests and the transform tests renamed appropriately. As
part of the process, hierarchies can now have a null type (ie, no
additional components maintained by the hierarchy). This should make
sorting out the issues highlighted by sbar a bit easier.
2022-11-05 21:29:38 +09:00
Bill Currie
57cd30fca3 [ecs] Move parent setting logic into hierarchy
It should have always been here, but when I first created the hierarchy
and transform objects, I didn't know where things would go. Having two
chunks of code for setting an entity's parent was too already too much,
and I expect to have other hierarchy types. Doesn't fix the issues
encountered with sbar, of course.
2022-11-05 17:54:49 +09:00
Bill Currie
cf911884c6 [ecs] Add support for sorting component pools
As the bookkeeping data is spread between three arrays, sorting a
component pool is not trivial and thus not something to duplicate around
the codebase.
2022-10-31 13:10:53 +09:00
Bill Currie
f6820c59e7 [ecs] Initialize registry href_comp to nullent
This indicates that no hierarchy reference component has been
registered, which must be done by the user when hierarchies are used.
2022-10-28 11:39:59 +09:00
Bill Currie
80c0beff89 [ecs] Support adding null hierarchies to non-root
As an implementation detail, inserting null hierarchies (src hierarchy
is null) is supported for ease of hierarchy construction from data. No
component data is copied, only the child and parent indices and counts
are updated.
2022-10-27 19:46:28 +09:00
Bill Currie
52b09e81cd [ecs,scene] Update tests for move to separate ecs lib
And fix an issue spotted in hierarchy.c: incorrect move of objects and
lack of check for valid entity when updating hierarchy reference
indices.
2022-10-27 15:35:29 +09:00
Bill Currie
db7f8a461e [ecs] Move ECS core into its own library
While the libraries are probably getting a little out of hand, the
separation into its own directory is probably a good thing as an ECS
should not be tied to scenes. This should make the ECS more generally
useful.
2022-10-26 17:24:03 +09:00