# Question
Title: Finding roots/zeros for collision detection?
For the most simple of 2D games, I have implemented *a posteriori* collision detection (overlapping rectangles) on the x/y Cartesian plane, but am now interested in understanding the basics of *a priori* collision detection...

In the link here, I noticed the reference to Newton’s Method. So, I want to better understand the link b/w finding zeros of an equation and detecting *a posteriori* collision.

Let's start with the most obvious case of finding roots of an equation: If you have a projectile's trajectory modeled as a quadratic function, you can find the roots to predict at what time the height will equal zero (or any other constant height, actually, by just solving f(x)=C to be f(x)-C=0 and then finding roots of that expression).

So, as I understand, finding the root can tell me the time at which the object will be at any chosen height. More broadly, we basically know the (x,y) location of the object for any given time. But how does root finding, in particular, translate to detecting collisions with another object? (The other object may be stationary, or be moving. If the latter, do you also determine roots/location of this moving object as well? Calculate the (x,y) trajectory of both objects and determine where they will intersect?)

Again, the basic question is where does root finding come into play? Any links to a basic primer on this topic, with a simple example would also be greatly appreciated.

# Answer
Root finding is used to calculate when two objects intersect (distance = 0 ) a basic example could be a Sphere/Plane intersection, This is solved easily by calculting the distance between the sphere and the plane and checking if it's near zero. Now the problem here is that we assumed that both objects are stationary and wont't change their position .

The more interesting thing to talk about, is actually when root finding using numerical analysis methods comes to play when you want to calculate dynamic collision detection, in other words when your objects are moving and you want to take time into account.

Your static collision detection methods can't predict that your object at `t+ delta t` will be at a different position because it doesn't take time into considerations, so the collision check might happen in a frame where the object has already passed the obstacle, this is also called **quantum tunneling** or **tunneling**. This happens due to the discrete nature of computers, that updates the program each frame/delta time.

It's best to explain using examples, so let's say you have a wall (Plane) and a moving ball.

Dynamic Collision Detection is used to avoid the drawback of static collision detection tunneling. So instead of checking statically each frame or number of frames, you instead model the ball/object movement with respect to the plane as a function of time. This can be numerically solved to find the root `(t)` when the motion curve of the ball intersects with the plane.

So now instead of only checking for collision at `T0` and `T0 + delta time` we can take into consideration the time interval between those, where your application fails to model due to it's discrete nature.

Keep in mind that not all dynamic collision detection cases need to be solved using numerical methods. Analytical methods can also come to play which is actually faster, but this is only true for specific cases of motion and shapes.

Your best bet is getting real time collision detection or real time rendering, both books will give you an overview of the techniques with code samples. However the resources on the internet for this topic is scarce, these links can be a good start although nothing straightforward:

Collision detection tutorial, have a section on dynamic collisions detection and source code.

David Eberly's paper on dynamic collision detection, great info but might be a bit heavy.

Real time rendering companion website with a lot of resources, some of them are on static and dynamic collision detection.

But keep in mind that that static collision detection might be enough if your objects are not moving quickly, so make sure you need dynamic collision detection before you implement it, but regardless learning is never a bad thing.
> 3 votes

---
Tags: collision-detection, mathematics
---


# Question
Title: How to call game Update from another form
I have three projects in one solution:

* a form with some tool (see it as a level-editor), in which there is PictureBox where I want to redirect drawing of the game.
* My game, with some methods and its Update/Draw methods:
* A launcher (where I can start the game or start the level-editor)

```
 protected override void Update(GameTime gameTime) {...}
 protected override void Draw(GameTime gameTime) {...}

```

This is the launcher's "Open game in editor mode" button code:

```
private void cmdEditorMode_Click(object sender, EventArgs e)
{
    using (Game1 game_instance = new Game1(true))
    {
        using (MapEditor form = new MapEditor())
        {
            form.Show();
            form.game_wrapper = new GameWrapperForLevelEditor(
                game_instance,
                form.pctSurface.Handle,
                form,
                form.pctSurface);
            game_instance.Run();
        }
    }
}

```

Note that:

* `true` in Game1 constructor is just a bool used to tell the game to open it in editor mode.
* `GameWrapperForLevelEditor` is another class used to make the form of the level editor and the Game itself in relation.

In particular (to draw inside the pictureBox drawSurface):

```
 public GameWrapperForLevelEditor(
            Game1 game,
            IntPtr drawSurface,
            System.Windows.Forms.Form parentForm,
            System.Windows.Forms.PictureBox surfacePictureBox)
        {
            graphics = new GraphicsDeviceManager(this);
            //...
            //...other things
            //...
            graphics.PreparingDeviceSettings +=
                new EventHandler<PreparingDeviceSettingsEventArgs>(graphics_PreparingDeviceSettings);
        }

```

and:

```
 void graphics_PreparingDeviceSettings(object sender, PreparingDeviceSettingsEventArgs e)
 {
    e.GraphicsDeviceInformation.PresentationParameters.DeviceWindowHandle = drawSurface;
 }

```

This is the launcher's Main code:

```
using System;
namespace Launcher
{
#if WINDOWS || XBOX
    static class MAIN
    {
        /// <summary>
        /// The main entry point for the application.
        /// </summary>
        static void Main(string[] args)
        {
            using (Launcher_form form = new Launcher_form())
            {
                form.Show();
                //Creo un'istanza del picture_box_render all'interno del form
                form.picture_box_render = new launcher_picture_render(form.pctLauncher.Handle);
                form.picture_box_render.Run();
            }
        }
    }
#endif
}

```

Note that:

* I use here another game (`picture_box_render`) because in my launcher's form I put a picture box where I want to run an animation that is rendered as another game loop.

Finally the draw part:

```
protected override void Draw(GameTime gameTime)
{
    GraphicsDevice.Clear(Color.Black);

    spriteBatch.Begin(SpriteSortMode.BackToFront, BlendState.AlphaBlend);
    spriteBatch.Draw(game.LastRender, Vector2.Zero, Color.White);
    spriteBatch.End();

    base.Draw(gameTime);
}

```

**My problems are:**

* `game_instance.Run();` (up) gives me this error (translated from italian, so sorry):

> Starting a second message loop on a single thread is not valid operation Use Form.ShowDialog.

* `game.LastRender` is Always empty because the game never run. `game.LastRender` is just a `RenderTarget2D` where Game1 draw method draws the game.

As a solution, I thought that I may don't `game_instance.Run();`, but just use `game.Update(...)` and `game.Draw(...)` inside my wrapper class. The problem is that these two methods are `protected`, and if I try to set them `public` it says me that I can't.

What am I doing wrong?

# Answer
You should use the **official sample**. It demonstrates *exactly* how to get XNA to output inside WinForms.

Any other method for doing this is almost certainly wrong and will either fail outright, or fail unexpectedly in certain circumstances.

---

To use the official sample, you will have to extricate your existing code from the `Game` class. This means you must implement your own `Draw` and `Update` methods, your own timing mechanism (you can use `System.Diagnostics.Stopwatch`), and possibly a replacement for `GameComponent` (if you use it).

I find it helps to separate your game into three projects: A shared "**engine**" XNA library, a "**game**" XNA project, and an "**editor**" WinForms project.

Then use the "game" and "editor" simply as thin wrappers for setting up the graphics device and calling your own `Update` and `Draw` methods on your own class in your "engine" project.

If you want a launcher, it's probably best to create a fourth project to contain it. I'd simply have it invoke the selected executable.
> 0 votes

---
Tags: xna, c#, windows-forms
---


title: Angle between two planes

text:
# Question
Title: Angle between two planes
I have two triangles in 3d space which share 1 edge and I would like to determine if the angle between their normal vectors is "uphill" or "downhill". In other words, if you set one flat, would the angle between them be acute (uphill) or obtuse (downhill). Hopefully that makes sense.

So far I have the normal vectors of each triangle and have calculated the angle between the two triangles, however this angle is always \>= 90 degrees.

```
Vector3 v1 = triangle1.Normal;
Vector3 v2 = triangle2.Normal;
float cosAngle = Vector3.Dot(v1, v2) / (v1.magnitude * v2.magnitude);
float degAngle = Mathf.Acos(cosAngle) * Mathf.Rad2Deg;

```

Is there a trick I am missing that lets me determine which direction this angle is in?

# Answer
Here is my suggestion. You just need two vectors.

* in the first triangle, choose the normal vector, **n1**
* in the second triangle, choose a vector **e2** from a point *on* the shared edge to the point *not* on the shared edge.

Then compute their dot product: **n1 . e2**. If it’s positive, the angle is acute. If it’s negative, the angle is obtuse.
> 5 votes

# Answer
Consider the plane parallel to the normal of the first triangle and containing the shared edge. You can find a vector normal to this plane by crossing the shared edge with the normal of the first triangle. Then take the dot product of this vector with the second triangle normal - the sign of the dot product will tell you whether the shared edge forms a hill or a valley (with zero indicating the triangles are co-planar to within the available precision).

A picture should help explain why this is so. I'm visualizing it with quads because it's easier to show perspective, but it applies equally to triangles. Note that your signs may be reversed based on various choices of coordinate system/order of terms.
> 3 votes

---
Tags: 3d-meshes, linear-algebra
---


title: Do videogames use numerical solutions?

text:
# Question
Title: Do videogames use numerical solutions?
Do video games often use numerical solutions in their calculations, such as you might generate using software like MATLAB or Mathematica?

Perhaps for making formulas for AI, or for game physics implementations?

# Answer
> 3 votes
### Mathematics

While I of course can't guarantee that no counterexample exists, in general maths software will not help you write videogames. While such packages can solve some incredible mathematical problems, it is not the kind of problems you generally face when writing a game. Remember, maths software does not write code, it doesn't even write expressions, it merely transforms the expressions that you feed to it.

Almost all the maths I use as a programmer, whether writing games or other software, is basic algebra. The true art of programming is to find solutions to open ended and vaguely defined problems, such as "How can I convey all the relevant information to the user in a simple and intuitive manner?", or "How can I make the jumping mechanic feel good?". Good luck feeding those problems to Mathematica.

### Physics

Your question implies being about physics simulation, and that is typically the most maths-heavy part of a videogame. While a good engine will usually use some clever formulas derived using differential maths in order to be as accurate as possible (see for instance Why is RK4 better than Euler integration?), numerical integration is pretty much the only thing you can do.

