## Monday, February 25, 2013

### Simple terrain smoothing

After creating or importing terrain you may find it to be too steep or jagged. Part of this depends on how your terrain system is written, but it also depends on the resolution of the terrain and terrain you're importing.

Let's image the grid below signifies sections of our terrain, with the numbers representing elevation. We can see there are two peaks that are 20 meters tall, surrounded immediately by flat terrain that is 0 meters tall. So we basically have two very steep and pointy peaks that are 20 meters high.

To smooth the section represented here in blue, we total up all of the heights in the red squares (which gives us 20), and we divide by the number of red squares (there are 8 squares, so 20 / 8 = 2.5), and we average that result and the height of the blue square together. (20 + 2.5) / 2 = 11.25. We now have our new smoothed value, and we replace the blue square with that value.

Here we can see the results after smoothing out just the one square in the example above.

Here's what we get when we run the algorithm against every square in the grid.

Here's the algorithm:
```public void SmoothTerrain(int Passes)
{
float[,] newHeightData;

while (Passes > 0)
{
Passes--;

// Note: MapWidth and MapHeight should be equal and power-of-two values
newHeightData = new float[MapWidth, MapHeight];

for (int x = 0; x < MapWidth; x++)
{
for (int y = 0; y < MapHeight; y++)
{
float sectionsTotal = 0.0f;

if ((x - 1) > 0) // Check to left
{
sectionsTotal += HeightData[x - 1, y];

if ((y - 1) > 0) // Check up and to the left
{
sectionsTotal += HeightData[x - 1, y - 1];
}

if ((y + 1) < MapHeight) // Check down and to the left
{
sectionsTotal += HeightData[x - 1, y + 1];
}
}

if ((x + 1) < MapWidth) // Check to right
{
sectionsTotal += HeightData[x + 1, y];

if ((y - 1) > 0) // Check up and to the right
{
sectionsTotal += HeightData[x + 1, y - 1];
}

if ((y + 1) < MapHeight) // Check down and to the right
{
sectionsTotal += HeightData[x + 1, y + 1];
}
}

if ((y - 1) > 0) // Check above
{
sectionsTotal += HeightData[x, y - 1];
}

if ((y + 1) < MapHeight) // Check below
{
sectionsTotal += HeightData[x, y + 1];
}

newHeightData[x, y] = (HeightData[x, y] + (sectionsTotal / adjacentSections)) * 0.5f;
}
}

// Overwrite the HeightData info with our new smoothed info
for (int x = 0; x < MapWidth; x++)
{
for (int y = 0; y < MapHeight; y++)
{
HeightData[x, y] = newHeightData[x, y];
}
}
}
}```

 Here's some purposely jagged terrain, without any smoothing

 Terrain after one smoothing pass

 After five smoothing passes

 After 50 smoothing passes. 20 passes would probably have been fine

### The bounce-pad hack in LEGO Universe

The bounce-pads (also known as "bouncers") in LEGO Universe were a means of travel, when you stepped on them they sent you to a specific location in the map, usually somewhere nearby that you could not otherwise reach. Bounce-pads were one of the first gameplay elements created during the production of the game (almost 3 years before the game released), and had no real issues during the entire production run or alpha/beta testing, so we were all somewhat surprised to run into a huge bug on the very first day the game opened up to the public.

The whole company gathered in the gym around some big screen TVs so we could watch the game go live for the first time. We watched a few people get in the game and play for a short time and then we all scattered back to our desks so we could login and play the game ourselves. No sooner than had I created my first character I had a person from the live service team at my desk describing to me a serious bug. Apparently there were a large number of players that were stuck in the very first area of the game called "The Venture Explorer", a small spaceship that served as an introduction level to teach players them the basics. About two thirds of the way through the map there is a spot where you must quickbuild your first LEGO model, a bounce-pad, and afterwards you step on it and it bounces you to the next NPC to give you your next mission. It seemed that about 1 in 100 players would build the bounce-pad but could not step on it to get bounced, so they had no way to get to NPC to get the next mission.

We had some in-game GMs talking with some of the players having this problem, and apparently they could see the bounce-pad but they couldn't step on it. The part of the code responsible for bouncing the player was the bounce-pad code that would set the player's velocity when the physics system told it that the player collided with the bounce-pad. Somewhere in that flow something was broken, and I wanted to find out what it was. We had nobody in the office that was experiencing this bug, none of our testers had seen it at any point during production either. Because we couldn't reproduce this in-house my next thought was to see what information I could get from the clients that were seeing the bug. As a gameplay programmer I didn't really know the details of what kinds of reporting and tools the live team had setup with the game to be able to get me information about this problem. As it turns out, there was almost nothing.

The client version of the game was setup to generate log messages for any errors, and there's a good chance the log file might tell me if something was amiss, like maybe the physics for the bounce-pad was failing to load, or if something was going wrong in the collision check. Sadly, the live team never got around to setting up a way for the clients to be able to send us their logs, or for a GM to be able to send a message to the client's program and have it return the logs to us. At the time they said something about possible legal reasons for us not getting information about them sent automatically to us, which seemed a bit ridiculous since the information didn't contain any account information besides the name of their in-game character, and a 32-bit account ID, which even if it got into the wrong hands is worthless. Anyway, getting any information from the client was impossible at the time.

Server log files were one thing I did have access to, unfortunately this was a client issue since not everyone was seeing it, and since the functionality to make the player bounce was entirely client-side, with only some server-side monitoring to check for cheating.

My next idea was to use some in-game tools that I had written during development, that created huge amounts of data about any object in the world. I was hoping I could use this tool to see if there might be any issues with the bounce-pad itself that the tool could find. The tool would analyze thousands of points of data on an object (at run-time) and check for any inconsistencies and report them back. This tool was not built into the version of the client that players used, so I would need to build an internal version of the client and log-in with it, additionally the server would not return the requested information unless you were using a GM account, for security reasons. It took awhile but finally I was given a temporary GM account to be able to analyze the problem, and still we were able to find nothing, mostly because the client information about the object was based on my client, which was working fine.

After about a day of sifting through logs and using tools to try and find any issues I could find nothing, and in the mean time GMs were having to sit in the game and teleport these players to the NPC so they could get their missions. The pressure was on to find a solution, but the only information I had to go on was that a small percentage of players were seeing a problem, and because this appeared to be a client-side problem and there was no system to get client logs back to me, there was nothing I could put in the game to get me any information about the problem. The reason this problem was on me was because I had written the bounce-pad system, the system that now appeared to be broken.

I enlisted the help of a couple fellow gameplay programmers to try and see what we could do to reproduce the problem in-house. We tried removing the physics asset from the computer to see how the game would react, and when starting the game the patching system would see the missing asset and simply download it again. There were code paths that could be hit if a physics file failed to load, so we put in some code to force the physics asset to fail to load, and in that case the game put in a fallback physics shape (a 1x1x1 cube), and even though that wasn't the proper shape it was still enough the player could touch it and the system would respond and bounce them, so that was a no-go. We checked to see if maybe the collision could be succeeding and somehow the bounce-pad code was failing to translate that into a bounce, but we couldn't see any point of failure, or a way to force it to fail.

So here we are with a problem we cannot produce, and a system we can't seem to make fail, and no way to get any information from the players that were seeing the problem. Leaving the bug as-is was unacceptable, as it would mean a lot of lost customers or the expense of GMs permanently stationed near the broken bounce-pad to teleport players. So the solution, was a hack.