State Machines

The Partridge Family were neither partridges nor a family. Discuss.
albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

State Machines

Post by albinopapa » February 11th, 2019, 4:50 am

In chili's original Intermediate series he covers Finite State Machines. A state machine I suppose is a way of organizing your code so that it only runs a specific set of instructions depending on the state an object is in.

If I recall correctly the example he used is a turn style. The starting state is locked waiting for the correct amount of change or a ticket. Once the transaction is processed, it triggers a transition to an unlocked state allowing for passage. Once the turn style has been used, the state is then transition to the locked state waiting for the next customer.

There are a couple ways to show this in code:

The boolean

Code: Select all

int main()
{
	constexpr int admission = 50  // 50 cents
	constexpr int maxRotation = 120  // 120 degrees
	bool isLocked = true;
	int deposit = 0;
	int angle = 0;

	while( true )
	{
		if( isLocked )
		{
			deposit -= GetAmountDeposited();
			if( deposit >= admission )
			{
				isLocked = false;
				UnlockTurnStyle();
				MakeChange( std::abs( deposit ) );
				continue;
			}
		}

		angle += GetCurrentRotation();
		if( angle == 120 || angle == 240 || angle == 360 )
		{
			angle %= 360;
			isLocked = true;
			LockTurnStyle();
		}
	}
}
The enumeration:

Code: Select all

