[OLPC-Games] Efficient general purpose tile engine, and a cellular automata machine

[Don Hopkins]

I'm developing a general purpose tile engine that can be used for 
cellular automata, and other tile based games, including all of 
SimCity's needs: the close-up map editor that's fully zoomable to any 
scale, with cursor and sprite overlays, and the overall map view, with 
transparent overlays to show stuff like population density, traffic, etc.

Thanks to all the helpful advice I've received, I've re-written my tile 
engine to use "nativeTarget = ctx.get_target()" to get the native 565 
xlib surface from the cairo context associated with the gtk widget, and 
then use "tilesSurface = 
nativeTarget.create_similar(cairo.CONTEXT_COLOR, tilesWidth, 
tilesHeight)" to create a 565 xlib surface for the tiles in the server. 
The I copied the tiles there to convert them from 888 to 565. So then it 
can copy them quickly onto the screen or an offscreen 565 xlib surface, 
where I can draw on top of them efficiently with Cairo, to implement 
efficient offscreen composition and overlays!

The tile engine is designed to provide an efficient 565 critical path to 
the screen, support scaling the tiles to any integral number of pixels, 
and it has a fast path for unscaled tiles. If the scale is 1:1, it just 
copies the entire tile collection into an xlib 565 surface in the 
server, to convert them all at once up front. If the scale is not 1:1, 
then it creates a temporary 888 single tile sized surface to clip out 
each tile, then clips and copies it into the 565 tile surface (a single 
surface that contains all tiles) in the server. That way the tiles are 
cleanly sliced apart so there is no possibility of bleeding between 
adjacent tiles when they're scaled (and resampled). [Maybe I'm just 
being paranoid. If it turns out there is no bleeding problem then I can 
simplify the code. But I'm afraid that if you just scale and resample 
all the tiles together they might bleed into each other along the edges.]

The tile engine also supports an alternative efficient pixel based 
renderer for single pixel sized tiles (which uses a surface as a color 
map, like the tile map but each tile is 1x1). The API is a bit different 
because instead of passing in a cairo context to draw with, you pass in 
a 24 bit image surface that it draws into, which you can then draw onto 
the screen yourself by scaling and clipping it however necessary. (Of 
course that does require Cairo or the X server to resample it, but at 
least it minimizes the size of the image it has to convert.) It could 
easily support 32 bit rgba images, too, so colormaps could contain 
transparency to produce translucent overlays with opaque bands (to make 
iso contour maps for population density and other overlays).

Since the colormaps and tiles are cairo surfaces, it's easy to process 
and render dynamic colormaps and tiles!

Question: How to I tell Cairo to use FILTER_FAST instead of FILTER_BEST? 
The set_filter method is supported by the cairo pattern object, but not 
the surface or the context. How to I wrangle a surface into a pattern, 
or use a pattern instead of a surface, or whatever I have to do to 
switch to fast nearest neighbor interpolation mode when scaling a surface?

It supports both pixels based color maps as well as bigger tile sets, 
because I want to be able to zoom into any scale, and have it still look 
nice and run fast. That way you can supply an "iconified" pixel based 
color map for use at small scales, as well a nice looking tiles that 
will be used at closer zooms. The higher level Python part of the tile 
engine lets you specify a minimum and maximum scale between which to 
cross-fade between the tiles and the pixels, so you can have your cake 
and eat it too. When you're zoomed way out, you see the pixels scaled to 
the exact zoom, softly interpolated with smooth solid colors. As you 
zoom in and it gets big enough to use the tiles, they fade in underneath 
the pixels with more detail, with the pixel colors overlayed 
transparently on top of the tiles. It looks really cool with the smooth 
interpolation, like the detailed tiles have colored LEDs that light up 
the cell area.

I made a demo application that uses my cellular automata machine engine 
(currently it runs the von Neumann 29 state cellular automata, but it 
supports lots of other rules). The initial configuration is an 
"autoinitializing exclusive or gate" which I like because it has lots of 
pretty blinking lights. I've started writing a 
panning/zooming/cursor/tile/editing user interface.

