Solving my Simulator's Biggest Problem

[00:00:00]Overall, I am quite satisfied with the current state of my ant simulator.

[00:00:05]It runs smoothly and allows to observe some interesting group behaviors.

[00:00:10]>> [music] >> Performance is good and the animations are mostly fine. However, there is one aspect that bothers me a lot >> [music] >> and for which I had no solution until today.

[00:00:22]The collisions between ants are a major [music] improvement over the previous version, but it brought its fair share of problems.

[00:00:30]The biggest issue is that the ants constantly bump into each other as if they were completely blind and stubborn.

[00:00:37]This problem seriously degrades the quality of the simulation as it affects [music] the very core of how the ants interact.

[00:00:45]In this video, I will present the approach I used to solve this tricky issue.

[00:00:52]Just as ants leave markers to guide others to points of interest, we leave a trail of personal data behind us on the web.

[00:00:59]This information can then be harvested by malicious actors for a wide range of harmful activities from simple scams to identity [music] theft. Unfortunately, massive data breaches are becoming increasingly [music] common. And if your information is exposed in one of them, the consequences can be truly devastating.

[00:01:20]Incogni, the sponsor of this video, helps prevent these incidents by automatically erasing these digital footprints [music] for you. To do this, it continuously scans trackers for your information and then requests its removal.

[00:01:35]Their custom removal feature even allows you to request the deletion of your data from specific websites, ensuring you maintain full control over your online presence.

[00:01:47]You can track all of this in real time directly from the dashboard >> [music] >> and the numbers are honestly quite impressive.

[00:01:54]A huge thanks to Incogni for sponsoring this video.

[00:01:57]>> [music] >> Use my code or click the link in the description to get 60% off an Incogni subscription.

[00:02:04]Ideally, we need a solution that enables the ants to look ahead and adjust their paths based on obstacles.

[00:02:12]There are numerous methods for this kind of problem, >> [music] >> which aim to simulate the behavior of agents moving in groups using avoidance strategies. [music] While these approaches tackle the issue from very different angles, one in particular caught my attention.

[00:02:28]>> [music] >> PBMAD which stands for position-based multi-agent dynamics.

[00:02:34]What makes this algorithm especially relevant to this [music] project is that it operates at the exact same level as the physics solver I use for collisions.

[00:02:44]Both systems are working in the same position-based framework, making the integration very natural.

[00:02:51]Let's explore how this algorithm works.

[00:02:53]Despite its intimidating name, the underlying mechanism is actually [music] quite simple.

[00:02:59]And fortunately, the paper describing the procedure is very well written.

[00:03:04]Let's consider two agents with [music] their respective velocities.

[00:03:08]Using this function, we can determine if and when they [music] will collide.

[00:03:13]Once the point of collision is found, we look at their positions just before >> [music] >> and just after impact.

[00:03:21]We then adjust [music] the post-collision positions to fix the overlap just as we would for a standard non-penetration constraint.

[00:03:29]Next, we calculate the displacement necessary to avoid the collision entirely.

[00:03:36]By subtracting these two values, we obtain the relative displacement needed [music] to prevent contact.

[00:03:42]If we project this displacement onto the collision axis, we isolate [music] the specific component of movement that brings the agents together.

[00:03:52]We can then offset the agents' [music] positions with this correction to cancel the collision before it happens. The correction is scaled based on how imminent the collision is.

[00:04:02]Let's see how this plays out with two groups facing each other.

[00:04:09]As we can see, this isn't quite the expected result.

[00:04:13]The issue is that [music] the applied correction reduces the approach speed, which causes the agents to slow down drastically when facing each other in this scenario. What we actually want >> [music] >> is for the ants to actively avoid one another instead of simply braking.

[00:04:29]To achieve this, rather than projecting the displacement onto the collision axis, >> [music] >> we will retain the tangential component.

[00:04:37]This adjustment should encourage the agents to favor trajectories >> [music] >> that allow them to smoothly brush past each other rather than just decelerating. Let's see the result with this approach.

[00:05:00]This is much better.

[00:05:01]The ants now try to avoid one another while maintaining their speed as much [music] as possible.

[00:05:07]Let's see what happens in a slightly more complex situation where the two [music] groups intersect at a 90° angle.

[00:05:17]In this scenario, too, the ants manage to avoid each other quite effectively, albeit a bit more chaotically. Out of curiosity, let's compare this with the correction applied along the normal axis.

[00:05:40]We can also compare it to having the avoidance system completely disabled.

[00:05:43][music] >> I find this result very satisfying.

[00:06:00]As always, it isn't perfect, but things rarely are in nature anyway.

[00:06:06]>> [music] >> Before activating the system in the actual simulation, let's run a quick performance test.

[00:06:15]I will then instantiate 20,000 ants instead of 200, >> [music] >> which is fairly representative of a heavy simulation load.

[00:06:27]To say the least, the performance isn't great.

[00:06:31]The reason for this is that whenever I implement a new feature, I always start by writing a naive, yet reliable version.

[00:06:40]Currently, identifying agents that might collide is done through a brute-force approach, meaning every single agent checks >> [music] >> against all the others.

[00:06:49]It works, but it is incredibly slow.

[00:06:52]Fortunately, the physics solver has already generated a spatial grid containing the positions of all objects, which we can now leverage [music] to efficiently find the colliders. To detect potential collisions within a given time horizon, we might assume it is enough to search for agents within a radius equal to the agent's speed multiplied by the maximum time.

[00:07:15]However, if another agent is moving toward it at that same speed, >> [music] >> it wouldn't be detected, even though it could still cause an impact.

