April 23, 2016

I've made myself a swarm

"So you've made yourself a swarm," you say. "But what's a swarm?" A swarm is an algorithm for producing natural-looking movement in large swarms of creatures. Another similar algorithm to use in similar situations is Craig Reynold's flocking algorithm. But the flocking algorithm is computationally expensive, so a swarm is a better alternative if you don't need accuracy, but a convincing organic movement of hundreds of creatures. The swarm I've made can easily run smoothly with 500 creatures.

The creatures can both run on the ground and fly, and you can include animations. When you zoom in you can see that the spiders's legs are moving and it's not decreasing the performance. If the creatures reach an obstacle they can climb (or fly a little higher), and when they reach the end of the obstacle they fall down. The climbing part is not yet that great because sometimes they will climb up but not always with the correct angle. But that's a later problem! They can also reach obstacles that can't be climbed and in that case they just turn around 180 degrees.

The creatures are running towards you, and when they reach you they slow down and begin to circle your position while trying to attack you.

It's also super-easy to reverse the roles: they hunter becomes the hunted. With a single button you can make it so the creatures disperse and run away from you.

They will also run away if they are injured, like if they touch a flame, and then die after a few seconds.

So what's the secret. First of all I got the idea from the article "Simple Swarms as an Alternative to Flocking" by Tom Scutt. You can find it in the book AI Game Programming Wisdom. But the basic idea is simple: use randomness:
  • The creatures have random top speed, which is how they spread out
  • The creatures have each a different random turn speed they can turn with
  • The creatures are using more randomness make their paths less straight and more natural-looking

Looks interesting? You can test it here: Swarm Algorithm.

April 19, 2016

Lessons learned from 10 game postmortems every developer should read

Even though computer games might look simple, they are extremely hard to design. A book I read summarized this perfectly when it described a computer game as a combination of everything. You have to be a psychologist to understand your users, you have to be an engineer to meet the technical demands, you have to be a designer to make the game pretty, you have to be an architect to design realistic environments, and so on.

A good way to improve your skills is to study what other developers have learned. I've already studied the game Antichamber: Breaking down the seven-year development of Antichamber by Alexander Bruce, and Chess: Why is Chess so popular? But now I've found an article called 10 seminal game postmortems every developer should read. It links to 10 other articles where game developers are summarizing what they learned when they developed their games. This will be a summary of the most important lessons learned:

1. Deus Ex
  • Don't give up your ideas. If there's a game you really want to make, don't give up on it. Someone will be foolish enough to give you the money eventually.
  • Follow the rules of role-playing, including: 
    • It's not fun to watch an NPC do something cool. If it's a cool thing, let the player do it.
    • If there's no need to look up and down - constantly - make a 2D game!
  • You have to be willing to change your thinking and goals. Part of the challenge of the game development process is making the tough decisions along the way, leading to many difficult junctures when you have to determine that something that can't be done right in the game shouldn't be done at all. These questions are knotty and solutions are far from obvious. To answer these questions you should:
    • Build a "proto-mission." This is the first implemented mission, playable start to finish, and it should capture everything you want your game to be. Get this mission working as early as possible, so you can see all the things you thought would work that didn't. For example, they thought the real world would be interesting as a gaming environment. But the answer was a tough-to-swallow "not very." So decided to not use the real world.
    • Have an early milestone. When you have reached this milestone you will understand the elements that really make the game work. They could go through their 500-page design document and cut everything that was extraneous, ending up with 270 pages. Less game? Not at all. What was left was the best 270 pages - the stuff that worked. If you wait until a few months to go before the ship date, it will be much more difficult to make changes.
  • By licensing technology, you will not always save time. You'd think cutting a year or more of engine-creation off a schedule would result in an earlier release date. On Deus Ex, that didn't prove to be the case. Time that would have been lost creating tools was lost instead to learning the limitations and capabilities of "foreign" technology.
  • Know your limitations. Always work within the limits of your technology rather than trying to make your technology do things it wasn't meant to do. Big budgets, lots of time, and freedom from creative constraints are seductive traps. Don't fall into them. Don't settle for less than greatness, but don't think too big. Balance should be the goal.

  • Using your own game engine is both good and bad. The engine exposed them to bugs that another team introduced (who used the same engine in their game), but it also gave them the ability to fix bugs and add new features to the engine. It allowed them to change it to support the game's specific features in ways that a general engine never could.
  • Know your limitations. They first analyzed the game engine's technological capabilities and then they decided on a design that would work with it. This process is almost mandatory when reusing an engine. Many of the times when they did deviate from this rule they had problems.
  • Finish the game on time. They focused on moving forward, and they didn't allow themselves to be bogged down because they desperately wanted to ship a game. While there are features in System Shock 2 that could have been better if they had not rushed them, they still believe that the game as a whole was made better by their resolve to finish it on time.
  • If you don't have the resources, use simple, reusable game-play elements. When you throw together many such systems, you end up with a lot of game play. They didn't have the time, resources or technology to develop the scripted cinematic sequences used by the then popular game Half-Life.
  • Keep what's working and improve the rest. As the name of the game says, System Shock 2 was a sequel, so they identified the key elements that made the first System Shock a good game and reinterpreted those elements using current technology.
  • Understand that running a business while participating in the development process of the game will be difficult. Neither of the founders started the company to be businessmen - they wanted to make a game. But you also have to make payroll, organize taxes and expense reports, and participate in business negotiations and contract disputes. So they decided to work harder, which destroyed their personal lives, even though they still devoted less time than they desired to every aspect of their work.

