10 Mar

Review: The Last Arcadian

The Last Arcadian is one of those games that in hindsight are pretty strange stuff for a public domain or shareware title. Considering even in the early 1990s a 3D shooter was automatically rather cool and thus profitable, The Last Arcadian makes you think why it wasn’t released commercially. It looks a bit dated even for a 1992 3D title but you have to keep in mind it is a one man show. A bit of money would have made it look much nicer. It could be compared to Epic but I’m not sure if that’s a compliment. I have seen worse — I have paid for worse.

(Another video below.)

The main idea is to go and destroy enemy bases while the enemy tries to do the same to you. The game is over if your base is destroyed. If you, flying a fighter, are killed, you will simply find yourself piloting a nearby fighter that was previously computer controlled. There are multiple wingmen flying around and if you watch the first video, they sometimes manage to win the game for you.

The enemy fighters are killed with lasers and homing rockets and the enemy base needs to be bombed. When you return to your base, you need to make sure nobody else is trying to dock at the same time; you have to request permission to land. You can also repair your fighter in the base and then return to the battle (to save the computer controlled fighters.) The bases can also fire cruise missiles that travel slowly and you need to escort them and also keep the enemy missiles away from your base.

Overall, the game is very nice. It is simple but has some quirky features and also some quite modern stuff like the zoom in your ship at the start of each level and the fact everything is three-dimensional. There is a feeling of immersion as the rest of the war goes on around you while you’re being resupplied — quite well done as I no longer have the imagination of a kid. If you’re a fan of the old 3D Star Wars shooters, you probably should check this out if you have an Atari ST lying around.

The game can be found on the ST Format 42 cover disk available on this page.

03 Mar

Review: Starball

I used to read ST Format back when I had an Atari ST. Later in its existence the magazine started to include better and more complete games and other software on its cover disk, probably because of the Atari was dying and publishers decided to give away their assets (or more like the actual developers were able to secure rights to the software from the publishers and then give it away so the work wouldn’t be in vain.) Also, back in the day shareware meant you got the full software to play with and only then you had to decide whether to pay or not to pay for it — it wasn’t uncommon for that to be actually profitable. Whatever the reason, I wouldn’t have probably ever heard of some pretty awesome games.

Starball was one of those games.

On the Amiga, there were a few excellent pinball games by Digital Illusions, including Pinball Dreams and Pinball Fantasies. On the Atari ST, there were practically no modern pinball games apart from the STE title Obsession which was most likely created to cash in thanks to the surging interest in pinball games thanks to DI and also because the STE was capable to give the same smoothness as on the Amiga. But for the plain vanilla ST users, there still were none. At least until Starball, that is.

Starball is a modern pinball game — as in the screen scrolls and it was made in the 1990s — but it’s very different from the look and feel of the relatively realistic pinball games on the Amiga. The gameplay and the table is very similar to the Crush series on the PC Engine (Turbografx-16) which realized a pinball video game doesn’t have to simulate a real pinball table and added common elements from video games in general. While Pinball Dreams had very smooth gameplay based on getting accurate chains of ramp runs, in Starball the ball is used to smash flying spaceships, cultists and Jimmy Hill’s chin. In addition, Starball has three smaller areas with their own set of flippers and even graphical theme and when you miss and the ball will simply fall down, it will only move your one area down. Unless you are already in the bottom area.

In the middle area, you are building a space ship one part at a time and trying to stop turrets destroying the spaceship parts. On top level, you try to crush little guys walking in circles and there’s a slimy face in the center. And the face will get slimier each time you kill all the little guys. And the bottom area has a huge fly-eyed alien and more explosions. The fly alien thing also contributes to the game in that its mouth takes you to a bonus level. There are at least two different bonus levels, in general they are much like the small Mario level in NES Pinball keeping in the overall pinball theme.

While the game is very enjoyable at least as a nostalgy trip, there are some faults. First, the gameplay isn’t nearly as fluid as what the standard set by Dreams was at the time. The flippers feel sluggish and sometimes the ball bounces all weird. However, you can easily adapt to the slight delay in the flipper hit. The table area isn’t terribly interesting in that there are no huge ramps and other stuff the Amiga games did well but the grimy graphics and the self-awareness of the limitations makes the game stand out.

The game can be found on the ST Format 64 cover disk available on this page.

22 Sep

Introducing My Latest Projects

… Or, How to Procrastinate Productively.

klystrack3

