Integer vs. Floating Point Worlds


The rigid chess-like, integer-based position system of Civilization has been discarded in favor of a world of free-roaming units in a floating point world, right? Not necessarily. Upon first glance, Warcraft II looks like a fully floating point world:

Screenshot of Warcraft II, published by Blizzard Entertainment.

However, closer inspection reveals the underlying square regions:

Blizzard Entertainment's art department did an effective job of hiding the underlying grid, but a grid still clearly exists. For Warcraft II, the programming advantages of regular grid locations far outweighed the game play advantages of a floating-point world. The integer grid makes collision detection a simple boolean check and pathfinding can be immediately reduced to ordered graph searching.

Graphically, this game is just Civilization in disguise. The game world consists of 2D landscape images that can be tiled seamlessly, with special tiles at the edges of regions, such as the tiles at the edge of the tree lines. The units in the game are just another type of 2D tile.

Drawing a series of self-contained square image tiles is easy, but it gets more complicated when the tiles are allowed to overlap. The tiles may be larger than a single grid square, but drawing them from the top of the screen down, or back-to-front order, results in the approximately correct 3D occlusion. A closer look at two of the units will illustrate this:

The green axe-wielding warrior's horned helmet is drawn in front of the horse-mounted knight due to the back-to-front ordering of the 2D images.

The grid is further hidden by the unit movement system. Units don't just hop from one square to the next. Instead, they walk at a certain pace across the game map. Behind the scenes, units probably move from the center of one grid square to the next and cannot stop in between positions. Each grid position would likely have three states: occupied, unoccupied, and about to be occupied by unit X. If a unit wanted to move to a particular grid location, the unit would first check if the square was occupied. If it was unoccupied, the unit would claim that square and begin to move toward it. If the square was already occupied or had already been claimed by another unit, the unit would have to wait or choose another square.

There are a few airborn units in the game. They follow the grid position as well, but they are allowed to fly over a grid position that is already occupied by a land unit. However, two air units cannot occupy the same grid position. This would indicate that an identical but separate grid position system exists for air units.

This system would maintain the simplicity of integer-based position systems while providing the illusion of a free-roaming floating point world. In practice, it's a bit obvious that units can only stop at the center of grid squares and that they only move in the eight compass directions, but it rarely detracts from the quality of game play.

The grid system also dictates the size of game objects. The buildings in Warcraft II occupy 3x3 blocks of grid squares. A single unit takes up a single grid square. Therefore, conventional logic tells us that every building is the size of nine people arranged in three rows of three people. This obviously isn't the case in the real world, but it's mostly acceptable in the game world.

This is all well and good, but are these techniques sufficient for more recent games? Consider Fire and Darkness:

Screenshot of Fire and Darkness, published by Singularity Software.

While this game has advanced far beyond the simple 2D images of Warcraft II, does it still have an underlying position grid? The game's ground units move with a freedom that is not possible in Warcraft II. They appear to be able to roam to any position in the game world and travel in any direction. This seems to indicate that if a grid exists, it is much more relaxed than in Warcraft II. Adding to the complexity are various air units that fly about in rather realistic fashion. These units appear to have inertia built into their movement system and they can divebomb and climb to various altitudes. Their freedom of altitude most likely means that the dual land grid/air grid system of Warcraft II would not be sufficient. If an underlying grid exists in Fire and Darkness, it is well hidden by the programmers.

The main function of the Warcraft II grid was to minimize the difficulties involved in moving units. Unit position tracking, collision avoidance, and pathfinding were all efficiently supported by the simple grid. Fire and Darkness has the same needs, but obviously uses a much more complicated data structure.

Keeping track of unit positions could be done by flattening the 3D world into two dimensions. If there is no way for two units to be on top of one another, as might be the case if there were bridges in the game, then the 3D world could be flattened into a 2D world. A secondary structure would be required to track flying units, but that was Warcraft II's solution as well. However, Fire and Darkness might not be a candidate for this technique. All of the units are futuristic and can climb vertical walls and cliffs. It is entirely possible that two units could be climbing the same cliff face and be positioned such that their 2D coordinates are identical. If this is indeed possible in the game, then a 3D data structure such as a binary space partioning tree or octree would be required to track positions.

Whether a 2D or 3D data structure is used, it needs to allow for fast collision testing. A unit position tracking system is useless if it cannot quickly determine which units are in the immediate vicinity or when a collision is about to occur. Without such collision testing, units would drive straight through other units or buildings.

The last problem is unit pathfinding. Pathfinding algorithms require that the game world be discretized in a 2D fashion. If a game uses a complicated 3D data structure, then it may be extremely difficult to translate that information to the pathfinder.

Different games will demand different requirements of their position tracking systems. Whether it is a 2D or 3D system or if it is integer or floating point based, the system must work smoothly and efficiently with the game. Every moving object in the game will be completely reliant on this system. Needless to say, matching the right system with a game is one of the most important programming decisions to be made.


Back to the index

kdmukai@princeton.edu
Last updated: 05/02/99 10:34 PM

All files Copyright (C) 1999 Keith Mukai