I think software architecture is all about the things you choose to enumerate and trade-off extensibility in return for the tight control you gain from having a finite universe (like the possibility of having “static” analysis, not in the conventional sense of “compile-time”, but in the sense that you have information about a computation before running it).
State machines are very special constructs in the world of programming. With them, you choose to enumerate the states that your software components can be in. It gives you extremely tight control over what exactly goes on in your software, but on the other hand the state diagrams become extremely complex in real world scenarios. We’re talking about tens of thousands of states and an order of magnitude more state transitions.
So the trick to state machines is how you choose to factor them! If your state machine looks like a near-perfect grid of states with transitions virtually only between neighbors, an explicit state diagram will contain 10000 states and ~20000 state transitions for a 100x100 grid but with a formalism that allows you to express grids, you’ll just say something like grid(100,100).
Another way of factoring state machines (and far more popular) is through hierarchical states, where you have “composite” states that contain other “substates” and a transition from a composite state to another state means, in the explicitly enumerated state diagram, a transition from each of the substates.
Another factorization way I can think of is behavior trees! They’re quite popular in gamedev, and they’re just a particular way of factorizing state machines in disguise. If your state machine mostly looks like a linear sequence of states (i.e, there’s an obvious flow), you might be able to reduce its complexity greatly by expressing it as a behavior tree.
So, whenever I see someone building a piece of software infrastructure built around state machines, and they show nice examples with toy state diagrams, I immediately seek the information about the kinds of factorizations they support, because plain state machines are not usable in the real world.
I had this same thought (though not as well expressed). In server coding, I really want higher level abstractions, not lower. Boxing the complexity is key to making the thing debuggable later. If you have to write a lot of the lower layers, like state machines, you can end up surrounded by so many trees that it’s no longer possible to really see the whole forest.
Behavior trees sound interesting, do you have any good starting references for them?
This is the blog post I’ve read when I first heard about them. I’m sure there’s a lot of academic literature around them, but the core idea is quite simple, so after having read that tutorial post I decided that’s what I needed for my game and implemented my own behavior trees tailored to my needs. They ended up being great! They let you define reusable and composable behavior pieces for your game objects. I heard they’re also quite popular in robotics for obvious reasons.
Great read. You should post this as a story!
Thanks for the advice, seems like it was already posted a year ago: https://lobste.rs/s/1fjtfx/behavior_trees_for_ai_how_they_work
I think the comment was for you to write up your experience implementing it…if not, then I’ll take this opportunity to suggest that you write up your experience. :)
That’s what I thought at first too, but considering hwayne replied to my comment providing the link to the blog post, I decided he referred to the linked post. Now that you’re explicitly suggesting the former, that might be just enough push for me to write a post and open-source my ad-hoc implementation (C++).
I didn’t even consider you doing a writeup of your own experiences but now that @jitterted suggested it I can’t second that enough.
I think you can second something at most once, then you’d be applying the consecutive ordinals :) Thanks for the encouragement, I’ll try to get down to it as soon as possible and inform you guys when it’s finished.