Building a Tiny Crowd Simulation for the Web

Introduction

I recently added a fun new effect to my portfolio website that I’m excited to share with you all. Inspired by the crowds present in Roller Coaster Tycoon, I wanted to create an “open-air art exhibit” vibe on my site, where tiny people would be walking around and admiring the work on display.

The result is a tiny crowd simulation, where visitors walk around the margins of the content, stopping to admire and even snap photos. Some visitors even hold balloons that float and bounce around! The crowds use RVO collision avoidance, and work is spread out across many frames through coroutines to optimize for performance. The graphics are rendered through Canvas/WebGL.

In this blog post, I want to take you through the step-by-step process of building this simulation. I’ll be breaking down each individual piece of functionality that made it all work. Whether you’re a fellow developer looking to add a fun touch to your website or just curious about how this kind of effect is made, I hope you find this post informative and enjoyable.

Obstacles and Attractions

In this ‘simulation’, there are two key features of the environment: obstacles and attractions. Obstacles are defined by DOM element boundaries and are avoided when agents are finding paths. On the other hand, attractions are also defined by DOM element boundaries, but are used as the destination for agent paths.

Effectively, attractions are used to give agents a place to move to, and obstacles impact how those paths are found. The congestion heatmap mentioned earlier is used to determine how much weight is given to each obstacle during pathfinding. This ensures that agents are directed towards paths that are less congested and more navigable.

Technically, RVO has a notion of “obstacles” as well, but it should not be confused with this article’s use of the term “obstacle” to refer to a DOM element marked as part of the available navigation area. By defining both obstacles and attractions in the DOM, we are able to create a realistic simulation where agents can navigate around obstacles and towards their desired attractions.

Agents (Overview)

To simulate people walking around the page, a simple “navigation agent” class was created for the purpose of finding a path across the world and subsequently traversing it. The logic is simple: an A* path query is performed, the waypoints are stored in the agent, and it moves towards each waypoint until reaching the destination.

The API is similar to that of a NavMeshAgent you’d find in Unity, however, it is relying on A* pathfinding instead of a navmesh. On creation, an agent might be given a balloon attachment. This uses a simple 2D spring to follow the player, which adds a bit of realism to the simulation.

Additionally, another 2D spring is used for controlling the agent’s velocity. This spring controls the acceleration of the agent based on the desired speed and the current speed of the agent. By using this spring, the agents can navigate the environment in a more realistic way, with smooth acceleration and deceleration.

Agents (Finite State Machine)

To create more engaging interactions, the agents in the simulation need to exhibit simple behaviors such as walking to their destination, admiring nearby attractions, or simply idling. To handle this, I created a very simple finite state machine for the agents which effectively rotates between each behavior.

The Travelling state is active when the agent is walking to their destination, Admiring is when they are “reading” content, and Idling is when they are just hanging out (probably waiting for an A* path query to return). With this, I can easily manage the ’lifecycle’ of an agent and debug behavior issues.

Additionally, this simple state machine allows for per-state effects, such as the occasional camera flash effect emitted by an agent when they are in the Admiring state. The resulting effect is a set of agents which are more engaging and dynamic, and whose behavior is more varied and less robotic.

Agents (Spring-Based Velocities)

One of my favorite uses of a spring is to control velocity of a character or vehicle. By using a critically dampened spring, changes in velocity or direction become much more curved, smooth, and natural-looking.

This is useful in particular for our AI agents which are effectively moving between waypoints. When an agent reaches a waypoint, their velocity is changed to point towards the next target. By ‘default’, this velocity change would effectively cause an agent to snap towards the correct direction and produce a harsh angle in their trajectory. However, with a spring, this velocity change effectively becomes smooth and resilient to major direction changes.

By incorporating this spring-based velocity control, the motion of the agents (particularly when rounding corners) becomes much more organic and realistic. If you’re interested in learning more about springs and their uses, this article provides a fantastic overview: [https://archive.is/a40u5]

Agents (Spring-Based Balloons)

For the held balloons, a simple usage of a 2D spring was employed to create a more dynamic effect. Rather than a static asset or animation, a spring was used to react to position changes of its owning agent.

Using a spring for the balloons position ensures that it will always follow its agent, while mimicking the ‘floaty’ nature of a balloon trailing behind someone. The balloon itself is rendered as a simple sprite with a line renderer attached, giving the impression that it is being held by the agent.

Overall, this minor effect adds a lot to the experience and was a lot of fun to implement.

Discretizing the DOM into an optimally small, non-uniform grid

To find a path across a given web page, I needed to query the webpage in terms of a grid. I reached for A* as a standard practice for pathfinding, which means I needed a way to discretize the DOM into an optimally small grid.

Each DOM element marked with a certain class is examined when building the grid. I used a simple algorithm that determines the size of each DOM element boundary, and finds the greatest common factor in each boundary size. These GCF’s become the cell width and heights. This produces a non-uniform grid with the largest possible grid cells, and therefore the shortest A* calculations.

However, if the grid is too big, many agents have to walk the same path, and many ‘visually obvious’ paths are not actually traversable. To provide finer granularity in the pathfinding calculations, I included a step to subdivide the grid as well. This helps prevent agents from getting stuck in bottlenecks, and ensures they can navigate around the page more efficiently/logically.

Using A* for pathfinding on the discretized DOM grid

With the DOM discretized into a grid, the actual pathfinding algorithm is a simple variant of A* without much frills. The ‘cost’ of each A* node is determined by two things: 1) whether the cell intersects with an obstacle boundary and 2) the current ‘congestion value’ of the given cell. (The use of a congestion heatmap is covered in the next section.)

