April 18, 2019

Fake fluid simulations in Unity - or how to make the water system from Sprinkle game

To research water simulation models I read a PhD thesis called Large-Scale Water Simulation in Games. The author has been working with the water system in Cities: Skylines, so if you want to learn more about how that was done you should read the thesis. But in the beginning of the thesis, the author was discussing different water systems in games. One of the games mentioned was Sprinkle, which is a mobile game where you have a fire truck and your job is to extinguish fires. It looks like this:

I played the game several years ago before I was interested in water systems, but when I saw it now I asked myself "How did they made that water system?" And above all, how could they simulate a water system on a mobile device? To simulate realistic water systems, you have to simulate the Navier-Stokes equations which is taking up a lot of computer power, so you are never doing it in games - and especially not in a mobile game from 2011.

One of the developers has written a blog post on how they made the water system: Sprinkle behind the scenes, and there's also a GDC talk pdf: Constraint fluids in Sprinkle. So what Sprinkle is doing is that they simulate water by using 600 particles and each particle disappears after 3.5 seconds to not make the simulation go slower. To display the particles on the screen they are using a "dynamic particle mesh" which I have no idea what it is, but in the GDC talk they say it's "point splatting with a few tricks." To simulate the particles they are using the built-in physics system together with a simplified Navier-Stokes simulation system. So it looks like this behind the scenes (this is before they add the dynamic particle mesh, so you can clearly see the particles):

To recreate the basic idea I found an article which is implementing something similar in Unity: Liquid Physics. The author is using just Unity's built-in collision system to simulate water, lava, and air. To create the solid surface from the particles, each particle consists of a circle with a gradient circle attached to it. The gradient gets a color (red, green, or blue), and then a render texture is used to capture the different colors:

...and then you use some shader tricks to generate a more solid surface that looks like the element being simulated. To change the type of particle to for example water, you experiment with the rigidbody settings to make something that feels like water. And in the end my version looks like this:

March 21, 2019

Self-driving car 2019 update

About four years ago I made a self-driving car in Unity, which is an implementation of the Hybrid A star algorithm. I update it about once a year, except for last year when I didn't update it, so I decided to give it an extra large update this year. The following improvements have been added:

1. Reeds-Shepp paths. The old version used modified Dubins paths to make something that resembles Reeds-Shepp paths, but now I decide to add the real Reeds-Shepp paths. These were really annoying to make, so I've decided to give away the code for free: Download Reeds-Shepp paths for Unity in C#.

2. Voronoi field. A voronoi field tells, from each cell in the grid, the shortest distance to a voronoi edge (which can be seen as the midpoint between two obstacles) and the closest obstacle. This is useful knowledge to help the car find a path through narrow passages between obstacles and it also speeds up the algorithm when you smooth the path and want to find the distance to closest obstacle.

3. GUI. The old version used different keys to display different textures and paths. But now I've added a real GUI to make it easier to change between the different options by just clicking with the mouse.

4. A semi and a semi with trailer. I've also made a Tesla Simulator, and in the last Tesla Simulator update I added the Tesla Semi truck and a trailer. So I thought it would be interesting to see if I could update the pathfinding for cars algorithm, with pathfinding for cars that also drag something behind them. It was easy to add a model to the algorithm that simulates a trailer, but the problem is to make the real trailer follow the path. So sometimes the drag vehicle is colliding with the trailer even though the algorithm is checking for that, so I will in the future try to find a solution for that.

5. Optimized code. I've learned one or two things since the last update, so I've optimized and cleaned the code.

6. Path following. In the old version of the implementation, the car used to follow the path generated by the Hybrid A* algorithm, which uses the rear wheels to generate the path. But to make the car follow the path with greater accuracy, this path has to be moved forward to the front axle. When the car is reversing this path has to be moved to a "mirrored front axle" to make it easier for the car to follow the path when reversing.

You can test it here: Self-driving car.

March 15, 2019

Download Reeds-Shepp paths for Unity in C#

My side-project is to make a self-driving car in Unity. I've been working on it for about four years and the last update was 2017. This year I decided to make another update because I've learned one or two things since 2017.

