Editing Halo 3 Engine

An example{{Ref/Reuse|bnetpub-betterbattle}} is the task of guarding an indoor environment. This task is broken into sub-tasks (such as guarding a main entrance and guarding a hallway). These sub-tasks are assigned priorities ("The most important thing is to guard the door, but if you can, also guard the hallway"), and each is broken into additional sub-tasks ("Guarding the hallway means guarding the front, the middle and the rear of the hallway.").

In addition to specific task trees, there are also three general stages of battle: advance, retreat, and make a last stand.{{Ref/Reuse|bnetpub-betterbattle}}

The behaviors of an individual AI-controlled combatant are also represented as tree structures where each [[Wikipedia:Node (computer science)|node]] is a self-describing behavior, such as "throw [[grenade]]" or "[[melee]]".{{Ref/Reuse|bnetpub-betterbattle}} The [[Wikipedia:Tree (data structure)#Terminology|root node]] of the tree is simply the beginning of a combatant's decision-making process. That node's children are the general tasks that the combatant is performing ("hide", "fight", etc.). Those nodes' children are specific behaviors. An example{{Ref/Reuse|bnetpub-betterbattle}} behavior tree can be represented with a multi-level bulleted list:

The specific algorithm has been described as:{{Ref/Reuse|bnetpub-betterbattle}}

In mathematical notation, the squads are expressed{{Ref/Reuse|bnetpub-betterbattle}} as a [[Wikipedia:Set|set]] <var>S</var> with <var>n</var> members; the tasks are expressed as a set <var>T</var> with <var>m</var> members. Bungie's goal was to find a mapping <var>F</var>(<var>S</var>)→<var>T</var> -- in other words, Bungie needed a function (<var>F</var>) that would effectively assign squads to tasks. There were two parts to this function: the developers needed to respect all task-capacity constraints and minimize the cost function <var>H</var>(<var>F</var>) -- in other words, they needed to avoid assigning too many squads or personnel to a task, and they needed to make the function (<var>F</var>) as efficient as possible (with <var>H</var> measuring how much it "cost" to use <var>F</var>). The first part of that problem (respecting task-capacity constraints) was referred to as "bin-packing".{{Ref/Reuse|bnetpub-betterbattle}}

The cost function (<var>H</var>(<var>F</var>)) gave Bungie "a basis for choosing one distribution over another".{{Ref/Reuse|bnetpub-betterbattle}} Basically, not every member of a squad will be performing the same tasks or behaviors in a given situation. Different tasks and behaviors will be distributed amongst the squad's members. Bungie needed a way to choose between two different distributions. The cost function allows the game to weigh different concerns—for example, the squads "don't want to travel far" but do "want to act coordinated" and "get near the player".{{Ref/Reuse|bnetpub-betterbattle}} The only danger in attempting to minimize <var>H</var>(<var>F</var>) is that "AI can look really stupid with [the] wrong <var>H</var>(<var>F</var>)".

The "greedy approach" to this system, expressed in [[Wikipedia:pseudocode|pseudocode]], is:{{Ref/Reuse|bnetpub-betterbattle}}

Refinements have also been made to that system; some are listed below.{{Ref/Reuse|bnetpub-betterbattle}}