Arctic Paint weblog

Voronoi diagrams in C++

2012-05-09T14:45:00.000-05:00

Why? I can't tell you... or wont? Anyways, I was looking for an implementation that was C++ friendly, didn't leak memory and let me easily build triangles from the resulting computation (for use in OpenGL).

I found an implementation that did none of those. But it was fast, and close-ish to C++ friendly... ish.

It was open source so I encapsilated it all, converted all those pesky malloc and frees to... not malloc and frees (which indirectly fixed the memory issues) and changed it to output the result to something a little more useful.

And now I'm sharing the result with you. https://bitbucket.org/jlm/voronoi-c/

Why minecraft's terrain loading is slow

2012-05-06T12:27:00.000-05:00

Fuzzycraft - not minecraft!

Oh I don't know, it's in Java? (Sorry, just getting the flame-bait out of the way.)

It's an interesting problem; sure it's just a bunch of cubes - but who wants to stop at a few thousand of them? You want a massive world where you can potentially see tens of thousands of theses blocks at a time. And due to its nature you're left without many of the techniques often used to optimize terrain rendering.

Sounds like a good opportunity to get a little more comfortable with OpengGL. Enter fuzzycraft-webgl; poorly textured terrain in all it's blocky glory! This ended up being horribly slow. More on that in a bit.

Trying out minecraft; the terrain seems to load very slowly. With my fairly high-end GPU I'm pretty sure OpenGL isn't the bottleneck here. Generating what blocks go where isn't slow either. (Test it by toggling the graphics options between fancy and fast; you can still see the chunks appearing one by one, oh so slowly) The only thing left is the process of building the geometry to send to the GPU.

I wanted to see if I could do better. Coffeescript was something I was wanting to try out and I always like to see how far WebGL can go. Turns out, getting good FPS was next to impossible with larger worlds. Generating the blocks of geometry to send to the GPU wasn't too bad; although to be fair, I had 8 cores chewing through it via web-workers.

Really, using OpenGL just works best in C. I was confident that it was possible to get it fast; both generating and rendering it. So I re-wrote it all in C++. There's really not a whole lot to say other than yes, it is very possible. There are still a few optimization I could do to make it run even faster. I may do them someday; but for now I've satisfied my curiosity.

So why does minecraft take so long to get those chunks of vertices to the GPU? I don't really know. Part of me wants to decompile minecraft's bytecode and find out. But I work with way to much Java as it is at my day job; and honestly, it's not a language I adore.

Flocking in javascript

2011-08-05T15:27:00.000-05:00

Flocking is one of those things I've been meaning to play with for a while. So here is my crude result; flocking in javascript. I'm not quite sure what type of flock it's simulating... definitely not birds though. I'm calling them noids.

Python markdown

2011-07-28T14:50:00.001-05:00

$ easy_install mark3
$ python -m mark3 < myfile.text

Or used as a python module:

from mark3.markdown import markdown
html_output = markdown(raw_text)

I wanted a markdown to html converter for python3 that was lightweight and fast. So I created mark3.
Much to my surprise I was able to get mark3 quite a lot faster than existing libraries (~7x faster).

$ hg clone https://bitbucket.org/jlm/mark3
$ cd mark3
$ python tests/speed_test.py

See the README for details on how mark3 differs from the official markdown implementation.

Things I learned about html5 canvas

2011-07-09T13:17:00.001-05:00

WebGL is awesome and all, but it's far less portable. For example, my AMD card has been blacklisted on linux. So I figured I'd revisit trying to make a real-time game with 2D canvas.
Check out the game so far.

Off-Screen Rendering

Off-screen rendering is both cheep and easy to use. Here I'm using it to render map tiles to a single image. Since the tiles are (mostly) static I don't need to be redrawing them individually each frame.

setInterval is not guaranteed to call at an exact interval

So I already knew this, but I forget how much accurate timing matters for real-time games. To the point, calculate time-past yourself with the getTime function:

var dt = new Date().getTime() - last_time;

Still use setInterval for scheduling logic and render functions, just don't expect the timeout values to be consistent with actual times.

Keep an eye on object allocation/deallocation

You don't normally have to think about allocating memory in javascript like you would in C. The problem comes when you're creating a real-time game and you notice it periodically skipping a beat, resulting in jerky rendering. This is caused by javascript's garbage collector, basically, blocking your program as it cleans up unused memory.
The way to avoid this problem is to limit the number objects you create and then discard. Or an easy solution; just use Chrome. It's significantly better about it.

It's better on Google Chrome

Simply put, Google Chrome is better for canvas based games. Dramatically better in some situations (or rather, Firefox is dramatically worse in some situations).

Canvas off-screen rendering

