CoE Developer Blog: April 2023

Greetings, Elyrians!

Welcome to the April, 2023 Monthly Developer Blog for Chronicles of Elyria & Kingdoms of Elyria!

Because I spent the entire month of March focusing on engineering, this will be another highly technical developer blog. However, in keeping with the commitment I communicated in the March 2023 CoE Developer Blog, I've provided plenty of visual aids in this update so people can see what I've been working on this month.

To begin with, I've continued the effort I started in February and finished the Spatial Partitioning System. To put the work from this month in the context of what's required to ship the Chronicles of Elyria, this is another view of the CoE Product Roadmap:

Image of Roadmap

In addition, I've spent time this last month working on a developer visualizer tool. In keeping with the soul theme of Soulbound Studios, I'm calling it Medium. Because, you know, it sees "entities & auras..."

I'll talk more about the long-term goal of Medium after we explore the new spatial partitioning system. However, in the meantime, I wanted to mention it as all of the videos in this developer blog are taken from inside Medium.

Spatial Partitioning

In last month's developer blog I talked a reasonable amount about what a spatial partitioning system is and why it's crucial. So I recommend going back and reading that one if you haven't already. But to recap the highlights...

As a game simulation runs, there's a constant need to perform proximity, collision, and intersection checks worldwide. Various game systems use these checks to determine and update the state of the world.

Here's a quick list of just some of the systems that need to perform such checks regularly.

  • The Knowledge & Gossip system would check for intersections between a citizen's field of view and all objects within it to determine what the citizen sees
  • The Building Buffs system would use proximity checks to find all objects which are within range to receive passive buffs
  • The Access Permissions would check for intersections between a citizen and room entities to determine which room and building a citizen is in
  • The Combat system would use a collision check between a weapon's collision volume and an object's collision volume to determine whether it hit anything
  • The Stealth system would check for intersections between a citizen's bounding volume and surrounding shadow volumes to determine whether the citizen is partially or entirely within shadows
  • The physics system may check for collisions to determine whether an entity is colliding with the terrain or other surface
  • The AI system may use proximity checks to find the closest weapon within some maximum distance to defend itself.

In games with many such intersections, collisions, and proximity checks, it becomes necessary to subdivide the world to perform those calculations efficiently.