I've put up a tar file with the latest code drop:

http://www.DonHopkins.com/home/cam.tgz

The way to build and run it is:

Untar the "cam" directory into your "sugar-jhbuild/source" directory.
Go into the directory "sugar-jhbuild/source/cam".
Edit the file autogen-sugar.sh to contain the absolute path to your 
sugar-jhbuild directory.
Run the script "./autogen-sugar.sh" to configure the project.
Build and install the project with "make install".
Go into the directory "sugar-jhbuild/source/cam/cam/test".
Run the script "python test.py".
A small window will open up.
Click in the window to set the input focus.
Press the left mouse button and drag to pan the cells.
Press "i" to zoom in, "o" to zoom out, and "r" to reset the zoom.
Once you zoom out with "o" a few notches you will see the pixel overlay 
fading in, and after enough zooming out it will be solid scaled pixels.
You can zoom into the tiles with "i". There is no limit on the zoom but 
the X server will barf after a while if you keep zooming.
Press the "d" key to toggle debug inset mode, which insets the view by a 
bit and draws a red rectangle where the clip of the view would be, so 
you can see how it optimizes the cells it draws.
It only draws exactly the cells it needs, into an offscreen buffer, then 
composes the outside background and the cursor on top of that in another 
buffer, then copies that to the screen.

Here are some pictures at various zooms, showing the cross fading and 
the debug inset mode:

http://www.DonHopkins.com/home/cam-1.png
http://www.DonHopkins.com/home/cam-2.png
http://www.DonHopkins.com/home/cam-3.png
http://www.DonHopkins.com/home/cam-4.png
http://www.DonHopkins.com/home/cam-5.png

    -Don

Thanks a lot for all the advice, which I have tried to follow!

> Right.  Make sure the whole critical path is 16-bit 565.
>   

>> Drawing a single rectangle, (if pixel aligned---that is, just using
>> integer coordinates and an identity transformation), has lots of
>> fast-path treatment in cairo, so please take advantage of it. You can
>> do that with either:
>>
>> 	cairo_rectangle
>> 	cairo_clip
>>
>> to setup the clipping and then cairo_paint to do the painting, or
>> just:
>>
>> 	cairo_rectangle
>> 	cairo_fill
>>
>> to draw the part you want. Either way you should be hitting the same
>> path in cairo to ask the X server to do very efficient things.
>>
>>     
>> OK, so that's giving you image surfaces, and that's causing the slow
>> conversion when drawing to X. So the best would be to do that just
>> once, (get your data uploaded into an xlib surface, and then draw from
>> there).
>>     
>
> Correct; about the only thing you can do here is use create_similar() on
> the xlib _window_ surface, draw your 24bpp image surface to that, and
> cache the 565 xlib surface for all further drawing.  Note that you will
> _not_ get alpha because the surface is 565.
>
>   

>> For a cairo context you can call cairo_get_target, (probably
>> context.get_target in python), to get the surface it's targeting. So
>> that should give you the surface you need from which you can call
>> create_similar. And for the case of a gdk drawable you can call
>> gdk_cairo_create, and then cairo_get_target. (I do think it's a little
>> annoying that GTK+ doesn't have a direct way to create a cairo surface
>> from a GDK drawable, but the gdk_cairo_create;cairo_get_target
>> approach works fine---even if its not quite obvious).
>>     

> Again, ensure that _any_ surfaces you use in your critical paths are
> 565.  If anything is not 565, you'll be subject to Xlib having to smash
> an 888 pixmap down to 565, and that's not very fast, even with MMX.
>   

>> Anyway, I hope that all works out well for you. And I'm looking
>> forward to hearing what kinds of performance improvements you get from
>> using cairo xlib surfaces of the desired depth.
>>
>> -Carl
>>     

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.laptop.org/pipermail/games/attachments/20070424/fdd87e75/attachment-0001.htm