int main()
{
	enum class TSState
	{
		Locked, Unlocked
	};

	TSState tsState = TSState::Locked;
	while( true )
	{
		switch( tsState )
		{
			case TSState::Locked:
				deposit -= GetAmountDeposited();
				if( deposit >= admission )
				{
					tsState = TSState::Unlocked;
					UnlockTurnStyle();
					MakeChange( std::abs( deposit ) );
				}
				break;
			case TSState::Unlocked:
				angle += GetCurrentRotation();
				if( angle == 120 || angle == 240 || angle == 360 )
				{
					angle %= 360;
					tsState = TSState::Locked;
					LockTurnStyle();
				}
				break;
		}
	}
}
The OOP approach ( this approach was used in Chili's original intermediate series )

Code: Select all

class TSState
{
public:
	TSState( class TurnStyle& _turnstyle );
	virtual void Do() = 0;

protected:
	class TurnStyle& turnstyle;
	int deposit = 0;
	int angle = 0;
	bool isLocked = true;
	static constexpr int admission = 50;  // 50 cents
	static constexpr int maxRotation = 120;  // 120 degrees
};

class TurnStyle
{
public:
	TurnStyle()
		:
		m_state( std::make_unique<TSStateLocked>( *this ) )
	{}

	void Update()
	{	
		m_state->Do();			
	}
private:
	friend class TSStateLocked;
	friend class TSStateUnlocked;

	int GetAmountDeposited();
	void MakeChange( int );
	int GetCurrentRotation();
	void LockTurnStyle();
	void UnlockTurnStyle();
	void Transition( std::unique_ptr<TSState> _state )
	{
		m_state = std::move( _state );
	}
private:
	std::unique_ptr<TSState> m_state;
};

class TSStateLocked : public TSState
{
public:
	void Do() override;
};

class TSStateUnlocked : public TSState
{
public:
	void Do() override;
};

TSState::TSState( TurnStyle& _turnstyle )
	:
	turnstyle( _turnstyle )
{}

void TSStateLocked::Do()
{
	deposit -= turnstyle.GetAmountDeposited();
	if( deposit >= admission )
	{
		turnstyle.UnlockTurnStyle();
		turnstyle.MakeChange( std::abs( deposit ) );
		turnstyle.Transition( std::make_unique<TSStateUnlocked>( turnstyle ) );
	}
}

void TSStateUnlocked::Do()
{
	angle += GetCurrentRotation();
	if( angle == 120 || angle == 240 || angle == 360 )
	{
		angle %= 360;
		turnstyle.LockTurnStyle();
		turnstyle.Transition( std::make_unique<TSStateLocked>( turnstyle ) );
	}
}

int main()
{
	TurnStyle turnstyle;

	while( true )
	{
		turnstyle.Update();
	}

	return 0;
}
Hopefully this one isn't overkill, but using C++17's std::variant:

Code: Select all

class TurnStyle;

class TSStateLocked
{
public:
	void Do( TurnStyle& _turnstyle );

private:
	static constexpr int admission = 50;
	int deposit = 0;
};

class TSStateUnlocked
{
public:
	void Do( TurnStyle& _turnstyle );

private:
	int GetCurrentRotation()const noexcept;

private:
	int angle = 0;
};


using TSState = std::variant<TSStateLocked, TSStateUnlocked>;
class TurnStyle
{
public:
	TurnStyle()
		:
		m_state( TSStateLocked{} )
	{}
	void Update()
	{	
		auto doState = [ this ]( auto& _state ) { _state.Do( *this ); };
		std::visit( doState, m_state );
	}
private:
	friend class TSStateLocked;
	friend class TSStateUnlocked;

	int GetAmountDeposited();
	void MakeChange( int );
	int GetCurrentRotation();
	void LockTurnStyle();
	void UnlockTurnStyle();

	template<typename T>
	void Transition( T _state )
	{
		m_state = _state;
	}
private:
	TSState m_state;
};

void TSStateLocked::Do( TurnStyle& _turnstyle )
{
	deposit -= _turnstyle.GetAmountDeposited();
	if( deposit >= admission )
	{
		_turnstyle.UnlockTurnStyle();
		_turnstyle.MakeChange( std::abs( deposit ) );
		_turnstyle.Transition( TSStateUnlocked() );
	}
}

void TSStateUnlocked::Do( TurnStyle& _turnstyle )
{
	angle += GetCurrentRotation();
	if( angle == 120 || angle == 240 || angle == 360 )
	{
		angle %= 360;
		_turnstyle.LockTurnStyle();
		_turnstyle.Transition( TSStateLocked() );
	}
}

int main()
{
	TurnStyle turnstyle;

	while( true )
	{
		turnstyle.Update();
	}
}
( continued discussion in next post )
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: State Machines

Post by albinopapa » February 11th, 2019, 5:14 am

First, I'd like to point out a few things about the different approaches.

Using bools
In this example, there are only two states, locked or unlocked. You could expand those states to Locked, ReceivingTokens,Unlocking,Unlocked,CrankTurning. Then repeat back to Locked. The logic for each state would require to if statement gymnastics and gets quite confusing. So for simple "two state" state machines a boolean might work just fine.

The enumeration
If we did break up each stage of the turn style or had an object with more states or more complex conditions for determining state, we would want to use enumerations. This allows us to only care about the logic associated for that particular state. The drawback in the code above would be the amount of room the logic takes up between cases. This of course can be dealt with by calling a function like; HandleLockedState() or HandleUnlockingState(). Another drawback which state machines based on bools and enums have is the need to reconfirm state at different points in the program. In the game world, you are going to have at least two phases, the update phase and the render phase. You will determine the state in the update phase, but then render something based on it's state which will have to be reconfirmed. The last drawback I can think of is adding or removing states as development carries on. You will have to track down each place a state was mentioned and handle that section of code. Depending on choices, this can make it very difficult to untangle.

Object oriented
You might look at it and decide "that's a lot of boiler plate", and you'd be right. I didn't realize this before I went down this path just how much extra code was needed to get this approach to work. However, it's code that is all "out of the way" and not a part of the main flow of the program. So if you see in the main() function, it's a simple call to turnstyle.Update() within the while loop. The TurnStyle object takes care of it's own state, the states handle what the turnstyle object does according to the rules of each state. There's no need to reconfirm the state in separate functions and the main logic or update phase is nice and clean.

The std::variant
There are a number of ways to implement the variant approach, I tend to prefer this for this example. Other ways are a bit more involved and there is even a way to mimic the inheritance model. This method is very similar to the inheritance model with the added bonus of not being dynamically dispatched, as in there is no vtable lookup. It knows the type and just calls the correct Do() function directly. There are no pointers, so no indirection, no dynamic memory allocation/deallocation. It can be kind of tough to get into std::variant, but if you need every ounce of speed and reduced memory footprint it's a must, make sure your algorithms are the bottleneck though, they of course will have a greater impact than any speed gains using std::variant over dynamic polymorphism.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: State Machines

Post by albinopapa » February 11th, 2019, 5:26 am

You might have picked up on the reason for a state machine. It's to separate the logic of each state more clearly. This will help some logic bugs you may run into. Depending on which method you choose, this could reduce the amount of code you have to write and maintain. It should reduce the amount of time spent finding certain bugs.

I was trying to make a game a while back that allowed for wall jumping. I had a hard time figuring it out and all it took was separating out some logic into another state to get it to work. Since the states were separated, I was able to confine my efforts into one or two spots in code.

You can imagine what the states were:
Idle, Walking, Running, Jumping, WallJumping, Crouching, and Rolling ( somersaulting, like Samus morphball in metroid ).

In the project I used enums because of the convenience of having all the code right there in front of me, but if I did it all over again or went back to it, I'd go with the dynamic polymorphism. It's less cumbersome than the std::variant route and it wasn't a very taxing game so I wouldn't have needed to go through the trouble of using variant. It would have made the code more scattered around, but the main game loop would have been a lot cleaner and the code with any bugs would have at least been all in the same file even with other parts of the logic in other files.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: State Machines

Post by albinopapa » March 27th, 2019, 7:52 am

Well, I hate to admit it, but I'm an unoriginal bastard.

I floundered for a few weeks and couldn't come up with any ideas of my own, so about 2-3 days ago I was reading through the forum and for some reason a game by a user named Clodi caught my attention called BoxWars. He posted it back in 2012 and I'm assuming it was pretty early on in the tutorials, but a fun game nonetheless.

After looking through his code I quickly realized this would be a perfect project to show off how to do a state machine using std::variant. The original version uses bools for every state from which menu your in to language selection ( yes, there are five languages to choose from ).

Now, I'm not saying the way I have implemented the states with variant is the best way or even the intended way, but to be honest it feels more natural the way I have done it.

Here's the repo of my version. There are a few graphical changes from the original, but functions the same.

I'll try the other ways of using std::variant and std::visit and see how it looks. Once the project has been converted to the other ways, they will be in their own branches.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: State Machines

Post by albinopapa » March 27th, 2019, 7:49 pm

Lambda inheritance
Visitor structures

So, I'm going to go out on a limb here and say that my original way has the benefit of looking a lot more familiar and clean.

The way I did the visitor structs probably isn't going to be doable or acceptable since I basically made the different states just tags to switch on, and the structures redirected their state to the functions in the Game class. The only reason I say this, is for things other than state or for many many more states, you probably wouldn't to shove everything inside the Game class. This means you are stuck with the design decisions I made with the first original refactor, and having global state for certain things ( Settings class in my case ), or you end up declaring all the visitors as friend.

The lambda inheritance version looks horrible and I think the idea of this technique is to use smaller lambdas, so maybe have the actual implementations in functions inside Game like I did with the structs, but if that's the case, I wouldn't even have to use the Overload class.

Code: Select all

void Game::OnTransition( NewGameMenu& _state){ ... }
void Game::OnTransition( LoadGameMenu& _state){...}

void UpdateModel()
{
   std::visit( [&]( auto& _state ){OnTransition( _state ); }, state );
   // versus
   std::visit( Overload{
      [&]( NewGameMenu& _state ){ OnTransition( _state ); }, 
      [&]( LoadGameMenu& _state ){ OnTransition( _state ); }
   }, state );
}
This is why I think that the inheritance version is meant for shorter blocks of code. It would be cleaner to just use the visit function and some actual overloaded implementation functions and let the compiler choose best fit than to create all those lambdas and fill in the implementation of each state.

I originally refactored this code using enums for state, then refactored it to the one in the master branch. Another way my version makes things easier is some variables need to be reset ( like the cursor index, the World object, and all the buttons and text boxes) and using RAII I don't have to specifically reset them, just happens automatically.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: State Machines

Post by chili » March 28th, 2019, 11:06 am

I just wanna say, your README.md looks dope. :D
Chili

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: State Machines

Post by albinopapa » March 28th, 2019, 5:06 pm

Thanks, turned out looking better than I expected. I like how there is some syntax coloring and would love for that to happen here on the forums, but I'm guessing it's a javascript script that is doing all that.

Anyway, yeah, don't know why std::variant is my drug of choice to get hung up on, but at least I got the state machine example I was looking for.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: State Machines

Post by chili » April 2nd, 2019, 4:52 am

Well, it does give you cache locality with polymorphism, and the visit scaffolding is nice. On the other hand, that sort of perf concern probably isn't going to be that common with most state machine systems you make, and a virtual call-based polymorphic approach will likely be more flexible.
Chili

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: State Machines

Post by albinopapa » April 2nd, 2019, 5:49 pm

chili wrote:On the other hand, that sort of perf concern probably isn't going to be that common with most state machine systems you make, and a virtual call-based polymorphic approach will likely be more flexible.
As far as performance concerns, I came across a video a few months ago that claimed that using switch cases are even faster in some cases than std::variant. The reason for this was switch uses a "jump to this instruction" while std::variant is implemented using a compiler generated function pointer table. After looking through the source code for std::visit and std::variant, that's pretty much what it is. The compiler generates a list of function pointers and associates them with a compile time ID based on it's position in the template parameter list when std::variant declared. It uses the ID as an index into the table, then calls that function.

I'm thinking you could pull this off using some constexpr-if statements, some static_casts and a couple of enum class or constexpr ints inside each of your classes to determine type which might net you similar results. The only reason I bring this up is the template programming for std::variant et al is insane genius/magic.

You are sort of right about the flexibility of dynamic polymorphism IMO. With dynamic polymorphism you, as an end user, are able to extend a library implementation just by inheriting from the base or interface class. With std::variant, there is no extending without modifying the source code of the library. Even as the sole developer, you would have to add a new class which has the same interface, then add the class to the template parameter list of the std::variant, so in that sense, you'd also be losing out in flexibility. However, it's still easily entendable, just not as easily as dynamic polymorphism.

As has been discussed between cyboryxmen and myself some time ago in another thread, vtable lookup isn't the biggest performance bottleneck, but the dynamic allocation/deallocation that is required for traditional dynamic polymorphism and data locality. For state machines, you are absolutely correct, you shouldn't be changing state every frame so it shouldn't make a huge impact and a dynamic polymorphism approach is much simpler to implement and is probably what I would recommend for state machines as well.

I'm not saying your approach of using state machines for character movement in the old intermediate series platformer is the best example, but in that case, it's possible that states will change quite frequently and in a different situation like developing an RTS type game where there are hundreds of entities in the world to change state, the traditional DP approach MIGHT become an issue. First off, 1,000 different entities each requiring their own DP implemented state machine with ( Idle, Walk, Attack, Die ), that's a lot of allocations as each new entity is created the state machine also must be created. The deallocatins as each state transitions and each entity dies would add up.

To simplify, changing game state or screen state, in other words something that doesn't change all that often and doesn't affect game play, it would be fine to use dynamic polymorphism. For changing the state often like entity state, I'd probably go with the std::variant approach. The nice thing about std::variant is that it plays well with inheritance. You can still have a base class which implements common functionality as well as having virtual functions. So your entities can all be stored in a vector to get cache friendly data locality, you get code reuse from the base class, you can get polymorphic behavior passing to functions taking a reference/pointer to base class, for instances you need the type information, you can pass the variant object by reference to a function then use std::visit with whatever method suits you ( lambda inheritance, visitor structures ) or whatever.

One method of getting around virtual function calls, is to use CRTP ( curiously recurring template pattern ), but this too has some curious restrictions. For one, since you aren't using virtual functions, your implementation ( child class ) has to have different names than the base class. For instance, you might have a Base<Derived>::Draw() function, but you aren't suppose to have the same name in your Entity child class. This is called name hiding I think. So you'd need to name it something like Hero::DrawImpl(), then in your base class Base<Derived>::Draw(){ static_cast<const Derived&>(*this).DrawImpl(); }. CRTP does nothing for data locality though. You still can have a single vector, because each base class is of a different type.
Base<Hero> hero;
Base<Goblin> goblin;
Base<Troll> troll;

You can pass these around in a DP way though, using some template programming:

Code: Select all

template<typename EntityType>
void Game::UpdateEntity( Base<EntityType>& _entity, float _deltaTime )
{
   _entity.Update( _deltaTime );
}
This ensures that only objects derived from Base can be passed in.
I've messed around a bit with mixing CRTP with std::variant, but the results were inconclusive as I made a few mistakes while testing. I thought I could just store a pointer to the derived class in the base class so I didn't have to keep casting the 'this' pointer, but this lead to multiple data being created instead of pointing to the same data. Plus, I wasn't sure if I should be creating a variant list of the concrete types or of the base class types, both approaches worked though.

One of the benefits of using CRTP ( without std::variant and aside from avoiding virtual function calls ) is you can extend the original implementation through inheritance just like the DP approach. So a library designer can create an interface with some predefined behavior and call your implementation's Derived::*impl function for custom behavior. As stated though, virtual function calls aren't the biggest bottleneck, so I'm not entirely sure why anyone would choose this option without using std::variant or some manual memory management model that is similar to get rid of the true bottleneck of dynamic memory allocations/deallocations and lack of data locality.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: State Machines

Post by chili » April 4th, 2019, 12:59 pm

The real question though isn't whether variant is faster than an approach that uses virtual/dynamic (it pretty much always will be), but whether it actually matters, and whether it is actually worth it. In order for the lack of inlining and memory latency to even be worth considering, you'll need to be dealing with a rather large amount of entities at once, and to be honest, most use cases don't need that. For every use case where the sacrifice in code flexibility, decoupling, and just developer man-hours in general would actually be worth considering, you'll find 20 where the cost-benefit analysis doesn't add up.
Chili

Post Reply