Halo 3 Engine

"Some of the test screenshots look exactly like their concept paintings."

— Bungie

The Halo 3 Engine is a game engine developed by Bungie Studios and utilized in Halo 3 and Halo 3: ODST. Its unique features include advanced graphics technologies such as high dynamic range, global lighting and depth of field effects within cutscenes.

Artificial intelligence

Task trees

In Halo 3's AI system, squads are given a set of tasks, with each task having priority levels and sub-tasks. Squads are "poured in at the top" of a tree of tasks, and "filter down" through that tree. The effect is that individual combatants are assigned to complete the most important tasks first, with leftover personnel being assigned to less important tasks.

Individual tasks can "turn themselves on and off"; when a high-priority task is turned on, squad members are reassigned as necessary to ensure its completion. When a task is completed (and turned off), the squad members that were working on it are reassigned to any other tasks that need completion.

An example 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.

Behavior trees

The behaviors of an individual AI-controlled combatant are also represented as tree structures where each node is a self-describing behavior, such as "throw grenade" or "melee". The 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 behavior tree can be represented with a multi-level bulleted list:

• Make a decision
  • hide
    • find cover
  • fight
    • grenade
    • melee
    • shoot
  • search
    • uncover
    • pursue
  • idle
    • sleep

The specific algorithm

The specific algorithm has been described as:

1. Consider a subtree fragment
2. Determine which children [tasks] are active
   • Squads in inactive tasks [are] assigned back up to [the] parent [task]
3. Consider top priority group
4. Collect squads to attempt to distribute [their members across tasks]
   • Squads currently in parent [task]
   • Squads in lower-priority tasks
5. Distribute Squads
6. Recurse for children in top priority-group
7. Iterate to next "priority group"

In mathematical notation, the squads are expressed as a set S with n members; the tasks are expressed as a set T with m members. Bungie's goal was to find a mapping F(S)→T -- in other words, Bungie needed a function (F) 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 H(F) -- in other words, they needed to avoid assigning too many squads or personnel to a task, and they needed to make the function (F) as efficient as possible (with H measuring how much it "cost" to use F). The first part of that problem (respecting task-capacity constraints) was referred to as "bin-packing".

The cost function (H(F)) gave Bungie "a basis for choosing one distribution over another". 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". The only danger in attempting to minimize H(F) is that "AI can look really stupid with [the] wrong H(F)".

The "greedy approach" to this system, expressed in pseudocode, is:

while (S is not empty)
   find pair (s,t) that give the minimum H(s,t) for all S x T
   (where adding s to t would not exceed t’s capacity)
if (s,t)
   assign(s, t)
   capacity(t) = capacity(t) -size(s)
   S = S –s
else
   end

Refinements have also been made to that system; some are listed below.

Filters

Particular tasks are only available to specific types of personnel. For example, only Brutes can drive Banshees, and only Jackals can act as snipers.

Collision detection

Halo 3's engine uses a posteriori collision detection. The collision detection engine does not account for movement between two frames of animation, a fact that is clearly demonstrated by the Panoramic Camera's ability to accelerate and clip past a level's boundaries in Theater.

Level boundaries

Halo 3 utilizes an extensive system of invisible walls, kill barriers, and other means of forcing players to stay within a level's boundaries.

The game also seems to have an algorithm that can detect whether or not objects have bypassed the level boundaries. This algorithm is used to delete "lost" Forge items; to kill players that have exited the map; and to return the Theater camera to the nearest living player if it exits the map. This can be demonstrated by using the Forge Floating Objects trick to place a Teleporter past all apparent invisible walls and kill barriers in a level—using it will still (usually) result in an instant death even though no kill barriers were touched.

A map's total size (including its unused areas) cannot exceed 100,000 world units along any of the standard three coordinate axes.

Matchmaking

Halo 3's Matchmaking operates by categorizing groups (parties) of players as searchers and gatherers. Gatherers basically wait for searchers to join them. Searchers ask the Matchmaking service to find gatherers; once a searcher has a list of gatherers, it evaluates them.

When a party connects to Xbox Live and acts as a gatherer, it registers itself with the Matchmaking service. Once enough searchers have joined, the gatherer determines the proper game settings, assigns connection host status as needed, and starts the match.

When a party becomes a searcher, it sends queries to the Matchmaking service in an attempt to find gatherers. Matchmaking processes the queries and their contained parameters, sending a somewhat filtered list of gatherers back to the searcher. The searcher then evaluates each gatherer, looking for a suitable candidate. If a candidate is found, the searcher will join their game; otherwise, the searcher will search again.

When searching, a searcher will start looking for exact matches. Analog parameters, like EXP, are followed to the letter, as are binary parameters, like spoken language and possession of a map pack. As the search continues, the parameters expand—the searcher starts looking for imperfect matches as well. Search expansion occurs in four steps:

1. Look for an optimum match. If necessary, expand analog filters slightly.
2. Ignore binary filters.
3. Expand analog filters as much as possible, and relax restrictions on connection quality.
4. Keep searching intermittently, and switch to gatherer status.

The objective is to find games quickly, so lists of gatherers expire quickly. In an effort to "balance the ecosystem", Bungie gave gatherers the ability to stop gathering and change to searcher status.

Physics engine

The Halo 3 physics engine runs calculations on every frame of animation, similarly to the collision detection engine. The engine is capable of calculating, among other things, elasticity on portions of character models; and bullet ricochet (in some cases).

Character models are elastic at some points, a trait that is clearly demonstrated by the Character Stretch Glitch's presence in the game. The elasticity helps to improve realism at slower speeds. Only some parts of a character's model are elastic; if you look closely at screenshots of the aforementioned glitch, you will find that the rigid parts of Spartans' and Marines' armor do not stretch.

The physics engine utilizes an optimization found in many video game physics engines: objects that remain at rest for several seconds are temporarily exempted from physics calculations (but not collision detection) until they are disturbed again; this is why floating Crates and Fusion Coils can remain floating in the air until the round is restarted or the items are disturbed. An object is considered "disturbed" if it is moved, picked up (in Forge), or if something collides with it. The optimization is likely based on the premise that an object that isn't moving now isn't likely to move in the near future unless something moves it or it moves on its own.

Rendering technologies

Numerous advanced rendering technologies were employed with the new Xbox 360's processor. Within cutscenes, depth of field effects were utilized. motion blurring effects, initially absent from the beta version of the game, were added in the release version.Normal, bump, and parallax mapping were all used to increase surface and lighting detail without increasing models' polygon counts. Mostly-unused functionality for real-time reflections is also present. The game has a draw distance of roughly ten miles (sixteen kilometers).

Hall of mirrors effect

Main article: Hall of Mirrors

A common graphical side-effect of some glitches is the hall of mirrors effect, which in Halo 3 has a few unique quirks. The hall of mirrors effect is when nothing is rendered on a particular portion of a screen; because the framebuffer is not cleared between frames, whatever was rendered in the last frame of animation will show up in the "empty space" on the current frame. In Halo 3, when playing in co-op or multiplayer, the "empty space" will be filled up with whatever is on the other player's screen. Another Halo 3-specific quirk sometimes causes odd red and blue patterns to appear in the midst of a hall of mirrors effect.

Related links

• Havok
• Slipspace Engine