Graph based game model

[Urs Holzer]

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?


-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
Pipmak-Users mailing list
Pipmak-Users@...
news://news.gmane.org/gmane.games.devel.pipmak.user
https://lists.sourceforge.net/lists/listinfo/pipmak-users

[Christian Walther]

Interesting theory!

The location graph seems a natural concept for a Pipmak game, judging  
from my own and rivenwanderer's use of it. My intention is that one  
day you will be able to view and graphically manipulate that graph in  
Pipmak itself.

Your idea of extending the graph to the game state is interesting,  
I've never thought of that. I might have to spend a bit more thought  
on it to recognize its usefulness. Can you give some more examples of  
problems that your final software would help solve? I mean, "can the  
game be finished at all?" is an interesting question from a  
theoretical point of view, but I doubt that anyone would design a game  
complex enough that they would need the help of specialized software  
to arrive at the answer "yes". Would your software somehow display the  
graph, or is the graph only a theoretical concept used internally?  
Does it even need to explicitly know the full graph (derivation of  
which seems like a non-trivial problem in itself), or can some insight  
be gained already from abstract graph theory, with limited input? What  
kind of input would it take, anyway?

Some questions spring to my mind right away: What if the effect of  
some user action does not only depend on the current node and the  
state table, but also on time or on a (pseudo-)random number or  
something like that? Does your model cover that too? If it does, is  
the resulting graph still small enough to be of any practical use?  
What if some dimensions are continuous? Does graph theory apply to  
graphs with uncountably many vertices? Or are you relying on the fact  
that in a digital representation, all dimensions are necessarily  
finite? Does your system for determining what to render take into  
account that some of the dimensions that apply to a particular node  
can be "separable"? E.g. when I have a lever with two states, and on  
its handle a light that can be either red or blue, then I need to  
render patches for all four combinations (the whole cartesian  
product): on-red, off-red, on-blue, off-blue. But when the lever and  
the light are in different parts of the screen, I only need to render  
two images, one with both on, one with both off, and can get two  
independent patches from them that together can represent all four  
states. Rendering all four combinations would still work, but in a  
situation of realistic complexity would be a gigantic waste of  
resources.

   -Christian

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
Pipmak-Users mailing list
Pipmak-Users@...
news://news.gmane.org/gmane.games.devel.pipmak.user
https://lists.sourceforge.net/lists/listinfo/pipmak-users

[Urs Holzer]

Christian Walther wrote:

> Interesting theory!
>
> The location graph seems a natural concept for a Pipmak game, judging
> from my own and rivenwanderer's use of it. My intention is that one
> day you will be able to view and graphically manipulate that graph in
> Pipmak itself.
>
> Your idea of extending the graph to the game state is interesting,
> I've never thought of that. I might have to spend a bit more thought
> on it to recognize its usefulness. Can you give some more examples of
> problems that your final software would help solve? [...]

First I have to say that it is rather an idea than a theory. It would not
surprise me if, at the end, I have to conclude that this idea is useless.
The next step will be that I look at some games and try to find out,
whether they can be modeled as I imagine and whether the question of the
dead end is useful.
 
> Some questions spring to my mind right away: [...]

Yes, all those questions have to be answered. But this will take me a lot of
time. So you have to be patient (or help me).

But I want to make two remarks:

1. The graph becomes too big. It grows exponentially in the size of the
state table. Since a game can easily have 100 entries in the state table,
this yields at least 2^100 nodes for the graph. So this would have to be
improved. The graph could be stored in memory without listing all nodes
explizitely. But what happens if one wants to run a breath first search on
it? It would take exponential time in the size of the state table, which
perhaps would be too much.

2. Example for a dead end (similar to the ones that turn up in my game): I
have positions A and B connected through a gate. At position A there is a
button which opens the gate and at position B there is one that closes it.
If you hit the button at B, you will no longer be able to go to A.
But now I have some dought that all dead ends can be found by an algorithm:
A friend of mine once played a game where one can rotate a bridge such that
it connects a point C to points 1, 2, 3 or 4. At point C there is the
control panel for the bridge which requires a code. Unfortunately the code
can only be derived if one has seen a painting at point 1. Actually, my
friend entered the right code by accident without knowing how to construct
it. (I believe that for every position you need a slightly altered code.)

Greetings
Urs


-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
Pipmak-Users mailing list
Pipmak-Users@...
news://news.gmane.org/gmane.games.devel.pipmak.user
https://lists.sourceforge.net/lists/listinfo/pipmak-users