* First of all because the objective is not to find a finite solution, it is to produce a game state 60 times per second that can be used to render the world to the user, so no matter the method you would have to make at least that many individual calculations anyway.
* Second because the simulation is constantly changing, if nothing else at least the user input will be an unpredictable factor, you can't put that in a closed form formula.
* Third because even moderately complex scenarios are impossible to solve analytically, you don't need to go further than the Three-body problem to find an example, compare the complexity of that to a typical videogame and it is pretty clear that task is hopeless.

---
Tags: mathematics, numerical-methods
---


title: Rotate Camera as an Object Manoeuvres

text:
# Question
Title: Rotate Camera as an Object Manoeuvres
There are loads of questions (all of which I have looked at) on here about cameras following objects. Using them, I have successfully got my camera to follow my car when driving, but I am unable to make the camera swing right when the car turns left (so it stays directly behind it) and vice-versa.

So far, this is how I've got my camera following my object:

```
    camOrigin.x  = (0   +globalPos.x+velocity.x); //Camera Position
    camOrigin.y  = (0   +globalPos.y+velocity.y);
    camOrigin.z  = (100 +globalPos.z+velocity.z);
    camLookingAt.x = (0 +globalPos.x+velocity.x); //Camera Looking at Object
    camLookingAt.y = (0 +globalPos.y+velocity.y);
    camLookingAt.z = (0 +globalPos.z+velocity.z);
    camNormalXYZ.x = (0);                         //Camera Normal = Y
    camNormalXYZ.y = (1);
    camNormalXYZ.z = (0);

```

I have tried to use the same algebra I've used to calculate the cars direction and velocity because I figured the angle the camera moves would be the inverted angle the camera needs to move, but it didn't work.

```
    camOrigin.x  = (0   +globalPos.x+velocity.x-sin(rotX_rad)); //Camera Position
    camOrigin.y  = (0   +globalPos.y+velocity.y);
    camOrigin.z  = (100 +globalPos.z+velocity.z-cos(rotX_rad));

```

I'm unsure how to take this further.

Edit: Little drawing to help describe the movement. I'm looking to move the camera from c to d when the car turns in the left direction (and vice-versa when turning right).

**Update:**

```
    rotX_rad = rotX*PI/180;     //convert to radians
    velocity.x = sin(rotX_rad); //calculate X coord
    velocity.z = cos(rotX_rad); //calculate Z coord

    //globalPos + velocity;
    globalPos.x + velocity.x*delta;
    globalPos.z + velocity.z*delta;

    ModelViewMatrix = glm::translate(viewMatrixMovingCube,globalPos);           //move/update car

    ModelViewMatrix = glm::translate(ModelViewMatrix,  glm::vec3(0,-48,0));     //position low on screen
    ModelViewMatrix = glm::rotate(ModelViewMatrix, rotX, glm::vec3(0,1,0));     //manually turn/control rotation of car

```

# Answer
A common base approach is to model the camera as though it were towed behind your character/vehicle on a free-swinging bar.

To do this, you keep track of an intended follow distance d and an intended height h.

Each frame, take the vector from your follow target (after it has moved) to the camera (before it has moved). Normalize it, multiply it by d, then correct the height to h. Now add it to your follow target's position to get your new camera position (you can either set it directly, or lerp the camera toward it for a softer camera feel)

This gives a camera that will be gradually pulled behind you anytime you move away from it. It's a conceptually-simple base, but it has some problems on its own so you'll need to layer additional behaviour on-top:

* The speed with which the camera gets behind you is inversely proportionate to the follow distance - a close camera swings responsively (maybe even a bit twitchy) while a distant one barely moves. You can fix this by tracking a "fake" camera at a fixed distance from your player that feels like the right balance, then multiplying its offset by a scaling factor to get your real camera offset.
* It needs some help getting around sharp corners. Normally it follows a curve of pursuit, which means it lazily cuts corners whenever it can. Adding a multiple of the player's "back" vector (negative forward) to the offset before you normalize it helps.
* Play with the look direction - you'll probably want the camera to look at a point above the follow target, and a ways ahead of it (this pushes the target toward the bottom of the screen so you can see more of what's ahead). Biasing this anticipation vector according to velocity and steering can help the camera feel responsive, without it moving around too much.
> 4 votes

---
Tags: c++, camera, vector
---


# Question
Title: Detecting right/left collisions with a bounding box
I'm building a platformer in cocos2d, my first game project. I'm working on movement and collision detection. I'm using a tilemap with a "meta" layer of invisible blocks that are designated collidable.

Everything seems to work pretty well except for one minor detail: when the character jumps from above into a platform, he does not fall but clips through it. If he jumps from below, it recognizes it and resets his Y velocity accordingly. I know that it's because of how I'm detecting the collisions, and just doing a simple comparison of the origin.y's, but I'm unsure of how to refactor this code better:

```
- (void) update: (ccTime) dt {
    CGPoint scaledVelocity = ccpMult(leftJoystick.velocity, 35.0f);
    CGPoint newPosition = ccp(player.position.x + scaledVelocity.x * dt, player.position.y);
    CGPoint oldPosition = [player position];

    float velocityX = player.Velocity.x + scaledVelocity.x * dt;
    float velocityY = player.Velocity.y;

    BOOL isCollision = NO;
    BOOL isCollisionBelow = NO;
    BOOL isCollisionRight = NO;
    BOOL isCollisionLeft = NO;

    NSMutableArray* collisionSprites = [[NSMutableArray alloc] init];

    if (oldPosition.x > newPosition.x) {
        player.flipX = YES;
    }
    else if (oldPosition.x < newPosition.x) {
        player.flipX = NO;
    }

    for (CCSprite* sprite in gameplayLayer.collidableTiles) {
        if (CGRectIntersectsRect(player.boundingBox, sprite.boundingBox)) {
            isCollision = YES;
            [collisionSprites addObject:sprite];
        }
    }

    // Figure out which direction collision is in
    if (isCollision) {
        for (CCSprite* collisionSprite in collisionSprites) {
            if (collisionSprite.boundingBox.origin.y < player.boundingBox.origin.y) {
                isCollisionBelow = YES;
            }
            if ((collisionSprite.boundingBox.origin.x > player.boundingBox.origin.x) && (collisionSprite.boundingBox.origin.y >= player.boundingBox.origin.y)) {
                isCollisionRight = YES;
            }
            if ((collisionSprite.boundingBox.origin.x < player.boundingBox.origin.x) && (collisionSprite.boundingBox.origin.y >= player.boundingBox.origin.y)) {
                isCollisionLeft = YES;
            }
        }
    }

    if (isCollisionLeft) {
        velocityX = 0.5f;
    }
    else if (isCollisionRight) {
        velocityX = -0.5f;
    }

    if (isCollision && !isCollisionBelow && player.characterState != kStateFalling) {
        velocityY = 0;
        velocityY -= 0.8f;
        [player setCharacterState:kStateFalling];
    }
    else if (!isCollisionBelow) {
        velocityY -= 0.7f;
    }
    else if (isCollisionBelow) {
        velocityY = 0;
        [player setCharacterState:kStateIdle];
    }

    if (rightButton.active) {
        if (player.characterState != kStateJumping) {
            velocityY += 15.0f;
            [player setCharacterState:kStateJumping];
        }
    }

    // Ground friction
    if (player.Velocity.x > 0) {
        if (player.Velocity.x < 0.5f) {
            velocityX = 0;
        }
        else {
            velocityX -= 0.5f;
        }
    }

    if (player.Velocity.x < 0) {
        velocityX += 0.5f;
    }

    [player setVelocity:ccp(velocityX, velocityY)];
    [player setPosition: ccp(player.position.x + player.Velocity.x, player.position.y + player.Velocity.y)];
    [gameplayLayer setViewpointCenter:newPosition];
    [player setOldPosition: player.position];
}

```

