A Magical Girl Simulation in Clojure (Yes, there was a point to doing this)

Recently I wrote a couple of Code Review.SE answers for games in Clojure. All the code I looked at was written essentially like C: data was stored in global variables or in “god” maps that were passed into every function. Entities were all modeled with plain maps or vectors. None of the code was bad per se, but everyone seemed to be ignoring Clojure’s object-oriented features, records, protocols, and multimethods, even though games and simulations are exactly where object-oriented programming really shines.

Since I didn’t have any real experience writing something like this in Clojure, I decided to write a very silly project: a simulation of a certain anime about magical girls and witches. I would try out the techniques I’d been recommending to other people, and find out if they really worked better than the bare-bones approach with global variables and built-in data structures.

The entities: exercising Clojure’s object-oriented features

I first put some thought into how I wanted to represent the entities: the magical girls, witches, familiars, and Incubators. (The familiars aren’t used in the final code, but they could be incorporated somewhere.) I knew I wanted to use the object-oriented features to do this, but Clojure gives you a ton of choices in how you organize that.

Which object-oriented feature?

Clojure has three major features which support object-oriented programming: records, protocols, and multimethods. Records and protocols together are closer to traditional classes like we have in Java and Python. A record is rather like a C struct: you can declare record types with the defrecord macro, and give a list of fields which are available on that record type. This causes a constructor function to be defined. The fields of a record are accessed just like a regular Clojure map; you can use get, or the names of the fields as keywords define functions which take the record as argument and return the value of the field. Unlike C structs, you can add fields to a record using Clojure’s assoc, just like you can with maps.

However, fields defined in the record actually become instance fields of a Java class which represents the record in the generated bytecode. The JVM is optimized around Java classes, so accessing instance fields is very fast. So records are sort of a performance enhancement.

Records are data holders. Since Clojure has first-class functions, you could theoretically have the data a record holds be functions, and then it would sort of feel like a class. But protocols and multimethods are better ways to get behavior on records; they permit polymorphism and limited types of inheritance.

Protocols are somewhat like Java interfaces. They’re lists of function names and signatures, defined with the defprotocol macro. When you define a record type, you can also have it adhere to a protocol, which is like implementing an interface: you give the bodies of the functions, which all take the record as the first argument. Different record types can adhere to the protocol in different ways, which gives you polymorphism in the same way interfaces do.

Multimethods are apparently a concept which originated in Common Lisp’s CLOS, although I have no familiarity with CLOS. They’re a little tricky to understand, but incredibly powerful.

In an object-oriented language like Java, you can have multiple classes implement the same method. When you call the method on some object, the runtime decides which version of the method to call based on the class of the calling object. Say we have a Goth class and a Beatnik class, which both inherit from Counterculturalist and both implement the method writePoetry from IPoetic. Given an object Counterculturalist c, we execute c.writePoetry(). Then, if c is an instance of Goth, we’ll get back something like “The world…is dark. Dark…like the depths…of my soul…”. If c is an instance of Beatnik, we’ll get back something like “Scabbidy dabbidy doo, blabbidy scabbidy doo”, accompanied by bongos.

Now, suppose we wanted to refine our criteria for choosing which version of writePoetry to execute. For example, suppose we wanted to distinguish GothFamiliarWithTheWorksOfWilliamWordsworth from GothUnfamiliarWithTheWorksOfWilliamWordsworth. In Java, we’d have to make two more classes, have each inherit from Goth, and have them override the writePoetry method again. That’s a lot of classes, and a lot of repeated code. Especially when we also need to distinguish GothWhoOnlyReadOnePoemByWilliamWordsworthAndHatedIt.

Wouldn’t it be nice if we could just add a field to the Goth class, familiarityWithTheWorksOfWilliamWordsworth, which would rate the familiarity on a scale of 0 to 100? Then have the writePoetry methods get progressively more Wordsworth-like as the familiarity rises?

Yeah, multimethods can do that. No ifs, &&s, or switches about it.

Specifically, multimethods can use whatever criteria you want to decide which version of a method to call, provided you can write a function to test those criteria. You call the multimethod with whatever data you want, and it uses the function you defined to decide which method to dispatch to. You can dispatch on multiple fields of a record or map. You can dispatch on functions of multiple arguments. You can get as crazy as you want. You can have a multimethod which decides how to dispatch based on whether the first argument is a map whose keys all start with s or not, and the second argument is a vector of vectors of maps whose values all implement java.lang.List.

