10,007
edits
Halo 3 Engine: Difference between revisions
m
clean up, replaced: www.bungie.net → halo.bungie.net (4), typos fixed: re-assigned → reassigned (2)
m (clean up, replaced: www.bungie.net → halo.bungie.net (4), typos fixed: re-assigned → reassigned (2)) |
|||
| Line 5: | Line 5: | ||
==Artificial intelligence== | ==Artificial intelligence== | ||
===Task trees=== | ===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:// | 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 | 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."). | 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."). | ||
| Line 44: | Line 44: | ||
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"/> | 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 | 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"/> | The "greedy approach" to this system, expressed in [[Wikipedia:pseudocode|pseudocode]], is:<ref name="bnetpub-betterbattle"/> | ||
| Line 67: | Line 67: | ||
''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. | ''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 | 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. | A map's total size (including its unused areas) cannot exceed 100,000 world units along any of the standard three coordinate axes. | ||
==Matchmaking== | ==Matchmaking== | ||
''Halo 3''<nowiki/>'s [[Matchmaking]] operates by categorizing groups (parties) of players as ''searchers'' and ''gatherers''.<ref name="bnetpub-matchmaking">[http:// | ''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 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. | ||
| Line 78: | Line 78: | ||
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 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 | 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. | #Look for an optimum match. If necessary, expand analog filters slightly. | ||
#Ignore binary filters. | #Ignore binary filters. | ||
| Line 91: | Line 91: | ||
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. | 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:// | 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== | ==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:// | 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=== | ===Hall of mirrors effect=== | ||