How can I refactor this code to work properly from all angles and reduce the complexity (I feel that there's too many booleans, and they all get a bit confusing).

# Answer
> 1 votes
As far as I know the Boundingbox rect has two properties `origin` and `size`. to check if some obejct is colliding from any of the sides you have to check both values: so I suggest you change your code like following :

```
if (CGRectMaxY(collisionSprite.boundingBox) < CGRectMinY(player.boundingBox)) {
    isCollisionBelow = YES;
}
if (CGRectMaxX(collisionSprite.boundingBox) < CGRectMinX(player.boundingBox)) {
    isCollisionRight = YES;
}
if (CGRectMinX(collisionSprite.boundingBox) > CGRectMaxX(player.boundingBox)) {
    isCollisionLeft = YES;
}

```

# Answer
> 0 votes
I'm afraid I dont have an answer in cocos2d, but i can give it to you in pseudocode.

**Summary**
The point with doing collision detection is to stop the player before it collides with an object. To do this you simply need to check if the players new position collide (or intersects) with the object, and then change the players position.

**How to do this:**
To do this you create a function which you call every time you're about to change the players coordinates. This function simply calculates the new position then passes it to a another function which then check if the new position collides. Then if the new position does not collide, change the players position, and voila collision detection and reaction!

**Example:**
If the player presses left --\>
Calculate players new coordinats --\>
New\_position.x = player.x - (movement\_speed * delta-time) --\>
Check new\_position.x for collision --\>
If new\_position.x collides - do nothing --\>
If new\_position.x does not collide - change players.x to new\_position.x --\>

This way the collision check never returns true for the players actual position, thus allowing the player to move freely even if it is on top of the object (theoretically colliding with the object).

If you want the collision to be more true to real physics you could of course always change the players position, but if it collides change the force (or movement speed) to zero.

There are of course other ways of doing this. For example one could check the players position according to the object (left\_zone, right\_zone, top\_zone, bottom\_zone), but this would be much slower and requires a lot more code.

Basic collision detection function (written in javascript, but should be easy to understand):

```
function collision(obj_1, obj_2) {
    var collision = Boolean(
        obj_1.x <= (obj_2.x + obj_2.width)
        && obj_2.x <= (obj_1.x + obj_1.width)
        && obj_1.y <= (obj_2.y + obj_2.height)
        && obj_2.y <= (obj_1.y + obj_1.height + height_margin)
    );

    // return true or false
    return collision;
}

```

---
Tags: iphone, cocos2d-iphone, cocos2d, objective-c, platformer
---


title: up vector for quaternion

text:
# Question
Title: up vector for quaternion
First, I know there's a question exactly like mine, and some ohter really close, but my implementation of the solutions didn't work at all. Ok, now to the question.

I created some forms of camera based on quaternions, however, for my *orbit/chase* camera every quaternion I create will roll the camera in an uncontrollable manner. What I want is a function like Unity's Quaternion.LookRotation where you can pass an up vector. This is a simplification current attempt of implementation:

```
Vector3 target = -Position; //Because we're looking at the origin
target.Normalize();

float cosine = Vector3.Dot(Vector3.Forward, target);
Vector3 axis = Vector3.Cross(Vector3.Forward, target);
Rotation = Quaternion.CreateFromAxisAngle(axis, (float)Math.Acos(cosine));

//Trying to unroll up vector to Vector3.Up
//based on the other answer but results were unchanged
Vector3 rolledUp = Vector3.Transform(Vector3.Up, Rotation);
Vector3 right = Vector3.Cross(target, Vector3.Up);
Vector3 newUp = Vector3.Cross(right, target);

Vector3 axis2 = Vector3.Cross(rolledUp, newUp);
float angle2 = (float) Math.Acos(Vector3.Dot(rolledUp,newUp));

Rotation = Quaternion.CreateFromAxisAngle(axis2, angle2) * Rotation;

return Matrix.CreateLookAt(
    cameraPosition: Position,
    cameraTarget: Vector3.Transform(Vector3.Forward, Rotation),
    cameraUpVector: Vector3.Transform(Vector3.Up, Rotation));

```

If my sleepiness got in the way of my clarity, here's what I have:

and here's what I want:

# Answer
you should only need to rotate around the y axis or you can just say to look at the point on the y-axis at the same height of the camera

```
target.y=0;
target.normalize();

```

of course then you can start to optimize because `axis` is `(0,1,0)` and all the other ups will be the same again (do double check that though)
> 0 votes

---
Tags: xna, rotation, quaternion
---


title: Where is MonoGame's API reference?

text:
# Question
Title: Where is MonoGame's API reference?
I wanted to pick up Monogame, but I can't find documentation. All I see on GitHub is some tutorials. I'm looking for class reference like this from XNA.

# Answer
> 3 votes
MonoGame's documentation portal is here. They don't appear to currently have an API reference as of this writing.

I would venture to guess that this is because MonoGame's API tries to be identical to XNA's, so you can probably get away with just using XNA's API reference. The focus of the MonoGame project appears to be on longer-form documentation like tutorials and the like at the moment.

# Answer
> 0 votes
Monogame's documenation can be found on their site: http://monogame.net/documentation

They also have tutorials on their github page: https://github.com/mono/MonoGame/wiki/Tutorials

If you're looking for detailed documentation like Microsoft has, you're out of luck. Monogame is an opensource engine. Not a well funded company like Microsoft. Documentation is the last thing developers usually want to work on, so when they aren't being paid for it, it's the last thing (if ever) to get done.

---
Tags: c#, monogame, documentation
---


# Question
Title: How to correctly aggregate networked data into UDP packets while avoiding fragmentation
I am starting to get my feet wet with game networking, having iterated many times now on some simple 2D games. For learning purposes, I've read the fantastic Gaffer on Games networking article a couple of times, the Source networking article, and the Quake sourcecode review about networking. I'm feeling comfortable with the concepts discussed there.

My question is about the proper implementation of data buffering within a game loop, with the intention of optimizing performance, and keeping **IP fragmentation in mind**. I'll give a python pseudocode example from just the client perspective, for simplicity. Also assume we are using UDP sockets.

Let's say hypothetically there are some events that can occur client-side, which should be transmitted to the server. Let's encapsulate this data in a simple dictionary called a **message**. A single message might look like this:

```
message = {
  'type': 'move',
  'data': 'right',
}

```

Within a single iteration of the client game loop, its possible for many of these messages to be generated. Here's an ultra-stupid game loop that might do this:

```
def main_loop():
    if game.input.buttonA:
        send_message({'type': 'foo', 'data': 'bar'})
    for event in game.system.events:
        send_message({'type': 'event', 'data': event.data})
    game.render()

```

A naive implementation of `send_message()` would be to serialize the message and fire it off in a packet to the server immediately. The problem with that is that we could be potentially sending hundreds of packets per frame--I don't understand the low level details but I would think flooding the socket like this would be dangerous and bad.

Since these messages are really small when serialized, like \<50 bytes, we could batch them up together in a single packet to send to the server. The implementation of that might look like this:

```
# Queue a message instead of sending it immediately
def queue_message(msg):
    message_queue.push(msg)

# Flush the message queue into a single stream, JSON serialize and send to server
def flush_messages():
    buf = []
    for message in message_queue:
        buf.append(json.loads(message))
    socket.send(''.join(buf))
    message_queue.clear()

def main_loop():
    if game.input.buttonA:
        queue_message({'type': 'foo', 'data': 'bar'})
    for event in game.system.events:
        queue_message({'type': 'event', 'data': event.data})
    game.render()
    flush_messages()  # Send actual packet at the end of the loop

```

This seems much better, because we're sending far less packets per frame by grouping messages together. But what happens if the game loop generates a LOT of messages? Well, if the total packet size is over the MTU (around 1500 bytes for UDP), then we're going to experience fragmentation.

Lets say you send a 2500 byte packet. It will get fragmented into two separate packets and then reassembled transparently on the other end. From how I understand it, the problem with this is that if either half gets dropped, the whole packet is lost. When we're dealing with a highly realtime networking architecture like a game here, I think we actually would prefer to have only half of those messages and get the other half later, rather than none at all. *Especially* because the messages dont have any dependency on each other, they are just little chunks of data.

The problem I'm facing now is how to properly implement **application level fragmentation**, such that I can control how packets get split up. One way to do this would be to go through all my messages, putting them into packets until the packet is full, and then create a new packet, finally sending all of the packets at once.

```
def flush_messages():
    buf = []
    bufsize = 0
    packets = [buf]

    # Stuff messages into packet buffers, overflowing into the next when we hit MTU
    for message in message_queue:
        msgsize = len(message)
        if bufsize + msg_size > MAXIMUM_PACKET_SIZE:
            buf = []
            bufsize = 0
            packets.append(buf)
        buf.append(message)
        bufsize += msgsize

    # Send all packets now and empty the message queue
    for packet in packets:
        socket.send(''.join(packet))
    message_queue.clear()

```

Another way would be to simply only send the first 1500 bytes worth of messages this frame, and allow the rest to be handled the next frame.

```
def flush_messages()
    buf = []
    bufsize = 0

    for message in message_queue:
        msgsize = len(message)
        if bufsize + msgsize > MAXIMUM_PACKET_SIZE:
            break
        buf.append(message)

    # Send packet, but DONT clear message queue
    socket.send(''.join(buf))

```

Of course, this latter approach has the danger of the buffer climbing over time and the server experiencing massive lag with respect to the client.

What's the right way to do this? Is my buffering approach here is wrong to begin with?

# Answer
First off, you misunderstand how UDP works:

> Lets say you send a 2500 byte packet. It will get fragmented into two separate packets and then reassembled transparently on the other end.

UDP datagrams are atomic. An UDP datagram will not be split up into packets.

I recommend sending the data in small atomic datagrams. The overhead is typically 28 bytes, not too excessive for 50 byte messages I think. If you want to batch them together, that is fine, but do not exceed 1500 bytes.

Make sure your datagrams are self contained, and useful in and by itself. Do not spread a single message over two datagrams, if one gets lost, the other is of no use.
> 3 votes

# Answer
> The problem I'm facing now is how to properly implement application level fragmentation, such that I can control how packets get split up. One way to do this would be to go through all my messages, putting them into packets until the packet is full, and then create a new packet, finally sending all of the packets at once.

This is the gist of the correct approach. More sophisticated approaches need to take into account message priority and volatility. Given a particular client (player), consider two different objects in your game: one is another visible but distant player and the other is an NPC about to attack the client's avatar. Assuming you have only the space left in your out-going packet for the update of one or the other you must have a way to choose which to go with. This will generally be based on a combination of factors both static and dynamic. Players typically have a higher static priority than NPCs but closer entities are more important than distant ones. Some calculation needs to - for each client - determine the current priority of each sending object or message. For instance, that NPC about to attack should be of the highest priority since it has the most impact on the client's game experience, even though you usually want all the other players to have high priority normally to keep the social and multiplayer aspects of the game running smoothly. Priority can go as low as "off" as in the usual kind of AOI filtering; distant objects probably don't need to be updated on the client at all (and in fact, not sending updates for non-visible objects is an important anti-cheating behavior in some kinds of PvP games). Object priority can also include time since last update to ensure that even low-priority objects will be updated periodically even under higher message loads. Remember that these values are *per-client* for any dynamic value; what's high priority to one player's experience will not be high priority for another's in many cases, especially for players that are far apart from each other.

A second consideration is that of volatility. Say an object A generates a new set of position/rotation/velocity values each frame and we want these updates to be network replicated. If during the last "network frame" you were unable to fit object A into a packet but you are this network frame, surely you don't want to send two copies of A's information (one stale) and use up all that extra space. In your message queue, you need a way to know that a particular message replaces another rather than retaining old copies of volatile data. The client doesn't need to know about the intermediate positions; only the most current. Client-side prediction and interpolation will deal with smoothing over the missing intermediate position data. Some messages are *not* volatile, however. A "player fired his gun" message should always be delivered to ensure that everyone sees the firing animations and doesn't miss one. Some messages may even be relevant to gameplay and the state changes they trigger may be essential, though in general you should prefer sending the current state (which is volatile) rather than sending signals to change state (which are non-volatile).

These both play into packet retransmissions, too. Instead of trying to retransmit a whole packet you can be more intelligent and only attempt to retransmit any non-volatile and non-supceded volatile messages that were in that packet. Given that most messages should be volatile in the typical game, this means that retransmissions will be of smaller size than their original packets and multiple retransmissions of the same data will not grow particularly quickly. You can then often keep a single fixed-rate packet stream even in the face of dropped packets.

So far as worrying about objects trying to send too many messages for one packet: just don't do that. The absolute most important thing you can do (aside from making it all actually work, of course) is to add very comprehensive and detailed debugging, timing, and profiling tools to your networking library. You should be able to see at a glance which objects are sending messages, how many messages they're sending, current priorities of objects and messages, number of bytes being generated per object, the per-frame message and byte rates of the game, etc., all both incoming and outgoing. Being able to dump stats in a textual format is nice; being able to visualize graphs of game sessions is even nicer; being able to visualize real-time in-game graphs is nicest (though you'd still want the other two). The ability to capture and replay the network game is also exceedingly handy. In the end, you should have the tools on hand to simply make sure your game isn't trying to generate too much data to fit in one packet. If you're having trouble, either consider raising your game's bandwidth requirements (many people use requirements based on advice from past generations of game consoles and their lower limits) or consider trimming some of the "fat" out of your network data.

Remember that with a combination of priorities and sensible update rates you can cut traffic quite a bit. A game object doesn't need to constantly retransmit its health but can instead only transmit it when it changes. Lots of game state can be updated very infrequently. Take a game timer for instance. Once a clock is synchronized, the client can be trusted to tick it appropriately. Periodically resynchronize the clock just to account for any drift rather than trying to send a current value every network frame. With a single synchronized clock you can then express many other more complicated messages as simple clock deltas (say, instead of a large absolute time value you can now use small deltas from the clock, allowing more bit-level compression).

That last aside bringing up the point: get comfortable with bit-level compression. It's especially common for those working in higher-level languages like Python to be less aware of the tricks you can do with bit twiddling and compression. Numbers you know to always be small can be encoded with less bits. String/enum values can often be replaced with much smaller indices to pre-computed (or at least pre-agreed-upon in early initialization messages) tables. A 3x3 rotation matrix (9 floats) can be trivially converted to one quaternion (4 floats). The quaternion can then be further optimized since we know we're always using unit quaternions: we can drop one component (now down to 3 floats) and then use much smaller IEEE754-like formats (or a fixed-precision format) often dropping the per-component size pretty far below their usual 32 bits. Given that most of your messages are likely to be position/rotation/velocity updates, figuring out how to best compress those values will give you a lot of bang for the buck.

There's a lot to be said for how you package up multiple messages giving further advantage to sorting them before packing them. Take again the pos/rot/vel updates. If you're sending lots of them per packet, consider having a single update message that encodes a list of updates rather than each update individually. Assuming you need both the update data itself and an object ID, you can reduce things from a packet payload of `msg_header|id|data|msg_header|id|data|msg_header|id|data|...` to `msg_header|count|id|data|id|data|id|data|...` which results in a net saving of payload size after only a few messages (by removing the need to repeat the the `msg_header` data more than once). Obviously if you have only one of a given message then the `count` field may end up being a net loss in terms of size reduction so this trick needs to be thoughtfully applied to only specific messages (or thoughtfully encoded if you want something very generic). You could even reduce the need to repeat `id` much or at all if you can figure out a good way for your game to keep network IDs (mostly) contiguous. These are all micro optimizations in the general sense but for some types of messages they can be rather macro-sized improvements.

*Short version*: **message priorities** and **tools, tools, tools.**
> 2 votes

# Answer
I would not recommend the second approach if your game is network intensive. As you pointed out, your game packets can experiment increasingly delay in this case.

I'm afraid that to be totally sure which one is the best approach you should profile your system. You already listed the relevant info needed to be profiled in your tests. They are:

1. How much lag is introduced when you postpone sending part of the packets. An elegant and robust way to quantify that is to make a stress test using threads simulating clients. The less elegant way is to write a fake flush function/object that have the intended behavior.
2. What is your peak of data transfer with acceptable lag. I think the same test of item 1 can report this quantity.
3. This is less important, but to eliminate all uncertains you could also quantify the percentage of game loop time that is being used by the disassemble/assemble of the messages.

You should always save in the back of your head the UNIVERSAL rules of optimization:

1. Should follow the rule "Don't do that unless you have to" or your system will suffer from premature optimisation.
2. Should not harm the system architecture. The API and maintainability is always first priority, since in the long run it pays itself by letting us sleep well...
3. Should be preceeded by profiling.

The same tips about optimizations are in this question. I would also suggest the book Effective Java, where these tips are extracted from. It is a must read for anyone which want to take the best from OOP.
> 1 votes

# Answer
For a game you're generally sending 10-30 packets per second, so at most you'll have 1/10th of a second of data in that buffer. If you're generating enough data to fill a 1500 byte packet in that time then you're almost certainly going to have bandwidth problems.

Many home internet connections have a very limited upload speed, so unless the game's limited to 2-4 players you'll run out of bandwidth on slower connections well before you hit the 1500 byte limit.

Because of that I wouldn't worry about it - if it's causing you problems you probably need to do some optimization on the data size before looking at the buffering scheme.
> 0 votes

# Answer
50 bytes packet? JSON? Take some steps back.

Sending JSON-encoded messages makes no sense, it's an egregious waste of resources.

1. figure out any thing that the client might be want to tell the server
2. create **extremely** small packets with bitwise fields

The first few bits should be the "command" (if you want to make it simpler, 1-byte commands are ok), followed by a few bits for the arguments.

For instance, your command for "move" is 0x4, and the following bits tell which movement buttons is the player clicking.

You also likely want to include a "sequence" number (1 or 2 bytes) to order packets, i.e. to discard older ones.

In total you should have packets ranging from 1 to 5 bytes tops. If they are any bigger, it's extremely likely you are doing something wrong.

Of course it might make sense to have an occasional big packet, but even that one should be carefully designed to be as small as possible.
> 0 votes

---
Tags: networking, multiplayer, udp, serialization
---


# Question
Title: How to save a character to be used in all Game States?
I am using C# and SFML.

I am having a problem understanding how to save a character in memory, so I can use the character in any game state.

Right now, the character is a class, and the player creates the character in the "Character Creation" GameState. However the actual variable is created in the GamePlayState class (see below).

```
class Character : IGameObject
{
    public Vector2f SpritePosition { get; set; }
    public Vector2f SpriteScale { get; set; }
    public string Name { get; set; }

```

However, I need all of the character data to be usable in any/all Game States.

I tried using a static game container (Dictionary, which held GameObjects- the player's character) but ran into some problems where I couldn't build. So I tried a different method to handle it.

I save all of my GameStates in a Dictionary which resides in the primary game loop.

```
stateSystem.AddState("Gameplay", new GameplayState(stateSystem));

```

I can call any specific GameState, but it acts as though the character (if created in Gameplay) cannot be access in other game states. The Game States can, however, access any other Game State.

For example, I tried to create the character in Gameplay - GameState

```
class GamePlayState : IGameObject
{

Character playerCharacter = new Character();

}

```

And in the class CharacterCreationState, I try to access that Character. It says "IGameObject does not contain a definition for playerCharacter".

```
Variable = stateSystem["Gameplay"].playerCharacter.variable;

```

I even created a function in my StateSYstem class which gets gameobjects.

```
        public IGameObject getGameObject(string stateID)
    {
        return _stateStore[stateID];
    }

```

This works to get the correct IGameObject, which would be the Gameplay State.

```
class GamePlayState : IGameObject
{

Character playerCharacter = new Character();

}

```

But once i have that IGameObject (the GamePlay Game State) I cannot grab the playerCharacter to manipulate it.

Perhaps I am just tired, but I am having a hard time figuring out how to do this without making the Character playerCharacter a global variable, creating in the main game loop.

# Answer
> 1 votes
Working from the framework you have now, can GamePlayState simply expose a public getPlayerCharacter() method? Then you can cast your IGameObject to a GamePlayState and call it. Something a bit like...

```
GamePlayState currentState = stateSystem.getGameObject("Gameplay") as GamePlayState;
if(currentState != null)
  PlayerCharacter playerCharacter = currentState.getPlayerCharacter();

```

If you want to change things up a bit, an approach I generally use is to have a singleton PlayerManager class, from which all game states (or anything else) can request any info they need about the player(s). Like:

```
PlayerCharacter player1Character = PlayerManager.GetInstance().GetLocalPlayer(1).GetActiveCharacter();

```

---
Tags: c#, character, gameobject, inheritance
---


title: Animation is too fast

text:
# Question
Title: Animation is too fast
I have an animation of a bullet but it seems to be going much faster than i was expecting.

I currently set it to `0.5 pixels per second` yet it seems to be moving way over hundreads of pixels per second.

Not quite sure where my logic is going wrong:

This is inside my gameLoop which im using to calculate it:

```
var deltaTime = (new Date().getTime() - started) / 1000; // divide to get seconds
var position = deltaTime * bulletVelocity; //bulletVelocity is 0.5

var vectorX = destinationX - startX;
var vectorY = destinationY - startY;
var distance = Math.sqrt(vectorX * vectorX + vectorY * vectorY);

var x = startX + (vectorX * position);
var y = startY + (vectorY * position);

if (x < destinationX && y < destinationY) {
    ctx2.drawImage(pulse, x, y); //draw the sprite on canvas
}

```

Have i got my logic wrong here i cannot work out why its moving so fast.

# Answer
You forgot to divide 'vectorX' and 'vectorY' by 'distance'.

If you do that, the code should work.
> 4 votes

---
Tags: mathematics, animation
---


# Question
Title: Poor mobile performance when running from Eclipse
So after weeks of thinking my rendering code was bad, I accidentally discovered the following:

**Running my game on a Nexus S**

* From Eclipse (Debug as -\> Android application): 12fps
* From the device while still attached to USB (getting log info in Eclipse still): 24fps
* From the device while not attached via USB: 56fps

I was wondering if anyone else has issues like this? I mean, the problem really isn't a problem since the final release build will likely have good performance, but for the time being I don't want to have to keep (un)plugging my device in and out when testing code all day long.

Is there some remedy for this or does anyone have any input/advice?

Thanks.

# Answer
> 1 votes
The debugger has to attach to the process, and it is what is causing your device to run more slowly than normal

It doesn't matter if you "debug" the app or not -- if it is set in the device, eclipse will debug

# Answer
> 0 votes
Debugging the app is expected to slow the device down.

The reason why you are slowing down even while not debugging is probably related to excessive logging.

---
Tags: java, android, performance, mobile, eclipse
---


# Question
Title: Predicting trajectory collisions for multiple moving objects
For the most simple of 2D games, I have implemented *a posteriori* collision detection (overlapping rectangles) on the xy Cartesian plane, but am now interested in understanding the basics of *a priori* collision detection...

On Wikipedia's entry on collision detection, I noticed the reference to Newton’s Method. So, I want to better understand the link between finding zeros of an equation and detecting *a posteriori* collision.

Let's start with the most obvious case of finding roots of an equation: If you have a projectile's trajectory modeled as a quadratic function, you can find the roots to predict at what time the height will equal zero (or any other constant height, actually, by just rearranging f(x)=C to be f(x)-C=0 and then finding roots of that expression).

So, as I understand, finding the root can tell me the time at which the object will be at any chosen height. More broadly, we basically know the (x,y) location of the object for any given time.

But how does root finding, in particular, translate to detecting collisions with another object? The other object may be stationary, or be moving. If the latter, do you also determine roots/location of this moving object as well? Calculate the (x,y) trajectory of both objects and determine where they will intersect?

# Answer
Very simply, if you define the minimum distance between two moving bounding volumes as a function of time, *D(t)*, then the roots *(a.k.a. zeros)* of that function are obviously the set of times, *{t1, t2, ... tn}*, when the distance between the volumes is exactly zero, *D(t1)=0, D(t2)=0, ... D(tn)=0*. If the volumes collide at some time in past or future, then one or more of those roots will be *real*. The smallest real root that is greater than or equal to the current time can usually be described as the time of the initial collision between the two volumes. If the volumes never collide in the past or future, then *D(t)* will have no real roots, because it is never equal to zero anywhere at any time, in which case it will only have imaginary roots. So, simply by examining the presence or lack of real roots in the distance function, you can determine if a collision occurs or not.

Polynomial functions up to degree 3 *(i.e. "cubic"; ax3+bx2+cx+d)* have well-defined roots that can be derived algebraically very easily. Polynomials of degree 4 *(a.k.a. quartic)* also have a relatively straight forward solution for their roots which was provided by Lodovico Ferrari, so it is sometimes called *Ferrari's Method*. For functions that are more complex than that, you can use Newton's method to systematically find roots between some *tmin* and *tmax*. Newton's method actually is somewhat ideal for collision detection, since we are usually only concerned with finding collisions between some known time interval. There's almost never any need to hunt down all of the roots for this application. Furthermore, the precision that we require for collision events often isn't very high. The precision of the root being computed can be tuned in Newton's method by simply increasing or decreasing the number of iterations spent in its loop.
> 0 votes

---
Tags: collision-detection, mathematics
---


# Question
Title: Why does the resolution of floating point numbers decrease further from an origin?
My OpenGL scene has objects that are positioned at ridiculously far distances away from the origin. When I view these objects, and pan/rotate/zoom a camera around them, they 'jitter'. That is, the vertices comprising the objects seem to snap around an imaginary 3d grid of points. I've read this is a common problem because of the amount of information that can be stored using floating point precision (which OpenGL, and pretty much everything else uses). I don't get *why* this happens though.

When searching for a solution, I came across the very simple 'floating origin' fix, and it seems to work. I just transform everything so my objects are in the same relative positions but whatever my camera's looking at is close to the origin. I found an explanation here: http://floatingorigin.com/, but I couldn't follow it.

So...Could someone explain why positioning my scene very far away (say 10 million units) from the origin results in the erratic behaviour I observed? And also why moving it close to the origin fixes the problem?

# Answer
This is ALL due to the way floating points are represented in computers.

Integers are stored pretty straightforward; each unit is exactly "one" apart from the "previous" just as you'd expect with countable numbers.

With floating point numbers this is not exactly the case. Instead, several bits indicate the EXPONENT, and the rest indicate what's known as the mantissa, or fractional part that is then MULTIPLIED by the exponent part (implicitly 2^exp) to give the final result.

Look here for a visual explanation of the bits.

It is precisely because of this exponent being an actual part of the bits that precision begins to WANE once numbers grow larger.

To see this in action, let's do a faux-floating point representation without getting into the nitty-gritty: take a small exponent like 2 and do some fractional parts to test:

2 * 2^2 = 8

3 * 2^2 = 12

4 * 2^2 = 16

...etc.

These numbers don't grow very far apart at only exponent 2. But now let's try exponent 38:

2 * 2^38 = 549755813888

3 * 2^38 = 824633720832

4 * 2^38 = 1099511627776

Whoa, huge difference now!

The example, while not specifically going to the VERY NEXT COUNTABLE (that would be the very next fractional part depending on how many bits it is), is there to demonstrate the precision loss once numbers grow larger. The "next countable" unit in floats is very small with small exponents and VERY large with larger exponents, whereas in integers it's ALWAYS 1.

The reason the float origin method works is because it's scaling all these potentially large-exponent floating point numbers DOWN TO small-exponent so that the "next countables" (precision) can be very small and happy.
> 26 votes

# Answer
Because floating point numbers are represented as fraction + exponent + sign, and you only have a fixed amount of bits for the fraction part.

http://en.wikipedia.org/wiki/Single\_precision

As you get larger and larger numbers, you simply do not have the bits to represent the smaller portions.
> 17 votes

# Answer
The classic in the field must be brought up: What every computer scientist should know about floating point numbers.

But the gist of it has to do with how single (double) precision floating point numbers are just a 32 bit (64-bit) binary number with 1 bit representing the sign, an 8-bit (11-bit) exponent of base 2, and a 23bit (52-bit) significand (the parentheses are the values for doubles).

That means the smallest positive number you can represent in single precision is 0.0000000000000000000001 x 2-127 = 2-22 x 2-127 = 2-149 ~ 1.40 x 10-45.

The next positive number is double that: 0.0000000000000000000010 x 2-127 = 2-148 ~ 2.80 x 10-45, and then the next number is the sum of the previous two 0.0000000000000000000011 x 2-127 = 3 x 2-149 ~ 4.2-45.

This continues increasing by the same constant difference until: 0.1111111111111111111111 x 2-127 = 2-126 \- 2149 ~ 1.17549435 x 10-38 \- 0.00000014 x 10-38 = 1.17549421 x 10-38

Now you have reached the normal numbers (where the first digit in the significand is 1) specifically: 1.0000000000000000000000 x 2-126 = 2-126 = 1.17549435 x 10-38 and the next number is then 1.0000000000000000000001 x 2-126 = 2-126(1+2-22) = 1.17549435 x 1.00000023.
> 8 votes

# Answer
The reason why floating-point numbers become less precise further from the origin is because a floating-point number is supposed to be able to represent large numbers. The way that this is done lends it the term "floating point". It splits up the possible values it can take (which is determined by its bit-length) so that there is about the same number for each exponent: For a 32-bit float, 23 of the bits define the mantissa or significand. So it will be able to take the value of 2^23 different values in each exponent range. One of these exponent ranges is 1-2 \[2^0 to 2^1\], so splitting the range 1 to 2 into 2^23 different values allows for a lot of precision.

But splitting the range \[2^10 to 2^11\] into 2^23 different values means the space between each value is a lot bigger. If it wasn't, then 23 bits wouldn't be enough. The whole thing is a compromise: You need an infinite number of bits to represent any real number. If your application works in a way that lets you get away with lower precision for larger values, and you benefit from being able to *actually represent large values*, you use a floating point representation.
> 2 votes

# Answer
It can be a bit difficult to offer specific examples of how floating-point precision works. To supplement the other answers, here’s one. Let’s say we have a *decimal* floating-point number, with three digits of mantissa and one digit of exponent:

> mantissa × 10exponent

When the exponent is 0, every integer in the range 0–999 can be represented precisely. When it’s 1, you’re essentially multiplying every element of that range by 10, so you get the range 0–9990; but now, only multiples of 10 can be represented accurately, because you still only have three digits of precision. When the exponent is at its maximum of 9, the difference between each pair of representable integers is *one billion*. You are literally trading precision for range.

It works the same way with binary floating-point numbers: whenever the exponent goes up by one, the range *doubles*, but the number of representable values within that range is *halved*. This applies to fractional numbers as well, which is of course the source of your problem.
> 1 votes

# Answer
In general, the resolution gets worse because the resolution is multiplied by the exponent value (2\**exponent part).

in acknowledgement of josh's comment: the above was just to put the answer into a succinct statement. Of course, as I have tried to indicate on http://floatingorigin.com/, this is just be beginning towards an overall solution and your program could have jitter from a number of places: in the precision pipeline or other parts of the code.
> 0 votes

# Answer
**OpenGL depth buffer is not linear**. The furhter you go, the worse resolution it has. I recommend to read this. Something taken from there (12.070):

> In summary, the perspective divide, by its nature, causes more Z precision close to the front of the view volume than near the back.

And another one (12.040):

> You may have configured your zNear and zFar clipping planes in a way that severely limits your depth buffer precision. Generally, this is caused by a zNear clipping plane value that's too close to 0.0. As the zNear clipping plane is set increasingly closer to 0.0, the effective precision of the depth buffer decreases dramatically. Moving the zFar clipping plane further away from the eye always has a negative impact on depth buffer precision, but it's not one as dramatic as moving the zNear clipping plane.

So you should move your near clipping plane the furthest you can and your far plane the closest you can.
> -1 votes

---
Tags: c++, opengl
---


title: Map color collision problem

text:
# Question
Title: Map color collision problem
Hello i'm doing a game in WPF, 2D version (top view)

I have the map and i'm trying to check for color collision in pixel each time the timer is activated

Well...with 1 object it works fine but with more objects at same time it just slow down the process

This is my code every time the dispatchertimer activates and i loop to check for collision on every object

```
CroppedBitmap cb = new CroppedBitmap(source, new Int32Rect(x, y, 1, 1));
int px = 1 * (source.Format.BitsPerPixel / 8);
byte[] pixels = new byte[px * 1];
cb.CopyPixels(pixels, px, 0);
Color c = Color.FromArgb(pixels[3], pixels[2], pixels[1], pixels[0]);
if (c.R == 255 && c.B == 255 && c.G == 255) {
   pixels = null;
   return true;
}

```

Any help to simplify the process? I really want to do it in WPF

PS: The map is 1018x731

# Answer
I think your main problem here is that you continuously allocate new memory. Instead of creating small buffers for each pixel you want to read, why not create a buffer from all the image pixels and the read directly from there?

Here's how I would modify your code. Disclaimer: I've never used WPF before, so take this with a grain of salt. I don't know how the pixel data is ordered in the array etc.

```
// -- Don't do this inside the loop, but somewhere else
// and keep a pointer to the pixels array
// read the entire image into a buffer
CroppedBitmap cb = new CroppedBitmap(source, new Int32Rect(0, 0, 1018, 731));
int px = 1018 * 731 * (source.Format.BitsPerPixel / 8);
byte[] pixels = new byte[px];
cb.CopyPixels(pixels, px, 0);

// -- do this inside your loop
// calculate the offset into the array
int offset = (y * 1018 + x) * 4;
Color c = Color.FromArgb(
    pixels[offset + 3], pixels[offset + 2], pixels[offset + 1], pixels[offset]);

if (c.R == 255 && c.B == 255 && c.G == 255) {
   pixels = null;
   return true;
}

```
> 0 votes

---
Tags: 2d, collision-detection, maps, wpf
---


title: Inconsistent sprite velocity?

text:
# Question
Title: Inconsistent sprite velocity?
I'm moving my sprites using the following formula:

**Code that I'm using (Only shows sprite's X position being calculated but Y position is also being done)**

```
spriteGridX = 240/480;  //I start out with a virtual 'Grid' so I can scale position to all resolutions etc so 240/480 would place the sprite at the center of the screen (X)

spriteScreenX = spriteGridX * width;  //Scale to physical screen where width is the width of the current devices screen (viewport)

spriteXTime = 8f; //8 being the amount of time in seconds that this sprite will take to traverse the entire width of the screen

spriteXVel = 1/spriteXTime; //Velocity that will be used to move the sprite along the virtual grid position

```

So, when I need to move the sprite, I simply do the following:

```
spriteXGrid+= (spriteXVel * Delta) //+= for right -=for left. I'm using a fixed delta time
spriteScreenX = spriteGridX * width; //And again, convert to usable screen position for current device
drawsprite(spriteScreenX, SpriteScreenY); //Draw the sprite (drawSprite is just a method I've written to draw openGL quads and it takes the screen X and Y as coordinates - spriteScreenY not shown here but essentially same as X with height instead of width.

```

**Problem**

The above seems to work OK (if I specify, as above, 8seconds, then the sprite does indeed take 8seconds to pass the whole screen as far as I can tell).

However, a problem becomes evident when I have 2 sprites (in my case, 2 horizontally moving platforms, both starting at the outer edges of the screen - one on the left and one of the right) - these move towards each other and when they 'meet', they go back in the opposite direction, and again when they reach their initial starting positions.

After the second time, they start to move slightly out of sync and the problem accumulates. Each platform has the same time/velocity settings and it seems that a sprite over the right side of the screen moves at a *very* slightly different speed than the one on the left.

After the initial move, the difference between the grid positions of my 2 sprites are a follows:

Left sprite = 0.002083334 Right sprite = 0.0020834

I can't work out why there is a difference. They're using the same formula.

Of course the problem could be that they are reversing at slightly different times and not the speed as I suspect, but for now I've ruled that out as they seem to be reversing correctly.

Be grateful if anyone could assist. Thanks

Test Device: Google Nexus 10, Samsung Galaxy Ace v1

# Answer
> 0 votes
I finally worked it out - it was a rather silly mistake on my behalf. When I was doing:

```
spriteScreenX = spriteGridX * width

```

I was actually casting the result from a float (spriteGridX) to an int (spriteScreenX), therefore was getting inconsistent sprite movement (in pixels) between the two sprites.

I should have been rounding up down to nearest int.

Once I rounded the results, everything seems to work perfectly.

# Answer
> 1 votes
This is probably due to floating point error. Every time you call

```
spriteXGrid += (spriteXVel * Delta)

```

you're performing an inexact arithmetic computation. The small error accumulates over time.

If your application only needs to move in X, you can get away with using an analytic solution, i.e.

```
curTime += Delta;
spriteXGrid = spriteVel * curTime;

```

If you want a more academic description of the problem, you can read What Every Computer Scientist Should Know about Floating Point Arithmetic

# Answer
> 0 votes
As specified in Mokosha's answer, this is most likely due to floating point error, and it is usually unavoidable. There are however a couple of things you can do:

The first, and most obvious, is to use `double` instead of `float` (if you aren't already). But even this will only slightly improve the situation, and over a long enough period of time, inaccuracies may still occur.

The second and more robust way is to "reset" your values in some way at specific times. For example, when your objects are at their closest positions together (just before or after they both reach the center) simply take the distance of one object from the center and set the second object to the same distance on the *opposite* side of the center - so if one is at `240.5` set the other to `239.5` (just as an example). If you have a small enough delta time, this will usually be imperceptible to the user. Alternately you can calculate the distance between the objects and offset each by half that value from the center - so if one is at `240.5` and the other is at `239.4` the distance between them is `1.1`, half of that is `0.55`, so you would set the values to `240 + 0.55 = 240.55` and `240 - 0.55 = 239.45` respectively. This should further decrease the player's perception to the "correction".

You can do this "reset" at some defined interval, or each time they reach their target location. Either way it should fix your problem ;)

---
Tags: android, sprites, movement, scale
---


title: java building game : snap to grid

text:
# Question
Title: java building game : snap to grid
I am making a game in where it's topdown and you can place blocks how can I have a snap to grid game so its like you place a block and it snaps to a grid so you cant place squares on top of eachother. Im not asking you to write my code (I don't mind if u do) I just want to know how to do this. my code so far that would be helpful to luck at and get an idea of what I mean:

```
public static ArrayList<hellstone> hpf = new ArrayList<hellstone>();

for (int i = 0; i < hpf.toArray().length; i++) {
    hpf.get(i).render(g);
}

public void mouseReleased(MouseEvent e) {
        if (e.getButton() == MouseEvent.BUTTON1) {
            Comp.ml = false;
            if (Comp.play && Comp.money >= 100) {

                if(inventory.sel == 0){
                Comp.hpf.add(new hellstone(Comp.mx / 2 - 10, Comp.my / 2 - 10));
                Comp.money -= 100;
                }else if(inventory.sel == 1){
                    Comp.b.add(new board(Comp.mx / 2 - 10, Comp.my / 2 - 10));
                    Comp.money -= 100;
                }

            }
        } else if (e.getButton() == MouseEvent.BUTTON3) {
            Comp.mr = false;
            if (Comp.play) {

            }

        }

    }

```

# Answer
> 0 votes
I figured it out. For each X and Y coordinate, I can do this:

```
x = (mousex / gridcellwidth) * gridcellwidth;
y = (mousey / gridcellheigt) * gridcellheigth;

```

---
Tags: java
---


title: Entity System handle graphics/textures

text:
# Question
Title: Entity System handle graphics/textures
I use in Java Artemis(entity system library) and Slick2D(graphics library) for a game.
Now I wonder me, how I should handle graphics(sprites, textures...).
In the demos of the page from Artemis it was made so:

SourceCode

I hope the diagram is good enough. So someone asks now "Whats the problem ?": The Problem is, that this method is not very efficient and it feels not very good, because:

* The spatial forms are created and initialized at run time
* The spatial forms are created individually for every entity(Load textures or create a shape...)

I think there a better ways, so I hope someone have a better idea.
And if someone have the idea to make simply a sprite or a texture component, that's not a solution, because some entities have for example more textures than one.

And a supplementary question, how I should handle animated graphics ?

Thanks for reading :) and sorry for my bad English :(

# Answer
I would add a cache system for all resources. In my game project (in C++, but very similar system) I would call `ResourceCache::instance()->Get("test.obj");` and then it would automatically load the resource if not cached, or instance the resource if it is. The added benefit to this is that it is dead simple to reload resources when they are lost.
> 0 votes

---
Tags: java, entity-system, entity, artemis
---


# Question
Title: How do I make my iOS game free for users who 'like' it on Facebook?
I've seen a game for free on iOS when the user 'likes' a page. Though it appears the promotion was run by Apple, not the developers of the game being given away.

How can I make my game free for a Facebook 'like'?

# Answer
This was done via a special deal with Apple, and cannot be done in general.

One way you might handle the situation is to make the game free on the store, but have most of the gameplay behind an in-app purchase paywall (such that your app essentially serves as a free demo that allows you to buy the upgrade to the full game). Then, you'd correlate all the FB likes with the Apple IDs of the corresponding FB users and issue the tokens for the upgrade IAP to those Apple IDs.

Unfortunately, there is no mechanism to do that Facebook-to-Apple-ID join, so you'd need to do it manually or build your own webservice that users used which would collect their information, do the "like" on their behalf, and then store the correlated IDs in a database you could process.

But even then, there isn't a way for you to issue tokens for IAPs (or apps themselves) arbitrarily. You can request promotional codes from Apple which could you then distribute to FB likers, but the number of promotional codes you can acquire is pretty limited, and unless you expect your total userbase to be *well under* that limit (less what you'd want to use for actual promotional purposes), doing this would probably be a terrible idea.
> 3 votes

