• Welcome to the Internet Infidels Discussion Board.

Video Games - Game-World Geometries

 
 
 
lpetrich

lpetrich

Contributor
Joined
Jul 27, 2000
Messages
26,849
Location
Eugene, OR
Gender
Male
Basic Beliefs
Atheist
I will here discuss the geometries of video-game game worlds.

I first consider two-dimensional ones, ones with the geometry of a flat surface. These ones have two main kinds of viewpoint, vertical and horizontal. A third one, oblique or axonometric, with an intermediate viewpoint, is essentially a variant of vertical viewpoint. Board games have been played for centuries, and they are essentially 2D with vertical viewpoints.

Many 2D games have only a partial view of the game world, a view of only a certain region. This view window is usually controlled by the player, whether directly or indirectly. A common form of indirect control is moving the game's player character, with the view window moving to stay centered on that character. Horizontal-viewpoint games with that feature are often called sidescrollers, from the view window moving sideways.

The first video games used simple geometric shapes, but by the late 1970's, sprites became common, small pictures of characters and scenery and the like that are overlaid onto the game-world display. The first game console to use sprites was the Fairchild Channel F, released in 1976, though the most successful early sprite user was the Atari 2600, released the next year.
 
From two dimensions I continue to the full three dimensions of space geometry.

The first 3D video game that I could discover is the arcade game "Night Driver" from 1976. It showed white roadside posts on a black background. It was thus the first racing game.

That was very limited, and likely the first to show detailed objects was "Battlezone" from 1980. It was a tank vs. tank combat game with a landscape with cubes and pyramids and distant mountains, all done in wireframe. One's viewpoint is at one's player character, one's tank, thus being a first-person viewpoint. Battlezone was thus the first first-person shooter.

These games use what may be called outdoor game engines, engines adapted for outdoor scenes, though they can also be used for indoor scenes. Flight simulators, city simulators (SimCity, etc.), nation simulators (Civilization, etc.), and army vs. army games all use outdoor engines. Outdoor engines are evidently an elaboration of vertical-view and oblique-view 2D game engines.

Fully 3D terrain started to appear in the late 1990's, with games like "Myth: the Fallen Lords" in 1997. That game is an army vs. army game, and in it, you command an army against an enemy army or against rival players' armies. In Myth and similar games, the terrain is specified with a heightmap, a 2D array of height values. As one might expect, one can create a heightmap with an image file. Between the points of the heightmap, the engine creates terrain-surface polygons.

An alternative approach is to use voxels, what one calls the pixels of a 3D raster image. But that has not been very common.
 
From sidescrollers comes indoor 3D games, as they might be called.

I will divide them into generations, and for each one, I will list some exemplars.

The first generation has a constant floor and ceiling heights and vertical walls laid out on a rectangular grid. "Wolfenstein 3D" 1992, "Ultima Underworld"(?) 1992, "Pathways into Darkness" 1993.

The second generation has a gameworld that is divided into interconnected rooms with arbitrary heights of horizontal floors and ceilings and arbitrary orientations of vertical walls. "Doom" 1993, "Marathon" 1994, "Dark Forces" 1995, "Duke Nukem 3D" 1996.

The third generation has a gameworld that has arbitrary polygonal surfaces. "Quake" 1996, "Unreal" 1998.

Though best adapted to indoor scenes, one can do outdoor scenes with these kinds of engines, and some more recent engines are hybrids, with indoor engines for buildings and outdoor engines for the surrounding landscape. Like in "Halo" 2001.


Why the restricted geometry? That is to reduce the amount of calculation that one has to do while rendering the gameworld. In general, one has to shoot a ray from one's camera in each display pixel's gameworld direction, and find out where that ray hits. In general, this requires a *lot* of calculation, and a compromise that gives reasonably good 3D scenes is to use flat surfaces and go from gameworld space to display space with a stereographic projection, as it's called. One then only has to do only one division per pixel.

Stereographic projection = (sideways position) / (line-of-sight position)

Other projections require more computation.


That describes the third generation of 3D indoor engines, but the earlier generations are more restricted than that. The reason for that is to lower the amount of computation needed. If one uses a horizontal view direction, then all the vertical lines of pixels in a wall require only one division per line. Likewise, all the view-space horizontal lines of pixels in a floor or a ceiling require only one division per line. One can even pan up and down by moving the view window up and down while keeping the view direction horizontal.


An important feature of video-game engines, especially 3D ones, is visibility calculation, trying to render only what is visible, like what is not hidden by other objects (occlusion). That can be a very complicated subject, I must concede.
 