3. Diablo II
  • Provide a constant source of simple pleasures. Offer a steady stream of goals and accomplishments, and try to make every single action fun:
    • Players continually kill monsters and get rewarded with treasure and experience
    • There's always a quest that's almost finished, a waypoint almost reached, an experience level almost achieved, and a dungeon nearly cleared out 
    • Moving around inventory items produces pleasing sounds 
    • Monsters die in spectacular fashion, like piñatas exploding in a shower of goodies
  • Randomness is your friend. Use randomly generated levels, monsters, and treasure. The player will more likely replay the game, but randomness also makes each player's game his or her own. They will tell their friends about what they have just done in the game, knowing for sure that their friends have not done the same thing.
  • The game should be easy to play. They used the "Mom test:" could Mom figure this out without reading a manual? Many games have different controls and key combination for all different actions when simpler is always better.
  • Make the game playable as soon as possible. Their initial priority was to get a guy moving around on the screen and hacking monsters. This is what players would be doing most of the time, so it had to be fun. For example, they realized that players would be killing large amounts of the same monsters, so they could plan for multiple death sounds and monster animations. If they hadn't experienced the core gameplay as early as they did, combat would have ended up feeling more repetitive.
  • Be the audience. You should like the game you are making. If after two years of making it (while playing it), and you are not bored to death, the game is clearly going to be a winner.
  • But randomness is also your enemy. Testing a game with randomness is not an easy task. The QA team created a web-based bug-reporting database through which they categorized and tracked all bugs, balance issues, and gameplay suggestions. In the end, this list included more than 8,300 issues and suggestions.
  • Make it easy to upgrade the game. Diablo II got criticism for having outdated graphics. When they began producing art for the game they had to use a specific graphics system. But when they released the game, the graphics was outdated. "We probably should have built in a scaling technology to take advantage of hardware that could display the same graphics at higher resolutions."

4. Thief: The Dark Project
  • Make it as easy as possible for everyone to contribute. Their goal was to create a set of tools that enabled programmers, artists, and designers to work more effectively and independently. Non-programmers should have a high degree of control over the integration of their work, without requiring the direct involvement of programmers. Designers with moderate programming skills should be able to create complex object behaviors.
  • Focus, focus, focus. Their original plan was full of features, including various multiplayer modes. But they discarded these ideas to instead focus on creating a single-player, linear, mission-based game centered exclusively around stealth.
  • Solve major problems as fast as you can. The game had problems with the AI, which was a core part of the game, but they didn't act fast enough. They had to throw away 80 percent of the AI code, and after a 12-week stretch the AI was ready for real testing.

  • When developing a sequel you are measured differently. You have to make the game better, and not just to make the same game over again. To do that you need a mechanism to quantify your previous mistakes and learn from them. If you don't figure out what you did wrong last time, you're not likely to fix it the second time around. They used post-project reviews to analyze both the strong and weak development areas of their earlier projects, and they also asked the fans what they wanted to see in the next game.
  • Use design guidelines. To make everyone work against the same goal, use a set of design guidelines, like "The player must always feel as if it is HIS actions that are making him succeed. He should feel that through his smart decisions and actions that he has solved a puzzle or battle." You can see their entire list here. But these are only guidelines - and not the law!
  • Don't forget your fans and the game after you have completed it. One of the most important things they have learned in their years in the industry is how important it is to support the fans that buy their games. This means first shipping a bug-free product, and second being completely available to help people that are having trouble with the game: on message boards, via contact emails, and everywhere else. What's the point of making games if you can't make sure people can play it - and who's better to work through technical issues than the people who made the game?

  • Do more with less. It doesn't take 50 people to create a major cross-platform software title. For example, they had no big quality assurance department because the public did the testing for them, and they listened to them as seriously as if they were coworkers on the project.

  • An update can become a real game. After the original Unreal was completed, they wanted to update the game with a multiplayer mode. But as the feature list grew and patches to Unreal were released, the add-on turned into a complete and independent game.
  • Use the community. They held polls on popular Unreal message boards to decide what to add or remove. The results of these polls were taken into consideration when the feature in question was implemented. But they also read the discussions of the fans of their lead competitor's game Quake III. 
  • Don't always use the community. The hardcore community is very vocal, but small. Designing a game to appeal to that community alone is a mistake. When they designed tutorials, they tested them on the parents and grandparents of team members to demonstrate that the tutorials were useful for attracting and keeping new players.