This month I finished adding two spatial partitioning systems to the Soulborn Engine (CoE & KoE's common, server-side game engine) to make the above more efficient. So far, I've added a quadtree and an octree. I will likely add more before the launch of CoE, as performance dictates, as different systems work better under different situations.

Before demonstrating the different spatial partitioning systems in use, I wanted to point out that performance is critical because these systems are used so frequently by so many entities worldwide. So, I spent a couple of weeks this month profiling and tuning the performance of the spatial partitioning systems. Optimizing the systems, I increased performance by 100x the naive implementation in some cases. Here are some images of the benchmarks. Note that the metrics below do not include any speedups from concurrent execution. These were all single-thread execution times.

Benchmarks Image 1

Benchmarks Image 2

With the introduction to spatial partitioning out of the way, and the metrics covered, let's look at the work done this month. In the first video below, the spatial partitioning system continuously subdivides the included area into groups of four boxes. This is to take advantage of a fundamental physical property: If two boxes don't intersect, then the contents of those boxes also cannot intersect.

The CoE/KoE Spatial Partitioning System

As the number of entities in the world increases, we subdivide further to limit the number of additional calculations. For a sense of scale, the smallest rectangles on the grid are 1m x 1m. The medium rectangles are 16m x 16m (the size of a plot), and the most prominent/darkest rectangles on the grid are a single parcel (64m x 64m). I have debug buttons to simultaneously add groups of approximately 100 and 10,000 entities. Towards the end of the video, there are roughly 40,000 entities in the area of 512m x 512m.

In the first video, all entities had uniform scale bounding boxes. But that isn't the case in practice. Some entities, such as buildings, can have dramatically larger bounding volumes. Here's an example of the system working with different-sized bounding boxes.

The quadtree with non-uniform bounding boxes

Note that some of the "bounding boxes" turn red in these videos. The bounding boxes turn red when the spatial partitioning system detects a collision. So this part of the Soulborn Engine is now fully functional and capable of running entirely on the server.

The partitions created by the quadtree aren't static. They're frequently updated to minimize the number of unnecessary checks performed. If I tell the entities to move, the partitions dynamically change within the quadtree.

The quadtree with moving entities

As mentioned, I've implemented two spatial partition algorithms into the system. The first, quadtrees, are great for 2D games or systems where you only need to break things up along two axes. Moving to a more complex solution becomes necessary when there are three dimensions.

The quadtree with terrain

Notice that the previous video introducing the terrain didn't change the spatial partitions in the quadtree at all! That's because changing the position of an object's elevation does not impact which partition it's in when using a quadtree. You may also have noticed in the video that some entities colliding (red) on the grid are no longer hitting (white) while on the terrain. That's because the elevation now separates them. However, if we only used the quadtree to determine collisions, it would indicate that a collision was still occurring. That's wrong. If two entities are in a building but on different floors, they're not colliding. We have a solution for that. The octree! We are, in fact, already using the octree for collision handling, which is why some bounding boxes turned white when we added the terrain.

An octree with terrain

The above all demonstrates that both the quad and octree are fully functional and support terrain collision on the server. As before, the octree is dynamic in the horizontal and vertical axes.

The octree with gravity

Medium (Developer Debug/Admin Visualizer)

I've been demonstrating the features and functionality of the (finally) implemented Spatial Partitioning System, server-side locomotion, and server-side collision systems using the newly implemented developer debug/visualization tool. A tool like this is standard. It exists in one form or another in virtually all game editors and, I imagine, all MMOs. You can see similar views/tools in the Unity Editor, UE4/5 Editor, Godot Editor, and Roblox Editor.

Thus far, we've used the UE4 Engine for the Chronicles of Elyria game client and the Unity Engine for the Kingdoms of Elyria game client. Seeing/hearing that we're working on our visualizer tool may raise some questions. I know this because that happened when I showed this tool to my family. Let me take the remaining part of this developer blog to talk about the long-term benefits of this visualizer - aside from just being a convenient way to demonstrate the server-side engineering work I've been doing.

What does Medium as a Server Visualizer do?

Most commercially available game engines provide an editor. This editor is used to construct a level/scene and, in most cases, view and debug the game while it's running. To build a level, you drag and drop objects into the environment, where you can then click on them to view their initial properties.

To debug the level, you generally hit "play," which starts the local simulation running. You can then see the game playing and again click on objects to see their properties changing in real-time.

But as these are offline games, the single source of truth resides within your client space. What happens when the source of truth lies on a server somewhere? What happens when the positions, bounding volumes, and all properties of the entities are distributed across multiple processes, living out on the internet? Then how do you see and "debug" the server?

In this scenario, the default would be to use some technology-specific tool to "query" the data. For example, suppose your entity data is all stored in SQL or NoSQL databases. In that case, you could use a SQL Query Tool or Editor to connect to the databases and view the data. But what if the state is changing so fast as to make repeated reads from a database impractical? In this case, you'd need to connect directly to the services performing the business logic to get a "view" of the data.

And that's where the Server Visualizer comes into play. At the most basic level, the Server Visualizer provides real-time access to the game state of a game, as seen by the server. For traditional tabular data, we can see the data associated with an entity by clicking on one in the viewer and then watching the live data change in real-time in some property viewer/editor - just as one might do in a game editor. For example, suppose I wanted to see how much a piece of food had decayed. In that case, I'd click on the food item or search it by entity Id and then look at the "Decay" property.

That said, some data, such as position, orientation, bounding volumes, entity types, etc., can be better represented directly in the 3D view. You can still see that information by clicking on or selecting an entity Id. However, you can learn so much more by viewing the relative positions of objects in the world.

I didn't have time to write any UI for this first version of the visualizer. At the moment, it's impossible to see the entities' run-time properties. But I got the position and bounding volumes for the base entity types and terrain displayed in the view.

Why Not Use the Game Client?

At this point, I've (hopefully) convinced you of the need to view the data on the server and see the spatial relationships of the entities. Why not add debug/admin tools to the standard game client? I'm glad you asked!

First, the typical game client has too little and needs too much information to be a good debug viewer. For your game client to show the states of all trees, bushes, characters, etc., it's constantly receiving state changes for every entity within your field of view (or within some sliding window of your current position). That's a lot of data that, unless you're interested in it, you don't need when viewing the world through a developer tool.

Taking the previous example, as a developer, if I want to know the decay of an apple on a table, I can click on the apple and implicitly subscribe to the data for that apple. Then I receive notifications about the apple's state. But for the client to display the apple on the table with the appropriate model, it needs to constantly receive updates about the decay of the apple. To be an effective admin/debug viewer, I need to limit the information I get to only what's critical for my current purposes.

At the same time, as the developer, I need access to any information. If I want to know all citizens' locations, I need to be able to zoom out and see them. But in the game client, the player is limited to only the information we want them to have. So, for example, if they're outside of a building, and the door is closed, we don't want them to get information about what's in the building, such as where the apple is located or what state of decay it's in.

Creating a perfectly acceptable visualizer within a game editor is possible. We've done it previously. In addition to our first visualizer, which was implemented in TypeScript and used WebGL to display the server's state of the world, we also added the functionality to our UE4 client. When hitting "play" in the UE4 game client, it connects to a local or remote server, updates the state of the world within the client to match the server state, and allows you to either play or visualize from there.

So why not use that one? Our current game, Kingdoms of Elyria uses something other than UE4 for the client. And our new platform uses a different networking and protocol stack. We also don't want to ship those features to the customer, which requires conditionally compiling all of that functionality out of the client before release if we include it. Incidentally, this identifies another critical point that leads to the next section - when you're developing multiple games on a single back end, it helps to have a single set of developer tools separate from the game client you're using.

Why not still use Unity (or Unreal)?

If you've watched the videos above, you know we're not using Unity either for Medium. Medium is "from scratch ." All rendering, UI, and input code are from me (using libraries.) So why not use Unity?

First, by writing my viewer, I control how "lightweight" the client is. As you saw in the video, I can view 50k+ entities with minimal hiccups without any optimization passes to the viewer. Even with minimal rendering requirements, etc., many features still need to be supported in both UE4 and Unity, which slows down performance, forcing me to debug or "see into" smaller parts of the world at a time.

Second, Unity and Unreal are both licensed engines. The Soulborn Engine is client agnostic, without knowledge of either Unity or Unreal. Using a Unity/Unreal viewer as part of our core development pipeline would force anyone using the Soulborn Engine also to have a license to the chosen game engine. This way, we can license the Engine w/o forcing other developers to use the same client and without us having to develop two different viewers for each possible license.

What's next?

While the Aura System will take little time to finish, my focus on the visualizer this month took up the time I was planning to complete the aura system. So that'll have to be demonstrated in May. But it was worth it to allow you to visualize the functionality I've been working on and see the world from the server's point of view.

Additionally, now that I've implemented a functional server-side spatial partitioning and physics system, it's time to incorporate that into the new MMO platform.

I need to get a mesh of spatial partitioning services working together, distributed across multiple processes, to do that. For that, I first need to finish the ServiceHost and put a new server networking & message layer in place. Ideally, these will also be demonstrated next month, with the visualizer showing support for entities and spatial partitions spread across multiple processes.

These are exciting times! While we've had visualizers in the past, this new one is significantly more performant, engine-agnostic, and is here to stay. Likewise, while we've had spatial partitioning and physics before, they were always client-side authoritative. Now we're finally entirely server-side authoritative. There's still more work, but the core platform is nearing completion, as is the core game engine. After that, it's just game mechanics and more game mechanics. Until next time!

Pledged to the Continued Development of the Soulborn Engine and the Chronicles of Elyria,