Saturday, March 30, 2013

Postmortem: Building Hard-shell Hockey with NME

NME postmortem
After finally creating my first game with NME and publishing it to the Android store, I thought I would share my experience so far.

To begin, I should explain what NME is and what it can do since I have only given it a brief mention before.
According to the official site NME is:
“The best way to build cross-platform 2D games or rich applications.”
“Using the innovative Haxe language compiler, NME deploys the same source code to C++, JavaScript and SWF bytecode without sacrificing reliability. As a result, NME provides fast hardware-accelerated performance for Windows, Mac, Linux, iOS, Android and BlackBerry, while also supporting Flash Player and HTML5. NME mirrors the traditional Flash API, so developers can leverage their existing experience to target new platforms, with better results.”
So far I have to say that statement is pretty accurate. But what about other similar tools that exist such as Corona, Unity, libGDX, Marmalade etc and why did I choose NME over them?
One of the more obvious reasons why I chose NME was my past experience with the Flash API which certainly lowered the learning curve. However, it was the fact that NME is the only truly free solution that won me over. LibGDX came closest out of the other choices I mentioned but it still required a $400 license fee for iOS. Having witnessed the HTML5 vs. Flash war I feel it is much safer to bet on technologies that are free and open source.
Of course NME is not without its flaws. Bugs and issues with various platforms do exist although fortunately they are few and far between. Additionally the community is not huge and so one can’t expect the same level of documentation and tutorials. That being said, I have really noticed over the past year how polished NME is becoming and how the community is growing which is fantastic to see. I am very much looking forward to seeing shader support for mobiles being added too.
So, having decided upon NME as the tool to use I realised I needed a game engine. When I first started there was not much choice so I decided to port over an engine I had made in Flash. As of now, ports of the popular Flash game engines like HaxeFlixel and HaxePunk exist. Regardless, software architecture and game engine design has interested me so I don’t feel that I wasted my time by creating my own and so far am very pleased with my results.
That being said, I did greatly underestimate how much work was involved in getting the game engine working properly.
The first challenge was getting the hang of rendering in a different way to what I had been accustomed to with Flash. In Flash, I would mainly use the DisplayList and at times blitting. This works great in web browsers but less so on mobile devices. Blitting actually causes the mobile to render via software which kills performance. The DisplayList, whilst better (it is GPU accelerated), is still not the optimum way of rendering. The best way when considering performance on mobiles is drawTiles and drawTriangles respectively. This means using a third party tool to export a swf into a tilesheet to render via drawTiles.
After understanding and implementing drawTiles, my next problem was displaying Android ads. I managed to find a library that used NME extensions to achieve this except that it did not work out of the box. Eventually I tracked down another person who had managed to get it up and running and they gave me a lot of tips. In the end this required delving into some of the NME framework and modifying the Java code template. It was after this that I decided to just focus on developing for Android as I did not want to waste a similar amount of time getting iOS ads working (although I believe they work out of the box on that platform) [...]

Read more: Postmortem: Building Hard-shell Hockey with NME

Friday, March 22, 2013

From Zero to Pitch: A Walkthrough for Game Designers

How can you take a rough game idea and turn it into something fun, interesting and engaging? This is definitely one of the most difficult obstacles that you must tackle as a game designer, as your job is to craft enjoyable experiences in a constrained environment. Would you believe me if I told you that after you finish reading and participating in the activities established in this article, you will have a game designed and ready to be developed? Yes, I know it sounds inconceivable, but trust me – this series of unconventional exercises will explain the workflow of designing a brand new game from zero to pitch.

Strengthen Your Game Design Muscle

I want to share with you one of the habits that helps me strengthen my game design muscle all the time:s turning real life experiences into games. When I started developing video games, I acquired the habit of trying to take everyday experiences and imagine them in terms of a video game; this makes you very aware of the things that are happening around you and the fun or frustrating factors in them. For example, let’s say that you took a flight and when you arrived at the airport your luggage got lost. This is a very frustrating scenario, but now take that experience and try to imagine how did the luggage got lost and what are the persons involved in that particular situation. Could you make a game based on this?
Can you take something apparently dull and turn it into something fun? Can you take something apparently dull and turn it into something fun?
What about a game where the player has to manage the conveyor belts at an airport and he loses points when passengers reach a certain amount of frustration levels when they don’t get their luggage? Or what if you experienced some turbulence during your flight and you got a little bit nervous… could you make a game where you had to fly an airplane and gain points by doing abrupt manoeuvres and scaring the passengers? Of course you can! This is the raw idea that you need to write down on paper and start working on. As a matter of fact, there’s this little booklet called the Tiny Game Design Tool that can make this process a little bit easier, by helping you jot the idea down as soon as possible. This tool is basically a printable PDF that you can carry in your wallet which helps you establish in very little time the following basic elements of your game:
  • Emotion, Mechanic and Theme
  • Main Character
  • Objects
  • Obstacles
  • Level Design

