Download

Game Engine:

A game engine is the core software component of a computer video game or other interactive application with real-time graphics. It provides the underlying technologies, simplifies development, and often enables the game to run on multiple platforms such as game consoles and desktop operating systems such as Linux, Mac OS X, and Microsoft Windows. The core functionality typically provided by a game engine includes a rendering engine (''renderer'') for 2D or 3D graphics, physics engine or a collision detection (and collision response), sound, scripting, animation, artificial intelligence, networking, streaming, memory management, threading, and a scene graph. The process of game development is frequently economized by in large part reusing the same game engine to create multiple different games. Modern game engines are some of the most complex applications written, frequently featuring dozens of finely tuned systems interacting to ensure a finely controlled user experience. The continued refinement of game engines has created a strong separation between rendering, scripting, artwork, and level design. It is now common (as of 2003), for example, for a typical game development team to have several times as many artists as actual programmers.

Overview

Like other middleware solutions, game engines usually provide platform abstraction, allowing the same game to be run on various platforms including game consoles and personal computers with few, if any, changes made to the game source code. Often, game middleware is designed with a component-based architecture that allows specific systems in the engine to be replaced or extended with more specialized (and often more expensive) middleware components such as Havok for physics, FMOD for sound, or SpeedTree for rendering. Some game engines such as RenderWare are even designed as a series of loosely connected middleware components that can be selectively combined to create a custom engine, instead of the more common approach of extending or customizing a flexible integrated solution. However extensibility is achieved, it remains a high priority in games engines due to the wide variety of uses for which they are applied. Despite the specificity of the name, game engines are often used for other kinds of interactive applications with real-time graphical requirements such as marketing demos, architectural visualizations, training simulations, and modeling environments.

Some game engines only provide real-time 3D rendering capabilities instead of the wide range of functionality required by games. These engines rely upon the game developer to implement the rest of this functionality or assemble it from other game middleware components. These types of engines are generally referred to as a "graphics engine," "rendering engine," or "3D engine" instead of the more encompassing term "game engine." However, this terminology is inconsistently used as many full-featured 3D game engines are referred to simply as "3D engines." A few examples of graphics engines are: RealmForge, Ogre, Power Render, Crystal Space, Genesis3D, and JMonkey Engine. Modern game or graphics engines generally provide a scene graph, which is an object-oriented representation of the 3D game world which often simplifies game design and can be used for more efficient rendering of vast virtual worlds.

Hardware Abstraction

With the advent of hardware accelerated physics processing various physics API such as COLLADA and PAL became available to provide a software abstraction of the Physics processing unit of different middleware providers and console platforms.

Middleware Some companies now specialize in developing software suites known as "middleware." Middleware developers attempt to "pre-invent the wheel" by developing robust software suites which include many elements a game developer may need to build a game. Most middleware programs provide facilities that ease development, such as graphics, sound, physics and AI functions. DX Studio, Gamebryo and RenderWare are three such widely used middleware programs. Some middleware only do one thing, but do it more convincingly than general purpose engines. For example, SpeedTree was used to render the realistic trees and vegetation in the role-playing game The Elder Scrolls IV: Oblivion. Two widely-used packages that provide subsystems of functionality include Havok and several of RAD Game Tools' systems. Havok provides a robust physics simulation system and RAD Game Tools develops systems for video rendering, audio playback and 3D rendering. Some middleware contains full source code, others just provide an API reference for a compiled binary library. Some middleware programs can be licensed either way, usually for a higher fee for full source code.

SpeedTree forest-rendering middleware

MMOG Middleware

• RealmCrafter
• Multiverse Network
• Gamebryo
• Bigworld Technology
• HeroEngine

Principles of Real-Time 3D Computer Graphics

Thus, real-time graphics is oriented toward providing as much performance as possible for the lowest quality possible for a given class of hardware. Most video-games and simulators fall in this category of real-time graphics. As mentioned above, real-time graphics is currently possible due to the significant recent advancements in these special hardware components called graphics processing units (GPUs). These GPUs are capable of handling millions of triangles per frame and within each such triangle capable of handling millions or even billions of pixels (i.e. generating these pixel colors). Current DirectX 10 class hardware are the most advanced GPUs capable of generating complex effects on the fly (i.e. in real-time) such as shadow volumes, motion blurring, real-time triangle generation among many others. Although the gap in quality between real-time graphics and traditional off-line graphics is narrowing, the accuracy is still a far-cry to be justified in the near-future.

Why real-time computer graphics?