---
Tags: ios, facebook, appstore
---


# Question
Title: Java Game : How to place one tile over another tile
Hi I am making a java game in were you can build land. at the moment when you place tile A on top of TileB it renders over it but when you place TileB on top of TileA it doesn't render it stays as tileA. so how could I have it so that it either one renders on top of each other. I think I might need to remove a tile from the array and then that space is free. But I don't know how to remove the tile that the mouse is hovering over from the array maybe that would help. my code.

```
public static ArrayList<hellstone> hpf = new ArrayList<hellstone>();
public static ArrayList<lava> lava = new ArrayList<lava>();

public void render() {
    Graphics g = screen.getGraphics();

    // drawing things.

    if (time < timer / 2) {
        ImageIcon i2 = new ImageIcon("res/lava.png");
        img = i2.getImage();
        g.drawImage(img, 0, 0, null);

    }
    if (time > timer / 2) {
        ImageIcon i2 = new ImageIcon("res/lava1.png");
        img = i2.getImage();
        g.drawImage(img, 0, 0, null);

    }
    for (int i = 0; i < castles.toArray().length; i++) {
        castles.get(i).render(g);
    }
    /*
     * g.setColor(Color.blue); g.fillRect(10,10,40,20);
     * g.setColor(Color.black); g.drawString("ADD", 16, 24);
     * g.setColor(Color.black); g.drawRect(9, 9, 41, 21);
     */

    if (play) {
        // bg----------

        ImageIcon i3 = new ImageIcon("res/hellbackgorund.png");
        img = i3.getImage();
        g.drawImage(img, 0, 0, null);

        // ImageIcon i2 = new ImageIcon("res/hellsun.png");
        // img = i2.getImage();
        // g.drawImage(img, 120, 80, null);
        for (int i = 0; i < lava.toArray().length; i++) {
            lava.get(i).render(g);
        }

        for (int i = 0; i < hous.toArray().length; i++) {
            hous.get(i).render(g);
        }

        for (int i = 0; i < hpf.toArray().length; i++) {
            hpf.get(i).render(g);
        }
        for (int i = 0; i < b.toArray().length; i++) {
            b.get(i).render(g);
        }

        for (int i = 0; i < orc.toArray().length; i++) {
            orc.get(i).render(g);
        }
        g.setColor(Color.YELLOW);
        g.drawString("" + money, 20, 10);
        ImageIcon i5 = new ImageIcon("res/coin.png");
        img = i5.getImage();
        g.drawImage(img, 2, 2, null);

        g.setColor(new Color(0,255,0,70));
        g.fillRect(((Comp.mx/2) /20) * 20 ,((Comp.my/2) / 20) * 20 , 20, 20);

        inventory.render(g);

    }
    for (int i = 0; i < gamemenu.toArray().length; i++) {
        gamemenu.get(i).render(g);
    }
    level.render(g);

    g = getGraphics();

    g.drawImage(screen, 0, 0, size.width, size.height, 0, 0, pixel.width,
            pixel.height, null);
    g.dispose();
}

```

