Limiting combinatorial explosions

[alex-dixon]

The following rule should insert a fact about an enemy threatening a friendly whenever an enemy unit is within "range" of a friendly one:

[[?enemy :unit/enemy ?enemy-loc]]
[[?friendly :unit/friendly ?friendly-loc]]
[[?enemy :movement/capability ?can-move]]
[(<- ?distance-between-them <- (distance ?enemy-loc ?friendly-loc)]
[:test (>= ?can-move ?distance-between-them)]
=>
(insert! [?enemy :threatens ?friendly])

Great! That was pretty easy to write. However, it entails a combinatorial explosion wherein n enemies are compared to n friendlies. Here's an annotated version that hopefully represents something like what's going on computationally.

; Matched enemy id "enemy-1"
[[?enemy :unit/enemy ?enemy-loc]]
; Matched friendly id "friendly-1"
[[?friendly :unit/friendly ?friendly-loc]]
; Looked up the distance "enemy-1" can move
[[?enemy :movement/capability ?can-move]]
; Run "enemy-1" and "friendly-1" through pathfinding algorithm and return result 
[(<- ?distance-between-them <- (distance ?enemy-loc ?friendly-loc)]
; Compare two numbers
[:test (>= ?can-move ?distance-between-them)]
=>
(insert! [?enemy :threatens ?friendly])

Without a heuristic by which to compare enemies and friendlies, we're kind of stuck comparing every enemy to every friendly.

I need to do some research, but it seems like we'll be OK after the first time this runs. Subsequently, for all enemies and friendlies whose ?enemy-loc and ?friendly-loc hasn't changed, this rule should not fire.

[sparkofreason]

Sounds like N-body gravitational simulations in physics. To exactly calculate the force on one particle, you'd need to calculate the distance to every other particle, which results in the combinatoric explosion. Instead they use slick heuristics that group particles such that distant particles are approximated as one body. Might be some inspiration for your problem there.

[alex-dixon]

@sparkofreason Thanks. We're considering using quadtrees for the case described above. Appears common in games for solving similar problems. I believe this is an issue that is dealt with in subsequent (unfortunately proprietary) incarnations of the Rete algorithm (Rete II, Rete NT) in a seemingly heuristicless way. How that's accomplished (and the perf they supposedly boast) is well beyond me.

@mikegai may have more input.

[mikegai]

@alex-dixon as we discussed the simplest way to address this is to have domain-optimized indexes outside of Rete help control/limit rule work. Something like:

[[?enemy :quad/near ?friendly]]
[[?enemy :unit/enemy ?enemy-loc]]
[[?friendly :unit/friendly ?friendly-loc]]
[[?enemy :movement/capability ?can-move]]
[(<- ?distance-between-them <- (distance ?enemy-loc ?friendly-loc)]
[:test (>= ?can-move ?distance-between-them)]
=>
(insert! [?enemy :threatens ?friendly])

where the nearness fact is coming in from the quad-tree.

[mikegai]

Note that this issue is just about "best practices" : I think we're too early to begin generalizing any of this in a framework and if we did it would be once we had optional logic modules.