Spatial acceleration structures?

[juj]

Heya, just wanted to dot down a thought or two: the intersecting circles demo demonstrates well a shortcoming of straightforward ECS style programming: sometimes a system that does a for-each over a set of components is the wrong algorithm to solve a problem.

The Circles-boxes demo runs fast with 600 objects in O(n) fashion. However the intersecting circles demo only manages 30 circles, which is due to the O(n^2) loop over all pairs of circles.

Instead of quadratic loop over all pairs of circles to test each pair for collision, an efficient way would be to maintain a spatial acceleration structure such as a QuadTree, to be able to perform all_colliding_pairs(circleComponent, circleComponent).forEach((e1, e2) => {}); queries in linear time.

Similarly, in many cases one would like to manually build index structures specific to a program. For example, in a Match-3 game, one would definitely not want to have to loop through each candy in the game map to find the one that has a coordinate (x=4,y=3), but being able to do 2D lookups with a grid/map structure gameMap[4][3] is desired.

A couple of other spatial queries that are very common:

• find-closest-entity(targetEntity, withComponent), e.g. an AI bee in a game finding the nearest flower to fly to,
• find-all-intersecting-entities(geometricShape, withComponent), e.g. a raycast or a geometric rectangle/grid area for an overlap,
• find-closest-intersecting-entity(geometricShape, originPoint, withComponent), e.g. get the first raycast target, or the closest object that lies inside a cone of visibility.
• find-any-colliding-entity(targetEntity, withComponent);, e.g. find if in an infinite runner the player collided with an enemy/spike/obstacle, and should die (no need to check further for any more obstacles if one is enough to kill)

If one does for-each loops over all entities with a certain component to solve these kind of queries, the result gets quite inefficient, even if one did wasm+simd+threads optimizations. Plain for-each loops over sets of components are as often the incorrect algorithm as they are the correct one!

[joshmarinacci]

Would it solve the problem if you could monitor add and remove events then use your own acceleration structure within the system that wants it?

[fernandojsg]

@juj this is definitely a topic we would like to work on. This is related also to the concept of having a common Transform component, and probably BoundingVolume(Sphere/Box). So we could use that Transform component for this kind of spatial checks, collisions, physics, rendering and so.
But we decided to leave that component out from the core from now and move that to a set of components and binding on top of the core.

We could add a helper too to implement some structure depending on the user needs: quadtree, octree, bvh, ... and that helper could provide some of the functions you mentioned so developers could use them in their system.
In any case is not mandatory to do the full loop on each system, you could iterate the entities as you want so that spatial structures could be integrated at a higher level concept on the systems too.

What I'm not sure if is worth the investment is to move this logic to the queries definitions somehow, where you could define a spatial query and then iterate on the results based on that or leave it to helper functions to be used on the execute method.

Thank for bringing this up, I'll ping you back as soon as I'll start looking into ideas on how to incorporate these.

[jdrew1303]

@juj One solution you could use is to use the tag and components to mark the entities for inclusion into your structure and to update from. An example of this would be something like the following:

class CollidableSystem extends System {
  constructor(world, attributes) {
    super(world, attributes);
    this.quadtree = attributes.quadtree;
  }

  execute(delta, time) {
    this.queries.toBeAdded.results.forEach(entity => {
      // add our entities to the tree and tag it as being managed (so we dont add it again)
      entity.addComponent(CollidableManaged);
    });

    this.queries.collidable.results.forEach(entity => {
      // here you might want to update the positions of the items in the tree or something.
    });

    this.quadtree.getCollisions().forEach(collisions => {
      // stuff!
    });
  }
}

CollidableSystem.queries = {
  collidable: {
    components: [Collidable, Position, Bounds, CollidableManaged]
  },
  toBeAdded: {
    components: [Collidable, Position, Bounds, Not(CollidableManaged)]
  }
};

import { QuadTree } from "random quad tree module";
const quadtree = new QuadTree();

const world = new World().registerSystem(CollidableSystem, { quadtree });

You can also break apart the systems for adding items to the quadtree, updating the positions and handling the collisions. I use this sort of pattern to handle adding items to three.js scene graph, the cannon.js world, audio, etc. There are usually a load of places where this is useful. Im not sure if its best practice but its handy from an architectural point of view. If you want to communicate across systems do so by tagging the entities with components.

[5310]

I've also been using spatial structures with ECSY simply by having one System manage all the partitioning and then querying that one System from the other spatial Systems instead of using ECSY's built-in tag-like querying. There's nothing stopping Systems talking to each other, so why not right?

class GridSystem extends System {
  grid = arrayND(GRID_SIZE, GRID_SIZE, 0)
  static queries = { 
    entities: { components: [Position,] },
  }
  //naïvely assigns each entity to the relevant grid
  execute (delta, time) {
    this.grid = arrayND(GRID_SIZE, GRID_SIZE, 0)
    this.queries.entities.results.forEach(entity => {
      const {x, y} = entity.getComponent(Position)
      const [i, j] = [x, y].map(v => Math.floor(rangeMap(0, GRID_SIZE, 0, GRID_SIZE * GRID_SCALE, v)))
      this.grid[i][j].push(entity)
    })
  }
  //query entities within a Chebyshev neighborhood
  //can be used by other systems with `this.world.getSystem(GridSystem).query(...)`
  query (x, y, d) {
    const [minX, maxX, minY, maxY] = [x-d, x+d, y-d, y+d].map(v => clamp(0, GRID_SIZE, v))
    const result = []
    for (let x = minX; x <= maxX; x++) for (let y = minY; y <= maxY; y++) result.push(...this.grid[x][y])
    return result
  }
}

From: https://codepen.io/5310/pen/LYYGQBe?editors=0010

[DavidPeicho]

I would argue that the acceleration structure should be out of the core. If you need it for Three, it should go in Escy Three eventually.