As to inhabitants of 3D gameworlds, these were originally sprites, but with their rendered sizes scaled appropriately.

As with 2D games, one does animations of sprites in flipbook fashion, going through a series of pictures and looping as needed. One typically has a separate animation for each kind of action. This is something like what is done in many children's cartoon series like the Hanna-Barbera ones, series that use a set of canned animations for walking and speaking and other actions (What RUINED Hanna-Barbera? - YouTube).

For 3D games, one uses separate animations for different directions, sometimes as many as eight. One can sometimes find such cheating as using mirror-image animations for side views, thus using the same set of pictures for both sides. One can also find a shortcut for making the sprite pictures: rendering 3D models in different poses and from different view directions.

The next step is to use 3D models in the game itself. In the mid 1990's, 3D-model inhabitants started becoming common, with Quake and Tomb Raider having some of the first ones. For animation, Quake goes through sets of model vertices for different poses, while Tomb Raider uses skeletal or parametric animation, with the model vertices being controlled with parameter sets or "bones", and the animation data being stored for the bones. The earlier Tomb Raiders used a separate model for each part, much like a marionette, but more recent skeletal animation has the bones control different vertices of the same model. Adding bones to a model is sometimes called boning or rigging.
 
The earlier Tomb Raiders had some oddities in their gameworlds' geometry. That geometry consists of several "rooms" with portals between them, and each room has a square grid in it, vertical walls, and floors and ceilings that can be slanted. This square grid is intended for making it easier to judge jumps, and Lara Croft, your player character, has to do a *lot* of them in the series.

The Tomb Raider series is also notable for a third-person or chase-cam viewpoint, where you look at your player character from outside. This is typical of 2D games, but it was 3D games that made this viewpoint stand out, from a first-person viewpoint being common in them.

The earlier Tomb Raiders used a Lara Croft model with 15 main parts: head, torso, hips, upper arms, lower arms, hands, thighs, calves, feet. All but the first one also had a segmented ponytail model. The parts are arranged in a hierarchy:

  • Hips
    • Torso
      • Head - ponytail parts
      • Left arm - upper arm, lower arm, hand
      • Right arm - upper arm, lower arm, hand
    • Left leg - thigh, calf, foot
    • Right leg - thigh, calf, foot
The main parts have canned animations, while the ponytail's animations are calculated using game-physics algorithms. Thus, the ponytail gets blown in wind, and when Lara falls, it points straight up.
 
no one I ever knew realized in the 80's how important trigonometry and vector math would be to them when computers grew up.
Speaking of which, if anyone knows a good site that provides a "cheat sheet" for vector calculations and trig tricks, I'd greatly appreciate it. btw, the "math is fun" website is not good for 3D vector info. Trig pretty good there though.
 
Looks interesting. I especially like the collision testing for fractal surfaces.

First-generation indoor engines:
Wolfenstein 3D's map renderer - YouTube

It shoots a ray in each horizontal direction until that ray meets a wall.

Second-generation indoor engines:
Doom WASN'T 3D! - Digressing and Sidequesting - YouTube
ADG Filler #48 - Is the Doom Engine a Raycaster? - YouTube

It uses a scheme called "binary space partitions" (BSP's) to find visibility. That's splitting the map space in two, then repeating that operation until all the map geometry is suitably accounted for in the splitting. It is now organized for an inward-to-outward search or an outward-to-inward one.

Bungie's Marathon engine is also second-generation, and it uses a different approach: portal rendering. Each polygon / sector / room is connected to its neighbors, and one does visibility by looking through these connections and repeating this operation as long as connections continue to be visible.


Though first-generation and second-generation share horizontal view with sidescrollers, they use horizontal maps that are extruded in the vertical direction. This horizontal geometry makes them much like 2D vertical-view and oblique-view games.

The video on Wolf3D noted that some Legend of Zelda levels do elevation by fakery. They are all 2D, but some terrain allows movement in only one direction, and it is given the appearance of a wall.

The Marathon engine allows rooms to be above other rooms, and for rooms to occupy the same space -- "5D space". The Doom engine does not allow that, however. Doom's successor Quake is full 3D, and it uses full-3D BSP's. Though one can have rooms above other rooms in it, one cannot have Marathon-style interpenetrating rooms.
 
I must note that first-generation and second-generation indoor engines often have level maps that can be displayed, but that third-generation ones don't. That is a feature that I missed in Quake and Unreal and Half-Life, even though I'm sure that it is possible to create such maps with those game engines. I recall id Software coming out with some Doom 4(?) that had such a map, however.
 
You must log in or register to reply here.
Back
Top Bottom