October 28, 2016

If you read one article about Rectangle-Rectangle Intersections read this one


I've made an autonomous traffic intersection in which self-driving cars can find their way through the intersection faster than if the intersection had traffic lights. How much faster you might ask? The answer is about 10 seconds according to my simulations. The problem is that if you add pedestrians and bikes to the equation, everything will break down, but that's a later problem!

To be able to know if a self-driving car can drive through the intersection without colliding with another car, you approximate each car with a slightly larger rectangle (to be on the safe side) and then you predict where the rectangle will be in the future with your favorite integration method. Each integration step you test if the (pink) rectangle is intersecting with any of the other (pink) rectangles. It looks like this:

Using a fast rectangle-rectangle intersection method is important to make the algorithm as fast as possible. But how can you find out if two rectangles with orientation in 2d space are colliding? The first idea I had was to divide the rectangles into two triangles and then detect if any of the four triangles are intersecting. If you google 2d triangle-triangle intersection, you will find that one way of doing this is:
  1. Approximate the triangles with rectangles and check if they intersect with an AABB-AABB intersection algorithm. These approximated rectangles have no rotation (they are called OBB if they have rotation) so you can't use this algorithm to solve the main problem, but you can use it to speed up the algorithm.
  2. If the approximated AABB rectangles are intersecting, then test if any of the edges of each triangle is intersecting with any of the edges of the other triangle with a line segment-line segment intersection algorithm.
  3. If the above fails, but the approximated rectangles are intersecting according to the first test, it means that one of the triangles could be inside the other triangle. To find out if that is true, you test if one of the corners of the triangle is inside the other triangle (and vice versa) with a point-in-triangle intersection algorithm
If the above sounds complicated I've written a more detailed explanation (with C# code in Unity) here: Are two triangles in 2D space intersecting? And maybe this image explains it better:

The problem with testing if two rectangles are intersecting by using the triangle-triangle intersection algorithm is that you maybe have to do the above four times. What if there is a better way? One other way to test if two rectangles are intersecting is using the Separating Axis Theorem, or SAT

SAT is a little bit more difficult to understand, but when you have understood the basic ideas (and have repeated both the dot product and vector projections), you will be able to apply the intersection algorithm to all convex polygons. So it's possible to test if both triangles and rectangles are intersecting with SAT, because a rectangle is a polygon with four sides. If you want a more detailed explanation of the SAT algorithm, I've written a longer article here: Are two rectangles with orientation in 2D space intersecting?

But what I found is that even though SAT includes fewer steps, it's actually slower. The reason is that the triangle-triangle intersection algorithm doesn't always need to go through all steps to see if the triangles are intersecting. So an important lesson is to take out your timer and test how fast each algorithm is. But as today's Momentum quote said: "Live as if you were to die tomorrow. Learn as if you were to live forever" at least I've learned something new!

October 22, 2016

No more red traffic lights!


Waiting for a traffic light turning green is never fun! But what if there was a world without any traffic lights? Well, when all cars on our roads are self-driving then it's possible to create an intersection without any traffic lights. This idea is called Autonomous Intersection Management. The basic idea I've used here originates from the report A Multiagent Approach to Autonomous Intersection Management. The authors of the report released this video so that's what we are aiming for here:

But the version you can test here is more complicated as each car is simulated in Unity, which makes it more realistic, so a car is not just a mathematical model of a car as they are in the report mentioned above. So each car in my simulation has an engine torque, braking torque, realistic wheels, drag force, and much more. This makes it much more difficult to simulate future positions of the car, which we have to do to check for collisions in the intersection.

The basic idea is that each car knows where it is going, such as driving forward or turning left, so it has a path through the intersection with waypoints. It can't change lane, and it can drive forward and turn left in one lane and drive forward and turn right in the other lane. To get a smooth curve between the waypoints I used a spline interpolation method called Bezier curve. The intersection looks like this:

When the car is close to the intersection, the intersection checks if the path through the intersection is clear by using the car's velocity and acceleration. To simulate the future positions of the car, I approximate each car with a rectangle and then I'm using an integration method called Forward Euler. At each integration step, I check for rectangle-rectangle collision with the other rectangles that are stored at this future time step which are approximations of other cars. This is happening until the car is outside of the intersection. The rectangles are also a little bit larger than the car to be on the safe side:

