My GSOC Journey #3: The Great Rework

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

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
The agents follow the same colour scheme. It’s a bit fast, but much prettier, don’t you think?

Devil’s Advocate

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.

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

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.

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store