Play With the Elements

The alchemy of creativity (Image taken from Everything is a Remix Part 3) The alchemy of creativity. (Image taken from Everything is a Remix Part 3.)
We have a raw idea. This idea is like clay: you can mold it, split it into two, make a shape with it, and so on. Now we have to play with this idea… but how? Well, another creative exercise that is very useful to constantly work your game design muscle is to put in good practice the three basic elements of creativity: copy, transform and combine. I took this elements from the third episode of Kirby Ferguson’s documentary Everything is a Remix and they will help us exercise our mind so that it can always be wide open to creativity.

Copy

006_copy
Get practice and experience by copying existing games, but also apply small modifications to make the game easier or more difficult. This process of repetition and modification is called iteration and is very common in software and video game development. An example of some games that follow this exercise are:
  • Plasma Pong, which is a Pong variant with fluid dynamics and a new game mechanic that lets the ball stick to your paddle.
  • FPS-MAN, which is a take on Pac-Man but with a change in perspective. Now you look at the action from the point of view of Pac-Man and it changes the game experience completely.
  • Portal: The Flash Version, which takes the basic mechanics of Portal but constrains them to a two-dimensional space. This is also known as a demake.

Transform

006_transform
Did you have an interesting experience today, this week or this month? If you didn’t… borrow one! Take a newspaper and watch the front page news; you will notice that these stories are generally based on events that have something interesting to tell. Pick a story you like and turn it into a video game. Ask yourself questions: Who are the people involved? Where did the action happen? Could the personalities involved be interesting characters for my game? A recent game that tackles this type of exercise is Riot, in which the player experiences both sides of a protest, as rioters and as police officers. This idea came to fruition when Leonard Menchiari wanted to capture the feeling of his own experience of protests.
A kid that has to reach an airplane while avoiding security guards, cameras and checkpoints A kid that has to reach an airplane while avoiding security guards, cameras and checkpoints.
A more personal experience I had with this exercise was a small game I made for a jam where participants had to develop games based on TV news. My game was called “Escape from el Dorado”, and was based on a TV report about a kid that infiltrated the “El Dorado” airport in Bogotá and got into a plane that ended up in Chile. This story made me think immediately about how I could implement stealth mechanics in an airport setting.

Combine

006_combine
Take an existing game and combine it with another game, or change its genre. What would happen? What if I took a game like Super Mario Bros. and applied a skill tree just like the ones found in Role Playing Games? A recent example of combination is Bombermine, which takes the classic Bomberman game and mixes it with multiplayer elements.

Planting the Characters’ Seeds

Now that we went from a raw idea to something that is starting to take shape, and slowly but steadily we are covering the basics. Now let’s design the characters. First we’re going to start with a game design tool called Game Seeds. This game is generally played in groups but for this particular exercise we will play a single player variant focused on character development. Tip:I assume that by now you know the basics of playing Game Seeds. If not, please take a couple of minutes to read my guide here.
Click here to see the full size image Click to see the full size image.
We’re going to start with this fifteen card grid as our foundation. Please pick just six cards that have game mechanics that appeal to you. Now, in three steps we’re going to fill the Game Seeds sheet found below with the information given to us by the cards:
This is the Game Seeds sheet. Click here to download the printable version This is the Game Seeds sheet. Click to download the printable version.

Step 1: Fill the Hero Profile

006_seeds
Now that you have selected the six cards, go through each one and write down the icons that appear the most for each category. (In the case of a draw, choose the one you like the most.) For example, in the “species” category of your six cards you might have three human icons, two robot icons and one creature icon; based on this your character will be human.

Example

From the fifteen card grid I chose Fight, Escape, Race, Duel, Destroy and Navigate. Using those cards this was my character:
  • Creature (3 occurrences) or Robot (3 occurrences) (a draw, therefore I pick Robot)
  • Androgyne (4 occurrences)
  • Lives in the past (4 occurrences)
  • Nomad (5 occurrences)
  • Tall (3 occurrences) or Short (3 occurrences) (a draw, therefore I pick Tall) and Heavy (4 occurrences)

