With Probus finished I’ve started out building a new game to keep me busy at the weekends, “Project: Tanks”. I’m sticking with the HTML5 canvas platform again, but aiming at PC web browsers this time. I’m hoping to play around with supporting player made content in this one, so I set out on making a slower paced ‘twin stick’ shooter inspired by the Wii Tanks game I enjoyed playing with my brother years ago.

I had a basic engine running pretty quickly and filled it with programmer art using the vector drawing functions of the HTML5 canvas. I intended to update this ‘art’ later in development but to my surprise by applying a simple technique to turn the dull 2D shapes into ‘3D’ wireframes I was able to make the programmer art into the games full visual style. I was so happy with the results that I wanted to share the technique in this post.

Over the course of the article we are going to develop a drawing routine to take a Tank model from the humble beginnings shown on the left, to the glorious ‘3D’ seen on the right.

The drawing functions will be detailed in pseudocode along the way and the Javascript that powers the examples can be downloaded here for reference.

The 3D effect will mimic a top-down oblique projection of our models in order to draw our 3D models on the canvas. This projection technique works by passing parallel rays through the 3D scene at an angle a little off vertical to project the 3D scene onto the 2D surface. For the top-down style we want we can achieve the projection without worrying about the precise mathematics, simply by drawing anything in the horizontal plane as normal whilst scaling the vertical coordinates by about 0.3.

The easiest way to get an feel for this projection is to see it in action. Take Nintendo’s Pokémon Fire Red for example,

At its most basic, the effect will work by defining a 3D model as a series of 2D layers, expanding them vertically into volumes, then stacking on top of each other to form the final image. By the rules of the oblique projection we will leave the X and Y coordinates of each layer as they are, and draw the vertical shifts by moving along Y to 0.3 times the upper and lower Z coordinates, `z_top`

and `z_bottom`

respectively.

To make rotations easy we will define each layer in the model as a list of vertices, ordered anti-clockwise, relative to a central axis: (0,0). When we come to draw the layer we will first rotate it around this axis, then translate it to the model’s position in the world space, and finally draw it shifted in Y by 0.3 times z_top and z_bottom.

We will use this function to draw each layer in the model from lowest to highest to make a crude projection.