Multimethods are much more powerful than protocols. They become even more powerful when you throw in the derive and isa? functions. I won’t go over those here, but you can read about them elsewhere. The Joy of Clojure covers them very thoroughly. With multimethods, derive, and isa?, you can basically implement your own form of object-oriented programming. You can combine records and multimethods and get some amazingly powerful designs.

With great power comes overly complex programs

I decided that I didn’t need so much power for this program. I went with protocols.

I made a record type for each of my entities, defined to hold the base-level fields. Fields which were less essential or prone to change were added later with assoc.

I made a Combatant protocol with various functions that define behaviors and properties of the entities: can-flee, blacken-soul-gem, increase-combat, won-battle, and fled-battle. Most of them only do anything interesting when called on a magical girl, but I implemented them for witches and familiars so that I could map them over a vector of entities of mixed types. Witches and familiars just get returned unchanged from their versions of the Combatant functions. This simplified my code for combat later on.

You can see that this is very similar to what you can do with an interface in Java. I could have written Java classes for each of my entities and had them implement an ICombatant interface. That’s why I didn’t need the power of multimethods.

Top-level architecture

Drawing Inspiration from Rich Hickey’s Ants Demo

I first planned my magical girl simulation as a discrete-time simulation; it would have turns or phases during which the entities would take actions, then stop to let the code update state. But ever since I read Seven Concurrency Models in Seven Weeks, I’ve been wanting to try out some concurrent programs, and this seemed like a good chance, so I decided to make the program a continuous-time simulation. But I had a hard time coming up with an architecture, until I remembered reading about Rich Hickey’s ant simulation. This is a demo Rich Hickey wrote early on in Clojure’s life to show how Clojure’s approach to concurrency works. Someone very helpfully made a literate programming version, so everything is thoroughly explained in text alongside the code.

If you don’t want to read the code, I’ll summarize. The ants move around on an 80 by 80 grid looking for food. As they explore, they leave pheromone trails for other ants to follow. When they find food, they bring a piece of it back to the nest. Other ants will reach the same source of food by following the pheromone trails. However, the trails decay and become weaker over time.

The ants are represented two ways: an ant struct (a record in modern Clojure) that tells us which direction the ant is heading, and how much food it’s carrying, if any; and a vector of ant agents. The world grid is a vector of vectors of refs to cell structs, which store how much food is on a square, how strong the pheromone mark on a square is, whether the square is part of the ants’ home, and the struct for any ant which is currently on the square. Making them refs lets the program update them concurrently, for example by moving an ant from one square to another, without worrying about another thread trying to access the same square before it’s done.

The ants’ behavior is implemented as the function behave. When the program starts, we send-off the behave function to all the ant agents. The ant agents only store the ants’ current locations, but with that information, we can look up the ant struct stored in the world grid and make any modifications we want. The behave function will make the ants move, pick up food, bring food home, and leave pheromone trails. It runs in an infinite loop by adding another invocation of itself to the ant agent’s work queue every time it’s called. Since each ant is an agent, and agents are concurrent, uncoordinated, and asynchronous, each ant behaves as an independent entity, in real time.

How does this work with magical girls?

My magical girl simulation is very similar to Rich Hickey’s ant simulation. Instead of ants, I have magical girls, and instead of food, I have witches. The magical girls search for the witches just like the ants search for food. Unlike the ants, the magical girls can sort of tell where the witches are because their soul gems will react to the presence of a witch; by contrast, the ants search for food at random, using the pheromones as a guide.

In the final version of my program, I used a continous world; instead of having discrete squares like a chess board, I used floating point numbers to approximate a realistic world. Each witch and magical girl has a detection radius. If the circles defined by the witch’s and magical girl’s detection radii overlap, the magical girl detects the witch and can choose to fight her. In a continuous world, you can’t wait for two entities to be on the same space before they can interact; there are just too many spaces.

What about core.async?

Seven Concurrency Models in Seven Weeks covers core.async, a new Clojure library whose premise is stolen from Go. (Rich Hickey himself says so, unabashedly.) I wanted to try out core.async too.

