pushdown automata

[amitevski]

I added support for pushdown automaton states see Readme.md updates for details or http://gameprogrammingpatterns.com/state.html#pushdown-automata

[gregwebs]

Do the pushed states need to be dynamic? Wouldn't it be better to model them ahead of time as a child state machine and when the event is sent behave differently depending on the status of the child state machine?

In this model you would have 3 states: walking, shooting, & standing, where standing is the equivalent of walking & shooting not being pushed on.

[amitevski]

so for my use case I need them dynamic. I'm programming a state machine for a pinball with different games. Lets call a game e.g. soccer. But this game can also have sub-games like "free kick". In all these states I can have states like bonus X2 mode, multiball...

Without pushdown states I would have to redefine this X2 state in every game and sub-game where this is possible. But with pushdown states I can reuse the pushdown state and just push it to the stack, regardless in which state I'm currently in. Maybe its pretty special for game programming..

[gregwebs]

Is the problem just one of duplicated code? What would help explain the most is if you give the state machine that demonstrates this. The README and test case seem too simplified.

[amitevski]

ok you asked for it :)

in following state machine I want to be able to have an x2bonus sub-state inside every other state. so I have to redefine it everywhere because I also want the event handlers in parent state to fire correctly

{
initialState: 'swe1',

swe1: {

  UpperJetBumperDown: function() {
    solenoid.fire('UpperBumper');
    this.dispatch('BlinkLamp', {id:'UpperJet', duration:20});
    this.dispatch('addPoints', 5000);
  },

  bankFull: function() {
     this.dispatch('addPoints', 500000);
  },
  ShieldHitDown: {target: 'ShieldHitDown1'},
  BonusHit: {target: 'x2bonus'},
  states: {
    x2bonus: {
    addPoints: function(points) {
        addPoints.call(this, 2, points);
      }
    },
    ShieldHitDown1: {
      BonusHit: {target: 'x2bonus'},
      ShieldHitDown: {target: 'SubGameSimple'},
      entry: function() {
        ui.setGameMessage('hit shield again to start simple game');
      },
      states: {
        x2bonus: {
          addPoints: function(points) {
            addPoints.call(this, 2, points);
          }
        }
      }
    },
    SubGameSimple: {
      ShieldHitDown: {target: 'CenterHit'},
      LeftDropTargetDown: {target: 'LeftHit'},
      RightDropTargetDown: {target: 'RightHit'},
      states: {
        CenterHit: {
          ShieldHitDown: function() {},
          LeftDropTargetDown: {target: 'LeftCenterHit'},
          RightDropTargetDown: {target: 'RightCenterHit'},
          entry: function() {
            ui.setTargets(['left','','right']);
          },
          BonusHit: {target: 'x2bonus'},
          states: {
            x2bonus: {
              addPoints: function(points) {
                addPoints.call(this, 2, points);
              }
            }
          }
    }
  },
  entry: function () {
    //update ui state

  },
  exit: function() {

  }
}
}

with pushdown states this could be simplified as follows. The event "BonusHit" will get catched in topmost event handler, but the state will behave like it was defined below any of the substates as I handle the pushDown states first.

{
initialState: 'swe1',

pushdownStates: {
  x2bonus: {
  addPoints: function(points) {
      addPoints.call(this, 2, points);
    }
  }
},

swe1: {

  UpperJetBumperDown: function() {
    solenoid.fire('UpperBumper');
    this.dispatch('BlinkLamp', {id:'UpperJet', duration:20});
    this.dispatch('addPoints', 5000);
  },

  bankFull: function() {
     this.dispatch('addPoints', 500000);
  },
  ShieldHitDown: {target: 'ShieldHitDown1'},
  BonusHit: function() {this.pushState('x2bonus'); },
  states: {,
    ShieldHitDown1: {
      ShieldHitDown: {target: 'SubGameSimple'},
      entry: function() {
        ui.setGameMessage('hit shield again to start simple game');
      }
    },
    SubGameSimple: {
      ShieldHitDown: {target: 'CenterHit'},
      LeftDropTargetDown: {target: 'LeftHit'},
      RightDropTargetDown: {target: 'RightHit'},
      states: {
        CenterHit: {
          ShieldHitDown: function() {},
          LeftDropTargetDown: {target: 'LeftCenterHit'},
          RightDropTargetDown: {target: 'RightCenterHit'},
          entry: function() {
            ui.setTargets(['left','','right']);
          }
      }
    }
  },
  entry: function () {
    //update ui state

  },
  exit: function() {

  }
}
}

[gregwebs]

Can x2bonus just be a separate state machine? In StateTree this could be the same state machine using concurrent substates.

[DavidDurman]

Pushdown automaton states is indeed an interesting addition. In Statechart terms, this is called History and was described in the original Harel paper: http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/Statecharts.pdf. Let me dive in into this a little more to give you a proper feedback on how this can be integrated in Statechart lib. @amitevski Thanks for the contribution, I'll give it a closer look in the coming week (just returned from vacation, that's why I was silent for couple days).

[DavidDurman]

Here is more info on transitions to History as presented by Miro Samek (author of the QHsm framework this lib is based on). See Chapter 5.5 Transition to History (p. 122): http://goo.gl/RHmfSJ

[amitevski]

This looks like a well suited example for the microwave, but I currently cant imagine how this will help for game programming.

The main difference is that with history states:

1. the exit handler of doorClosed state or in my case swe1 will be called. This is the handler where I save game state and do some other cleanup. Obviously I dont want to do that when entering x2bonus state.
2. as far as I understand, events wont be bubbled up to the history state. In my case this is a must have feature. Because in x2bonus state I only want to handle addPoints event, all other events should be handled by the previous states

[gregwebs]

StateTree has history states. I found switching the behavior to default to the last history state rather than setting a default state to be invaluable. That is what is in section 5.5 of that PDF. I can't say that I am fully making the connection here to history states though, or at least it still seems like concurrent substate (a 2nd state machine in this library) make more sense.

[amitevski]

@gregwebs I did not know about state trees before. Could you provide an example how such a state would look like?

[gregwebs]

I have an example with concurrent substates in the README. I don't understand everything that is going on in the given example, in part due to missing references, but also in part due to my lack of understanding of the statechart library. But here is a rough StateTree translation:

var states = makeStateTree().root
states.concurrentSubStates()
var Bonus = null
var NoBonus= null
states.subState("x2bonus", function(x2bonus){
  NoBonus = x2bonus.subState("NoBonus").defaultState()
  Bonus = x2bonus.subState("Bonus")
})

states.subState('app', function(app){
  app.subState('swe1', function(swe1){
    swe1.defaultState()
    .subState(("ShieldHitDown1", function(ShieldHitDown1){
      ShieldHitDown1.enter(function(){
        ui.setGameMessage('hit shield again to start simple game');
      })
    })
    .subState(("SubGameSimple", function(SubGameSimple){
      SubGameSimple.subState("CenterHit", function(CenterHit){
        CenterHit.enter(function(){
            ui.setTargets(['left','','right']);
        })
      })
  })
})

function dispatchAddPoints(points){
  if (Bonus.isActive()) { addPoints(2, points); }
}

function UpperJetBumperDown(){
  if (swe1.isActive()) {
    solenoid.fire('UpperBumper');
    dispatchAddPoints(5000);
  }
}
function bankFull(){
  if (swe1.isActive()) { dispatchAddPoints(500000); }
}

Bonus.goTo() // rather than pushState, just go to the state you want to be in

[amitevski]

@gregwebs to be honest I like the json syntax much more. And as far as I can see I would have to do event processing by myself. In statechart there's a generic event dispatching function.

Also I'm quite familiar with the original QEP active object framework so everything is easier in statechart :)