Monday, October 12, 2009

2D Physics Engine Tutorial – Part 3

In part 2 we had a look at the collision detection part of physics engines. In this post we take a look at the collision response part and see what kind of mechanisms it involves.

Movement

Physics engines have the ability to move objects around both in linear and angular motion. It is done using linear and angular velocity (with speed and acceleration), force and integrators.

Velocity

Velocity is a vector that describes the rate of change in position; the magnitude of the vector is the speed and the direction of the vector is the direction in which the speed is applied.

Velocity definition

901d56d788a63b1a2e5bf684ea444d57

v is the velocity vector, Δx is the displacement and Δt is the change in time.


Force

Force exist in many ways, but generally it is the agent that cause a body to change in motion or make a mass change its velocity. Force has both magnitude and direction and thus it can be expressed as a vector.

Newton’s second law

33559ed31bc09e706e6de860655b1fea

F is the force vector, m is the mass and a is the acceleration vector.


Acceleration

Acceleration is change in velocity over time. Acceleration can be defined by isolating a from Newton’s second law:

Acceleration definition

Newtons2Law

F is the force vector, m is the mass and a is the acceleration.


Integrator

In the previous velocity definition it is stated that velocity is the displacement over time. If we know the current position, velocity and the force that will be applied on it, we can integrate it to find its position and velocity at some point in the future. The integrator performs numerical integration; that is – it takes a small step into the future and tries to find the next position and velocity an object will have – each time it takes a step, it will use the previous result as the new starting point. It works like this:

  1. Use initial position, velocity and force
  2. Step 1 time step into the future and integrate to find the new position and velocity
  3. Add the position and velocity change to the previous position and velocity
  4. Go to step 1, using the results obtained in step 3.

This way we can find the position and velocity of any object at any point in the future.

Euler’s method

Euler’s method is a simple first-order numerical integrator that we can use to integrate the position of an object. The step-by-step method mentioned above is used in Euler’s method.

Solving an example using Euler’s method of integration:

 EulerIntegrationCode

If we run this code, we will get the following results:

Time Position Velocity
0 0 0
1 0 10
2 10 20
3 30 30
4 60 40
5 100 50
6 150 60
7 210 70
8 280 80
9 360 90
10 450 100

The problem with this is that the result is not correct. Using the equation of motion we should get 500 meters:

clip_image002[4]

But we got 450 using Euler’s method. That is because Euler is inaccurate when velocity over the time step is not constant. Using a smaller time step will get us closer to the real result, but it will always have an error.

There are a lot of alternatives to Euler’s method:

All of them are more accurate than Euler’s method, but they can also be slower (RK4 needs 4 steps at each iteration as an example) and they are more advanced.

Overview

Here is an updated overview of the physics engine structure. We just added the Integrator part of the engine.

image

Sunday, October 11, 2009

User managed games and automatic server checks

Let me ask you one thing: Why does network-enabled games utilize user controlled user management (like kick voting menus)?

The answer is really simply: User management

User management

Network-enabled games need some kind of online-police that can control the game and its users. Imagine a rouge user that joins an online game just to create havoc and chaos. I have met several examples myself in my past as both server admin, game moderator and as a player. They all have one thing in common: Make people angry and laugh at their inability to act on it. Let us have a look at the different types of bad guys:

The microphone guy

The first case is a user that connects his microphone, turns up his music (Usually obnoxious repeating music designed to drive people crazy) and press the “talk” button. This can continue the whole game and it makes people furious. Players start to blame the game and game moderators that they are not doing anything about it, but fact is that they are powerless. Once the trend has started, not even an army of server admins can respond fast enough to prevent the damage.

The message spammer guy

This one continues to spam the chat with messages of random characters. Games where the chat is displayed onscreen with the rest of the HUD are the most vulnerable ones. A devious mind can easily exploit the fact that the length of messages are only wrapped at the length of the screen. This means that he can eventually fill up the whole screen with text and make other users unable to see anything.