[00:07:25]Therefore, >> [music] >> we must double the search radius to account for the relative speeds.

[00:07:31]We can then restrict our search to the grid cells that intersect the time horizon's radius.

[00:07:43]Using the spatial grid >> [music] >> already yields significant improvements.

[00:07:48]The avoidance system's execution time drops from over 300 milliseconds to around 100.

[00:07:55]The simulation is now usable, running at a much better frame rate.

[00:08:00]However, we can improve performance even further by considering that the agents cannot see behind them.

[00:08:07]This allows us to process only the cells within their field of view, saving a few extra milliseconds.

[00:08:15]The relationship between the ants' perception time horizon >> [music] >> and the number of cells to check is quadratic. Therefore, an extremely simple way to save time is to reduce this radius.

[00:08:28]Until now, I had been using a maximum [music] time to collision of 5 seconds, but it turns out that 2.5 seconds is more than enough for this simulation.

[00:08:38][music] This small adjustment has a massive impact, cutting the system's execution [music] time in half, down to just 45 milliseconds. While this does affect the ants' behavior by causing them to form smaller groups, [music] it does not affect the avoidance mechanism capabilities.

[00:08:57]A key aspect of this avoidance mechanism [music] is that it deals with future interactions, potentially 100 ticks away.

[00:09:05]Because of this, it is not strictly necessary for every agent to re-evaluate its future collisions on every single frame. We can easily reduce [music] the computational load by updating only half of the agents on any given tick.

[00:09:20]This instantly divides the execution time >> [music] >> by two, while maintaining good simulation quality. To compensate for the lower update rate, [music] the avoidance corrections are scaled by a factor of two.

[00:09:32]This brings us down to 24 milliseconds, >> [music] >> which is not bad, but still too high for a simulation aiming for 60 frames per second.

[00:09:42]The main bottleneck remains the search for potential collisions, [music] which requires iterating over a massive number of cells.

[00:09:50]Fortunately, [music] this search step has one specific characteristic. There are no dependencies between the agents.

[00:09:58]This means [music] we can heavily parallelize it. Each thread will be responsible for a subset of the agents and will record the collisions it detects into its own [music] array.

[00:10:16]Once the collisions are gathered, we still resolve them sequentially.

[00:10:20]>> [music] >> As doing so concurrently could introduce data races.

[00:10:24]It is possible to parallelize this step as well, >> [music] >> but we will leave that for later.

[00:10:30]By utilizing 12 threads, >> [music] >> the processing time drops to just 4 milliseconds, which is immediately much more reasonable.

[00:10:38]Thanks to all these optimizations, [music] the system is finally ready to be used in the actual simulation.

[00:10:47]I have also reworked the user interface to make it less intrusive and easier to extend.

[00:10:53]The various features are now accessible via a menu at the bottom of the screen [music] and I have added a Zen mode to minimize the UI.

[00:11:08]I am now going to add a colony with a large food source nearby.

[00:11:15]Placing an obstacle right in the middle will really put the system to the test.

[00:11:20]As its edges will create situations with extremely high ant density.

[00:11:25]Right from the moment the ants spawn, we can see that they are quite organized.

[00:11:30]Their movements are more uniform [music] and they do not get in each other's way.

[00:11:50]The ants have found the food source, so the real test can now begin as the first trails form and the ant population starts growing.

[00:12:00]Let's speed things up a bit to see the trails emerge.

[00:12:16]We can already see that adding the avoidance system does not prevent the formation of roots at all, which is a great start.

[00:12:27]The ants seem to navigate well and no longer collide head-on.

[00:12:31]However, the density isn't very high yet.

[00:12:41]I find the ants' trajectories very satisfying.

[00:12:44]The navigation is much more organized than before. [music] >> [music] >> In crowded areas, navigation is trickier but remains much smoother than in the previous version.

[00:13:31]>> In the hotspot near the obstacle, >> [music] >> the density has increased significantly.

[00:13:36]A few ants struggle slightly to make their way through.

[00:13:40]But, overall, the swarm remains quite disciplined.

[00:13:57]The population has now grown substantially, approaching 1,200 ants.

[00:14:02]We are far from the 20,000 entities used in the performance test, >> [music] >> so the computing cost of the avoidance system here is negligible.

[00:14:17]There is one detail I haven't mentioned.

[00:14:20]Ants carrying food are heavier, so they delegate most of the avoidance correction >> [music] >> to the unburdened ants.

[00:14:27]This is why we can often see the latter clearing the path to let the carriers [music] pass.

[00:14:45]Everything seems to be going well.

[00:14:48]I will let the simulation run longer to test the whole system with many more ants.

[00:15:08]It seems to me that with this new mechanic, the paths are straighter.

[00:15:12]Perhaps [music] having far less chaos on the trails helps optimize the trajectories.

[00:15:28]>> Another change I made to the simulation is that the colony physically grows as the population increases.

[00:15:35]In addition to providing a visual [music] indicator of the colony's size, this helps absorb a much larger flow of arrivals and departures, rather than creating massive bottlenecks around the nest.

[00:16:12]After an hour of simulation and nearly 6,000 ants, I am very satisfied with the result.

[00:16:19]The trails remain highly organized and the whole system feels much more cohesive.

[00:16:25]Performance remains solid, even though more could potentially be parallelized.

[00:16:38]As always, the project and its source code are available on my Patreon.

[00:16:43]I'd like to take this opportunity to thank all the members who support my work. And of course, Incognit >> [music] >> for sponsoring this video. You can find all the relevant links in the description. Thanks for watching.

[00:18:09]>> Mhm.