Cellular Automata

From RogueBasin
Jump to navigation Jump to search

Overview

Games based purely on Cellular Automata are unusual, that is, strict use of cells without continuous movement. There is for instance Halls of the Things created in 1982 that used this approach. A later famous game is Diablo I. On the other hand many games feature many of the mechanics of a Cellular Automata. There are several good sources how to build these for instance here. The following is only a short description from a Rogue/game perspective.

Aether/Cells

Every Automata starts with the cell design. Any nodes system works, but it is recommended to use convex cells of equal size. The cells are commonly contained in a set of computer arrays that can be arranged in planes, rooms or in hierarchy. The size and shape of cells are very important to the design. However cell structure can be modified after creation. Most popular cell size in Rogues is cell size equal to the player size. The exact contents of the cell is also of importance, values, pointers and objects are common. Values as cell contents is the simplest and easiest to use when programming.

Clock

All Automatas need some time of clock that creates the next time frame. The classic method of copying all data and creating a new copy is not very practical for rogue games. A working method is to first mark every visible cell and then process each marked cell only once. It is possible to process cells without tracking previous computed cells or copying cells, however this needs very careful selection of rules and processing order.

Rules/Laws of Nature

Very basic if cells contain simple values. Each rules simply looks at adjacent rules and is applied or not applied. If cells are objects or indexes processing can become complex. It is always possible to add more cells only containing values if the rule system becomes complex when the cells contain complex vales (such as objects or are indexes). The order of how cells are being processed and how nodes are structured influence the logic.

Sprite Based

Very common for 2D Games but also possible for 3D Games. These games commonly have a game map, with static elements that are the same as a Cellular Automata and a few free moving 2D elements (or 3D) using some ad hoc physics system. Because it is possible to always add more cells and add cells within cells is is straightforward to map Cellular mechanics to and from the moving 2D elements (or 3D). These engine have a long history and have been based on hardware see detailed description.

Binary Space Partitioning

A space of convex shapes can be created using BSP and these convex shapes can be further divided by the BSP into convex and regularly sized cells. Details on BSPs can be found here. The point of this space that it easily allows creating ramps and irregular shapes that work with straight forward physics equations. BSP games were popular in the 90s as they worked with the 3D low polygon count at the time. The games in question were not considered Celullar Automatas on the other hand physics in these games from the 90s was very similar to an Automata built on BSP

Raster Display

Some games were based in part or entirely on the properties of the screen and the screen buffers. These worked roughly like Automatas using cell size equal to screen pixel size.