The execution kernel of RC++: RETE*, a faster RETE with TREAT as a special case

Some behaviours of computer game agents can be naturally expressed as collections of rules and knowledge bases. General purpose rule-based languages provide high-level constructs for expressing complex conditional behaviour. We examine the runtime kernel of RC++, a rule-based language developed for game AI, to explore the costs associated with adopting general-purpose, rule-based approaches for computer game production. The kernel of RC++ is the RETE* algorithm, an extension of the RETE algorithm with better time characteristics, but also able to exhibit the beneficial properties of TREAT (a low memory cost alternative to RETE) when required. RETE* achieves this functionality and performance by employing (i) asymmetric deletion, (ii) dual tokens, and (iii) a dynamic beta-memory cut mechanism. The dynamic beta cut allows the RETE/TREAT trade-off to be exploited by users. Theoretical and empirical performance comparisons for RETE, TREAT and RETE* are provided. The implications for the utility of rule-based programming for the computer games industry is discussed, and we conclude that there is still some way to go before rule-based programming can be employed in the game-making process.