Posts

Showing posts from August, 2009

Raycasting explained

Image
Raycasting can be an extremely useful tool in computer games. There is a lot of confusion on what raycasting really is and how it can be used. I’ll try to explain some it in simple terms and give some simple examples.Raycasting - as the name suggests involves a ray – but what exactly is a ray?A ray is part of a line which is finite in one direction, but infinite in the other. It can be defined by two points, the initial point, A, and one other, B.

Source: Wikipedia In Farseer Physics Engine we define a ray as two vectors; start and end. We can for obvious reasons not have an infinite length ray, we have to have some kind of boundary where the ray stops. This means that rays essentially become lines and then we simply use those lines to test for collisions with other stuff like other lines, AABB or geometries.Collision testingThere are 4 test cases that can be performed:Point Line AABB Geometry The great thing about all those (except number 1) is that they can be reduced to simple li…

New game using Farseer Physics – Zombies 2.0

A new game just got posted on the Farseer Physics Engine forums, this time it is a zombie survival game. You are the lone protector of a science team, but you do have the choice of 16 different base upgrades and 15 different weapons to help you out. It features real-time lightning and pure action. Check out out!

Simulators And Determinism

Image
When working with simulators, it is important to understand determinism and why we have trouble with determinism across different platform and configurations. Simulators that are iterative converge their solution over multiple iterations and can accumulate system-inherited errors and thus can become unstable over time. Why is determinism importantDoes determinism in simulation systems even matter? The short answer is yes, very important. The long answer is that simulations systems usually base their current world on the previous world. It takes one step at the time (time step) and calculate everything based on the previous step. If you shoot a projectile towards a target it, the trajectory of the projectile will travel in a certain curve. If you run the same simulation on a different platform, the projectile might end up somewhere totally different than the first simulation.Take the following example with a projectile trajectory. They both have the same initial conditions.Simulation o…

Performance tips and tricks – part 3

Image
In part 2 I gave a list of the different C# keywords that could potentially increase the performance of your code. This time we take a look at the different manual inlining techniques – it will not be like the two previous posts as this one can’t be presented in simple code snippets. The compiler is normally in charge of doing those kinds of optimizations, but sometimes it might not because of some requirements. First off, let’s get an overview of the different optimizations done by the C# compiler:Constant foldingConstant and copy propagationCommon subexpression eliminationCode motion of loop invariantsDead store and dead code eliminationRegister allocationMethod inliningLoop unrolling (small loops with small bodies) More…As you see, it is quite effective and contains the mostly used optimization techniques required by modern compilers.Why manually optimize?Well, the problem is that while the compiler almost always takes the right path, there are times where manual inlining is necess…

Performance tips and tricks – part 2

Image
In part 1 I presented you with some tricks on loop optimizations and constants. This time I’ll show you some simple keywords in C# that can speed up the execution of your code for the various reasons.Sealed keywordMarking a class as sealed makes it it unable to be used as a base class. This is primarily used to prevent other classes from deriving from it. This can unlock some run-time optimizations.Before:After:Static keywordYou can use the static keyword to instantiate a copy of a class at run-time and only keep that one copy in memory. You can read more about the static keyword in the link – be careful with it, you should only use it where appropriate.Before:After:Struct keywordThere are two types of allocations in C#: Stack and heap
The stack is where all the value types go: int, char, enum, structs and the like.
The heap is where all the reference types go: class, interface, string and the like.The stack does not get garbage collected and allocations in that memory space is a lo…

Performance tips and tricks – part 1

Image
In this post series I will take a look at the different tips and tricks that can increase the performance of your application. You probably already know some of them and some of them are even just a bit of logical thinking. In any case, it should help you remember the different techniques. I took all these tips and tricks out of my article High Performance Game Development (The revised version – coming out soon) since they apply to almost all languages.Move work out of loopsThis one is kind of obvious, but it can be hard to identify in some cases. You simply move work from inner loops to outer loops or even out of a loop altogether. I’ve made some simple examples of this:Before:After: Don’t use loopsThis is much like the previous one. One important difference is that you don’t use loops at all. You will save a lot of instructions and thus you will have better performance.Before:After:Use constants whenever possibleUsing constants can greatly improve performance. The compiler can make …