I decided to make one of my current projects open source and post them on Google Code just for fun. The project is a tool chain that I’m using to remake Thrust. In reality, I decided to divide the project into two separate projects: the actual game engine (called klystron) and related tools, and a music editor that uses the engine.

Here are two videos I made a while ago that demonstrate the engine. The first is the music editor (called klystrack) — it’s much less ugly at the moment but the sound synthesis is the same, and that’s what matters:

The sound engine (“Cyd”) is basically a very simple software synthesizer with capabilities comparable to the SID or any 8-bit machine from the 80s. The editor is a fairly standard tracker, much like GoatTracker.

The graphics half of the engine is basically a wrapper around a quite fast collision detection system (pixel-accurate, or it wouldn’t be much good for a thrustlike) built on SDL. It also does background collisions and drawing as well. As you may have guessed, the whole point is to provide a limited but still helpful set of routines that are useful for creating 2D games not unlike what video games were in 1991.

And, here’s a proof I’m actually working on the actual game (the sound effects are created in real time by the sound engine):

A note on Google Code: it’s rather nice. It provides the standard open source development stuff like source control an such but I really like how clean and hassle-free it is. Adding a project takes a minute and after that it’s simply coding and some quick documentation on the project wiki. The project wiki is good example of how simple but elegant the system is: the wiki pages actually exists inside the source control as files, just like your source code.

Go check Google Code out and while you’re at it, contribute on my projects. :)

01 Jul

Wordle and 30 Years of Games

Here’s a superficial analysis on game titles. I have used Wordle to generate a word cloud from lists of recurring phrases in game titles. What I generally wanted to know is how a generic title from 1985 would differ from a generic title from 2009. The size of a word or phrase is relative to how many different titles contain the text and also how complex the phrase is (so one word long “phrases” won’t dominate the more interesting, relatively rare phrases).

What the word clouds show are very generic words like “space” or “super”, the number two (a game series is more likely to be two than three games long) and multiple word phrases which usually are popular game series, clich├ęs (Foobar of Doom) or games with many versions or expansion packs. It is interesting that the generic words tend to be the same across 30 years — all generations of gamers seem to love dragons. Another point of interest is that a phrase from a 1980s game title is much less likely an established brand as it most likely is in the 1990s. Also, in the 1990s is became common that a game title has the release year attached to it, since EA et al started to churn out minor updates to their sports games as brand new releases.

30 years of games. Find your favorites!

1980-2009

1980-2009

1980-1989

1980-1989

1990-1999

1990-1999

2000-2009

2000-2009

23 Jul

Collision Detection with Occlusion Queries Redux

Introduction

Here we describe a method for checking collisions between arbitrary objects drawn by the GPU. The objects are not limited to any shape, complexity or orientation. The objects that are checked for collisions can be the same objects that are drawn on the screen. The algorithm is pixel perfect but without further refining is limited to 2D collisions.

Description

The algorithm can be divided in three separate steps:

  1. Determine which objects need testing

  2. Set up the GPU buffers and draw the first object so the stencil buffer is set

  3. Make an occlusion query using the and using the stencil from the previous buffer

If the occlusion query returns any pixels were drawn, the two objects overlap.

Determining objects that need to be tested

Figure 1.
Figure 1.

To speed up the algorithm, we need to eliminate object pairs that can’t overlap. This can be done by projecting the object bounding volumes in screen space. Then, we can quickly check which 2D polygons overlap and do further checking. Choosing the shape of the bounding volumes/polygons is not relevant. In this document we will use rectangles for the simplicity.

The example case in figure 1 shows two colliding objects (overlapping bounding rectangles shown red), one near hit (green overlap) and one object with no collisions or bounding rectangle overlap. To determine the collisions (and non-collisions) we need checks for every bounding rectangle (15 checks) and two checks using the GPU1. Without the use of the bounding rectangles, we would need 13 more checks on the GPU.

The bounding rectangles in the example can be generated by finding the maximum and minimum coordinates and using them as the corner points of the rectangle. Since the algorithm finds collisions as seen from the camera, we need first project the object coordinates (or the object bounding volume coordinates) on the screen and find the minima and maxima using those coordinates. Most 3D frameworks provide functions for projecting a 3D point to screen coordinates using the same transformations as seen on screen2.

Drawing objects

Before we start drawing the objects on the graphics buffer, we need to clear the stencil buffer. After that, the GPU should be set to draw only to the stencil buffer, that is we don’t need the color buffer or depth buffer to be updated.

