title: GLSL code is very slow...why?

text:
# Question
Title: GLSL code is very slow...why?
I know this is a very difficult thing to simply modify without the full project code, but I am having a massive performance problem with GLSL code that seems to be very efficient to me. I am stuck at 14 fps if I use mipmaps and only 23 if I am simply using the normal glTexImage2D() method, yet have it setup to render 30 times per second. The problem is in the fragment shader - the vertex shader is ridiculously fast, as it is just passing the parameters in to the fragment shader.

```
varying vec4 color;
varying vec3 normal;
varying vec4 position;

uniform sampler2D t_diffuse;
uniform sampler2D t_bump;
uniform sampler2D t_specular;
uniform mat4 light_color;
uniform vec4 light_position;

void main() {
    vec4 diff = texture2D(t_diffuse, gl_TexCoord[0].st);
    vec3 bump = normalize(texture2D(t_bump, gl_TexCoord[0].st).xyz * 2.0 - 1.0);
    vec4 spec = texture2D(t_specular, gl_TexCoord[0].st);

    vec4 ambient = vec4(light_color[0][0], light_color[0][1], light_color[0][2], light_color[0][3]);
    vec4 diffuse = vec4(light_color[1][0], light_color[1][1], light_color[1][2], light_color[1][3]) * diff;
    vec4 specular = vec4(light_color[2][0], light_color[2][1], light_color[2][2], light_color[2][3]) * spec;

    vec3 vector = light_position.xyz - position.xyz;
    float distance = sqrt((vector.x * vector.x) + (vector.y * vector.y) + (vector.z * vector.z));

    vec4 final = ambient + diffuse + specular;
    final.xyz *= max(0.0, dot(normalize(vector), bump)) / distance;

    gl_FragColor = final;
}

```

The light\_color variable holds one color in each row, so light\_color\[0\] is red, light\_color\[1\] is green, et cetera.

The textures aren't even vary large - and even then, I can do Starcraft 2 at max settings (30-40 fps), so it isn't like they are much of an issue. What is in here that can possibly be so slow?

# Answer
If you can do StarCraft at 30-40 fps then GLSL is most likely not your bottleneck. Reading your description, I get the feeling that you might be calling glTexImage2D for every frame, which could explain your low frame rate. I'm very confident your problem lies in your client rather then the shader.
> 3 votes

---
Tags: opengl, glsl
---


# Question
Title: Which type of Xbox console should I get to begin developing games on it?
If I want to start developing small indie-like games with XNA on Xbox (I don't think any game I'd make would need more than 100, maybe 200 megabytes), will the 4gb Slim (I want to get a slim version because of the wi-fi) version of the console be enough, or should I get the 250 gb version? I don't really plan to play actively on the console as I'm more interested in developing on it. Also, will a console and a verified student XBLIG account be enough to set up everything I need to run and debug my game on the console? Thank you.

# Answer
The answer is no.

You'll need an actual hard-drive to use the XNA connect application (upload your game) - but not to play other games.

You'll need a physical hard-drive - NOT flash memory to deploy games.

If you have a AppHub Membership (from DreamSpark, you say yours is from); this is all you need. You will link it with your Gamertag and download the Connect App and and you'll be all set from there.
> 4 votes

---
Tags: xna, xbox
---


# Question
Title: Why do most game devs prefer OGL for OS X and D3D for Windows?
Today I decided to check what Diablo 3 developers used to do graphics: OpenGL or Direct3D? My mind was completely blown: For Windows, they've used D3D and for OS X they've used OGL.

I did some research and found that most game developers prefer the same method. This choice doesn't make sense to me. Writing one game engine with OpenGL for OS X and then rewriting same for Windows with D3D seems a lot of unnecessary work. Wouldn't it be easier to just take OpenGL and make a game engine that works on both operating systems?

# Answer
> 12 votes
As others have mentioned, on OS X (and Linux), OpenGL is the only game in town for hardware-accelerated graphics. So the question really comes down to: why do developers use Direct3D instead of OpenGL *on Windows*?

One possible reason, as suggested in the comments, is that they started out as a Windows-only project and later decided to add OS X / Linux support, but didn't want to throw out their already-working Windows code. But another possible reason is that the developers may simply consider Direct3D to be *superior* to OpenGL, enough that they would rather write their rendering code twice than use OpenGL on Windows.

Part of this is clearly a "holy war" kind of issue - Direct3D and OpenGL use very different styles of interface, have different design values, and appeal to different coders' tastes. Like Mac vs PC, or Emacs vs vim, or tabs vs spaces, one can endlessly debate these things without ever convincing anyone.

Putting all that aside, though, I think it's fair to say that during the last several years, Direct3D has been *objectively* superior to OpenGL for Windows graphics programming, for the following reasons:

* For a good while, OpenGL seriously lagged behind in features. Direct3D 10 and 11 added support for new GPU features like geometry shaders, tessellation and compute shaders that it took OpenGL *years* to catch up to. There's a good Tom's Hardware article from a few years ago that gives you a taste of how disappointed people were about the lack of OpenGL feature development during that time.
* Direct3D has historically had much better tools: the debug runtime / debug layer, which generates warning messages about incorrect or questionable API calls you make; and PIX, the graphics profiler/debugger. For a long time, OpenGL had nothing comparable.
* The major GPU vendors have usually made Direct3D driver support a higher priority than OpenGL driver support. As a result, bug fixes and performance improvements often come sooner to the Direct3D drivers than the OpenGL ones.
* Console compatibility: from what I understand (not having worked with it myself), the XBox 360 graphics API is very similar, if not identical, to Direct3D 9. To whatever extent this is true, it likely means an easier time of porting games between PC and 360. It also means that if you're shipping your game on the 360, you have to write a Direct3D renderer anyway - so you might as well use it on Windows too.

By the way, our own Nicol Bolas also wrote an answer to a related question at programmers.se that goes into a lot more detail about the history of the OpenGL/Direct3D rivalry.

All that being said, there are signs that the tide is starting to turn. OpenGL developers have been working very hard to rectify the features and tools issues. OpenGL has now reached feature parity with Direct3D 11 and even gone a bit beyond. Timothy Lottes of NVIDIA wrote a blog post outlining his reasons for switching to OpenGL, with a lot of links about the new extensions and tools. Valve Software recently reported that they got an OpenGL version of Left 4 Dead 2 working and it was (slightly) faster than the Direct3D version, indicating that the driver support is there. So, it's possible we will see a swing back toward multi-platform developers using OpenGL on Windows. Or we may not.

# Answer
> 3 votes
DirectX is written for OS Windows with own optimizations to platform, etc. There aren't any realizations of it for another platforms. OpenGL is an open alternative which started grow when mobile and tables become more powerful to render some hard scenes.

Anyway, I'd give you and advise to write everything using OpenGL, but it's only my opinion. It's free, crossplatform, powerful and fast.

# Answer
> 1 votes
It is likely that the actual reason for it is just politics. Many experienced game developers use DirectX since ages. Thus DirectX is used. (And than OpenGL was later added by the developers that made the Mac port.)

One thing however is that people that use OSX are sure to have GPU's that have properly working OpenGL implementation. This can't be said for sure for Windows PC's, due to the long time where games on Windows were primarily DirectX. This is bound to get better in the future though, with the rise of Steam for Linux and thus cross platform game development. If you want to write OpenGL code for Windows without having to worry about the OpenGL implementation of the GPU you could try ANGLE.

# Answer
> 1 votes
Simply because Direct3D runs way better on Windows then OpenGL in most cases. GLSL doesn't event run on most Netbooks and OpenGL driver support is very flaky on Windows. Like vSync with OpenGL on Windows doesn't work without installing the drivers yourself manually.

For games, you rly want to use Direct3D on Windows... Other platforms only support GL in most cases. Also Windows RT and WP8 only support Direct3D.

---
Tags: opengl, directx, windows, macos
---


# Question
Title: Increase restitution (bounciness) of an object in a JavaScript formula
I'm going slightly around the houses on this one. I originally started a thread over on Stack Overflow about it but then it seemed to diverge into mathematics, with no joy from the SO community over there (https://math.stackexchange.com/questions/295485/modify-formula-for-bouncing-object-to-increase-restitution). So my final attempt before I admit complete failure is to ask here. I don't know if you guys do JavaScript, nor how similar this may be to any traditional gaming language, but it's worth asking.

Basically I have the following JavaScript formula representing a bouncing object with gravity, from the standard jQuery UI library: http://code.jquery.com/ui/1.10.0/jquery-ui.js (search for 'Bounce: function'). A demo here shows it in action: http://jsfiddle.net/NtkNB.

```
Bounce: function ( p ) {
    var pow2,
        bounce = 4;

    while ( p < ( ( pow2 = Math.pow( 2, --bounce ) ) - 1 ) / 11 ) {}
    return 1 / Math.pow( 4, 3 - bounce ) - 7.5625 * Math.pow( ( pow2 * 3 - 2 ) / 22 - p, 2 );
}

```

It works nicely but I need to increase the 'bounciness' of the object. I believe this is called 'restitution'.

I've played around with the numbers but it's admittedly just trial and error (mostly error!) and just can't get it to work as desired. I wondered if someone here might be able to understand this and could say whether it's actually possible to increase the restitution of the object within the bounds of this equation, or if not, how it could be modified such.