function draw(Model shape, Canvas g) { Vector2D transformed; Vector2D start; for (Layer layer in shape) { g.start_stroke(); g.start_fill(); // Move the stroke to the first vertex start = layer.vertices[0].rotate(shape.rotation) start += shape.position; // Shift down to the z_bottom position. start.y += layer.z_bottom*0.3; g.move_to(start); // Draw a line along the rest of the vertices for (int i = 1; i < layer.vertices.length; i++) { transformed = layer.vertices[i].rotate(shape.rotation); transformed += shape.position; transformed.y += layer.z_bottom*0.3; g.line_to(transformed); } // Close the shape with a line to the first vertex g.line_to(start); g.end_fill(); g.end_stroke(); // Repeat the procedure for the upper layer g.start_stroke(); g.start_fill(); start = layer.vertices[0].rotate(shape.rotation) start += shape.position; // This time we shift to z_top start.y += layer.z_top*0.3; g.move_to(start); for (int i = 1; i < layer.vertices.length; i++) { transformed = layer.vertices[i].rotate(shape.rotation); transformed += shape.position; transformed.y += layer.z_top*0.3; g.line_to(transformed); } g.line_to(start); g.end_fill(); g.end_stroke(); } }

Using this routine the tank has a (somewhat abstract) 3D feel!

It's worth noting that by adding an opaque fill to the layers we are departing a little from a true wireframe render. The end result is worth it, however, as the occlusion of the lower layers by the higher ones reduces the visual clutter and helps to sell the 3D feel. For this reason we'll stick with this filling strategy as we develop the method further.

By drawing each layer in ascending order we have created much of the 3D effect, but to make it convincing we need to draw the layers as volumes rather than a stack of planes. We will construct said volumes by drawing each layer at both z_top and z_bottom, as we did before, and joining the vertices between the layers to fill the vertical faces.

To correctly draw the vertical faces we must limit ourselves to only drawing convex shapes, i.e. those with internal angles all smaller than 180 degrees. Convex shapes are important for this drawing as they allow us to use the counter-clockwise ordering of the vertices to draw the vertical faces in the right order.

To achieve this generalisation of layers to volumes we will expand the drawing function to 7 phases:

- Create and store a full list of transformed vertices.
- Identify the left and right most transformed vertices, using the largest Y coordinate to tie-break.
- Draw the vertical faces by starting from the left most vertex shifted to z_top and connecting it down to its position at z_bottom.
- Sequentially connect onwards through the transformed vertex list (all shifted to z_bottom) until we reach the right most vertex identified before.
- Connect up to the right most vertex at z_top and close the shape back to the left most vertex at z_top.
- Draw vertical lines from z_top to z_bottom for all the vertices between the right the left extremes.
- Finally, draw the whole layer shape at z_top as before.

This is summarised more precisely as the pseudo-code below,

function draw_volume(Model shape, Canvas g) { for (Layer layer in shape) { int n_verts = layer.vertices.length; List<Vector2D> transformed; // Create the transformed list, maintaining the ordering for (int i = 0; i < n_verts; i++) { transformed.push(layer.vertices[i].rotate(shape.rotation) + shape.position; } // Identify the left and right most transformed vertices Vector2D left(+MAX_NUMBER, 0); Vector2D right(-MAX_NUMBER, 0); int left_index; int right_index; for (var i = 0; i < n_verts; i++) { if (transformed[i].x < left.x or (transformed[i].x == left.x and transformed[i].y > left.y)) { left = transformed[i]; left_index = i; } if (transformed[i].x > right.x or (transformed[i].x == right.x and transformed[i].y > left.y)) { right = transformed[i]; right_index = i; } } // Draw the vertical faces g.start_stroke(); g.start_fill(); // Start at the left most vertex. int i = (left_index+1)%n_verts; g.move_to(transformed[i]+shape.z_top); g.line_to(transformed[i]+shape.z_bottom); // Run along the bottom of the panels. while (i != right_index+1) { g.line_to(transformed[i]+shape.z_bottom); // Move through the list rolling around to the start if needed. i = (i+1)%n_verts; } // Connect to the top g.line_to(transformed[right_index]+shape.z_top); // And back to the top right to close the shape g.line_to(transformed[left_index]+shape.z_top); g.end_fill(); g.end_stroke(); // Draw the layer shape at the top. g.start_stroke(); g.start_fill(); g.move_to(transformed[0]+shape.z_top); for (int i = 1; i < n_verts; i++) { g.line_to(transformed[i]+shape.z_top); } g.line_to(transformed[0]+shape.z_top); g.end_fill(); g.end_stroke(); } }

This function is very close to the final method and produces some nice results, but there remains a problem that we need to fix: volumes that share a Z level can produce strange results. You can see this in the example tank below when then turret points downwards, the barrel of the cannon should emerge from the turret, instead it appears to be below it.

What we have so far above works nicely when the model is a simple ‘totem pole’ style arrangement of layers stacked on top of each other, but If the model has side-by-side layers then we must be more careful.

We can clearly see what is wrong when this bulldozer faces down,

The problem lies in the order that we draw the layers. When the dozer is facing upwards we want to draw the scoop first so the main body is drawn over the top of it. When the dozer is facing downwards however, we want to draw the scoop last so it is on top.

Unfortunately it's not possible to solve this layer ordering problem in the general case and no matter how we sort things we can always make arrangements that don't play nicely. These three rectangles are a good example,

To properly handle all cases we would need to implement a depth-buffer to control what is drawn on top of what on the pixel scale. That is beyond the scope of this post (and Project: Tanks in general) however, and instead we must be happy with a pretty good solution of sorting the layers into the best order we can before we draw the model. This style of sorting the layers then drawing them in ascending order is known as the painter's algorithm and whilst we know it will fail for some arrangements we can limit the number of problem cases by designing our models sensibly.

Sorting the layers of the tank and bulldozer based on the direction the model is facing gives us the final effect we were looking for,

Whilst it would be nice to have a general purpose sorting routine experience suggests it is better to define the sorting on a model by model than to try to make a catch all algorithm. When we start to draw multiple models moving around each other we will find the layering problem rises again between the models, but for this sorting the models by ascending Y position seems to give a good result if all the models are of roughly the same size and height.

This is all I've needed for Project: Tanks so far but it's easy to see how the technique could be generalised for more complex results. We could allow for sloped faces by defining independent top and bottom vertices and how they connect to give pyramidal structures and bevels. Additionally, we could add the means to draw non-convex shapes through a decomposition into convex sub-shapes and not stroking the internal edges.

In fact, we are very close to having a full 3D renderer for general models. If we defined our models as triangle lists (and maybe used a more refined perspective projection method), we would have a fully 3D 'painter's algorithm' renderer. At this point however, it feels like a the simplicity that was so appealing has been lost, and it might be time to consider an proper 3D library.

So there we have it, the basic 2D tank has been developed into a much more interesting '3D wireframe' model and as well as having a strong aesthetic identity the technique developed remains reasonably simple with a relatively low cost when drawing simple models. What's more, its easy for an 'artistically disadvantaged' programmer such as myself to make appealing graphics just by stacking basic shapes.

The strong wireframe aesthetic is nice for some projects, but it is clearly not right in most settings. The ideas at the core of the method are not doomed to a retro oblivion however, and the same technique of shifting by a scaled Z coordinate can be used with layers of bitmaps to give a more general 'pixel art' effect. A great example is given by like 100 bears in a post that formed the inspiration for this work and is definitely worth a read.

Right, with all that rendering set up it's time for me to make the rest of the game!

A lot of the challenge of good procedural generation is in appropriately setting how much of something should be included as a function of something else. Getting this blending right can be a tricky business, and I’ve been slowly collecting a library of mathematical functions that have interesting properties suited to this task. I thought I’d kick off this blog with a post describing my favourite of these functions, a sigmoid function,

$$ f_{S}(x; \sigma) = \frac{x^2}{\sigma^2 + x^2}$$

Sigmoid functions are simply functions that give an S shape when plotted. There are many such functions known, but \(f_{\mathrm{S}}\) has some particularly appealing properties that allow the developer a great deal of control over its shape, whilst staying simple and efficient to evaluate.

I first came across \(f_{\mathrm{S}}\) in the context of Tikhonov Regularisation where it acts as a filter, removing noise from ill-posed matrix equations. After working with it for a while, I started to notice some of its nice characteristics and began to wonder if it can’t be put to some good use in procedural game generation…

The function \(f_{\mathrm{S}}\) is deceptively simple depending on one variable, \(x\), and one parameter, \(\sigma\), and returning a number in the range \(0 \leq f_{\mathrm{S}} < 1\). By plotting it we can see exactly why itand sigmoid functions in general is so well suited to procedural generation:

The function resembles a player’s skill within a game as it progresses over time. We can see 3 clear areas,

- An initially flat upwards curving slope (green) where an inexperienced player begins to develop familiarity with mechanics.
- Next follows a region of roughly linear progression (yellow) as the player develops a solid understanding of the mechanics.
- Finally the progression curves downwards and becomes flatter (red) as the player masters the game and approaches the skill ceiling of the game.

We can use this similarity to the player’s experience to control the difficulty and features encountered in a procedurally generated game to match the progression of our players.

Despite its simplicity a great deal of control over \(f_{\mathrm{S}}\) is present through the parameter, \(\sigma\), that defines the overall rate of the progression. Intuitively \(\sigma\) sets the value of \(x\) at which the function returns 0.5 and the progression curve begins flatten out. You can explore how changing the value of \(\sigma\) affects \(f_{\mathrm{S}}\) in the interactive plot below,

σ: 13 |

So what are some ways we can use \(f_{\mathrm{S}}\) in procedural generation?

Most clearly we can use \(f_{\mathrm{S}}\) when we want to control the amount of one thing as a function of another numerical variable. We can do this with any pair we can express as two numbers but if both are continuous variables then some simple analysis reveals some useful relations.

Lets explore an imaginary procedural RPG called ‘Level Quest’. Unlike most RPGs, the hero in Level Quest gains experience and becomes stronger simply as time progresses, rather than through player actions, with the rate of experience gain controlled by our sigmoid function,

$$ \text{Experience per Second} = f_{S}(t)\times\text{Max Rate}$$

During the course of the game we will want to know how much experience a player has, ideally by simply by knowing how much time has passed. Whilst we could achieve this by incrementing an experience variable we are going to use a little bit of calculus to get a quick answer from the simple form of \(f_{\mathrm{S}}\).

Intuitively, the amount of experience gained by the hero over a given time period is equivalent to the area under sigmoid curve for the period of interest. Lets take as an example the question:

“How much experience will the hero gain in the time window between 7 and 23 seconds of play, given \(\sigma\) = 15 and a maximum rate of 20 exp per second?”

This is expressed mathematically as the definite integral,

$$ \text{Experience} = \int^{t_{\mathrm{Start}}}_{t_{\mathrm{End}}} \frac{x^2}{x^2+\sigma^2}\mathrm{d}t \times \text{Max Rate} $$

the solution to which is,

$$ \text{Experience} = \left ( \sigma \times \arctan\left ( \frac{\sigma(t_{\mathrm{Start}} – t_{\mathrm{End}} ) }{t_{\mathrm{Start}}t_{\mathrm{End}} + \sigma^2} \right ) – t_{\mathrm{Start}} + t_{\mathrm{End}} \right ) \times \text{Max Rate}$$

Using this equation we can quickly calculate that the hero will gain 307.58 experience points between 7s and 23s. Now we can efficiently work out how much experience a player will have at any time, even if we want to start them off at a time other than 0. This example of a hero gaining experience is admittedly crude but knowing how much of something a player has come across can be a useful tool when trying to balance a game’s design.

We already have a nice way of controlling sigmoid progression through the \(\sigma\) parameter but there is another controlling parameter hidden in \(f_{\mathrm{S}}\) that can grant us further control over the progression. This ‘hidden’ parameter is the exponent and we will label it \(\lambda\) from here on,

$$ f_{\lambda}(x; \sigma, \lambda) = \frac{x^{\lambda}}{x^{\lambda} + \sigma^{\lambda}} $$

The new parameter, \(\lambda\), controls how sharp the progression curve is, giving a flatter curve when \(\lambda\) is small and a sharper step-like like progression when \(\lambda\) is large.

With both \(\sigma\) and \(\lambda\) at our fingertips we have an enormous degree of control over the shape of \(f_{\mathrm{S}}\) and hence the variables we want it to control. You can have see the effect of both \(\lambda\) and \(\sigma\) in the plot below, have a play and see how the curve responds to different choices.

σ: 13 | |

λ: 2 |

Unfortunately the calculus we used before to find the area under the curve becomes more complicated when \(\lambda\) is not 2. For some values a relatively simple integral can still be found, but the general case is not so easy. If you’ve settled on a \(\lambda\) value you like you could run it though a tool like Wolfram Alpha and see if the result is usable, but non-integer and extreme values are unlikely to be have useful integrals.

Of course if you aren’t interested in knowing the area under your progression curve then this isn’t a problem.

We’ve made a small look into some of properties that make \(f_{\mathrm{S}}\) an appealing equation for procedural generation and looked at how we can achieve even more control by varying the exponent parameter. This function is, of course, by no means the only way to achieve smooth transitions, but the simplicity and flexibility of \(f_{\mathrm{S}}\) and its calculus make it appealing for applications in game programming.

The ‘Level Quest’ example used above is nice and simple, but I think the function has much more power when applied to more abstract things like terrain generation and resource placement. In my game Probus I used \(f_{\mathrm{S}}\) to control the occurrence of asteroid objects and made them more common as the player progresses, adding some flavour and complexity to the later systems.

For such a simple thing, \(f_{\mathrm{S}}\) has earned a valued place in my tool-kit of functions, and I keep finding more uses for it. I’d love to hear ideas or other interesting functions, please feel free to suggest any of your own in the comments.

]]>