If the first car that has arrived to the intersection can't find a clear path, the intersection checks if next car in the queue can find a clear path, and so on until there are no-more cars to check. The problem now is that the first car in the queue might wait for a path for an infinite amount of time. To solve this, there's a timer saying that if the first car in the queue has waited for 10 seconds, then the intersection should prioritize this car until it finds a path through the intersection.

But what if an emergency vehicle arrives? In that case the intersection will prioritize all cars in the same lane as the emergency vehicle until the emergency vehicle has entered the intersection. It will at the same time prioritize all cars in the lane next to the lane the emergency vehicle is in, because those lanes will never cross in the intersection.

The simulation is not yet 100 percent good, so some collisions will happen, but that's just a matter of fine-tuning all the parameters. Anyway, the version described above looks like this:

But is an autonomous traffic intersection faster than traffic lights? It's easy to add traffic lights to the simulation and then calculate the average time it takes for a car to drive through the intersection. According to my studies, the average time it takes a car to drive through an intersection with traffic lights is about 1 minute. You can compare this with the average time it takes a car to drive though an autonomous traffic intersection, which was about 50 seconds.

Looks interesting? You can test it here: Automatic traffic intersection.

October 18, 2016

Why Gamification Beats Peanut Butter on Pancakes

The 21-day Gamification Course is a free e-mail course by Yu-kai Chou, who has written the book Actionable Gamification. But what on earth is gamification? According to Wikipedia, gamification is:
...the application of game-design elements and game principles in non-game contexts to improve user engagement, organizational productivity, flow, learning, crowd-sourcing, employee recruitment and evaluation, ease of use and usefulness of systems, physical exercise, traffic violations, and voter apathy, among others. A review of research on gamification shows that a majority of studies on gamification find positive effects from gamification. However, individual and contextual differences exist.

If you are making a game it's obviously a good idea to understand the game-design elements and game principles. But if you are not making a game, you may also need to apply the ideas behind gamification. Last year I read the book Superbetter, which is promising to give you a framework so you can apply the ideas behind gamification to improve your own life. The book says: "Playing SuperBetter for 30 days improves mood, reduces symptoms of anxiety & depression and increases belief in the ability to successfully achieve goals."

One of the interesting ideas from the book Superbetter is what you should do if you have experienced a traumatic event. If you, within a few hours after that event, play a game like Tetris, then you will minimize the risk of getting post-traumatic stress from the traumatic event. So as in Wikipedia's definition, gamification can be applied to many more areas than just traditional games. With that in mind, let's learn more about gamification.


Gamification is the art of stealing all the fun and addicting elements found in games and applying them to real-world or productive activities. But why is it called gamification if it can be applied to so many other areas? The reason is that the game industry was the first to focus on human-focused design because games have no other purpose than to please the user playing the game. This is actually not entirely true because there are games with a purpose other than to be fun, such as a game helping victims with burn injuries heal their wounds, but you get the idea.

Human-focused design is a design process which is trying to optimize for the human in the system and not the efficiency of the system. You can compare it with the iPhone, which didn't have a stylus because Steve Jobs focused on the human and not the technology, which is called function-focused design. Games have to focus on the human because a game is not a game if not a human is playing it. But if you are building something else, like a nuclear reactor, then you can focus on designing an efficient system.

The game industry might not be old, but it has spent a lot of time to master motivation and engagement, so you can now learn something from games, such as why the game World of Warcraft is addicting? I personally had a classmate who disappeared from school because he became addicted to World of Warcraft. What if there was a way to make school as fun as games? This is what you will learn here!

You can argue that it is the challenges and limitations, such as rules and obstacles, that makes a game fun. A game like soccer has a challenge (win the game against the opposing team) and limitations (you can only kick the ball with your feet), but everyone, including me, doesn't enjoy playing soccer. So a game needs more than just challenges and limitations to be fun.

Why do you want to do something?

Why do you like to play soccer, and why do I hate to play soccer? There are 8 fundamental reasons (called core drives, or CD) why you and me want to do something:
  1. Meaning. You want to do something because you feel it has a purpose.
  2. Accomplishment. You want to do something to overcome challenges.
  3. Empowerment. You want to do something because you like to be creative and test different strategies.
  4. Ownership. You want to do something if you feel like you own what you are doing.
  5. Social influence. You want to do something because other people around you are doing it. 
  6. Scarcity. You want to do something now because you think the opportunity may be lost if you are not doing it now.
  7. Unpredictability. You want to do something because you want to see what's happening after you have done it. 
  8. Avoidance. You want to do something to avoid something negative happening if you are not doing it. 
