Game Development Reference
In-Depth Information
input
c
a
a
c
a
a
c
d
b
b
d
b
b
b
b
a
b
c
d
d
a
b
c
b
d
a
c
b
d
a
c
d
b
a
c
c
d
b
a
b
c
d
a
a
b
c
d
b
a
c
d
a
b
c
d
c
a
b
d
b
c
a
d
a
b
c
d
b
a
c
d
a
b
c
d
c
a
b
d
LARs
priorities
7
7
5
1
4
7
5
7
3
3
6
6
6
3
3
6
Figure 2.7 Latest appearance records for a given sequence of colours from
{
a, b, c, d
}
for the Muller condition
F
=
{{
b, d
}
,
{
a, b, c
}}
sequence, it is moved to the first position in the ordering. To define the
parity condition of the automaton we additionally mark the old position of
the colour that has been moved. This idea is illustrated in Figure 2.7 for
the colour set C =
. The LARs are written vertically, and when
reading the next colour it is moved to the top. The numbers below the LARs
are the assigned priorities and are explained later.
The marked positions are underlined. We point out that it is not the
underlined colour that is marked, but the position. For example, in the fifth
LAR in the picture, it is not b that is marked but the second position because
this LAR was obtained by moving d from the second position to the front.
Note that in this way the colours that appear only finitely often gather at
the end (bottom) of the LAR and that the marker eventually stays in the
part of the LAR that keeps changing.
Formally, a latest appearance record (LAR) over C is an ordering
{
a, b, c, d
}
d 1
···
d n of the elements of C with one marked position h :
LAR ( C )=
{
[ d 1 ···
d n ,h ]
|
d i
C, d i
= d j for all i
= j, and 1
h
n
}
.
The set of LARs serves as the set of states for the parity automaton. The
transition function (update of the LARs) is defined as explained above:
δ LAR ([ d 1 ···
d n ,h ] ,d )=[ dd 1 ···
d i− 1 d i +1 ···
d n ,i ]
for the unique i with d = d i . Note that the LARs and their update do not
depend on the Muller condition F .
It remains to assign the priorities to the states, i.e., to the LARs. This
is done depending on the size of the part of the LAR that has changed in
the last transition. As explained above, the biggest part of the LAR that
changes infinitely often represents the set of colours that appear infinitely
often and hence the parity automaton should accept if this set belongs to
the Muller condition.