My GSOC Journey #3: The Great Rework

It’s been a while, hasn’t it? I recently completed the last part of my GSOC proposal! Check out my previous blog posts here and here. The last part of my proposal was making the existing pathfinding functionality in Agents.jl more flexible, and extending it to ContinuousSpace. While a fairly straightforward idea, this was an undoubtedly long and complicated set of changes. Much more than I, and dare-I-say my mentors George and Tim, expected it to be.

The problem

The way pathfinding worked at the time involved passing a Pathfinder struct to the GridSpace constructor, which used it to create another struct, which was stored in the space. Not only did this tie an optional functionality to the space unnecessarily, it also necessitated an extra field and type parameter in the struct that wasn’t used most of the time. One of my goals of making pathfinding more flexible was to allow multiple “profiles”. What if you want to simulate both birds and rabbits? They don’t move around the same way, necessitating different pathfinding parameters: in other words, different profiles.

The solution

After a lot of deliberation and many ideas, we finally converged upon the best solution: The current implementation is too closely tied to the space, isn’t scalable or flexible. A complete, breaking, rework was required. The core code would remain largely the same, but the pathfinding struct (AStar) would be separate from the space. This also eliminated the need for the intermediary Pathfinder struct, since it only facilitated creating AStar inside GridSpace anyway. The user creates and stores AStar structs as they see fit, and pass them into any method that requires it. This has two major advantages:

• It directly leads to multiple profiles, since the user can choose which struct to pass into the pathfinding functions.
• It is scalable to other types of pathfinding algorithms and other spaces without polluting any of the core code, since all that is required is defining new methods and/or structs

While this would be breaking, which is definitely something to avoid where possible, the benefits outweigh the costs. Since pathfinding itself was also very new, it was highly unlikely this would annoy many users.

The key takeaway from all of this discussion was that I need to spend more time before adding new features. In addition to considering how to make new features easy to use, one should also consider scalability and flexibility of the implementation, and how it impacts the overall maintainability of the codebase.

Pretty pictures

The rework itself didn’t take much time, since all that was necessary was adding a more convenient AStar constructor and refactoring the pathfinding-related methods. To showcase the new capabilities, I made a modified predator-prey simulation involving 3 species of animals (rabbits, foxes, and hawks) on mountainous terrain. This needed two profiles, one for land animals and one for airborne ones. The initial implementation used a height-map on a 2D grid. Here’s a GIF of it running:

Rabbits are brown circles, Foxes are yellow squares, and Hawks are blue triangles

Over a video call, Tim, George and I decided this could be an excellent demonstration of a 3D model, which we didn’t have any examples of. For this, I also ended up implementing visualisation support for 3D models in InteractiveDynamics.jl, which contains visualization functions for several JuliaDynamics packages. It ended up looking like this:

The agents follow the same colour scheme. It’s a bit fast, but much prettier, don’t you think?

To ensure our new pathfinding API was everything we wanted it to be, it was decided that I would branch off the current pathfinding_rework branch to extend pathfinding to ContinuousSpace first. Once that was merged back into pathfinding_rework, we would be sure that the new API is robust.x

The idea for adding pathfinding to ContinuousSpace was simple enough: use the exact same code, and simply divide the space into a discrete grid. Having discrete properties distributed over a ContinuousSpace is something I’ve had to deal with in my models too. Since it would be used in pathfinding as well, I opened an issue about this.

Devil’s Advocate

A lot of features might sound nice, but in the end each one should have a robust reason to exist

George closed this through a PR, but before discussing the problem, he posed a simple question: Why do we need pathfinding in ContinuousSpace anyway? What does it accomplish that can’t happen in GridSpace?

This wasn’t something I was expecting. Why wouldn’t you want continuous pathfinding? In my mind, it was a logical extension of the existing functionality. Nevertheless, I had to come up with a strong reason and this forced me to question the underlying premise of my proposal. I concluded (with the agreement of both George and Tim) that it allows the concept of speed to exist, which is not possible in GridSpace. For example, foxes can move at 1.3 times the speed of rabbits.

George, by playing devil’s advocate, forced me to justify my proposed changes. This is something I definitely plan to do for myself from now on. A lot of features might sound nice, but in the end each one should have a robust reason to exist, or else end up bloating the library unnecessarily.

Continuous complexities

Although adding pathfinding to ContinuousSpace was fairly easy, there were a lot of small intricacies and edge cases to be addressed. For starters, there would need to be repeated conversion between coordinates in ContinuousSpace, and indexes of the underlying grid on which A* is run. I decided to store the final path in the coordinates of the space, since it would only need to be computed once and would simplify other functions.

Moving along a path in GridSpace is straightforward: just move to each successive grid index in each successive iteration. ContinuousSpace, however, has to interpolate between each point on the path. This requires accounting for floating-point error, fast-moving agents overshooting the target, and some vector math. Additionally, the space can be periodic, so going off one side of the space wraps around to the opposite side. This implies that the vector from point A to point B isn’t just B-A but instead this absurdity (in Julia code):

best = to .- from
for offset in Iterators.product([-1:1 for _ in 1:D]...)
    dir = to .+ offset .* size(space) .- from
    if sum(dir .^ 2) < sum(best .^ 2)
        best = dir
    end
end

As usual, tests came to the rescue here. After implementing (what I thought were) working continuous pathfinding methods, I added tests for them. Needless to say, it took several iterations of finding and eradicating edge cases to finally get it right.

Agents.jl has the pre-existing functions random_position (to get a random position in a discrete space) and nearby_positions (to iterate over valid positions surrounding an agent). Since pathfinding has a concept of whether or not a position can be walked on, we decided to add versions of these methods that take such conditions into account. Consequently, random_walkable and nearby_walkable were added. The former returns a random walkable position (in both GridSpace and ContinuousSpace) and the latter returns an iterator over walkable positions surrounding an agent (in GridSpace only).

Note how in GridSpace, an agent can be instructed to move to a nearby position using nearby_walkable. However, this isn’t really possible with ContinuousSpace. To combat this, I also added a method for random_walkable that returns a random walkable position within a given radius of a given position. Since ContinuousSpace has theoretically infinite positions, implementing nearby_walkable for it isn’t possible and doesn’t make sense anyway.

Prettier pictures

With this implemented and merged, we decided to shift the example I made to ContinuousSpace. Besides showing off the new features, it also made sense to be able to give different animals different speeds.

All animals are spheres now, which is anecdotally appropriate

In conclusion

This completes all of the changes in my proposal. Since I still have two weeks left before evaluations, we decided I should work on some other smaller issues, such as adding compression to my checkpointing system and improving the performance of the A* implementation.

Google Summer of Code turned out to be an amazing experience. I learned a lot from it, and met many incredible people in the Julia and Open Source communities from all over the world. Agents.jl is more than a GSOC project for me, though. I use it often for my own models, and definitely will continue to contribute to it in the future.

Stay tuned!

I have another post coming up summarising all my work, as well about the GSOC journey beyond the code, including the incredible people I met and worked with.