Step 2: Fill the Hero Attributes

Now take a look at the bottom of the cards and mark the Hero Attributes section with an “X” for each attribute that appears.

Example

Using the cards I chose I get the following attributes:
  • STR (STRENGTH) (6)
  • HEA (HEALTH) (6)
  • DEX (DEXTERITY) (4)
  • WIS (WISDOM) (2)
  • CHAR (CHARISMA) (0)
So Strength and Health are the main attributes of my character, and it is neither wise nor charming! Once you’ve done this, add your personal touch to the character in the Character Development section. This will define all the details that are going to give personality to your character.

Step 3: Pick the Mechanic; Draw Your Hero

Finally, pick your favourite game mechanic from the six cards you chose. This will be your main gameplay mechanic. Now you can draw a sketch of your hero based on all the attributes and his profile. This is my hero sketch, a tall and heavy androgyne robot in a steampunk world who was built using parts from a bank vault:
This is the point were you realize I suck at drawing This is the point were you realize I suck at drawing.

The Basic Elements of Game Design

006_4_elements
Now that we have a basic foundation of our game and a main character, it’s time to play with the elements that will form the game. I recommend you start with the elemental tetrad shown above because it’s going to be very straightforward for you when defining your game and the experience you want to give to your players. Use what you have done so far as a guide to define the following:
  • Aesthetics: This is how the game looks, sounds and feels, and it’s also what has the most direct relationship to the player.
  • Limbo is a game that is very good at capturing someone's attention just by it's aesthetics Limbo is very good at capturing someone’s attention just by its aesthetics.
  • Mechanics: These are the rules of your game. Use the game mechanic you chose in the previous activity and expand on it, asking yourself what the main goal of your game is and how players are going to achieve it.
  • Pong is a game that has a very limited set of rules, but that doesn't mean the game will be boring Pong has a very limited set of rules, but that doesn’t mean it’s boring.
  • Story: What tale do you want to tell through your game? Is it going to be a micro-narrative as in NES games, or is it going to be a complex and branching story?
  • David Cage is always pushing the envelop in terms of storytelling with games like Indigo Prophecy and Heavy Rain David Cage always pushes the envelope in terms of storytelling, with games like Indigo Prophecy and Heavy Rain.
  • Technology: This is the medium in which the aesthetics, mechanics and story will take place. What kind of technology are you going to use that will make the game possible?
  • Maybe your game works better as a board game, or as a game for smartphones Maybe your game works better as a board game, or as a game for smartphones.

Look at Your Creation Through Lenses

Our game is growing and finally taking shape, and now it’s time to polish the rough corners. To do this we are going to use the questions from the Deck of Lenses and focus them in areas of our game that we think need improvement.
Read more: From Zero to Pitch: A Walkthrough for Game Designers

Tuesday, March 12, 2013

How to Speed Up A* Pathfinding With the Jump Point Search Algorithm

Pathfinding is ubiquitous in games. So it’s important to understand the implications which are present when using algorithms such as A*. In this tutorial we’re going to cover a relatively new method for searching grid based worlds: Jump Point Search, which can speed up A* by orders of magnitude. Note: Although this tutorial is written using AS3 and Flash, you should be able to use the same techniques and concepts in almost any game development environment. This implementation is based on the original paper and article on JPS found here: Jump Point Search. The Lua based implementation, Jumper, was used for help with some parts of the implementation.

Jump Point Search Demo

Click the SWF to give it focus, then move your mouse over non-blocking areas of the map to have the NPCs try to get to it. Hit Space to switch between A*, Jump Point Search, and both. No Flash? Check out the YouTube video instead:

Setup

The demo implementation above uses AS3 and Flash with the Starling Framework for GPU accelerated rendering and the polygonal-ds library for data structures.

Pathfinding

Pathfinding is often used in video games and you are sure to bump into it at some point during your game development career. Its primary use is to give intelligent looking movement behavior to artificial entities (NPCs), to avoid them bumping into things (often). In some games the player avatar is also subject to pathfinding (strategy games, many third person RPGs and adventure games). So you might assume that the problem of pathfinding is solved, but unfortunately that’s not the case; there is no silver bullet which you can use and just be done with it. And even in big AAA games, you will still find funny things like this:
There may not be a silver bullet, but there is a bullet: the A* (A star) algorithm. In this tutorial we are going to see a brief overview of A* and how to speed it up using another algorithm, Jump Point Search. First we need a way to represent our game world in a way that a pathfinding algorithm can use it.

