The first working version2019-05-31
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.
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.
After getting one bird going two birds was the next logical test scenario. Yellow circles == birds. :)
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.
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.
This was the same two bird test scenario but with debugging mode turned on.
Guessing at performance
This 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.
This 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.
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.
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.
One 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.