Anyway, with that elegant proof out of the way, let's start trying to do some modeling. Petri nets are often used to model event driven systems which are ... da da daaaa... systems which are driven by events. Are computer programs event driven systems... surely. Although, we could go further in detail by considering the physics of transitors etc. and classify them as hybrid systems (event- and time-driven systems). However, for now, let us just start with the simple Petri Net (there are other kinds of Petri nets... people like to make new Petri Net modeling frameworks for the purposes of Ph.D. thesis... haha... i'm funny, i never realized this... ok continuing on). Also note, I'm by no means an expert on Petri Nets, but we need some tools so i'm trying to present a few.
Just as a teaser... this is what I mean by modeling for a game using Petri Nets.
Why am I doing this, well mainly, because some computer scientists like to use these models and you might find them interesting. I want to see if we can use them to develop our game model for behaviors. After all, what are we doing if not modeling after "real world" things? Petri nets are used to describe various types of systems from manufacturing systems to your PDA. They can describe systems working in parallel (concurrent) and Petri nets have a mathematical description. You might find them useful some day. Just look at all the "people" that find them useful.
What is a Petri net? Well, so far, we know they are themselves. But lets go deeper. A Petri net is a graph composed of places (i.e. circle like thingies depending on how accurately you can draw a circle, but no one is that perfect), arcs (i.e. lines with arrows) and transitions (i.e. bars without the single women). I think we are being informal enough don't you? Below shows a simple Petri net model.
I definitely do not like the way this Petri net is staring at me. Anyhoo... Places typically represent states while transitions represent events. For example, a place could represent "the door is opening" and an event could be "the door is open." Lets, see another Petri net,
Let's go through an iteration or two of this Petri net. First, the black circle thing inside a place is a token and represents the state of the Petri net. For the example above, this means we are currently in the "Bucket is being filled" state. When the bucket is full, the transition (i.e. event) is "fired" and our little token friend slides down past the transition into the "Bucket is being empitied" place. The Petri net state is now:
Now we wait for the bucket to be emptied. When this occurs, the "bucket is empty" transition "fires" and our friendly token slides up the arc to the "bucket is being filled" place. And we return to:
I think you get the drift now. But there are rules to this "Token Game"
1. A transition can "fire" only when all of its input places have a token. By input places, I mean places with arcs pointing to the transition in question. See below:
2. When a transition "fires" we remove one token from each of the input places and add a token in each of the output places.
3. If there are two different transitions which are both "fireable" we have to have some sort of rule which to choose to fire. Sometimes, we just let the choice be random. Other times, it's based on some priority.
A little more advanced Petri net lets you have more than one token in a place and transitions which are labelled with a number representing how many tokens pass through when fired. For example:
I'll let you play with a few Petri net models of elevators, manufacturing systems, traffic lights, etc. from this excellent website. They put big hollow squares for transitions and more than one arrow from an input place to a transition to represent the number of tokens required. I'll let you play a little and then we'll go to a mathematical description. I hope I haven't insulted your intelligence too much or made myself unclear. For now consider this Petri net related to gaming:
========
OK back after a breather. Let move on now to how to describe a Petri net mathematically. What we would like to do is have an equation that would take an initial state of our simple Petri net (tokens and their locations) and tell us the next state when we fired a particular transition (assuming there are valid transitions to fire).
The equation should look like this:
u(k) = u(k-1) + (M-N)*t(k-1)
Where u(k) is the next state vector s x 1, u(k-1) is the previous state vector s x 1, M and N are matricies s x r, and t(k-1) is a vector r x 1 representing which transition is firing. r is the number of transitions and s is the number of places. k=1,2,3,4,... represents our time step.
For example, if u(0) = 1 and M-N = 4 and t(0) = 1 then
u(1) = u(0) + (M-N)*t(0) = 1 + 4*1 = 5
To construct M and N is very simple. Each row of M or N represents a place. Each column of M or N represents a transition. M will be something we call an Output Matrix and N will be something we call an Input Matrix.
For purposes of example, lets consider the following Petri net:
In the figure above, the numbers are just labels for each of the separate places and transitions.
To construct the M matrix, we look at each place (row of M) and look to see if there are any transition arcs pointing to it. If there are, we put a 1 in the column for the transition (column of M) it represents.
For this example:
..Transitions --->...1 2.....Places
M =.................[ 0 0 ]......| 1
.....................[ 0 1 ]......| 2
.....................[ 1 0 ]......V 3
You can see from this matrix that there an arc pointing from transition 1 to place 3. Also you can see that transition 2 has and arch pointing to place 2.
To construct the N matrix, we look at each transition (column of N) and look to see if there are any place marks pointing to it. If there are, we put a 1 in the row for the place (row of N) it represents.
..Transitions.--->...1 2......Places
N =.................[ 1 0 ]......| 1
.....................[ 1 0 ]......| 2
.....................[ 0 1 ]......V 3
From the N matrix, we can see there is 1 arc pointing from place 1 to transition 1, 1 arc pointing from place 2 to transition 1, and 1 arc pointing from place 3 to transition 2.
Therefore, M-N = Z =
[-1 0]
[-1 1]
[1 -1]
There we have it, our model
u(k) = u(k-1) + Z*t(k-1)
Now t(k-1) is a vector with one element a 1, and the rest 0's. The row in t(k-1) with the 1 represents the transition we wish to fire.
For example:
t(0) =
[1]
[0]
means we wish to fire transition 1
t(0) =
[0]
[1]
means we wish to fire transition 2
u(k-1) is the state or number of tokens in each place of the Petri net before firing. For example:
u(0) =
[4]
[2]
[3]
means there are 4 tokens in place 1, 2 tokens in place 2, and 3 tokens at place 3.
=======
So lets use this initial setup for another example
u(0) = 1 token in place 1 and place 2, and 0 in place 3 =
[1]
[1]
[0]
t(0) = fire transition 1 =
[1]
[0]
then
u(1) = u(0) + Z*t(0) =
(pardon me for using dots as space holders)
[1]....[-1 0]...[1]
[1].+.[-1 1].*.[0].=
[0]....[1 -1]
[1]....[-1]...[0]
[1].+.[-1].=.[0] = we have one token in place 3
[0]....[1]....[1]
We have:
Now normally you have to check to see if transition 1 follows the rules before you fire (i.e. there are enough tokens in the input places to fire). Then you would fire the transition. You can check this by using N, t(k-1) and u(k-1), I'll let you figure it out as an exercise.
Anyway, I hope you got some sort of feeling for this so far.
====================
Did you figure it out? How to check if we can fire a certain transition?
Well, it's fairly simple: you take N*t(k-1) and compare the rows to u(k-1). If any of the rows of N*t(k-1) are greater than u(k-1), you can't fire the transition you want as selected through t(k-1).
===================
So the steps are:
1. Model your behaviors with a Petri Net using events as transitions and places as states.
2. Find the Z = M-N matrix.
3. Intialize to the first state, u(0).
4. Determine which transitions can be fired by u(k-1) >= N*t(k-1).
5. Select a transition.
6. Compute the next state using u(k) = u(k-1) + Z*t(k-1).
7. k=k+1, goto step 4.