The difference between these core drives is not always clear! For example, being part of an exclusive shopping network is:
  • 1. Meaning - You want to be a part of the elite.
  • 2. Accomplishment - You made it into the club.
  • 4. Ownership - You get to buy the best stuff!
  • 5. Social influence - Now your friends are jealous of you.
  • 6. Scarcity - You are part of this 1 percent ultra exclusive club!

A summary of each core drive

1. Meaning. You believe you are doing something greater than yourself or that you were "chosen" to do something important. Examples:
  • Spend your spare time updating Wikipedia. You believe that by updating Wikipedia your work will affect millions of people around the world in a positive way.
  • Being a member of a limited network, such as "an exclusive, member-based online shopping site for clothing and accessories, which runs time-limited sales which can only be viewed by its members." 

2. Accomplishment. You have an internal drive to make progress, develop skills, and overcome challenges. This is the core drive that is the easiest to design for because you can simply add leaderboards, points, and trophies. But don't forget the challenge, because you don't want to get rewards for free. Examples:
  • I wrote a book about Elon Musk (the challenge) and my "leaderboards, points, and trophies" is the book's Goodreads rating. Each time I get a good rating I feel proud and sometimes I take a print-screen of the rating and attach it to a tweet.
  • When you buy something on the auction site eBay, you feel that you won. So even though you might have paid more compared to what you initially wanted to pay, you feel that you won against the other guy who were bidding against you.  

3. Empowerment. You need ways to express your creativity by repeatedly trying to figure things out and try different combinations. This makes you feel good and you take action because you find the action enjoyable on its own. You also need to be able to see the result of your creativity by receiving feedback so you can improve what you have done. Examples:
  • The game Minecraft is popular because you can be creative in it and do whatever you want. Other people can join the map and give you criticism, but you can also give yourself criticism because you see what you've created.   
  • Websites that let you play around with your personal economy so you can test different strategies. What's happening if you invest 20 percent in stocks and save 30 percent in your savings account?   

4. Ownership. You are motivated when you feel like you own something, and you want to make what you own better. Besides being the major core drive for wanting to accumulate wealth, this deals with many virtual goods or virtual currencies. If you in a game spend a lot of time to customize your profile or avatar, you automatically feel more ownership towards it. This is also the core drive that makes collecting stamps or puzzle pieces fun (for some). Examples:
  • In Pokemon the player has to catch all Pokemons.
  • McDonald's had a physical game where you had the chance to get a piece of the game when you bought a hamburger. When you accumulated all the pieces McDonald's gave you a reward. 
  • You've spent a lot of time writing blog posts on your blog (you now own it) and you want to improve it by increasing the number of readers.

5. Social Influence. This drive incorporates all the social elements that drives you, such as mentorship, acceptance, social responses, companionship, competition, and envy. When you see a friend who is amazing at some skill or owns something you also want to own, you become driven to reach the same level. This also includes your drive to draw closer to people, places, or events that you can relate to. If you see a product that reminds you of your childhood, the sense of nostalgia would likely increase the odds of you buying the product. Examples:
  • The online game Parallel Kingdom has mentors that spend time with you when you've just started the game. They give you items and a push in the right direction. Players who get help tell themselves: "I can't possibly quit this game now and let my mentor down. He/she just gave me his valuable items! I can't let his/her effort go to waste." So they continue playing because someone else has done a favor for them. 
  • A hotel wanted to persuade their guests to reuse their towels, so they tested two different signs: "Please help us save the environment by reusing your towel," and "80 percent of the guests that stayed in this room reused their towels." It turned out that the second sign was most effective because we humans tend to do what other humans do. If you are told other people are reusing their towels, then you will also reuse them.  

