flocking boids

Hi ... I got a bit stuck with my 3D space game when trying to get real-time impostors right. Impostors are dynamic billboards for rendering hundreds of distant asteroids. After a three week holiday, it was hard getting back into the code, so I put it on hold for now. On the bright side, I started working on a new arcade game that is really 2D, but with a 3D twist. It is inspired by Geometry Wars / |g|ridwars, GridRunner, and another old Jeff Minter game that features four cannons along the screen edges.

An intern that I'm currently working with, pointed out flocking to me. The guy is studying game technolology — you can actually get a master's degree in game technology nowadays, how great is that?

Anyway, flocking, also known as swarming, is a technique reminiscent of particle systems. While particle systems simulate physics models like fireworks, smoke, or fountains (water drops), flocking is an AI system that is great for simulating groups of animals. An impressive YouTube video shows such a simulation of a flock of birds that is under attack by two birds of prey.

On first thought, you might think that group behaviour is programmatically implemented by controlling the group as a whole. This is not true. Every bird (or boid, as the bots are called) in the flock is an autonomous entity sporting its own artificial intelligence.

How is this implemented? Each boid has an area of sight. If it sees it is going to collide with another boid (or object), it will adjust its heading to avoid collision.

At the same time, the boid wants to stay with the group. It does this by adjusting its heading, to get close to others, while trying to match the heading of a boid that is near. As a consequence, the boid will follow others.

Coming from an age when computers were slow, I first thought that this would be too slow to do in real-time. As it turns out, a modern cpu has no problems whatsoever with the little bit of math required for directing each boid. A pitfall is to have a boid influence another, and recursing because this action influences another, and ... You should not try to solve a mathematical puzzle here. Instead, focus on only one boid at a time and have it make the decision of how to adjust its heading. Do this for every boid, every discrete time step.

I implemented the AI rules in 2D in a game, and while the result is not as impressive as the flock of birds video, it is kind of cool. I started out by making sure that the monsters (or boids) would no longer pass through each other. This is done with a simple circle collision test. When a monster collides, it chooses another direction to move in. Once this was working, changing the code to get flocking behaviour was rather easy: increase the collision radius (area of sight) and adjust the direction only slightly rather than choosing an entirely different direction.

One problem I ran into was that the play area in this game is small and I don't want monsters to fly off the screen. So, the monster had to turn at the edges. Again, increase the area of sight, and have it adjust the direction.

In the game, the gliders (paper airplane models) flock together, while the magenta thargoids are going around like bumper cars, and are disturbing the gliders. The yellow cubes are stationary obstacles in the arena.

Note that it is possible to extend the AI with more rules, but flocking is a technique that already yields quite amazing results with just a few simple rules.

Vertex Buffer Objects - what you can and can not do with them

In 3D games, models consisting of thousands of vertices and polygons, are rendered to screen at least at 30 frames per second. For every frame, these vertices are transmitted from the memory to the GPU over the bus. For static models, this is a huge waste of time and bus bandwidth, because the vertices are the same for every frame. Why not cache the data in graphics memory and tell the GPU to get it there? This is what vertex buffer objects (VBOs) are all about.

In my 3D space game, I added the 3D model of an asteroid. The model has ~2700 vertices, which is not much at all (by modern standards), but I decided it should be a VBO and enable the code for even higher detailed models.

Never having used VBOs before, I took the safe route and implemented the asteroid first without any VBO code, and rewrote it later to use a VBO. This was a lot of extra work, but there were some lessons learned.

I found the following:

• use GL_TRIANGLE_STRIP for the most efficient way of rendering shapes. However, for most meshes from 3D modelers you would use GL_TRIANGLES. For the asteroid, I use GL_TRIANGLE_STRIP.
• Use glDrawElements() rather than glDrawArrays(). Making an extra array with indices seems more work but is very worthwhile the extra effort.
• I had to include degenerate triangles to stitch multiple triangle strips together. Degenerate triangles are 'fake' triangles that refer to the first vertex in the next triangle strip. (Consider triangle ABC, and degenerate triangle DEE to refer to EFG).
• ARB extensions for VBOs are old-fashioned by now. VBOs have been included in OpenGL for a long time and you can use the functions without the need for meddling with ARB extensions.
• Allocating a new VBO for every type of coordinate is wasteful. Instead, allocate a single VBO to store vertices, texture coordinates, normals, colors, etc. and use glBufferSubData() to place the data into the vertex buffer object.
• If you use glDrawElements(), you must buffer the indices using a separate VBO. The reason for this is that the indices have target GL_ELEMENT_ARRAY_BUFFER. I tried mixing indices into subbuffers (GL_ARRAY_BUFFERs) and it did not work for me.
• If you do not have an array at hand, but generate coordinates on the fly, use glMapBuffer() to get a pointer to memory. Mind that you are not directly writing into graphics memory; the buffer will be copied to graphics memory by glUnmapBuffer().

