Game Development Reference
InDepth Information
T
is a search tree. We have to
clear
(
v
)
∩
search
(
f
)=
∅
and therefore
show that it is tighter than
T
. Clearly, the weight of all nodes
v
=
t
remains
unchanged. Furthermore, we get
δ
clear
(
t
)
, search
(
e
1
)
,...,search
(
e
r
)
∪

guard
(
t
)

=

V
[
new
(
t
)]

(7.1)
δ
(
new
(
t
)
, clear
(
t
)
, search
(
e
1
)
,...,search
(
e
r
)
∪
V
[
new
(
t
)]
=

δ
(
new
(
t
))

\
(7.2)
δ
(
new
(
t
)
, clear
(
t
)
, search
(
e
1
)
,...,search
(
e
r
)

=

+

V
[
new
(
t
)]
δ
(
new
(
t
))

\
(7.3)
new
(
t
)
,δ
(
clear
(
t
)
, search
(
e
1
)
,...,search
(
e
r
)

≥
+

V
[
new
(
t
)]
search
(
e
)

∩
search
(
e
)
\
δ
(
new
(
t
))
∩
(7.4)
=
δ
(
clear
(
t
)
, search
(
e
1
)
,...,search
(
e
r
)
∪
V
[
new
(
t
)]
∩ search
(
e
)

=
guard
(
t
)
.
The equality between (7.1) and (7.2) follows from the fact that
V
[
new
(
t
)]
∩
δ
(
new
(
t
)
, clear
(
t
)
, search
(
e
1
)
,...,search
(
e
r
)
=
δ
(
new
(
t
)). The equality of
(7.2) and (7.3) then follows as the two sets are disjoint by construction. The
inequality in (7.4) follows from Lemma 7.23 above.
If
δ
(
search
(
e
))
 > δ
(
clear
(
e
))

then the inequality in (7.4) is strict and
therefore in this case we get
w
T
(
t
)
<w
T
(
t
) and therefore
weight
(
T
)
<
weight
(
T
).
Otherwise, if
then the inequality in (7.4) may
not be strict and we therefore only get that
w
T
(
t
)
≤ w
T
(
t
) and therefore
weight
(
T
)
≤ weight
(
T
). However, in this case the edge
e
is now monotone, by
construction, and the only edges which may now have become nonmonotone
are
e
1
,...,e
r
whose distance from the root is larger than the distance of
e
from the root. Therefore, the badness of

δ
(
search
(
e
))

=

δ
(
clear
(
e
))

T
is less than the badness of
T
.
.
Case 2.
Now assume
δ
(
search
(
e
))
 > δ
(
clear
(
e
))

and let
e
1
,...,e
r
be
the outgoing edges of
s
other than
e
. We define a new search tree
T
:=
(
T,new
, search
) where
new
(
v
):=
new
(
v
)
, clear
(
v
):=
clear
(
v
) for all
v
=
t
and
search
(
f
)=
search
(
f
) for all
f
=
e
and
This concludes the first case where

δ
(
search
(
e
))
≤
δ
(
clear
(
e
))

search
(
e
):=
E
(
G
)
\
clear
(
t
)
new
(
s
):=
new
(
s
)
clear
(
t
)
search
(
e
i
):=
search
(
e
i
)
∩
∩
clear
(
t
)
for all 1
≤
i
≤
r
clear
(
s
):=
clear
(
s
)
∩
clear
(
t
)
.
Search Nedrilad ::
Custom Search