Editing Halo 3 Engine

{{Era|RW}}
{{Quote|Some of the test screenshots look exactly like their concept paintings.|[[Bungie]]}}
The '''''Halo 3'' Engine'''<ref name="igntrailer">[http://xbox360.ign.com/articles/706/706251p1.html '''E3 2k6''': ''Halo 3 Trailer Impressions'']</ref> is a game engine developed by [[Bungie|Bungie Studios]] and utilized in ''[[Halo 3]]'' and ''[[Halo 3: ODST]]''. Its unique features include advanced graphics technologies such as [[wikipedia:High Dynamic Range|high dynamic range]], global lighting and [[Wikipedia:Depth of field|depth of field]] effects within cutscenes.<ref>[http://www.1up.com/do/newsStory?cId=3158071 '''1 Up''': ''Bungie Says Halo 3 Graphics are Coming Together'']</ref>

==Artificial intelligence==
===Task trees===
In ''Halo 3''<nowiki/>'s AI system, squads are given a set of tasks, with each task having priority levels and sub-tasks.<ref name="bnetpub-betterbattle">[http://halo.bungie.net/Inside/publications.aspx#ctl00_rightSideContent_publicationRepeater_ctl13_publicationBookmark '''Bungie.net: Publications:''' ''Building a Better Battle: HALO 3 AI Objectives'']</ref> Squads are "poured in at the top" of a [[Wikipedia:Tree structure|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<ref name="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 name="bnetpub-betterbattle"/>

===Behavior trees===
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 name="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 name="bnetpub-betterbattle"/> 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:<ref name="bnetpub-betterbattle"/>
#Consider a subtree fragment
#Determine which children [tasks] are active
#*Squads in inactive tasks [are] assigned back up to [the] parent [task]
#Consider top priority group
#Collect squads to attempt to distribute [their members across tasks]
#*Squads currently in parent [task]
#*Squads in lower-priority tasks
#Distribute Squads
#[[Wikipedia:Recursion|Recurse]] for children in top priority-group
#Iterate to next "priority group"

In mathematical notation, the squads are expressed<ref name="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 name="bnetpub-betterbattle"/>

The cost function (<var>H</var>(<var>F</var>)) gave Bungie "a basis for choosing one distribution over another".<ref name="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 name="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 name="bnetpub-betterbattle"/>
 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.<ref name="bnetpub-betterbattle"/>
;Filters
:Particular tasks are only available to specific types of personnel. For example, only [[Jiralhanae|Brutes]] can drive [[Type-26 Ground Support Aircraft|Banshees]], and only [[Kig-yar|Jackals]] can act as [[Sniping|snipers]].

==Collision detection==
''Halo 3'''s engine uses ''[[Wikipedia:Collision detection#A posteriori versus a priori|a posteriori]]'' [[Wikipedia:Collision detection|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 Mode|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|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/Tricks#Method C|Forge Floating Objects]] [[Forge/Tricks|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''<nowiki/>'s [[Matchmaking]] operates by categorizing groups (parties) of players as ''searchers'' and ''gatherers''.<ref name="bnetpub-matchmaking">[http://halo.bungie.net/Inside/publications.aspx#ctl00_rightSideContent_publicationRepeater_ctl10_publicationBookmark '''Bungie.net: Publications:''' ''E Pluribus Unum: Matchmaking in HALO 3'']</ref> 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|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:
#Look for an optimum match. If necessary, expand analog filters slightly.
#Ignore binary filters.
#Expand analog filters as much as possible, and relax restrictions on connection quality.
#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 [[kig-yar point defense gauntlet|some cases]]).

Character models are elastic at some points, a trait that is clearly demonstrated by the [[Character stretch glitch|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 [[SPARTAN-II Program|Spartans']] and [[UNSC Marine Corps|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 [[Forge/Tricks#Floating Objects|floating]] [[Forge Objects|Crates]] and [[Fusion core|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.<ref>[http://halo.bungie.net/News/content.aspx?type=topnews&link=h3forgeobjects '''Bungie.net''': ''Halo 3 How-to: Forge Object Editing'']: "''Objects are sensitive things, and consider themselves disturbed if they are moved, picked up, or destroyed.''"</ref> 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. [[Wikipedia:Motion blur|motion blurring]] effects, initially absent from the beta version of the game, were added in the release version.<ref>[http://www.atomicmpc.com.au/article.asp?CIID=97254 '''Atomic MPC''': ''Halo 3 - Review - Console Gaming'']</ref>[[Wikipedia:Normal mapping|Normal]], [[Wikipedia:Bump mapping|bump]], and [[Wikipedia:Parallax mapping|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.<ref>[http://halo.bungie.net/News/content.aspx?type=topnews&cid=12834 '''Bungie.net''': ''Bungie Weekly Update: 10/05/07''] - '''BlatentB:''' "What happened to the real time reflections on Master Chiefs visor?" '''Frankie:''' "Nothing. They’re still in the game engine, but they’re not really much use, and are kind of a waste of CPU, so in many instances, MP for example, we save resources for more important stuff by using cube maps."</ref> The game has a [[Wikipedia:Draw distance|draw distance]] of roughly ten miles (sixteen kilometers).

===Hall of mirrors effect===
{{Main|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 [[Wikipedia:Framebuffer|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 [[campaign#Cooperative|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.

==Sources==
{{Ref/Sources}}

==See also==
*[[Havok (software)|Havok]]
*[[Slipspace Engine]]

[[Category:Halo 3]]
[[Category:Halo 3: ODST]]
[[Category:Development]]