Search
  • Yukkafuzz

This week I spent maybe three or four hours attempting to squash one insidious bug. It was an infinite loop, which does not cause the game to crash; rather it causes it to just "hang", where the program is running but I can't take any actions. The only way to stop this is to open task manager and "end task" on Unity, the game engine I use to develop EXO. So every time the bug occurs, I have to restart the entire system. That also means I can't view any of the debug logs - messages I put in the code that print to the console - which is my most effective way to track down bugs. Instead, I was forced to narrow down the issue by "commenting out", that is, temporarily removing, parts of the code and running the program again to check whether it hangs or if removing that code stopped the issue. Still, that typically wouldn't take that long, but this particular infinite loop happened in the generation code, which complicates the task of just commenting out certain lines.


To understand this, let's explore how the generation system works in a bit of depth. First, generation is hierarchical. You can think about the motion of a body in, say, a solar system, as a hierarchy of orbits. The Earth and anything in its orbit move around the Sun slowly, completing their orbit once a year. Those objects orbiting the Earth, like the Moon, not only move relative to the Sun but also to the Earth, so first move the Earth and all of its orbiters, and then move the Moon in its orbit around the Earth and all of the other objects orbiting the Earth. The hierarchy can continue - what about a space probe orbiting the moon? Well, it moves with the Earth and the Moon and in its own orbit about the Moon.


