Bubble Shield

Shields are probably my most favorite part of Supreme Commander and other futuristic games.  They invoke a hidden part of my SciFi core which makes me very happy :)

An image I found at media.moddb.com.  It shows how well Supreme Commander rendered shields - transparent but  still has a shape and electromagnetic like properties.

I just got the "Bubble Shield" working the other week.  It took a huge overhaul of the way items work.  I implemented an "interceptor" style framework that works like this:

• Interceptors will be called in a filter chain fashion (invoking each one in order and then returning back through the chain).
• Interceptors will be collected in a list when an item is used from the actor (user of the item), board (the environment around the actor), and the target (the one to use the item on).
• Typically interceptors will provide:
• Actor: Time, Update on Use
• Board: Line of Sight, Range Check, Console, Audio, Accuracy
• Target: Damage Modifiers, Health
• Interceptors can be injected or modified to add additional functionality for mods.
• Interceptors usually modify an "invocation" object instead of the actual items or units.  This allows things like shields to reduce the damage before it is calculated in the target's health.  Cloning the item might also be another good approach.

1st implementation of a "Scottonian" Bubble Shield.

The basic factors for creating a shield can be narrowed down to:

• cost per turn - The time units used while shield is active.
• cost per activation - Time units used to activate the shield.
• charge time - Time it take for the shield to become active.
• activation time - How low the shield will remain active.
• damage - How much damage the shield can absorb.
• in/out probability - The probability of damage to the item's wearer and how much accuracy is changed while the shield is active.

For now, the "Scottonian" bubble shield behaves as follows:

• cost per activation = 5
• charge time = 2
• activation time =  4
• damage = 2

The shield is a damage modifier, so damage is first subtracted from the shield and the remainder is passed to the target.

The Game

In a previous post I alluded to a game I was working on but didn't talk about the game itself.  I'll slowly be describing it over several posts.  It is meant to be a multiplayer, squad, tactical, turn-based game.  It has fog-of-war, usable items, vehicles, cloning of units, multiple worlds, A.I., and many fun objectives.

The theme of the game is currently using Stargate SG-1.  It isn't public yet, so I didn't see any harm in making the engine fun and engaging while it is still in the very early stages.  In the picture, you can see the controls on top, a friendly unit on the left and a Jaffa on the right.  The dark colored tiles indicate the fog-of-war.  The map is a Goa'uld ship.

Objectives
I've decided to start with some simple core objectives:

• Versus - Standard team games that are scored on kills and last man alive.
• Horde mode - Wave after wave of enemies come at you until you can't take it anymore.
• King of the Hill - Protect a specific location for a certain amount of time.
• Location - Get some or all of your team members to the indicated location.
• Mission - Units always start in a specific location and the objective depends on the mission.  A less procedurally generated objective, but gives a standardized test of skill for you and your friends.

Cloning Units

I think this feature is very interesting, but in no way unique because some games like Eve use the concept.  The principle is that players build up experience and spends so much time on units - only to have them killed by a silly mistake.  Well, in X-COM these deaths could be avoided by saving the game, but this isn't interesting.  Some would even consider it cheating because it has no cost to the player, can be done as often as the player wants, and has no analog to real life.  Eve got around this by allowing the player to pay credits to "save" unit's memories and DNA as a "clone".  Basically, a save point that covers all the negative affects - if the player can afford it.

Time Units

The game currently uses time units to perform actions like moving or using an item.  The new XCOM game doesn't use these at all, but provides a subset of actions that can occur each turn, much like Flotilla.  I don't think division and subtraction is as hard as Firaxis thinks it is to strategy, but I will concede that it make these games more fun for the general player.  I've played the new XCOM game and I will stick with time units for now.

Maps
Maps are built in a "Map Builder" web application that is part of the main deployment.  Emily has been making a lot of the maps that I use today: Mother Ship, Arena, Medieval Planet, Longest, and SGC.  Maps are composed of a grid and each tile has "attributes" that add things like walls, spawn points, etc.

Jersey 2.0 Custom Java Objects

