April 23, 2016

I've made myself a swarm

0 comments
"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

0 comments
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

0 comments
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.