I totally appreciate any help anyone can give on this one as I've sunk so many hours into this without any joy whatsoever.

Many thanks.

# Answer
> 4 votes
Instead of drowning in maths, you could simulate physics.

For every object every step:

```
apply gravity  (add constant to velocity)
apply velocity (add velocity to position)
if position > some limit then
    reverse velocity
    multiply velocity by "bounciness" between 0 and 1
    if velocity < 0.5 then
        set velocity and gravity to 0
    endif
endif

```

Here's a comparison of bounciness values `0.7`, `0.8` and `0.9`:

<sup>(Apologies for the low framerate. GIFs are complicated.)</sup>

---
Tags: mathematics, javascript, physics, movement
---


# Question
Title: 8 directional movement - Maintain vertical position
I have a top-down game that has 8 directions of movement (top/down/left/right/topright/topleft/bottomright/bottomleft). There are sprites for each direction of movement. This is just an example spritesheet:

The problem is when I want to retain the vertical position. When I let go of the buttons on the keyboard, it polls the keys quickly and ends up facing the character in either left/right/up/down position depending on the last key that was released.

I added a delay for polling the keypresses, but I do not like this solution as it creates a noticeable lag.

Can anyone think of logic that would be able to allow my sprite to retain the proper direction when the keys are unpressed? Here is the current code:

```
if (kbState.IsKeyDown(Keys.Up) && kbState.IsKeyDown(Keys.Left))
    character.ChangeDirection(Direction.UpLeft);
else if (kbState.IsKeyDown(Keys.Up) && kbState.IsKeyDown(Keys.Right))
    character.ChangeDirection(Direction.UpRight);
else if (kbState.IsKeyDown(Keys.Down) && kbState.IsKeyDown(Keys.Left))
    character.ChangeDirection(Direction.DownLeft);
else if (kbState.IsKeyDown(Keys.Down) && kbState.IsKeyDown(Keys.Right))
    character.ChangeDirection(Direction.DownRight);
else  if (kbState.IsKeyDown(Keys.Up))
    character.ChangeDirection(Direction.Up);
else if (kbState.IsKeyDown(Keys.Down))
    character.ChangeDirection(Direction.Down);
else if (kbState.IsKeyDown(Keys.Left))
    character.ChangeDirection(Direction.Left);
else if (kbState.IsKeyDown(Keys.Right))
    character.ChangeDirection(Direction.Right);

```

---

**Edit**

Settled for the following code:

```
float delay = 0.04f;
float DELAY = 0.04f;
....

//Get movement
delay -= (float)gameTime.ElapsedGameTime.TotalSeconds;
if (delay < 0)
{
      int vertical = kbState.IsKeyDown(Keys.Up) ? -1 : kbState.IsKeyDown(Keys.Down) ? 1 : 0;
      int horizontal = kbState.IsKeyDown(Keys.Left) ? -1 : kbState.IsKeyDown(Keys.Right) ? 1 : 0;
      movement = new Vector2(horizontal, vertical);
      delay = DELAY;
}

character.Update(gameTime, movement);

```

Seems I have to use a delay in order to get this to work. Thanks for the feedback guys.

# Answer
This is something I just worked on because I had similar issue in the past and the question made me curious to revisit it.

One thing to start with is to create your own utility class for handling Input that you can use on all future projects as the default methods with XNA are clumsy. You want methods as @Hackworth mentioned to detect when a key has been released/pressed/down that is easier to manage.

Within my Update Method for the character:

```
 var velocity = Vector2.Zero;

    // Notice that velocity persists through these keypresses and
    // keys are polled individually
 if (InputHandler.KeyDown(Keys.Up) && !InputHandler.KeyDown(Keys.Down))
     velocity = new Vector2(velocity.X, -1);
 if (InputHandler.KeyDown(Keys.Down) && !InputHandler.KeyDown(Keys.Up))
     velocity = new Vector2(velocity.X, 1);
 if (InputHandler.KeyDown(Keys.Right) && !InputHandler.KeyDown(Keys.Left))
     velocity = new Vector2(1, velocity.Y);
 if (InputHandler.KeyDown(Keys.Left) && !InputHandler.KeyDown(Keys.Right))
     velocity = new Vector2(-1, velocity.Y);

    // now that each part of the Vector2 is set to 0/1/-1 we can set an enum
    // Representing this Vector2's direction.
    SetDirection(velocity);

    // Now, within that tiny amount of time we might have released a key
    // which causes our character to annoy us with his orientation.
    // So, let's override with a more desired orientation.

    // Up_Right
    if (InputHandler.KeyDown(Keys.Up) && InputHandler.KeyReleased(Keys.Right))
        DrawDirection = Directions.UP_RIGHT;
    if (InputHandler.KeyDown(Keys.Right) && InputHandler.KeyReleased(Keys.Up))
        DrawDirection = Directions.UP_RIGHT;
    // Up_Left
    if (InputHandler.KeyDown(Keys.Up) && InputHandler.KeyReleased(Keys.Left))
        DrawDirection = Directions.UP_LEFT;
    if (InputHandler.KeyDown(Keys.Left) && InputHandler.KeyReleased(Keys.Up))
        DrawDirection = Directions.UP_LEFT;
    // Down_Right
    if (InputHandler.KeyDown(Keys.Down) && InputHandler.KeyReleased(Keys.Right))
        DrawDirection = Directions.DOWN_RIGHT;
    if (InputHandler.KeyDown(Keys.Right) && InputHandler.KeyReleased(Keys.Down))
        DrawDirection = Directions.DOWN_RIGHT;
    // Down_Left
    if (InputHandler.KeyDown(Keys.Down) && InputHandler.KeyReleased(Keys.Left))
        DrawDirection = Directions.DOWN_LEFT;
    if (InputHandler.KeyDown(Keys.Left) && InputHandler.KeyReleased(Keys.Down))
        DrawDirection = Directions.DOWN_LEFT;

    private void SetDirection(Vector2 direction)
    {
             if (direction.X == 0 && direction.Y == -1)
                DrawDirection = Directions.UP;
            else if (direction.X == 0 && direction.Y == 1)
                DrawDirection = Directions.DOWN;
            else if (direction.X == -1 && direction.Y == 0)
                DrawDirection = Directions.LEFT;
            else if (direction.X == 1 && direction.Y == 0)
                DrawDirection = Directions.RIGHT;
            else if (direction.X == -1 && direction.Y == -1)
                DrawDirection = Directions.UP_LEFT;
            else if (direction.X == -1 && direction.Y == 1)
                DrawDirection = Directions.DOWN_LEFT;
            else if (direction.X == 1 && direction.Y == -1)
                DrawDirection = Directions.UP_RIGHT;
            else if (direction.X == 1 && direction.Y == 1)
                DrawDirection = Directions.DOWN_RIGHT;
    }

```
> 2 votes

# Answer
What you need is to store the previous frame's keyboard state. Then determine which button has just been pressed compared to the previous state, and only if a button goes from released to pressed can it change the direction of your character. That way, you don't need to fiddle with artificial delays or anything.

Basically you want to implement the equivalent of the KeyDown event that you may know from a Forms or WPF UI application.

You could use this method:

```
    private bool keyWentDown(Keys key)
    {
        return kbState.IsKeyDown(key) && prevKbState.IsKeyUp(key);
    }

```

Basically you can re-use your code as it is. However, you don't execute it every frame, but only when your character direction actually needs updating, i.e. when any of the direction keys has been pressed.

So the complete code could be:

```
        if (keyWentDown(Keys.Up)
            || keyWentDown(Keys.Down)
            || keyWentDown(Keys.Left)
            || keyWentDown(Keys.Right))
        {
            //your code
        }

```
> 2 votes

# Answer
Compare the last player position (differing from the current position) with the current position and don't take the arrow keys in account at all. I.e. only store the last position when actually a movement happens.

Assuming (y-axis pointing towards bottom):

```
if (x < lastX) {
    if (y < lastY) {
        // top left
    } else if (y == lastY) {
        // left
    } else { // y > lastY
        // bottom left
    }
} else if (x == lastX) {
    if (y < lastY) {
        // top
    } else if (y == lastY) {
        // Not allowed
    } else { // y > lastY
        // bottom
    }
} else { // x > lastX
    if (y < lastY) {
        // top right
    } else if (y == lastY) {
        // right
    } else { // y > lastY
        // bottom right
    }
}

```
> 0 votes

---
Tags: xna, c#, monogame
---


title: Optimizing gravity calculations

text:
# Question
Title: Optimizing gravity calculations
I've got a bunch of objects of varying size and velocity which gravitate towards each other. On every update, I have to go over every object and add up the forces due to gravity of every other object. It doesn't scale very well, is one of two big bottlenecks I've found in my game, and I'm not sure what to do to improve the performance.

It *feels* like I should be able to improve the performance. At any given time, probably 99% of the objects in the system will only have a negligible influence on an object. I of course can't sort the objects by mass and only consider the top 10 largest objects or something, because the force varies with the distance more than with the mass (the equation is along the lines of `force = mass1 * mass2 / distance^2`). I think a good approximation would be to consider the largest objects *and* the closest objects, ignoring the hundreds of tiny fragments of rock on the other side of the world that can't possibly affect anything -- but in order to find out which objects are closest I have to iterate over *all* the objects, and their positions are changing *constantly*, so it's not like I can just do it once.