So, are VBOs the golden egg? Well, no. They are a great way of speeding up the rendering of high poly-count meshes. There are things that VBOs are simply not suited for. This has to do with both the limitations of OpenGL and what it is that you're trying to achieve. For example, I tried loading the stars into a VBO. This turned out not to work very well, because in my code, stars are point sprites, and each star has a specific point size. Since you can not set the point size in a vertex array, it also makes no sense to use a VBO. I sorted the stars by size to draw them as a vertex array nevertheless, but this resulted in a low vertex count per call so it still makes no sense to use a VBO here.

I also noticed that 1D textures do not work in vertex arrays. Maybe I'm using them for the wrong purpose (texturing GL_LINEs) but considering that glBegin/glEnd is practically deprecated there may be a problem here.

Another problem I had was with face culling. This is not the VBOs fault, but I suspect that when you drape a triangle strip into a convex shape, it may show artifacts. Enabling depth testing did not help me here, but disabling face culling did.

Although VBOs are an add-on to vertex arrays, it seems like OpenGL always requires you to turn your code inside out when you want to change something. I stuck to static meshes for now and decided to abstract a VBO class from it, which wasn't exactly easy either. Anyway, here is a link to a site that I used to implement VBOs:

• http://www.ozone3d.net/tutorials/opengl_vbo_p2.php

Real-time rendering a lens flare

After adding a sun to my 3D space flyer, the only thing missing was a cool lens flare special effect. Making a lens flare is not very hard, and the effect looks great. It makes your environment look more realistic, it comes to life.

Oh sunny boy

The sun is by itself worth a paragraph in this blog. When rendering a sun, don't fall into the trap of texturing a sphere with a "sun" texture — this looks very unrealistic. Instead, use a textured quad to display an image of a sun. Photos by NASA are practically unusable here, but the photos do show that the sun as seen from space, is a white ball with a yellowish glow, and has streaks. You can make a sun texture using the GIMP (or Photoshop) and choose Light effects: Nova. Apply radial gradient to fade away to the edges of the image.

When displaying the textured quad in-game, I did not want the sun to visibly rotate as we're rotating the spaceship. The perfect way to do this is to do "cheating spherical billboarding". This ensures that the sun with its streaks remains stationary even when we are rolling the spaceship (and thus, the view). Cheating spherical billboarding works like this:

glPushMatrix();

glTranslatef(position.x, position.y, position.z);

// reset submatrix to identity: do cheating spherical billboarding

glGetFloatv(GL_MODELVIEW_MATRIX, matrix);

matrix[1] = matrix[2] = matrix[4] = matrix[6] = matrix[8] = matrix[9] = 0.0f;

matrix[0] = matrix[5] = matrix[10] = 1.0f;

glLoadMatrixf(matrix);

... draw 2D textured quad here ...

glPopMatrix();

Use additive blending to give the sun the bright intensity that it has.

Shine a light on me

Now that we have a sun, let's get to the lens flare part. A lens flare is a series of rings or circles in the line of sight to a bright flash (like the sun). This line always cuts through the center of the camera. So, knowing the position of the sun and the position of the camera, we can calculate the positions of the flare elements. How many elements you want and what size they should be is up to you.

Note that when looking directly into the sun, the lens flare will be larger than when the sun is off to the side. So, you can use the distance as a measure for scaling the lens flare elements.

When searching the net, you will find that NeHe's tutorial renders a 3D lens flare even though a lens flare is really a 2D special effect, as it occurs in the lens of the camera.

The math for a 3D lens flare is less intuitive than for a 2D lens flare and drawing the flare is easier in 2D, so I implemented it as a 2D image post-processing effect.

The following needs to be taken into consideration:

• when the sun is visible, a lens flare effect should be drawn
• use gluProject() to find the 2D onscreen position of the sun
• gluProject() returns pixel values; scale these to fit your viewport
• the distance between the sun's 2D position and the center of the screen is a measure for the scale of the lens flare elements
• vary color and size of the flare elements
• use additive blending because we are working with light effects
• the sun may be occluded by another object in which case a flare should not be drawn