Additionally, a custom coroutine class was developed to help spread the pathfinding work out over multiple frames. This helps prevent the page from freezing up while the pathfinding calculations are being made.

Ultimately, this produces paths that prefer to stick to ‘walkways’, i.e., the margins between content. However, if an agent is pushed into an ‘out of bounds’ area, the pathfinding still works as expected, and the agent will quickly move into an acceptable position.

Use of a congestion heatmap as a source for pathfinding weights and attraction selection

The idea for using a congestion heatmap came from Squirrel Eiserloh’s recent presentation at GDC ‘23. I developed a heatmap class that effectively allows one to ‘seed’ a 2D grid with values, blur those values across the heatmap, and of course then query for those values later.

Here, we use the heatmap to determine congestion; by seeding the heatmap with the agent positions and appropriately blurring it, we are able to query any cell in the world and determine how congested that particular area is. The weight value itself is arbitrary and took some tuning; if the cost is too high, then even following in another’s “wake” would ultimately cause them to reroute in an unrealistic fashion.

The congestion map is used when the agents are performing their A* search, ultimately heavily weighting paths that pass through high-traffic areas. This helps agents to find paths that reach their destination without adding to any existing traffic jams on the page. Similarly, when the agents are choosing their next ‘attraction’, they will reference the congestion map to select an attraction/viewing point that is not totally crowded.

The ultimate result is a system where agents are incentivized to “fan out” and cover an evenly-distributed area while optimizing for avoiding large crowds. When they can’t avoid crowds or other agents, though, we need a collision avoidance mechanism.

Using a TypeScript port of RVO2 for collision avoidance

With paths in hand, our agents can walk to their destination. However, they will clip through each other as they walk, and I wanted to add a bit more realism to the crowds. Using something like Phaser’s physics bodies would add a lot of strain on the CPU, which is unacceptable as this effect is meant to be “dressing” for the webpage experience.

Thankfully, a collision avoidance solution exists and is actually used by Unity and Unreal for their NavMeshAgent behaviors. It’s called RVO (Reciprocal Velocity Obstacles) or ORCA (Optimal Reciprocal Collision Avoidance), and it’s a method for simulating crowd behavior.

RVO/ORCA works by considering each agent’s velocity and predicting its future position. It then creates a ‘velocity obstacle’ around each agent, which is essentially a 2D volume that represents all the velocities that would cause the agents to collide. These volumes are combined and analyzed to determine a new velocity for each agent that avoids collision. TLDR: math!

To use RVO in my simulation, I ported the C# library RVO2 to TypeScript. After some work, I managed to get everything working. I first tested it using a basic canvas implementation and then moved to using Phaser 3 as that was the end goal for the WebGL support.

The main difference when porting the library is that the TS/JS version is single-threaded, whereas C# is set to be multithreaded. There was also an issue with the KdTree’s leaf size, which broke the nearest neighbor queries. Not sure why this was an issue in TS and not C#, but setting a leaf size based on the number of active RVO agents seems to have fixed all issues.

In theory, this ported library could be made multithreaded through the use of WebWorkers, but the performance in regard to transferring things ‘over the wire’ would need to be measured to ensure it’s a worthy tradeoff. I have no plans to pursue this idea at this time.

Creating a Coroutine class to help spread work across multiple frames

The A* pathfinding queries could sometimes take a long time. They use a while loop under the hood, and with a large enough web page, a pathfinding query can take as long as 1 or 2 seconds. My A* algorithm itself could probably be improved, but even with optimizations, there is a chance the page could hang as pathfinding is performed.

The solution I reached for was: coroutines! These are not new to JS, but I wanted to try my hand at writing my own. Additionally, I wanted to ensure that the performance for the page remained buttery-smooth, and the low-level coroutine knowledge helped me make optimizations.

