Category Archives: 2D

Essentials of Software Engineering – With a Game Programming Focus

I’ve been commissioned to write a big document about what I think it means, and what is necessary, to become a good software engineer! If anyone finds the document interesting please do email me (email on my resume) with any questions or comments, even if you hate it and deeply disagree with me! This is the first release so some sections may be a bit skimpy and I might have some false info in there here and there.

I’m a fairly young engineer so please do take all my opinions with a healthy dose of skepticism. Nonetheless I hope the document is useful for someone! Many of my opinions come from my interpretation of much more experienced engineers I’ve come in direct contact with, and this PDF is sort of a creation of what others taught me.

As time goes on I may make edits or add new chapters, when I do I’ll modify the version number (just above the table of contents). Here is the PDF:

Download (PDF, Unknown)

TwitterRedditFacebookShare

Forest RTS – Unfinished Game

 

Decided to release an unfinished game that will never be finished. RIP. The game started as a for-fun game jam to test out working with a couple friends of mine. In the end we ended up working for 2-3 weeks before deciding to move on to another project. Read more about the game here.

Download executable: Download (ZIP, 9.53MB).

Link to source: here.

forest_clip

bear swamp_poison swamp

I ended up enjoying the human AI quite a bit, and it grew to a decent size! This was my first time implementing things like A*, or a semi-complex state machine, and the end it was total fun. Here’s an explanation of the human behavior in case anyone was curious (taken straight from the source code);

Download executable: Download (ZIP, 9.53MB).

Circular Orbits | Planetary Motion | NBody Simulation

I took a few hours yesterday to start on a simulation for a job application. Part of the simulation involves trying to figure out how to create stable nbody orbits, at least stable for some amount of time to look interesting.

Turns out that the mathematics beyond constructing a circular orbit of just two bodies is a bit far-fetch’d. We can see in this link that solving for the velocity of each planet is very straightforward. Let me take a screenshot of the final equations here:

orbit_math

To me this makes a lot of sense and matches my own derivation, albeit with a slightly different final form (just due to some algebra differences). I plug in the equation into my simulation and hit run, however there’s just not enough velocity to keep an orbit. See for yourself (the simulation is slowed down a lot compared to later gifs):

satellites_slow

Each white circle is a body (like a planet) and the red circle is the system’s barycenter.

So I tinkered a bit and found out the velocity is too dim by a factor of sqrt( 2 ). My best guess is that the equations I’m dealing with have some kind of approximation involved where one of the bodies is supposed to be infinitely large. I don’t quite have the time to look into this detail (since I have much more exciting things to finish in the simulation), so I just plugged in my sqrt( 2 ) factor and got this result:

satellites

Here’s the function I wrote down to solve for orbit velocity in the above gif:

I’m able to run the simulation for thousands of years without any destabilization.

If any readers have any clue as to why the velocity is off by a factor of rad 2 please let me know, I’d be very interested in learning what the hiccup was.

Next I’ll try to write some code for iteratively finding systems of more than 2 bodies that have a stable configuration for some duration of time. I plan to use a genetic algorithm, or maybe something based off of perturbation theory, though I think a genetic algorithm will yield better results. Currently the difficulty lies in measuring the system stability. For now the best metrics I’ve come up with is measuring movement of the barycenter and bounding the entire simulation inside of a large sphere. If the barycenter moves, or if bodies are too far from the barycenter I can deem such systems as unstable and try other configurations.

One particularly interesting aspect of the barycenter is if I create a group of stationary bodies and let them just attract each other through gravity, the barycenter seems to always be dead stationary! The moment I manually initialize a planet with some velocity the barycenter moves, but if they all start at rest the barycenter is 100% stable.

satellites_all

Freelist Concept

A freelist is a way of retrieving some kind of resource in an efficient manner. Usually a freelist is used when a memory allocation is needed, but searching for a free block should be fast. Freelists can be used inside of general purpose allocators, or embedded directly into an optimized algorithm.

Lets say we have an array of elements, where each element is 16 bytes of memory. Our array has 32 elements. The program that arrays resides in needs to request 16 byte elements, use them, and later give them back; we have allocation of elements and deallocation of elements.

The order the elements are allocated is not related in any way to order of deallocation. In order for deallocation to be a fast operation the 16 byte element needs to be in a state such that a future allocation be handed this element to be reused.

