Game Development Reference
FIG 5.20 All possible maze
configurations and an example
NPC DNA string.
front and right, the action tells the NPC to move forward. This is obviously a
bad choice, but nonetheless, the NPC has nothing to go on but the actions
provided in its DNA. The fewer times an NPC's DNA leads it into a wall, the
farther it will get exploring the maze.
In the beginning, 100 NPCs are created each with random DNA setting. The
NPCs are allowed to explore the maze. The ones that get the farthest will have
DNA sequences that allow them to move farther. These are the ones kept for
breeding. Now and then mutations are thrown in to create DNA sequences
that may not occur from the natural selection process. Results from 10
generations of this program are shown in Figure 5.21 . Feel free to download
the code and play around with it for yourself.
5.10 Cellular Automata
Many strategy and simulation games are played out on a grid. The best
example is SimCity . The AI running beneath SimCity is a cellular automata. In
short, a cellular automata is a grid of cells with associated values where each
value is updated constantly by the value in neighboring cells. SimCity uses
this mechanism to decide what happens in associated cells based on what
the player is doing. For example, if the player puts a nuclear power plant in
a particular location, any mansions in surrounding cells become worthless
and soon the occupants will move out. Cells between an apartment block
and the bus stop will affect the distance the occupants must travel to work
and also the occupancy rate. Such a simple AI mechanic can create some
very complex-looking relationships.
One of the most famous cellular automata is the Game of Life developed by
researcher John Conway in 1970. It is an infinite 2D grid of cells. Each cell
can be in one of two states: dead or alive. The state of the cell is based on