Forefont Projects

The first working version

The First Working Version!

Well, it has been a bit of a winding road, with a few detours but I got here in the end. I have now made a working (or at least mostly working) base version of my original project vision outlined in Birds of a Feather. In this post I am going to outline the work have done so far on the Murmuration repository, the journey getting something working, and the things I learned along the way.

The visualisation

It took me a bit of time to settle on a graphical visualisation framework that worked for me. I looked at both graphics libraries and game frameworks but the main thing I was looking for was the ability to draw 2D graphics to the screen easily and eventually port the simulation to the web using WASM and Canvas just by building the same source code with a different Cargo target.

During this exploration process I looked into a few different frameworks. The first deciding factor was whether or not the framework supported building to a WASM target right now. That one narrowed it down the options quite a bit. The other main factor was how easy it was to get started. This was harder to figure out and required actually trying out a few different libraries seeing what I could get to compile, if I could get shapes to show on the screen, and if I could get things to animate. There were a few cases where the framework documentation or examples were not complete enough for me to follow and there were some other cases where the code examples provided just wouldn't compile, presumably because they were outdated. And no shade to the maintainers for those frameworks, Rust is relatively new and these framework maintainers are building this stuff in their spare time. As I get more experienced in Rust I think things like documentation and working examples are a place I have the potential start contributing back to the community.

After trying a few different frameworks I found the one that worked best for getting me started was Quicksilver. It had working documentation and examples to help get me started and it supported deploying to the web! And with that find I was off drawing my first bird/circle and getting it to move across the screen.

scenario-two-birdsAfter getting one bird going two birds was the next logical test scenario. Yellow circles == birds. :)

Design considerations

The first goal was "just get it working" but past that I did have a few design considerations and goals I wanted to achieve. At the start of this project I was still very new to Rust (and still feel so) having had only built a handful of executables and no real applications. So, when I felt stuck because I wasn't doing it the "best way" on my first try I did my best to try talk myself out of that unrealistic expectation and just carry on with the goal of just getting it to work, even if that meant duplication, large files, functions, and methods.

Besides the project goals of wanting to simulate emergent swarm behaviour I also tried to consider how I wanted the code to be structured as I went. This was largely a push and pull between an Object Oriented style and Functional Programming style. I'm still not quite sure what suites Rust best yet but I seem to have mostly fallen back into a hybrid style. I don't know if this is language related or experience related (my Ruby and Javascript accent) but I think it is likely both. What I do know is that I do like the idea of a code structure that is a series of transforms on state and I did not quite get there across the simulation code.

One thing I did try to achieve, and I think somewhat successfully, was once I got the code running I tried to keep the simulation code and the framework code as separate as possible. If for some reason I feel like a different framework would suit better I wanted to be able to move from it as easily as possible. Also, I think this architectural separation will mean I can easily move from real time simulations to pre-calculated simulations if I wanted to try that. I also think this in part this choice comes out to my experience of working with Ruby on Rails web applications, knowing that as they grow keeping your app code separate from your framework code can be really helpful down the road. I think if I can eventually pull the simulation code out into a library I will have achieved what I want towards this end. So, right now I think it is going pretty well. It took a bit of refactoring after the fact to get there but I'm pleased with where it is right now.

Finally, I wanted to achive some form of visual debugging. Ever since I took robotics classes at the University of Manitoba I have remembered how useful visualisations of the internals of your system can be. So I tried to add that into my simulation as quickly as possible. And that coupled with some easily accessible test scenarios I did find helped quite a bit early on and thought the development process.

murmuration-in-debug-modeThis was the same two bird test scenario but with debugging mode turned on.

Guessing at performance

As mentioned in an earlier post one of the hopes I had with writing this simulation in Rust (and later compiling it to WASM) was that I could run lager simulations than one I originally wrote in JavaScript. Sadly, this has not yet been the case. Even when compiled to a release build (release builds run faster than development builds) the simulation tops out at about 2000 "birds". I suspect there are few reasons for this.

randomised-birdsThis is was the main test case which could be slow with too many birds. The test scenario is many birds starting off in random locations with random initial velocities.

randomised-birds-debug-modeThis is the same random location scenario but with debugging mode turned on. Initially useful but interesting to watch their velocities (green lines) start lining up as they flocked together.

