Teach me: Finite State Machines (FSM) - Hardcore Theory

Not for 'how-to' coding questions but PHP theory instead, this forum is here for those of us who wish to learn about design aspects of programming with PHP.

Moderator: General Moderators

User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by Chris Corbyn »

jshpro2 wrote:Yeah... that's what I was getting at. Why not define "constraints" and hueristic cost functions and let the computer search the state space. For instance a solution that drove the car into an obstacle would impede the goal solving and thus would rank lower on the hueristic. That's what I was trying to get at is though technically any logic can be "serialized" into a linear flow like this, that is just one paradigm to define the logic. You would still need a framework that defined the constraints though
We might continue this topic once we've finished working on this state machine :) I sort of want to pin down FSM logic before exploring alternatives, pretty much because it's definitely a FSM that is used in parsers, not heuristics or anything a "fuzzy" as that.

So, I wrote a lot of code to do this. I'd have preferred to create a FSM that sits separately to the Car class and somehow "configure" or "build" a generic FSM in the Car. Unfortunately I don't think this is going to work very nicely in PHP due to lack of lambda style functions (at least, decent ones) or anonymous objects.

I'm still unclear how a lookup table comes into play... I'm assuming that the table I wrote before is basically what the lookup table would contain, and the FSM uses that to switch states, somehow?
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by josh »

Chris Corbyn wrote:I'm still unclear how a lookup table comes into play... I'm assuming that the table I wrote before is basically what the lookup table would contain, and the FSM uses that to switch states, somehow?
Didn't realize this was for your parser. Yeah, basically it has to map each state "node" to its successor nodes, so when its in a given state there would be a function to return a set of legal successor states. I kept derailing the thread about nueral nets and stuff because I thought you were literally writing a car analogue hah
User avatar
Christopher
Site Administrator
Posts: 13596
Joined: Wed Aug 25, 2004 7:54 pm
Location: New York, NY, US

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by Christopher »

Chris Corbyn wrote:I feel like I lost my evening coding this :P Lots of copy & paste and repetitive code!
Please don't let me write anything like that again 8O
I didn't want you to do that in the first place! :drunk:
Chris Corbyn wrote:So, I wrote a lot of code to do this. I'd have preferred to create a FSM that sits separately to the Car class and somehow "configure" or "build" a generic FSM in the Car. Unfortunately I don't think this is going to work very nicely in PHP due to lack of lambda style functions (at least, decent ones) or anonymous objects.

I'm still unclear how a lookup table comes into play... I'm assuming that the table I wrote before is basically what the lookup table would contain, and the FSM uses that to switch states, somehow?
Well, you wrote a very nice Finite Event Machine with a bunch of State handlers, and discovered first hand how little fun it is to code one of those! :( ;) Now try a Finite State Machine with a bunch of Event handlers. :)

So invert your thinking. Event handlers check for the Event and Current State in the State table to see if there is a State Change. You could even do it with one Event handler if you pass the Event in. You would then just lookup the Event and Current State in the table see if there is a State Change for it.

Remember, the FSM is not the Car. It is the Car's behaviour -- how it responds to Events. The Car would still have "code" to express its current State. In MVC terms, think if the FSM as Filtering the Request (Events) and then setting the State of the Model. So it's the Controller in that sense. After that, the View shows the Model and we see the effect of the Event.
(#10850)
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by Chris Corbyn »

:lol: Hillarious. I'm such a n00b!

I'll give it another shot. Thanks for the clarification :)
Post Reply