World Representations

One of the most important things to consider when thinking about pathfinding for your game is world representation. How is the data of the passable areas and obstacles organized with programming structures in memory? The simplest representation you can use is a grid-based structure, where path nodes are organized in a grid and can be represented by a 2D array. We are going to use this representation in this tutorial. Specifically it will be an eight-way grid representation: allowing movement in straight and diagonal directions.
The black pixels in the image represent the blocking cells.
Your requirements might be different, so this structure might not suit you. Good thing is that with some processing (usually done offline) you can change pathfinding representations to other formats. Alternatives to grid based approach would include things like polygon (obstacles represented by polygons) or navigation meshes (navigation areas represented by polygons); these can represent the same data with fewer nodes. Another data that can be stored in map representation are costs: how much it costs to travel from one node to another. This can be used for the AI to determine the path that, for example, prefers roads over regular terrain (making the cost of the road less than the terrain). Jump Point Search is specifically designed for eight-way grid based map representation so we’ll use that. Also, in its vanilla form it doesn’t support weighted maps. (In the final section I’ll discuss a possible way to remedy this.)

A* Pathfinding Refresher

Now we have a world representation let’s take a quick look at implementing A*. It’s a weighted graph search algorithm which uses heuristics (little “hints”) of how to best search the area from the start node to the end node. I highly recommend that you check out this visualization of pathfinding algorithms: PathFinding.js – visual. Playing with it can boost your intuition of what the algorithm is actually doing – plus it’s fun! For pathfinding using A* in rectangular grids we do the following:
1. Find node closest to your position and declare it start node and put it on 
   the open list. 
2. While there are nodes in the open list:
   3. Pick the node from the open list having the smallest F score. Put it on 
      the closed list (you don't want to consider it again).
   4. For each neighbor (adjacent cell) which isn't in the closed list:
      5. Set its parent to current node.
      6. Calculate G score (distance from starting node to this neighbor) and 
         add it to the open list
      7. Calculate F score by adding heuristics to the G value.

  • A* Pathfinding for Beginners (In-depth article that explains F and G scores among other things.)

  • Heuristics is essentially making a guess at the chance that the node being evaluated will lead to the goal. Heuristics can make a big difference in efficiency of pathfinding algorithms as they tend to limit the number of nodes that need to be visited. We are going to use Manhattan distance for our purposes (meaning that nodes closer to the goal will have a smaller number):
    private function manhattanDistance(start:Node, end:Node):int {
        return Math.abs(end.x - start.x) + Math.abs(end.y - start.y);
    }
    
    This is more or less it. We stop the algorithm when we find the goal node, and then track back using parent variable of node to construct the path. Search algorithms can be used for other things as well. A* is a general weighted graph search algorithm, and can be used on any such graph. This can cover other fields in AI, such as finding the optimal steps to achieve certain objective: throw a bomb or run for shelter and try to sneak behind an enemy? In game development we need to do things fast, when updating our games at 60 frames per second every millisecond counts. Even though A* performs reasonably well for some uses there exists the need to make it faster or use less memory.

    Optimizations

    Choosing the representation is the first thing that will have an impact on pathfinding performance and your choice of pathfinding algorithm. The size of the graph that is being searched will have a big correlation on how your pathfinding performs (which makes sense; it’s easier to find your way in your room than in a big city). Then you would consider higher level optimizations which usually involve clustering data to smaller regions and then searching those while later refining paths in travelled smaller regions. For example, if you want to go to a restaurant in a neighboring city, you first consider how you get from your city to that one, and once you are in that city you limit your “searching” to the area where the restaurant is located, ignoring the rest. This would include things like swamps, dead end elimination and HPA*. On the lowest level you have to do the searching. You chose your data representation and possible abstractions and then plug them in an algorithm that will pick out nodes, travel here and there searching for the goal. These algorithms are usually based on the A* searching algorithm with possible modifications. In simpler cases you can get away with using straight A* which offers you the simplicity. I’ve provided a grid based implementation in the source download.

    Jump Point Search

    [...] Read more: How to Speed Up A* Pathfinding With the Jump Point Search Algorithm