Forem: Kevin Hoffman

How I Ruined a Radar System

Kevin Hoffman — Sat, 13 Feb 2021 16:09:16 +0000

The Backstory

Around a year ago, I was working on a technology demonstration for my WebAssembly back-end, a project that would end up being called wasmCloud. The demo was a game engine that ran in the cloud--a distributed ECS (Entity/Component/System) architecture.

This game allowed players to enter a shared, persistent, 3D sci-fi universe from web browsers and mobile devices alike. The ECS had a system called radar that would, on each frame, populate the list of entities to appear on a player's radar GUI.

After a few hundred people got into the game, we noticed the radar system would get a bit laggy. After it lagged, it eventually got so bad that the radar contacts being displayed in the GUI were several seconds behind what was actually happening in real-time according to the movement system. If we left the game running long enough, the radar system lag ultimately made the entire game unplayable and we had to restart it.

Thankfully the fault did not lie with my underlying "WebAssembly in the cloud" technology, but rather with the naive radar algorithm.

Why Modeling Things as Humans Perceive them is Dangerous

Some of us are old enough to have learned computer programming at a time when most professors thought Object-Oriented Programming was "the way".

We were enthralled by our ability to create cats that could also be lions, chairs that could also be containers, animals that could roar or meow. It was the best time to be alive.

But modeling things in a computer using the same perspective with which humans view that thing is often naive and, in many cases, highly inefficient or broken outright.

My naive radar algorithm wasn't quite object oriented, but it was modeled the way a human might think about the problem. How do I know the list of radar beacons that are on my screen? You could model all the empty space in the universe and examine it for beacons, but we all know that would be a ludicrous idea. Surely there was a better way.

So my "better way" was this: During each entity-frame (a frame sent to a system for a specific entity) just find every radar beacon in the universe (this was an ECS, so I didn't care what entity to which the beacon component was associated), do a euclidean distance check against the positions reported by all beacons in the universe and the radar range of the current transceiver component. Anything less than the transceiver's range away would get dumped into the radar_contacts component (a simple list with GUI hints for rendering).

You see the problem here? A universe with 1000 radar beacons and 1000 transceivers (aka 1000 players) would make 1,000,000 loop iterations per root game frame. So, if the radar system operated at 1hz (1 frame per second), it would have to finish those 1,000,000 loop iterations in under a second. If it didn't finish all of its work within its allotted frame time, it would get behind. Once behind, it would get more behind every frame, until it was eventually so behind that the UI was useless to players. Moreover, if the system needed to make message broker requests for any of those calculations, we're also looking at a million messages per second... just for radar.

We knew this was garbage but it was a demo and we literally got the demo working the day before the conference, so nobody was about to go back in and re-architect radar, especially when we weren't demoing radar, we were demoing WebAssembly as a unit of deployed compute. We just rebooted the game universe once radar got behind. We also scaled out the number of radar system instances we had running (each system was a .wasm file/actor), and that delayed the inevitable, but it didn't change the overall throughput requirements of just the radar system from 1,000,000 requests/second.

This Should've Been The Way

Having had a ton of time to lick my wounds from the defeat that came at the hands of the age-old villain, "rushing to meet a conference deadline", I'd like to think I know better now.

Rather than modeling the universe in a way that required each radar system's entity-frame (set/archetype of components) to make a loop iteration/data request for every other player in the universe, we need to model the data in a way that supports the way it will be used.

Each frame, for each player, the radar system needs to know which other nav beacons are "within range" of the current player's radar receiver. So how do we reduce this to O(1) cost instead of O(n^2)?

There are a couple of techniques, and the first involves an optimization that I call "hash key buddies".

The Hash Key Buddy System

If the vector of things that satisfies your request can be contained within a single hash key, then retrieving that list of things can be done in O(1) cost! I'm sure smarter people have a much better name for this, but the idea is that your hash keys are traversal paths through a binary space partition tree.

I woke up one morning with this idea for recursively sub-dividing regions of space so that the path through these sub-divisions would be predictable. Turns out, this was invented decades ago and is called a Binary Space Partition tree.

A BSP is basically a tree structure (there are many specializations, including k-d trees, used for partitioning n-dimensional space) that divides some "space" into a binary tree. The organization of the tree is up to you--you choose what the leaf nodes contain for your needs. I discovered that there are also other kinds of trees that aren't binary that are optimized for different uses (which led me down a rabbit hole of searching and tab opening).

In our case, we could have taken the 3-dimensional universe and sub-divide it in half recursively down to some depth that is a multiple of our universe size. At each "slice" step, we cut the universe in half and the left child and right child refer to the two divisions, respectively. We then recursively slice those children in half, and so on.

What we're left with is "buckets". Many BSPs are designed so that a leaf is the smallest unit, e.g. a point in a modeled space of point regions. Here's where the "optimize for need" comes in.

Identifying a bucket is like playing the Price is Right game of Plinko. You start at the top (root node) and you traverse recursively by "turning left" or "turning right" until you reach a leaf node. You can then map a "left turn" to the number 0 and a "right turn" to the number 1. What can we do with a "path of bits"? Why, we can turn them into real numbers of course, which can then be used as hash keys!

So let's say my world is 256x256x256 and I want to sub-divide it such that each leaf is 16x16x16, which is roughly the 3D radius of my most powerful radar receiver. If I take a player's location and recursively compare it against the "buckets" in the tree until I hit a leaf, I might take the path right-left-left-left. This gives me a "bit path" of 1000, which is the number 8 (side note: while there are math shortcuts to speed this up, the "slow" traversal to find the bucket is O(log2n) cost).

This has the very, very useful side effect of making it so that everything in the same 16x16x16 region of space can have a "bit path", which I'll call the position key, of 8.

If I want the fastest radar approximation, I can simply dump everyone in the same position key region of space onto my radar display and call it done. This is O(1) cost.

What if I need it to be more accurate? You've probably figured out that this algorithm treats the imaginary boundaries between sub-regions of space as hard barriers that can block radar.

In reality, if I'm in the top right corner of a region, my radar receiving sphere (assuming that's the shape) will overlap with a few other regions. Here's what's even more awesome about hash buddy keys. The region of space that is adjacent to mine is also mathematically adjacent to my "buddy key".

