Efficient collision detection?

[ul]

On the one hand, iterating all entities to check for collision detection could be expressed as an elegant and concise rule. On the other hand, the naive rule will be grossly inefficient in the presence of many entities moving on each tick, leading to O(n^2) checks. What would be the recommendation? Is there an efficient ruleset to use, or should collision detection have its own implementation and just be fed data from the session?

I reckon uniform grid might be expressed as a ruleset and still be relatively efficient:

1. Have a rule that derives which entities present in which cells.
2. Have another rule that checks collisions for all entities spotted in the same cell.

What do you think? Would expressing it as a ruleset introduce significant overhead? Are there any other options?

[oakes]

Yeah I think you just need to partition your entities so you can skip unnecessary collision checks. I'm not sure what you mean by "expressing it as a ruleset" though, maybe rephrase that.

[ul]

By "expressing it as a ruleset", I meant something that relies on joins to aggregate information. E.g. something like having

[id1 :entity-type t1]
[id1 :grid-position p]
[id2 :entity-type t2]
[id2 :grid-position p]

in :what and then maybe checking for actual collision in :when and then inserting derived fact about it in :then.

As opposed to having just

[id :entity-type t]
[id :grid-position p]
[:global :grid-content grid-content] ;; map of grid cell to entities spotted there

and doing all the checking inside the rule that is interested in finding out if the entity is colliding / is blocked by smth.

[oakes]

If you're going to do it the first way I definitely recommend collecting things in derived facts to reduce the number of joins, like explained here.