**\*******the mosue listenr******\*****\****

```
public void mouseReleased(MouseEvent e) {
    if (e.getButton() == MouseEvent.BUTTON1) {
        Comp.ml = false;
        if (Comp.play && Comp.money >= 100) {

            if(inventory.sel == 0){
                //(mouse.x / gridCellWidh)*gridCellWidth
            Comp.hpf.add(new hellstone(((Comp.mx/2) /20) * 20 ,((Comp.my/2) / 20) * 20 ));
            Comp.money -= 100;
            }else if(inventory.sel == 1){
                Comp.b.add(new board(((Comp.mx/2) /20) * 20 ,((Comp.my/2) / 20) * 20 ));
                Comp.money -= 100;
            }else if(inventory.sel == 2){
                Comp.hous.add(new house(((Comp.mx/2) /20) * 20 ,((Comp.my/2) / 20) * 20 ));
                Comp.money -= 400;
            }

        }
    } else if (e.getButton() == MouseEvent.BUTTON3) {
        Comp.mr = false;
        if (Comp.play && Comp.Orcs < 99) {

            Comp.orc.add(new orc(new Random().nextInt(100),new Random().nextInt(100),Color.green));
        }

    }

}

```

---

please help me figure this out.

# Answer
The problem here is your drawing order. No matter what order your tiles are enabled, each one is drawn in a specific order. No matter what order blocks are added, Lava is always drawn first, which means that any other block in the same place will cover it up because it is drawn later in the loop. The way you have your drawing system will not allow lava to cover up anything for example. You need to rethink your approach to drawing the tiles, either add a flag to indicate which was last placed, or use 2D lists/arrays.
> 2 votes

