Implementing finite-state-machine AI. (C#)

I was reading this book about state driven AI(Programming Game AI By Example) which clearly explains the structure, however it does so in C++.

I want to re-create this structure, however I'm having a plethora of problems already. This is especially complicated for me because I usually do everything in JS.

(Basic structure)


And here's my code so far:

Code (CSharp):

1. using UnityEngine;
2. using System.Collections;
3. using System.Collections.Generic;
4.  
5. //Imagine that every class here only has a single instance. A singleton without the actual implementation.
6.  
7. public class AI : MonoBehaviour {
8.     Human human;
9.     // Use this for initialization
10.     void Start () {
11.         human = new Human(); //You are trying to create a MonoBehaviour using the 'new' keyword.  This is not allowed.  MonoBehaviours can only be added using AddComponent().  Alternatively, your script can inherit from ScriptableObject or no base class at all.
12.  
13. //Well, Human inherits AI which inherits MonoBehaviour.
14.  
15. //I thought however that inheritance only inherits and doesn't create a new instance. But now that I think about it, that wouldn't make sense.
16.  
17. //What is the work-around for this problem? I can't fathom one at the moment.
18.  
19.         human.Start ();
20.     }
21.  
22.     // Update is called once per frame
23.     void Update () {
24.         human.Update();
25.     }
26. }
27.  
28.  
29.  
30. class Human : AI{
31.     StateMachine stateMachine;
32.     internal void Start(){
33.         stateMachine = new StateMachine ();
34.  
35.         stateMachine.Start ();
36.     }
37.  
38.     internal void Update(){
39.         stateMachine.Update ();
40.     }
41. }
42.  
43.  
44.  
45. class StateMachine:Human{
46.     State state;
47.     public pointer globalState; //A pointer to the current instance of any State class that the AI is currently in.
48.  
49.     internal void Start(){
50.         state = new State ();
51.     }
52.  
53.     internal void ChangeState(/*pointer*/){ //Pointer to a state's class instance.
54.         //globalState = /*pointer*/
55.     }
56.  
57.     internal void Update(){
58.         //state.Execute(globalState);
59.     }
60. }
61.  
62. class State:Human{
63.     internal void Enter(){
64.  
65.     }
66.  
67.     internal void Execute(/*delegate*/){
68.         //delegate.Execute;
69.     }
70. }
71.  
72. class Idle:State{
73.     internal void Enter(){
74.         //Do whatever when starting this state.
75.     }
76.  
77.     internal void Execute(){
78.         //Do whatever Idle state does.
79.     }
80.  
81.     internal void Exit(){
82.         //Do whatever when exiting this state.
83.     }
84. }

So, as you can see there are 2 problems here. The pointer one(which can be solved using a string for the state and a getter that returns the instance of said state. But I didn't try doing this yet, and it wouldn't be as elegant.) and the cannot create MonoBehavior(I still want all the state classes to be able to access the MonoBehavior freely.)

So, C# Gurus, what kind of code structure would I have to implement in order to make this kind of higher structure possible? I can't think of anything that would accommodate for the structure described in the book, but then again I'm very new at C# as a whole.

Thanks.

 

Don't derive StateMachine from Human.

Also, ignore the notion of "pointer" in C#, everything is a pointer, you just don't have to deal with up/down casting.

 

You're confusing yourself with the many C++-isms in the original code, e.g. trying to shoehorn pointers into a language that doesn't have such a construct (as @LightStriker) already pointed out.

Game AI by Example is an excellent book, but I would take the concepts and skip the actual implementation. You don't need to implement your own state machine code as there are already a few options out there that will do that for you. PlayMaker is one example that is built specifically for Unity and allows for visual design of states, transitions and actions.

There's also an open source library for C# called Stateless that does a great job of implementing FSMs in C#. I have used in the past with Unity and found it to be powerful and bug-free.

I also wrote my own library called TinyStateMachine which is even simpler and more lightweight (just one C# file), which is based on writing state transition tables directly in code. But I couldn't be bothered to document it except by writing a few unit tests.

TL;DR: Finite State Machines are good. Game AI by example explains the concepts well, but more elegant implementations can already be found for C#.

 

I see. Thanks for the replies guys.

I looked at some of the libraries and I don't think they'd suit me at the moment. They add a lot of complexity which I have no control over, and I don't understand them very well.

I really do understand and like the structure that is in the OP. However, I have still found no way to do that. Shame indeed.

I have found other implementations, particularly in this stackoverflow thread (http://stackoverflow.com/questions/5923767/simple-state-machine-example-in-c)

I however fail to see how they're different from a bunch of 'if' and 'switch' statements.

What I like about the structure in the OP is that it is very hierarchical and thus manageable and easy to understand(for me.)

I'll post here once I find out what thing I'll do.

 

Maybe your first a.i. should be something less complicated than a human. Try making a statemachine for something not even intelligent. How about a door or a light? It'll get you used to whatever you're unfamiliar with and get you in the right mindset to make a state machine.

I myself as a programmer for over a decade now find using PlayMaker a fun way to organize code into a series of state machines. It's cool to visualize and fun to use, and ridiculously easy to make changes to. But since that's money, here's what I would do for a door by implementing my own little state machine.

Code (CSharp):

1. enum States{closed, opening, open, closing}
2. int doorState = States.closed;
3.  
4. ...
5.  
6. switch(doorState)
7. {
8.     case States.closed:
9.     //execute closed code & listener for interaction
10.     break;
11.     case States.opening:
12.     //execute code for animating the door open, switch to open when done
13.     break;
14.     case States.open:
15.     //listening code for event to close door
16.     break;
17.     case States.closing:
18.     //code to animate door closed and switch to closed state
19.     break;
20. }

 

Well, that kind of implementation is simple. I'll give it a try. Although, I wouldn't want to continue with this kind of implementation.

But, to give everyone a broad idea of what I'm doing - I'm just making a stealth-game prototype.



And I have a script within each human that is called 'DetectBear', this script is in each Human. The script 'AI' is also in each human. Each human also contains 2 trigger colliders, which both contain scripts that simply return a list of objects that are within those colliders.

Code (CSharp):

1.  
2. using UnityEngine;
3. using System.Collections;
4. using System.Collections.Generic;
5.  
6. public class DetectBear : MonoBehaviour {
7.  
8.     private GameObject bear;
9.     private LayerMask mask;
10.     //private PolygonCollider2D polygonCol;
11.     private whoIsInside insideScriptImmidiate;
12.     private whoIsInsideLong insideScriptLong;
13.     private bool bearDetected = false;
14.  
15.     private List<GameObject> listImmediate;
16.     private List<GameObject> listLong;
17.     private RaycastHit2D ray;
18.     // Use this for initialization
19.     void Start () {
20.         bear = GameObject.Find ("Bear"); //Gets our player.
21.         mask = ~(1 << LayerMask.NameToLayer ("FoV")); //Gets FoV layer and puts it into mask so that we ignore the FoV layer.
22.         //polygonCol = transform.Find("FoV").GetComponent<PolygonCollider2D>(); //Gets FoV polygon within the 'FoV' gameobject which contains it.
23.         insideScriptImmidiate = transform.Find("FoVImmediate").GetComponent<whoIsInside>(); //Get who is inside script within FoVImmediate.
24.         insideScriptLong = transform.Find("FoVLong").GetComponent<whoIsInsideLong>();
25.     }
26.    
27.     // Update is called once per frame
28.     private float timerThreshold = 3f; //Time.Delta is in seconds, so is this.
29.     private float timer = 0f;
30.     void Update () {
31.         listImmediate = insideScriptImmidiate.getList ();
32.         listLong = insideScriptLong.getList ();
33.  
34.         ray = Physics2D.Raycast(transform.position,
35.                                             bear.transform.position - transform.position,
36.                                             Mathf.Infinity,
37.                                             mask); //Draw ray from Human to Bear.
38.  
39.         if(listLong.Contains(bear) && ray.collider.gameObject == bear){//If bear is in range and visible.
40.             if(listImmediate.Contains (bear)){
41.                 bearDetected = true;
42.             } else if(listLong.Contains (bear)){
43.                 timer += Time.deltaTime;
44.  
45.                 if (timer > timerThreshold) {
46.                     bearDetected = true;
47.                 }else{
48.                     Debug.DrawRay (ray.point, (new Vector3 (ray.point.x, ray.point.y, 0) - transform.position) * -1, Color.yellow);
49.                 }
50.             }
51.         }else{
52.             timer = 0f;
53.             bearDetected = false;
54.         }
55.  
56.         if (bearDetected) {
57.             Debug.DrawRay(ray.point, (new Vector3(ray.point.x, ray.point.y, 0) - transform.position) * -1, Color.green);
58.             gameObject.GetComponent<AI>().setState(AI.States.panick);
59.         }
60.     }
61. }
62.  

This basically detects the bear in one of the two ways. And as you can see, it also has an if statement at the end that just draws a green ray if the bear is detected, which also changes the state of that particular human. In the future, I'd like a 'global' controller script that will set the state of a human based on its instance id. But, that is not needed right now.

And here's the AI script:

Code (CSharp):

1.  
2. using UnityEngine;
3. using System.Collections;
4. using System.Collections.Generic;
5.  
6. public class AI : MonoBehaviour {
7.     public enum States{idle, panick}
8.     States state = States.idle;
9.     // Use this for initialization
10.     void Start () {
11.  
12.     }
13.    
14.     // Update is called once per frame
15.     void Update () {
16.  
17.         switch (state) {
18.             case States.idle:
19.                 Debug.Log ("I'm idle.");
20.                 break;
21.             case States.panick:
22.                 Debug.Log ("I'm panicking.");
23.                 break;
24.         }
25.  
26.     }
27.  
28.     public void setState(States s){
29.         state = s;
30.     }
31. }
32.  

I like this implementation, except for the switch statement. I want small, manageable chunks of code that are easy to follow.

So, this AI structure and path finding is left. But, I'm stuck at the AI structure right now, especially since I've never done this type of thing before.

 

Finite State machines are all about them switches, bro

Your code will not get more complicated than you see it there. Another class can contain definitions for what needs to be done by each state, and your class you have there can just be the state machine itself. The key will be to design your algorithms to run in single steps, to also match the design of state machines.

Action
Goal test
Success / fail / other event event where you switch states and set values

 

I implemented a FSM based on the concepts in Programming Game AI By Example. From memory the main point of his code was to keep the states as separate classes from the state machine. It went something like this. Be aware this is all just from memory, and may not work properly.

The state machine code. I seem to recall needing to abstract this one step further for flexibility. IE this was a regular C# class owned by a MonoBehaviour. But you should be able to see the general structure here.

Code (CSharp):

1. public class StateMachine : MonoBehaviour {
2.     private State currentState;
3.  
4.     public void SwitchState (State newState){
5.         currentState.EndState(this);
6.         currentState = newState;
7.         currentState.BeginState(this);
8.     }
9.  
10.     void Update (){
11.         if (currentState != null){
12.             currentState.UpdateState(this);
13.         }
14.     }
15. }

Here is the base class for a State.

Code (CSharp):

1. public abstract class State {
2.     public abstract void BeginState(StateMachine stateMachine);
3.     public abstract void UpdateState(StateMachine stateMachine);
4.     public abstract void EndState(StateMachine stateMachine);
5. }

Making the individual states is simply a case of inheriting from the base class.

 

No, it's not. I never have switch/case in my state machine. Each state is a class, and it's to each state to determine how and when to change to another state.

 

That is very true. An abundance of switches is the quickest way to build an unmaintainable state machine.

 

@LightStriker I've been under the impression that a simple finite state machine can be implemented with a switch statement. I learned from reading examples (FSMs implemented in C, C++ and Java using switches) and also, a switch seemed to be a sensible way to turn a diagram for an FSM into code.

I've made classes just to group relevant methods together, but using those classes as the states sounds like transitions / expanding transitions would be a pain. Wouldn't they need a reference to each other since the Type is going to be that class?

@BoredMormon is that so? I've yet to have a problem. How can someone get disorganized if they're using enums?

--edit

Read your post that I missed after mine. I see, so the state-class thing is the implementation style for that author (maybe others? never heard of it myself). I'll look into that. I should know these things if I'm going to be a teacher in 3 years, haha.

It's so easy to find implementation examples that use switches. My learning (for most things) came from tearing apart examples, I've never read the 'proper' ways in how-to books.

 

Switches are fine for a machine with 3 or 4 states. However try implementing a nested state machine with a dozen states on each level, plus global transition, state entrance and exit behaviour and multiple state variables. Do this all with switch statements. Then go back and change the behaviour inside one state completely six months later. You'll get the idea.

Having each state as a separate self contained script has several advantages

• Easier to read an entire states functionality in one place
• The base state machine can be reused every where. Simply plug in a new set of states and you are good to go
• The code complexity does not increase significantly with extra states
• Changing one state does not effect the others. The system is modular enough that you can replace a state entirely without effecting the system.

There are several other ways to implement a state machine, including graphical (with a tool like playmaker) and an event based system (Unity gems has a good frame work). There are others.

As with any frame work there is a trade off between functionality and complexity. For simple jobs the complexity of a fully fledged state machine is not warranted. If you are making a space invaders style AI then a switch statement is probably good enough. But if you want something like Skyrim then you'll need to spend a fair bit more time on your frame work.

 

It really doesn't take much for a switch/case state machine to become a bloated unmaintainable mess. You ends up having a bit of everything all over the place, methods off different state near each other, and a very hard time to insert or remove a state. This kind of state machine is fine when you know exactly what you need, and it is very unlikely to change later - which the design never does, right?

In one game, I even did a door in object-oriented FSM, and it helped... when the design decided the door could be blocked, slammed, crush the player, destroyed... and not just open, opening, closed, closing.

Once you know how an OO FSM works, which is dead easy really, you won't go back. OO FSM really starts to shine when the complexity increases, like with any kind of AI. Using polymorphism for your state is a blessing... By example, if you have a collection of state in the air, a collection on ground, a collection underwater, etc. And then you have player, NPC, enemy, and other that can all share the same states, which is simply impossible with switch/case.

 

@LightStriker I'm sure I'll figure it out when I get that far. My plan for my doctorate, if I can go with the option, is to make a complex state machine to be a good a.i. of my mother's favorite dog who will be near death at that point in time. As for your door example, isn't expanding a switch statement as easy as adding the case to the switch and appending a new state to the enum?

In the event to switch crushed, I would set the state to States.crushed. What you said about them sharing states made me realize my misunderstanding... that's just because your states are methods xP You can share them because they are the behaviors. If that's the point, then I get it now. My [probably outdated] idea of a state machine is that a state is more like a label to group actions together with. I can see now that the correct idea for a state machine is that the states are the actions? Or are both valid but the state-class-function idea scales better?

@BoredMormon I have done such with a switch I went back to a horror game from when I was still new to unity. I added a state to the monster behavior between tracking and killing the player. I added 1 more case to check for the final listen state in which the player might escape if they make no noise.

Maybe I made a flaw in designing my state machine and violated a convention. By making the current state a public variable I could just set it into another state from any point by accessing that variable in the script. And for your fourth point... if you're adding a new state to happen between two other states, don't you have to modify the events to transition into that state? Sounds about the same work for having my function choose the new state instead of the previous one. If this should be obvious, then it's probably a flaw with switch based finite state machines that I overcame by violating a convention for making them I wouldn't know, my top concern has been making things work above all else.

 

If it works for you, then fair enough. But my experience is that switches turn to spaghetti very quickly.

 

I guess I'm not explaining myself properly... A state is not a single action; it has properties, it may have multiple methods, and by experience it is very helping to have a kind of constructor/destruction for when the state starts and when it stops. It's never "as easy as adding an entry in an enum".

They can be shared not because they are method, but because they are object. Each AI can have its own instance of "NPCWalkState", while feeding it with its own parameter, like where a NPC can walk, at what forward speed, what turn speed, etc.

Here's an example of the class hierarchy used in a game I worked on;

Character > Player
Character > NPC
Character > Enemy

State > CharacterState > GroundState > WalkState
State > CharacterState > GroundState > RunState
State > CharacterState > GroundState > SlideState
State > CharacterState > GroundState > StumbleState
State > CharacterState > GroundState > RespawnState
State > CharacterState > AirState > JumpState
State > CharacterState > AirState > DoubleJumpState
State > CharacterState > AirState > DashState
State > CharacterState > AirState > SlamState
State > CharacterState > AirState > DeadState
(and 15 other states like that)

Player, NPC and Enemy have different stats and behaviour. However, they all can use those states;

Code (CSharp):

1. machine.SwitchState(new JumpState(machine, character));

Example of a state;

Code (CSharp):

1. public class JumpState : AirState
2. {
3.     // Velocity, jump height, and other parameter
4.  
5.     public JumpState(StateMachine machine, Character character)
6.         : base(machine, character) { }
7.  
8.     public override void Constructor()
9.     {
10.         base.Constructor();
11.  
12.         Character.Animator.SetTrigger("Jump");
13.         Character.Visual.FXHandler.Jump();
14.  
15.         if (Character is Player)
16.             StatsManager.Instance.Jumped();
17.     }
18.  
19.     public override void Update()
20.     {
21.         UpdateBallisticCurve();
22.  
23.         // Evaluate other possible action in mid air
24.         if (Character.Jump()) // The character has its own input method for deciding an action
25.             Machine.SwitchState(new DoubleJumpState(Machine, Character));
26.  
27.         if (Character.Dash())
28.             Machine.SwitchState(new DashState(Machine, Character));
29.  
30.         if (Character.Slam())
31.             Machine.SwitchState(new SlamState(Machine, Character));
32.  
33.         if (IsGrounded()) // IsGrounded is a method of AirState
34.             Machine.SwitchState(new RunState(Machine, Character));
35.     }
36.  
37.     public override void Destructor()
38.     {
39.         Character.Visual.FXHandler.StopJump();
40.     }
41.  
42.     private void UpdateBallisticCurve()
43.     {
44.         // Jump logic
45.     }
46. }

 

Execution wise? Without a doubt lol. If the behavior is very complex and cannot be broken up, it's entirely up to knowing what enum to search for in your giant switch xD But if the methods are broken up and designed like PlayMaker state machines, your class can be just the switch. Then if you've got a case, method call and break, managing 100 states would be 300 lines.

@LightStriker it's still sounding like a design thing to me. That point regarding the ease of expansion sounds unfortunate. I'll ask a few of the cs graduates about state machines, they might be able to explain it better since they know me lol.

 

Code (CSharp):

1.  
2. using UnityEngine;
3. using System.Collections;
4. using System.Collections.Generic;
5.  
6. public class AI : MonoBehaviour {
7.     StateMachine stateMachine;
8.  
9.     void Start () {
10.         stateMachine = new StateMachine(this);
11.         stateMachine.addState ("Idle", new State_Idle (this));
12.         stateMachine.addState ("Panick", new State_Panick (this));
13.     }
14.  
15.     void Update () {
16.         stateMachine.Update ();
17.     }
18. }
19.  
20. public sealed class StateMachine{
21.     AI ai = null;
22.  
23.     public StateMachine(AI t)
24.     {
25.         ai = t;
26.     }
27.    
28.     //////////////////////////////////////////////////////////
29.     public AI GetAI(){
30.         return ai;
31.     }
32.     //////////////////////////////////////////////////////////
33.     Dictionary<string, State> states = new Dictionary<string, State>();
34.  
35.     public void addState(string s, State o){
36.         states.Add(s, o);
37.     }
38.  
39.     public object getState(string s){
40.         return states[s];
41.     }
42.  
43.     public void Update(){
44.         foreach(KeyValuePair<string, State> state in states)
45.         {
46.             state.Value.Update();
47.         }
48.     }
49. }
50.  
51. public abstract class State
52. {
53.     public string Name { get; set; }
54.  
55.     public abstract void Entry();
56.     public abstract void Update();
57.     public abstract void Exit();
58. }
59.  
60. class State_Idle : State{
61.     string Name = "Idle";
62.     AI ai = null;
63.  
64.     public State_Idle(AI t){
65.         ai = t;
66.     }
67.  
68.     public override void Entry()
69.     {
70.         Debug.Log("Idle Entry");
71.     }
72.  
73.     public override void Update()
74.     {
75.         Debug.Log("Idle Update");
76.     }
77.  
78.     public override void Exit()
79.     {
80.         Debug.Log("Idle Exit");
81.     }
82. }
83.  
84. class State_Panick : State{
85.     string Name = "Panick";
86.     AI ai = null;
87.  
88.     public State_Panick(AI t){
89.         AI ai = t;
90.     }
91.    
92.     public override void Entry()
93.     {
94.         Debug.Log("Panick Entry");
95.     }
96.    
97.     public override void Update()
98.     {
99.         Debug.Log("Panick Update");
100.     }
101.    
102.     public override void Exit()
103.     {
104.         Debug.Log("Panick Exit");
105.     }
106. }
107.  

This is my solution thus far. I'm happy with in, and I hope it will be sustainable and won't need any changes in the future.

This is only the bare-bones structure, I obviously didn't add anything to it yet.

 

How long have you been in this business for? Everything requires changes

 

I've never been in the business ):

 

Knowledge of state machines will be a good resume piece for getting into that business.

 

Actually reading your code this time there is nothing that jumps out at me as bad. You may want to include BeginState and EndState functionality as you go. You also need to define transitions between states.

 

I would dump the dictionary and the strings. Why would you need those?

 

Strings are a double edged sword. On the one hand the offer flexibility that is not otherwise easy to produce. But typos in string introduce hard to spot bugs. In general the conventional wisdom is to avoid strings.

 

My alternative to that would be to just create new states every time instead of reusing them. Is that better?

 

You'll basically be doing that anyway. I haven't bumped up against it yet, but I think I'll just attach scripts as states and enable and disable. Coroutines that check every second would probably be all that's necessary, and the code is going to be unique for the type of npc. Events are more important.

 

It's not like you change state every frame, so the garbage collection should be a non-issue.

 

There are multiple different ways to handle the states. You can use a dictionary and specific state instances if the states need to remember their own data. There is a memory cost to doing this.

You can create new states, there will be a performance and gc cost to soon this. There will also be difficulty storing data between states.

Static states save on memory and GC. But they cannot store any data.

Ultimately you choose what structure works for your project.

Pro tip for working with strings: whenever possible use a variable instead of a hard coded string. In your case State.name. This will dramatically reduce typos.

 

I note that the more experienced programmers are talking about how difficult it is to read a piece of code, while the less experienced programmers are talking about how difficult it is to write a piece of code. Over the long term, 'readable' becomes progressively more important.

The reason to use an Enum instead of a string when possible is to get compiler errors instead of runtime errors. Simple compiler errors are typically fixed in seconds. Simple runtime errors are typically fixed in minutes. Every programmer has a non-zero error rate, and it has an embarrassing tendency to be stable, even though we learn and improve.

 

And the reason to use classes over enum is for flexibility, maintainability and reusability. Viva el polymorphism!

 

Sorry, yes, you're absolutely right. I'm a huge fan of the Strategy pattern, which is what the OO-based approach to state representation seems to be based on. I was weighing in on the discussion about 'strings' without really paying attention to the code sample. (Post #18 is the one where strings entered into the discussion.) Now that I've gotten over my 'half asleep posting' fail, my comment on post #18 is:

If your states have a Name property, then using a dictionary where you add the name as a separate variable compromises maintainability because you have two different entities that are storing the same information. Better to simply use a list and use StateList[index].Name if you want the name of one of the entities in the list.