Ten Thousand Cards

When I was first invited to join ZA/UM, one of the core problems they were dealing with was the soft cap on dialogue size with the tooling they were using at the time. The biggest dialogues in Disco Elysium have well over a thousand nodes, but their tooling started to chug at a couple of hundred. I solved that early on, but with Tarinoi we wanted to do even better.

Setting our target ​

When making anything performance sensitive, you need to know what your target is. If you're dealing with a hundred cards, you don't really need to worry much about performance at all, the platform will carry it as long as you're not doing anything actively wrong. With a few thousand, you need to cull and manage graphics memory so you're only rendering what's necessary. With 10,000, you can still keep the raw card data in memory, but you will have to be pretty careful with the graphics objects and to parcel work out so it doesn't cause stalls or stutters. A hundred thousand needs spatial indexes. A million needs streaming and indexes for off-page connected content.

The biggest dialogue I've seen actually going into a game was a bit short of 2,000 cards. The biggest I've seen used in a tool like this was about 7,000 cards – it was a dumping ground for stuff that was left on the cutting-room floor but might be resurrected some time. Based on these numbers, we set our performance target to 10,000 cards per board on the kind of hardware we expect game developers to be working on, with an additional requirement that from there on out, performance would degrade gracefully rather than failing catastrophically.

My test board with over 10,000 cards, running on a 4k monitor at about 60fps.

The big bottleneck: interactive elements ​