---
Tags: java
---


title: Using Geometric Slerp to move Camera

text:
# Question
Title: Using Geometric Slerp to move Camera
I'm writing a program in `C++` using `OpenGL` and `GLM`; I'm trying to get my camera to follow my car. So far it successfully follows it around the screen, but I'm having trouble adjusting the Camera's origin (position) to make it stay directly behind the car when it turns. (when the car turns, I want the camera to turn as well to stay inline with it).

After doing a little googling and S/Oing, I think the way forward is by using Geometric Slerp, who's equation is seen here.

It involves the following equation and relates to this diagram:

Below is what I'm trying to achieve; in a program, I have a camera following a car and when the car turns, the cameras position needs to update to stay behind it. Below are two doodles to help you understand my description above. The first image shows the car and camera; the second shows the details:

I have tried writing a function for the equation as seen below:

`vec2 slerp = (((sin((1-t)*Omega))/(sin(Omega)))*p0)+(((sin(t*Omega))/(sin(Omega)))*p1)`

But I'm unsure how to calculate P1... I'm assuming P0 is the current position and Omega is the rotation of the car. (so by turning left, the camera rotates from P0 to P1.

This is how my car position is updated and how I've got my camera following my object:

```
camOrigin.x  = (0   +globalPos.x+velocity.x); //Cam Position
camOrigin.y  = (0   +globalPos.y+velocity.y); //Assuming I need to *slerp to X and Z??
camOrigin.z  = (100 +globalPos.z+velocity.z); //stays 100 behind car on Z plane
camLookingAt.x = (0 +globalPos.x+velocity.x); //Cam Looking at Object
camLookingAt.y = (0 +globalPos.y+velocity.y);
camLookingAt.z = (0 +globalPos.z+velocity.z);
camNormalXYZ.x = (0);                         //Cam Normal = Y
camNormalXYZ.y = (1);
camNormalXYZ.z = (0);

```

Or maybe I'm looking at this wrong and there's an easier way to do this?

# Answer
Based on your sketch, you can simply rotate `P0` by Omega to become `P1`. The problem is finding the rotation axis which is trivial in your case: the up vector of your camera. Keep in mind that rotation happens around the origin(0,0,0) by default so might need to translate, rotate and translate back depending on the space you're working in.

So what you have to do is:

1. Calculate `P1` by rotating `P0` around the camera up axis by Omega.
2. Now you have `P1` you can interpolate between the two values.

I also want to stress the fact that interpolation is usually used for animation. In other words generating intermediate values. So you first calculate start and end points then generate the intermediate values.

The second option, is to use vector math, which might be more generic and a little bit more more complex. It's might also be slower (performance wise) which is not worth the trouble.
> 1 votes

# Answer
you actually just want to rotate your p0 by `rotation_speed*deltaTime`

or in rotation notation:

```
P' = P0*Axis_angle(axis,rotation_speed*deltaTime);

```
> 0 votes

---
Tags: opengl, c++, physics, camera, geometry
---


title: Unity/VS debugging only with UnityVS?

text:
# Question
Title: Unity/VS debugging only with UnityVS?
**Hi,**

this one thing isn't clear to me: Is it possible, to debug C# of Unity 4.3 with Visual Studio 2013 without any plugin?

If no, what or how else should I debug then?

# Answer
You can only use Visual Studio to debug unity projects if you have unity VS.

From someone who has it, unless you are part of a team and all running unity pro you could probably do fine with unity and it's built in install of monodevelop.

Mono develop still lets you debug your projects just not using visual studio.

The unity VS plugin attaches you to your game code which you can't normally do because it runs within the unity process itself (by design i believe).
> 1 votes

---
Tags: unity, debugging, visual-studio
---


# Question
Title: How should I generate the board for a match-3-style game?
I am trying to create a "match 3" game. I'm stuck figuring out a good algorithm to fill up the game board.

My game's board is 8x8.

**EDIT:**

A few things:

The board should always be solvable. for example, the user has a score to reach by making matches. All boards must be able to produce enough available matches for the user to win each level or solve it.

# Answer
One of the easiest ways is to generate the board solved. Generate a board that is all matched pairs, then run it through an algorithm that shuffles it about until some criteria is met (Like no matching triplets left on the board.)

There will always be a solution for a board made this way that can be solved to completion if you control the number/intensity of the shuffling.

Edit: I wrote this thinking it was a match two for some reason. With a match three it is a bit more difficult, and it depends on the way the pieces move after being removed, and if any new pieces are added. With a match 3 it may be more realistic to start with three blocks matched, then add three more matched that possibly break up the first three, and loop and repeat until you have a full board.

Basically play the game in reverse as a function and it should generate solvable boards.
> 4 votes

---
Tags: java, android, algorithm, andengine
---


# Question
Title: Randomly generating the hallways between a network of rooms
So here's my base map:

(It won't necessarily be 5x5, just using this as an example.)

It's kinda boring the way it is with all the rooms connected. I want it to be more of a randomly generated labyrinth, where every room is accessible like so:

I've tried setting the hallways randomly:

```
foreach(Room r)
{
    r.northWall = randomBoolean();
    r.southWall = randomBoolean();
    r.eastWall = randomBoolean();
    r.westWall = randomBoolean();
}

```

But that almost always ends up with rooms that you're unable to go to, like this:

And often some rooms have no hallways at all. I tried saying each room must have a minimum of 2 hallways, but it still doesn't fix the problem that sometimes there an inaccessible areas.

How should I go about doing this? I'm not too worried about the speed, as long as it's not ridiculously slow (Some levels will have 100+ rooms).

# Answer
> 6 votes
One option you could try is using a maze generation algorithm: http://en.wikipedia.org/wiki/Maze\_generation\_algorithm

Personally I like using a recursive backtracker method.

```
Start: all doorways closed and all nodes unvisited, pick one node to start with
step 1: visit current node and look at nearby unvisited nodes and randomly move to one of them (open the door) and repeat step 1
step 2: if no nearby nodes are unvisited, go back to the previous node and repeat step 1
step 3: if you return to the start node, your maze is complete

```

# Answer
> 2 votes
Spelunky's algorithm is descibed here:

http://tinysubversions.com/spelunkyGen/

The basic approach is to ensure connectivity between rooms in a path until a suitable distance is hit. Every other room can be totally random, or an algorithm can be applied to ensure there's a path from every room to the "main path" from start to end.

To generate the main path, and algorithm similar to Spelunky's makes a lot of sense. Limit the options of which paths you are allowed to generate to ensure a legal path.

Once you have a full main path, you can then fill in the side rooms and ensure connectivity. If you assign the main path rooms a unique "group" ID of 1, you can then assign each new room you create its own group ID (+1 to last group ID) if it has no hallways to existing rooms. If the new room does have a hallway to an existing room, use the ID of that existing room. If at the end of the process you have any rooms with IDs other than 1, they form a cluster of inaccessible rooms. You can then randomly pick any room in that cluster that borders another cluster and connect them, then assign all the rooms of one group with the other's (always picking the lower/older ID of the two). Repeat until every room has an ID of 1. This ensures that all rooms are connected while keeping the assurance that the main path is still connected, creating dead-ends. If you want to allow loops or such then you can increase the number of hallways you create when isolated groups are detected.

This is just one way to do it. There are many, many more.

# Answer
> 0 votes
This problem reduces to finding a spanning subgraph of your room grid, so any spanning subgraph algorithm will work. This is a well-solved problem, and there are many super-fast algorithms to choose from.

In particular, you could find a spanning tree (using any of these algorithms, for example), and then add a few extra connections if you want loops as in your example above.

---
Tags: algorithm, procedural-generation
---


title: Rendering order

text:
# Question
Title: Rendering order
In this thread Rendering a model with transparent or translucent uv map applied doesn't work , I asked about what was wrong with my model that the transparency wasn't working. I've got an answer that it was the sorting order that was wrong. I need to use back-to-front when, I assume, I was using front-to-back. Could somebody elaborate on that? I don't really understand what is the sorting order and how can I change it.

# Answer
> 3 votes
Transparency with OpenGL is typically achieved using alpha blending, as you are attempting to do with `glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA)`. In order for you to get the desired effect, though, it helps to understand what the blending function *means.*

Let's consider the following scenario: you first draw a triangle, and then you want to draw a semi-transparent square on top of it. So first you draw a blue triangle, with the RGBA colours (0.0, 0.0, 1.0, 1.0). The alpha channel of 1.0 means it's completely opaque. Then you draw the green square on top, (0.0, 1.0, 0.0, 0.4). The resulting colour of where they overlap will be:

`(0.0, 1.0, 0.0) * 0.4 + (0.0, 0.0, 1.0) * (1.0 - 0.4)`

In other words:

`square_colour * square_alpha + triangle_colour * (1.0 - square_alpha)`

It's a very simple blending function. How it's actually achieved: when drawing a fragment (in this case a fragment of the square), the already existing fragment at that location gets sampled (which turns out to be green, since we drew a green triangle there). Then, using the old colour value at that location, and the colour of the fragment to be drawn, it blends the two for the resulting fragment. If you draw another semi-transparent object on top of that, it will sample the new colour, and again perform blending.

Now what if you were to change the order you drew the triangle and the square? Well, you'd draw the square, which is partially transparent, then you'd draw the opaque triangle, and... you guessed it, the result would be an opaque triangle, unblended.

So when you are rendering a 3D model with transparency, the order you draw them in matters! Not to mention, the problem gets worse with depth testing:

Let's say the square is closer to the camera than the triangle. If you draw the square, then the triangle, the square should still be on top. Except... the triangle won't get drawn at all? The reason is simple: with depth testing, before drawing the fragment, that location gets sampled once again, this time for depth. If the old fragment is closer to the camera than the new fragment, the new fragment gets discarded! So in the case of the square and the triangle, the triangle gets discarded, despite the square being "transparent".

Without depth testing, if you draw the square first, then the triangle, you get what you'd expect, the opaque triangle on top (not what you want).

Solution? Render the stuff furthest away from the camera first, then get closer (i.e. draw it back-to-front).

If you only have one layer of transparency, then what you want to do is: first draw everything that is opaque, then everything that is transparent. If you have multiple layers of transparency, then things get more complicated. Google **depth sorting**, and you'll find various different methods for achieving the desired effect.

# Answer
> 3 votes
The most robust method to ensure there are no transparency artifacts is to:

1. Disable writes to the depth buffer (although you may want to have a separate depth buffer for effects, I'll explain later)
2. Decompose your object into convex pieces (unnecessary in this specific case, a box is already convex)
3. Sort the parts of all objects from farthest away to closest
4. For each part in order, draw the backfaces and then the frontfaces (or just the frontfaces)

Depending on what you want, drawing both backfaces and frontfaces might be overkill, but it is useful for effects like opacity depending on thickness, refraction, and subsurface scattering.

You can safely draw all the fully opaque objects in one pass, because the depth buffer will take care of any overlap. To sort the convex parts, you can use the GJK distance algorithm to calculate the distance from the part to the near camera plane. This is embarrassingly parallel, so you can easily exploit multiple threads to do it quickly.

# Answer
> 1 votes
When attempting to do transparency, you need to be very meticulous in assuring you are drawing the rearmost elements first and you should also make sure that the polygons behind your cube (including parts of the cube itself) are not being culled. Using Opengl's built in depth test culling will not bend them properly if you draw them out of order. Here is the OpenGL spec on Transparency. http://www.opengl.org/archives/resources/faq/technical/transparency.htm

---
Tags: opengl, transparency, draw-order
---


title: Optimising meshes

text:
# Question
Title: Optimising meshes
The game MegaGlest uses a MD3-like mesh format, which is keyframe-based vertex animation.

One of the challenges moving forward is to continue to support lower-end hardware. We know some users have trouble with high-poly models, and the current MegaGlest assets are thoughtfully spartan because of this. Not all players have hardware that supports shaders, even.

However, we aim to provide a much richer experience to people with today's high-end hardware. We also aim to add support for a bone-based format, probably IQM/IQE. We want much higher quality meshes, but we want to continue to support low-end hardware.

The plan that is hatching in my mind is to distribute high-end meshes and have the low-end targets auto-simplify them in order to meet some sliding scale of budget.

How do you simplify meshes? I can find lots of research-like papers, but nothing really mainstream nor concrete. And to my mind, some consideration of triangles per unit cube (in game space) is needed, and not just arbitrarily saying 'make this mesh have only n triangles', where the triangles may be unevenly distributed around the model.

# Answer
> 2 votes
There are several decimation algorithms you can implement, here is the original paper on decimation. But as you said non of them are mainstream, or even easy to implement.

I would say your best bet is to check OpenMesh's decimation framework, they have a policy based C++ implementation of decimation algorithms, so you can try different policies based on the criteria you need. I have on-hand experience with it and I would say they got impressive results maintaining the general shape and the attributes of the vertices. The only drawback I can think of is that they use half-edge data structure, so unless it's a pre-process it might not be practical to use in your game.

They also have an editor where you can try it without even bothering with code.

---
Tags: 3d-meshes, optimization
---


# Question
Title: How do I scale a motion capture animation?
I used motion capture in my room using the Kinect. As I don't have much space I make compressed running moves, i.e. I put my legs up and down while not moving far forward.

How can I stretch the animation, so me walking 1 meters amounts to the skeleton walking 3 meters or similar while not exaggerating movements to the left/right?

# Answer
Run along a main axis (x, y, or z) and scale the animation along that axis.

If you don’t have a lot of space, you’re not going to produce a natural running gait. At best you’ll be able to use this as a basis for manual alterations, or a reference for a hand-done animation. One thing to try might be to undersell your movements along the axis of movement, so that they appear less distorted when scaled.

Alternatively, head to the gym with a laptop and set up your Kinect next to a treadmill.
> 1 votes

---
Tags: animation, skeletal-animation, motion-capture
---


# Question
Title: AABB collision detection not detecting in some cases
I'm using simple AABBs in a tile based world, and for some reason the algorithm does not detect collisions when moving towards the left and then down. I actually upload a video to YouTube to demonstrate the problem because I can't figure out a good way to explain my problem. Here it is: AABB collision detection problem

As you can see, the little wireframe tile that moves around is the player, and when I move to the left, and then try to move down on the tiles, the player just slips right through. Detection works when moving to the right. Here's my algorithm to detect collisions:

```
public static boolean isColliding(AABB a, AABB b) {
    if (Math.abs(a.pos.getX() - b.pos.getX()) < a.size + b.size) {
        if (Math.abs(a.pos.getY() - b.pos.getY()) < a.size + b.size) {
            return true;
        }
    }
    return false;
}

```

The pos variable in the AABB class is the center of the AABB in question, and the size is half the size. Here's how I move the player:

```
if (Keyboard.isKeyDown(Keyboard.KEY_SPACE)) {
        move(0, 1, 0, MOVESPEED);
    }
    if (Keyboard.isKeyDown(Keyboard.KEY_D)) {
        move(1, 0, MOVESPEED, 0);
    }
    if (Keyboard.isKeyDown(Keyboard.KEY_A)) {
        move(-1, 0, -MOVESPEED, 0);
    }
    if (Keyboard.isKeyDown(Keyboard.KEY_LSHIFT)) {
        move(0, -1, 0, -MOVESPEED);
    }
    if (Keyboard.isKeyDown(Keyboard.KEY_SPACE) && onGround) {
        onGround = false;
    }

```

Which references this method:

```
private void move(float x, float y, float sx, float sy) {
    if (getX() / 32 + x >= 0 && getX() / 32 + x <= world.mx && getY() / 32 + y >= 0 && getY() / 32 + y <= world.my) {
        if (world.tiles[(int) ((int) getX() / 32 + x)][(int) ((int) getY() / 32 + y)] != null) {

            Tile t = world.tiles[(int) ((int) getX() / 32 + x)][(int) ((int) getY() / 32 + y)];
            Vector2f tempPos = new Vector2f((pos.getX() + (pos.getX() + 32)) / 2, (pos.getY() + (pos.getY() + 32)) / 2);
            box.update(new Vector2f(tempPos.getX() + sx, tempPos.getY() + sy), 16);
            t.color = true;

            if (!Collision.isColliding(box, t.getBox())) {
                setPos(getX() + sx, getY() + sy);
            }
        } else {
            setPos(getX() + sx, getY() + sy);
        }
    } else {
        setPos(getX() + sx, getY() + sy);
    }
    glPushMatrix();
    glTranslatef(getX(), getY(), 0);
    glPopMatrix();
}

```

32 is the tile size and the player size, just for reference. The 'tempPos' vector is just a vector that holds the center of the player's position. AABB is a class that stores a vector and a size variable, and the update method just updates those variables.

I guess my question is either, why is it only working on one axis, or how can I change my move method to be "better"? I've been trying to figure out why this isn't working, and I just can't come up with any ideas because it happens constantly, so it's not that my entities are moving too fast and the algorithm isn't detecting the collisions.

# Answer
Let's say you are at the position (336, 330), and you are moving the block downwards. According to this line in your code:

```
if (world.tiles[(int) ((int) getX() / 32 + x)][(int) ((int) getY() / 32 + y)] != null) {

```

You're going to be checking the point tile (10, 9), which is fine. *But your tile is positioned half way between two tiles.* That means you should also be checking the tile (11, 9) for a collision. Casting to an `(int)` **rounds down.** But you should also have a conditional where you are **rounding up.**
> 1 votes

---
Tags: java, collision-detection, aabb
---


title: Separate game clocks/intervals in XNA

text:
# Question
Title: Separate game clocks/intervals in XNA
I am making a real time strategy game in XNA. I have separated the Client (rendering, input, sound) code from the Sim (game logic).

I want to have features like replaying and fast forwarding. Also, I would like to give the Sim longer time intervals in its Update to finish its work without having to always implement time slicing to prevent frame rate stuttering. I imagine I can do this when the two systems become decoupled and have their own update frequency.

So, how can I run the Client and Sim at two different update intervals? How should I code it?

Currently I am running with FixedTimeStep = false and using ElapsedGameTime in Update() computations. Can I create new GameTime instances to leverage this existing code..?

# Answer
> 1 votes
you dont need to use another gameTime object, since its just a clock. you just have to build yourself different timer.

there might be easier/better way to do it, but since I dont know them, here how i'd try 1st.

What you want to update base on a different elapse time. just use different variable for when you want your update. lets set update speed for replay to 1/10 of normal (normal = 60 times per second, so once about each 16.66 elapseGameTime, lets say 15 to be safe. you want 10x that, roughly so about once each 150 ms )

```
bool replayMode = True;
int UpdateSpeed = 170;
double elapseTimer ;

public override void Update(gameTime GameTime)
{
   elapseTimer += GameTime
   if (replayMode)
     UpdateSpeed = 150;
   else
     UpdateSpeed = 15;
   if (elapseTimer > UpdateSpeed ){
        elapseTimer = 0 ;
        foreach (Manager manager in MyManagerList) {
            manager.UPDATE();
         }
   }
}

```

Since elapseGameTime will reset to 0 after each update, you can set updateSpeed base on different value you want. Might not be perfect, but it should help you get started.

---
Tags: xna, game-loop, timestep
---