In our never ending quest to improve our skills and learn a little more about designing video games, we decided to make a game called Zombie Rockers.

Zombie Rockers is an example of a match three game like Zuma, Luxor and Pirate Poppers.
Basically, the objective of the game is to prevent a chain of balls of different colors rolling along a given path from reaching the end of the path by throwing balls and making groups of 3 or more balls of the same color.

We choose this game because we thought it would be a simple game, and that we could implement the basic mechanic in a simple way, generating some content and levels and make a full simple game out of it. But the reality was that it was a much harder task that what we initially thought. The basic mechanic has a lot of little details that were hard to represent in an easy way in our framework, and generating content although easy the first time, is hard to modify and tune, and we are too lazy also.

We were working on the game about two months ago and we were waiting to publish it because we wanted it to have the minimum of features it required and to remove all bugs we found. Now that it is in a playable state we decided to put it in the games section.

The biggest problem we have is that the game has the best name ever in the whole wide world, but there are no zombies.

Hope you can give it a try, play the game here.

Our first version of the online server for highscores is up and running on google app engine!

We have updated Jylonwars to use it, please try the game and leave any feedback you may have.

We are doing our first attempt at implementing online highscores for our games.

Our Score structure right now is:

Score {
id : String   - The unique identifier
name : String - The name of the player
points : long - The value of the score
timestamp : date - The time when the score was submitted
tags : Set[String] - A set of tags of the score
data : Map         - Extra data of the score
}


The tags are used to classify the scores by different criteria, for example, the difficulty, the level, etc.

Data is a map of simple values used to add extra information of the score, like bombs left when the user died or enemies killed of each type, etc.

The idea is to have an online application for the highscores of all the games. All comunication is performed using a gameKey which is unique for each game and allow us to separate the scores by game.

Our current API consist of a submit method and a query method and it is based in HTTP and JSON.

submit(gamekey : String, name : String, tags : Set[String],
points : long, data : JSONString) : String


This method allows us to submit a new score and returns the generated id for it. The extra data attached to the score is specified by a JSON string. The timestamp is generated at the moment the score is stored.

scores(gamekey, tags, limit, ascending) : List[Score]


This method allows us to query for scores of a game by using:

• tags : returned scores must have every tag in tags
• limit : returned quantity must be less than limit
• ascending : if true scores are returned ordered by points ascending

Our first implementation will be based in google app engine but is not online yet, and Jylonwars will be the first game using it.

There are some features we are thinking about:

• Security: the submitted scores should be encrypted and validated (we know it is not totally safe but it would prevent casual tampering)
• Online scores board

Also, we are thinking about making the server project opensource.</p>

The idea of this post is to share some techniques you could use in order to optimize collision detection in your game, but without implementation detail.

Sometimes when we are developing games, part of our logic could be based on the fact that two objects are in contact or not. In Dasasult, we want to know when bullets are in contact with other objects (for example: droids, scene obstacles or the level limits) and we want to know the area where a droid can walk.

Every object we want to check collisions has a position and a polygon shape defining its form in the collision space. Collision detection between objects is performed by checking collisions between their shapes.

The cost of our collision detection by now is heavy because we are checking collisions between all objects. If we increase the number of objects, then the performance is going to be affected. So, if that is the case, then we could have in mind some optimizations to improve it.

The first one is based on the fact that an object A collides with B then B collides with A and the same when not colliding. We could have a structure to mark whenever we check an object colliding with another object and then use that mark to avoid check the inverse collision. That will let us improve a bit because we will have only half collisions detection but with the cost of memory for the new structure.

The second one is to use bounding boxes for fast intersection detection. The idea is to avoid collision detection between game objects if their bounding boxes are not colliding. The most used shapes for this purpose are: Axis Aligned Bounding Boxes (AABB), Oriented Bounding Boxes (OBB) and Spheres.

For Dassault objects we used AABBs because they are really easy to build and work with.

Bounding boxes are really good when perfect collision is too heavy, but we have a new structure for each object and we have to update it whenever the object changes its position, size or angle.

Figure: droids and obstacles bounding boxes.

The third one is based on the spatial information of the objects to avoid intersection detection with objects far from each other.

Spatial structures are used for this purpose. The idea is to divide the space in zones so we could know in any time, for example, which objects are in a given zone or which zones contains a given object. There are several types of spatial structures: Grids, Octrees/Quadtrees, Binary Space Partitioning (BSP), Kd-trees, etc.

Note: these structures are commonly used for other purposes, for example, frustrum culling and networking algorithms.

For Dassault we used Quadtrees because we have some knowledge of them and a partial implementation to start with, also they work fine with AABBs.

When using spatial structures, we could improve a lot the performance because we can avoid to check a lot of collisions, but also we are growing in the information to maintain and we should be aware that each time an object moves we have to update in which zone is it now. Each spatial structure has its own pros and cons for different cases, you should have them in mind when choosing one for your game.

The next example show a possible use of spatial information (using grid partitioning):

Figure: example of objects in different zones

If we take a look at the image, we have object 1 in zone A and B, object 2 in zone B and object 3 in zone D. In one moment we would like to detect collisions for object 1, then we check collisions only with objects in zone A and B, that is, object 2.

After you decided the spatial structure to use, collision detection could be performed like this:

for each object in my zone {
colliding = false
if (getStoredCollision(me, object) != null)
return getStoredCollision(me, object)
else if (collisionBetweenBoundingBoxes(me, object) == false)
colliding = false
else
colliding = perfectCollision(me, object)
storeCollision(me, object, colliding)
return colliding
}


Conclusion

The solution we used worked as we thought and let us to improve a bit the performance of the game. However, the current implementation could be too featureless based on your game requirements, sometimes you need more information from collisions like the points of contact, the movement direction of each colliding object, the normal vector of the contact points for each object, etc. If you want that stuff and more you could use a physics engine, for example, Box2d or Bullet Physics Library (both libraries have Java ports).

Well, hope you enjoyed the post, feel free to make a comment if not.

As I said on the last post, I want to talk about how animations were implemented in Dassault.

In the original game, droids are animated using one image for each frame of the animation. Those images could be all in a single file or not. Here is an example of an animation:

This solution could be expensive for Dassault because droids are rendered in several layers, so to animate a droid we need to animate each droid’s layer.

Another solution, and the one used in Dassault, is to separate the droid in parts to create a hierarchy and then animate those parts by moving them inside the game.

For Dassault, the droids are separated in three parts, the body and the two legs:

And here is an example of how the parts are related to the droid:

droid {
body {
position (0,0)
}
leftleg {
position (-5,5)
}
rightleg {
position (5,5)
}
}


Where each part position is relative to the droid’s position.

To perform the animation, given a specific time, we calculate the value of a property by interpolating the values of two key frames.

For example, we could animate the value of the position of the leftleg part by specifying that on 0ms it should be (0,0) and on 100ms it should be (0,-10) so, when the time is 50ms the position would be (0,-5).

Here is an example of how the animation could be specified:

walk {
body.position {
time 0 (0,0)
time 200 (0,-5)
time 400 (0,0)
time 600 (0,-5)
time 800 (0,0)
}
leftleg.position {
time 0 (0,0)
time 200 (0,-5)
time 400 (0,0)
time 800 (0,0)
}
rightleg.position {
time 0 (0,0)
time 400 (0,0)
time 600 (0,-5)
time 800 (0,0)
}
}


And here is a video showing how it looks inside the game:

This example shows how to animate positions, with the same ideas you could animate an angle, colors, alphavalues, etc.

Next time, I want to talk about collision techniques used for Dassault.