If my algorithm does some quick back-of-napkin math to figure out the other region into which my radar sphere extends, I can get an exact list of all the nav beacons in my range by doing a euclidean distance check on those in my own region and the adjacent region, making the cost O(n) where n in this case is the aggregate number of beacons that could reside in those regions. This is less efficient than the previous, but still deals with a much smaller value of n. Further, the smaller the sub-division the fewer the number of entities I need to check during each frame (but also the smaller the player's perceived radar range).

So, in short, if you need to support a query like "give me everything in my sub-region of the world" or you do a 2-pass filter, which is "euclidean distance filter everything within my sub-region or collection of sub-regions", then using a BSP traversal path as a key for a hash map of vectors could be a ridiculously fast optimization. If you need to do anything other than just dump the bucket items into some other component, then this solution does not scale. This kind of modeling can cause a "zone crash", where a single "bucket" or approximation region contains so many items that you now have the original problem I described--it takes longer to process the items in the bucket than you have latency in your frame budget.

Using a Full K-D Tree

It was at this point that I started scratching my head. If my needs go beyond the "give me everyone in my bucket" level of precision, can I optimize the traversal of the bucket inhabitants so that I can get the list of people in radar range faster than O(n)?

You bet you can, and this is where things get pretty awesome. If I organize the list of nav beacons in this bucket by the sub-region of space they're in, then I might be able to do a traversal that's cheaper or shorter than by calculating n distance squares.

Of course, organizing the items in a leaf bucket into a tree is really just the same thing as making the root tree taller or more deep. Remember that any node in a tree is just another tree.

I briefly mentioned earlier that another way you can model this problem is to take a "point list" (the locations of all the nav beacons in the universe) and then every single nav beacon becomes a leaf on this tree.

Because every point in this tree is a leaf, the "hash key" now refers to only one coordinate in space. Coincidentally, this also means that your K-D tree implementation needs to handle multiple "things" existing in the same position.

This is where, at least to this nerd's mind, things get beautiful. Now, to find the list of all nav beacons that are within some euclidean distance of a point of origin, this is just a graph traversal starting at the radar receiver's leaf, and collecting all nav beacons within n traversal hops.

Transient Data Structures

I want to make one more point before my bloviation comes to an end. This point is that all too often we just assume that data is stored in just one canonical way for its lifetime. This assumption creeps throughout our code and propagates needless inefficiencies everywhere.

In the case of a k-d tree mapping a point region, this structure might not be optimized for keys changing. Mutating a k-d tree in place requires a re-organization of the entire tree.

If a ship's position changes every frame, then it will be re-organized within this tree every frame. If all 1,000 ships are assumed to be moving, then what we really want to do is construct this k-d tree anew at the beginning of each frame rather than incurring the re-sort/re-organization cost of each move during the movement system frames. The point here is that given what we know of the data and the rate of change, it's faster to build this structure from scratch every frame than it is to mutate it in place.

Summary

In summary, my point here is that thinking of space and the objects within space from a human perspective led me down a horribly inefficient road.

Thinking about space and the objects within it as data structures that are read-optimized or write-optimized for specific purposes means that my systems can now get a lot more work done per frame, which means I can have more systems doing more interesting things in my simulation and I don't have to worry about them getting behind and exceeding their frame latency budget.

p.s. - fun fact: Open Location Codes, also called "place keys" are just ascii-encoded traversal paths through polar coordinate sub-divisions of the planet!

Invoking Functions on Distributed Game Objects

Kevin Hoffman — Fri, 29 May 2020 15:52:30 +0000

This is the second post in my series on developing a modern MUD using waSCC and WebAssembly; taking old-school monolithic concepts from the MUD worlds of yore and migrating them to the new, cloud-native, wasm-based future.

I've found that writing posts like this before coding helps me organize my thoughts and saves me some time when I get to the IDE. I like to call this method blog-ahead compilation.

LPC Function Calls

In LPC, there are countless reasons why a block of code might need to invoke a function on another game object. This could be in combat to reduce hitpoints, it could be the code that changes the state of a set of armor from unworn to worn, a sword from sheathed to wielded, etc. We need to make function calls to buy things from stores, to send text messages to players, to flip quest bits when a player places an ancient relic in the base of a fountain. The list goes on.

In the world of the single-process monolith, function invocation is pretty simple, and in LPC it looks something like this:

my_object->function(parameters);
call_other(my_object, "function", parameters);

In most variants of LPC that I remember, you were able to make function calls in either an OOP-like (the "arrow") fashion or the regular C style syntax.

What's important to notice about this code is that the variable my_object is an instance variable just like any other, and is sitting in memory directly in the monolithic process.

If we need to invoke a function call on a game object in a world where game objects are spread across a cluster of driver processes, then we need to re-think things quite a bit.

Managing Distributed Game Objects

One possible way to deal with distributing game objects is to just simply distribute instances across a grid and then provide some kind of RPC plumbing to allow remote invocation. This means that for every single game object active in the virtual world, there is an instance variable consuming a stack pointer and heap memory somewhere in a process in the cluster.

This feels inefficient to me, like we're reaching for the safety blanket of old techniques because that's what we're familiar with. The only reason we want to manage game object instances like traditional language primitive objects is because these things have state exposed through simple fields or properties. In the cloud, we don't want stateful, long-running variables.

Further, if each of these long-running stateful variables is actually a WebAssembly interpreter (since our user code is all wasm actors), that's a ton of duplicated overhead per game object. If we get to hundreds of thousands of game objects, this will absolutely not scale well.

Instead, what we want to do is load the prototype of the game object, and then provide per-instance data as parameters to each function call. This means that the prototype remains stateless, and every function call is able to be executed by the prototype (the actor wasm code).

With this approach, we can have a single actor like std/sword handle all function invocations for all of the thousands of instances of swords in the game. If the path through /std/sword starts to get too "hot", then we can simply spin up more copies of this prototype on different nodes in the cluster and distribute load across them.

If the function call needs state for processing, it'll query it from a K/V store or cache or get it as part of the call (those are optimization details I can worry about later).

Making Distributed Game Object Function Calls

Recall that an instance of an object in an LPMud is a combination of its prototype and some form of unique instance identifier. Our distributed mudlib capability provider can keep track of the mapping between what the game calls a prototype (e.g. std/sword or areas/kevin/dragon1) and what waSCC calls an actor. waSCC uses URL-friendly encodings of ed25519 keys to uniquely and globally identify actors. Our mudlib will keep a mapping between the game prototype name and the public key of an actor, so that it can hide the complexity of those public keys from developers and convert a content-developer-friendly function call like this:

let sword: &dyn Sword = get_object("/std/sword#5672458").unwrap();
sword.wield();

into code like the following that is safely hidden from game content creators:

fn get_object(obid: &str) -> &dyn GameObject {
    let (public_key, instance) = obid.pk(), obid.instance()); // a value like ("MB4OLDIC3TCZ4Q4TGGOVAZC43VXFE2JQVRAXQMQFXUCREOOFEKOKZTY2", "562478")
    &RootGameObject::new(public_key, instance)
// Could do &RootGameObject::from_objectid(obid) as a shortcut
}
. . .

