Category: Computer Graphics

Artifact 1.0.4 – Hello integer overflowing highscore!

Yesterday I finally finished some of my planned Artifact updates. The new version can be downloaded from here. Below is a detailed account of the changes in this version.

  • Added a game mode (rascal), where you can not lose:

    As my 4 year old daughter was playing the game I had to keep typing cheat codes to keep her alive. This made me realise that I could introduce a game mode where it is not possible to lose, and where the player has infinite resources. Once I added the rascal mode she played for quite a while, and she even figured out some smart plays all by herself.

    • Artifact
    Rascal mode allows exploration of the game in a different way. Hello integer overflowing high score!

  • Removed global score tracking:

    Global score tracking from games not played on a server will always be prone to modified clients posting fake scores. This can be mitigated though obfuscation, but not really solved. My implementation was also very bad, and very hard to maintain. Maybe I’ll revisit this one day, but for now I am glad its gone.

  • Removed hash checks of local data:

    I do not care if you hack your local files so that you have insane scores. Hack the game all you want!

  • Prepare for OS X removal of some carbon audio API:

    I kept getting this message in my logs:

    WARNING: 140: This application, or a library it uses, is using the deprecated Carbon Component Manager for hosting Audio Units. Support for this will be removed in a future release. Also, this makes the host incompatible with version 3 audio units. Please transition to the API’s in AudioComponent.h

    The solution was to upgrade openal-soft by building from source, and replace the old openal.dylib that came with Slick2D with the libopenal.dylib built, which I guess uses the API Apple wants you to use.

Useful if caught in overly simplistic space combat

One of my favorite games, and by far the one I used the most time creating content for during my youth is Escape Velocity Nova. The Escape Velocity series are 2D space RPGs, which means there is lots of 2D space combat. In these types of games you typically have three main types of weapons, non-turreted, turreted and homing. Non-turreted and homing weapons are not really that complicated. The non-turreted fire in one direction (typically forward), while the homing weapon typically turns as hard as it can towards the target at maximum speed. Turreted weapons were always a puzzle to me though, they somehow knew where you would be, and fired to intercept your ship. I always wondered how this was done.

Some years later during a visualization class (on how to find intersections between geometric primitives) I was wondering if I could use geometric equations to figure out where a spaceship needs to aim its torpedo, if it knows the position and velocity of the target. Below is the solution I came up with. It assumes constant speed for the target and the torpedo.

The positions of something moving at constant speed, can be described by this equation where t denotes time, \vec{v} the current velocity and \vec{p_o} is the starting position. This restricts the position of the target to a line, where the position on the line is determined by t.

(1)   \begin{equation*} \vec{p} = \vec{p_o} + \vec{v}t \end{equation*}

For 2 dimensions this is:

(2)   \begin{equation*} \begin{pmatrix}p_x\\p_y\end{pmatrix} = \begin{pmatrix}p_{xo}\\p_{yo}\end{pmatrix} + \begin{pmatrix}v_x\\v_y\end{pmatrix}t \end{equation*}

The possible locations p of a constant speed (s) bullet fired from point c in any direction, are given by this equation, where again time is denoted by t. This restrict the possible positions to a circle which expands with time.

(3)   \begin{equation*} (st)^{2} = (\vec{p} - \vec{c})^{2} \end{equation*}

For 2 dimensions this is:

(4)   \begin{equation*} (st)^2 = (p_{x} - c_x)^2 + (p_{y} - c_y)^2 \end{equation*}

Now inserting the restrictions on p_x and p_y from 2 into 4 gives a polynomial that only depends on t:

(5)   \begin{equation*} (st)^2 = ((p_{xo}+v_xt) - c_x)^2 + ((p_{yo}+v_yt) - c_y)^2 \end{equation*}

Rearranging gives:

(6)   \begin{equation*} s^2t^2 = (p_{xo}-c_x + v_xt)^2 + (p_{yo}-c_y + v_yt)^2 \end{equation*}

Simplifying by setting constants i = p_{xo}-c_x and j = p_{yo} - c_y and moving towards standard form:

(7)   \begin{equation*} s^2t^2 = (i)^2 + 2iv_xt + v_x^2t^2 + (j)^2 + 2jv_yt + v_y^2t^2 \end{equation*}

Rearranging to standard form:

(8)   \begin{equation*} 0 = (v_y^2 + v_x^2 - s^2)t^2 + 2(iv_x + jv_y)t + (i)^2 + (j)^2 \end{equation*}

This is a quadratic equation, with coefficients:

(9)   \begin{equation*} a = v_y^2 + v_x^2 - s^2 \end{equation*}

(10)   \begin{equation*} b=2(iv_x + jv_y) \end{equation*}

(11)   \begin{equation*} c=i^2 + j^2 \end{equation*}