8. Age of Empires II: Age of Kings
  • Don't make any bold promises. Their original plan was to finish the game in a year, which failed, and it didn't make the publisher Microsoft happy. But they managed to save the day by making an expansion for the original Age of Empires. 
  • Take care of your employees. Crunch time is a period where you realize you have f*cked up so you have to work really hard (sometimes for months) to finish the project. But your social life will suffer. They solved this by scheduling crunch time well in advance at multiple points in the development process. The hours were 10 a.m. to midnight, Monday through Friday, with Wednesday nights ending at 7 p.m. so they could go home to their families. They had weekends off and meals were provided during the week.
  • Monitor your play-testers. They discovered that a play-tester had turned cheats on, playing to win not to test, in almost every game for over a month, which invalidated all the feedback from that group for the prior two months.
  • With success comes a responsibility to behave appropriately. Nothing lasts forever (the company shut down in 2008). Behaving in an exemplary manner and being friends with the industry at large is far more important than chest-beating about your current success.

9. Rainbow Six
  • A good license won't help a bad game. But it can give a good game the visibility it needs to be a breakout title. 
  • Rely on proven technology. Their external unproven solutions for rendering and networking both fell through and had to be replaced with internally developed code late in the development cycle.

  • Begin small. A core team of about six was formed, and at the start of Lionhead they worked in Peter Molyneux's own house. 
  • Take risks. At the time they started, you couldn't have done what they did. No-one knew if the graphics could run on the computers, no-one knew if the AI would work.
  • Everyone has bugs. At one point they had 3000 bugs, and for each bug they fixed, three more appeared.  

April 4, 2016

Hardcore pathfinding for self-driving cars

What if you have a car and want to find the shortest route from point A to point B. A normal car can't turn around its own axis 360 degrees like a tank can, so you have to come up with another solution that takes the wheels into account. One solution is called Hybrid A star, which is a modification of the classic A star algorithm. It looks like this:

The yellow lines in the image above are the possible paths if the car is driving forward and the blue lines are the possible paths if the car is reversing. If you want more details about the Hybrid A star pathfinding algorithm, I've written a more detailed description here: Explaining the Hybrid A Star pathfinding algorithm for selfdriving cars. But the problem with Hybrid A star is that it doesn't care about the final orientation of the car. So if you want to make sure that your car is ending up at a position with a certain heading, then you need to modify Hybrid A star. 

There are two common ways to modify the algorithm so you end up at a position with a certain heading: Dubins paths and Reeds-Shepp paths. Both paths types are very similar and the basic idea is that you get the shortest path by trying different combinations of circles and straight lines between circles. 

The main difference between Dubins paths and Reeds-Shepp paths is that a car following a Dubins path can just drive forward. The final 6 paths looks like this:

Depending on the position of the cars, you may end up with fewer than 6 Dubins paths. It is possible to modify these 6 Dubins paths so the car can also reverse, which is just a matter of mirroring the calculations. You will then end up with something like this, where the white line is forward and the gray line is reverse:

You can actually add these 12 paths to Hybrid A star and get a solution where Hybrid A star will (sometimes) end up at the desired position and heading. So when you expand the search tree you can test if a fixed path solution is available by testing if the car can drive the entire path and not collide with an obstacle. It will be way too slow to test it when you expand each branch so make sure to test it every x branch and test it more often when you are closer to the goal. It will not always work because an obstacle may be in the way, but it's a better solution than the solution we had before. If you want to learn how to make Dubins paths, I've written a tutorial on how to do it: How to make Dubins paths in Unity with C# code.