6. Scarcity. This is the drive of wanting something because you can't have it and you want it immediately. Many games can say "come back in 2 hours later to get your reward." The fact that you can't get something right now motivates you to think about it all day long, so you might pay to have it at once. Examples:
  • Facebook started at a small scale for just Harvard students. When Facebook opened up to everyone, you wanted to join because you previously couldn't.
  • Until the mid 20th century, diamond engagement rings were a small and dying industry in America. But then someone came up with the idea to restrict the supply of diamonds to make them a status symbol. The diamonds themselves aren't actually that rare.
  • The game Candy Crush gives you the opportunity to either pay to get something now or wait sometime. Some pay because they want it immediately. 
  • You are more motivated to buy a product with a limited edition, even though you don't know how many "limited" is. 100 products? 1 million products? It doesn't matter to you! 

7. Unpredictability. You want to know what's happening next. If you don't, your brain is engaged and you think about all the time. This is why you watch movies or read books. However, this drive is also the primary factor behind gambling addiction. There are experiments showing how rats continuously press a lever because of unpredictable rewards. What if the next press will result in cheese? Examples:
  • What if the next lottery ticket will make you rich?
  • What if the famous person on Twitter is finally replying to your tweets?

8. Avoidance. This core drive is based upon the avoidance of something negative happening, such as avoiding losing previous work or avoiding admitting that everything you did up to this point was useless because you are now quitting. The problem is that you are much more likely to change your behavior to avoid a loss than to make a gain. Examples:
  • It's much harder to sell a stock if you have lost money on the stock than it is to sell a stock with a profit. This is why so many people are losing money in the stock market! What you should do is to sell the losers and hold on to the winners. 
  • When spending time on an auction on eBay you don't want to lose the auction. 

The Octalysis framework

You can summarize the 8 fundamental reasons (core drives) why you want to do something in the co-called Octalysis framework:

You can connect the different sides of the octagon to the different parts of your brain. But that's boring so let's see examples of the framework in action:



Example: Blogging

Why do you want to have a blog? As said before, there are 8 fundamental reasons (core drives) why you want to blog:
  1. Meaning. You believe that by writing articles you can help people and make the world a better place. You will also become a better writer. 
  2. Accomplishment. It's a challenge to write a blog: you have to come up with new ideas about what you are going to write, and you have to update frequently.
  3. Empowerment. By experimenting with the blog design and different types of articles you can be creative and see how many readers you can get.
  4. Ownership. You've spent a lot of time with the blog so now you feel like you own it, so you want to improve it.
  5. Social influence. It's more fun to blog when you see that people are reading the blog, and it's fun to compete with other people who are writing similar articles.  
  6. Scarcity. Writing a blog is a long-term investment. You don't know which articles will become popular, so you have to wait and see. 
  7. Unpredictability. It's fun to see which articles will become popular. 
  8. Avoidance. You measure how many people are visiting your blog and it's painful to see when the trend line is down. If the trend line is down, you want to write more articles to avoid the fact that all the hard work up to this point has been a waste of time.  

Example: Selling video games

While writing this article I read the book Game Over: How Nintendo Conquered The World. It explained how Nintendo used gamification to sell more video games:
...it was wise to market video games like movies - released cautiously, rationed so that demand outpaced availability, and then withdrawn from circulation as soon as interest began to wane. This rationing tactic, treading games like priceless objects (Scarcity), worked. After all the hyper about a new game took hold (Meaning), kids dragged their parents to stores, but outlets couldn't keep the games in stock. A kid who was absolutely dying to get "Link" [a game] would arrive at the store, only to find it sold out. Maybe he would try a few other stores without success (Empowerment and Unpredictability), but then he would buy another Nintendo game. Then, a week or month later, a new supply of "Link" would come in. The kid wanted "Link" more than ever then, and unless his were the most iron-willed of parents, they would succumb.
The Atari wave (the competing game company) had floundered in large part because of a flooded market. By design, Nintendo did not fill all of the retailers' orders, and it kept half or more of its library of games inactive.

I also suspect that the kid's friends, and those around him who had found a copy of the game, were influencing the kid to buy the game (Social influence). When the kid finally bought the game, the kid had overcome the challenge to find the game (Accomplishment and Avoidance as in not finding the game at all). Now when the kid has spent a lot of time to find the game, the kid now feels like the kid owns the game (Ownership) and will thus enjoy it more.

