Video and Computer Game Programming
Video game programming is closely related to
computer graphics,
but has its own special needs -- often speed is much more important
than verisimilitude. Therefore rather than using slow but accurate
graphics techniques such as radiosity, video game engines are typically
based on simpler techniques such as raycasting, using binary space
partitions as a primary geometric data structure.
Simulation of non-player-characters in video games
often requires some geometric computation, for instance of
short paths around obstacles.
There may also be the possibility of a connection with
graph drawing,
for automated layout of adventure game maps.
- For basic theoretical work on BSP trees, see two
papers by F. Yao and M. S. Paterson: "Efficient binary space
partitions for hidden-surface removal and solid modeling", 5th
Symp. Comp. Geom. (1989) 23-32 and Disc. Comp. Geom. 5 (1990)
485-503. and "Optimal binary space partitions for orthogonal
objects", 1st SODA (1990) 99-113. See also E. Torres,
"Optimization of the binary space partition algorithm (BSP) for the
visualization of dynamic scenes", Eurographics (1990) 507-518, and
Agarwal et al., "Binary space partitions for fat rectangles, 37th FOCS (1996).
Apparently the question of tight complexity bounds for planar
BSP trees remains open.
- The BSP tree FAQ is largely devoted to implementation issues,
and includes a description of BSP usage in DOOM.
- Game
programming resources, C. Ericson, Neversoft Entertainment.
- The
Nexus game programming page.
- Ian Parberry's
Laboratory for Recreational Computing.
- 3d Engines
for real-time graphics.
- US
Patent 3889107 covers the use of binary space partitions for hidden
surface removal, shadow calculation, and collision detection.
Part of
Geometry in Action,
a collection of applications of computational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Semi-automatically
filtered
from a common source file.
