commit 52bf2367389b040e2be517a9c6eeaada641dea72 from: Omar Polo date: Wed Apr 29 15:34:04 2020 UTC blogged about finite state automata with Godot commit - d3dca3c29985d069b8d12d92e48671fedcaeb704 commit + 52bf2367389b040e2be517a9c6eeaada641dea72 blob - /dev/null blob + 47cef5fb6c782cced82c182b603c2f6864d1485a (mode 644) --- /dev/null +++ resources/posts/finite-automata-godot.md @@ -0,0 +1,269 @@ +Recently, a friend of mine introduced me to the wonderful world of +game development with Godot. + +During the initial (and still ongoing btw) enemy IA implementation, I +searched a bit on how to implement a state machine in gdscript. Now, +a state machine isn't something difficult to do, and neither +error-prone, but I wanted to know if there was some idiomatic way of +doing things. Oh boy, what I found is rather nice. + +Let's start with a simple introduction: a state machine (for what +matters to us in games) is a way to manage the state of an actor. It +can be the player, or an enemy, or even some other entity (such as an +object that can receive inputs). A state machine is a collection of +states, only one of which can be enabled and receive inputs. We can, +of course, change the state whenever we want. + +For instance, let's say that we have a player that can run and dash, +if we model the player with a state machine we can define two state, +`Normal` and `Dash`, with `Normal` being the default, and switch to +`Dash` when a key is pressed, and then from the `Dash` state return to +the `Normal` state when a certain amount of time has passed. + +Another example can be the enemies: they're in a `Wandering` state by +default but if they see a player they start following it, and thus +they change their state to `Chase`. Then, if the player dies, or it's +too far away, they can switch back to `Wandering`. + +There may be other way to manage the state, but I do really like the +state machine abstraction (not only in games), and the code is pretty +clean and simple to maintain, so... + +--- + +The simplest way to implement such machine in gdscript is something +along the lines of: + +```gdscript +enum states { WANDERING, CHASING, FLEEING } + +var state = WANDERING + + +func _process(delta): + if state == WANDERING: + do_wandering_process(delta) + elif state == CHASING: + do_chasing_process(delta) + else: + do_fleeing_process(delta) + + +func do_wandering_process(delta): + if can_see_player(): + state = CHASING + else: + move_randomly() + +# ... +``` + +and this is fine. Rather verbose, if I you ask me, but it's fine, and +it works. + +It turns out we can do better, like [this article on +gdscript.com](https://gdscript.com/godot-state-machine) shows. Their +proposed approach involves a node, called `StateMachine`, which +manages the states, and some sub-nodes where you implement the logic +for that state. There are some bits that I think can be done better, +so here's a (in my opinion) slightly better state machine (using typed +gdscript this time): + +```gdscript +# StateMachine.gd +extends Node +class_name StateMachine + +const DEBUG := false + +var state +var state_name := "default state" + +func _ready() -> void: + state = get_child(0) + _enter_state() + + +func change_to(s : String) -> void: + state_name = s + state = get_node(s) + _enter_state() + + +func _enter_state() -> void: + if DEBUG: + print("entering state ", state_name) + state.state_machine = self + + +# proxy game loop function to the current state + +func _process(delta : float) -> void: + state.process(delta) + + +func _physics_process(delta : float) -> void: + state.physics_process(delta) + + +func _input(event : InputEvent) -> void; + state.input(event) +``` + +(if you're wondering why I've type-annotated everything but the `var +state`, that is due a current limitation of the type annotations in +Godot: if class A has annotation of class B, then class B cannot have +annotations of A. This limitation is known and is worked on, future +version of Godot won't have this problem.) + +The state machine proposed is very simple: it holds a current state +and provides a `change_to` function to change the state. That's it. + +Where my implementation differs from the one linked before, is in the +implementation of the states. All my states inherits from the `State` +node, so all that machinery with `has_method` isn't needed. The +implementation of the superclass `State` is as follow: + +``` +# State.gd +extends Node +class_name State + +var state_machine : StateMachine + +func enter() -> void: + pass + +func process(_delta : float) -> void: + pass + +func physics_process(_delta : float) -> void: + pass + +func input(_event : InputEvent) -> void: + pass +``` + +One additional features this approach offers that the previous don't +is the `enter` function. Sometimes you want to perform action upon +entering a state (like changing the animation and stuff), and it's +cleaner to have an explicit `enter` function that gets called. + +Then, we can define states as: + +```gdscript +# WanderingState.gd +extends State + +# myself +onready var enemy : Actor = get_node("../..") + +func process(delta : float) -> void: + if can_see_player(): + state_machine.change_to("ChasingState") + else: + move_randomly() +``` + +and as + +```gdscript +# ChasingState +extends State + +# myself +onready var enemy = get_node("../..") + +func process(delta : float) -> void: + if player_is_dead(): + state_machine.change_to("WanderingState") + elif enemy.life < FLEE_THRESHOLD: + state_machine.change_to("FleeingState") + else: + ememy.velocity = move_and_slide(...) +``` + +with a scene tree as follows: +``` +Enemy (KinematicBody2D in my case) + |- ... + \- StateMachine + |- WanderingState + |- ChasingState + \- FleeingState +``` + +(the `get_node("../..")` is used to get the `Enemy` from the states, +so they can change parameters.) + +This way, each state gets its own script with its own +`process`/`physics_process`, as well as with their private variables +and functions. I really like the approach. + +A final note: I didn't take benchmarks on any of the proposed +approaches, so I don't know what is the fastest. + +## Addendum: Pushdown Automata + +One additional thing that sometimes you want your state machine is +some sort of history. The state machine as defined in the previous +example doesn't have a way to _go back_ to a previous state. The +linked article solves this by using a stack (really an array) where +upon changing state the old state get pushed. + +I honestly don't like the approach. Let's say that you have three +states `A`, `B` and `C`, and that only `C` can, sometimes, go back in +history, but `A` and `B` never do so. With a simple stack you can get +a situation where you have + +```gdscript +oldstates = [A, B, A, B, A, B, A, B, A, B, ...] +``` + +that is wasting memory for no good. + +One way to have record history but save some memory can be along the lines +of what follows: + +```gdscript +# StateMachine +extends Node +class_name StateMachine + +var state +var last_state +var history = [] + +func change_to(s : String) -> void: + last_state = state + state = get_node(s) + _enter_state() + +func prepare_backtrack() -> void: + history.push_front(last_state) + +func pop() -> void: + history.pop_front() + +func backtrack() -> void: + state = history.pop_front() + if state.count() > 0: + last_state = state[0] + _enter_state() + +# the rest is not changed +``` + +and then call `state_machine.prepare_backtrack()` on `C` `enter` +function. Then, if `C` wants to backtrack it can simply call +`backtrack()`, otherwise if it wants to change to another state, say +`B`, it can do so with: + +``` +state_machine.pop() +state_machine.change_to("B") +``` + +This approach isn't as idiot-proof as the one in the linked article, +but if used with a little bit of care can provide a pushdown automata +without memory wasting for states that don't backtrack. blob - 2e53737ddc08fc258c7beca468780b6ca6d63ff1 blob + 2427a0497c86ab1b9f605664a495a58f278b1e95 --- src/blog/posts.clj +++ src/blog/posts.clj @@ -1,3 +1,9 @@ +(add-post! {:title "Finite State Machine in Godot" + :slug "finite-automata-godot" + :date "2020/04/29" + :tags #{:godot} + :short "Did I mention how I love finite automata?"}) + (add-post! {:title "cgit & gitolite" :slug "cgit-gitolite" :date "2020/04/22"