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