A self-driving car is not one algorithm - it consists of several algorithms combined together. The main algorithm in this self-driving car is a path-finding algorithm called Hybrid A*, which is a modification of the classic A* algorithm. Most games are using A* to make characters find their way around the map. But unlike a character, a car can't turn 360 degrees on the spot, so some modifications have to be made. But no matter how many modifications you make, Hybrid A* will never find the target with the exact position and rotation, so we need some kind of path that ends up exactly where we want to go. 

One such path is called a Dubins path, which is the shortest path from point A (with heading A) to point B (with heading B). In total, there are six Dubins paths and you have to measure all of them to find the shortest one. They look like this: 

The problem with those paths is that sometimes a car has to reverse into the spot where it want to go, and a Dubins path is just forward (or just reverse if you make some modifications). If you can both drive forward and reverse, the shortest path from point A (with heading A) to point B (with heading B) is called a Reeds-Shepp path.

While then Dubins paths are six in total, the Reeds-Shepp paths are 48. Also, the original Reeds-Shepp report called Optimal paths for a car that goes both forwards and backwards is not the easiest report to read. Luckily, Matt Bradley has managed to implement the report in C# - but in another game engine than Unity. So I decided to translate the code to make it work in Unity. The main challenge I met was that it took some time to realize that Unity is using a different coordinate system than the coordinate system used in the original implementation.

This is the end result (black means that the car should reverse and white means forward):

You can download the Reeds-Shepp paths (and Dubins paths) here.

February 11, 2019

Tesla Motors Simulator - 2019 update 1

New year and new Tesla Motors Simulator updates are rolling out. In the last update I managed to introduce a bug where the car continued to accelerate for some short time even though you didn't press the gas pedal button. This happened at higher speeds and you felt it most when driving the Roadster 2020. I fixed this bug in this update with maybe 10 lines of code, but it introduced some other inaccuracies, so I had to change the parameters in all cars to make them have the same performance as the real cars.

In the future I might build my own "wheel collider" to have more control over it. I'm currently using Unity's built-in and it's working like a black box where you put in some values and then some values comes out and no-one really know what's going on inside of the box.

In the last update I removed the destruction system that deforms the car when colliding with something. The reason was that I'm using a simplified destruction system and the destruction is sometimes very inaccurate looking from what it would have looked like in real life. But people were sad about it, so I decided to implement it again. I also added dramatic sparks to make it look cooler when colliding. Other games, like BeamNG have more realistic destruction system, which I believe is called soft-body physics. But realism means slower performance and the destruction system I'm using is fast. But I might implement a better one in the future.

The third thing I added was a simple container trailer that the Semi can drag around. The trailer is still a little buggy here and there, sometimes it flips when colliding with some small object, but it's working overall like a real trailer would. I also realized I could take this trailer and add it to my pathfinding algorithm for self-driving cars, so it becomes self-driving trucks!

February 7, 2019

Steering Behaviors - or how not to evacuate a building

One good book I read is The Unthinkable: Who Survives When Disaster Strikes - and Why. It discusses an aircraft accident where many people died even though the computer simulations said they should have survived. What went wrong? The answer is that the computer simulations assumed people move in the same way as water.
For a long time, engineers assumed people would move out of a building like water. They would fill the space they had, coursing down the staircases and flowing out to safety like a river of humanity. Buildings were constructed accordingly. The problem is, people don't move like water.

So if you are trying to model real people, you have to take pain and fear into consideration. People make decisions, they stumble and fall, and they fill up space unevenly. On their way out, they pause to rest when they can. But if you are just trying to make a simple game, you can treat people like water. Treating people like water in games is also known as Steering Behaviors. These individual behaviors are supposed to work like Lego bricks - you can combine several of them to get the final character behavior you need.

Let's say you have a character that's following a path. It will work fine until the character is meeting another character moving in the opposite direction? One solution now might be to calculate a new path with some pathfinding method like A* (A star). But this will take some unnecessary computation power. A better way is to use these steering behaviors, which will make the character avoid the other character and then continue following its path.