But why is Nintendo's share of the market today much lower than Nintendo's share of the market in the 1990s if they have figure out the secret to how to sell games? The answer is that today it's much more difficult to create a hype about a new game (Meaning) because so many good games are being produced each year. Nintendo is also doing their best to avoid creating a hype about a new game because they are preventing YouTubers from playing their games, and since many gamers are buying the games the YouTubers are playing (Social influence), no-one is buying Nintendo games.    


This was just a short summary of the 21-day Gamification Course. If you want to learn more you should take the course yourself. I learned a lot, even though I had studied the area before by reading books like Influence, Yes!, and Superbetter. So I will continue to study the area because a good product is not good unless you have users who are actually using the product. And since you can use gamification in other areas as well, such as avoiding post-traumatic stress, you now see why gamification actually beats peanut butter on pancakes. 

October 9, 2016

Why are some games fun and other games boring?


I've read the book A theory of fun for game design by Raph Koster. While the word game can include games like chess, the book has a focus on digital games, such as computer games, which the author also has worked with. Neither should you confuse game design with game theory, which is used in areas like in politics and economics, and is about how competitors make optimal choices.

Compared with many other areas, such as math, the design of digital games is a relatively new area. I think I played my first computer game in like 1995 and it was also around that time when computer games started to become mainstream. So there isn't really a complete theory of how to make digital games interesting to play, but this book is trying to develop the basics of such a theory. I've already read another similar book called The art of game design by Jesse Schell. While the latter book has far more content, you can read "A theory of fun for game design" in a weekend. But I still think you should read both books.

Game design is tricky to study because a game is a combination of many different areas. If you want to be a good game designer, you have to be an expert in cognitive psychology, computer science, environmental design, and storytelling - and that's just to name a few. To really understand why you think some games are fun and other games are boring, you need to see them from all these points of view.

The basic idea the book is trying to give the reader is that we humans are still cavemen, and that's why we like to play games. Our primitive brain is consuming patterns, such as recognizing faces. The same thing is happening when we play games because a game consists of patterns we are trying to recognize. It's when we have recognized, or learned, a new pattern that we have fun.

What's happening when we have have fun is that endorphin is released into our system, and this is always happening when we have learned something new or mastered a task in an environment where there's no pressure - not just when we play games. Why is this happening? The reason is that it's important for the survival of the human species that we learn, so our bodies reward us for it with moments of pleasure. So if you are making a game you have to make sure the player is always learning something.

This release of endorphin can make games have other purposes than just making us have fun. According to the book Game Over Press Start To Continue:
Some serious ill children in a hospital who played Nintendo required half as much pain medication as those who didn't. Television had no effect on the amount of medication required.
According to doctors, playing Nintendo games has the power to alleviate pain for two reasons. First, the intensive interaction with video games requires a degree of concentration that acts as a diversion and distraction from pain - and everything else. Secondly, the highly excited state achieved during this interaction generates a steady flow of endorphin into the bloodstream. Endorphin is the naturally occurring proteins that mask pain and cause a sense of euphoria. Nintendo playing can cause a sort of high, but so can jogging.  
To make sure the player is always learning something new you have to come up with puzzles:
  • The player wants new puzzles. What's happening when you think a game is boring to play is that you have stopped learning something new, which is the same thing as saying that you know the answers to all puzzles in the game. The easiest way to add new puzzles is to add multiplayer, which is why chess is so popular. If you play chess against a physical person then each new game is a new puzzle to solve, so chess consists of an endless amount of puzzles.
  • These puzzles should be different, but not too different. A new puzzle might force a whole new system on the brain, and often the brain doesn't like that because it doesn't like to do more work than it has to. You think this is exhausting, so you will stop playing the game. So the game designer shouldn't mix too many different types of puzzles. This is yet again why chess is popular. Each new game of chess is a new puzzle, but the difference between each new game of chess is not too different.  
  • The player has to understand the puzzles. You will not try to solve patterns and puzzles that appear as noise to you, instead you'll likely select problems you think you have a chance at solving. So if the you don't understand the puzzle, you will stop playing the game.  
  • The player must want to solve the puzzles. You and me like to learn different things and we have different experiences when we start playing the game. So everyone will not like your game, which is why you have to come up with puzzles your specific audience likes to solve. You will never be able to make a game for everyone. The puzzles you come up with should be puzzles that your audience has solved before. If we encounter a problem we've seen before, our first approach is to try the solution that has worked before, even if the circumstances aren't the same. We are lazy!

An actual image from the book

