Building an AI for Fatal Reaction: A 2D Side Scrolling Shooter

We recently released Fatal Reaction to the Apple App Store. It's a free realtime fast paced 2d multiplayer shooter. The online mutiplayer experience seems to be fun, but there aren't many people playing the game. Most people who try the app can't even fully experience it. At certain times of the day it takes 5-6 minutes to find someone to play against.

Just Some Bots Having Fun (Update Awaiting Apple's Approval)

"Find Players Online" Lets You Search for Players While Practicing!

It quickly became clear that we needed to have an offline multiplayer experience. Writing an AI for such a game isn't easy. The player is in a continuous environment, inputs such as movement speed can range from 0-1 and moving about the level requires various kinds of jumps with different speeds and jump heights. Finally there was the problem of using the weapons. Most of the weapons did instant damage. It is easy to write bots that can own humans at this task. I needed to make bots that were competitive. When I first took on the task of writing the AI, there was no obvious solution.

I decided to break the task up into small easier to digest steps. The first task I decided to take on was that of pathing. The bots need to run around the map and do so in an efficient and natural manner while not getting stuck. The big decision for me was whether to manually feed pathing information or have the app generate the pathing automatically. My main goal was to have the pathing work and work right. I really could not think of an efficient way to calculate the pathing automatically. Even if I could, each device that loads the map would need to recalculate the pathing. After much thought I decided to manually feed it pathing information.

Pathing for the Level Facility

Having decided I needed to manually input the pathing information, I tweaked the level editor to help me. Finally I wrote the code necessary to help me read the pathing information in the game. After going back through my data structures course, I came up with an algorithm to help traverse the map. Soon my AI was running around the level following the player!

Pathing for the level Country Side

Having accomplished the most basic task, I added more layers of logic and decision making to the AI. It added instructions to know when to go on the offense and when to retreat. After adding some randomization to the aiming, the AI started to behave like a human. With planing and attacking the problem one task at a time, the daunting task of writing an AI became feasible.

Preview of the Bots in Action

The new version of the Fatal Reaction has been submitted to the app store. Within a week or so, it will be available on the App Store! If you have an iPhone, iPod Touch or iPad, try out the free app. We are looking for feedback to help us improve the app. And keep a look out for the next version update with the AI to play offline!

Settings Screen for the AI

What happens when a Javascript constructor returns?

function T(){return T.a}
T.a = new T();
T.b = new T();
T.a == T.b

If you run this, the last statement will be true. Why?

The basic concept in a constructor's return statement is that if the return value is a primitive (null, number, boolean) then the result will be as expected. The "new" statement will return a reference to the newly created object. If the return is a reference, then that is what will be returned.

Thus when T.a = new T(); is called, T.a is undefined and the reference to the newly created object is returned. When T.b = new T(); is called T.a is defined and the reference to T.a is assigned to T.b. That is why the final statement T.a == T.b is true.

This is an interesting way to implement singletons in Javascript without having to write any special methods or use any other techniques.

You can also implement the Flyweight design pattern after majority of the program is written using a constructor.

Dojo Maven Integration

Project Structure:

/src
     /main
          /assembly/project-dojo.xml
          /javascript
                     /profiles/project.profile.js
                     /projectpackage1/**.js
                     /projectpackage2/**.js
pom.xml

project.profile.js

dependencies ={
    layers:  [
        {
        name: "../projectpackage1/projectpackage1",//output file
        dependencies: [
        "projectpackage1.hello"//list of all the files that need to be compressed into the given file.
        ]
        }
    ],
    prefixes: [
        [ "dijit", "../dijit" ],
        [ "dojox", "../dojox" ],
    ]
};

project-dojo.xml:

<?xml version="1.0" encoding="UTF-8"?>
<!-- $Id: soc-dojo.xml,v 1.1 2010/04/06 19:27:59 rsingh Exp $ -->

<!-- Assembly descriptor for the CSP DOJO Custom Build ZIP -->
<assembly>
  <formats>
    <format>zip</format>
  </formats>
  <fileSets>
    <fileSet>
      <directory>${basedir}/target/javascript/release/dojo</directory>
      <outputDirectory></outputDirectory>
      <includes>
        <include>projectpackage1/**</include>
        <include>projectpackage2/**</include>
      </includes>
    </fileSet>
  </fileSets>
</assembly>

pom.xml:

<project xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://maven.apache.org/POM/4.0.0" xsi:schemalocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
 <modelversion>4.0.0</modelversion>
 <groupid>project-group</groupid>
 <artifactid>project-name</artifactid>
 <packaging>pom</packaging>
 <name>SOC DOJO Custom Build Project</name>
 <description>

 <repositories>
  <repository>
   <id>topaz-repository</id>
   <name>Topaz Project Maven2 Repository</name>
   <url>http://maven.topazproject.org/maven2</url>
  </repository>
 </repositories>

 <build>

  <plugins>

   
   <plugin>
    <groupid>org.apache.maven.plugins</groupid>
    <artifactid>maven-dependency-plugin</artifactid>
    <executions>
     <execution>
      <id>unpack dojo</id>
      <phase>generate-sources</phase>
      <goals>
       <goal>unpack</goal>
      </goals>
      <configuration>
       <artifactitems>
        <artifactitem>
         <groupid>org.dojotoolkit</groupid>
         <artifactid>dojo</artifactid>
         <classifier>src</classifier>
         <version>1.5.0</version>
         <type>zip</type>
        </artifactitem>
       </artifactitems>
       <outputdirectory>${project.build.directory}/javascript</outputdirectory>
      </configuration>
     </execution>
    </executions>
   </plugin>

   
   <plugin>
    <groupid>org.apache.maven.plugins</groupid>
    <artifactid>maven-resources-plugin</artifactid>
    <version>2.3</version>
    <executions>
     <execution>
      <id>copy-js</id>
      <phase>generate-sources</phase>
      <goals>
       <goal>copy-resources</goal>
      </goals>
      <configuration>
       <outputdirectory>${project.build.directory}/javascript</outputdirectory>
       <resources>
        <resource>
         <directory>src/main/javascript</directory>
         <filtering>false</filtering>
        </resource>
       </resources>
      </configuration>
     </execution>
    </executions>
   </plugin>

   
   <plugin>
    <groupid>org.codehaus.mojo</groupid>
    <artifactid>exec-maven-plugin</artifactid>
    <version>1.1</version>
    <configuration>
     <executable>${java.home}/bin/java</executable>
     <workingdirectory>${project.build.directory}/javascript/util/buildscripts</workingdirectory>
     <arguments>
      <argument>-classpath</argument>
      <argument>../shrinksafe/js.jar</argument>
      <argument>-classpath</argument>
      <argument>../shrinksafe/shrinksafe.jar</argument>
      <argument>org.mozilla.javascript.tools.shell.Main</argument>
      
      <argument>build.js</argument>
      <argument>profileFile=${project.build.directory}/javascript/profiles/soc.profile.js</argument>
      <argument>action=release</argument>
      <argument>optimize=shrinksafe</argument>
      <argument>layerOptimize=shrinksafe</argument>
      <argument>internStrings=true</argument>
      <argument>cssOptimize=comments.keepLines</argument>
     </arguments>
    </configuration>
    <executions>
     <execution>
      <id>generate-release</id>
      <phase>generate-sources</phase>
      <goals>
       <goal>exec</goal>
      </goals>
     </execution>
    </executions>
   </plugin>

   
   <plugin>
    <artifactid>maven-assembly-plugin</artifactid>
    <configuration>
     <descriptors>
      <descriptor>src/main/assembly/soc-dojo.xml</descriptor>
     </descriptors>
    </configuration>
    <executions>
     <execution>
      <phase>package</phase>
      <goals>
       <goal>single</goal>
      </goals>
     </execution>
    </executions>
   </plugin>

   <plugin>
    <groupid>org.apache.maven.plugins</groupid>
    <artifactid>maven-install-plugin</artifactid>
    <executions>
     <execution>
      <id>install-custom-build</id>
      <phase>package</phase>
      <goals>
       <goal>install</goal>
      </goals>
     </execution>
    </executions>
   </plugin>

  </plugins>
 </build>

</description></project>

Google App Engine: Scaling cost

I recently released an application for the iPhone called Device Locator. This application has an interesting pricing model: We provide hosting for users' recent location data for a one time fee. Currently the application runs on a LAMP stack on a shared server. The over all cost is reasonable. This solution, however will not be viable for long. For every new user we get, we can add about 33 new requests per day. These requests are going to come in no matter what. In order to keep this service running in the future, we will need to write a scalable service.

Choosing a Service

There are many services out there in the cloud computing realm that we can utilize to help us scale. I will not go into comparing the different services, but simply talk about my approach to solving the problem.

My initial gut feeling was that the Google App Engine should be reasonable. I reasoned that: I know java (later you will see why this didn't matter), Google does crazy stuff and heck I have taken a graduate level course in distributed computing which talked specifically about Google's scaling infrastructure. One of the other major factors in choosing a cloud computing service was that I didn't have to manually run any services. I do not need to worry about administering my virtual servers. Google's App Engine seems to provide everything I can ask for. (Except running an Apple Push Client)

The Problem

The problem is simple. The service should keep meta data about a device. When it receives a location update, it should add the location to a queue and delete the oldest location if the number of locations is greater then a specific constant.

With the scaling problem simplified to its guts, we can now try approach the problem.

Getting a Feel for the App Engine

Before we invest heavily in the app engine, we needed to determine the real cost of running this service on the App Engine. Our solution was to simply forward all locations from our current service to the Google App Engine and see how well it handles the requests.

At first we implemented the service in Java using proper classes and domain models. We had a Device Object with an array of DeviceLocations. The array was sorted using the annotations provided by JDO. So when we got a new location we simply remove the last location and add the new one at the end.

This solution was simple, but costly. It took 500 ms to process each request. Our queue size for the locations was 100. This processing time was simply unacceptable. We were being charged $0.10 for each hour. With the amount of users it would easily add up.

I searched far and wide as to what could be causing the CPU usage to be so much. I ran into some discussions which talked about how the CPU time was not just web server's CPU time but also the datastore's. I read some more and realized that Google's calculation of CPU time was not exact. It was an estimate. Their CPU time is at a fixed gigahertz rate. If they use faster CPU's you can burn through your time much much quicker. This was a little unsettling.

To debug what was causing the CPU usage, I stripped down the code to the bare minimum. I realized that to pull an entity and update a value it took 150 ms. After some more research I found out that applications written in Python could be 50% faster.

So I took to writing the service in Python. I quickly realized that Python had much more control over the datastore. It was really easy to pick which fields to index and which fields to ignore. In Java, all fields were indexed. This might have added to the CPU usage. Python also had a better implementation for the different data types. There was a data type to store a 1mb string.

At the end I decided to only use 1 entity type: Device. To store the locations I serialized and deserialized the an array stored in JSON. I reasoned that since since Google does not calculate CPU time exactly, I wanted to reduce the amount of time spent in I/O. My new implementation would query the locations using an ID and then manipulate the field and save it.

To my surprise the same exact functionality on average used only 116 ms. This was more reasonable.

Although I am still not impressed, it is reasonable.

According to Moore's Law every two years costs should be recalculated. I do not think Google has done that yet.

TL;DR For the Google App Engine use Python. You do not want to scale a costly service.