2011-07-07T10:01:00.017-05:00

Rendering to an off-screen buffer can be a great way to cache expensive drawing operations or preform post processing effects. html5's canvas element lets us do it easily.

var buffer = document.createElement('canvas');
var buffer_ctx = buffer.getContext('2d');
// ... draw to buffer_ctx ...

Then simply use our new buffer as an image:

main_ctx.drawImage(buffer, 0, 0);

For example, I can use an off-screen buffer to apply an expensive bloom effect:

Playing with WebGL

2011-06-02T08:13:00.010-05:00

OpenGL is one of those things I like to play with from time to time. So naturally I wanted to check out WebGL now that Chrome and Firefox support it.

It's fun being able to use javascript and web technology in conjunction with OpenGL. Building GUIs using raw SDL/OpenGL was always rather a pain for me. I don't even like how standard toolkits work (GTK+, Qt etc). So being able to use HTML widgets and jQuery on top of my 3D scene is really awesome.

Unfortunately it's noticeably slower than an equivalent program running natively. When profiling, the GL calls seemed to be the bottleneck. A bit less so on Windows than Linux, although that may have been due to better driver support on the former.

So like usual, optimizing comes down to reducing the number of GL calls you make per frame.

The javascript logic and matrix transformations ran very fast. This was the case for both Firefox and Chrome and was a very pleasant surprise.

You can try out what I made at http://arcticpaint.com/planes/, play with the source or what ever. It's all under public domain (with the exception of the glmatrix library which has a BSD license).

I had also started toying with the idea of a turn-based game http://arcticpaint.com/islands/ (very, very far from completion)

If you want to check out more webgl stuff http://learningwebgl.com is a great resource. They also have some decent tutorials that are easy to follow along if you're new to OpenGL.

A casual game service

2010-11-04T13:16:00.002-05:00

I recently started a new project called Gervice. My goal is to allow you to easily plug your standard "game" features into a web based games. With a single function call you can load and save state, log scores and move count and integrate with an online community.

Pure Python to deb and rpm

2009-07-26T14:13:00.005-05:00

I recently started supporting Number Drill, my math drill software, for Linux a few days ago. Number Drill is a pure python program with the external dependencies of pygame, rabbyt, PyOpenGL and a few others. All of which were in the Debian and Fedora repositories.

I originally tried using cx_Freeze to make a binary to distribute. But I kept on running into major problems with this method. And as it ended up I would have to include a plethora of .so files (such as all of pygame and everything that it depends on, libssl and everything it depends on etc) just to avoid version conflicts that resulted in segfaults. Not to mention the resulting package ending up far larger than it should be.