sword.call(this_interactive(), "wield", []); // This is an RPC efun

In the above code, the call function would then forward an invocation up to the mudlib capability provider (running in the waSCC host process) and in turn execute the appropriate network code to find the prototype, build context, invoke the function, and return the result.

A Note on Polymorphism

I don't want to support inheritance in this MUD because wasm modules (actors, game objects) are intended to be treated as freestanding, portable units of compute. Trying to build inheritance into them would be an affront to WebAssembly, in my opinion.

But, I do want to be able to treat things similarly and allow code to be shared. How do we deal with the fact that all weapons can be wielded? What if I want to make a scenario where a chair can be wielded or a cardboard box can be worn as armor? That's a topic for an upcoming blog post, because translating the flexibility of LPC's multiple inheritance hierarchies into freestanding WebAssembly modules without forcing a ton of code duplication is no small task.

Managing Per-Call Context

When we invoke the wield function on a sword, we need some context in order to properly deal with that call. This context is especially important because the actor in which this function resides is stateless by design.

We need to know who wielded the sword. We also needed to know which sword this is, and the values of all of the variables currently set on that sword.

An absolutely crucial aspect of LPC that I enjoyed so long ago is that wizards were able to be productive and create programmatic content without needing to know the underlying details of how the MUD and game driver worked. In my case, I spent months building an entire area with no knowledge of the intricate interplay between the mudlib and game driver, or what the difference was between library functions and external functions.