Example:

Chatspam

The foul mouth guy

The only purpose this guy has is to piss people off. He might not have bad intentions when starting the game, but as soon as someone addresses him, he sees an opportunity of playing a dangerous game of foul-mouthing. All kinds of bad words known to man are exchanged and if the game contains a profanity filter, it also becomes an exercise of finding words that are not included in the game blacklist.

The newbie hater guy

  Games should be equal toward all its users in the sense that it should not prefer experienced users over new users. Once a newbie has achieved some kind of experience, he might feel better when jumping on new players and make them feel stupid. This guy makes experienced users group together and flame the new users and make them feel guilty. It can create a bad user experience and eventually loss of players.

The idle guy

This guy spawns in the game and then go for a 15 minute toilet visit. The word “player” means that the guy is playing – if he is not playing, then he is only in the way of other users. Imagine a line at the supermarket where you have been standing for 10 minutes before you realize that the guy in front of you suffers from narcolepsy and fell asleep while still standing up. (bad example, I know - You get the point)

The newbie general

This kind of guy really depends on the game. Some games contain a general or  commander seat where guy in that seat controls stuff other users can’t. A good example is the Savage game where the job of the commander is giving buffs like heal, extra armor and give negative buffs to the enemy. Each game 1 player gets to know how to command and 10 players get experienced in fighting. This causes experienced commanders to become a rarity. Once a new user is in the commander seat, the game might as well announce the other team as the winners.

The evolution of games

All the cases listed above have in common that they create a bad user experience, lessen the quality of the game and fill up the forums with posts made by furious players. This is reflected in the reputation of the game and the loss of users (and again loss of money).

The solution is quite simple: User controlled user management.

Since old times when the first popular network games started popping up, we have had bad guys. The thing about being a bad guy is that there are no consequences to your actions. They might be kicked if some user decide to report them, but the problem with that is that there might be hundreds of users each day and the response time is not always great. Realizing this fact some games implemented user controlled user management though voting menus and automatic filtering and checks.

Listing the different mechanisms:

  • Aggressive profanity detection
    • Detect profanity and keep a statistic. Kick the user when too much profanity has been detected and remember to warn first.
  • User kick vote
    • Users can initialize a kick vote towards a single user. This is useful in cases where automatic detection fails.
  • Text spamming detection
    • Put in a delay after 3 rapid messages and double the delay time each time this rule is violated.
  • Microphone spamming detection
    • Record the length of time spent on the microphone.
  • User kick/spamming history
    • If a user is constantly getting kicked from servers or has a history of rule violations, investigate the case.
  • Idle player detection
    • When a user has not moved for 1 minute, kick him.
  • Game specific limitations
    • Like the case of newbie commander, make sure that new players are sufficiently experienced before giving them commander status.

The bottom-line is that players and their collective attitude towards the game together with automatic “bad guy” detection is necessary to keep a game playable, we learned that though the evolution of networked games. It is more important than you might imagine and so easy to prevent.

Monday, October 5, 2009

Floating and fixed point arithmetic

A user posted a question on the Farseer Physics Engine forums about fixed point math. The topic include numeral systems, implementation details and performance. A whole lot of posts have been written about it. I’m not going to provide a full introduction to fixed point math, I’m simply going to provide an abstract answer to the questions (one that apply to similar questions).

Background

Back in the good old days (before the Intel i486 CPU) all applications used fixed point arithmetic. Floating point was something new where you could get a tradeoff between space, value range and precision, but at the cost of performance.

Let us take a quick example: A fixed point number with the radix (point/dot) after the forth digit: 5186.3924, would be represented with a floating point as 51863924 with an exponent of 3:

5.1863924*10^3 = 5186.3924

Let us have a look at the up’s and down’s of floating point math.

Positive side of floating point

There are both positive and negative sides of floating point arithmetic. It is basically a tradeoff that the programmer needs to balance; choosing the lesser of two evils.

Greater range and precision