A singly linked list can be used to hold onto all unused and free elements. Since the elements are 16 bytes each this is more than enough memory to store a pointer, or integer index, which points to the next block in the free list. We can use the null pointer, or a -1 index to signify the end of the freelist.

Allocating and deallocating can now look like:

Setting up the memory* will take some work. Each element needs to be linked together somehow, like through a pointer or integer index. If no more elements are available then more arrays of size 32 can be allocated — this means our memory is being managed with the style of a “paged allocator”, where each array can be thought of as a page.

The freelist is an important concept that can be embedded ad-hoc into more complex algorithms. Often times it is important for little pieces of software to expose a very tiny C-like interface, usually just a function or two. Having these softwares self-contain their own internal freelists is one way to achieve a simple interface.

Example of Hiding the Freelist

For example say we are computing the convex hull of a point-set through the Quick Hull algorithm. The hypothetical algorithm exposes an interface like this:

This QHull function does no explicit memory allocation and forces the user to allocate an appropriate amount of memory to work with. The bounds of this memory (how big it needs to be for the algorithm’s worst case scenario) is calculated by the ComputeMemoryBound function.

Inside of QHull often times the hull is expanded and many new faces are allocated. These faces are held on a free list. Once new faces are made, old ones are deleted. These deleted faces are pushed onto the free list. This continues until the algorithm concludes, and the user does not need to know about the details of the embedded memory management of the freelist.

Convex hull about to expand to point P. The white faces will be deleted. The see-through faces will be allocated.

A convex hull fully expanded to point P. All old faces were deleted.

The above images were found at this address: http://www.eecs.tufts.edu/~mhorn01/comp163/algorithm.html

Printing Pretty Ascii Trees

I’m terrible at writing recursive algorithms. Absolutely horrible. So for practice I decided to try printing a binary tree where all branches have two children, all in the console. It turns out this is a pretty useful quick-n-dirty debugging tool when creating trees.

I really like formatting of Tree for linux so I decided to steal it.

After 3 straight hours of trying out stupid stuff I finally come to a working solution (my earlier attempts were around 150 lines of code, the solution was like 70):

Which will print cool trees like this one:

I then realized that I could use singly linked lists to represent trees with any number of children, which is totally necessary for the parser I am currently writing. So after 30 minutes I was able to form version 2 for arbitrary trees; this version is surprisingly right around the same length and complexity as the previous version:

And will print trees like this monster:

I also ended up finding a pretty cool implementation by a random stack-overflow user that prints trees in horizontal format (which turns out to be much more limited for the purposes of a console, since it can’t print larger trees, but might look a lot prettier for small trees):

It may be preferable to upgrade to the limited edition Box Drawing characters for best viewing pleasure:

Capture

 

In which case you’ll probably want to use some specific character codes (I used 195, 196 and 192 in the above image).

Interactive Cubic Bezier Splines

Cubic Bezier splines look rather beautiful. Splines in general look great and are super useful for all sorts of cool stuff.

Creating splines usually involves defining some control points and moving those around until the desired effect is achieved. However, clicking on or interacting with the spline itself turns out to be a lot harder than just messing with control points.

In particular I want to talk about cubic Bezier splines. This kind of spline is defined as 3 * n + 1 control points, where n is the number of Bezier curves in the spline. The first four points represent the first curve, then the last point and the next three represent the next curve, and so on.

The resulting spline can look like the curved arrows in this graph:

http://www.graphviz.org/Gallery/directed/datastruct.png

Actually interacting with these splines would be pretty difficult since cartesian coordinates are not in the same basis as the spline itself. What is needed is the ability to express a relation between these two spaces.

Since I haven’t studied curves in great detail there’s much math that goes beyond me (for the time being) in solving this problem. However in Graphics Gems I there’s a section called “Solving The Nearest-Point-On-Curve Problem” where some public domain C code is given that computes the closest point on a cubic Bezier curve to a given input point. The C code is really old and actually calls malloc in a recursive function, presumably to avoid stack overflows on old machines with minimal memory. This can be converted to use a stack data structure on the process stack space, all without much work for the user.

After a few minutes I was able to set up a cool demo:

closest_point_on_bezier2