The following shows a combination of the behaviors:
  • Seek - move along the flowfield direction
  • Solid obstacle avoidance - is in this case finding the closest point on the wall (the walls are just lines), and if the character is predicted to collide with the wall it should steer away from the closest point)
  • Moving obstacle avoidance - is in this case moving a character away from the character it's colliding with. So it's not a steering behavior but a commonly used cheat to avoid intersecting characters

While researching steering behaviors I learned that the most difficult of the behaviors is avoiding moving obstacles, so there are multiple algorithms trying to deal with the problem. 

Algorithm 1. The most simple obstacle avoidance behavior is trying to just avoid the most dangerous obstacle by predicting where it will be in the future, while ignoring all others.

Algorithm 2. Is trying to avoid all of the dangerous obstacles by predicting where they will be in the future, and then scale the prediction so that obstacles closer to our character are considered more dangerous. 

Algorithm 3. This one has a name and it's Power Law. It's similar to Algorithm 2, but is also calculating an energy. As you can see, the characters are finding their way through the congestion in a slightly more realistic fashion.

Algorithm 4. RVO. This is what Unity is using to make characters avoid each other on their navmesh. I never implemented this behavior but might do it in the future.

As you can see, some of the characters are intersecting with each other. This is a commonly used cheat and the idea is to avoid congestion, you shrink the radius of each character until it's not anymore stuck. This cheat was used in the game Planet Coaster (as explained in this article) and they sold millions of copies, so it should be allowed in your game as well!  

Adventures making a custom navmesh in Unity

I was watching this talk by Oskar Stålberg, who is one of the creators behind a cool indie game called Bad North. In it he said he had fun making a custom "navmesh," and since I had no experience whatsoever from navmeshes, I decided to make my own navmesh. I've earlier got questions if my pathfinding-for-cars algorithm is working on Unity's navmesh (or any navmesh) and I've up until now said "I have no idea" because I wasn't sure how a navmesh is working.

What is a navmesh?
Once upon a time it was common to divide the area, where a character in a game can walk around, into a grid, like a chessboard. The problem with this method is that if you have a big map, you will get a large chessboard, making pathfinding very slow. A better way (in some cases) is to make a navigation mesh (navmesh). You do this by dividing the area into convex shapes, such as triangles, meaning that you will hopefully end up with fewer triangles than cells in the chessboard. This will make pathfinding more efficient because the pathfinding algorithm has to investigate fewer nodes.

How can you learn how to make a navmesh?
To learn how to make a navmesh, I googled "Unity navmesh tutorial." But all tutorials I found were about how Unity's own navmesh system is working - not how to make your own custom navmesh. But why are there almost no tutorials on navmeshes? The reason is not that finding your way around a navmesh is difficult - the reason is that it's difficult to create the shapes, like the triangles, that makes up the navmesh itself. So after much research, I learned that if you want to learn how a navmesh is working, you have to learn the following areas:
  1. How to create the navmesh itself
  2. How to find the shortest path on a navmesh
  3. How to make characters follow the shortest path

How to create the navmesh itself
A navmesh consists of connected convex shapes. The reason they have to be convex is that if you are standing inside of a convex shape, you can walk in a straight line to any other point in that shape. If the shape had been concave you would have to do some local pathfinding inside of the concave shape. These shapes are in many cases just triangles, but some merge these triangles into other convex shapes, such as rectangles, to make pathfinding more efficient.

The problem is: how can you create these connected triangles from the game level you have? You might have these houses and you want some character to find the shortest path between the houses. I believe the answer to that question is Constrained Delaunay Triangulation, which is a big topic, and I've written a tutorial on it here: Constrained Delaunay Triangulation. So now you have something that looks like this:

How to find the shortest path on a navmesh
You have these connected triangles, and now you want to find the shortest path from one triangle to another triangle. To do that you connect the center of each triangle with the center of each neighbor, and then you just run some pathfinding algorithm, like A* (A star), on that graph. When the character is moving between each triangle, it should not move to the center of the next triangle, but the closest point on the edge shared by the current triangle and the next triangle.