If this actor-based wasm MUD is going to be successful, we need to be able to hide the irrelevant details so content creators can easily do their jobs.

To keep the API clean, I don't want wizards to have to code things like context.get_something("foo") over and over again, nor do I want them to know the details of how we're representing context internally. Instead, the context will be transparently set in a variable hidden in the mudlib actor API prior to the invocation of a function. If a function call needs context, then it can obtain it from the underlying variables.

Let's take a look at some sample Rust wasm code that might be found in /std/sword.wasm:

public_functions! { wield };

fn wield() -> Result<()> {
    let me: &dyn Sword = this_object();
    let ti = this_interactive();
    write(ti, "You wield the sword. Is it glowing??")?;
    say(ti.third_person() + 
      " wields the sword. It begins to glow!\n")?;
    me.set_wielded(true);
    Ok(())
}

This looks like super simple code, but there's a "metric crap-ton" of complicated things happening, and that's as the world should be.

Feature developers should write simple logic, and boilerplate and plumbing belongs elsewhere.

Let's take it apart step by step:

this_interactive() returns a &dyn Interactive, a game object reference that supports core functionality, plus interactive functionality (it can send and receive text). All of this is done inside the wasm module boundary through the mudlib API by accessing the thread-safe (actors are single-threaded) context that was hydrated prior to invocation.
write() sends a text message to the interactive thing (which could be a player or a game-controlled NPC). This creates a remote invocation request that will bubble out across the wasm boundary, through the mudlib capability provider, across the network to the prototype for the current interactive object (e.g. /std/player). Context is built remotely prior to invoking the say function in the player prototype (which is a waSCC-hosted actor).
say sends a text message to every object listed in the inventory of the room the wielder is standing in
this_object() is essentially the "self" reference, and is a &dyn GameObject which is in turn automatically cast to &dyn Sword via supertrait casting.
set_wielded makes a call to the host's key-value capability to set the wielded value of actor Mxxxxx....x instance 12345 in the distributed cache.

