Introduction

After seeing crowds navigate in a recent computer game that I played, where two oncoming groups of people (NPCs) seemed to unrealistically side step to avoid each other, I wondered if I could write something better. I gave myself four weeks to do so.

I decided to keep things simple and gave each character (NPC) a simple set of rules and abilities that mimic my own when I'm walking among a crowd. My introversion makes navigating crowds an unpleasant experience, yet I seem to excel at it. It made me wonder whether, conversely, extroversion makes people enjoy crowds yet poor at navigating them. One thing we have in common is -troversion: hence the name of my program. (You may well sigh!)

Ladybirds 🐞

To save time with realistic graphics and 3D scenes, I use simple 2D orthographic top-down rendering. But because heads and hats, representing the NPCs, don't look very good, nor offer a clear sense of direction, I chose the humble ladybird. (Of course, ladybirds can fly, but we'll ignore that oversight.)

To keep things even simpler, I chose a perfectly circular sprite (except for the antennae) to keep collision detection trivial, and without legs to avoid the need for animation.

A Pair of Ladybirds

Each ladybird has a start position and token finishing point. ("Token" because the objective is to navigate through a crowd; it's not about getting home. In a computer game, for example, the finishing points would usually be offscreen or they would be waypoints to keep things moving.)

Here, two ladybirds want to pass in opposite directions. They turn to avoid each other. Because the ladybirds are on direct collision courses, whether to turn left or right is equally beneficial, so they both (independently) choose left (the direction dictated when tied). Once they pass each other, they turn back towards their finishing points.

Eight Ladybirds

We now have eight ladybirds; four on each side. Here, things get more complicated. Let's see how they deal with passing each other. Both linear motion and turning have acceleration and deceleration, with fixed maximum speeds.

24 Ladybirds

How about 24 ladybirds; 12 on each side? The ladybirds are not allowed to communicate directly with each other but are allowed to see. They have a narrow field of view, which keeps the computational upper bound to O(n^1.5) in medium-sized scenes, where n is the total number of ladybirds. For each ladybird that can be seen with this tunnel vision, the observing ladybird must turn to avoid it if oncoming, or slowdown if going the same way.

96 Ladybirds

And here we have 96 ladybirds; 48 on each side. It's interesting to see how they exhibit emergent collective behaviour as they form into groups and lines.

96 Fat Ladybirds

The algorithm also works when the ladybirds are fat and crammed in without much wiggle room. While the ladybirds could walk outside of the frame, the algorithm keeps them close together.

1000 Fat Ladybirds

A 2D grid is used to partition the scene so that, for any given ladybird, only others that are nearby and within line of sight are considered. By limiting the distance each ladybird can see, the algorithm is scalable. While the upper bound in medium-sized scenes is O(n^1.5), as the scenes grow, this myopia causes it to tend towards O(n). In the following video, each group of ladybirds has a single, offscreen finishing point, simulating a waypoint as discussed above. After starting, the video quickly ramps up to 10× its normal speed: the original taking a boring 4 minutes 31 seconds.

Conclusion

The project took a total of 93 hours (that's about two-and-a-half working weeks). Most of that time was trying new parameters then scrapping them for simplicity. Thus, there are only a handful of parameters, already mentioned, such as maximum turn speed, sight distance and field of view, that determine how the ladybirds behave. Even small changes can have a big effect on the feel of the simulation. In fact, I wrote a Monte Carlo–based adaptive optimisation algorithm that learned parameters aimed at minimising the time taken for each ladybird to reach its finishing point. The videos above use these learned parameters, which were generated across different scenes, so no per-scene preprocessing was required.

I have other demos with fixed obstacles, corridors, and even families of ladybirds that must stick together. But for now, other projects are calling...

...oh, go on then, one more.

Families

In this demo, we have ladybird families. The mothers have finishing points, but their offspring have their mothers as the target.