Geometry in Action

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.

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.