The famous inverse square root

Image
I’ve already mentioned before that you can approximate divisions using a division-free Newton-Raphson approximation. You can also use the Newton-Raphson method for approximating the square root and the inverse square root function.But first, what do we actually use inverse square root and square root for? A lot really – everything that uses a normalized vector; collision responses, lightning and reflection to mention a few. It is an important part of any game and the operation has to be as fast as possible. Back in the day when computers had weaker CPUs and no specialized hardware to handle floating point operations (Today we even have specialized physics cards and specialized lightning circuits), some steps had to be taken to compute the inverse square root a million times each second as quickly as possible.And here it is:I could go into details on how this works, but I think it has been described sufficiently on Wikipedia's article Fast inverse square root. Suffice to say that t…

Mathematical operations and micro-benchmarking

Image
You might have heard that the division operation on a modern FPU is slower than a multiplication operation. If you have not heard this before; it’s true – divisions are indeed slower. But why?Without going into the technical details, the divide operation is an iterative algorithm and the multiplication operation is computed directly. One of the more common ways of doing divide operations on a FPU is to use a divide-free Newton-Raphson approximation to get the reciprocal of the denominator and then multiply with the numerator. More on this will come in a later post.Let’s put it to the test.
Here we run 10.000.000 iterations where we divide 500 by 11.5Here we multiply 500 by the multiplicative inverse (reciprocal) of 11.5 From what I described earlier our multiplication example (code example 2) should perform better than the division example. Here are the results:Division: 00:00:00.0010787
Multiplication: 00:00:00.0010871Something is clearly wrong. First off all, they have virtual…

New game using Farseer Physics Engine – Superspace

Another game got posted on our forums. This time it is a space shooter game with cooperative, death match and racing modes. It has 36 different levels for you to play with. The game has great particle effects, nice dynamics and classic sounds.You can view a trailer of the game on youtube: Superspace trailer

Another game using Farseer Physics Engine – Square Off

A new game called Square off just got posted on the Farseer Physics Engine forums. It is created by Gnomic Studios and has entered the Dream Build Play competition.It features great graphics, multiplayer and a huge fun-factor. Take a look at this video to see what I mean.

New game using Farseer Physics Engine - Ninjic

We have about 1300 daily pageviews and  200 downloads each day over at the Farseer Physics Engine project. We also have a quite a few users posting their games for others to review and to show off how they used the engine.A lot of the games are good, but Ninjics surpassed my expectations. The graphics is from UP Studio and the designer and a guy teamed up to create a ninja-style game.See the video of Ninjic on youtube.

Google analytics and Blogspot

I looked around for some statistics to get an idea on the amount of visitors that read my blog. I was surprised that nothing like that existed by default. Google is the owner of Blogspot and they are known for their detailed analytics of the internet and reliable site tracking, so I thought that it was a joke that Blogspot did not have a statistics module by default.Google took the right path.So why not include a statistics module by default? I’ll tell you why; the best sites in the world are defined by their functionality and ease of use. By not including a default statistics module and let the users choose what they like is very clever and gives your users an extremely flexible service.I personally went with Google Analytics. There are several other services that tracks sites statistics. The choice is up to you.

The accuracy and speed of function approximations – part 3