All of these functions could fail, which can in turn cause wield to fail, which would eventually send a message to the player that typed wield sword, which would ultimately be delivered via socket over the telnet connection (or web socket to the browser client).

Summary

Building an elastically scalable cloud-native online multiplayer world is a difficult thing. However, my hypothesis is that as developers building business functionality day in and day out in the cloud, we deal with a lot of the same problems.

If we remain vigilant about hiding complexity from feature developers (in the case of our MUD, wizards writing actors), then we can make the act of creating clean, crisp, secure, functional code an actual joy, and maybe writing code won't suck as much as it does today.

p.s. all of the code in this post is purely hypothetical, and will likely change radically once I sit down to code some of this up.

WebAssembly in the Cloud - Will it MUD? ⚔️

Kevin Hoffman — Fri, 22 May 2020 23:58:48 +0000

Overview of MUDs

Throughout my career, one of the first things that I've done when encountering a new technology is ask myself whether this technology can be used to create a MUD, a multi-user dungeon (or dimension). MUDs, at least historically, are multi-user, online, text-based adventure games. It's quite possible that there are some MUDs that are older than some of the people reading this post. Just because a technology is old doesn't mean it's bad. I'm going to over-simplify a bit, but MUDs tend to come in two flavors:

Data-Driven - an engine presents a gaming experience by reading from a fixed-schema set of data
Code-Driven - a driver (what we nowadays would call a virtual machine) loads user/wizard-supplied code files on demand to provide the gaming experience.

I personally have no interest in the former. For the latter, the best example of a code-driven MUD is the famous LPMud. An LPMud has 3 core components:

The game driver (virtual machine) - This is a stateful process that runs on a host, providing a network interface and exposes a suite of "efuns" (external functions) to LPC code.
The mudlib - Code written in LPC that provides the foundation of the game, e.g. weapons, objects, economy, guilds, magic, rooms, etc.
User (wizard) Code - Code written in LPC by players of the game. This code utilizes the mudlib to create the virtual world in which players inhabit.

LPC is a blueprint or prototype based language. Every file (e.g. lib/weapons/sword.c) is a game object. If a game object can be cloned, then multiple instances of the blueprint can exist in memory. In the case of a sword, the blueprint object is lib/weapons/sword and a specific instance of a sword (the one my character is wielding that is worn and about to break, for example) might be lib/weapons/sword#127.

Before I get into how any of this relates to WebAssembly, let's take a look at a sample bit of LPC code:

inherit "/lib/room";

void create() {
    ::create();
    set_short("a simple room");
    set_long("A simple room in a simple building.");
    set_description("This is a simple room in a simple building.  It is very nice.");
    add_exit("north", "/realms/descartes/north_room");
}

This code might exist in a file like areas/kevin/simple_room.c. It should be fairly obvious the benefits of having user-created code like this rather than admin-defined fixed data. This lets the game evolve over time and get more and more features that can be supplied by users rather than a single core developer.

waSCC Overview

