kometbomb

Programming and stuff.

Category Archives: Programming

17 Jul

Nanopond Screensaver

[This is an archive post from my old homepage]

For those who don’t know what Nanopond is: Adam Ierymenko’s Nanopond a minimal (absolutely tiny) artificial life system based on randomly mutating and evolving computer programs that eventually get more and more efficient in copying their program thanks to natural selection. While it does not have as diverse dynamic as Ray’s Tierra but it is more interesting to look at.

See a time-lapse video of evolution in action:

This screensaver is a quick hack of Nanopond that allows it’s use as a Windows screensaver. Does not support passwords or anything fancy but it saves the pond when the saver exits. Delete nanopond.1 in the Windows directory to start over.

The pond size (and the screen resolution) is the standard 640×480, but the pond depth has been set to 64 to minimize the pond state file size (with the default settings it’s around 80 megabytes, now around 20 MB).

Download – Binaries and the source code. Extract nanopond.scr (optimized for Pentium MMX) or nanopond_athlonxp.scr (optimized for AMD Athlon XP) in your Windows directory. You need the SDL libraries.

11 Jul

Hardware-accelerated 2D collision detection in OpenGL

NB: Here is a better post about the below algorithm. Includes source code.

The idea

Did you know you can do pixel accurate collision detection using the OpenGL stencil buffer and occlusion queries? I got this idea while working on a 2D/3D game engine (think of a side-scroller but with 3D objects).

The idea is actually very similar to how you do collision checking on most 8-bit computers and consoles: when drawing the sprites on screen, the graphics chip automatically keeps track if it drew a pixel on something that was already there. OpenGL doesn’t do that by default (especially because this is not a 3D method) but we can fake it. This is how I do it:

  1. Each model has it’s bounding box which is translated and rotated with the object

  2. Each potential collision between two objects is checked:

    1. Project each corner of the bounding box on the screen plane (gluProject()). You can project all the object vertices if you want more accuracy

    2. Get the smallest rectangle that fits around the projected points

    3. Using this rectangle check if the objects are anywhere near each other, i.e. check if the rectangles overlap. If the rectangles do overlap:

      1. Use the first object to draw a stencil shape (i.e. use the same drawing code you use to draw the object on the screen but enable GL_STENCIL_TEST and put the stencil function in the GL_ALWAYS mode). You need to clear the stencil buffer, I do this with the scissor area set so I clear just the needed area.

      2. Use the second object to do an occlusion query using the stencil – draw only if the stencil is set (again, reuse the code for drawing the object in general but enable stencil test and start the occlusion query before drawing).

      3. The objects collide if there are any pixels drawn, i.e. the objects shared some pixels and the query returns a non-zero value

  3. Draw the scene, next frame etc.

(Text on yellow is what I’m talking about here)

Discussion and improvements


Now, this isn’t exactly a fast technique and you probably will have good results with normal multiple bounding box/rectangle checking even if that isn’t as accurate as this method. However, this should work with anything you can draw on the screen with OpenGL, including alpha textures (i.e. 2D sprites) and you don’t need to keep track of any extra bounding boxes.

One thing I like is that you automatically get a bit more sophisticated collision checking: even if this method is inherently 2D, you can use the far and near clipping planes to make the objects not collide if an object is actually behind another object. If you use perspective, you can stop the player colliding with a floor that stretches to infinity (which of course when projected in 2D only goes from the bottom of the screen to the middle of the screen) – just draw the part of the floor that is at the same the depth as the player.

You can also optimize this a lot. In my case, I get more speed using the rectangle check above and limiting collisions (e.g. no check between two enemies, checking only player and landscape collisions, testing only the rectangle if it is a static square tile etc.). I also don’t draw the stencil every time I check an object pair and obviously cache rects if the orientation of the object doesn’t change much.

Not much examples here but you should get this working in a few days by just googling for occlusion queries, stencil buffer and OpenGL (assuming you already do know how to draw stuff on screen and realize how the object translation and rotation works etc.). There are a ton of tutorials on the Net about drawing reflections and whatnot using stencil, which is precisely what we do here, only that we don’t show the reflection and only count the pixels.

Links

14 May

-mthreads, -mthreads, -mthreads…

This falls in the obvious category but I’m posting this just that someone will see this even by accident: always use -mthreads when using threads under MinGW. I repeat (so that I remember this in future): always use -mthreads when using threads under MinGW. I just spent hours using gdb instead of -mthreads.

I.e.:

g++ -mthreads -o game.exe game.c

The mentioned option makes MinGW use thread-safe stuff internally. It is not enough a library claims to be thread-safe (well, actually it probably claims to be thread-safe as long as the runtime providing malloc et al is safe, which indeed is not the case when not using -mthreads).

At least Viewer2 is fast now.

29 Apr

Automatic build numbers

I needed a program that would keep track of a single number, increase it on demand and output the number to the standard output. This is because I don’t really like using any IDEs (at least anything for MinGW) and so I don’t have all the modern luxuries like automatic build numbers (a sequential number that increases every time the program gets built). I have only an editor, a compiler, and make. I have included the packaging of the releases in the makefile (i.e. make & make installer). It’s eventually confusing to name all of your installers with the same filename, so that’s what I need the build number for.

The program I wrote, called bn, stores the build number in a single-line file. bn filename increases the number in filename and outputs the result. If you add noinc after the filename only the current number is output. In the makefile, add bn buildnumber in the rule that builds your executable:

program.exe: program.c
  gcc program.c -o program.exe
  bn buildnumber

Every time program.exe gets built, the number in the file buildnumber increases by one. I use the limited command line interface in Windows but the make I use has the more capable shell sh built-in, so I can have a rule like this (cp -f is the same as copy /y in sh):

installer: program.exe
  makensis program.nsi   # outputs the installer as installer.exe
  cp -f installer.exe installer-build-`bn buildnumber noinc`.exe

In sh, everything that is between two grave accents (`) gets treated as a separate command as you would type it in. However, this makes sh substitute bn buildnumber noinc with whatever the command prints in stdout. So, effectively the line in the makefile is seen as (assuming the build number is 1000):

  cp -f installer.exe installer-build-1000.exe

Note: You have to manually create a file named buildnumber. Just save a text file with a single line with the number that you want to start counting from. This is so that you don’t accidentally overwrite something.

Scratch one tedious manual task per release! You can also use this to inject numbers in the actual executable or keep track of times a program is run (by using a batch file).

Download the program with the source code (in C)