This tool would be great for some kind of interactive spline editor. It would also be perfect for colliding circles (or spheres in 3D), making the curve itself a potential candidate for a physics engine collider type. Since the curve is defined by control points, the curve can actually deform at run-time without any big complications.

Approximating the Curve

In reality a spline like this would probably just be “rasterized” to some kind of approximate shape that is easier for a physics engine to collide, rather than dealing with the exact spline itself. This is likely due to there not being a straightforward way to compute the closest point on the spline to a plane (at least, I sure don’t know how to write that code).

One tactic would be to interpolate a few points out of the curve (and by few I mean as many as needed), and then use these points as an approximate representation of the curve. This could be like converting the curve to a line strip, which might make interactivity much simpler in many cases.

Generating these points can be a piece of cake. Personally I’d just write out some lerps and call it good. If we look at the simplest Bezier curve with 2 control points it’s easy to see it’s just a single lerp (these animations were taken from the Wikipedia page for Bezier curves):

Bézier_1_big

 

If we add a third point we can perform two lerps, and then lerp the results together. Intuitively this gives us a quadratic Bezier curve, and looks like:

Bézier_2_big

 

Following suit we can use 4 control points and create a cubic Bezier curve:

Bézier_3_big

 

An easy way to convert a cubic Bezier curve to a line strip involves sampling points on curve at time t, where t is on the interval of 0 to 1. Here’s some example code:

For example, Box2D defines a “chain shape” as a line strip of segments. Generally this strip is used to approximate curved, non-moving surfaces. Splines can very easily be converted to strips and sent to Box2D to define a chain shape.

Some Spliney Links

  • http://phildogames.com/blog/spline.html
  • http://www.gamasutra.com/view/feature/131755/curved_surfaces_using_bzier_.php
  • http://www.jasondavies.com/animated-bezier/
  • http://pomax.github.io/bezierinfo/
  • http://ciechanowski.me/blog/2014/02/18/drawing-bezier-curves/

Minimum Bounding Sphere

Today I was reading this article by Ericson. The article is on the derivation involved in writing a function to calculate the minimum bounding sphere of a set of three or four points. The topic itself isn’t very interesting (to me) when compared to the algebra itself. Ericson skips the algebra I had trouble with, so my article here will serve the purpose to record the algebra he skipped (in case other readers had trouble, or I ever want to reference the math again). The article I am writing here directly follows Ericson’s article, so I will assume readers have read and understood Ericson’s article.

Say we have a set of three points S = {A, B, C}, which can be thought of as a triangle. The problem of calculating the minimum bounding sphere of S involves checking to see if the circumcenter of S lies within or outside the triangle S. Lets name the circumcenter P. One immediate implementation involves computing P, followed by the computation of the barycentric coordinates of P with respect to S. These coordinates can be used check if P lay within S.

However computing P of S followed by the barycentric coordinates of P with respect to S involves a lot of redundant computations. Furthermore, if P does not lay within S then P itself does not need to be computed at all, since only the barycentric coordinates were needed.

It would be nice to compute barycentric coordinates of P with respect to S directly, and only if necessary construct P.

P in relation to S can be defined as:

\begin{equation}
\label{eq1}
P = A + s*(B – A) + t*(C – A)
\end{equation}

Where \(s\) and \(t\) are barycentric coordinates of S such that \(s – t – (1.0 – s – t) = 0\) if P is within S. Since P is equidistant from A, B and C, we can express P in relation to S with the following:

\begin{equation}
\label{eq2}
dot(P – B, P – B) = dot(P – A, P – A)
\end{equation}

\begin{equation}
\label{eq3}
dot(P – C, P – C) = dot(P – A, P – A)
\end{equation}

The interesting part involves plugging \eqref{eq1} into \eqref{eq2} and \eqref{eq3} followed by a collection of terms. Since I myself am a noob when it comes to algebra I had to go look up algebraic properties of the dot product to make sure I did not screw anything up. In particular these few rules are useful:

\begin{equation}
\label{eq4}
dot(u, v + w) = dot(u, v) + dot(u, w) \\
dot(s * u, v) = s*dot(u, v) \\
-dot(u – v, u – w) = dot(v – u, u – w)
\end{equation}

Lets go over substituting \eqref{eq1} into \eqref{eq2} directly, however lets only consider the first part of \eqref{eq2} \(Dot(P – B, P – B)\) to keep it simple:

