surroundings. Each edge links two nodes and has an age which gives the time since it was last activated. This algorithm needs to be omniscient, because the position of the imitated player, the demonstrator, is to be known at any time.

The principle of the GNG is to modify its graph, adding or removing nodes and edges and changing the nodes' position for each given demonstrator's position. The algorithm does the following: for each input the closest and the second closest nodes are picked. An edge is created between those nodes and the closest node's error is increased. Then the closest node and its neighbours are attracted toward the input. The ages of the closest node's edges are increased by 1 and too old edges are deleted. Each λ **input a node is inserted between the**
node with the maximum error and its neighbours having the maximum error. At the end of an iteration, each node's error is decreased by a small amount.

The version we use is a bit modified to give better results for our needs as shown by figure 1. Instead of inserting a new node each λ **input, a node is inserted when a node's error is superior to a parameter**
MAX ERROR**. As each node's error is reduced by**
a small amount ERROR DECAY **for each input, the**
modified GNG algorithm does not need a stopping criterion. Indeed, if there are many nodes which represent well the environment, the error added for the input will be small and for a set of inputs, the total added error will be distributed among several nodes. The decay of the error will avoid new nodes to be added to the GNG resulting in a stable state. However if the player which serves as a example goes to a place in the environment he has never gone before, the added error will be enough to counter the decay of the error, resulting in new nodes to be created.

This algorithm has 5 parameters which influence the density of nodes, the quality of the representation, the adaptivity and the time to reach a stable state:

- The attraction applied to f irst toward (**x, y, z**) - The attraction applied to f irst**'s neighbours toward**
(**x, y, z**)
- The nodes' error decay, ERROR **DECAY** - The nodes' maximum error, MAX **ERROR** - The edges' maximum age, MAX AGE
Nodes can be used as a representation for the character's decision system. However, edges only represent proximity and not paths between nodes: nodes can be close but there may be a obstacle between them, so edges cannot be used by the model.

nodes **← {}** edges **← {}**
while **demonstrator plays** do
(x,y,z) ← **demonstrator's position**
if |nodes| = 0 or 1 **then**
nodes ← nodes ∪ {**(x,y,z,error=0)**}
end if if |nodes| = 2 **then**
edges ← {**(nodes,age=0)**}
end if first ← **closest((x,y,z),nodes)** second ← **secondClosest((x,y,z),nodes)**
edge ← edges ∪ {{first,second}**,age=0)**} first.error+=||**(x,y,z)-first**|| Attract first toward (x,y,z) ∀ edge ∈ **first's edges, edge.age++** Delete edges older than MAX AGE Attract neighbours(first) toward (x,y,z) ∀ node ∈ nodes, node.error-=ERROR **DECAY**

if first.error > MAX ERROR **then**
maxErrNei ← **maxErrorNeighbour(first)** newNode ← **between(first,maxErrNei)** first.error/=2, maxErrNei.error/=2 newError ← **first.error+maxErrNei.error** nodes ← nodes ∪ {**(newNode,newError)**}
end if end while

Figure 1: Algorithm used to learn the topology of the environment represented by a growing neural gas.

## Evaluation

We used the game Unreal Tournament 2004 because it features quite complex environments. Human players can also control avatars in the game so the GNG can learn for them. We have to choose the parameters in a empirical way because we cannot find them analytically nor use an optimization algorithm. Indeed, our goal is believability and it can be only measured with human judges. This kind of evaluation is not suitable for optimization. The best parameters we found are:
- Attraction force applied to f irst **is 0.03 times the**
vector (x, y, z) − **f irst**
- Attraction force applied to f irst**'s neighbours is**
0.0006 times the vector (x, y, z) − **second**
- **Nodes' error decay is 10** - **Nodes' maximum error is 20000** - **Edges' maximum age is 75**
To compare with other environments, the position in Unreal Tournament is given in Unreal units (1 meter is roughly equal to 50 Unreal units) and all the parameters are based on a demonstrator's position in Unreal units.