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

Search Nedrilad ::

Custom Search