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 solution

  • 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

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

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

All animals are spheres now, which is anecdotally appropriate

In conclusion

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!