That was about the time Matthew suggested just distributing the pyc files (gasp! I know, it's not open source) and letting package systems like deb and rpm handle dependencies. This method has ended up working almost perfectly. Both Ubuntu 9.04 and Fedora 11 have all the dependencies I require available. The resulting packages are very small (no binaries included, just the python byte code).

The only disadvantage is that it requires the latest versions of Ubuntu or Fedora (as of today) as they are the only releases that have new enough versions of my dependencies.

We wrote a bash script that automatically packages up a pure python program into both a deb and rpm. If you are interested in here it is: http://arcticpaint.com/static/blog/python_to_deb_rpm.sh

I believe that this method of packaging is even more effective in the open source world. It essentially just makes getting your program to run from source as easy as possible.

PyOpenGL 3.0 with py2exe

2009-05-16T09:54:00.004-05:00

One of the major hindrances to using PyOpenGL before 3.0 was released (not python 3.0) was that packaging it with py2exe was next to impossible. Thankfully with the release of PyOpenGL 3.0 it is easy. Just include these two imports in one of your project files:

from ctypes import util
try:
    from OpenGL.platform import win32
except AttributeError:
    pass

That will tell py2exe which part of PyOpenGL to include. Otherwise you have to copy them over manually. Be sure to have the try and except around all win32 imports so your program remains cross platform.

Better pygame and rabbyt texture loading

2009-05-07T13:23:00.010-05:00

For one of my current projects I'm using rabbyt in conjunction with pygame. With the default texture loading, if your image dimensions are not powers of two your resulting sprite will be blurry. Pyglet fixes this by creating a new texture with correct dimensions, blitting your image onto the texture and then setting the texture coordinates. That way OpenGL doesn't do its blurry scaling job on your image.

Well, pygame's texture loading doesn't do that. So you either go to great pains to make sure all your textures are powers of two (which can be annoying when you don't want your sprites to be those sizes) or do the coordinate mapping manually.

Here is a custom texture loading hook that does this on all textures when you load them:

from __future__ import division
import pygame, rabbyt, sys, os
from rabbyt._rabbyt import load_texture

def next_pow2( n ):
 """
 Find the next power of two.
 """
 n -= 1
 n = n | (n >> 1)
 n = n | (n >> 2)
 n = n | (n >> 4)
 n = n | (n >> 8)
 n = n | (n >> 16) 
 n += 1
 return n


class Tex:
 def __init__(self):
     self.id = 0
     self.width = 0
     self.height = 0
     self.tex_coords = (0,0,0,0)

_texture_cache = {}
def load_and_size(filename, filter=True, mipmap=True):
 if filename not in _texture_cache:
     pygame = __import__("pygame", {},{},[])
     if os.path.exists(filename):
         img = pygame.image.load(filename)
     else:
         img = pygame.image.load(os.path.join(data_directory, filename))
  
     t = Tex()
     t.width,t.height = size = list(img.get_size())
     size[0] = next_pow2(size[0])
     size[1] = next_pow2(size[1])
     t.tex_coords = (0,t.height/size[1],t.width/size[0],0)
      
     n = pygame.Surface(size, pygame.SRCALPHA|pygame.HWSURFACE, img)
     n.blit(img, (0,size[1]-t.height))
  
     data = pygame.image.tostring(n, 'RGBA', True)
     t.id = load_texture(data, size, "RGBA", filter, mipmap)
     _texture_cache[filename] = t
 return _texture_cache[filename]

rabbyt.set_load_texture_file_hook(load_and_size)

Gondola and 4 types of players

2009-03-31T12:05:00.003-05:00

Gondola was our pyweek 7 entry. Based on feedback there and elsewhere I have concluded that, at least when it comes to Gondola, there are four types of players.

1. Those that wanted to optimize their networks. A player from this group can spend hours playing on just one map, trying to make things run better. The ideal group to be in to enjoy Gondola.

2. Those that wanted to solve a puzzle. They lay out their networks and then they're done. Either they don't realize it or it just doesn't appeal to them to go back and optimize their routs. Keeping these players going takes a lot of large and complex maps. Maps also require some sort of goal; something to work towards and be able to fail at doing. Which is something Gondola's current selection of maps does not provide.

3. Those that just want explosions. Gondola is similar to simcity in the sense that it is a simulation and a toy. There is no real goal other than to do better that you have before. But one thing that Gondola doesn't have that simcity does is explosions. There are no futureistic robots that come and wipe out your infrustructor. No fires, tordadoes or anything else destructive.

4. Those that just didn't get it. I guess the game, for some people, isn't explained well enough. I don't blame them at all because the tutorial really isn't that comprehensive. I wish I knew in what way they didn't get it though, so I could address the confusing aspects. A game, idealy, should not require any explination or even a tutorial in order to start playing; Something I am still trying to figure out how to do.

Zooming and performance

2009-03-07T11:14:00.010-06:00

One problem I was continually having with SnowballZ was zooming. The further you zoomed out the slower it went (as, obviously, it had to draw everything). To the point where zoomed all the way in would give me 120fps and all the way out 30fps. Unacceptable.

I started working on making it fade into a paper-looking map when zooming out; So I could strip out the trees and terrain. But on the fly cartography that looks even half way decent is a lot of work. That's when Matthew suggested rendering the entire map to a texture. Bingo.

I created a function that set the viewport to cover the entire map and rendered just the terrain, trees and other decor to an off-screen buffer; Which I then saved to a texture. Now when the player zooms out to a certain point it switches to drawing that one texture which, compared to a 80,000+ vertex terrain and a couple hundred trees, is much faster.

The one drawback of this method is that it isn't perfectly seamless. But you wouldn't notice the difference unless you were looking for it. I rendered to a 1024x1024 texture so it is a little blurry when you use it too close up. This could be solved by rendering it to a larger texture but my concern comes when you have a map that is bigger than my 150x150 tiles (odd number, I know).

If there is any interest in seeing how I did it here it is:
(slightly modified for clarity out of context, my thanks to Richard Jones for showing how to do this on the pyglet mailing list)

# create our frame buffer
fbo = GLuint()
glGenFramebuffersEXT(1, ctypes.byref(fbo))
glBindFramebufferEXT(GL_FRAMEBUFFER_EXT, fbo)

# allocate a texture and add to the frame buffer
tex = image.Texture.create_for_size(GL_TEXTURE_2D, 1024, 1024, GL_RGB)
glBindTexture(GL_TEXTURE_2D, tex.id)
glFramebufferTexture2DEXT(GL_FRAMEBUFFER_EXT, GL_COLOR_ATTACHMENT0_EXT,
GL_TEXTURE_2D, tex.id, 0)
status = glCheckFramebufferStatusEXT(GL_FRAMEBUFFER_EXT)
assert status == GL_FRAMEBUFFER_COMPLETE_EXT

# now render
glBindFramebufferEXT(GL_FRAMEBUFFER_EXT, fbo)

# Snipped. This is where I render my map. See lib/map/display.py for full code.

# clean up
glDeleteFramebuffersEXT(1, ctypes.byref(fbo))
self.offscreen_map = rabbyt.Sprite(tex, shape=(0,map_w,map_h,0),
tex_shape=(0,1,1,0))

Using this method requires a certain OpenGL extension that older hardware might not have. You are also limited to a max texture resolution. Which could be an issue when it comes to large maps, even on newer hardware.

A method that avoids both of these problems is to split up your prerendering of the terrain into sections of 512x512 textures. That avoids the sharpness problem. As long as your section resolutions are smaller than your screen size you can render them to the backbuffer and copy that to a texture, which avoids GL extention problems.

This is how I'm doing it:

chunk_res = 2048
chunk_tex_res = 512
num_chunks = (map_w//chunk_res+1, map_h//chunk_res+1)

glClearColor(0,0,0,0)
for x in range(num_chunks[0]):
   for y in range(num_chunks[1]):
       tex = image.Texture.create_for_size(GL_TEXTURE_2D,
               chunk_tex_res, chunk_tex_res, GL_RGB)

       l = x*chunk_res
       t = y*chunk_res+chunk_res
       r = x*chunk_res+chunk_res
       b = y*chunk_res
       glMatrixMode(GL_PROJECTION)
       glLoadIdentity()
       glViewport(0,0,chunk_tex_res,chunk_tex_res)
       glOrtho(l, r, b, t, -1000, 1000)
       glMatrixMode(GL_MODELVIEW)
       glLoadIdentity()
       glClear(GL_COLOR_BUFFER_BIT)

       # (Snipped) Render your map here.

       glBindTexture(GL_TEXTURE_2D, tex.id)
       glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP_TO_EDGE)
       glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP_TO_EDGE)
       glCopyTexImage2D(GL_TEXTURE_2D, 0, GL_RGB, 0, 0,
               chunk_tex_res, chunk_tex_res, 0)

       self.offscreen_chunks[(x,y)] = rabbyt.Sprite(tex,
               x=x*chunk_res, y=y*chunk_res,
               shape=(0,chunk_res, chunk_res, 0))

glViewport(0,0,self.scene.view.width,self.scene.view.height)

Penguins with emotions

2009-02-23T14:17:00.006-06:00

Having the penguins share your emotions is a great way to connect with the player. When your little posse is outnumbered 4 to 1 your penguins don't like it any more than you do!

In fact, as they aren't exactly the most mature little creatures, they'll get down right angry. To the point where they will throw their snowballs faster, harder and further.

When your on the wrong end of the deal you might find it a little annoying how these little guys don't even take time to aim. Normally that would be a good thing but each snowball, even when thrown just in your general direction, will hit at least one of your penguins.

Run my little penguins, run!

2009-02-22T17:22:00.008-06:00

For the next release of snowballz I'm trying to simplify the user interface for two reasons; So it's easier for players to learn and secondly (and most importantly at this point) it's easier for me.

One issue I've always had with controlling the penguins is the run mode. In versions 0.9.x, by middle clicking you tell your penguins to run without stop, regardless of enemies, to where you send them. A great way to get your snowballers behind enemy lines. Apposed to if you were to just right click, in which case they would stop and throw snowballs at enemies.

The one problem I've had with this method is that it isn't obvious. No-one would ever discover it, which could be frustrating.

That's when I remembered hearing about an article talking about networking RTS games. One interesting thing that the article mentioned was to filter out rapid clicking; As players tend to repeatedly tell their units to go to one spot as if it made them get there faster. Thus saving network bandwidth (it was an old article written when most people had dialup).

So why not use this behavior to do what the player expects? So I got rid of the confusing middle click and set it so that when a player rapidly tells their penguins to move it adds a double arrow to the move icon (which specifies run mode). And their penguins will run through the middle of a snowball fight without stopping until they get to where you sent them.

And there we go. The run feature will be discovered just by playing. It doesn't have to be in a tutorial or tips & tricks. Now let's see if I can get the rest of the interface like that.

Our entry in pyweek 7

2008-09-02T14:09:00.000-05:00

This past pyweek (#7) was the first that Matthew and I got to compete in. It was a lot of fun and it resulted in Gondola. Gondola has turned out to be a very fun game; especially if you are the type that likes laid back games such as simcity or transport tycoon … or have an odd passion for optimizing distribution networks.