Graph based game model

[Urs H. <ur...@an...>]

Hi

As some discussion about automatic creation of hotspots and node.lua files
has arised here, I tell you the following ideas now instead of doing that
when my first game is finished. Since my time is sucked up by other
projects and also because there is some technical problem in my game, it
will take a lot more time until it is actually finished. But here my ideas,
they are a bit mathematical, since I am a math student, but anyway:

I have observed that a Pipmak game is actually an finite state automaton.
(Well, one could imagine a Pipmak game that can not be described as an
automaton, but would it be interesting?) We can describe the whole game as
a directed graph. The vertices of the graph are all possible combinations
of the location (i.e. the name of the node) and the possible values of the
state table. The edges are the traversals the user can make: Changing the
node, klicking a switch, moving a lever and so on. One vertex is the
beginning of the game, and another (or several others) mark the end of the
game. Now, using graph algorithms, we can answer some questions: Can the
game be finished at all? If one reaches a given vertex by starting at the
beginning, can the game still be finished (i.e. are there no dead ends)?
Are there states we do not have to render since they can not be reached?

First, let us define the the Location graph of a game. It contains every
node in the game as vertex. The directed edges are the directions the user
can move to by simply clicking on a hotspot. This graph can be laid out in
3D space using the locations of the cameras. This layout would allow us to
automatically generate hotspots.

An entry in the state table is what I call a dimension. It is simply the set
of all values this entry can take. For example, in my game one can switch
off the light, so I have a dimension Light={off,on}. Also, one can move a
lever which yields a dimension Lever1={1,2,3,4}. The cartesian product of
the set of nodes and all dimensions gives the state space. The state space
is simply the set of all possible states the game can have. The vertices of
the game graph G are elements of this state space.

Now every location can be annotated with the dimensions that can be observed
there. For example in my game, the dimension Lever1 can only be observed on
some locations, since one can not see the lever from the other locations.
However the dimension Light can be observed everywhere. This
actually "glues" together vertices in the game graph. I currently use this
information for rendering.

The ultimate goal is to transform my ideas into a software package that
greatly aids in designing games for Pipmak. What do you think about that?