The shortest path on a navmesh can be simplified by using a line-of-sight algorithm - the character doesn't have to navigate between the triangles if it can move in a straight line to the goal triangle. But how can you detect if a character can see the goal point it wants to reach? The answer is by using a line-line intersection algorithm. If you draw a straight line from the character to the position it wants to reach, and if this line is not intersecting with any of the triangles edges that are obstacle (has no neighbor), then the character can move in a straight line to the position it wants to reach.

How to make characters follow the shortest path
Now you know which triangles the character has to pass to reach the goal destination. To make it reach the destination, you should learn a set of algorithms called Steering Behaviors. This is what Unity is using to make the characters find their way around their navmesh system. For example, they are using an algorithm called RVO to prevent characters from colliding with each other.

More than pathfinding
Navmeshes are useful for other areas than just pathfinding for characters. While researching navmeshes I read that you can use them to simulate flow. When simulating flow in games you move a texture by using a color and the color determines in which direction the texture should move. For example, if the color is red, then the texture moves in a certain direction. This makes it look like the water is flowing. This colored texture is called flowmap, but they are almost impossible to paint by hand, and what if the flow is suddenly changing direction while the game is running? With a navmesh, you can create dynamic flowmaps.

To make this work you should connect the vertices of each triangle in the navmesh, and then run a flowfield algorithm to find the shortest path from each node to the destination in the triangle you want to reach. As said before, you can use the line-of-sight algorithm to detect if a node can see the goal position. Each node will now get a direction and this direction is used to set the vertex color of the mesh. You can access this vertex color in a shader and thus get the flow direction. Moving the texture in the direction of the flow is kinda tricky and this is a good article on the subject.

This is the dynamic flowmap that determines the direction of flow:

...and then you can simulate something like smoke on the navmesh:

...or water:

Read more
This was just a short introduction, so if you want to learn more about navmeshes, you should read:

February 6, 2019

The art of fake volumetrics - or how to make fluffy red pandas

