# Roguelike with effect handlers

> **WARNING** This is an experimental feature and syntax, you should not count on it being supported by future releases of OCaml! [Proceed with caution!](https://discuss.ocaml.org/t/tutorial-roguelike-with-effect-handlers/9422/4)

In my [previous notes about effect handlers](https://hackmd.io/@yF_ntUhmRvKUt15g7m1uGw/Bk-5NXh15), I mentioned that algebraic effects were going to be great for scripting control flow. It's time to see them in action! We are going to implement a small roguelike, where the player controls a camel lost in the desert:


If you want to follow along, this local switch works nicely:

$ mkdir rogue && cd rogue
rogue/ $ opam switch create '.' 'ocaml-variants.4.12.0+domains+effects'
rogue/ $ eval $(opam env)

Traditional roguelikes have some interesting characteristics that makes them "hard" to implement properly:

- They are neither real time nor turn by turn. On a first approximation, it looks like the characters play one after the other, which sounds pretty easy! But a closer look reveals that some actors are playing faster than others: What allow you to outrun the elephants is that you take less time to move than them, so you get to play more often. For gameplay purposes, each action has a duration in the game world.
- They also feature a lot of non-player characters, with different behaviors, interactions and "artificial intelligence". We need to make it trivially easy to specify new animals with distinct abilities. If it's even a little bit complex, the busy work is going to stop us from creating a rich universe.

We'll see how the new algebraic effects can help on both front, by capturing the essence of timed turns and letting us script our animal's brains in a very simple way.

But before we can do that, we have to become gods and create a world where our characters will evolve!... Just kidding, I'm going to keep things awfully simple here. Our world is just a big old matrix of cells:

type cell = Empty | Cactus | Camel | Snake | Elephant | Spider | Spider_egg

type world = cell array array

Each cell can contain exactly one thing:
- Either it's empty, and anyone can step there
- Or it's a cactus, which represents a spiky impenetrable wall
- Or it's an animal, the player character being represented by a `Camel` of course!
- Or it's a.. spider egg? Yuck, what are those for.

The `array`s are going to make it very easy to update the world. And the `world` is going to be a global:

let width, height = 50, 30

let world = Array.make_matrix width height Empty

let get (x, y) = try world.(x).(y) with _ -> Cactus
let set (x, y) v = world.(x).(y) <- v

I don't have much to say to redeem myself, but the `get` and `set` helper functions will make the rest of the code a tiny bit shorter. If we attempt to `get` a cell outside the boundaries of our world, an exception will be raised and we will pretend that only cactuses can exist out there. This creates an implicit barrier for the animals.

In the beginning, the world is fully `Empty`. Yet any proper roguelike needs procedural generation: We'll spawn a fixed number of entities at random positions on the map. The `Random.self_init ()` ensures that we get a fresh experience every time, but you can replace it with `Random.init 42` for deterministic level generation.

let () = Random.self_init ()

let random_position () = (Random.int width, Random.int height)

let () =
  for _ = 0 to 200 do set (random_position ()) Cactus   done ;
  for _ = 0 to 20  do set (random_position ()) Snake    done ;
  for _ = 0 to 10  do set (random_position ()) Elephant done ;
  for _ = 0 to 3   do set (random_position ()) Spider   done

let camel_initial_position = random_position ()
let () = set camel_initial_position Camel

In the end, there won't be exactly 200 cactuses, 20 snakes, etc, since the random positions can overwrite a previous entity. But there will be exactly one `Camel` since it's the very last update! We keep its position in `camel_initial_position` for later (but we won't really need it when we are done.)

Now that we have a random world, it would be nice to see it. We'll be using the excellent [`Notty` library](https://github.com/pqwy/notty) for drawing our game in the terminal. It provides declarative combinators for composing an image, freeing us from a lot of tedious work. You should first install it in the local switch:

$ opam install notty

We also need to tell the build system about it, so let's create a `dune` file with the `notty.unix` library enabled:

(executable
  (name rogue)
  (libraries notty.unix))

The actual drawing code is really short since Notty is doing all the hard work. For fun, each cell is rendered with a unicode character: you should know that your terminal may render emojis with 1 or 2 characters width depending on your font. For example on my computer, the spider is only as large as a single char so I added a trailing space to align everything properly with the bigger emojis. And if your terminal doesn't support pretty graphics, feel free to replace them with retro ascii art!

open Notty

let string_of_cell = function
  | Empty      -> "  "
  | Cactus     -> "\u{1F335}"
  | Camel      -> "\u{1F42A}"
  | Snake      -> "\u{1F40D}"
  | Elephant   -> "\u{1F418}"
  | Spider     -> "\u{1F577} "
  | Spider_egg -> "\u{1F95A}"

let draw_cell c = I.string A.empty (string_of_cell c)

let draw_world () =
  I.hcat
  @@ Array.to_list
  @@ Array.map
       (fun column -> I.vcat @@ Array.to_list @@ Array.map draw_cell column)
       world

The `I.string` converts our unicode text into a notty "image". We could customize the background and text color with attributes, but here we leave the default values with `A.empty`. To render the world matrix, Notty provide us with `I.hcat` and `I.vcat` for horizontal and vertical concatenation. We only have to do some conversions since they expect lists rather than arrays.

At this point we can already draw our little world!

open Notty_unix

let terminal = Term.create ()
let render () = Term.image terminal (draw_world ())
let () = render ()

The `terminal` is notty's abstraction to keep track of what has been drawn and to process keyboard events. If you run our program at this stage, the result is going to be disappointing:

$ dune exec ./rogue.exe

The program starts, renders, then quickly clears the screen and exits! We get to see nothing. To keep the game running, we'll allow the player to control the camel with the arrow keys:

let keyboard_direction () =
  match Term.event terminal with
  | `Key (`Escape,       _) -> exit 0   (* press <escape> to quit *)
  | `Key (`Arrow `Left,  _) -> (- 1, 0)
  | `Key (`Arrow `Right, _) -> (+ 1, 0)
  | `Key (`Arrow `Down,  _) -> (0, + 1)
  | `Key (`Arrow `Up,    _) -> (0, - 1)
  | _                       -> (0, 0)

The keyboard direction is added to the current position to determine where the camel ends up:

let ( ++ ) (x, y) (dx, dy) = (x + dx, y + dy)

let camel current_position =
  let new_position = current_position ++ keyboard_direction () in
  assert (get current_position = Camel) ;
  set current_position Empty ;
  set new_position     Camel ;
  new_position

What does it mean to move the camel? Here we simply free its previous position with `Empty`, then write that there is a `Camel` at the new location. You see, it's impossible to move "the" camel, as it doesn't exist. It's not the camel that moves Neo, only our perception of it.

One last step, we need a main loop: This repeats the render-move sequence of operations indefinitely so that we can keep playing. Each time the camel moves, we track its new position in a reference for the next time.

let () =
  let camel_position = ref camel_initial_position in
  while true do
    render () ;
    camel_position := camel !camel_position ;
  done

And now we can actually play! Well if you call that a game, it seems like our camel has the uncanny ability to eat everything that stands in its way, leaving an `Empty` trail behind it. When we update the world matrix, we never check if the desired new position is not already occupied... In fact, you can also end the game by stepping outside the map as even cactuses won't stop this hungry camel!

Let's make sure that our characters will respect the physical law of our world from now on by only being able to move onto empty cells:

let move old_position new_position =
  match get new_position with
  | Empty ->
      let character = get old_position in
      set old_position Empty ;
      set new_position character ;
      new_position
      
  | _ -> old_position

let camel current_position =
  let new_position = current_position ++ keyboard_direction () in
  move current_position new_position

The `move` function makes sure that when the `new_position` is unavailable, the animal will stay put. It's now moving the old cell rather than always putting a `Camel` at the new position, so that we can use it to move any other creature.

While the game works better with this fix, its world still feels dead. Every other animal is frozen in place. It's time to give them a will of their own! Let's think about what we might want them to do and what it will imply for our code:

- To implement the camel, we needed to keep track of its current position in the main loop. The other animals will also need to know where they are, so perhaps the `main_loop` should maintain a list of all the character's positions?
- Is the animal current location enough to determine what it should do next? Maybe not: When an elephant spots the player, I want it to charge in a straight line! Since this will happen over multiple turns, the elephant will need to remember what long term action it committed to. We could use a state machine / an automata: If you are in the `Charging` state, then try to continue the charge forward... but if you end up in a cactus, then go into a `Knocked_out` state for a bit, etc.
- The spider will be able to lay eggs, and if the player doesn't destroy them soon enough, they will hatch into more spiders! Is the egg part of the state of the spider? If the mama dies, the egg and its future babies should still be active.
- When an animal is badly hurt, perhaps it should run to a safe zone, heal, then remember to come back hunting the player at its last known position. State machines are nice, but perhaps we should look into [behavior trees](https://en.wikipedia.org/wiki/Behavior_tree_(artificial_intelligence,_robotics_and_control)), they seem better suited for sequencing complex behaviors?
- How will we share common tactics between different animals? It sounds a lot like we have to implement bits of our own programming language at this point.

I don't really have time to explore the "bad" solutions and show you how painful they are in practice. You will have to use your imagination and/or make your own mistakes! But if you try, I think you'll realize that all of our issues are in fact related to the main loop: We can only specify the behaviors in tiny steps, and must somehow "save and restore the internal state" of each character between each interaction. The situation would be a lot easier if we had only one character in our world, since it could then ignore the need for a main loop and just do its things sequentially.

In fact, we can accomplish exactly this by creating a system thread for each of the characters! By virtue of executing in its own process, the animal's brain is free to follow its logic and ignore the main loop:

- The main loop wouldn't need to store the animal's positions, since the internal states would be managed locally by each thread.
- The elephant's charge behavior would be a standard loop where we try to move the elephant forward, and the knockout after hitting a cactus could be a `Thread.delay 20.0` (such that this thread does nothing for 20s). We would never need to reify the automata into explicit states, as it would be implicit in the control flow.
- For the spider to lay eggs and birth new spiders, it would just spawn new independent threads.
- But we have to be very careful about race conditions... We don't want animals updating the world simultaneously and stepping on each other toes. That's very impolite.
- Also the non-playing characters should wait when it's time for the player to make its move.
- And actually `Thread.delay` is measured in real-world human time, not game-time. So that's not going to work.

Perhaps system threads don't exactly have the semantic we are looking for, but it would have been very convenient if they did. Alright alright, you know what I'm going to say and I'm still going to say it: Let's use algebraic effects! We'll create our own customs threads that have all the right properties to ease the definition of our animal's behaviors. And it's going to fit on a napkin. No state machine, no behavior trees, just standard OCaml code which is a lot more expressive anyway.

When it's their time to play, an animal thread will be able to update the world with the guarantee that it is the only one active at that time. Once it has finished its action, it will signal the end of its turn by performing an effect:

effect End_of_turn : unit

Just like in board games, the `End_of_turn` is a hint that this character has terminated its current turn and that the next animal in line can now play. When every other creature will have played, it will once again be the turn of the first character.

Note that the `End_of_turn` effect is known as *cooperative* multithreading: We won't be able to force a character thread to pause at arbitrary points, we will have to wait for it to tell us when it's done.

let queue : (unit -> unit) Queue.t = Queue.create ()

In order to schedule the animal's rounds, we'll use a `Queue`. This is a first-in first-out (FIFO) datastructure, much like a line of clients at the supermarket: New clients are added at the end of the queue, and get serviced last. Our `queue` is going to store functions of type `(unit -> unit)`. When we will call one of these functions, it will mean that we let the corresponding character play its next turn until it performs a new `End_of_turn`.

let player character =
  try character ()
  with effect End_of_turn k ->
    Queue.add (fun () -> continue k ()) queue

This introduces the syntax for "catching" and handling effects. It's similar to exceptions:
- If `character ()` terminates normally, then nothing more will happen. This entity will not play ever again, it's as good as dead.
- But if the function `character ()` performs an effect, we'll get a continuation `k`. This continuation `k` corresponds to the function suspending its execution at a `perform End_of_turn`.
- If we call `continue k ()`, then the execution of the character function will continue right back at its suspended `perform End_of_turn`, as if the effect never happened in the flow of its execution.

Another way to think of the continuation `k` is that it implicitly "saved" the internal state of the character at the point of the `perform`. It's a lot like this function hit the "pause" button on its execution, we can always press "play" again later to continue where we left off.

So this is the trick: we don't call the continuation immediately! Rather we schedule the continuation at the end of the queue with `Queue.add`. It will eventually be processed after all the other tasks of the queue have been done (= all the other animals made their move).

let run_queue () =
  while true do
    render () ;
    let suspended_character = Queue.pop queue in
    suspended_character () ;
  done

When things are on the queue, they don't magically get executed. We have to actively go `pop` the next task (which removes the first element from the queue), execute it, and repeat for the next ones. It looks like our queue will eventually become empty: In reality, the execution of `suspended_character ()` will generally perform a new `End_of_turn` which re-adds a new round to the queue.

There's a non-obvious step when we finally execute a `(fun () -> continue k ())` from the queue by calling `suspended_character ()`. This character behavior will continue and eventually perform a new `End_of_turn` effect. Shouldn't we be handling this new effect? Actually no, it will use the same handler that created the continuation `k` in the `player` effect handler: then the new continuation will also land at the end of our queue (and be eventually processed by further iterations of the `run_queue` loop)

I almost forgot to mention the sneaky call to `render ()` in the while loop: It's there to draw the game world to the terminal before every step and give feedback to the player. We'll get some nice animations as we'll see each animal make their move in turn.

Now that we have a custom thread scheduler, it's time to see how to use `perform End_of_turn` in our characters! Let's fix the `camel` player function to use the new effect:

let rec camel current_position : unit =
  let new_position = current_position ++ keyboard_direction () in
  let new_position = move current_position new_position in
  perform End_of_turn ;
  camel new_position

This is now a recursive function that never terminates. But right after moving, it suspends itself thanks to `perform End_of_turn`, giving an opportunity for others to do something at this point.

Now let's see some "artificial intelligence" for the non-player characters. I don't hold the reptilian brain of a snake in high esteem, so I just made them move randomly:

let all_directions = [ 1, 0 ; -1, 0 ; 0, 1 ; 0, -1 ]

let random_direction () =
  List.nth
    all_directions
    (Random.int @@ List.length all_directions)

let random_move old_pos =
  let new_pos = move old_pos (old_pos ++ random_direction ()) in
  perform End_of_turn ;
  new_pos

let snake initial_pos : unit =
  let pos = ref initial_pos in
  while true do
    pos := random_move !pos
  done

It's still interesting to see that we can perform the `End_of_turn` from within the factored `random_move`... and that we are free to implement the `snake` as an imperative loop if we so wish! The snake behavior is totally ignoring the main loop, it has created its own.

Let's look at a harder example. The elephant's charging behavior is implemented by:

let rec camel_in_sight pos direction =
  let next_pos = pos ++ direction in
  match get next_pos with
  | Camel -> true
  | Empty -> camel_in_sight next_pos direction
  | _ -> false

let camel_in_sight pos =
  List.find_opt (camel_in_sight pos) all_directions

let rec elephant pos : unit =
  match camel_in_sight pos with
  | None ->
      elephant (random_move pos)

  | Some direction ->

      let rec charge pos =
        let next_pos = pos ++ direction in
        match get next_pos with
        | Empty ->
            let next_pos = move pos next_pos in
            perform End_of_turn ;
            charge next_pos
            
        | Cactus ->
            for _ = 1 to 20 do
                perform End_of_turn (* knocked out! do nothing for 20 turns *)
            done ;
            pos
            
        | _ ->
            perform End_of_turn ;
            pos
      in
      
      let pos_after = charge pos in
      elephant pos_after

First there is a bit of logic to detect in which direction the elephant should charge to hit the camel. If none is found, then the elephant performs a random move. Otherwise, it enters the `charge` loop for the next few turns: It can not change direction until hitting something. If it ends on a cactus, the elephant gets stuck for 20 turns... and finally is allowed to chase the player again thanks to the recursion.

I like how self contained this code looks: If we ignore the `perform End_of_turn`, the code still makes sense to describe the path taken by the elephant to charge the player character. We don't need to think about the state machine of the elephant, it's implicit in the flow of the algorithm.

For the spider, we need a way to spawn new characters independent of their mother:

let spawn child = Queue.add (fun () -> player child) queue

This helper function adds a new function `(child : unit -> unit)` to the queue of characters. It's very important to call the `player` effect handler here, otherwise the `child` will not be able to perform its own `End_of_turn`.

let rec spider pos =
  try_to_lay_egg pos ;
  let new_pos = random_move pos in
  spider new_pos

and try_to_lay_egg pos =
  let egg_pos = pos ++ random_direction () in
  if get egg_pos = Empty && Random.int 100 = 0
  then begin
    set egg_pos Spider_egg ;
    spawn (fun () -> egg egg_pos)
  end

The spider has a 1% chance of laying an egg at an empty adjacent cell. It then tries to randomly move elsewhere.

and egg pos =
  for _ = 1 to 10 do
    perform End_of_turn ;
  done ;

  for dx = -1 to 1 do
    for dy = -1 to 1 do
      let child_pos = pos ++ (dx, dy) in
      if get child_pos = Empty
      then begin
        set child_pos Spider ;
        spawn (fun () -> spider child_pos)
      end
    done
  done

The egg is mutually recursive with the spider. It starts by doing nothing for 10 turns, and finally spawns new spiders all around it on the available empty cells. It then terminates (no recursion), meaning that it will not be re-added to the queue (= it will hatch only once).

The final step is to actually create the initial characters. We iterate on the initial world and `spawn` all the characters to populate the queue.

let () =
  world
  |> Array.iteri @@ fun x ->
     Array.iteri @@ fun y -> function
       | Camel    -> spawn (fun () -> camel    (x, y))
       | Spider   -> spawn (fun () -> spider   (x, y))
       | Elephant -> spawn (fun () -> elephant (x, y))
       | Snake    -> spawn (fun () -> snake    (x, y))
       | _ -> ()

let () = run_queue ()

The `run_queue ()` has replaced our main loop: it will iterate on each of the spawned characters present in the queue, then loop repeatedly while animals keep on performing their actions. When its the `camel` time to play, the system will wait for the player to press a key (with no other animal acting concurrently, just waiting patiently in the queue for their round).

And that's all folks, we made a roguelike!

But wait, what about life, attacking, healing, pathfinding, the winning and loosing conditions, ...? I'm afraid those don't have much to do with effects.

For example, in order for one character to affect the life of another by attacking or healing, it must somehow be able to access the life "state" of the other entity. The character threads we defined are all about managing the internal logic and the non-public state, but we haven't setup a way to communicate between entities. At the moment, the `world` itself is acting as a shared blackboard where animals can communicate by updating the cells. But the enum definition of `cell` is too limited and you will need to upgrade it if you want to go beyond.

It doesn't mean that we can't play tricks with control flow once we have added some communication channels! For example, if the animals expose a `life : int ref` in their corresponding cell (available for other animals to update on an attack), they could detect a hit right after performing their `End_of_turn`:

exception Dead
exception Hit

let end_of_turn life =
  let previous_life = !life in
  perform End_of_turn ;
  if !life <= 0 then raise Dead ;
  if !life < previous_life then raise Hit

By calling this function in place of `perform End_of_turn`, it would allow our animals to quickly react by escaping their current behavior to the nearest backup plan (defined by a `try ... with Hit -> ...` somewhere in the animal brain.)

Communication channels can be more elaborate: Rather than updating the `life` reference directly, external attacks could push events to an `event list ref` specific to each character. The events would be applied by the animal at the beginning of its turn, allowing it to ignore or interpret some events differently: The animal might be invulnerable for a few rounds, fire attacks might actually heal him, etc etc.

Finally, it's worth noting that our scheduler isn't actually specific to roguelikes: Real-time games with multiple entities can also benefit from these custom threads. They just have shorter rounds and don't wait for the player to move.

-------------------------------

Remember in the introduction when I promised that "some actions can take more time than others" for gameplay purposes? We already saw an example of this in the elephant knock out and the spider's egg waiting to hatch:

let sleep n =
  for _ = 1 to n do
    perform End_of_turn
  done

When a character thread calls `sleep 3`, it will do nothing for the next 3 rounds. This gives the others more opportunities to play in between. We can artificially slow down the movement speed of an animal by making it sleep in between!

Yet the implementation is not really satisfying: The scheduler will keep trying to let this sleeping animal play, only to have it perform an `End_of_turn` immediately. Can we skip those useless rounds? For a start, we'll need to tell the scheduler how long the character wants to sleep, so we replace the `End_of_turn` effect by a `Sleep duration`:

effect Sleep : int -> unit

We'll also need to upgrade the `Queue` datastructure as it is too simple to support the required operations. We don't have to look too far though, the next best thing is called a *priority* queue: Rather than adding only at the end, this datastructure can insert new elements at any point in the line. The priority queue will represent the timeline of future turns, indexed by the time where each character wants to play next.

As this one isn't available in the standard OCaml library, we shall `opam install bheap` and add `bheap` to the libraries of the `dune` build file. While the interface is similar to the previous `Queue`, we have to specify the time ordering before we use it:

type time = int (* or float *)

module Timeline = Binary_heap.Make (struct
  type t = time * (unit -> unit)
  let compare (t0, _) (t1, _) = Int.compare t0 t1
end)

let dummy = (0, fun () -> assert false)

let queue = Timeline.create ~dummy 32

The `bheap` implementation of priority queues requires a `dummy` element on creation, but you can safely ignore this as it'll never show up again (it's an internal detail). It also requires an initial size as a hint, but it'll quietly adjust if we ever put more than 32 elements in the queue.

We now have to keep track of the current in-game time to insert future turns at the right position in the priority queue:

let now = ref 0

let player character =
  try character ()
  with effect (Sleep duration) k ->
    let next_turn = !now + duration in
    Timeline.add queue (next_turn, (fun () -> continue k ()))

let spawn child = Timeline.add queue (!now, (fun () -> player child))

This isn't so different from the previous implementation. The `!now + duration` computes at which time this character should wake up: We insert its continuation at this point in the timeline.

The current `now` time will be updated as we pop the next task out of the queue:

let run_queue () =
  while true do
    render () ;
    let (time, suspended_character) = Timeline.pop_minimum queue in
    now := time ;
    suspended_character () ;
  done

And we are done, well that was easy!

But while the priority queue scheduler yields a smarter implementation of `sleep`, it also makes it harder for characters to react to external events. Before, the `End_of_turn` was giving them an opportunity to abort a long sleep if something urgent came up. Now when an animal gets hurt... it still has to wait the full duration of its last `Sleep` before being given control again.

In other words, "sleeping" animals won't really die until they have finished their nap! This is probably not what we want: How can we force them to wake up early? We have to call their continuation before the scheduler planned to:

- This requires their continuation to be accessible to the other actors, just like their `life` had to be public state in the `world`
- We also have to decide in the code which external events should wake up the other animals
- When we do call their continuation early, we must be careful to also cancel it from the scheduler's priority queue, as it will otherwise try to continue it a second time. This is both wrong from a game logic point of view, but also forbidden by the OCaml runtime. You can only `continue` a continuation once.

... With all that being said, I'll cowardly let you implement this new stuff by yourself! (I don't think the priority queue optimization is worth the trouble here in comparison with the queue!)