Solving the quadratic equation gives two solution for t, if an answer is positive and has no imaginary part, there is a solution to the problem.

Inserting a solution for t in equation 1 gives the x,y coordinates where the torpedo should be aimed, and where it will hit the target.

Below is an implementation of this, where the constant speed of the torpedo can be set. If there are two solutions, the smallest t is chosen. If there is no solution (typically because the target it too fast for the torpedo to catch) the torpedo is never launched.

 

canvas

As you can see in some cases, this does not take into account the size of the target, only the targets center. This can be remedied by using a representative selection of boundary points of the target instead, and firing if one of them would connect.

The solution does also not take into account how fast the target can change direction, or when the torpedo runs out of fuel. This can be handled by not firing if the time from the torpedo is fired to the impact is too long.

This method can also quite easily be expanded for an accelerating weapon or target. This will result in a higher degree polynomial though, which are mostly only possible to solve using numerical methods like Newtons’s method for example.

The van der Corput sequence

Lately I have been looking for a solid way to create a robust implementation moving a spaceship from one point to another. This turned out to be a hard problem, and led me to a lot of new literature, which included Steven M. LaValle’s Planning Algorithms. Randomly reading from it I found a small gem called the van der Corput sequence.

The van der Corput sequence is useful for sampling in an interval. LaValle discusses it as an option to random sampling within the context of sampling for planning algorithms. I had thought about similar issues in the context of root finding, where I always wondered how to predictably generate a sequence that would distribute samples evenly over an interval, as well as do so in a manner that would not “favor” parts of the interval over others.

One naive way to sample over an interval, is to split the interval in X pieces and do the samples in order. If X is 8 and this method is used the interval would be explored as shown to the left in the figure below (clearly this means the the early parts of the interval will be explored first). Using the van der Corput sequence would result in exploration as seen on the right (which explores the interval much more evenly).

Van der Corput
Naive sampling on the left. Van der Corput sampling on the right. Grey circles show performed samples.

Generating the van der Corput sequence is surprisingly simple and elegant, just flip the bits of the naive sequence as seen in the binary column above. I find this very peculiar, since mirrored donkeys do not normally turn into cheetahs.

The great properties of this sequence is that whenever you end it, it will have explored the interval pretty evenly. A second nice property is that you can easily continue the sequence beyond an initial size, by creating the naive sequence at the position you want to start from, and keep reversing the results.

This method will definitely go into my toolbox of things to consider whenever I am thinking about using random sampling.

Game and application progress

The last weeks I have been very busy trying to finish my game.

The experience so far has not been great. I’m using a Java library called Slick for rendering and basic container for my game. While I was developing my game I have figured out that a lot of the stuff I have made is already present, but often not supporting the exact function I need.

Some of my code is also quite old and naive, and it does have some bad quirks that I have now hopefully fixed.

Anyway I have now added sound effects for many of the mechanics in the game, and it became even more fun. Sound is actually very hard to get perfect, and I have in some areas settled for not perfect since it would take me way to long to find something better.

As far as my other summer programming is coming along, I have got QT and OpenCL cooperating nicely and my prototype program seems to send the stipples to their correct position, what is left of the main tasks is rendering the stipples. Once that is done I will focus on making a GUI for specifying options for the stippling. This includes.

– Scaling up image to have more weights for the stipples.
– Selecting stipple size.
– Specifying threshold for weight value in initial random distribution of stipples.
– Specifying iteration number.

First Post!

It is alive!

My blog has its first post, and all is well.

As a first post I’d like to share the current status of my game as well as some interesting CG topics I would like to look into during summer.

Artifact

My game is called Artifact, and it is an arcade style game. For those who have played Ambrosia Software’s Barrack, my game is very similar, and it was major inspiration for creating this game. The game itself is pretty similar, but introduces some different challenges and a system for better resource management, making the player more in control of the resources he or she has access to.

At this moment the game is fully playable and quite fun. What is left is balancing, and adding sound. The big issue is sound since this is a topic where I have no experience. Hopefully there will be some progress in that domain during summer, so that I can release the game itself this fall or winter.

Summer CG

During this summer I also have some projects that I’d like to finish. During the last semester I implemented a weighted k-means algorithm for creating stipple images. The algorithm was made using GPU through OpenCL for computation. The algorithm worked nicely in Mac OS X, but when transfered to Windows(the assignment used a windows only application) it stopped working properly and instead started crashing when I used above 200 points, though I had tested it on the same graphics card in Mac OS X with 5000 points. Since I had no time to fix it during the semester and I really want to make it work, this summer I will try and create an application to turn any image or animation into a stippled video or animation. I have decided to make it in C++ and QT since I feel I need to be more comfortable with C++.

I also want to test the image space ambient occlusion on some models, and see how well it would function for different types of games.