Game Development Reference
algorithms. Each generation has 60 seconds to explore as much of the maze as
possible. The ones that explore the most are bred for the next generation.
Each NPC does not know what the maze looks like. It only has information
on its current surrounding area. This information is coded into a binary
sequence. From the NPC's location what is to the left, front, and right of it are
recorded. Take, for example, the layout in Figure 5.19 . To the left is a wall, to
the front is a wall, and to the right is free space. This is coded with a 1 for a
wall and a 0 for a space. In this example, the code would be 110 (wall to left,
wall in front, and space to right).
FIG 5.19 An example maze layout.
The NPC has four actions available to it: move forward, turn left and move
forward, turn right and move forward, and turn around and move forward.
These are coded into the NPC's chromosome as 1, 2, 3, and 4 for each action,
Returning to the maze layout, at any position the NPC could be faced with
one of six layouts. These being:
[0,0,0], no walls
[0,0,1], a wall to the right
[0,1,1], walls to the front and right
[1,1,1], walls left, front, and right
[1,0,0], a wall to the left
[1,0,1], walls to the left and right
For each possible maze configuration, the NPC has an associated action.
In this case, the NPC's DNA is six chromosomes long. An example is shown
in Figure 5.20 .
In Figure 5.20 , if the NPC encounters a wall to the right only, its associated
action is 2, meaning turn left and move forward. In the case of a wall to the