If you want to be really hardcore, you can modify the Dubins paths and end up with the Reeds-Shepp paths. Instead of just 12 paths (or 6 if you just use the standard Dubins paths) you will now have no less than 36 paths to calculate. The good thing is that if you have already calculated the 6 Dubins paths, you will know how to calculate the first 20 paths. And I argue that knowing these 20 paths may be enough, and adding more paths will just take longer time and speed of the algorithm is here more important than necessarily finding the shortest path. One of these paths is looking like this:

If you want to test the final self-driving car, you can test it here: A self-driving car finding its way through a maze.

February 4, 2016

Alan Turing on Artificial Intelligence


Alan Turing (1912-1954) was a brilliant man who is most famous for his work with cryptography during the Second World War. According to the movie The Imitation Game, he and the other cryptographers shortened the war with two years, saving more than 14 million lives. But the movie is a very simplified version of Alan Turing's life, and if you want to learn more about him you should read the biography Alan Turing - The Enigma by Andrew Hodges. 

I believe Alan Turing - The Enigma is the most famous biography about Alan Turing. Among other things, you will learn that during the war Alan Turing decided to buy silver bars and hide them beneath the ground in case the Germans invaded Britain. After the war, Alan Turing and a friend tried to find the silver bars. He sort of knew where they were hidden and they also brought a metal detector, so the dug some holes, but they couldn't find them. So if you by chance find some hidden silver bars near Shenley in England, they might be Alan Turing's lost silver bars.

While not hiding silver bars or solving German codes, Alan Turing was thinking about artificial intelligence, and he is widely considered to be the father of artificial intelligence. Within the field, Alan Turing is most famous for developing the so-called Turing test

The basic idea behind the Turing test is to figure out if an artificial intelligence is really intelligent. If you have seen the movie Ex Machina, you have seen that the creator of the robot Ava wants the main character in the movie to administer a Turing test to see if the robot really is intelligent. The movie is fiction, but there are reports that a computer program called Eugene Goostman, which simulates a 13-year-old boy, has passed the Turing test. So the test is limited because the chatbot is not intelligent. But Alan Turing developed the test at least 60 years ago, so we can't blame him. What we need is an updated Turing test. Some have suggested that a better idea is to test the ability of an AI to predict which is really what our brain is doing (according to some theories). 

Speaking of brains, as the Second World War ended Alan Turing told a friend that he wanted "to build a brain." That was not an easy task in 1945 - even in 2016 we are not really sure how the brain really works. For example, we have no clue why we have to sleep. There are theories, but no facts why we actually have to spend one third of our lives in bed. 

It's unclear how much Alan Turing knew about the physiology of the human brain. The brain cell itself, which is called a neuron, was discovered in the 19th century. But it wasn't until 1952 that Alan Lloyd Hodgkin and Andrew Huxley presented the now famous Hodgkin–Huxley model, which is a mathematical model for transmission of electrical signals in neurons. 

Alan Turing, who was a mathematician, would have liked the Hodgkin–Huxley model as it consists of several differential equations, but is is unclear if he ever saw it (he was working with something called morphogenesis, which is how spots appear on animals, when the report came out). He died two years after the model was finished. But the same scientists who developed the Hodgkin–Huxley model had in 1939 published a paper how they had recorded action potentials from inside a nerve fibre. So even though neuroscience wasn't as popular as it is today, there were pieces and theories Alan Turing could have used.

But according to his biography:
"He would have seen pictures of nerve cells, but at the level at which he was approaching the description of mind, the details were not important. In speaking of building a brain he did not mean the components of a brain, or that their connections should imitate the manner in which the regions of the brain were connected. That the brain stored words, pictures, skills in some definite way, connected with input signals from the senses and output signals to the muscles, was almost all he needed."

Alan Turing's idea to build a brain was to write "instruction notes" and see whether a machine could behave like a brain in developing "thinking spots" for itself. He wanted to show that a machine could learn. The problem was that he didn't have a machine to experiment with - the computers we have today would have helped him but they didn't exist back then.

The brain he wanted to build was a universal machine that would be all machines. In 1944, Alan Turing said that he had plans for "the construction of a universal machine and of the service such a machine might render to psychology in the study of the human brain." 

Once, Alan Turing held a speech about his plans for building a brain. He said: "No, I'm not interested in developing a powerful brain. All I'm after is just a mediocre brain, something like the President of the American Telephone and Telegraph Company." This was while he was in US and had consulted the American Telephone and Telegraph Company and was apparently not satisfied with the situation. He then continued to explain how he wanted to feed the brain with facts on prices of commodities and stock, and then ask the machine the question: "Do I buy or sell?" 