I'm really upset how Jersey 2.0 is handling custom java objects for query parameters.  The Jersey query types can have a constructor that accepts a single String argument, a static method named 'valueOf' or 'fromString' that accepts a single String argument, or a read only List<T>, Set<T> or SortedSet<T>.

It assumes that objects are created from a single parameter.  Most of my parameters are created from multiple parameters combined together.  For example, a location object is usually sent like "?x=0&y=0&z=0".  Why not match these parameters to a type's constructor like Vector3d(int x, int y, int z) assuming the application is compiled in debug or allowing param annotations on constructors and/or getter/setter methods would be a giant step in the right direction.

NIO

Applications that have constant connections/feedback from the user to a server and back normally involved polling, a response ticket for accessing later, or Non-blocking IO of some sort (e.g. Netty).  Today we now have better solutions using Servlet 3.0 with asyncronous request processing and HTML 5's web sockets.

Spring MVC:
http://blog.springsource.org/2012/05/06/spring-mvc-3-2-preview-introducing-servlet-3-async-support/

I'm still investigating how to do this with using Jersey with just Jetty and Tomcat, but it looks like Jersey 2.0 isn't ready yet:
http://jersey.java.net/nonav/documentation/snapshot/async.html
http://jersey.java.net/jersey20.html

Minmax and Me

Game Searching
I had some basic courses on the subject of creating a minmax search tree for games in college at GaTech.  I learned a lot from my professor Thad Starner and reading the "Artificial Intelegence: A Modern Approach".  Creating one for something like X-Com turns out to be a big challenge.  Here is a screenshot from a prototype game I developed in my free time (mostly focusing on the game engine and not the look and feel yet):

Minmax and Alpha-Beta Implementation and Challenges
It wasn't hard automating actions like moves, end turn, and using items - this was already there because it was needed by the UI.  It did take a second to figure out how to represent all the different actions a player could take.  Fortunately, the game already had a concept of different games having a different "process id" so that multiple games could exist at the same time.  By making some processes public and ones that dealt with A.I. private... each action could be stored and evaluated.

After having separate game states and a way to evaluate them, next came minmax.  This wasn't hard at all and started out with a simple BFS of items, end turns, and moves.  At last, a full tree of every single possible action a player could make.  However, this took a very long time.  Here is a screen shot of a tree using JGraph to visualize what happened in the search (green are moves, yellow are items, and red is end of turn):

Next, I implemented alpha-beta pruning to speed things up a bit.  This helped a lot!  For a tree that looked 2 turns ahead, it went from 13 min down to 1 min.  This was giving me about 600 nodes/sec.

Now I could test the A.I. in the game and see how it performed.  Well, it turned out that I was using a very small board (4x4) and two units that didn't have many item actions.  The outcome was a single unit to calculate 1 turn ahead needed over 1 hour.  This was horrible and devastating at the same time.  I started thinking: Is minmax not usable in practice?  Do I need to use some sort of greedy, iterative deepening to come to a conclusion faster?  Do I need to switch to something like Machine Learning?

I was hurt emotionally... I needed help or my A.I. would take too long for it to be useful.  I asked a few people that I knew of in the field of A.I. and received a very positive response from Mark Watson.  I found him by reading some of the papers he wrote on alpha-beta searches posted on his site.  He stated a few pointers; the most notable of which being that 600 nodes/sec is much too slow.  Some quick searches revealed that, at tournaments for chess, programs reached thousands of nodes per second.  I didn't see one that did less than a few thousand (pdf).

I found that the "line-of-sight" algorithm was taking a very long time.  Fixing this reduced the speed from over 1 hour down to a reasonable 30 sec for 2 turn look ahead.  This gave me about 7,000 nodes/sec.  Much faster and usable in the game, but not the greatest.

I played the A.I. again and it seemed fine in an open room, but now had a lot of issues with the fog-of-war.  I need to add some belief information so that the A.I. will not forget about the opponent when not in sight and then forget later on when there are too many possibilities.  This is very challenging because the opponent must be accounted for and a lot more special rules for evaluation and determining what the opponent did on their turn while matching it to the current state.

Another issue is that the A.I. just sits around when no other player is near.  I need to add some evaluators for searching, guarding, etc.  For now, this would just complicate things more.