Currently I'm doing something like this:

```
private void UpdateBodies(List<GravitatingObject> bodies, GameTime gameTime)
{
    for (int i = 0; i < bodies.Count; i++)
    {
        bodies[i].Update(i);
    }
}

//...

public virtual void Update(int systemIndex)
{
    for (int i = systemIndex + 1; i < system.MassiveBodies.Count; i++)
    {
        GravitatingObject body = system.MassiveBodies[i];

        Vector2 force = Gravity.ForceUnderGravity(body, this);
        ForceOfGravity += force;
        body.ForceOfGravity += -force;
    }

    Vector2 acceleration = Motion.Acceleration(ForceOfGravity, Mass);
    ForceOfGravity = Vector2.Zero;

    Velocity += Motion.Velocity(acceleration, elapsedTime);
    Position += Motion.Position(Velocity, elapsedTime);
}

```

(note that I've removed a lot of code -- for example the collision tests, I do not iterate over the objects a second time to detect collisions).

So I'm not always iterating over the whole list -- I only do that for the first object, and every time the object finds the force it feels toward another object, that other object feels the same force, so it just updates both of them -- and then that first object doesn't have to be considered again for the rest of the update.

The `Gravity.ForceUnderGravity(...)` and `Motion.Velocity(...)`, etc. functions just use a bit of XNA's built in vector math.

When two objects collide, they create massless debris. It's kept in a separate list and the massive objects do not iterate over the debris as part of their velocity calculation, but each piece of debris must iterate over the massive particles.

This doesn't have to scale to incredible limits. The world isn't unlimited, it contains a border which destroys objects that cross it -- I'd like to be able to handle maybe a thousand or so objects, currently the game starts to choke around 200.

Any thoughts on how I might improve this? Some heuristic I can use to shave the loop length from hundreds down to just a few? Some code I can execute less often than every update? Should I just multithread it until it's fast enough to allow for a decent sized world? Should I try to offload the velocity calculations to the GPU? If so, how would I architect that? Can I keep static, shared data on the GPU? Can I create HLSL functions on the GPU and call them arbitrarily (using XNA) or do they have to be part of the draw process?

# Answer
This sounds like a job for a grid. Divide your game space into a grid and for each grid cell keep a list of the objects currently in it. When objects move across a cell boundary, update which list they're in. When updating an object and searching for others to interact with, you can look at just the current grid cell and a few neighboring ones. You can tweak the size of the grid for the best performance (balancing the cost of updating the grid cells - which is higher when the grid cells are too small - with the cost of doing the searches, which is higher when the grid cells are too large).

This will, of course, cause objects that are farther apart than a couple of grid cells not to interact at all, which is probably an issue because a large accumulation of mass (either a big object, or a cluster of many small objects) should, as you mentioned, have a larger region of influence.

One thing you could do is keep track of the total mass within each grid cell, and treat the whole cell as a single object for the purposes of farther-away interactions. That is: when you calculate the force on an object, calculate the direct object-to-object acceleration for the objects in a few nearby grid cells, then add in a cell-to-cell acceleration for each farther-away grid cell (or maybe just the ones with a non-negligible amount of mass in them). By a cell-to-cell acceleration, I mean a vector computed using the two cells' total masses and the distance between their centers. That should give a reasonable approximation of the summed gravity from all the objects in that grid cell, but much more cheaply.

If the game world is very large, you could even use a *hierarchical* grid, like a quadtree (2D) or octree (3D), and apply similiar principles. Longer-distance interactions would correspond to higher levels of the hierarchy.
> 26 votes

# Answer
The Barnes-Hut algorithm is the way to go with this one. It's been used in supercomputer simulations to solve your exact problem. It's not too hard to code, and it's very efficient. I actually wrote a Java applet not too long ago to solve this problem.

Visit http://mathandcode.com/programs/javagrav/ and press "start" and "show quadtree".

In the options tab, you can see that the particle count can go all the way up to 200,000. On my computer, the calculation finishes in about 2 seconds (the drawing of 200,000 dots takes about 1 second, but the calculation runs on a separate thread).

Here's how my applet works:

1. Create a list of random particles, with random masses, positions, and starting velocities.
2. Construct a quadtree from these particles. Each quadtree node contains the center of mass of each subnode. Basically, for each node you have three values: massx, massy, and mass. Every time you add a particle to a given node, you increase massx and massy by particle.x\*particle.mass and particle.y\*particle.mass respectively. The position (massx/mass, massy/mass) will end up as the node's center of mass.
3. For each particle, calculate the forces (fully described here). This is done by starting at the top node and recursing through each subnode of the quadtree until the given subnode is small enough. Once you stop recursing, you can calculate the distance from the particle to the node's center of mass, and then you can calculate the force using the node's mass and the particle's mass.

Your game should easily be able to handle a thousand mutually attracting objects. If each object is "dumb" (like the bare-bones particles in my applet), you should be able to get 8000 to 9000 particles, maybe more. And this is assuming single-threading. With multi-threaded or parallel computing applications, you can get many more particles than that updating in real time.

See also: http://www.youtube.com/watch?v=XAlzniN6L94 for a large rendering of this
> 17 votes

# Answer
Nathan Reed has an excellent answer. The short version of it is to use a broadphase technique that fits your simulation's topology, and to only run the gravity calculations on pairs of objects that are going to have a noticeable effect on each other. It's really no different than what you'd do for regular collision detection broadphase.

Carrying on from that, though, another possibility is to only update objects intermittently. Basically, each time step (frame) only update a fraction of all the objects, and leave the velocity (or acceleration, depending on your preference) the same for the other objects. The user is unlikely to notice any delay in the updates from this so long as the intervals aren't too long. This will give you a linear speed up of the algorithm, so definitely look into the broadphase techniques like Nathan suggested as well, which can give much more significant speedups if you have a ton of objects. While not at all modeled the same in the slightest, this is kind of like having "gravity waves." :)

Also also, you could generate a gravity field in one pass, then update the objects in a second pass. The first pass you're basically filling a grid (or a more complex spatial data structure) with the gravity influences of each object. The result now is a gravity field that you can even render (looks pretty cool) to see what acceleration will be applied to an object at any given location. Then you iterate over the objects and simply apply the gravity field's effects to that object. Even cooler, you can do this on a GPU by rendering the objects as circles/spheres to a texture, then reading the texture (or using another transform-feedback pass on the GPU) to modify the object's velocities. So long as the GPU has a decent fillrate and your objects have a reasonable (if technically unrealistic) cut-off distance for their gravitational effect, this will likely be the fastest approach (but profile and test, as always).
> 3 votes

# Answer
I would recommend using a Quad Tree. They allow you quickly and efficiently look up all objects in an arbitrary rectangular area. Here's the wiki article on them: http://en.wikipedia.org/wiki/Quadtree

And a shameless link to my own XNA Quad Tree project on SourceForge: http://sourceforge.net/projects/quadtree/

I would also maintain a list of all the large objects so that they can interact with everything regardless of distance.
> 3 votes

# Answer
Just a small bit of (possibly naive) input. I don't do game programming, but what I am feeling is that your fundamental bottleneck is the gravity-due-to-gravity calculation. Instead of iterating over each object X and then finding the gravitational effect from each object Y and adding it, you can take each pair X,Y and find the force between them. That should cut the number of gravity calculations from O(n^2). Then you will be doing a lot of addition (O(n^2)), but this is normally less expensive.

Also at this point you can implement rules such as "if the gravitational force will be less than \epsilon because these bodies are too small, set the force to zero". It may be advantageous to have this structure for other purposes too (including collision detection).
> 0 votes

# Answer
In extending seanmiddleditch's answer, I thought I might shed some light (irony?) on the gravity field idea.

Firstly, don't think of it as a texture, but a discrete field of values that can modified (a two-dimensional array, as it were); and the subsequent accuracy of the simulation could be the resolution of that field.

When you introduce an object into the field, its gravitation potential can be calculated for all surrounding values; thereby creating a gravitation *sink* in the field.

But how many of these points should you calculate before it becomes more or as ineffective as before? Probably not many, even 32x32 is a substantial field to iterate for each object. Therefore break the entire process into multiple passes; each with varying resolutions (or accuracy).

Ie, the first pass may calculate the objects gravity represented in a 4x4 grid, with each cell value representing a 2D coordinate in space. Giving an O(n * 4 * 4) sub-total complexity.

The second pass may more accurate, with a 64x64 resolution gravity field, with each cell value representing a 2D coordinate in space. However, as the complexity is very high, you can restrict the radius of surrounding cells affected (perhaps, only the surrounding 5x5 cells are updated).

An additional third pass could be used for high accuracy calculations, with maybe a resolution of 1024x1024. Remembering at no time are you actually performing 1024x1024 separate calculations, but operating only on portions of this field (perhaps 6x6 sub-sections).

In that way, your overall complexity for the update is O(n * (4\*4 + 5\*5 + 6\*6)).

To then calculate the velocity changes to each of your objects, for each gravity field (4x4, 64x64, 1024x1024) you just map the point masses position to a grid cell, apply that grid cells overall gravitational potential vector to a new vector; repeat for each "layer" or "pass"; then add them together. This should give you a good resultant gravitational force vector.

Therefore, the overall complexity is: O(n * (4\*4 + 5\*5 + 6\*6) + n). What really counts (for complexity) is how many surrounding cells you update when calculating the gravitational potential in the passes, not the overall resolution of the gravity fields.

The reason for low resolution fields (first passes) is to obviously encompass the universe as a whole, and ensure outlying masses are attracted to more dense areas despite distance. Then use higher resolution fields as separate layers to increase accuracy for neighboring planets.

I hope this made sense.
> 0 votes

# Answer
How about another approach:

Assign an area of influence to objects based on their mass--they're simply too small to have a measurable effect beyond that range.

Now divide your world up into a grid and put each object in a list of all the cells it has an influence on.

Do your gravity calculations only on objects in the list attached to the cell an object is in.

You only have to update the lists when an object moves into a new grid cell.

The smaller the grid cells the less calculation you'll do per update but the more work you'll do updating lists.
> 0 votes

---
Tags: xna, algorithm, physics, optimization
---


title: How to design rating (leaderboard)

text:
# Question
Title: How to design rating (leaderboard)
I have a quiz online game. For each game there is a prize (number of scores). Now I have three ratings: top for the last day, top for the last week, total top (based on the sum of scores). Sum is not bad, but there is an issue: the more you play (even with bad results), the higher you are because more games leads to more points. I want to build a new rating, that takes in account not only sum of scores, but performance in games to. Just an average prize is not a good idea for me, because it means that winner of a single game will be higher, than a person who won 9 games and got not-maximum score in the last one.

Do you have any ideas/experience, what formulas could be used?

Thanks.

# Answer
> 3 votes
I'd probably ignore these scores and make a rating similar to the Elo rating system.

In short:

* Have an invisible rating number for each and every player. They start at some fixed number, like 100 or 1000.
* You then try to determine how good the player will be (either against other players he's playing with/against or simply "how many questions he'll answer right").
* Once that's done, you let them play.
* After the game compare the real result to the expected result calculated before.
* The bigger the discrepancy, the bigger the change in the Rating will be. For example, you expected the player to guess 50% of the questions correct. If he did better (and wins), he's gaining points based on how good he was (only slightly better? -\> less points; a lot better -\> more points). In case of a lost game, you do the same - just reversed.

For a highscore or ranking, you can now compare these ratings. You could do things like "highest rating overall" or "highest gain last week". To avoid people stop playing to Keep a good position you simply lower their score over time if they don't play at all.

Just find a good name/system to actually visualize this. Just don't display raw numbers, as this might get People into number crunching, trying to manipulate it, etc.

---
Tags: game-design, leaderboards
---


# Question
Title: Jagged transparency when rendering translucent textures (OpenGL 3.2 + GLSL)
Like most others, I'll start off mentioning that I'm still a beginner when it comes to OpenGL and GLSL programming. So bear with me on any dumb mistakes you may spot in the code ahead.

I'm basically trying to render a model of a girl whose hair is implemented with transparent TGA textures. In my code I've setup OpenGL 3.2 (core profile, no fixed function calls) with the following calls before rendering the model's geometry (in clock-wise order):

```
glEnable(GL_DEPTH_TEST);
glEnable(GL_DEPTH_CLAMP);
glDepthMask(true);
glDepthFunc(GL_LEQUAL);
glDepthRange(0, 1);
glClearDepth(1.0);

glEnable(GL_BLEND);
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);

```

In my fragment shader, I'm doing alpha premultiply of the textures coming in and I'm also discarding fragments with an alpha value lower than 0.5, like so:

```
vec4 SampledColor = texture2D(gColorMap, TexCoord0.xy);

SampledColor.rgb *= SampledColor.a;

if (SampledColor.a < 0.5) {
    discard;
}

FragColor = SampledColor * TotalLight;
FragColor.a = SampledColor.a;

```

The rendered image does display some transparency, but the model's hair looks jagged, here's a snapshot:

http://i32.photobucket.com/albums/d9/\_Silencer/Samples/test\_002.png

And here's the base texture being used to sample color values:

```
i32 . photobucket . com/albums/d9/_Silencer/Samples/sample.png

```

(note: photobucket only allowed me to upload sample as `.png` :P, but it's a TGA file).

I know for sure that the hard jaggies happen because I'm telling the shader to discard the fragment if falls below my arbitrary alpha threshold. What I'm wondering though is if there's any way to smoothly display the transparent pixels in the texture, pretty much like what can be seen on the right side of the rendered image, where the hair texture does blend in well with the gray background color.

I'm also pretty sure that I'm feeding an appropriate transparent image to OpenGL, but I can't find a way to get rid of the jagged artifacts.

Now, if I don't discard the fragment in the Fragment shader, the rendered hair texture will still appear transparent, but the "background" of the geometry adopts the background color of the color buffer, like so.

http://i32.photobucket.com/albums/d9/\_Silencer/Samples/test\_001.png

I've read that I may need to draw the geometry in sorted order according to the distance from the current viewpoint but I'm not sure how could I determine that with the hair chunks in this case.

So clearly I'm not understanding how to correctly handle translucent textures in rendered geometry. There has to be a nice way to do this since many games show this kind of textures correctly.

**UPDATE** The longer I continue investigating the subject, it seems that this is not a trivial problem. I may need to implement some sort of order independent transparency technique. I read that this can be done on OpenGL 4.0 capable hardware. What about OpenGL 3.3 hardware?

I appreciate any pointers or advice anyone could provide.

Thank you for your time and help!

# Answer
> 4 votes
I think the 0.5 falloff is really too strong and unnecessary; with 0.1 instead you will probably discard 95% of the fragments you already discard. You could even smooth the alpha to avoid remaining artifacts:

```
if (SampledColor.a < 0.1)
    discard;
SampledColor.rgb *= smoothstep(0.1, 1.0, SampledColor.a);

```

# Answer
> 2 votes
You have two options:

* Separate the hair geometry from the model and draw it after, ensuring a correct back-to-front order.
* Use alpha testing. You won't have nice blending this way but the hair contour will appear nicely sharp.

---
Tags: opengl, glsl, transparency
---


# Question
Title: Minecraft - How do I check if someone has a clear inventory
How do I check if a player has a clear inventory? I'm making a PvP arena plugin but I need it so when someone types `/pvp` join, it checks if they have a clear inventory. If they do have a clear inventory, it lets them join, if they don't, it asks them to.

I tried this but it's not reliable as there are more slots:

```
if(p.getInventory().getArmorContents() == null
    && p.getInventory().getItemInHand() == null
    && p.getInventory().getItemInHand() == null) {

```

Then I tried this but it did not work:

```
if (p.getInventory().getContents().length == 0) {

```

# Answer
> 4 votes
You could try to accomplish it by looping through player's inventor and checking if Nth slot in his inventory is empty, if it isn't -- the function returns false.

```
    private boolean hasItems(ItemStack item) {
        for (int i=0; i<=thePlayer.inventory.getSizeInventory()-5; i++) {
             if (thePlayer.inventory.mainInventory[i].itemId != NULL) {
                 return false;
             }
        }
        return true;
    }

```

You subtract 1 from the getSizeInventory() because it returns length and the arrays in Java are zero-based, and 4 because crafting slots count as well (I guess).

---
Tags: java, minecraft-modding, bukkit
---


# Question
Title: Accessing other classes from a Box2D (farseer) body
I'm using Farseer for physics in a game, and have several key classes: Planet and PlanetProp. Each planet has a large circular body and a "field". This field is a large sensor around the body. PlanetProps are pulled towards whichever planet's field they are currently in (a struct called PlanetInfo). So I've set up a collision handler in PlanetProp which will (whenever it is called) detect whether the fixture it has collided with is a sensor.

I then plan to A) detect if the sensor belongs to a Planet and B) Set the PlanetProp to be pulled towards the planet

So in other words, is it possible to access a class using a collision callback with a fixture from a body in that class?

EDIT: Does this involve UserData? If I was using C++ I might be able to put a pointer to the class in that, but I'm using c#.

# Answer
> 1 votes
In C# there you have "**reference types**" and "**value types**". Reference types are created with the `class` keyword. Value types are created with the `struct` keyword. (Extended explanation on MSDN.)

A reference (for example a "`Planet myPlanet`" variable if you have `class Planet`) is very similar to a pointer. It takes the same space (32 bits or 64 bits, depending on your architecture) and "points to" (references) an *instance* of a *reference type*. Unlike pointers you can't perform arithmetic on them, and this is so the garbage collector can do its thing and track what objects are still referenced (so they are not collected).

So you are quite safe to set the `UserData` to an instance of the planet object. It will refer to that same object and a copy will not be made.

It's a different story if you have a value type (ie: `struct Planet`). This would get copied when you assign it. (Actually, in this case, because `UserData` is of type `object` and expects a reference type - the framework will "box" your value type by copying it into an immutable reference type.)

Personally I find it helpful - especially when doing game development where you care about memory - to use different syntax highlighting colours for reference types vs value types.

---
Tags: xna, c#, box2d
---


# Question
Title: How to read key value pair in cocos2dx from txt file?
I this is the first time I am developing for BB10 OS using cocos2dx.

I need to read key value pair in Cocos2Dx.

eg: Skill= 5
Power= Awesome

The target is Blackberry 10OS and using QNX Momentics for development. Is there a library for this? Or as an alternate approach, if this can be a stored in a lua file, then how to parse the lua file to retrive these values, based on keys?

# Answer
> 0 votes
cocos2d-x can parse .plist and store it in a CCDictionary. I suggest you use a plist rather than a normal txt file.

If you are using XCode, you can create from there.

To load the plist and store it in the dictionary, you can do this:

```
const char *plistPath = CCFileUtils::sharedFileUtils()->fullPathFromRelativePath("myplist.plist");
CCDictionary *myKeyValuePairDictionary = CCDictionary::createWithContentsOfFileThreadSafe(pszPath);

```

---
Tags: cocos2d-x
---


title: Physics movement prediction is way off

text:
# Question
Title: Physics movement prediction is way off
I'm making a simple, non-networked game. There are two players and a ball. In implementing the AI for the second player, I've run into a huge problem predicting where the ball will hit the ground. Either I've made a mistake in the physics engine or in implementing the prediction itself. I wrote the physics engine, and while it works visually as I expect it to, I won't rule it out as a suspect. First I'd like to make sure I haven't made a mistake in the prediction code. Here's what I have found so far:

I print the predicted time to impact and the accumulated time in each frame. The time predicted for impact is way off.

```
tti: 0.678233
total time: 0
.
.
tti: 0.0108339
total time: 0.94969
[ball] ground collision

```

The code for predicting is in two functions.

```
double nextBallCollisionWithGround(Ball *ball, double groundHeight) {
    double timeToImpact = quadraticSolver(kGravity, ball->velocity().y, ball->position().y - ball->radius() - groundHeight);
    std::cout << " tti: " << timeToImpact << endl;
    double groundPos = -3.;
    if (timeToImpact > 0) {
        groundPos = ball->velocity().x * timeToImpact + ball->position().x;
    }
    return groundPos;
}

double quadraticSolver(double a, double b, double c) {
    double ans = -1.;
    double det = (b*b) - (4.*a*c);
    double t1, t2;
    if (det > 0.) {
        t1 = (-b + sqrt(det)) / (2. * a);
        t2 = (-b - sqrt(det)) / (2. * a);
        if (t1 > 0.)
            ans = t1;
        if (t2 > 0.)
            ans = t2;
    }
    return ans;
}

```

If there's no problem in these functions, I can include the relevant parts of the physics engine to see if the problem is there.

# Answer
I don't know what `kGravity` is, but it should be half the gravitational acceleration.

Because the formula is:

```
h(t) = t * velo_y + 0.5 * -gravity * t^2

```

Where, `h(t)` is the height in function of time, `t` is the time and `velo_y` is the initial y velocity. And `gravity` is for example `9.81 m/s^2`.

So, as you can see, the `a` of the quadratic equation is `0.5 * -gravity`.

---

Some remarks:

* Little imperfection to your quadratic solve method: the determinant can be zero as well. You will have two identical roots.
* In order to get the correct root for this equation, you should make sure you are taking the smallest positive root for your collision prediction.
> 3 votes

---
Tags: mathematics, physics
---


# Question
Title: Put objects on a 2D maps using a matrix of distances
Is that possible to put objects in a 2D map using only a matrix of their relative distance ?

An example would be putting cities on a map using the distances between them. There would be a minimum of 4 cities.

Thanks a lot.

# Answer
> 0 votes
Distance could be enough information to plot 4 cities - but only if you're ok with them ending up in a different configuration every time.

For example, if you have city B a distance of 10 cells away from city A, then you can use bresenham's to determine a circle describing all possible locations for city B. If you add city C into the equation (and City C has to be 12 cells away from city B and 8 away from city A), then it gets tricky - you'll have to again use bresenham's to get circles of radius 8 and 12 around cities A and B, and see where those two intersect. There's dozens of possible layouts just for this - the larger the radii, the more there will be.

If your cities all have required distances from each other, this gets more complicated as you add more cities. As soon as you add a city D, your layout for cities A B and C isn't guaranteed to accomodate it. If all you have is a single distance requirement (i.e. city D only has to be 15 cells from city C), then it becomes a lot simpler.

I hope I didn't overcomplicate this - let me know if I can clarify or elaborate!

---
Tags: 2d, maps, planning
---


title: Problem with GLFW input

text:
# Question
Title: Problem with GLFW input
I am using GLFW for the input in my game. I just started learning it and I have encountered a problem. The problem is the input, I have a callback function, where I check for keypresses. I want the program to toggle wireframe mode when the user press 1, therefore I have this code:

```
if(key == '1' && action == GLFW_PRESS)
{
    wireframe = !wireframe;
}

```

The problem is that I am Czech and we obviously have different keyboard layout - I use english keyboard layout for programming and when I press 1 it works, however, when I press the same key on czech layout it doesn't work, probably because we have to press Shift along with the '1' key to actually get the 1 on the screen. It may seem obvious that it does not work, but when I used SFML it worked.

I also tried replacing the '1' with 49 or 0x0031, but the result is the same.

Is there a solution or do I have to set the layout manually by the system API?

Thanks in advance.

# Answer
What I think happens is that a unicode int gets passed when you have your Czech layout.

(What I'm not sure is how the int get's passed as a char . . .)

If you use xev in the terminal, a window will pop out and input info will print in your terminal when you click/move/drag keys or your mouse.

This is a good way to check what the difference between '1' in US layout and '1' in Czhech layout.

There might be a better way to doing this, but otherwise I would suggest to create a table from your xkbmap manually or make a script that gets that info and automatically makes an array from it.

That's all I know, but good luck!
> 1 votes

---
Tags: c++, input, glfw
---


# Question
Title: What Java library/framework for a game with Baldur's Gate like grapics?
I really would like to create my own small rpg. It could probably look as simple like baldurs gate. So without fancy 3D stuff.

As language I want to use java (or scala, I thinking about it - the good thing is that all java libs would work with scala too, and there are a lot of java game libs) and I'm not sure what lib/framework should I choose. I thought about LWJGL or Slick2D. Because I wont use that much 3D, Slick2D would be the better choice? Or doesn't matter? Any ideas or suggestions? Thank you

# Answer
> 5 votes
If you're considering using LWJGL, I would suggest you also check out libgdx, which uses a LWJGL wrapper for the desktop client. You get the added benefit of an easy port to Android/iOS/HTML5. I don't know how this compares to Slick2D.

Also, even if you are making a 2D game, you should still use 3D-acceleration (e.g. through OpenGL), thought this might be hidden away by the framework so that you don't notice it. 2D graphics in a 3D world doesn't need to be more than looking at a picture on a frame.

Do some research on the various engines you can choose from (this is a google search away). Things to consider is entry-level difficulty, what features you need, and what platforms you are targeting.

# Answer
> 3 votes
I would go for a 3D native approach with LWJGL. When you use OpenGL, all the rendering happens on the GPU, which improves performance. This will allow you to extend your graphics when you think it would be nice to. Using OpenGL allows you everything. This way, you are not limited to some features of a specific library.

On the other side, you will learn how to work with OpenGL.

Don't think that when you use OpenGL, your game can't be 2D.

---
Tags: java, 2d
---


title: Guidelines when rigging a character

text:
# Question
Title: Guidelines when rigging a character
Just wondering that how many IK (Inverse Kinematic) bones should you apply to a game character before it starts to go resource hog. Basically should you try to get rid of IK bones and just try to animate without them but using IK bones makes things easier for the animator but might cause unnecessary use of resources and possibly cause bottleneck when calculating bone and mesh translations.

I'm using Blender and couple of animation tutorials are suggesting to use IK controllers and they indeed help a lot but when importing the character into a game they might be plain pointless since they are used only to help the animator.

# Answer
> 4 votes
I'd expect that they are no costlier than a standard bone to most game engines. The way animations are normally exported is by storing the transform of each bone for every frame of animation (with some optimizations to save on storage space).

The standard skinned animation limitations in game engines tend to be:

* A maximum of four bones influence each vertex. It'll pick the top four and ignore the rest.
* The fewer bones the better as the model may need to be subdivided if there's too many due to limitations on older hardware. Aim to stay under about 64 bones where performance is more of an issue than animation quality.

---
Tags: animation, skeletal-animation, rigging, inverse-kinematics
---


title: OpenGL: Transformations

text:
# Question
Title: OpenGL: Transformations
I'm not sure if I correctly understand 3D transformations in OpenGL. Let's assume I'm using the typical matrix stack.

It seems like you move the world X units over, drop in a bag of verts (a mesh) and move the world back by popping the matrix off the stack, then you repeat the process to place another model?

Say I wanted to place a model at `(10, 0, 0)` and another at `(0, 10, 0)`. I *think* I would...

```
PUSH move(10,0,0);
DRAW model A;
POP;
PUSH move(0,10,0);
DRAW model B;
POP;

```

Some questions come to mind, like for example what does loading an identity matrix do in the stack?

Am I right to assume that these operations in effect move the world around, then you draw the mesh at 0,0,0 in world space when you've moved the world to your liking?

Or is it the other way around, does GL "apply" the matrix stack to your mesh as you draw it?

Thanks, -Cody

# Answer
OpenGL is a state-machine, it has a *current matrix*.

There are several functions to manipulate the current matrix:

* `glLoadIdentity`, `glLoadMatrix` overwrite the current matrix.
* `glTranslate`, `glScale`, `glRotate`, `glMultMatrix` multiply the current matrix with the appropriate matrix generated by these functions **from the right.**

Now, whenever you draw something it is transformed using the current modelview matrix (and then using the projection matrix). **The stack itself is not used in any way in those transformations, it is merely for storing matrices.** When you push the current matrix onto the stack the current matrix doesn't change. When you pop, the current matrix is overwritten with the matrix from the top of stack.

Also, OpenGL's camera is always at the origin looking in the -Z direction. You can't move the camera but you can “move the world around the camera” into your preferred position.
> 4 votes

# Answer
It's the other way around. Changing the transformation matrix doesn't do anything to what has already been drawn. It only affects what is going to be drawn. Think of your matrix stack as a bunch of filters which your vertices get sent through when you send them to the video card.

An identity matrix does - by definition - nothing when multiplied with another matrix.
> 3 votes

---
Tags: opengl, transformation
---


# Question
Title: Smooth Sprite Movement - Don't Add Velocity to Position?
I am trying to figure out if there is a way to move a sprite smoothly on the screen at different speeds without stuttering, but keeping the effect that it's moving smoothly; especially at faster velocities.

Below is a basic version of what I have with all of the object specific logic stripped out for readability.

```
void MoveableGameObject::update(double time)
{
    //maxVelocity is 10
    currentVelocity = min<float>(currentVelocity + acceleration * time, maxVelocity);
    location.x += currentVelocity;
}

void MoveableGameObject::draw()
{
    sprite->draw(location.x, location.y)
}

```

The part that I do not like is that the next time the frame renders and max velocity has been achieved, the sprite jumps 10 pixels and looks stuttery. If I tone down the numbers then it is of course smoother, but also slower.

I need to find a way to still have the speed, but give a smooth transition somehow. I am having a hard time wrapping my head around trying to implement movement speeds. Am I just using the wrong scale in terms of velocity to pixels?

My brain hurts, but I am still having a blast tinkering around with this and is a nice change of pace from doing nothing but business applications for the past 7 years.

I do have the ability to say run the game logic 20 times a second while rendering at 60 frames a second. Figured I would mention that in case that helps with an answer. Currently they are both just set to 60 since I am only running a single sprite and wanted to test the movement and check the sprite location on `update()` vs. `draw()`.

Thanks in advance for any help.

EDIT: I forgot to mention and not sure if it matters or not, but I am currently using SDL to render.

# Answer
Is that update(time) or update(dt)?

You would have something like:

```
void frameUpdate(){
   dt = time - oldTime;
   time = oldTime;

   // FPS at that specific frame would be 1.0/dt assuming time is in seconds
   // Normally you get the time in microseconds or at least milliseconds
   //   so it would be 1.0/(dt*1e6) or 1.0/(dt*1e4)

   update(dt);
}

```
> 1 votes

# Answer
You should probably change the line:

```
location.x += currentVelocity;

```

to

```
location.x += currentVelocity * time;

```

Remember that velocity describes the change in position *per time*.

In fact, for added accuracy, you could rewrite your `update()` method to look like this:

```
void MoveableGameObject::update(double time)
{
    double oldVelocity = currentVelocity;
    currentVelocity = min<float>(oldVelocity + acceleration * time, maxVelocity);
    location.x += time * (oldVelocity + currentVelocity) / 2;
}

```

The averaging of `oldVelocity` and `currentVelocity` accounts for the fact that the velocity is actually changing during the timestep due to acceleration, so (assuming constant acceleration) the *average* velocity is halfway between them.

For constant acceleration, ignoring the maximum velocity cap, this formula will, in fact, give exact results regardless of the timestep. (It amounts to the same thing as the *Δx* = *v·Δt* \+ *½a·Δt*2 formula you may recall from high school physics for motion under constant acceleration.) If the acceleration varies, you can get even more accurate results using (e.g.) the velocity Verlet method.
> 4 votes

# Answer
It seems that your acc and vel integration isn't right. I'm too busy to write a full answer right now, but read this link: http://lol.zoy.org/blog/2011/12/14/understanding-motion-in-games and also see this ANIMATED presentation on the matter too: http://richardlord.net/presentations/physics-for-flash-games
> 1 votes

---
Tags: 2d, sprites, movement, sdl
---


title: Implementing a color picker

text:
# Question
Title: Implementing a color picker
I'm making a paint program using applets in Java, and I want to create some sort of color palette where the colors blend into each other, similar to this:

However, I'm having trouble understanding the correlation between the R, G, B, values and the X, Y coordinates for both the outer circular color palette, and the inner hue selecting palette.

Representation:

# Answer
The color picker widget you posted defines colors in HSV color space. In HSV space, a color is defined by three values:

**hue:** an angle between 0° and 360° which defines the color (0° is red, 120° is green, 240° is blue). In RGB terms, it tells you which channel (red, green or blue) is the one with the highest value, which one is the channel with the second highest value, and their ratio to each other.

**saturation:** the intensity of that color (a saturation of 0 is gray, hue doesn't matter in this case). In RGB terms, it represents the ratio between the highest channel and the lowest.

**value:** the brightness of the color (a value of 0 is black, neither hue nor saturation matter in this case). It's equal to the RGB channel with the highest value.

In the widget above, the outer ring represents the hue, the x-coordinate of the rectangle represents the saturation (0 is left), and the y-coordinate the volume (0 is at the bottom).

Here are two functions in C which convert between HSV and RGB. Source: http://www.cs.rit.edu/~ncs/color/t\_convert.html

```
// r,g,b values are from 0 to 1
// h = [0,360], s = [0,1], v = [0,1]
//      if s == 0, then h = -1 (undefined)
void RGBtoHSV( float r, float g, float b, float *h, float *s, float *v )
{
    float min, max, delta;
    min = MIN( r, g, b );
    max = MAX( r, g, b );
    *v = max;               // v
    delta = max - min;
    if( max != 0 )
        *s = delta / max;       // s
    else {
        // r = g = b = 0        // s = 0, v is undefined
        *s = 0;
        *h = -1;
        return;
    }
    if( r == max )
        *h = ( g - b ) / delta;     // between yellow & magenta
    else if( g == max )
        *h = 2 + ( b - r ) / delta; // between cyan & yellow
    else
        *h = 4 + ( r - g ) / delta; // between magenta & cyan
    *h *= 60;               // degrees
    if( *h < 0 )
        *h += 360;
}

void HSVtoRGB( float *r, float *g, float *b, float h, float s, float v )
{
    int i;
    float f, p, q, t;
    if( s == 0 ) {
        // achromatic (grey)
        *r = *g = *b = v;
        return;
    }
    h /= 60;            // sector 0 to 5
    i = floor( h );
    f = h - i;          // factorial part of h
    p = v * ( 1 - s );
    q = v * ( 1 - s * f );
    t = v * ( 1 - s * ( 1 - f ) );
    switch( i ) {
        case 0:
            *r = v;
            *g = t;
            *b = p;
            break;
        case 1:
            *r = q;
            *g = v;
            *b = p;
            break;
        case 2:
            *r = p;
            *g = v;
            *b = t;
            break;
        case 3:
            *r = p;
            *g = q;
            *b = v;
            break;
        case 4:
            *r = t;
            *g = p;
            *b = v;
            break;
        default:        // case 5:
            *r = v;
            *g = p;
            *b = q;
            break;
    }
}

```
> 5 votes

# Answer
Usually you would implement this sort of thing via an HSV to RGB conversion, not in RGB directly. The angle around the ring controls the hue, and the XY coordinates on the square select saturation and value. Then you convert the HSV color to an RGB color using the standard formulas, for example as written on Wikipedia.
> 3 votes

---
Tags: algorithm, color, palette
---


# Question
Title: Books that discuss practical rendering techniques?
I'm looking for some books that discuss practical rendering topics like say rendering a bsp level or md2/3 mode, making a little quake like game as the goal or something to that effect. Any recommendations would be much appreciated.

# Answer
> 0 votes
If you want to do any rendering then you should develop an understanding of the foundation frameworks that will be used, as well as an understanding of the rendering pipeline as a whole. OpenGL and DirectX are the two primary standards for rendering graphics, with OpenGL having many varieties depending on the target platform, and DirectX being microsoft exclusive.

Something like this is a good start for DirectX http://www.amazon.com/Introduction-3D-Game-Programming-DirectX/dp/1936420228/ref=sr\_1\_1?ie=UTF8&qid=1360540306&sr=8-1&keywords=directx

And this is one of the standard books for OpenGL http://www.amazon.com/OpenGL-SuperBible-Comprehensive-Tutorial-Reference/dp/0321712617/ref=sr\_1\_2?ie=UTF8&qid=1360540469&sr=8-2&keywords=opengl

---
Tags: rendering, books, binary-space-partitioning, quake3
---


# Question
Title: How to split login and game logic when writing servers?
I'm building a poker like game server, I was going to have all logins and game logic to be handled on one server, but from my research on the web, I learn that this would not scale, and it would make sense to split the work into a login and game servers. But what I don't get is after I handled authentication in the login server, and have the client make a new connection to the game server, how would I know which client is which? Would I not have to re-login again and thus defeat the purpose of having a server for login? Is there some way to pass a connection across processes and machines that I don't know about? Excuse my little knowledge of networking.

# Answer
Although Philipp's answer is perfectly good, there is a slightly different way that does not require a connection between the login server and the game server, which is useful if such a connection is difficult.

1. When the user authenticates successfully on the login server, they are sent a game server address and a login token as above. However this token consists of 2 parts: the time on the login server, and a hash of that number plus their username, their IP address, the IP address or ID of the game server, and a secret key that only you know.
2. The client attempts to log in to the provided game server by sending this token. The server forms the same hash as before, based on the information in the login token plus its own IP address/ID and the secret key. If this hash matches the one in the token, you know the player authenticated properly. Then check the date is not too old (eg. more than 1 minute).

This works because:

* It can't be copied and re-used as the date will expire.
* It can't be constructed without a fresh login without knowing the secret key.
* It can't easily be intercepted by someone else (eg. with a packet sniffer) and used because the original IP address is used to construct it.
* It can't be used for a different account as the username forms part of the hash.
* It can't be used for concurrent logins on different game servers as the server's ID/IP address forms part of the hash.

Or to put it more simply, the hash ensures that it's nearly impossible for the sender to have forged their login token and so the information in the token can be trusted.

As with any security oriented hashing, use the best hash function you can get - at the moment people seem to like bcrypt, PBKDF2, and scrypt - and ensure your secret key is very long so as to make brute force reproduction less practical.
> 3 votes

# Answer
1. After the user authenticated itself to the loginserver, give it a token (an unique, randomly-generated string too long to be guessed).
2. The loginserver picks a gameserver. Send the token, the username and all other relevant data about the user from the loginserver to the server it picked.
3. Send the token and the hostname of the gameserver to the client. Then disconnect it from the loginserver.
4. The client then connects to the gameserver with its username and token.
5. When the token from the client matches the one just reported by the loginserver, you accept it.

Note that in order for this to be secure, the tokens need to be created from a cryptographically secure random number generator, each token may only be accepted once by the gameserver and unused tokens should be discarded after a few minutes.
> 8 votes

---
Tags: server, authentication
---


title: free asset library for panda3d

text:
# Question
Title: free asset library for panda3d
my game with panda3d is slowly taking form. It's still a mere testcase but I'd like to improve its visual. Since the assets from my previous projects don't fit this game I've used placeholders for the player and enemy models. Now the moving cubes and spheres are starting to annoy me. The game is still very small and I'd rather invest my time in coding instead of modelling.

**Do you know a free asset library for panda3d ? I know I can convert most models to panda's .egg format so any good database would be appreciated.** Yes, I've already looked at the standard "asset gallery" from the panda3d website.

I'm probably going to redesign everything eventually, nevertheless I'd prefer opensource/free-to-use libraries because I don't want to check every rock and tree if I have to replace it for distribution.

# Answer
OpenGameArt.org is a place where free and open source assets are collected and distributed:

http://opengameart.org/
> 4 votes

---
Tags: models, 3d-meshes, assets, panda3d
---


# Question
Title: App Programming Question: Converting Code and Project Folders for the Smartphone's OS Compatibility
I was thinking about how does the *Angry Bird* game for the iOS successfully converted into an Android compatible version. Does it involve using Phonegap or something?

When making games for iOS, the programmer preferred XCode. For Android game app, the programmer preferred Eclipse IDE and a LibGDX engine library. Because of this, like *Angry Birds* for example, this game became compatible for the iOS, Android, and even on the desktop computer.

The question is...how does it work?

# Answer
Quote from http://docs.xamarin.com/ios/Guides/Application\_Fundamentals/Building\_Cross\_Platform\_Applications

> Rarely does an organization have the luxury of building mobile apps for a single mobile platform. The fact is, the smartphone and tablet space is dominated by three big platforms: iOS, Android and Windows. As such, **in order to reach users, apps must be designed and built for all three of them. Traditionally this means using each platform’s provided technology and SDK, i.e. Objective-C for iOS, Java for Android and .NET for Windows**. Most cross-platform mobile toolkits fall short in this space because they provide a lowest-common-denominator experience and prevent developers going “to the metal” on any given platform.

Totally googled it :)
> 2 votes

---
Tags: android, iphone, cross-platform, compatibility
---


# Question
Title: How to display height information in tilemap
I want to create a hexagonal tilemap and show regions of different height in the same screen. What ways can you think about to indicate which height a tile is on. (current, lower, higher?)

Several tilemap games avoid this by having special mountain tiles, but that allows for ~2 heights and I would like for more differentiation.

Another approach is to just draw the tiles of current height, but this does look very strange if the map is very bumpy (lot's of holes).

I have not found a nice way to whiten or blacken tiles that are lower or higher than the current viewpoint. Any ideas?

# Answer
> 7 votes
I would go for the pseudo-3d approach and visualize the height with a vertical offset. To avoid the problem that parts of the map are concealed by cliffs, I would only use a few pixels per height level and avoid having differences of more than 4 or 5 levels.

As you can see from this mockup, this is good for visualizing that the tile to the north is higher than the tile to the south, but not so good for visualizing that a tile to the south is higher. For that reason I would recommend to avoid this situation in map design... or you give the player the ability to rotate the map so that they can always choose the best angle to visualize the situation. But don't rely too much on this - you want the player to fight the enemy, not the camera.

# Answer
> 2 votes
I only have experience using GLSL but I'm sure something similar would work for other shading languages.

When you pass your vertex to the shader, you can also pass a uniform stating the current height you're at. That way if you pass the vertex's height through to the fragment shader, you can blend that value with your normally generated texture or color value using mix() or some such.

---
Tags: 2d, tilemap
---


title: XML serialization error on XBOX 360

text:
# Question
Title: XML serialization error on XBOX 360
When try to save game on an xbox with xml serialization i get a code 4 error. I made sure t oadd all the xml referances and there is no errors until i run the game. Any suggestions?

# Answer
Did you reference the correct xbox360 xml serialization namespace found in

**C:\Program Files\Microsoft XNA\XNA Game Studio\v4.0\References\Xbox360\System.Xml.Serialization.dll** ??

Code 4 is a generic error that is difficult to solve without more information on the xml serialization code you have. Paste it here if you need more help.
> 1 votes

---
Tags: xna-4.0, xml
---


title: Run XNA game without graphics

text:
# Question
Title: Run XNA game without graphics
Wondering if there is anyway to run an XNA game with out displaying anything.

I have a working game that runs in a client server setup where one player is the host and other people can connect to his game.

I now want to be able to run the game as a host on a decicated server with no graphics card, basically I dont want to run any Draw() logic at all.

Do i really need to go through the entire game and remove all references to XNA?

How have people done this?

**EDIT**: The reason I want to do this is because I have a working client server setup in the game and I dont want to make a separate "headless" server program.

# Answer
Just make a normal C# project and include the XNA binaries. This will gain you access to the XNA data types and framework methods. My game does this and it works flawlessly.
> 10 votes

# Answer
The answer is: don't do this. If you don't need to make a game - i.e; you're not looking to take advantage of the things XNA offers, why do it? You really should be looking into developing a custom piece of software that can successfully simulate the game you wish to play - typically a console system of some sort. If you give more details, I will update my answer with a less generic response.
> 2 votes

# Answer
Well if you simply wish to eliminate the draw calls have you tried using this : Suppress Draw
> 1 votes

# Answer
To build on untitled's suggestion, you can just include references to the DLLs and use them without using any of the default game loops. For examples of this you can look at the winforms tutorial series on the creators club: http://xbox.create.msdn.com/en-us/education/catalog/sample/winforms\_series\_2

Also if you want to get even more fancy you can replace the entire XNA game loop with your own custom one, and control the entire process. For more information on this look at https://stackoverflow.com/questions/6361691/custom-xna-game-loop-in-windows
> 1 votes

# Answer
If you change the Output Type of a XNA Project to "Console Application", the application will simply open an empty Console at start-up, without ever opening the actual game's window. This might be useful for what you are trying to accomplish, since you want to do tests, and you can very easily use the Console as a debug window.
> 1 votes

# Answer
You can also consider overriding the update and draw calls, and simply return.

Also, dont call the graphicsdevice in your main game classes, which should stop the xna window from being instanced on the game acting as your server.
> 1 votes

---
Tags: xna, xna-4.0
---


title: Smooth rotation

text:
# Question
Title: Smooth rotation
I would like to rotate my Player very smooth. At the moment the player stops rotating when I release the button. Also the rotation should get faster, if the player rotates longer. I use XNA and have no idea how to solve this.

Sry for my english, I hope you understand what I mean.

Michi

# Answer
you could try something like this

```
float turnSpeed;
if (KeyBoard.GetState().IsKeyDown(Keys.Right))
    turnSpeed++;
if (KeyBoard.GetState().IsKeyDown(Keys.Left))
    turnSpeed--;

 RotationAngle += turnSpeed;
 //Adjust what you multiplay turnSpeed for how long you want him to stay spinning.
 turnSpeed *= 0.89f;

```

He should now speed up while turning, then when you release the turning keys on the keyboard he should spin a tiny bit then stop.
> 0 votes

---
Tags: xna, c#, rotation, monogame
---


title: PHP and Javascript/HTML5 Collaboration

text:
# Question
Title: PHP and Javascript/HTML5 Collaboration
I've recently been working on a fairly complicated game. I've stored information with local storage, but that allows the player to edit it, and does not transfer from computer to computer. The two scripts run on a single server, and I use the following to ping the php server:

```
function initiateLoginSequence() {
    var isnewplayer=prompt("Hello! Are you new?(Y/N)");
    if(isnewplayer.equalsIgnoreCase("N")) {
        var username = prompt("Enter username.");
        var password = prompt("Enter Password.");
        //parsing code goes here later.
    } else {
        var username = prompt("Enter a username. This will be used for future logins.");
        var password = prompt("Enter a password. This will be used for future logins.","*");
        var req = new XMLHttpRequest();
        req.open('POST', 'http://69.144.34.106/Scores.php', true);
        req.send("returning=false"+"&name="+username+"&pw="+password+"&level="+lvl+"&save=true");
        req.send();
    }
}

```

I then process the results with this:

```
<?php
   $returning=_POST["returning"];
   $save=_POST["save"]
   $password=_POST["pw"];
   $username=_POST["name"];
   $score=_POST["lvl"];
   $connection=mysql_connect("localhost:3306","****","*****");
   if($returning=="false" && $save=="true") {
     mysql_select_db("userdata",$connection);
     $sqlcmd = "CREATE TABLE ".$username."(
     Username varchar(".$username.")
     Password varchar(".$password.")
     Score varchar(".$score.")
     )";
     mysql_query($sqlcmd);
   } else if($save==false) {
     $sqlcmd="SELECT * FROM userdata"
     $result = mysql_query($sqlcmd);
     while($row=mysql_fetch_array($result)) {
        if($row['Username']==$username && $row['Password']) {
            echo row['Score'];
        }
     }
   } else if($save==true) {
     $sqlcmd="SELECT * FROM userdata"
     $result = mysql_query($sqlcmd);
     while($row=mysql_fetch_array($result)) {
        row['Username']=$username
        row['Password']=$Password
        row['Score']=$Score
     }
   }
?>

```

But after creating the mysql database, nothing is populated. So my basic question is, Am I doing this right? If not, what am I missing?

# Answer
Several points:

* You should definitely enable error reporting and error logging into a file on the PHP side, otherwise you'll have no evidence of problems. AJAX errors usually cause little visible error to the user.
* You should check for errors on the Javascript side too

PHP error handling is famous for being both bad (e.g. the default action for most unusual conditions is to continue regardless and issue a warning, which possibly goes to the client browser, or might be ignored as well), AND complicated. Once you fully understand PHP error handling, you can write an error handler which carries out appropriate actions in all cases.

In my opinion:

* Creating a table for each user is not a good database model (Consider a row per user instead)
* Hard-coding the server IP address in the Javascript code is almost certainly not the right thing to do (e.g, how do you move your application from your test to production server without changing it?)
* a PHP error handler should log all errors and report every possible piece of contexual information (especially a stack trace) into the error log, and stop execution; it is necessary to provide a mechanism for certain errors to be suppressed in some cases (for example, error\_reporting). Don't use the @ operator ever.

Security:

* You may wish to research what SQL injection is, before you continue to use PHP / MySQL in your application (Hint: Consider using parameterised queries)
> 6 votes

# Answer
It seems to me like you have a misconception about what's the meaning of a `TABLE` and whats the meaning of a `DATABASE` in SQL.

A database has many tables.

Each table can have multiple columns and entries ("rows").

The `SELECT` statement gets data from a table of the currently active database. You are trying to select from `userdata`, which is the name of your database, not from a table of your database.

Your `CREATE TABLE` command is semanitically wrong. When you create a table, you create the columns. The columns define how each entry in the table looks, but no data is inserted yet. This happens later with separate `INSERT INTO` commands. The values in parenthesis after varchar is the length of the fields of the column. For example, `username VARCHAR(20)` means that each entry in the table has a field username which is a variable-length string with a length of up to 20 characters.

Also, you generally create the tables once when you deploy the application. When the application is in use, you avoid adding or changing tables. When you have multiple users, you usually create one table `users` where each row represents one user. The columns you create in the CREATE TABLE command (which is usually not done with PHP code but with a GUI tool like PhpMyAdmin) describe what data is saved in each row.
> 0 votes

---
Tags: javascript, html5, client-server, php, scoring
---


# Question
Title: How attach a model with another model on a specific bone?
I meet a difficulty attached to a model to another model on a "bone" accurate. I searched several forums but no result. I saw that many people have asked the same question but no real result see no response. Thread found :

How to attach two XNA models together?

How can I attach a model to the bone of another model?

https://stackoverflow.com/questions/11391852/attach-model-xna

But I think it is possible.

Here is my code example attached a "object" of the hand of my player

```
private void draw_itemActionAttached(Model modelInUse)
    {
        Matrix[] Model1TransfoMatrix = new Matrix[this.player.Model.Bones.Count];
        this.player.Model.CopyAbsoluteBoneTransformsTo(Model1TransfoMatrix);
        foreach (ModelMesh mesh in modelInUse.Meshes)
        {
            foreach (BasicEffect effect in mesh.Effects)
            {
                Matrix model2Transform = Matrix.CreateScale(1f) * Matrix.CreateFromYawPitchRoll(0, 0, 0);

                effect.World = model2Transform * Model1TransfoMatrix[0]; //root bone index
                effect.View = arcadia.camera.View;
                effect.Projection = arcadia.camera.Projection;
            }
            mesh.Draw();
        }
    }

```

# Answer
> 2 votes
If you use this approach, you need to multiply the world matrix in the effect with the world matrix of the bone of model2:

```
private void draw_itemActionAttached(Model modelInUse)
{
    Matrix[] Model1TransfoMatrix = new Matrix[this.player.Model.Bones.Count];
    Matrix[] Model2TransfoMatrix = new Matrix[modelInUse.Bones.Count];
    this.player.Model.CopyAbsoluteBoneTransformsTo(Model1TransfoMatrix);
    modelInUse.CopyAbsoluteBoneTransformsTo(Model2TransfoMatrix);
    foreach (ModelMesh mesh in modelInUse.Meshes)
    {
        foreach (BasicEffect effect in mesh.Effects)
        {
            Matrix model2Transform = Matrix.CreateScale(1f) * Matrix.CreateFromYawPitchRoll(0, 0, 0);

            effect.World = Model1TransfoMatrix[0] * Model2TransfoMatrix[mesh.ParentBone.Index] * model2Transform;
            effect.View = arcadia.camera.View;
            effect.Projection = arcadia.camera.Projection;
        }
        mesh.Draw();
    }
}

```

Also you should multiply the matrices in this order to get the best results. If you want to save some time you also could remove the model2Transform matrix because it is the identity matrix and thus changes nothing but the time needed to multiply the matrices.

---
Tags: xna, models, matrix, mesh
---


# Question
Title: help using image to overlay grayscale around player
I'm sorry for the confusing title but it is hard to explain in one sentence.

This is what I have

What I want to do is use that black overlay to convert everything in the black area to grayscale. This will create a colored aura around the player.

Does this require pixel shading or is there a simpler method?

# Answer
> 1 votes
You'll need a (simple) shader.

Render the whole scene in color to an offscreen. Then run the whole output texture through a greyscale shader.

You can then run a pass using both textures as input along with the mask to select which source(s) to sample and how to mix them.

You could do it without the explicit greyscale pass, too. I think the extra pass makes it a bit easier, though.

Remember that color space is not linear, so a greyscale shader is not as easy as averaging the RGB components. See http://www.johndcook.com/blog/2009/08/24/algorithms-convert-color-grayscale/ for some help there.

# Answer
> 0 votes
For what I think you want to achieve, I think the simplest/best way is using shaders.

Modifying the pixels in a shader is much easier (and efficient) than having a dual set of assets, with the alpha map masking out the colored assets (or any other way of doing this that comes to mind). You could of course pre-process the assets to make them grayscaled, etc.

Now, I think the pay-off of using shaders and playing around with it might give you a lot of freedom to create interesting looking effects, without worrying much at all about how this affects your assets and structure.

Disclaimer: I haven't used xna, so I don't know how cumbersome it is to use shaders here.

# Answer
> 0 votes
I would recommend using the shader provided in this answer. Add another function and you should be able to convert everything to grayscale.

```
float4 PixelShader(VertexOut input) : COLOR0
{
    float4 color;
    color = tex2D(ColoredTextureSampler, input.textureCoordinates.xy);
    return dot(color, float3(0.3, 0.59, 0.11));
}

```

---
Tags: xna, c#, pixel, shading
---