When representing worlds, you normally save a set of objects. The programm will iterate over the objects or tuples of objects very often, so it's necessary to minimize the work. It should also not consume unneccessary memory. There a several ways to represent these sets of objects.
The simplest way is just an array of objects. This will require all objects to be the same size. It's also possible to let the objects contain references to other data. This will allow the objects to decide their real type at runtime and allow some kind of dynamic typing. When there are multiple references, it's even possible to save multiple references to different components. The references may or may not contain a value. So the types can be changed easily at runtime by adding or removing referenced components. All of the approaches using a single array have the same problems: You have to iterate over all objects in case you want to do some action: That may become a problem, if one action only has to be done for a few objects. Even if all actions are done in the same iteration, it has to be checked if it is one of these few objects. It's even a bigger problem, when iterating over all tuples of objects. One problem is the need of dynamic multiple dispatch (checking types of both objects in order to know, what to do). This would have to be implemented by oneself in most programming languages. But there is a more important problem. Normally you would only have to iterate over pairs of objects, that may collide (by calculating a tree of the objects for optimization) and just for a few objects iterate over all other objects once (for example only if one of the objects has a big mass, the gravity is calculated between it and the other object). This will really reduce the amount of work to be done (O(n log(n)) or O(n m), where m is much smaller than n, instead of O(n^2)), but is difficult using single arrays.
There is another popular approach called entity component system (ECS). In this case, you don't save the components as pointers in some struct, but every componennt of an object has its own array. An object is just an ID, which maps to the array indices. There are optimized ways to fastly iterate over all objects, that have some common components. In many cases it's even a good thing, that same components are saved in the same array because that way there is a higher cache locality. But when too many components are needed for some calculation, that won't help. ECS also allows to dynamically add and remove components and change the object type that way. The problems with ECS is, that it's difficult to understand and to control, what's happening exactly. But at least the concept is very flexible and easy to understand. Instead it may be best, to just do it in an intuitive way, which does not require dynamic types, multiple references nor big structs with unneccessary data.
The simplest way to implement sets of objects of multiple types is just using multiple sets of the same type, which each just get represented by a single array. In order to explain, what this will mean, I'll add an example:
- There are two sets of objects, static objects, which don't move, and dynamic objects, which move
- Static objects save their position and some collision information
- Dynamic objects additionally save their velocity, which changes their position, and maybe some acceleration information
- When a collision between any two objects happens, dynamic objects change their velocity
So there are following steps:
- Recalculate the new positions for dynamic objects
- Check all collisions, where at least one object is a dynamic object, and calculate it's new velocity
This will be implemented in the following way:
- To recalculate the position of dynamic objects, only one iteration over the set of dynamic objects is neccessary
- To recalculate the velocity of dynamic objects, you have to iterate over all tuples in the set of dynamic objects and all tuples, where one object is in the set of static objecs and and one in the set of dynamic objects. It's not neccessary to iterate over all tuples in the set of static objects
When there is just a small number of dynamic objects, this approach seems pretty efficient. For large numbers of dynamic objects, it may be better to use acceleration structures. But even when using acceleration structures, for the static objects this structure only has to be recalculated when the set of static objects changes or one is moved because of some other reason.
Even this approach will allow to add and remove components. For converting a dynamic object to a static object, you would just have to remove the object from the dynamic object set and add an object with the same position and collision data to the static objects set. For converting a static object to a dynamic object, you would just have to remove the object from the static object set and add an object with the same position, collision data and zero velocity to the dynamic objects set. Copying all the data may be inefficient. When this is done often, it may be better not to save the data directly inside the object, but inside references.
But this approach may get unintuitive, when there are too many types of objects. For example let's add a component, that let's an object apply gravity to all dynamic objects. Objects containing this component will be called gravity objects. If an object can be as well a gravity object as a dynamic object, it's necessary to add two new arrays. So a single new component may in the worst case double the number of needed arrays. There are two problems now:
- Implementing a struct for each combination of components will be much work
- Adding an array for each of these structs will be complicated
There has to be better ways to allow this. Next this approach has to be simplified, so it's easier to use than normal ECS, because you theoretically have access to whole structs, and will hopefully be more efficient because of less indirection.
The first step is adding a way to simplify struct creation. Therefore there needs to be a way to add components. A component is just a tuple of data, which may depend on some properties of other components and will itself expose properties. There could be a position component, which just contains a position data, doesn't depend on other components and exposes a way to get the position and to translate the object. Then there may also be a mover component, which contains velocity data, depends on some component, that can translate the object and exposes some way to get the velocity and to accelerate the object. At last, there could also be a mass component, which contains mass data, depends on some component, that can accelerate the object, and exposes some new way to accelerate the object depending on the mass. Multiple components can be combined into a mixin at compile time. A mixin will just be a struct containing all the data of the combined components. The combined components are ordered. A feature of a component is able to use the exposed features of the next component, that uses this feature. In the end, all these calls can be inlined, and there is just some object, that exposes some features as methods. A mixin can just be created like a struct, but every field of the mixin just is a tuple of values, that represents a component. The type won't even have to declared explicitely, but created implicitely, when creating some object of the mixin. This way it should be pretty intuitive to declare different types of complex objects with similar properties.
In order to add new types to the arrays without having to select one of the many arrays manually, it will be helpful to have a single data structure, that just contains all needed arrays. The type of the data structure should be created just by specifying all the data types (which should preferably mixins), that can be contained by any of the arrays. This datastructure just needs a few methods, which highly depend on compile time features:
- single method to add new elements (which array will be filled is generically checked at compile time)
- an iteration, which calls the same function/method on all objects of the arrays, on whose objects it is defined for (needs compile time test, for which arrays the function/method is defined)
- some way to remove some element from an array (could also be done during an iteration)
- an iteration, which calls the same function/methods over all tuples of objects of the same or even different arrays, when it is defined for that tuple of types (also compile time tests needed to get all the tuples of arrays, that need to be iterated over) This should already be enough, to allow implementing very complex behaviours in a structured way.
A Scopes programm using these new structures may look like this:
component pos vec2
expose 'pos (self)
load self
expose 'translate (self vec)
self += vec
component vel vec2
expose 'accelerate (self vec)
self += vec
expose 'update (self)
if (exposed? self 'update)
component-call 'update self
assert (exposed? self 'translate)
component-call 'translate self (load self)
component circle f32
expose 'draw (self)
if (exposed? self 'draw)
component-call 'draw self
let rad = (load self)
draw-circle (component-call 'pos self) rad
component sprite (pointer Sprite)
expose 'draw (self)
if (exposed? self 'draw)
component-call 'draw self
let rad = (load self)
draw-sprite (component-call 'pos self) rad
fn object-list (T)
component
.. "<object-list " (Any-string (Any T)) ">"
Array T
expose 'pos (self)
let pos =
local vec2
for object in self
pos +=
'pos self
pos / ((countof self) as f32)
expose 'translate (self)
for object in self
pos +=
'translate self
let objects =
MultiTypeArray
mixin pos
mixin pos vel
mixin pos circle
mixin pos sprite
mixin pos vel circle
mixin (object-list (Mixin pos)) vel sprite
mixin (object-list (Mixin pos circle)) vel
'add-object objects
mixinof
pos = (vec2 0)
vel = (vec2 0)
sprite = (load-sprite "person.png")
'add-object objects
mixinof
pos = (vec2 0 256)
circle = 64.0
'add-object objects
mixinof
vel = (vec2 0 64)
pos = (vec2 0 -64)
# => error: invalid type for array, you have to declare pos first
'add-object objects
(mixin pos vel)
vel = (vec2 0 64)
pos = (vec2 0 -64)
# but this will work because the type is correct
'map objects 'update # update all objects
'map objects 'draw # draw all objects
'map-tuple objects
inline (left right) # reverse direction, when two
if
and
defined-methods left 'pos 'circle 'vel 'accelerate
defined-methods right 'pos 'circle 'vel 'accelerate
let dis =
+
'pos left
'pos right
if (dis < ('circle left) + ('circle right))
let vel =
avg
'vel right
'vel left
'accelerate right (vel - 2.0 * ('vel right))
'accelerate left (vel - 2.0 * ('vel left))
# this does not allow loop elimination for invalid tuples yet