waSCC, WebAssembly Secure Capabilities Connector, is a WebAssembly host runtime that dynamically binds cloud native capabilities to actors (WebAssembly modules). The goal of waSCC is to let developers define pure business logic and deploy it in a small, secure WebAssembly module that is completely decoupled from the capabilities that satisfy non-functional requirements.

As I was developing waSCC, one thought kept gnawing at the back of my brain: can I use waSCC to let people write MUD code as wasm actors?

I think the answer is yes.

waSCC as an Evolution of LPMud

Back in the good old days, an LPMud was a single process running on a machine to which players would telnet in order to play. If we're going to build a modern MUD, then it needs to be a distributed, cloud-native system that can dynamically scale to handle changes in load. Thankfully, this is precisely what waSCC is designed to do.

Recall the 3 components of an LPMud:

Game Driver (VM)
Mudlib (LPC)
User Code (LPC)

waSCC is a WebAssembly host, and as such is a virtual machine that executes wasm modules. This means we can probably use waSCC runtime hosts as components of a distributed game driver.

A mudlib is a core set of functionality that is securely exposed to user code that provides foundational building blocks for creating virtual worlds and game experiences. A waSCC capability provider seems like an ideal way to provide a mudlib. User code could make requests of the mudlib to do everything from set state (remember this is a distributed system, state isn't local to a process) to communicate with players, trigger weather events, initiate combat, and much more.

Finally, user code in an LPMud is written in LPC. User code in a waSCC-based MUD would be written in any language that compiles to a waSCC-compliant actor .wasm file.

As a thought experiment, let's take a look at what it might look like to re-write the previous LPC example as a Rust-based waSCC actor (for information on creating waSCC actors, check out this tutorial.

#[macro_use]
extern crate wasmud_mudlib as mudlib;

gameobject_handlers! { mudlib::msgs::CREATE => create }

fn create(msg: mudlib::msgs::CreateMessage) -> HandlerResult<()> {
    mudlib::room::create(); // Perform default room setup

    set_short("a simple room");
    set_long("A simple room in a simple building.");
    set_description("This is a simple room in a simple building.  It is very nice.");
    add_exit("north", "/realms/descartes/north_room");
}

It looks pretty similar to the original LPC code, but what you don't see here is that because this is a WebAssembly module running under a waSCC host, it's automatically getting enterprise-grade scalability and security and a pile of other features.

We can continue down this road and see what it might look like for the room to clone an NPC and move it into the room upon creation:

fn create(msg: mudlib::msgs::CreateMessage) -> HandlerResult<()> {
    mudlib::room::create(); // Perform default room setup

    set_short("a simple room");
    set_long("A simple room in a simple building.");
    set_description("This is a simple room in a simple building.  It is very nice.");
    add_exit("north", "/realms/descartes/north_room");

    let dragon = clone_object("/npcs/dragon");
    dragon.move(this_object())?;
}

The cool new stuff here is clone_object and the move function on the dragon variable. In traditional LPC, since it was running in a single monolith, code like this would directly instantiate the dragon.c file by running it through the VM interpreter and then immediately add the dragon reference (e.g. /npcs/dragon#1284) to the room's _inventory field.

This code, by virtue of running under waSCC, is far more powerful. The clone_object function will ask the mudlib provider to instantiate another actor (/npcs/dragon.wasm). Our user code does not care where or how this dragon is instantiated. Next, calling move on the dragon will ask the (distributed) mudlib to move the dragon into this room, triggering all appropriate real-time events and dealing with all the ugly things in the background like replication, eventual consistency, etc.

Summary

In conclusion, it is my hypothesis that we can use waSCC, actors, and secure capability providers to create a MUD that lets players write code that looks and feels as simple as the original LPC, but automatically deals with running in a distributed, dynamically scaling, multi-user environment in the cloud.

I would love to hear your thoughts on this as a potential project. Do you think it's a good idea? Should I continue a series of blog posts as I attempt to write some of this MUD in waSCC? Let me know!

To stay up to date, you can keep in touch with me on Twitter and you can check out the waSCC organization on GitHub.