Floating point numbers have a greater range of number representations. You can’t write 0.00001234567 and 12.34567 with fixed point. The radix is fixed! You can with floating point and that is one of the main reasons we use floating point over fixed point. Let us take a look at the following example from Wikipedia:

In a decimal floating-point system with three digits, the multiplication that humans would write as

0.12 × 0.12 = 0.0144

would be expressed as

(1.2 × 10−1) × (1.2 × 10−1) = (1.44 × 10−2).

In a fixed-point system with the decimal point at the left, it would be

0.120 × 0.120 = 0.014.

A digit of the result was lost because of the inability of the digits and decimal point to 'float' relative to each other within the digit string.

Since floating point numbers are split up into 2 numbers: Significant and exponent, it makes sense that the range of floating point numbers is defined by the number of bits allocated to the significant and exponent. There are different types of floating point data types available:

  • Single – Single precision with 32 bits. Called single or float in C#.
    • Range: ±1.5 × 10−45 to ±3.4 × 1038
    • Precision: 7 digits

32bit float

  • Double – Double precision with 64 bits. Called double in C#.
    • Range ±5.0 × 10−324 to ±1.7 × 10308
    • Precision: 15-16 digits

64bit float

There are even 128 bit versions with a higher range and precision.

Negative side of floating point

Floating point numbers comes at a cost. One is space, but that is neglectable in today’s computers with the high amount of RAM and huge bandwidth. More important is accuracy and performance of the arithmetic operations associated with floating point.

Performance

As mentioned before, the i486 CPU was the first CPU to get an FPU and thus the floating point operations were no longer emulated (or run via a coprocessor). This sped up the operations by a large factor. Nearly all CPUs today have an FPU located inside of them. Graphics cards are also one big FPU – it specializes in floating point math and can process a huge amount of floating point numbers.

So what is the problem?

Well, as the forum post points out, some devices does not have a FPU and even if they do, their floating point operations can be magnitudes slower than fixed point operations. A good example is the Xbox 360 platform. It does have an FPU and it even has the AltiVec instruction set. But the software designed for the Xbox 360 (the .Net Compact Framework - NetCF for short) does not utilize those instructions. This means we have lower floating point throughput on the Xbox360.

Accuracy

Floating point numbers have a bad reputation of being inaccurate. Floating point are not able to represent numbers like π or 0.1 correctly and inaccuracies may create inconsistency in your application. Lets take an example:

If you take the sine of pi, then it should yield zero: sin(π) = 0
That is not the case with most (if not all) floating point implementations.  sin(π) in C# yield the following result with double precision:

1.22460635382238-16

Equality checks are also a cause of concern. If you check a condition like sin(π) = 0 then it will yield false even though it is mathematically true. Normally we use epsilon and check the equality up against that.

The crazy part of this is that the floating point standard is not the same on different platforms. The implementation on an Intel CPU might be different from an AMD CPU. The differences can also sometimes lie in the operation system – further fueling the inaccuracies across platforms.

The solution

There are no perfect solution. As mentioned before it is a tradeoff and sometimes floating point is the way to go. However, there are some alternatives.

Fixed point

Fixed point math is based on simple integers. You can represent the number 1.200 by the value of 1200 and a scaling factor of 100. Most fixed point libraries implement a fixed point version of integer and then use bit-shifting to scale the values.

Fixed point math has some advantages over floating point:

  • Same behavior on all platforms (deterministic)
  • Faster on platforms without FPU (and sometimes even with FPU)
  • Lower space usage

But as always, there is a downside too:

  • Complex implementations
  • Lower range of values
  • Overhead of constantly scaling values
Double precision

Double precision floating point data types are 64bit and have a higher precision than normal 32bit floating point. This is not really a solution as it simply shifts the problem to a whole other dimension. It might lower the impact of the problem, but it does not go away. Sometimes it is sufficient to switch to doubles and it is far easier to do than converting everything to fixed point math.

This solution only works on platforms with an FPU as it will run even slower than single precision floats.