Game Development Reference

In-Depth Information

computed in iterations as follows:

Attr
0

(
R
)

=
R

A

Attr
i
+1

(
R
)=
Attr
i

(
R
)

∪

A

A

Attr
i

{

v

∈

V
A
|∃

u

∈

(
R
):(
v, u
)

∈

E

}

A

Attr
i

{

v

∈

V
E
|∀

u
:(
v, u
)

∈

E

→

u

∈

(
R
)

}

.

A

The set
Attr
i

(
R
) contains those vertices from which Adam can ensure to

reach a vertex in
R
after at most
i
moves. For a finite game graph there exists

an index
i
such that
Attr
i

A

(
R
)=
Attr
i
+1

(
R
) and we set
Attr
A
(
R
)=
Attr
i

(
R
)

A

A

A

for this index
i
.

From the vertices that are not inside
Attr
A
(
R
) Eva has a simple winning

strategy to avoid a visit of
R
: She always moves to a vertex outside of

Attr
A
(
R
). The definition of the attractor ensures that such a move is always

possible. Furthermore, from outside the attractor Adam does not have the

possibility to move inside (again by definition of the attractor).

In the product game graph from the example in Figure 2.4 the attractor

for Adam of vertex 3 consists of the grey vertices (
c,
1)
,
(
d,
2) (in the first

iteration), and (
a,
2) (in the second iteration). A strategy for Eva to avoid

the attractor is given by the dashed arrows.

In the original game, Eva can realise the strategy by running the DFA

A
on the play and making her decision based on the current vertex of
G
,

the current state of

, and the strategy from the product game. These are

precisely the components required for a strategy automaton as defined in

the previous section.

A

Exercise 2.1
The method illustrated above uses a translation of regular

expressions into deterministic finite automata. Analyse the method when

using non-deterministic finite automata instead and show that it does not

work in general.

For the above example we used a translation from regular expressions

to DFAs. For infinitary conditions (something happens infinitely/finitely

often) standard DFAs are not enough. To treat such conditions we can use

ω
-automata.

2.3.1
ω
-automata

Automata on infinite words are defined in a similar way to automata on

finite words. The main difference is that a run of such an automaton does not

have a last state because the input is infinite. For automata on finite words,

acceptance of a word by a run is defined in terms of the last state of the run:

Search Nedrilad ::

Custom Search