Game Development Reference
In-Depth Information
The set V contains the positions the searchers and the fugitive can occupy.
In our example, this is the set V ( G ) of vertices of G .
The Searcher admissibility relation defines the possible moves the searchers
can take. As in our example the searchers are free to move from any position to
any other position, the Searcher admissibility relation is just
S
:= Pow( V )
×
Pow( V ).
The fugitive admissibility function models the possible moves of the fugitive:
if the searchers currently reside on X
V ( G ), the fugitive currently resides
V and the searchers announce to move to X
somewhere in R
V , then
( X, R, X ) is the set of positions available to the fugitive during the move of
the searchers. In the case of the Invisible Cops and Robber Game described
above
F
( X, R, X ) is defined as
F
X ) from v to u
{
v
V : there is u
R and a path in G
\
( X
}
the set of positions reachable from a vertex in R by a path that does not
run through a searcher remaining on the board, i.e., a searcher in X ∩ X .
Finally, the complexity function c is defined as c ( X ):=
- the number
of vertices in X . The complexity function tells us how many searchers are
needed to occupy a position X of the Searcher. On graph searching games
played on graphs this is usually the number of vertices in X . However, on
games played on hypergraphs searchers sometimes occupy hyper-edges and
then the complexity would be the number of edges needed to cover the set
X of vertices.
Based on the definition of abstract graph searching games we can now
present the rules for invisible and visible games.
|
X
|
7.2.2 Invisible abstract graph searching games
Let G := ( V,S,F,c ) be an abstract graph searching game. In the variant of
graph searching with an invisible fugitive, the searchers occupy vertices in
V . The Fugitive, in principle, also occupies a vertex in V but the searchers
do not know which one. It is therefore much easier to represent the position
of the Fugitive not by the actual position v
V currently occupied by the
fugitive but by the set R of all positions where the fugitive could currently
be. This is known as the fugitive space ,or robber space . The goal of the
searchers in such a game therefore is to systematically search the set V so
that at some point the robber space will be empty.
The rules of the invisible abstract graph searching game on G
are
defined as follows. The initial position of the play is ( X 0 :=
,R 0 := V ), i.e.,