To develop an artificial brain, Alan Turing argued that it would be possible to start with an unorganized machine. It could be made up in a random way, like the neurons in a child's brain are, and then teach it how to behave:
"...by applying appropriate interference, mimicking education, we should hope to modify the machine until it could be relied on to produce definite reactions to certain commands." 
But he also argued that it will not be possible to apply the exact same teaching process to the machine as to a human child. It will not be possible to send the machine to school. And neither had he plans to make an exact replica of a human:
"I certainly hope and believe that no great efforts will be put into making machines with the most distinctively human, but non-intellectual characteristics, such as the shape of the human body. ...their results would have something like the unpleasant quality of artificial flowers. Attempts to produce a thinking machine seem to me to be in a different category."

So to sum up, Alan Turing was aiming for something similar to the smart operating system from the movie Her:

...and not the smart robots from the movie Ex Machina:

December 28, 2015

Nikola Tesla on Artificial Intelligence


Nikola Tesla (1856 - 1943) was an inventor born in Croatia, and is best known for his contributions to the design of the modern alternating current (AC) electricity supply system. He was also very bright, which was a problem because he could design his machines in his head so he didn't always build the final product. And if you don't build the final product and sell it, then you will not make much money. So Tesla came up with these brilliant machines, but he still had to borrow money to survive. 

Tesla has also given his name to the electric car company Tesla Motors. One of the founders of that company, JB Straubel, was a fan of Nikola Tesla (but it wasn't he who gave the company its name), and his favorite book about the man is Wizard: The Life and Times of Nikola Tesla by Marc Seifer. I finished reading that book and learned, among other things, that one of the reasons Tesla could accomplish so much was that he was ambitious. This is very similar to Albert Einstein, who could also dedicate his life to whatever he was doing.  

When Tesla was a young student, his teachers were worried about him. The reason was that he had "a veritable mania for finishing whatever I began." So he couldn't simply stop himself from doing whatever he was doing. If he began reading a book he couldn't do anything else before he had finished it. So the teachers said that "the boy was at risk of injuring his health by obsessively long and intense hours of study." He could study for 20 hours a day. 

Tesla would move to the US together with his ambitions. He could experiment day and night, holidays not except. He drove himself until he collapsed, working around the clock, with few breaks. He preferred working through the night, when distractions could be minimized and concentration could be intensified. He argued that "every hour, every moment, that was not spent working on inventions was time away from his purpose." Even the intervals spent eating and sleeping delayed progress, so he reduced his sleeping to a minimum and his eating to the bare necessities. He argued he could sleep 2 hours per day while "dozing" from time to time to recharge his batteries. He said:
I get all the nourishment I require from my laboratory. I know I am completely worn out, and yet I cannot stop my work. These experiments of mine are so important, so beautiful, so fascinating, that I can hardly tear myself away from them to eat, and when I try to sleep I think about them constantly.

One other thing I learned from the book was that Tesla was also interested in Artificial Intelligence. The young Tesla studied the theories of René Descartes, who envisioned animals, including man, as simply "automata incapable of actions other than those characteristic of a machine." Tesla said that he wanted "to devise mechanical means for doing away with needless tasks of physical labor so that humans could spend more time in creative endeavors." When Tesla was asked to predict the future he said that robots and thinking machines will replace humans. His vision was that machines could liberate the worker and that fighting machines could replace soldiers on the field.

Tesla had come to see the human body in its essence as a machine. He said that memory "is but increased responsiveness to repeated stimuli." It's unclear if he actually tried to build a machine similar to himself, but he was thinking about it:
Long ago I conceived the idea of constructing an automaton which would mechanically represent me, and which would respond, as I do myself, but of course, in a much more primitive manner to external influences. Such an automaton evidently had to have motive power, organs for locomotion, directive organs and one or more sensitive organs so adapted as to be excited by external stimuli. Whether the automaton be of flesh and bone, or of wood or steel, it mattered little, provided it could provide all the duties required of it like an intelligent being.

But what is known is that Tesla built a remote controlled boat. To him, his boat was not simply a machine, it was "a new technological creation endowed with the ability to think." It was also, to him, the first non-biological life-form on the planet, arguing that life-forms need not be made out of flesh and blood. He said:
Even matter called inorganic, believed to be dead, responds to irritants and gives unmistakable evidence of a living principle within.