The ant demo code is pretty old as Clojure code goes. No one uses structs or the sync macro anymore, and there are easier ways to build a UI in Clojure than calling to AWT through Java interop. I wondered whether a modern version of the ant demo could use core.async to clean some things up.

I soon realized that there was no place for core.async in the ants demo, at least so far as I could see. Go, and core.async by merit of having stolen its premise from Go, implement CSP, a paradigm for concurrency invented by computer scientist Tony Hoare in the 1970s. CSP and actors (as seen in Erlang, Scala, and the Akka framework) are both models of concurrency based on message passing. They’re sort of like two sides of the same coin. Actors are a special kind of process which the system runs concurrently, set up with a mailbox and a PID so they can receive messages from other actors. Just how actors send and receive messages is transparent to the programmer. It’s an implementation detail. When an actor sends a message, it could be appending to a queue in the machine’s memory, or serializing the message and sending it to another machine in the same cluster, or it could be encoding the message as JSON and sending it to a web service running on a server on the other side of the planet. From the programmer’s perspective, these all look the same.

In CSP, there’s nothing special about the process. Processes in a CSP-based architecture can be threads, or actual OS processes, or they can just be separate functions operating in the same thread at different times. Where actors use a special abstraction for the process, CSP uses a special abstraction for how messages get passed: the channel. Any process which has a reference to a channel can write to that channel, and any other process can read from that channel, at any time. CSP still lets you run things across multiple machines, but the implementation of the channel will change.

As I was thinking about how to apply core.async to the ant program, I remembered that, hey, core.async is CSP, and CSP stands for communicating sequential processes. As soon as I thought that, I realized that core.async wasn’t really applicable to the ant demo. At first I thought this was because the ants don’t communicate with each other. But they do—through the pheromones. Modeling the pheromone trails with channels seemed pointless and overly complex. It’s just not a good fit. The way Rich Hickey modeled ant pheromone trails is a good way to model how ants communicate.

By the way, even though CSP and actors are closely related, there’s something in Clojure which behaves much more like an actor when it comes to entity modeling: agents. The ants are independent entities acting asynchronously. Agents are perfect to model that.

That means core.async would be an even worse fit for my simulation, because magical girls and witches don’t communicate with each other at all. They’re completely independent. But agents are still useful, because my magical girls are going to be independent entities acting asynchronously, just like the ants.

Agents of F.A.I.L.

Since I was heading into uncharted waters here, I did what I often do when I need to explore whether something works: I brutally stripped down the features to the bare essentials and implemented a prototype. In this case, I used Quil to make a display of pink and black dots. The pink dots represented magical girls, and the black dots were witches. I coded up something very similar to the ant demo. I used agents to represent the magical girls. Rather than use a discrete grid like the ants demo, I used a continuous world with floating point coordinates. I stored the witches in a vector and had each one hold onto its coordinates.

This worked pretty well as long as I only had about five or six magical girls. Above that, it pretty much broke down. Unlike actors in Erlang and Akka, Clojure agents aren’t designed so that you can have hundreds or thousands of them going at once. Brian Carper ran into similar problems when he wrote a game and tried to make every entity its own agent. I knew this problem was only going to get worse when I added the rest of the features. The prototype didn’t even have the magical girls searching for witches or engaging in battles; they just milled around at random, ignoring the witches. And the performance was still too lousy to allow more than five or six magical girls at a time.

I threw away that prototype and rewrote it to work like most real-time games do: some code runs every frame to update the state of the world. It’s still kind of turn-based, but it looks more or less real-time when it’s running. It was disappointing, but I learned a lot from looking at Rich Hickey’s ants code (including how to do literate programming in Emacs Org Mode), so I’m glad I gave it a try.

The rest of it

The rest of the code was pretty standard Clojure stuff, but it was fun and interesting to put my functional thinking powers to the test. Object-oriented and imperative programming fit games and simulations so well that it’s tempting to overuse Clojure’s imperative escape hatches. One CR.SE user whose code I looked at had done just that, using atoms as mutable variables and updating them in an imperative style. This user felt the design had gone wrong somewhere. I pointed out James Hague’s excellent Purely Functional Retrogames article as a good source of advice.