Now, the first object can be drawn. After that, we will draw the second object. Before we start we need to set up the occlusion query to count the drawn pixels. We also need to use the stencil buffer created in the previous step and set the GPU to draw only if the stencil buffer is non-zero. We don’t need to update any buffers at this point.

After the second object is drawn, the pixel count returned by the occlusion query tells how many pixels overlap. For most purposes, we can assume a non-zero value means the two objects collide3.


Figure 2.

Figure 3.

Figure 4.

Consider the above example. Figure 2 shows two objects as seen on screen. Figure 3 shows the stencil derived by drawing only the green (right) object. Figure 4 shows what will be drawn of the red (left) object if we limit the rendering to drawing on the stencil (the occlusion query will tell us six pixels were drawn).

Sprites

For sprite objects that consist of only one quad and an alpha blended texture with transparent area representing the area that cannot collide with anything, the same result can be achieved by setting the alpha testing to discard pixels below a certain tolerance. This will then avoid updating the stencil buffer on the whole area of the quad.

Optimizations

The stencil buffer can be created to contain the collision area of e.g. every enemy currently on the screen and then testing with the player object. This avoids the necessity to test between every object individually, which can be costly since the occlusion query has to finish before the next query can start. If the objects on the screen can be grouped to a handful of categories, such as the player, the enemies, player bullets and so on, multiple objects can be tested simultaneously where it is not important to know exactly which two objects collided (e.g. when deciding whether to kill the player which in a shooter game generally is because the player collides with the background, an enemy bullet or an enemy — all of which would be drawn in the same stencil buffer).

Ideally, the above can be done so that every object group has its own stencil buffer. This then makes it possible to create the stencil and start the queries in their respective buffers, do something useful while they execute and then query for the occlusion query results.

Caveats

Most of all, doing collision detection with occlusion queries is admittedly a curiosity. There are many, many ways to do collisions faster and most likely with less technicalities. Using a simple rectangle (a cube or a sphere in 3D applications) to test collisions between complex objects has been used since the first video games and it still provides acceptable accuracy. Indeed, some games even use an extremely small collision area (e.g. a single pixel) to test collisions with larger objects with great success. Additionally, the algorithm is potentially a bottleneck, especially when triple buffering etc. are used since occlusion queries generally are started after the previous frame is drawn and then read when the next frame is drawn (i.e. it’s asyncronous). This limits either the algorithm accuracy for real time (frame accuracy) or the framerate since we may have to wait for the query to finish for a relatively long time.

A serious consideration is to use the occlusion query algorithm to test between a complex object, e.g. with a large end of level boss with a complex, changing shape and use a simpler geometry based algoritm to test between hundreds of bullets. A hybrid algorithm could even first make an occlusion query to know which objects collide and then use a different algorithm to find out more about the collision.

This is inherently a 2D algorithm. The GPU sees any situations in which two objects overlap as a collision, as seen from the location of the camera. This if fine for side-scrollers et cetera, which also benefit from pixel perfect (fair, predictable) collisions, and other situations in which all the objects to be tested are on the same plane. Multiple depth levels (e.g. foreground objects never collide with background items) improve the situation and so does drawing only the parts of the objects that are between specified depth levels4.

Another possible problem is that the screen resolution may be different between systems, which makes the algorithm have different levels of accuracy. This can be avoided by doing the checks in a fixed resolution. Limiting the collision buffer resolution also improves the algorithm speed in cases the GPU fillrate is a bottleneck.

Finally, some older systems may not support occlusion queries or stencil buffers. As of 2008, this is increasingly rare but should be taken into consideration.

Appendix A. Source code for OpenGL

The following is source code extracted from a proof of a concept/prototype game written in C++ using OpenGL. The source code should be self explanatory.

The following builds the bounding rectangle for a object:

BoundBox box=object->GetBoundingBox();

object->DoObjectTranslations();
	
glGetDoublev(GL_MODELVIEW_MATRIX, modelViewMatrix);
glGetDoublev(GL_PROJECTION_MATRIX, projectionMatrix);
glGetIntegerv(GL_VIEWPORT, viewport);

for (int i=0;i<8;i++) 
{
    GLdouble screenX, screenY, screenZ;
			
    vec3 c=box.Corner(i);

    gluProject(c.x(), c.y(), c.z(), 
        modelViewMatrix, projectionMatrix, viewport, 
        &screenX, &screenY, &screenZ);
					    
    maxX=max((int)screenX,maxY);
    maxY=max((int)screenY,maxY);
    minX=min((int)screenX,minX); 
    minY=min((int)screenY,minY);
}