The big bottleneck with a tool like this is the interactive part of the UI. If we were to instantiate every field on every card, or build the cards using the HTML DOM (or any other UI library, if this wasn't a webapp), we'd quickly hit an effective performance cap. Built out of HTML, even a single card with bare-bones styling would have dozens of DOM nodes. Modern browsers are really performant, but they cannot handle DOMs of tens or hundreds of thousands nodes easily, especially if things are changing dynamically – cards being moved around, edited, resized, reconnected. You will get progressive slowdowns, hitches, stutters, stalls, and eventually rasterisation errors (screen going blank sometimes).

Therefore, we took the same approach as tools like Miro: rendering the cards on a canvas element in one layer, with a single set of UI controls overlaid on the currently focused card, positioned so that it lines up with the rendering and gives the illusion of being the same thing. The graph layer manages its own interactions – for dragging cards around, resizing them, connecting and disconnecting them, deleting and creating them, and so on.

There is only ever one set of active controls, which adapts to the focused card to align with its contents.

We built our card rendering engine on PixiJS – a popular library for rendering 2D scenes with WebGL on the browser. In many ways, our renderer looks like what you have in a game engine. We load our board data into memory as plain objects, then we create Pixi graphics objects for the ones near the viewport. Pixi then uploads these to the GPU and renders them. We toggle their display on and off as they enter and exit the viewport so we don't render things unnecessarily. We pan and zoom around with camera transforms, all of which run on the GPU and are really fast and fluid.

However, our cards are complex enough that we can't redraw them as vectors every time. Instead, the card content – the text, the avatars, the colours, the grain texture, the field outlines and so on – should only be redrawn when it changes and reused otherwise. In other words, we need to be able to generate textures for the cards on the fly. This creates another complication: memory limits. If we're zoomed all the way in, we're looking at a handful of cards and need to see them at full resolution. When we zoom out, more and more cards come into view. If we were to use the same textures all the time, we'd run out of memory. Therefore, we need to regenerate the textures at different resolutions as we zoom out, destroying the higher- or lower-resolution ones and replacing them with the new ones on the fly. An additional complication is that because textures are rendered asynchronously, when you're zooming or panning fast, it might fall behind – so we need a way to manage the texture queue so we cancel texture requests that aren't needed anymore and prioritise ones that are.

So when you're zooming and panning around the board, there's a quite a lot going on: Pixi views being created and returned to the pool and having their display property switched on and off, textures being destroyed, requested, and recreated, with some of those requests cancelled, and graphics being redrawn. All of this has to be done without hitches, stutters, or stalls, with a constant frame rate. If you're on a slower computer, it's much less distracting to have the textures lag a bit than to have stalls and stutters, so we also need to make sure that if resources are tight, things degrade in a way that's least distracting to users.

The frame budget and parcelling out work ​

For this, we used a pretty standard graphics programming technique – the same that's used in just about every game with real-time graphics updates: the frame budget. Pixi provides a ticker that fires every graphics frame, and lets you hook functions to it every time it fires. So we wrote our render loop to fit in that budget. If we have a 60 fps frame rate, we have about 16 milliseconds for each frame. So we parcel that out to each of the different things that needs to be done within that frame, making it so that if, for example, we run out of time to create new card graphics objects, that spills over into the next frame instead of hitching.

Additionally, we moved texture rendering to a worker thread. Worker threads run in the background so even if they do something that lasts longer than a single frame, it won't cause the UI to hitch. This also frees up frame budget on the main thread. When the renderer on the main thread determines it needs a fresh texture for a card, it sends a message to the texturing thread to request one. When the texturing thread finishes, it posts the finished texture back. The renderer picks up the texture and associates it with a card. The next time the card is rendered, it picks up the texture, sends it to the GPU, and it's updated on the card.

The nice thing about this process is that each individual step is very quick, so it lends itself very well to being parcelled across frames. Moreover, things will only spill between frames when you're moving around the graph fast – zooming or panning quickly – which means most of the time you won't even be able to perceive texture updates landing a few frames late, especially if they're about levels of detail – if the scene is in motion, you simply won't be able to see when the resolution switch happens.

All the way out ​

Finally, we made a few optimisations that also related to user experience. As you zoom out, the cards become so small you can't properly make out what's on them anymore. At that point, we block out the text into translucent grey blocks, and even further out, we remove the textures altogether, just showing the avatar of the character who's on the card (if there is one). And when zoomed all the way out, we only show the cards as coloured rectangles – at that point, even the avatar would be a smear you can't make sense of.

These visual transitions also correspond to a UX change that we think feels very intuitive and makes it possible to work with a graph effectively when zoomed all the way out. At that point, we switch off Pixi's hit detection. You won't be able to interact with wires, pins, resize handles, or other hotspots on cards. They would be incredibly tiny, and even being able to hit the right one would be very, very difficult – if we kept them, you would just get frustrating misclicks all the time.

Instead, we switched to our own hit detection that runs over the data objects that underlie the Pixi graphics. This hit detection will only determine if your pointer is over a card or not. The cards themselves are still big enough to reliably interact with, so with the hotspots removed, these interactions become predictable and intuitive again. The upshot is that when zoomed all the way out, you'll be able to marquee-select, drag, copy, cut, and paste cards, without having to worry about accidentally selecting wires you can't even see properly or triggering other similarly hard to see interactions.

It takes a quite a bit of measuring and debugging to find out where the bottlenecks are and to get everything feeling fluid under all conditions.

Ten thousand cards, and beyond ​

This UX interaction improvement also brings the graph performance well past our 10,000 card target. The data model based hit detection is much, much faster than Pixi's much more complex hit detection, and since our cards are rendered as 1-pixel textures scaled to the card dimensions and tinted with the card colour, they render very fast.

When pushing the renderer, I found that the graph remained usable at 100,000 cards, with about 25,000 of them displayed on-screen at the same time. The frame rate had slowed down a bit and it took a few seconds to load all those cards when first going into a graph, but in the unlikely event that somebody with a reasonably beefy machine would want 100,000 cards on a board, they could totally do that. As great as the temptation to overengineer, I decided that there's no point optimising away the frame rate slowdown at these numbers – the added complications to the code wouldn't be worth performance improvements that would only be good for bragging rights.

There are all kinds of reasons why making a 10,000 card board is a terrible idea – not least because it would be a production and QA nightmare – but if you want to, you can, and more importantly, that soft cap lets realistically huge flows of a thousand-odd nodes breathe easily. Every tool has its limits, and we want to push Tarinoi's out far enough that you never need to think about them. We believe that you should be able to structure your work based on what your project needs, not by what your tooling can handle. We don't ever want Tarinoi to be the bottleneck.