I wrote a Coroutine class that accepts a generator function, which occasionally yields, similar to what you’d see in Unity. It exposes a Promise so you can await your coroutine if needed.

This adds more time to the overall query process since there are some pauses between processing. This caveat is a non-issue for this particular use case; the experience doesn’t break if an agent hangs around for an extra half second or so.

I also wrote a CoroutineManager which handles scheduling all of the instantiated Coroutine classes. Under the hood, it uses requestAnimationFrame, requestIdleCallback, or setTimeout as its ‘scheduling mechanism.’ For this particular case, I found that requestIdleCallback provided superior FPS performance. This means that all pathfinding queries are effectively deprioritized by the browser itself, which is exactly what we want here; the browser should prioritize playing videos or running UI code over this effectively functionless feature.

Even with using requestIdleCallback, if too many coroutines are active and updating, eventually frames will begin to drop if they are all updated in sequential order. To solve this, the CoroutineManager uses an arbitrary ‘frame budget.’ This means that on each requestIdleCallback, the CoroutineManager will only update coroutines for ~11ms (90fps) before stopping and exiting. Any completed coroutines are pruned from the active list, and any remaining will be next to be updated.

The end result is a system that lets you queue coroutines without impacting framerate, at the cost of a longer processing times. This was super effective for the needs on this project regarding A* pathfinding.

Use of the Halton Sequence (2,3) to place new agents/visitors with minimal congestion

In order to spawn new agents for our simulation, I wanted to determine starting placements that were a bit more evenly spread out when compared to uniform randomness. Typically, I would reach for Poisson-Disk, but wanted to try something different, and maybe a bit simpler.

One way to do this is by using a Halton Sequence, which is a deterministic sequence of quasi-random numbers. The random values produced by these sequences are distributed more evenly than true random numbers, but provide a ‘good enough’ randomness to replace Poisson-Disk Sampling. I wrote classes for HaltonSequence and HaltonSequence2D in TypeScript, which can generate a 1D and 2D sequence respectively.

By using the HaltonSequence2D class and the (2,3) sequence, I was able to determine generally optimal starting placements for agents. This led to a 66% drop in congestion at simulation startup when compared to placing agents based on uniform randomness!

The (2,3) sequence is visually similar to poisson-disk sampling, but of course does not abide by the strict neighbor distance requirement. For the case of spawning moving agents, this looks great and consumes very low CPU overhead.

Overall, this was a small win but overall improved the experience without needing to calculate a poisson-disk fill or anything.

WebGL rendering via Phaser 3

Since this project was going to be rendered to webpages, performance was key. I wanted to ensure that WebGL was used wherever possible, so any work that could be pushed to the GPU would be.

Given my prior experience with Phaser 3, I decided to leverage it for this project. Phaser 3 is a powerful game framework with extensive support for WebGL. It allowed me to easily create a WebGL rendering context and use it to draw the agents and balloons on the canvas.

Phaser spawns the canvas element and through CSS, it is placed on top of everything via z-index. To prevent mouse interactions from being intercepted, I apply a simple pointer-events: none; to the canvas.

Integrating RVO with Phaser was pretty straightforward after resolving some issues around scaling certain units/settings. Overall, the use of Phaser 3 helped me streamline the rendering process and improve the performance of the simulation.

Debugging/Dev Tools

I created a simple DevTools controller class which provided access to dat.gui and stats.js.

dat.gui provides a ‘control drawer’ with various functions or variable settings. It provides controls to update values on the fly, or to trigger registered functions on button press. This made it really easy to enable debug visualizers; I could click a few buttons to toggle on/off the debug drawings on the fly.

stats.js provides visual monitors for various metrics, such as FPS, memory usage, or any other custom stat you want to track. For this project, I added a few monitors: 1) Current hottest value on congestion map 2) Number of actively running coroutines 3) Number of failed A* queries 4) Breakdown of agent counts by current state (idling, etc)

Conclusion

In this project, I’ve explored the various components and techniques involved in creating a tiny crowd simulation for a portfolio website. By combining DOM discretization, A* pathfinding, RVO2 collision avoidance, and a range of other optimizations, I achieved a fun and engaging visual effect that adds personality to the site without sacrificing performance.

Through the use of Phaser 3 for WebGL rendering, coroutines for spreading work across multiple frames, and other performance optimizations, I ensured a smooth experience for users. Additionally, by incorporating elements like the Halton Sequence and congestion heatmaps, I was able to enhance the realism and behavior of our agents, making the simulation more interesting.

I hope you’re able to find some inspiration or useful code snippets here. Please feel free to reach out if you have any comments, questions, or suggestions. Thank you!