XMas in summer

How do you render a 3D Christmas tree in Flash?

Papervision is an option, but don’t expect the 3D tree model to look realistic…
This project has a mini, custom-built 3D tree renderer.
It rotates particles around a 3D cone shape, replace those particles with random Bitmap objects of branches, rotate and colorize them randomly, and you get a decent 3D tree feeling.

This build uses 1600 particles, some are dynamic, an they represent pictures which people can upload, sphered within xmas balls.

Click the image to view the 3D tree.
note that the webservice which loads the uploaded xmas balls is currently unavailable, so only the non-decorated tree is shown.

Astar pathfinder with Pixel Bender and Alchemy

draw a maze with the mouse

The biggest limitation was that everything is always grid-based. You would simple flag certain nodes in the grid as walkable and not walkable and then calculate the best path.

Why Pixel Bender for a path finder?
My initial goal was to have the astar pathfinder run on a pure black and white bitmap data object. This way a designer could simply place complex objects on a map and a developer could easily transform the map to a black and white collision map.
The next step of course would be to have Flash analyse this bitmap and create a grid for pathfinding accordingly.
Using getPixel in a loop would be very slow, especially in very large bitmaps, so Pixel Bender was obviously used here.
A cool bonus is that Pixel Bender also runs asynchronously in a seperate thread from Flash.

How does Pixel Bender create the grid?
The Pixel Bender kernel script takes 2 parameters, one being the black and white bitmap obviously, the other being a node distance value. This node distance is the effective distance between 2 individual nodes in the grid. For example: a bitmap of 600 pixels width would output 30 columns in the node distance is 20 pixels.

As you probably know, Pixel Bender loops over each individual pixel.
For each pixel, the node to the top-left of that pixel is found. Then the script will test if the current pixel happens to be in a straight line between 2 adjacent nodes.
If it is, another test will determine if you can walk from node A to B, this is not the case should the pixel be black.

For each pixel, a result is kept. The output of the Pixel Bender kernel script is image3, so that gives 3 values for each pixel to use.
The first value is a binary value, this binary value is a collection of bit flags for the pixel, namely : is walkable or is not walkable, if the pixel is on the straight line to the node on the right/bottom-right/bottom/top-right.
The other 2 values are used to store the col and row of the top-left node.

For quick updating I also divided the black and white bitmap into areas, each area is 200×200 pixels large and is processed by its own ShaderJob. This way, when the black and white map is updated, I can process these updates by area instead of having to re-process the image as a whole each time.

Now for Alchemy…
Thanks to Ralph Hauwert’s excellent post on how to optimize the use of Alchemy and Pixel Bender, I decided to try the same with this experiment.
Flash will write the Pixel Bender result straight into Alchemy memory, where it is then processed in C to a usable grid.
The actual astar algorythm was also ported to C since the algorythm potentially runs a very large loop when using low node distance values or large black and white collision maps.

As a result
The path finder does run faster than in pure AS3, but not by a great amount. You can test it here.
The initial choice is to set the node distance property. The lower the value, the more nodes Pixel Bender will generate and thus the more data Alchemy has to crunch to display the astar path result.

Please note that…
the initial choice can really result in a slow pathfinder if you select ‘intensive’ for example. In most practical implementations the less-intensive settings are more than enough.

Credit to mr. Doob for the excellent Stats class

c code used in Alchemy
Around 90% of this app was built in C for use in Alchemy, below is the source.
It’s a bit cryptic sometimes, mostly due to some efforts in trying to optimize code execution with Alchemy.
Flash is only used to paint the maze and display the result from Alchemy & PB.

Alchemy C source