# Is Rete an efficient algorithm to implement a system that allows NPCs to make decisions based on their world views and inner state?

I'm developing an AI "mind" engine, which allows NPCs (non playable characters) to think and make decisions, based on their view on the game world, and their own inner states (in the future I may add the NPCs' memory - long or short term - if necessary).

Given those inputs, they can give a list of possible actions, with possibilities, for example with a rabbit:

• World view: a wolf (enemy) is 100m away, the carrot is 40m away.
• Inner state: it is hungry, it has big courage and can take risks.

So the expected type of output will be the actions that the rabbit can do:

• Runs away: 40%
• Bites one bite of carrot then run: 80%
• Keep eating and don't give a damn about the wolf: 20%

Based on the desired actions, it will give its decision: which action to take. But that's future works, now I'm concentrating on how to produce that list of actions.

I read the chapter 5, book Artificial Intelligence for Games, Ian Millington and I found the Rete algorithm, which allows match a rule sets to a given database - in my case, the database will be the combination of the NPC's world view and inner state. It seems suit well with my needs, but after making a search, I can see very few (actually, zero) projects that use this algorithm.

Is it so heavy and slow for computer games? Or does it have any more drawbacks that can't be widely used?

## 1 Answer

It's trivial enough to determine actions via a fast formula (including bitwise ops) or a LUT (lookup table which could be a dense array, sparse array or hashmap), given the available info coming in via AI senses. Combine with FSM and you'll have a simpler, quicker, more debuggable system.

I don't think you really need inference, here! You could instead demand various arguments to the formula and just leave unknown ones as defaults (e.g. zero) such that they don't contribute (much) to the end result in terms of actions to be taken by the AI.

I suppose one benefit you would get from Rete is the ability to "remember" without a full recalc each time... but I doubt that's something to be concerned about given your relatively tiny datasets. Bear in mind that any graph structure like Rete's tends to be much slower than dense or even sparse arrays of equal node count, as CPU cache benefits greatly by linear alloc / read-ahead as opposed to the random access style that dynamically-allocated graph nodes demand.

• Is using LUT + FSM combination can be expandable? Because, I'm developing an engine/plugin, so that it shouldn't be tied into a single situation. Is using arguments a little bit... inflexible? I mean, I want my engine/plugin to be used in many different circumstances - the arguments-functions bond is not flexible enough to do that. – Tống Tùng Giang Jul 7 '16 at 11:16
• Depends how generic/expandable you engineer it to be. Rete is ready made and, to some degree, flexible, and you could linearise allocation of the graph that it uses. Still, I suspect Rete isn't really a great fit for the games space. I have a gut feeling you'll implement it and then some time later, it will evolve into something tighter / more specific / more efficient, or find such a solution elsewhere. See also this. By all means, use it as a stepping stone for learning. Just expect change. – Engineer Jul 7 '16 at 17:18
• After googling I found Rete is proprietary, that's why it doesn't have pseudo code online. If I choose it I may stumble a risk to pay money even when I write it from scratch, so no, no Rete anymore. Anyway, thank you very much for your suggestions, I will consider using a naive approach on rule-based system, to see if I can do anything for its slowliness (as described). – Tống Tùng Giang Jul 8 '16 at 4:25
• @TốngTùngGiang Well then I've learnt something too, did not know it was proprietary. Feel free to accept this answer? (checkmark on left) Good luck. – Engineer Jul 8 '16 at 10:55