That hierarchy can get quite large in multiple-star systems. A binary star is seems simple enough - both stars orbit a common point, and then they each have their own orbiters. But rarely, (actually, I'm not sure if science has confirmed exoplanets this way or not) planets may also orbit that common point rather than one of the stars specifically. Then, a trinary star adds another layer. One star is orbiting the center of mass of the other two stars, which are orbiting each other. A (highly unusual) quaternary star can go one of two ways: two binary stars orbiting each other, or one star orbiting the center of mass of a trinary star. Each of these layers, at least theoretically, could have other objects also orbiting those centers of mass.


Naturally, this orbit hierarchy provides the best way of generating artificial solar systems. First, generate the star. Then generate the planets and other objects orbiting the star. Then, for each of those objects, generate the objects orbiting them and those objects' orbiters. Continue this until everything that should have orbiting objects has created them.


Because each object does essentially the same thing to generate its orbit and its orbiters (and a few other characteristics), all types of objects share the code used to do those things. In fact, the code-sharing is also a hierarchy (a normal inheritance hierarchy, for my programmers out there). Typically, this organization is helpful for solving bugs, but in this case, it arguably made it more difficult. I wanted to temporarily remove the code that caused the bug, but all I knew was it was somewhere in this generation hierarchy. Sure, I can stop the bug occurring by telling the star not to generate any orbiters. But that stops all of those objects' orbiters from being created as well, and so great - I've narrowed it down that generating the characteristics of just the star does not cause the bug. There are probably around 500 objects in the system, and I've eliminated one of them as a possibility. Whoop-dee-doo.


Still, that's the starting point. As it happens, the system that was causing the bug was quite large (I was also testing some new changes to generation, which is partly the cause) - there were more than 40 objects orbiting the star. That just added to how long everything took, because generating a system that large takes non-negligible time. The strategy from here looks like this: limit how many orbiters the star can generate, starting with half. If the bug still occurs (it did), then halve it again. Now the star only generates ten orbiters. Does the bug occur? No, so bump the number by half of what you just changed it by (up to 15). Bug? No, up it by half again (up to 17.5, rounded to 18). Bug? Yes, now try 16. Bug? No, and congratulations! We've narrowed down that the bug occurs somewhere in the generation of the 17th orbiter. (That process is known as binary search). But guess what? That orbiter is a gas giant the size of Jupiter! You know what that means?


Moons!


But let me take a step back once more. Another reason this bug was so tricky is that it did not occur for every object of a specific type, which all share 100% of their code. At first, I thought maybe a somewhat unusual type had a guaranteed infinite loop in it, like a comet or a derelict space ship. But after I examined the system the bug was occurring in, it was clearly not the case. Some rarer objects were generated successfully before the 17th orbiter we just decided has the cause. And the other objects' code simply could not possibly have an infinite loop - I manually went through their code to check, several times, since it really seemed like that would be the cause. But no.


Back to the moons. This is where the code sharing makes things a little difficult. The gas giant shares the code for generating orbiters with the star (and with just about every other object). I wanted to stop the gas giant from generating its orbiters to confirm whether it or one of its orbiters was causing the bug, but I didn't want to stop the star from generating its own, since that would preclude the gas giant's existence. It's just a little bit of copy/paste, a little bit of if statements and that can be done, but it is another extra step.


Unfortunately for me, the 17th orbiter, the gas giant itself, was not the cause of the bug. The program ran fine when not generating its orbiters. So I repeated the binary search narrow-down process, this time with the thankfully small number (5) of moons. I could smell it - I was getting close! But then it really threw me off the trail. The problem was occurring with the first moon, which, as it turned out, was the one moon to have another, baby moonlet orbiting it. When I figured all of that out, I thought "it must be caused by a moon orbiting another moon!" And I went deep into the code, searching the pieces related to that to try to find an incorrectly written "while" loop, which are almost always the culprit to this kind of problem.


But I didn't find anything. In fact, I didn't even find any while loops at all, much less an incorrect one. I needed more clues to find my mistake. I had narrowed it down to the one actual object for which generating its properties (not its orbiters) created this bug, but I did not know where in the process of property generation it was happening. More copy/paste, if-statements later, I could comment out, property by property. Don't forget that whenever the bug occurred I had to restart Unity.


Finally, I found the property causing the problem, which was the atmosphere (which was practically non-existent by the way, for a moonlet this small). But even scouring these few lines of code, I couldn't tell what the problem was. So it was time to bring out the rarely used (for me) big guns: the debugger. It's a handy feature that lets you execute code line by line - find which loop is actually going infinite - and look at the contents of an object, so maybe I could tell what was unique about this tiny moon, compared to all the other moons of the same type.


So I pulled up the debugger, hit run, waited for a couple of seconds, and then,



Some things aren't as easy as they sound. So I spent another 20 minutes trying to figure out the problem. It ended up that a quick update of my IDE (Visual Studio) - the program I use for writing code - did the trick.


With the debugger finally running, I found that the loop going infinite was a loop I use for generating practically everything in the entire game! It was one of my random value generation functions that let you put some bounds on the generated value. (Programmers: I use normal distributions, not linear distributions, so this is not reinventing the wheel exactly.) That code had been used over and over - was there really a problem with it? Well, sort of. I quickly found the reason the loop went infinite was that the bounds' minimum was greater than the bounds' maximum, which was caused by a missing line of code in the atmosphere generation function. The thing is, only unusual other random values could cause the atmosphere code to put a minimum that was too large, so it hadn't been occurring with everything.


I added the missing line to the atmosphere function, but I also added a line to my bounded random value function that would crash the program if the minimum were greater than the maximum. One test run of the program to confirm I had fixed the issue, and finally, after quite the ordeal, that bug was over.


Hope you enjoyed reading about the work that can go into a game like this!


-Yukkafuzz


P.S. The moral of the story is: assert your preconditions.

  • Yukkafuzz

Beauty underlies the wonder of exploring a new place. So it's essential for places one can discover in any game, especially ones focused on exploration, be beautiful.


For many of the early years in games, developers chased photorealism (having the game look like a photo of real life) as the one way to achieve more beauty. But as graphics improved, the challenge of making them realistic required more and more resources. AAA games still, for the most part, have graphics that attempt photorealism (and some of them are quite good at so doing, I might add), but smaller developers were forced to become more creative with the beauty their games contained.


And so, the idea of an art style proliferated throughout indie/small games. Some would go for the nostalgia of 2D and pixellated - since games had now been around long enough for that to exist - some would go with simple, using modern lighting effects with low-fidelity objects and textures, and some decided on a cartoon style (many AAA games have done this as well - Zelda: Breath of the Wild comes to mind). Of course other styles exist I have not listed here as well.


The obvious question is, where does EXO fit in all of this? And the answer has shaped itself and morphed over the course of development, as I imagine it does for many games. I don't want to get caught reaching too far for photorealistic, but I don't quite want something as simple and cartoony as, say, Astroneer (which is a big inspiration for me, by the way). But the exact point in between has been in flux. EXO's planets, as viewed from space, were one of the first features of the game. But they've been slowly changed to arrive at their current (and probably not quite final) form, all in the pursuit of the wonder of exploration.


Take a look at what a planet looked like early on:


Early on, there were only three simple planet visuals you could find.

That's decidedly in the "simple" art style category, but as a space nerd I really wanted to see planets with detail that looked a bit more like the planets we know in our solar system. So I created a tool to generate some textures to use on my colored spheres.


The second iteration of planets had some detail that (I think) added some beauty.

Creating the tool is somewhat more involved than just one sentence and, "Voila!" It generates noise in a three dimensional space so that I can "sample" at a certain position (x, y, z). This sample will give a number between 0 and 1, which is converted to a color according to a gradient I have put in. So, the tool samples the noise at a bunch of points on the surface of a sphere, and stores the resulting colors in a 2D image. To get satisfying results, I slide around a lot of different settings:

Using the texture generation tool involves many sliders.

With the tool in hand, I had created some more detailed and better-looking planets. But there were still only three possibilities. When I'm exploring many systems, the novelty of those three fairly pretty planets quickly wears off, and I lose the wonder felt when finding something new.


Clearly, I needed some added variety. I allowed each planet to randomize its underlying color, with some colors more rare than others. This did create some wonder when I found a planet with a rare color, like the pink ice giant below, but since the variation of color on the surface was always one of just a few possibilities, it still did not really achieve a truly unique feeling.


Randomized color for each of my planet types actually helped a lot, but eventually seeing the same pattern over and over got old.

One of my main tenets for EXO: Perl is that, on average, things you find should "make sense", so that when you find something that "doesn't make sense", it feels cool and unique, rather than dumb. So, for example, if you find a planet near its star that planet should be very hot, generally, so that the one time you find a cold planet near the star you think "Whoa, I wonder what caused that!" instead of "Wow, this game developer really does not understand science." With this in mind, the appearance of planets should, generally, align with the planets' properties. Coupled with the lack-of-variety issue that had become apparent, this meant I needed to create some detail that fit more extreme situations - most obviously, high and low temperatures.


Cold, icy planets and extremely hot, molten planets were previously missing. Notice the bumpiness on the surface on the left, and the way the one on the right emits its own light.

While I was working on these new planet types, I also leveled up my tool to allow creating bumpy and light-emitting surfaces. These look great, as far as I'm concerned, but, varying the underlying color does not work as well with more complex details. The contrast between the brown and the whitish gets muted if a tint is added. Perhaps you can guess the solution I'm using?


I had long avoided trying this because I knew it would involve one of my least favorite things: performance optimization. But EXO now generates a unique texture for every planet, using the tool I had written with some additions. To generate a surface with the detail in the above two planets, it takes my computer about a second. Imagine a system with 100 planets or moons (not an unreasonable amount) - that would be almost a two-minute loading time! So, of course, all surfaces are not generated with that level of detail at first. As you get closer to them, they'll create their surfaces in more detail.


I'm still in the process of fully following my "things make sense" tenet for this new planet texture strategy, but the idea is this: the possible settings for creating the texture (see the above screenshot) will be different for planets with different types and features. So I'll leave you with a bunch of the possibilities.




-Yukkafuzz

  • Yukkafuzz

It was an early design decision to avoid photorealism in EXO. The feel should not be cartoonish exactly, but simple. Not only does this align with the experience I hope the player to receive, but it's also a practical choice; one person cannot create AAA game graphics and make the rest of a game in a reasonable time frame. With that, I wanted to make sure to avoid imitating other games around with non-photorealistic styles - Minecraft and Astroneer come to mind - when it comes to planetary terrain in EXO. So I arrived at the idea of a block-based system, like Minecraft, except where every "block" can take a number of shapes, allowing for corner pieces, slants, and many others. To accomplish this, I needed a system to determine which shape a given block should take.


Consider a cube. It has eight vertices. But what if I remove one vertex, and make a shape with the remaining seven? You get a cube with a corner chopped off, like below:

Cube with a cutout corner. A technique for smooth lighting is used (averaged normals on vertices), so the faces of the shape are not too sharp.

What if I take off two vertices? Now what shape does it make? .... It depends on which two. Can you determine how many fundamentally different shapes can be formed with 6 vertices of a cube? (As in, different shapes that cannot form each other by rotating and flipping.)


Well, if you remove two vertices that form an edge, you'll get a shape I call a slant. There are twelve orientations of the slant shape (one for each edge). It's fundamentally different to remove two vertices across a face diagonal, as you'll get a shape that's a cube with two corners chopped off, with a diagonal edge between those corners. (There are also twelve orientations of these, one for each face diagonal.) Finally, as you might guess, the last different shape is formed by taking away two vertices across the long diagonal of the cube. That shape is also a cube with two chopped-off corners, but this time they are opposite each other. (4 orientations of these). See below for pictures - in order mentioned.



All right, so what's the point here? For every unique set of vertices you choose, there is a unique orientation of one of these "morphologies" of a cube's eight vertices. (More math for those inclined: how many total shapes/orientations are there? Answer at the bottom.) So interesting terrain can be produced by generating a value "used" or "not used" for each vertex in a large grid. This works for continuous terrain because neighboring cubes share vertices. The edge of one cube's morphology will always align with the neighbor's on that side, since they determined their shape using the same used/not used values for the vertices on their shared face.


Now, complications do arise when fully implementing this for terrain in game. First of all, any 2D shapes look very jarring in a 3D world. So most three- and four-vertex morphologies should actually be ignored. (Imagine the triangle made up by three vertices. You would just see a floating triangle with no depth). For efficiency, the program also should not consider any cube faces that will be hidden by other blocks. So, a block with all 8 vertices used should actually render (show on screen) nothing: if it's fully "used", it is fully solid, which means it should be totally covered. As it turns out, for any morphology, anything on a cube face need not be rendered, since its neighbor will share that face, except when the face makes up the only used vertices.


Imagine a solid, flat ground surface made up of many layers of cubes. Now imagine a ghost layer of cubes on top of that surface. Each of those ghost cubes has its bottom four vertices on the surface. It's actually those ghost blocks that the terrain algorithm uses to render the ground. This is more convenient than checking if a given shape is neighboring "air" on a certain side to determine to show a face.


However, that causes one small complication: what if (for example) three coplanar vertices get generated at the top of a spire? As was mentioned before: floating triangles! So in the end, the terrain generation algorithm does have to check the neighbors of blocks with only three or four coplanar vertices to decide whether to actually render them.



The spire on the left has an awkward-looking 2D top.


To put this into context, the whole terrain creation "pipeline" goes like this:

1. Create a large grid of points.

2. Use Perlin noise to generate a value between 0 and 1 for those points.

3. Threshold that value: air if below a certain value, and solid if above.

4. Go through each "block" and look up the correct block morphology. (Represented as a set of triangles to render. So I had to manually program in more than a hundred sets of triangles, for all the different morphologies.)

5. Translate the resulting triangles into that block's position.

6. Put the resulting triangles in the "mesh" (the object that gets sent to the graphics card)


As you can see, it can be quite a process! I've gone in depth on only one of these steps here (although a couple of them are trivial). Still, I hope it provides some insight on the work and the kind of fun (read: math) that goes into EXO: Perl.


-Yukkafuzz


Answer: 256. (or 255, if you don't count no vertices, or 247, if you don't count single vertices either.) Each vertex can either be used or not be used, so it has 2 states. There are 8 vertices. So the possible combinations can be calculated as 2^8 = 256. Subtract if you don't count low vertex counts as morphologies, and there you go.


Sample terrain in context, on a planet.

One Knight Studio © 2019