Now I had to follow that advice myself, and I thanked the Rich Hickey for destructuring, because this code would have been a nightmare without it.

The basic idea behind my design was to have my entities and other important state stored in a bundle of world state which would be passed around. Each frame, the top-level code would pass the state bundle through a pipeline of state update functions which would return “diff maps”—maps which contained the changes that needed to be reflected to the world state. The diff maps could be combined with the world state using Clojure’s merge and merge-with functions. This design was based on James Hague’s article.

Hague suggested that the code for state-updating functions is easier to read if you have the functions take separate arguments, instead of just passing in the whole state bundle, and unpack the values from the bundle at the call site. I didn’t do this. Thanks to destructuring, though, the state bundle gets unpacked in the function’s argument list, so it’s still informative to glance at the argument list to see what data the function uses, and I could name the arguments without having to do a let inside every function.

The final version of this code feels very clean and nice and purely functional, but it also feels fragile and somewhat restrictive. Although the functions themselves are nicely separated, and I can insert new stages in the pipeline if I want, I don’t feel like I can do anything that isn’t easily expressed by functions in a pipeline that return results.

I almost got myself in trouble with this. I organized the display code in Quil around the idea of turns / frames, with a certain number of frames per day. At the end of a day, the magical girls all get sent back to their home squares. This simulates magical girls returning home at night to sleep and spend time with their families.

I needed to begin a turn with a function that would move the magical girls to a new position, except when the day was over. When the day was over, they needed to go home. This would be easy to write in an imperative style: just something like

if turns % turns_per_day == 0:
    move_home(magical_girls)
else:
    move(magical_girls)

in pseudo-Python. I couldn’t do that here though; I had to somehow cause the move function to send the magical girls back to their home squares, and return the newly resting magical girls as part of a diff map to send into the next stage of the pipeline.

When I was writing the move function, I made it so a move on a magical girl with no defined position would place her at home. I did it so the function would be more robust and not crash if I forgot to set a position on some magical girl, but it turned out to be useful here. I mapped over the magical girls, using dissoc to remove their positions. Subsequently, when move was called, they would be moved home.

I ended up implementing this with the following code:

(defn before-combat
  "Creates new magical girls and moves the magical girls for this
  turn. Returns a diff map of changes. Meant to be called in pipeline
  with events/round-of-combat and events/spawn-witches."
  [{:keys [magical-girls witches incubators
           turns turns-per-day world-size] :as bundle}]
  {:magical-girls ((comp
                    (partial map #(events/move % (:within-world? bundle)))

                    (if (zero? (mod turns turns-per-day))
                      (partial map #(dissoc % :position))
                      identity)

                    (partial
                     concat (events/spawn-magical-girls
                             incubators
                             world-size)))

                   magical-girls)
   :witches witches})

That feels very complicated to me. There’s a lot of nesting and strange point-free-type stuff going on here. But I needed the function to return a diff map, because that’s what the next stage of the pipeline was expecting as input. I suppose I could have defined a name for the function I made with comp, but it’s only used once, and it’s so specific and in such violation of the single-responsibility principle that I don’t even know what I’d call it. So maybe it’s actually less confusing with a giant comp written out here, than it would be if I added some pointlessly specific function that’s only used once?

Overall, though, I was pretty satisfied with how the code turned out. For the most part, it felt like a confirmation that functional programming can be much easier and more elegant than imperative programming. I had a lot of fun writing it, too.

Tests

I wrote unit tests for almost everything in this project. This was where the advantages of functional programming became extremely obvious.

For one thing, since all my data was immutable, I didn’t need fixtures to refresh the state of my sample data. I could just make some top-level definitions and keep on reusing them.

Since I wrote all my functions without side effects, I could test practically everything in isolation, without having to build up a lot of infrastructure around it.

Early on, I realized that I couldn’t test things that used random numbers if I was getting my random numbers from Clojure’s rand and rand-int functions. Instead, I made an instance of java.util.Random inside my namespace. It was dynamic, so I could rebind it with binding to another instance with a known seed, and get deterministic tests.

Writing the tests for this project was a joy. I had almost no major bugs and never really felt the desire for a stepping debugger, all thanks to the tests. The only time I wished for a more powerful debugging tool, I found myself wishing for Typed Clojure. I got around this using Clojure’s precondition and postcondition facilities.

Incanter

Incanter is a pretty cool library. I used it for some of the stochastic and random number stuff in this project. It’s very easy to use and there’s a lot to it.

That said, I feel like Clojure lags behind Python in statistical and scientific computing. Incanter is easier to use than Numpy/SciPy/Matplotlib, but it’s missing quite a few things that the Python scientific stack has. I still had fun with it, though. I graphed a few circles to help me design one of the tests. It only took about four lines of code, and I had a nice-looking plot of four circles with a legend.

Quil

I love Quil. I looked at Processing a few times, but I was a little wary of learning a whole new language just for playing around with some graphics. Quil is great, in that it’s even easier to play around with graphics using Quil than using Processing, and I can do it from a language I already know, Clojure.

I took computer graphics at university and hated it. We did all raw OpenGL calls from C++, except on our last assignment, when everyone cheated and used game engines and 3D modeling programs to create nice things which they read in and rendered on screen with raw OpenGL calls. Except me, because I didn’t know about any of those programs because I wasn’t a PC gamer. I worked with a partner who did, so she created most of our assignment, but then it didn’t work and we couldn’t figure out why because the code was so disorganized. The construction of OpenGL actively fights any attempt to organize your code with object-orientation, so C++ was mostly just C with STL vectors. Which I guess is still better than C. But still disorganized.

The main thing I hated about computer graphics at university was the utter lack of fun. Graphics are supposed to be fun. You’re making cool things appear on screen. Nothing is less fun than OpenGL. OpenGL is so low-level it felt like writing assembly again at times. I stupidly made things hard on myself by using vertex buffer objects and shaders instead of just using the fixed function pipeline like everyone else, but even later when I tried the fixed function pipeline, there was just too much garbage to deal with. I understand that OpenGL is written that way for performance reasons so the guys making those fancy video games that us old timers who played the original Megaman X on the Super Nintendo don’t even know the names of can make them perform. But that’s not what I’m doing.

That’s why I love Quil. It makes graphics simple and fun. It removes a whole layer of pointless crap you don’t want to have to deal with when you’re just exploring and having fun. Sure, it doesn’t perform that great. Who cares. If I really need blazing fast performance, then I’ll move to C++ and OpenGL.

Conclusion

This was an interesting project, and I was able to exercise a lot of the things I’ve learned about Clojure and functional programming in the past few years.

Unfortunately, like many of my projects, it’s not really done. It reached a point where I’d pretty much learned what I wanted to know, and then I gave up on it.

As it is, you can start it up and see magical girls and witches moving around on screen, but there are a couple ways it fails to fulfill my original vision:

  • Magical girls don’t stop after killing one witch. They keep going. In the show, magical girls were never in the mood to go hunt down another witch after they’d managed to kill one. They do stop at the end of a day and go home, but I feel the witch attrition rate is much higher than it should be thanks to this.

    I did come up with a way to fix this: after a magical girl defeats a witch, unset her position so that she gets sent home on the next turn, and also set a waiting property. Have the move function ignore any magical girl who has the waiting property set. Unset waiting at the beginning of a day. I haven’t gotten around to implementing this, though.

  • The magical girls don’t really seek out the witches. They move around at random, stumbling on witches. The witches’ discovery radii are pretty large, so the girls don’t really have trouble finding witches to fight, though.
  • There were a lot of features I had planned that I never implemented. I was going to have familiars as extra impediments to the magical girls. I even wrote the familiar record and protocol code, but it’s not used anywhere in the program. I was going to have a giant fancy system of gradated discovery radii with different probabilities for discovering a witch.
  • There are probably still scalability problems. I used the equivalent of a nested loop to find pairs of witches and magical girls which were within each others’ ranges. I looked into quadtrees, but they seemed quite complicated.
  • It would be nice if there were more monitoring mechanisms, so you could check out how your magical girls are growing, and get stats like the conversion rate into witches and whether new magical girls are getting totally squeezed out by older, more powerful ones (like what happens in the programming world on a job search).
  • I may come back later and implement some of these things. Or not. After all, it’s not like simulations of magical girls in Clojure is going to get me a job.

    Advertisements