1 Recently, a friend of mine introduced me to the wonderful world of
2 game development with Godot.
3 
4 During the initial (and still ongoing btw) enemy AI implementation, I
5 searched a bit on how to implement a state machine in gdscript.  Now,
6 a state machine isn't something difficult to do, and neither
7 error-prone, but I wanted to know if there was some idiomatic way of
8 doing things.  Oh boy, what I found is rather nice.
9 
10 Let's start with a simple introduction: a state machine (for what
11 matters to us in games) is a way to manage the state of an actor.  It
12 can be the player, or an enemy, or even some other entity (such as an
13 object that can receive inputs).  A state machine is a collection of
14 states, only one of which can be enabled and receive inputs.  We can,
15 of course, change to another state whenever we want.
16 
17 For instance, let's say that we have a player that can run and dash,
18 if we model the player with a state machine we can define two state,
19 `Normal` and `Dash`, with `Normal` being the default, and switch to
20 `Dash` when a key is pressed, and then from the `Dash` state return to
21 the `Normal` state when a certain amount of time has passed.
22 
23 Another example can be the enemies: they're in a `Wandering` state by
24 default but if they see a player they start following it, and thus
25 they change their state to `Chase`.  Then, if the player dies, or it's
26 too far away, they can switch back to `Wandering`.
27 
28 There may be other ways to manage states, but I do really like the
29 state machine abstraction (not only in games), and the code is pretty
30 clean and simple to maintain, so...
31 
32 ---
33 
34 The simplest way to implement such machine in gdscript is something
35 along the lines of:
36 
37 ```gdscript
38 enum states { WANDERING, CHASING, FLEEING }
39 
40 var state = WANDERING
41 
42 
43 func _process(delta):
44   if state == WANDERING:
45     do_wandering_process(delta)
46   elif state == CHASING:
47     do_chasing_process(delta)
48   else:
49     do_fleeing_process(delta)
50 
51 
52 func do_wandering_process(delta):
53   if can_see_player():
54     state = CHASING
55   else:
56     move_randomly()
57 
58 # ...
59 ```
60 
61 and this is fine.  Rather verbose, if I you ask me, but it's fine, and
62 it works.
63 
64 It turns out we can do better, like [this article on
65 gdscript.com](https://gdscript.com/godot-state-machine) shows.  Their
66 proposed approach involves a node, called `StateMachine`, which
67 manages the states, and some sub-nodes where you implement the logic
68 for that state.  There are some bits that I think can be done better,
69 so here's a (in my opinion) slightly better state machine (using typed
70 gdscript this time):
71 
72 ```gdscript
73 # StateMachine.gd
74 extends Node
75 class_name StateMachine
76 
77 const DEBUG := false
78 
79 var state
80 var state_name := "default state"
81 
82 func _ready() -> void:
83   state = get_child(0)
84   _enter_state()
85 
86 
87 func change_to(s : String) -> void:
88   state_name = s
89   state = get_node(s)
90   _enter_state()
91 
92 
93 func _enter_state() -> void:
94   if DEBUG:
95     print("entering state ", state_name)
96   state.state_machine = self
97   state.enter()
98 
99 
100 # proxy game loop function to the current state
101 
102 func _process(delta : float) -> void:
103   state.process(delta)
104 
105 
106 func _physics_process(delta : float) -> void:
107   state.physics_process(delta)
108 
109 
110 func _input(event : InputEvent) -> void;
111   state.input(event)
112 ```
113 
114 (if you're wondering why I've type-annotated everything but the `var
115 state`, that is due a current limitation of the type annotations in
116 Godot: if class A has annotation of class B, then class B cannot have
117 annotations of A.  This limitation is known and is worked on, future
118 version of Godot won't have this problem.)
119 
120 The state machine proposed is very simple: it holds a current state
121 and provides a `change_to` function to change the state.  That's it.
122 
123 Where my implementation differs from the one linked before, is in the
124 implementation of the states.  All my states inherits from the `State`
125 node, so all that machinery with `has_method` isn't needed.  The
126 implementation of the superclass `State` is as follow:
127 
128 ```gdscript
129 # State.gd
130 extends Node
131 class_name State
132 
133 var state_machine : StateMachine
134 
135 func enter() -> void:
136   pass
137 
138 func process(_delta : float) -> void:
139   pass
140 
141 func physics_process(_delta : float) -> void:
142   pass
143 
144 func input(_event : InputEvent) -> void:
145   pass
146 ```
147 
148 One additional features this approach offers that the previous don't
149 is the `enter` function.  Sometimes you want to perform action upon
150 entering a state (like changing the animation and stuff), and it's
151 cleaner to have an explicit `enter` function that gets called.
152 
153 Then, we can define states as:
154 
155 ```gdscript
156 # WanderingState.gd
157 extends State
158 
159 # myself
160 onready var enemy : Actor = get_node("../..")
161 
162 func process(delta : float) -> void:
163   if can_see_player():
164     state_machine.change_to("ChasingState")
165   else:
166     move_randomly()
167 ```
168 
169 and as
170 
171 ```gdscript
172 # ChasingState
173 extends State
174 
175 # myself
176 onready var enemy = get_node("../..")
177 
178 func process(delta : float) -> void:
179   if player_is_dead():
180     state_machine.change_to("WanderingState")
181   elif enemy.life < FLEE_THRESHOLD:
182     state_machine.change_to("FleeingState")
183   else:
184     ememy.velocity = move_and_slide(...)
185 ```
186 
187 with a scene tree as follows:
188 ```tree
189 Enemy (KinematicBody2D in my case)
190  |- ...
191  `- StateMachine
192      |- WanderingState
193      |- ChasingState
194      `- FleeingState
195 ```
196 
197 (the `get_node("../..")` is used to get the `Enemy` from the states,
198 so they can change parameters.)
199 
200 This way, each state gets its own script with its own
201 `process`/`physics_process`, as well as with their private variables
202 and functions.  I really like the approach.
203 
204 A final note: I didn't take benchmarks on any of the proposed
205 approaches, so I don't know what is the fastest.
206 
207 ## Addendum: Pushdown Automata
208 
209 One additional thing that sometimes you want your state machine is
210 some sort of history.  The state machine as defined in the previous
211 example doesn't have a way to _go back_ to a previous state.  The
212 linked article solves this by using a stack (really an array) where
213 upon changing state the old state get pushed.
214 
215 I honestly don't like the approach.  Let's say that you have three
216 states `A`, `B` and `C`, and that only `C` can, sometimes, go back in
217 history, but `A` and `B` never do so.  With a simple stack you can get
218 a situation where you have
219 
220 ```gdscript
221 oldstates = [A, B, A, B, A, B, A, B, A, B, ...]
222 ```
223 
224 that is wasting memory for no good.
225 
226 One way to have record history but save some memory can be along the lines
227 of what follows:
228 
229 ```gdscript
230 # StateMachine
231 extends Node
232 class_name StateMachine
233 
234 var state
235 var last_state
236 var history = []
237 
238 func change_to(s : String) -> void:
239   last_state = state
240   state = get_node(s)
241   _enter_state()
242 
243 func prepare_backtrack() -> void:
244   history.push_front(last_state)
245 
246 func pop() -> void:
247   history.pop_front()
248 
249 func backtrack() -> void:
250   state = history.pop_front()
251   if state.count() > 0:
252     last_state = state[0]
253   _enter_state()
254 
255 # the rest is not changed
256 ```
257 
258 and then call `state_machine.prepare_backtrack()` on `C` `enter`
259 function.  Then, if `C` wants to backtrack it can simply call
260 `backtrack()`, otherwise if it wants to change to another state, say
261 `B`, it can do so with:
262 
263 ```gdscript
264 state_machine.pop()
265 state_machine.change_to("B")
266 ```
267 
268 This approach isn't as idiot-proof as the one in the linked article,
269 but if used with a little bit of care can provide a pushdown automata
270 without memory wasting for states that don't backtrack.