Image
In part 2 we had a look at the accuracy of the approximated functions. In this part we will take a look at the speed of the same approximated functions.There is no reason to use approximation unless you gain something from it. Usually the gain will be in the form of a speed improvement over the real function. Embedded devices with low memory and low frequency CPU can benefit greatly from approximation – even new computers can benefit from it. Lets test it out:The timing depends a lot on the platform and settings. This is compiled under .Net 3.5 SP1 x64 in release mode. Timing is based on 1000000 iterations.The results are clear – the quadratic curve equation is a lot faster than both the Taylor series and real sine function. The quadratic curve equation is also more accurate than the Taylor series.ConclusionIf you are programming for embedded devices such as mobile phones, PDAs or barcode readers, you can gain a lot of function approximations. In this article series we tested the accu…

The accuracy and speed of function approximations – part 2

Image
In part 1 we took a look at two different function approximations; Polynomials and Taylor series. We found out that Taylor series are a lot more accurate than the quadratic equation – or is it?The quadratic equation is fine in some cases. If you want to create a swinging hammer, a wave or the movement for a platform; this approximation is fine. But we can add some extra precision to the function and get it to be even more accurate. The new function looks like this:The first function f defines the sine approximation and the second function g adds some extra precision. The result will look like this:We are nearly unable to distinguish the two lines from each other. And remember from part 1, it is exact in 0, π/2 and π. So using this quadratic equation is really more accurate than Taylor series – but accuracy is not everything. We will take a look at the performance in part 3.Update: Part 3 is here

The accuracy and speed of function approximations

Image
The hard truth of function approximations is that they are not very accurate – that is why they are called approximations (duh). But just how accurate are the different approximations? Here I will take a look at the accuracy of the different sine function approximations.First off, what exactly are we going to approximate? Let us take a look at the sine function in a graph:The X axis goes from –π to π.Let the approximation begin. We start out with a polynomial approximation. We simply use  a quadratic equation to approximate the curve of the sine function as best as we can. I came across a post where a guy used –π, -π/2, 0, π/2,π as points of reference and derived a function from that. He came up with:Without getting too much into the details, this quadratic equation only approximates the curve of the interval [0 ; π]. Putting this equation into a graph with the real sine function gives us this:
Blue is our sine function and red is our quadratic equation. As you can see, the quadratic f…

That new code smell - With C# example

The High Performance Game Development article is coming along fine. I wrote up some C# code that follows with the article, most of the code is examples on transcendental function approximations.Here is a pretty example on a sine function using Taylor Series:publicstaticfloat FastSin(float x)
{
return x - ((x * x * x) / 6) + ((x * x * x * x * x) / 120)
- ((x * x * x * x * x * x * x) / 5040);
}
Much more to come!

Who owns the article?

I've been writing an article called High Performance Game Development for quite some while now, and since it (in my opinion) contains a culmination of high quality knowledge about the complicated area of performance, I would like to make it available to the masses. I went looking for a place to post the article, but was surprised to see that most sites simply takes away your rights to the content of the article. Their disclaimer text often goes like this:
By submitting your article to xxxxxxxx, you are granting to us a permanent, non-exclusive license to use the article in any format we deem appropriate, with the assurance that you will always be given full credit for your work
I was also surprised to see that all sites want you to write the article, then upload it to them. You have no way of editing the article by yourself. You will have to contact the site owners to get your article updated. I can understand why they do this - it must be because of vandalism and inappropriate word…

The state of TTS systems

I have this semi-blind friend that I used to work together with. He uses an application called Zoomtext for reading online news, install applications and so on. The only problem is that the program is poor in quality - always lagging around the screen, crashing and is really heavy to dance with. Being geek by nature I tried to find alternatives and stumbled upon some online TTS (Text-To-Speech) system with some really good quality voices. One of them was iSpeech. It is a webservice based application where you can upload your content for free. But free does not necessarily mean easy, here is what I think about it:1. It is online and thus you can only past it some text and then get the speech results. There are no parsing of documents on the fly so you can read while you listen. This can be solved (sort of), read on...2. Building an application that works together with the parsing engine of Zoomtext seems to be pretty easy. Problem is that each upload of text portion will contain an adv…

New blog

I’ve been thinking about getting a blog, and now it finally happened. Stay tuned…