In the case of real-time interactive computer graphics, usually a user is in control of what is about to be drawn on the display screen; the user typically uses an input device to provide feedback to the system - for example, wanting to move a character on the screen - and the system decides the next frame based on this particular instance of action. Usually the display is far slower (in terms of the number of frames per second) in responsiveness than the input device (in terms of the input device's response time measured in ms). In a way this is justified due to the immense difference between the infinitesimal response time generated by a human-being's motion and the very slow perspective speed of the human-visual system; this results in significant advancements in computer graphics, whereas the advancements in input devices typically take a much longer time to achieve the same state of fundamental advancement (for e.g. the current Wii controller), as these input devices have to be extremely fast in order to be usable.

Another important factor controlling real-time computer graphics is the combination of physics and animation. These techniques largely dictate what is to be drawn on the screen - or more precisely, where to draw certain objects (deciding their position) on the screen. These techniques imitate the behavior (the temporal dimension, not the spatial dimensions) seen in real-world to a degree that is far more realistic than and compensating computer-graphics' degree of realism.

Physics Engine

Finally, hybrid methods are possible that combine aspects of the above paradigms.

In most computer games, speed of simulation is more important than accuracy of simulation. Typically most 3D objects in a game are represented by two separate meshes or shapes. One of these meshes is a highly complex and detailed shape which the player sees in the game, for example a vase with elegant curved and looping handles. However, for purposes of speed, a second highly simplified invisible mesh is used to represent the object to the physics engine. To the physics engine, the object may be processed as nothing more than a simple tall cylinder. It is therefore impossible to insert a rod or fire a projectile through the handle holes on the vase, because the physics engine does not know the handles exist and only processes the rough cylindrical shape. The simplified mesh used for physics processing is often referred to as the collision geometry. This may be a bounding box, sphere, or convex hull. Engines that use bounding boxes or bounding spheres as the final shape for collision detection are considered extremely simple. Generally a bounding box is used for broad phase collision detection to narrow down the number of possible collisions before costly mesh on mesh collision detection is done in the narrow phase of collision detection. In the real world, physics is always active. There is a constant Brownian motion jitter to all particles in our universe as the forces push back and forth against each other. For a game physics engine, such constant active precision is unnecessary and a waste of the limited CPU power. In the 3D virtual world Second Life, if an object is resting on the floor and the object does not move beyond a certain minimal distance in about two seconds, then the physics calculations are disabled for the object and it becomes frozen in place. It remains frozen until a collision occurs with some other actively physical object, and that reactivates physics processing for the object. This freezing of stable non-moving objects allows the physics engine to conserve processing power and increase the framerate of other objects currently in motion, but can lead to unusual problems such as a huge slow pendulum freezing in place on the upswing, as it slows down and starts to reverse direction. The primary limit of physics engine realism is the precision of the numbers representing the position of an object and the forces acting on that object. When the precision is too low, errors can creep into the calculations due to rounding, causing an object to overshoot or undershoot the correct position. These errors are compounded in situations where two free-moving objects are fitted together with a precision that is greater than what the physics engine can calculate. This can lead to an unnatural buildup energy in the object due to the rounding errors, that begins to violently shake and eventually blow the objects apart. Any type of free-moving compound physics object can demonstrate this problem, but it is especially prone to affecting chain links under high tension, and wheeled objects with actively physical bearing surfaces. Higher precision reduces the positional/force errors, but at the cost of greater CPU power needed for the calculations. Another unusual aspect of physics precision involves the framerate, or the number of moments in time per second when physics is calculated. Each frame is treated as separate from all other frames, and the space between frames is not calculated. A low framerate and a small fast-moving object leads to a situation where the object does not move smoothly through space but in fact seems to teleport from one point in space to the next point in space as each frame is calculated. At sufficiently high speeds a projectile will miss a target, if the target is small enough to fit in the gap between the calculated frames of the fast moving projectile. In Second Life this problem is resolved by making all projectiles as if they were arrows; a long invisible shaft trails behind the bullet so that as the bullet teleports forward, the shaft is long enough to cover the gap between successive teleports of the bullet and collide with any object that might fit between the calculated frames. Physics based character animation in the past only used rigid body dynamics because they are faster and easier to calculate, but modern games and movies are starting to use soft body physics now that it is possible. Soft body physics are also used for particle effects, liquids and cloth. Some form of limited Fluid dynamics simulation is sometimes provided to simulate water and other liquids as well as the flow of fire and explosions through the air.

Collision Detection

In physical simulation, we wish to conduct experiments, such as playing billiards. The physics of bouncing billiard balls are well understood, under the umbrella of rigid body motion and elastic collisions. An initial description of the situation would be given, with a very precise physical description of the billiard table and balls, as well as initial positions of all the balls. Given a certain impulsion on the cue ball (probably resulting from a player hitting the ball with his cue stick), we want to calculate the trajectories, precise motion, and eventual resting places of all the balls with a computer program. A program to simulate this game would consist of several portions, one of which would be responsible for calculating the precise impacts between the billiard balls. This particular example also turns out to be numerically unstable: a small error in any calculation will cause catastrophic changes in the final position of the billiard balls. Video games have similar requirements, with some crucial differences. While physical simulation needs to simulate real-world physics as precisely as possible, video games need to simulate real-world physics in an acceptable way, in real time and robustly. Compromises are allowed, so long as the resulting simulation is satisfying to the game player.

Some iterate the linear interpolation (Newton's method) to calculate the time of collision with a much higher precision than the rest of the simulation. Collision detection utilizes time coherence to allow ever finer time steps without much increasing CPU demand. After an inelastic collision, special states of sliding and resting can occur and, for example, the Open Dynamics Engine uses constrains to simulate them. Constrains avoid inertia and thus instability. Implementation of rest by means of a scene graph avoids drift. In other words, physical simulators usually function one of two ways, we shall refer to them as the a posteriori and a priori methods. In addition to the a posteriori and a priori distinction, almost all modern collision detection algorithms are broken into a hierarchy of algorithms.

In the a priori methods, we write a collision detection algorithm which will be able to predict very precisely the trajectories of the physical bodies. The instants of collision are calculated with high precision, and the physical bodies never actually interpenetrate. We call this a priori because we calculate the instants of collision before we update the configuration of the physical bodies.

The main benefits of the a posteriori methods are as follows. In this case, the collision detection algorithm need not be aware of the myriad physical variables; a simple list of physical bodies is fed to the algorithm, and the program returns a list of intersecting bodies. The collision detection algorithm doesn't need to understand friction, elastic collisions, or worse, non-elastic collisions and deformable bodies. In addition, the a posteriori algorithms are in effect one dimension simpler than the a priori algorithms. Indeed, an a priori algorithm must deal with the time variable, which is absent from the a posteriori problem.

On the other hand, a posteriori algorithms cause problems in the ''fixing'' step, where intersections (which aren't physically correct) need to be corrected. In fact, there are some who believe that such an algorithm is inherently flawed and unstable.

The benefits of the a priori algorithms are increased fidelity and stability. It is difficult (but not completely impossible) to separate the physical simulation from the collision detection algorithm. However, in all but the simplest cases, the problem of determining ahead of time when two bodies will collide (given some initial data) has no closed form solution -- a numerical root finder is usually involved.

Some objects are in resting contact, that is, in collision, but neither bouncing off, nor interpenetrating, such as a vase resting on a table. In all cases, resting contact requires special treatment: If two objects collide (a posteriori) or slide (a priori) and their relative motion is below a threshold, friction becomes stiction and both objects are arranged in the same branch of the scene graph; however, some believe that it poses special problems in a posteriori algorithm.

Video Games

For a long time, video games had a very limited number of objects to treat, and so checking all pairs was not a problem. In two-dimensional games, in some cases, the hardware was able to efficiently detect and report overlapping pixels between sprites on the screen. In other cases, simply tiling the screen and binning each sprite into the tiles it overlaps provides sufficient pruning, and for pair-wise checks, bounding rectangles or circles are used and deemed sufficiently accurate.

Three dimensional games have used spatial partitioning methods for n-body pruning, and for a long time used one or a few spheres per actual 3d object for pair-wise checks. Exact checks are very rare, except in a few genres such as simulation. Even then, exact checks are not necessarily used in all cases.

Because games use simplified physics, stability is not as much of an issue. Almost all games use a posteriori collision detection, and collisions are often resolved using very simple rules. For instance, if the protagonist finds himself embedded in a wall, he might be simply moved back to his last known good location. Some games will calculate the distance the protagonist can walk before getting embedded into a wall, and only allow him to move that far.

A slightly more sophisticated and striking effect is ragdoll physics. If a video game character is disabled, instead of playing a preset animation, a simplified skeleton of the character is animated as if it were a rag doll. This rag doll falls limp, and might collide with itself and the environment, in which case it should behave appropriately.

In many cases for video games, approximating the protagonists by a point is sufficient for the purpose of collision detection with the environment. In this case, binary space partition trees provide a viable, efficient and simple algorithm for checking if a point is embedded in the scenery or not. Such a data structure can also be used to handle "resting position" situation gracefully when a protagonist is running along the ground. Collisions between characters, and collisions with projectiles and hazards, are treated separately.

A robust simulator is one that will react to any input in a reasonable way. For instance, if we imagine a high speed racecar video game, from one simulation step to the next, it is conceivable that the cars would advance a substantial distance along the race track. If there is a shallow obstacle on the track (such as a brick wall), it is not entirely unlikely that the car will completely leap over it, and this is very undesirable. In other instances, the "fixing" that the a posteriori algorithms require isn't implemented correctly, and characters find themselves embedded in walls, or falling off into a deep black void. These are the hallmarks of a mediocre collision detection and physical simulation system.

Referances taken from Wikipedia. All text is available under the terms of the GNU Free Documentation License.