Game Development Reference
In-Depth Information
a
a, 0
b
b, 0
c
c, 0
d, 0
d
a, b
a, 1
b, 1
a, 2
b, 2
0
c
d
d
c
a, b
1
2
a, b
c, 1
d, 1
c, 2
d, 2
c
d
a, b, c, d
3
3
Figure 2.4 Product of the game graph with a DFA yields an equivalent
safety game
are shown, and on the right-hand side the product game graph. The meaning
of the grey vertices and the dashed edges is explained below. For the moment
they can be considered as normal edges and vertices. Formally, the vertices
of the product graph are pairs of a vertex of the original graph and a state
of A . From a pair ( v, q ) there is an edge to ( v ,q ) if there is an edge ( v, v )
in G , and a transition in A from q to q with input c ( v ). So in a play over
the product graph the current vertex always encodes the vertex of G and
the state that
would have reached after reading the colour sequence of the
current play prefix in G .
Now the goal of Eva is to avoid the final state of A because this would
mean that the play prefix matches the regular expression. In the game graph
this event is represented by the bottom vertex labelled 3 (in the full product
there would be vertices ( a, 3) ,..., ( d, 3) but since Adam wins as soon as one
of these vertices is reached they are collapsed into a single vertex).
So the goal of Eva in the new game is to avoid the vertex 3. Such a game
is called a safety game because Eva has to remain in the safe area of the
game (corresponding to the states 0 , 1 , 2of
A
). To solve such a game we can
simply compute the vertices from which Adam can force to reach the bad
vertex. The set of these vertices is called Attr A (3), the attractor for Adam
of the vertex 3. In general, for a set R of vertices, the attractor Attr A ( R )is
A