rect = Rect(minX,minY,maxX-minX, maxY-minY);

The following can be used to set the rendering mode before drawing the object on the screen, on the stencil buffer or when making the occlusion query (note how we disable most of the rendering when drawing something that will not be visible to the player, also notice how the stencil buffer is cleared if we enable stencil drawing mode — using scissor makes this efficient):

void GfxManager::SetRenderMode(RenderMode mode) {
  if (mode==STENCIL) {
    glDepthFunc(GL_ALWAYS);
    glDisable(GL_LIGHTING);
    glClear(GL_STENCIL_BUFFER_BIT);	
    glEnable(GL_STENCIL_TEST);
    glDisable(GL_DEPTH_TEST);
    glStencilFunc(GL_ALWAYS, 1, 1);						
    glStencilOp(GL_REPLACE, GL_REPLACE, GL_REPLACE);				
    glColorMask(0,0,0,0);	
  } else if (mode==OCCLUSION) {
    glDepthFunc(GL_ALWAYS);
    glDisable(GL_DEPTH_TEST);	
    glDisable(GL_LIGHTING);
    glEnable(GL_SCISSOR_TEST);
    glEnable(GL_STENCIL_TEST);			
    glStencilFunc(GL_EQUAL, 1, 1);						
    glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);		
    glColorMask(0,0,0,0);			
    glBeginQueryARB(GL_SAMPLES_PASSED_ARB, m_OccId);
  } else {
    // Set normal rendering mode here (enable lighting etc.)
  }
}

Similarly, the following is used to end drawing (specifically to end the collision testing, at which the function returns the number of pixels drawn)…

int GfxManager::FinishRenderMode(RenderMode mode) {
  if (mode==OCCLUSION) {
    glEndQueryARB( GL_SAMPLES_PASSED_ARB );
    GLuint occ=0;
    glGetQueryObjectuivARB( m_OccId, GL_QUERY_RESULT_ARB, &occ);
    return (int)occ;
  } else {
    return 0;
  }
}

… using something like this:

int GfxManager::DrawObject(int oid,vec3 pos,vec3 rot,RenderMode mode) {
  SetRenderMode(mode);
  Draw3DObject(oid, pos, rot);
  return FinishRenderMode(mode);
}

This is from the main loop, it simply goes through all objects in the game. Notice how we first prepare the collision checking for the first object to be tested (i.e. create the stencil as in step 2 of the algorithm).

for (unsigned int a=0;a<m_Objects.size();a++) {
  m_Objects[a]->PrepareCollide();
  for (unsigned int b=a+1;b<m_Objects.size();b++) {
    if (m_Objects[a]->TestCollide(m_Objects[b])) {
      // We have a collision
    }	
  }
  m_Objects[a]->FinishCollide();
}

Note that DrawObject is the same method as we use to draw the visible object on the screen. The only thing that differs is that the drawing mode is set to stencil or occlusion query. Also worth noting is how we use the rectangle to set the scissor to further reduce the workload.

void GfxObject::PrepareCollide() {
  GetGfxManager()->SetScissor(this->GetBoundingRect());
  GetGfxManager()->DrawObject(m_GfxId,GetPosition(),GetRotation(),STENCIL);
}

void GfxObject::FinishCollide() {
  // We simply reset the scissor
  GetGfxManager()->SetScissor();
}

int GfxObject::DrawCollide() {
  // We could set the scissor here to even smaller area, the overlapping area
  return GetGfxManager()->DrawObject(m_GfxId,GetPosition(),GetRotation(),OCCLUSION);
}

bool GfxObject::TestCollide(Object *obj) {
  Rect a=GetBoundingRect();
  Rect b=obj->GetBoundingRect();
	
  // No need for further collision testing if the rectangles
  // don't overlap
  if (!a.TestCollide(b)) return false;
	
  // We have a collision if any pixels were drawn
  return obj->DrawCollide() > 0;
}

Links

  1. To speed up the checks done on the GPU, we can set the scissor rectangle to the overlapping area. This helps in cases in which the overlapping area is small compared to the complete area of the object.
  2. OpenGL has gluProject(), DirectX has D3DXVecProject()
  3. It may be useful to consider a larger tolerance for fairness’ sake
  4. E.g. setting the near and far clipping planes to the distance of the second object (assuming it won’t be a problem that the clipping results in objects that have a hole)