Good methods for building a Finite State Machine?

I was building an "acting system" for remote-controlled sackbots, and I had a bit of trouble with it - keeping state that I didn't want it to, not making the transitions I wanted it to, occasionally cycling rapidly between states or jumping momentarily to the wrong state before going to the correct one... I got it sorted out (it still does that momentary "jump to the wrong state before jumping to the correct one" thing, though) but it got me thinking about how to implement a finite state machine (FSM) in LBP2...

It seems like the way to go is to use a big selector for all the possible states in the machine, with logic combined (via AND) with individual outputs to trigger selector inputs - and then one-shot the various triggers to keep them from producing multiple state changes.

It's not an ideal solution: it produces a messier circuit than I'd like. Each input to the selector has to be connected to an OR gate with as many inputs as there are possible triggers for that state.

I tried another approach: still using the selector to control which state was active, but representing each state as a circuit board, and connecting a selector output to the "enable" line for that microchip. Then each microchip (representing a single "state") contains all the logic for its own outgoing transitions. I ran into a few issues there - some of my logic didn't like being turned off and then back on (still looking into that) - and that approach still requires the big OR gates on every selector input. I feel like I was having some other problem with this approach, but I can't remember what. Maybe it was just seeming too cumbersome for the specific problem I was trying to solve...

So, any better ways to make a state machine? It seems like it would be a good way to create behavior patterns in general...

FSMs are notoriously difficult to design implement in hardware. They are great in high level conceptual models, but once you get down to the nitty gritty work of wiring up individual gates (as opposed to synthesizing on some form of PLD / FPGA) then it's a right ***** for anything other than a very simple system. The LBP2 tools provide a significant reduction in complexity and development woes than what you might encounter in the real world. I don't think you'd manage to make a cleaner system using discrete logic in the real world (I have mental images resurfacing of the nests of wires these things create - it's not pretty :p). Even a purely algebraic solution, done manually, is, IMO, more of a headache than LBP implementation.

The erroneous state transitions should be completely fixable with the introduction of pulsing appropriate signals that cause issues. Alternatively you can go down the more classic solution of adding intermediate states, that require that signal to go low again before the full transition occurs. So, if signal i triggers the transition from state A to B, but it also triggers state B to state C, you can add in an additional state that forces the signal to go low again before it fully gets to state B.

I've used both in LBP state machine design and they are both useful methods, depending on the application.

The state retention is best achieved with a select switch - that's basically it's entire purpose, to be a state machine. I'm also a fan of the putting entire states into microchips. Not sure what issues you are having, probably it's devices that retain state not resetting? Remember that all wires go to zero when the Microchip is turned off, but components with internal state retain that state, the disabled parent chip mere supresses their outputs. These components will need to be explicitly reset by you - a battery in the microchip tends to be a neat way of resetting those components as most of them have some explicit reset input.

I don't fully understand what the inherent requirement of large OR gates on every input is, this sounds like a practical issue of your application, and would probably be required no matter what your core implementation is.

Another trick, that doesn't sound like it's going to be applicable to your application is to identify sets of states that regularly / always feed into each other. Make these states be adjacent on the select switch and you can use the increment / decrement to swap between them.

Quote:

---

Originally Posted by rtm223

I don't fully understand what the inherent requirement of large OR gates on every input is, this sounds like a practical issue of your application, and would probably be required no matter what your core implementation is.

---

Yeah, I agree there's probably not a good way around it in LBP2 (though I wish there were!)

Basically states A, B, and C may all have conditions which cause them to transition to state D. So the input on the selector which activates state D must have an OR gate with three inputs. Not bad in and of itself but with every input having an OR gate on it, and each OR gate having a number of inputs close to the total number of states - it gets a bit cumbersome is all.

The circuit element that was giving me trouble was a timerless one-shot I'd made. As you say, it was holding on to its state. I didn't really dig into the problem to see if I could find a solution, I just gave up on using that one-shot and made a mental note to review the design or scrap the thing...

I mentioned a problem in my implementation where the FSM would momentarily enter the wrong state before entering the right one - that was related to the use of the increment/decrement input of the selector in conjunction with the normal selector inputs. Basically hitting "up" on the D-pad (to get a level-2 happy) and then hitting "down" (to go back to "neutral") resulted in the selector "simultaneously" decrementing and selecting a state. So the sackbot would momentarily go to "level-1 happy" before getting to "neutral". This was noticeable as the Sackbot would open his mouth for a moment before going "neutral".

Adding a slight delay to the outputs before they trigger the sackbot behavior chips would be one way to smooth that out, I'm sure...

Thanks for the response - I do wish there were a better solution to this - even if FSMs aren't the easiest things to implement in digital logic they do seem like a natural choice for implementing various sorts of dynamic behavior...

Quote:

---

Originally Posted by tetsujin

It seems like the way to go is to use a big selector for all the possible states in the machine, with logic combined (via AND) with individual outputs to trigger selector inputs - and then one-shot the various triggers to keep them from producing multiple state changes.

---

TBH, that's about the only method I've ever used, as it's probably the least taxing on the thermo. There may be some gain in breaking into multiple smaller state machines if it simplifies the state transition logic (e.g. in cases where you can exploit the Cycle input), but I suppose the most optimal design will ultimately depend on its required behaviour.