For one thing I started wanting to write the code with a "bird centric" view. This meant for every frame rendered, for every single bird, the simulation has to figure out what is in that bird's "neighbourhood" and then figure out what it should do about it. I did this a bit for a certain kind of fidelity sake (birds don't know what is happening in the whole world just what is happening within the realm of their senses), rationalisation sake on my part (I'm currently more comfortable with a object or actor world), as well as for parallelisation sake (of being able to distribute these calculations easily with some kind of parallelisation/actor model in future). That said I might have to switch to a more world centric model where things like birds current position in the world and neighbourhoods are done in just one, or at least fewer, passes. Writing this now I feel like this is once again showing my conflicting design styles of object verses functional design styles.

Another reason the simulation is slower than my original JavaScript "Critters" one is because in this case I am now sticking to the the traditional "boid" calculations something I never achieved in the Critters swarm simulation. Because the Critters simulation never got much past the first pass I had just "eye balled" what the calculations should be based on my own guesses. This likely meant (I have not gone back to do an in depth review of my old code) I had fewer expensive loops when calculating the state of the world back then as I do now. I don't think I will revisit Critters in much depth at this point as I want to just continue on with this project but I wanted to note the likely difference. If I do ever try a rough comparison between a hand-rolled JavaScript implantation and a WASM implantation I'm more likely to port this Murmuration simulation to JavaScript instead.

Finally, another reason for the ~2000 birds limit is that I wrote as much of this simulation by myself as I could. One reason for that is to make sure I could keep targeting WASM (failed a bit here with one of the two crates I'm using at first but got back on track by specifying some crate features). The other and more important reason for me was a learning one. Writing as much as I could meant I understood as much of what was going on as possible, no libraries doing things I didn't quite understand yet. I know from experience (and this project!) that learning a language's conventions and syntax alongside a libraries or frameworks can often be s recipe for frustration and project blocking issues. So, with that I wrote my own Point and Vector structs and corresponding calculations, which I think likely do to my unfamiliarity with linear algebra maths, could have been written much more efficiently with matrix calculations or something like that. Likely soon I'll be looking at the nalgebra library to see how much more performant it's data types and provided calculations are.

Measuring Performance

As has been noted many times elsewhere that humans trying to guess why programs are slow is a bad idea likely to go wrong. Computers and compilers now do amazing things now to compute optimise our human centric code in ways we can't always predict. So using tools to measure is the best way to go. With that knowledge in mind I dug into how to generate and use flame graphs.

flame-graphOne of the flame graphs produced from the Murmuration simulation.

Being new to Rust, Quicksilver, and game programming I really didn't have much of a clear idea as to why the simulation might running slower than expected and since using flamegraph, well, I'm still not sure! But, one thing I do know is that this version of Murmuration spends most of its time calculating each bird's "neighbourhood" and the new vectors based on that for each bird, for very update cycle. I guess that isn't too surprising but it was good to confirm that it wasn't some obvious mistake I made performing slow draw times or something else like that I did wrong. It gives me a good place to start and hopefully have a high impact to optimise.

As a bit of a side note, before I dug into using flamegraph I was trying out Rayon as a quick way to add parallelisation to the simulation. In my case it didn't seem to add much of a speed up but it did make the flame graph I generated much harder to read. After I pulled Rayon out the flame graph was easier to read. I just wanted to note that for anyone else trying this out for the first time.

Potential improvement paths

So, there are a few places I can go from here to continue to improve Murmuration. I think to start I would like to try to improve the performance of the simulation before I start adding any more or different behaviours or before adding heterogeneous elements.

To start, now that I'm more comfortable with Rust as I mentioned I am going to see about using the nalgebra library and how and how that might speed up some of the calculations being performed.

Before moving to a completely wold centric architecture of the simulation I might have another go at parallelisation as well. This time more explicitly though using Actix a popular actor based library written in Rust.

Failing, or as well as, those two changes I will likely also try to optimise things with a couple "whole world" centric passes during each update, hopefully finding a way to reduce any repeated and expensive calculations. This might also tie in well to use of the nalgebra library if matrix calculations can be leveraged somehow. I have a sense it might be but as noted my maths in this area is just too limited to know right now.

What that's all tried out I do want to continue progressing to a simulation with multiple types of entities in the world. Having heterogeneous system of entities, each with their own set of rules, reacting to themselves and each other in different and hopefully interesting ways.

In good company

While writing this simulation and this article I found out that the Rust based Amethyst game engine is working on WASM support (with a grant from Mozilla) and is also, as it happens, working on a reference implementation of a heterogeneous multi-agent system called Evoli! It is nice to be in good company and perhaps someday when I've followed my own learning goals further along I can come back and compare notes and maybe even see if I can help contribute to the Evoli project.