Archived

This topic is now archived and is closed to further replies.

superpig

Finite State Machines

Recommended Posts

I''m writing a small program to create Finite State Machine diagrams (with the possibility of ''simulating'' them or building code frameworks later on). The diagrams will be in the style of those used in ''Game Architecture and Design.'' I''ll probably open-source the project when done, or at least make it freeware. I''m trying to decide how to implement the connections between diagram elements (states, events, and conditions). I''ve noticed something which appears to be true for all the diagrams they provide, and I''m asking to see if anyone can find an exception to the rule. Every ''connection'' in the FSM consists of three parts. The connection begins at an ''event,'' goes to a ''start'' state, and finishes at an ''end'' state. The idea is that when the event is triggered, the state changes from the ''start'' state to the ''end'' state. From common sense, I can''t see how this could be wrong. An FSM, by nature, means a transition from one state to another when triggered by an event (associated with the first state). The only close-exception to this is where an event ''resets'' a state - but this could be see as going from the event, to the ''start'' state, and back to the ''start'' state (i.e. start == end). Can anyone think of any situation where an FSM would not necessarily obey these rules? Superpig - saving pigs from untimely fates - sleeps in a ham-mock at www.thebinaryrefinery.cjb.net

Share this post


Link to post
Share on other sites
Not too sure what you mean by not obeying the rules, but what happens if you get inputs which the state did not expect?

Share this post


Link to post
Share on other sites
I''m not so much talking about a real-world state machine - where random input could, concievably, have to be accounted for; I just mean on a diagram. The only input a state gets is through the lines going into it (and it knows about all of them).

The rule I refer to is this:

In a Finite State Machine, the only form of connection between components is a three-point connection: from an event, to a state, to a state.

Can anyone think of any exception at all to this, or possibly prove me right?

Share this post


Link to post
Share on other sites
Sounds good to me. I don''t understand what you mean by "updating" the node by having a transition to itself, though... Either the state changes or it doesn''t - what room is there left? Or do you mean an implicit self-loop if nothing worthwhile happens at all?

Share this post


Link to post
Share on other sites
The idea of a ''re-entrant'' state is that when the state is entered, certain variables are set - when the state is ''re-entered,'' those variables are then reset.

For example, take the ghosts in Pacman. They have three states - Hunter, Hunted, and Eaten. Say the ghost is in the Hunter state. Pacman eats a powerpill, so all ghosts move into the Hunted state. Normally, a timer event would occur after a given amount of time (to set the states back to Hunter), but if Pacman eats another powerpill before that happens, then the ghosts ''re-enter'' Hunted state. This has the effect of resetting the timer.

Superpig
- saving pigs from untimely fates
- sleeps in a ham-mock at www.thebinaryrefinery.cjb.net

Share this post


Link to post
Share on other sites
Strictly speaking the timer is not part of the state. Otherwise you''d have to make one state for every possible count...

Timer==0 is an event that triggers a transition from state "hunted" to "hunter":

[hunted]----(timer==0)---->[hunter] 


So you''d not re-enter the state, just reset the timer so that the triggering event occurs a little later....



------------------------------
"Reality is nothing, perception is everything!" - First Wizard Zeddicus Zu''l Zorander

Share this post


Link to post
Share on other sites
Gah! Stop picking apart my examples

Another way of doing it would be to store the clocktime when the state was entered, and then keep checking that time against the current clocktime (i.e. when the currentTime>=startTime+10) or something like that.

But implementation isn''t the point. The ''state timer expires'' event is purely symbolic, the actual way it''s done is irrelevant.

Well, ok, so maybe the ''re-entrant'' states aren''t strictly necessary. But they''re not the issue here!

Can anyone (*without* further pedantry, please ) think of any examples of an FSM which does not follow the trigger-startstate-endstate pattern?

Superpig
- saving pigs from untimely fates
- sleeps in a ham-mock at www.thebinaryrefinery.cjb.net

Share this post


Link to post
Share on other sites
quote:
Original post by superpig
Can anyone (*without* further pedantry, please ) think of any examples of an FSM which does not follow the trigger-startstate-endstate pattern?

No. There is none.

As an aside, have you considered basing your application off an existing diagramming solution (eg Dia, Kivio)? Kivio is only available for KDE, but Dia is available for all Unices and Win32. They''re both under the GPL. Given all of Kivio''s features, you might even want to consider porting/forking it to whatever platform you''re working with.

Dia homepage
Dia Win32 Installer
Kivio project page (just in case you''re interested)

Share this post


Link to post
Share on other sites
Thanks, but Kivio''s not what I need. I''m running Red Hat alongside XP, so I did look at it, but it''s a little too generic.

Plus I need practice at MFC.

I intend to build in a ''simulator'' part of the program - where you can set up a number of ''instances'' of the machine, and then fire off events to check that everything happens the way you expect it to. Kivio can''t do that.

And as for there being none: I think you''re right, by the nature of the machine, but is there a proof somewhere, please? I''ve already coded it on the assumption that there is no exception, but if I have to change that I''d rather change it now than later...

Superpig
- saving pigs from untimely fates
- sleeps in a ham-mock at www.thebinaryrefinery.cjb.net

Share this post


Link to post
Share on other sites
"Every ''connection'' in the FSM consists of three parts. The connection begins at an ''event,'' goes to a ''start'' state, and finishes at an ''end'' state. The idea is that when the event is triggered, the state changes from the ''start'' state to the ''end'' state."

You could invert the model, but it would be the same model.. as in: begins in an "end state" (a search routine), encounters an event (a data object), and finishes in a "start state" (an acquisition routine). the default being "on" instead of "off".

Share this post


Link to post
Share on other sites
OK. My current implementation is generic enough to allow connections between any three objects (including object-self-self connections). Thanks, everyone.

Share this post


Link to post
Share on other sites