Re: Graph based game model

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

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