If there is an object in front of the sun, no lens flare should be drawn. NeHe's tutorial shows that it's easy to do a depth test here by reading a single pixel from the depth buffer using glReadPixel(). The fun part is that in my code the sun is drawn infinitely far away with depth testing disabled, so if the depth buffer contains a value here, there must be an object in front of it.

The easiest way to draw the flare elements evenly spaced over the line of the flare, is to make a vector from it, normalize it, and "travel along" this vector to place the elements.

The code looks just like this:

GLfloat center_x = SCREEN_WIDTH * 0.5f;

GLfloat center_y = SCREEN_HEIGHT * 0.5f;

// screenPos is the onscreen position of the sun

// mind that the pixel coordinates have been scaled

// to fit our viewport

GLfloat dx = center_x - screenPos_x;

GLfloat dy = center_y - screenPos_y;

GLfloat len = sqrt(dx * dx + dy * dy);

// normalize the vector

GLfloat vx = dx / len;

GLfloat vy = dy / len;

// choose a spacing between elements

dx = vx * len * 0.4f;

dy = vy * len * 0.4f;

// note that we already are in 2D (orthogonal)

// mode here

glPushMatrix();

glTranslatef(screenPos.x, screenPos.y, 0);

// travel down the line and draw the elements

for(int i = 0; i < numElements; i++) {

glTranslatef(dx, dy, 0);

draw_flare_element();

}

glPopMatrix();

The result is quite nice. You can make things crazier by adding more circles, starbursts, hexagonal elements, and horizontal blue anamorphic streaks.

Rendering glow

Hi, in the space game that I'm working on lately, I added a gyroscope-like object to help the player orientate him/herself in 3D. This gyroscope is presented as a wireframe sphere with a ring around it. To this gyroscope, I wanted to add a "glow" effect to it so that it looks ultramega cool.

Rendering glow is nothing new, and with some googling you can quickly find descriptions on how to do it. As always, it's easier said than done, especially when you've never rendered glow in your life before — so I like to write a little blog entry about this.

So, how does it work? In essence, just render a blurred copy of all glowing parts in the image, and then do an additive blend of the object. So the steps to take are:

• render glowing parts of scene
• copy rendered image data to a pixel buffer
• apply blur filter
• put blurred image into a texture
• draw texture
• set blending to additive blending
• render scene

I tried reading the pixel data with glReadPixels(), which didn't work for me for some reason (in hindsight, maybe the back buffer was not selected, or maybe some other problem). I read that glReadPixels() is slow and you should use glCopyTexImage2D() anyway. One caveat with glCopyTexImage2D() is that you must call glTexParameter() or it will not work.

Since the image is blurred anyway, it is usually OK to work with a low-res texture (that gets stretched when drawn).

The code for making the texture looks like this (note how I use the home-made PixelBuffer class):

/*

...

start by rendering the glowing parts of your object here

...

*/

// put rendered image into a texture

glEnable(GL_TEXTURE_2D);

glBindTexture(GL_TEXTURE_2D, texture_id);

glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);

glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);

glCopyTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, 0, 0, 64, 64, 0);

// get the pixel data from texture and blur it

PixelBuffer *pixbuf = [[[PixelBuffer alloc] initWithWidth:64 andHeight:64] autorelease];

glGetTexImage(GL_TEXTURE_2D, 0, GL_RGBA, GL_UNSIGNED_BYTE, [pixbuf pixels]);

[pixbuf renderFilter:blur];

// put the blurred image back into the texture

glTexSubImage2D(GL_TEXTURE_2D, 0, 0, 0, 64, 64, GL_RGBA, GL_UNSIGNED_BYTE, [pixbuf pixels]);

Now simply render a quad and texture the blurred image on it. Use alpha blending to make it look better. For the second part, enable additive blending and render the scene again.

glBlendFunc(GL_SRC_ALPHA, GL_ONE);

glEnable(GL_BLEND);

I use GL_SRC_ALPHA rather than GL_ONE, but you really have to try and see whether it makes a difference or not.

For making the blurred texture, I first set the glClearColor() to 0, 0, 0, 0 (even zero alpha). This was needed to get the desired result. You may not need to do this, depending on what it is you're doing, but I mention it here because it was one of those gotchas.

Lastly, many say you need to reset your viewport temporarily to the size of the texture. In this case, I did not need to do this. However, as you add more glowing objects to your scene, it's wise to render all glowing objects in a scene to a single blur-texture in one go. Then draw a fullscreen quad with the blur texture, and off you go.