These puzzles can be everything between heaven and earth. But, as said before, we humans are still cavemen, so what we think is fun is actually training us to be better cavemen: 
  • Players like to run and shoot, which is actually teaching them to escape dangerous animals and hunt for food. 
  • Players like to cheat, which is another cavemen skill. They didn't have any rules back in the old cavemen days, so the best cheater was the one who was most likely to survive. In a battle, tricking the enemy to attack the weak point when in fact it's the strong point is a cheat, but it's the winning strategy making the cavemen survive.
  • A players who's playing the easiest level 200 times just to build up enough resources so the player can cruise through the rest of the game with little risk is the same as what the cavemen did when they stockpiled food to survive the winter.
  • Players like realism even though they are not aware of it. If we see a character in the game, which has been modeled to look like a real person, we can tell if there's something wrong with the character. If the character is not 100 percent realistic, our primate brain thinks the character may be sick, so our primate brain is telling us to stay away from the character which is why we don't like it. This is why so many movies featuring animated "realistic" characters has failed. The same is true for physics. It has been shown that in games considered to have the "best controls" shared an important characteristic: When you hit the jump button, the character spent almost the same amount of time in the air.   

So the basic idea behind a digital game is easy. The book argues that to test if a game is fun to play, the best test is to play the game without any graphics, music, story, etc. If that's fun, then everything else will improve the game. Some game developers tend to add a story to a boring game, but we don't play games because of stories, so most players tend to skip the story or quit the game if the player can't skip the story. Graphics is important, but as we have seen with games like Minecraft, graphics is not what makes a game a fun game. Finally, the book argues that a game should provide the player insights into the player itself.  

If you don't want to read the book, or if you read the first version of the book, or if you are just bored, the author made a video presentation called A theory of fun 10 years later

October 4, 2016

The most boring article about curves you'll ever read

I'm using Paint.net as my main painting program. It may not be as good as Photoshop, but it's free and far better than what is delivered with Windows. If you want to make a curve in Paint.net you have two options: Cubic Spline or Bézier Curve. Both curve types are almost the same, but just almost. But have you ever wondered how the computer is creating those curves? The answer is interpolation.

This summer I read a book called Essential Mathematics for Games and Interactive Applications and it included an entire chapter on interpolation. If you want to connect two points with a curve you need to do what the game Mafia did: learn interpolation:

If you want to build curvy roads you have to do what the game Cities: Skylines did: learn interpolation:

Interpolation is actually a big topic within math. You can define interpolation as "a method of constructing new data points within the range of a discrete set of known data points." The easiest form of interpolation is linear interpolation, where you follow a straight line from A to B (the known data points).

But curves are more interesting than straight lines. I recently had the need to connect two points with a curve, so I was forced to learn everything about interpolation. If you want to connect two points with a curve you have two main options:
  1. Generate a Catmull-Rom spline. You should use this alternative if you want to control the shape of the curve by moving the points that make up the curve. I suspect that this is the method Paint.net is using to generate a cubic spline because a Catmull-Rom spline is a cubic spline. 
  2. Generate a Bezier Curve. You should use this alternative if you want to control the shape of the curve even though the points that make up the curve are fixed. If you use this curve you get two handles that you can move around to determine the shape. This curve type was developed to make aerodynamic car bodies.   

Both of these curve types are actually quite easy to generate. To generate the Bezier curve you just have to make a few linear interpolations between the end points and control points. The problem is to move along the curves. What's happening when you generate these curves is that the derivative is not constant, with the result that the step size is not constant. You move along the curves with a parameter called t. This t is between 0 and 1, where t is 0 at the start of the curve and t is 1 at the end. But because the derivative is not always constant, 0.5 is not necessarily at the middle of the curve. This is the result if you have a Bezier curve (you can see that the lines at the beginning of the curve are longer than the lines as the end of the curve):

To solve this problem you have to go to your bookshelf, find the book you used when you studied numerical methods, dust it off, and repeat both Simpson's rule and Newton's method. It was about 12 years since I used that book, so it was really dusty. Anyway, if you use those methods, you will be able to generate a Bezier curve with constant steps (to generate a Catmull-Rom spline with constant steps you follow the same procedure):

If all this sounds complicated, I've written a tutorial on how to do it: Everything about interpolation in Unity with C# code.