Most objects in games tend to be kinda flat. The reason is that all objects in games consists of triangles and each triangle takes some time to display on the screen, so you should use as few of them as possible. But what if you need to display something that's not a flat surface, such as hair or smoke? Then you need to use a trick, which I don't think has a name, but we can call it fake volumetrics (I've heard the name "quad stacks" or "shells"). This is how it works:

Let's say you want to make a fluffy red panda:

This panda is flat, while real red pandas tend to be fluffy. To make it less flat you need to fake fur because you cant make each fur straw because it's way too complicated for games. You do this by rendering the panda multiple times, and each time you grow the size of the panda by making the mesh larger along the normals of each triangle. This is done step-by-step around 10 times. Each step you also change the transparency of the fur, so fur closer to the body is less transparent than the fur furthest away from the body. You now get a fluffy panda:

To avoid getting fur in the eyes and the nose you can simply use a texture telling the algorithm not to grow the triangles around the eyes and the nose.

With the same technique, you can make fake volumetric smoke/fog. You begin with a simple plane at the bottom, and then you add multiple planes on the top of the original planes while changing the transparency the higher up you are. And you end up with this:

If you need a better explanation of how to make fake volumetric smoke, you can watch this YouTube video: UE4 VFX For Games: Brute Force Volumetric Gases - Ground Fog & Vapor. The problem with this technique is that if you zoom in really close, you can see the individual fog planes:

To avoid this you can either add more planes, or make sure the player is staying far enough away from the smoke!

February 2, 2019

Lessons learned from the Paradox podcast - Season 4

Paradox Interactive is a company that's both developing and publishing games. In their podcast they talk about the business of video games, and if you want to listen to it on your own, you should search for "The Paradox Podcast" on iTunes or wherever you can find popular podcasts. I've earlier summarized season 1season 2, season 3, and this is season 4:

  • The successful game RimWorld is a perfect "paradox game" they never published/developed because RimWorld is a combination of the games Factorial (manufacturing), Don't Starve (survival), and The Sims (social). 
  • Paradox has acquired the game Prison Architect, which is a game first released in 2015. They acquired it from the company that developed it, so they didn't acquire the developer itself. Prison Architect is a good game because it's a sandbox where you can create your own stories, so Paradox believes they can come up with new content in a similar way as Microsoft is still making money from Minecraft by updating it. Prison Architect is obviously not as big as Minecraft, but both games are similar to each other. Paradox also plans to develop other "Architect" games, such as Ski resort Architect. 
  • Paradox has an idea that to provide free updates to an existing game, they can sell paid updates (DLCs) to game and that will also pay for some free updates to the same game. A seven year old Paradox game is still getting free updates because some people pay for the paid updates. 
  • There's currently a war between developers if they should put their game on the Steam store or on the Epic store. A better idea is to focus on making a good game and put it on a store, and competition between stores is good.
  • Farming Simulator might sound like a stupid game idea - who would want to spend time drive around in a tractor? But it turns out people like to farm, the company behind the game announced they will turn farming into an e-sport, so what you think is boring can be fun if you make the boring parts fun to play.
  • The quality of games released every year is increasing because people can now go to school and learn game development, which is not something you could some years ago. But releasing a good-looking game with no bugs is no longer enough - it also has to be fun to play. And you also need to figure out a way to market the game, which is what Paradox can do for you. 
  • Paradox has recruited Rod Humble to lead a new Paradox studio in US called Tectonic. He has made 200 games (including Sims 3) and has 30 years of experience. 
  • Rod Humble believes in "The Valve style" when making games. Valve is a successful game developer and they believe in: 
    • Small groups
    • Each group members should be specialized in one area while still having a broad range of skills
    • Small amount of documentation (1 page is enough)
    • Moving fast by prototyping ideas without first having to ask if you are allowed to do it and then some manager has to make that decision one month from now 
  • Game developers make art - they sell a fantasy, telling a dream. A game is not like toothpaste which you actually need. 
  • An interview with Wendy Young and her experience of working through the ups and downs in the game industry. 
  • How can you reach a new type of audience that plays another type of game than the audience you already have? Just because you make a game that attracts that type of audience does't mean they will automatically be aware of your game. What Paradox did to make the new audience aware of the new game was to launch a dating app which is an odd thing to do if you are a game developer. But it would make the new audience be aware of the game. 
  • To measure if your marketing idea was successful, you measure of many people found what you wanted them to find. For example, how many watched the trailer, how many media sites wrote about the game, how many signed up for the newsletter, how many pre-ordered the game? But it's still difficult to really measure if it was a success if you have nothing to compare the numbers against.     

This article will be updated as they release new episodes!

January 15, 2019

Computational Geometry - Part 3

As said before and before, I've spent some time learning an area called Computational Geometry. One of the algorithms I learned was how to make a Voronoi diagram. The algorithm I implemented suffered from floating point precision issues, so sometimes the Voronoi diagram lost some edges. The reason was that the algorithm was cutting lines to create the diagram, but the more the lines were cut, the worse the precision of the lines became (because of  floating point precision issues) and in the end the algorithm removed lines it shouldn't have removed.

A better way to generate a Voronoi diagram is to use a Delaunay triangulation algorithm. This algorithm doesn't suffer from floating point precision issues and is easier to implement if you know how to implement the Delaunay triangulation algorithm. To create a Voronoi diagram from a Delaunay triangulation you need just 150 lines of code, while the older algorithm needed 600 lines of code.

This is the result. You can also see the Delaunay triangulation (the black lines).

One other area I struggled with last time I studied the area was how to cut triangles in the best way. You may think that there are many algorithms that can cut connected triangles in 2d space in a simple way, but not a single one can be found when searching on Google. The answers on Stack Overflow consists of solutions where you have cases. For example, if a line-segment of one triangle is intersecting two line-segments of the other triangle we want to cut, then we need to create 2 new triangles depending on which lines are intersecting, and the solution becomes more and more complicated.

Perhaps a more elegant way is to use what we used to create a Voronoi diagram: the Delaunay triangulation. But in this case we force the triangulation to include some triangles we want to cut from the triangulation, and we get a Constrained Delaunay triangulation, which looks like this:

You can also use the Constrained Delaunay triangulation if you for example want to make a navigation mesh for your game.