\begin{equation}
\label{eq5}
dot(A + s*(B – A) + t*(C – A) – B, A + s*(B – A) + t*(C – A) – B)
\end{equation}

Since things immediately get really long some substitutions help to prevent errors:

\begin{equation}
\label{eq6}
u = A – B\\
v = s*(B – A) + t*(C – A)\\
w = u + v \\
\end{equation}

\begin{equation}
\label{eq7}
Dot(w, u + v)
\end{equation}

\begin{equation}
\label{eq8}
Dot(w, u) + Dot(w, v)
\end{equation}

\begin{equation}
\label{eq9}
Dot(u + v, u) + Dot(u + v, v)
\end{equation}

\begin{equation}
\label{eq10}
Dot(u, u) + Dot(v, u) + Dot(u, v) + Dot(v, v)
\end{equation}

If I were to expand \eqref{eq10} on this webpage it would not fit. Instead we will make use of a few more substitutions and then arrive in the final form:

\begin{equation}
\label{eq11}
x = s*(B – A) \\
y = t*(C – A) \\
x + y = v
\end{equation}

\begin{equation}
\label{eq12}
Dot(A – B, A – B) + 2*Dot(A – B, x + y) + Dot(x + y, x + y)
\end{equation}

By following the same process we can finish the substitution and notice that:

\begin{equation}
\label{eq13}
Dot(P – A, P – A) = Dot(x + y, x + y)
\end{equation}

The final form of the substitution would be:

\begin{equation}
\label{eq14}
Dot(A – B, A – B) + \\ 2*Dot(A – B, x + y) + \\ Dot(x + y, x + y) = Dot(x + y, x + y)
\end{equation}

\begin{equation}
\label{eq15}
Dot(A – B, A – B) + 2*Dot(A – B, x + y) = 0
\end{equation}

\begin{equation}
\label{eq16}
Dot(A – B, A – B) + \\ 2*Dot(A – B, s*(B – A)) + \\ 2*Dot(A – B, t*(C – A)) = 0
\end{equation}

\begin{equation}
\label{eq17}
s*Dot(B – A, B – A) + t*Dot(B – A, C – A) = \\ (1/2)*Dot(B – A, B – A)
\end{equation}

This final equation \eqref{eq17} matches exactly what Ericson came up with on his own blog. Through a similar process \eqref{eq1} can be substituted into \eqref{eq3}, which would result in:

\begin{equation}
\label{eq18}
s*Dot(C – A, B – A) + t*dot(C – A, C – A) = \\ (1/2)*dot(C – A, C – A)
\end{equation}

Computing AABB Trick (Loop Trick)

Lately I noticed a small trick that applies to loops when trying to find a minimum or maximum of some values. Usually I just apply the trick to loops where I need to compute an AABB over some geometry. I think I noticed this trick when reading a for loop Erin Catto wrote in some of Box2D’s internal code.

The trick is super simple: just process the first element outside of the loop to set up your initial conditions, then form your loop to skip the first element. An assumption would be made that there’s at least one element in the array to process. Here’s an example for computing an AABB:

Usually I myself would have written this kind of code like so and not given any more thought to it:

This second code chunk is arguably just slightly more esoteric and is definitely a little less efficient for no good reason.

One could also skip the first element when finding the min/max of any sort of array, like for example: dot product results. Though simple it’s pretty nice to find small ways to write slightly better code.

Robust Parallel Vector Test

In an effort to try to find some robust tests for parallel vectors I’ve decided to create some slides talking about the solutions I’ve come across. Hopefully one day some reader can comment or email about some alternatives or better solutions! I decided to write this blog post in slide format since Microsoft’s Powerpoint is pretty snazzy for making quick diagrams and whatnot :)

Here’s the link to Ericson’s blog post on tolerances: Tolerances Revisited. Please note there’s a little bit of ambiguity about whether the test should care if the vectors point in the same direction or not. In general it doesn’t really matter since the point of the slides is numeric robustness.

The gist of the slides is that the scale of the vectors in question matters for certain applications. Computing a good relative epsilon seems difficult, and maybe different epsilon calculations would be good for different applications. I’m not sure!

Here’s a demo you can try out yourself to test two of the solutions from the slides (tests returning true should be considered false positives):

Output of the program is:

Download (PDF, Unknown)