# Question
Title: How can I build a graphical map for my MUD engine?
I am working on a text-based game totally from scratch and one thing I am not sure how to do is the map system.

In my mud engine totally writen in Javascript (that will be executed in a Node.js environment), I use that kind of data to design an area and the links between rooms.

```
/**
 *       [003]-[004]
 *         |     |
 * [001]-[002] [007]
 *         |     |
 *       [005]-[006]
 **/
var map = {
    "001" : {
        "Id" : "001",
        "Name" : "Room 001",
        "Directions" : {
            "N" : "",
            "S" : "",
            "E" : "002",
            "W" : ""
        }
    },
    "002" : {
        "Id" : "002",
        "Name" : "Room 002",
        "Directions" : {
            "N" : "003",
            "S" : "005",
            "E" : "",
            "W" : "001"
        }
    },
    "003" : {
        "Id" : "003",
        "Name" : "Room 003",
        "Directions" : {
            "N" : "",
            "S" : "002",
            "E" : "004",
            "W" : ""
        }
    },
    "004" : {
        "Id" : "004",
        "Name" : "Room 004",
        "Directions" : {
            "N" : "",
            "S" : "007",
            "E" : "",
            "W" : "003"
        }
    },
    "005" : {
        "Id" : "005",
        "Name" : "Room 005",
        "Directions" : {
            "N" : "002",
            "S" : "",
            "E" : "006",
            "W" : ""
        }
    },
    "006" : {
        "Id" : "006",
        "Name" : "Room 006",
        "Directions" : {
            "N" : "007",
            "S" : "",
            "E" : "",
            "W" : "005"
        }
    },
    "007" : {
        "Id" : "007",
        "Name" : "Room 007",
        "Directions" : {
            "N" : "004",
            "S" : "006",
            "E" : "",
            "W" : ""
        }
    }
};

```

On the MUD game I am actually playing, the mud command display something like this:

I would like to know in pseudo-code the way to do this in the most efficient way.

Please note that it has a maximum character length for each lines and that the map is centered around You (@).

Thank you for your help!

# Answer
> 4 votes
If your room layout is consistent enough (all connections are the same length and can be traversed in both directions, and no rooms overlap), this is a simple exercise in recursion. Here's a quick piece of code that should do it:

```
var offsets = {
    "N": [0, -1],
    "E": [+1, 0],
    "S": [0, +1],
    "W": [-1, 0]
};

// recursively plot the locations of the rooms on a grid:

function drawMap ( map, room, grid, x, y ) {
    var loc = x + "," + y;
    if ( loc in grid ) {
        if ( grid[loc] !== room ) {
            // inconsistency detected
        }
        return;
    }
    grid[loc] = room;

    if ( x < grid.minx ) grid.minx = x;
    if ( x > grid.maxx ) grid.maxx = x;
    if ( y < grid.miny ) grid.miny = y;
    if ( y > grid.maxy ) grid.maxy = y;

    var neighbors = map[room].Directions;
    for ( dir in neighbors ) {
        if ( dir in offsets && neighbors[dir] !== "" ) {
            var off = offsets[dir];
            drawMap( map, neighbors[dir], grid, x + off[0], y + off[1] );
        }
        // else handle unknown direction
    }
}

var grid = { "minx" : 0, "maxx" : 0, "miny" : 0, "maxy" : 0 };
drawMap( map, "001", grid, 0, 0 );

// draw the grid in pretty ASCII art:

var mapString = "";
for ( var y = grid.miny; y <= grid.maxy; y++ ) {
    var line1 = "";
    var line2 = "";
    for ( var x = grid.minx; x <= grid.maxx; x++ ) {
        var loc = x + "," + y;
        if ( loc in grid ) {
            var neighbors = map[ grid[loc] ].Directions;
            line1 += ( neighbors.E !== "" ? "+-" : "+ " );
            line2 += ( neighbors.S !== "" ? "| " : "  " );
        } else {
            line1 += "  ";
            line2 += "  ";
        }
    }
    mapString += line1 + "\n" + line2 + "\n";
}

// document.write( "<pre>" + mapString + "</pre>" );

```

Some possible improvements left as exercises include:

* Drawing different rooms and connections differently, and generally making the output fancier.
* Support for diagonal connections.
* Handling one-way connections correctly.
* Allowing variable (integer) connection lengths.
* Detecting situations where a room seems to appear more than once on the map (e.g. where a room is connect to itself), which can cause the code above to recurse forever. (This is fairly easy, just maintain a separate list of mapped rooms.)
* Automatically resolving situations where two rooms seem to appear in the same location (e.g. where going S,E,N,W gets you into a room other than the one you started in).

The last exercise is a difficult one, since it potentially gets you all the way into the complex realm of arbitrary graph layout algorithms.

---
Tags: maps, mud
---


# Question
Title: What can I do to render generated 2D terrain in XNA?
I am working on a smooth terrain generation algorithm in C# and using XNA to display the data.

I am making it so it creates a new point halfway between each point per iteration, at a random height between the two. This works OK, and I am getting the current result, randomly placed points.

Now what I want to do is turn these points into a primitive (I think that is what it is) and display it like a mountain, obviously using a mountain texture. Example below (using different point data, made up in paint)

Any help or tips are greatly appreciated, and look forward to your responses.

# Answer
> 8 votes
In addition to Blau's answer you could also generate a `VertexBuffer`. What you would do is something like:

```
// Create the arrays to hold the data.
var vertices = new VertexPositionColorTexture[_points.Length * 2];
var indicies = new short[6 * (_points.Length - 1)];

for (var i = 0; i < _points.Length; i++)
{
    var pt = _points[i];

    // Calculate the texture coordinate along the horizontal plane.
    var u = (float)_points.Length / i;

    var vertexIndex = i * 2;
    // Create the vertex at the top of the landscape
    // that is at the current X co-ordinate.
    vertices[vertexIndex + 0] = new VertexPositionColorTexture(
            new Vector3(pt.X, pt.Y, 0),
            Color.White,
            new Vector2(u, 0)
        );
    // And the bottom.
    vertices[vertexIndex + 1] = new VertexPositionColorTexture(
            new Vector3(pt.X, _height, 0),
            Color.White,
            new Vector2(u, 1)
        );

    // Create indicies that will make two triangles that
    // fill the *right* of the current vertex.
    if (i < _points.Length - 1)
    {
        var indexIndex = i * 6;
        indicies[indexIndex + 0] = (short)(vertexIndex + 0); // Top left
        indicies[indexIndex + 1] = (short)(vertexIndex + 1); // Bottom left
        indicies[indexIndex + 2] = (short)(vertexIndex + 3); // Bottom right

        indicies[indexIndex + 3] = (short)(vertexIndex + 0); // Top left
        indicies[indexIndex + 4] = (short)(vertexIndex + 3); // Bottom right
        indicies[indexIndex + 5] = (short)(vertexIndex + 2); // Top right
    }
}

_vertexBuffer = new VertexBuffer(GraphicsDevice, typeof(VertexPositionColorTexture), vertices.Length, BufferUsage.WriteOnly);
_indexBuffer = new IndexBuffer(GraphicsDevice, IndexElementSize.SixteenBits, indicies.Length, BufferUsage.WriteOnly);

_vertexBuffer.SetData(vertices, 0, vertices.Length);
_indexBuffer.SetData(indicies, 0, indicies.Length);

// To draw:
GraphicsDevice.Indices = _indexBuffer;
GraphicsDevice.SetVertexBuffer(_vertexBuffer);
_basicEffect.Texture = _myTexture; // Your texture
_basicEffect.World = _worldMatrix;
foreach (var item in _basicEffect.CurrentTechnique.Passes)
{
    item.Apply();
    GraphicsDevice.DrawIndexedPrimitives(PrimitiveType.TriangleList, 0, 0, _vertexBuffer.VertexCount, 0, _indexBuffer.IndexCount);
}

```

This should create a vertex buffer that looks like this:

You should read up on BasicEffect if you want to learn how to set up textures during your rendering.

# Answer
> 7 votes
You can create a Texture2D this way.

```
        Texture2D Mountain = new Texture2D( GraphicsDevice, Width, Height);
        Color[] PixelData = new Color[Width * Height];

        Color colA,colB;
        float r;
        for ( int x=0; x < Width && x < YourHeights.Length; x++ )
        {
            for ( int y=YourHeights[x]; y < Height; y++ )
            {
                // This is for colorize relative to height
                // You can change or apply other texture
                if (y<Height/3) {
                    colB = Color.IndianRed;
                    colA = Color.White;
                    r = 1.0f - y / (Height/3.0f);
                }
                else if (y<2*Height/3) {
                    colB = Color.Indigo;
                    colA = Color.IndianRed;
                    r = 1.0f - (y-Height/3.0f) / (Height/3.0f);
                } else {
                    colB = Color.RosyBrown;
                    colA = Color.Indigo;
                    r = 1.0f - (y-2*Height/3.0f) / (Height/3.0f);
                }

                PixelData[x + y * Width] = Color.Lerp( colB, colA, r );
            }
        }
        Mountain.SetData<Color>( PixelData );

```

Maybe you need to build more textures if your level is too long... or you can modify the texture scrolling it and adding new columns of pixels in the scroll side.

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


# Question
Title: How should I handle different aspect ratios in a fullscreen game?
I am creating a game using C#, GDI+ and Raster images (2D images). For performance sake, I believe that I should have the game change the user's resolution to 800 x 600 and run the game in that setting. However, the graphics look distorted in a wide screen since the aspect ratio for 800 x 600 is different than from a wide screen. I cannot figure out how to determine the aspect ratio.

How is game programming normally handled on different resolutions? Should I even change the user's resolution? If I dont change the resolution, the game slows down a lot.

Also, some wide screens will "maintain the aspect ratio" when changing the resolution to 800 x 600 (thus creating black bars on the right and left) and some wide screens will fill up the entire screen. How do people handle that situation??

# Answer
> 3 votes
In your current situation I would advice to get device resolution that is most similar to your planned resolution or slightly bigger than it (800x600 -\> 1024x720) and deal with it manually. Add black areas on sides or some artistic patterns that complement your game.

As already said GDI+ is not a common approach to 2D game nowadays, but the general principle of dealing with various screen aspects still stands.

---
Tags: c#
---


# Question
Title: What use for a 3d browser based multiplayer online game?
Can you help me choosing the right tools for this project? It's a 3d browser based multiplayer online fighting game. A few 3d functions are necessary for positioning, but no heavy rendering will happen. It needs very low ping rates, though, as it will be very dynamic. HTML5 + three.js + some networking lib seems like a fair choice, but I'm concerned about performance and cross-browserism. It's for learning purposes but I can use it for professional showoff. Thoughts?

# Answer
Ping rates aren't dependent on the library you use at all. They're going to be dependent on your network. I know you probably just meant that you want low latency, but it helps to get the terms right. :)

You really have only a few options. WebSocket gives the best integration and performance, but is not supported on all browsers yet, and the spec still isn't finalized iirc. Flash can be used everywhere and offers slightly more flexibility in choice of protocol and browser compatibility but the JavaScript-Flash bridge can be a serious performance bottleneck on most browsers in my experience.

If you don't need IE support right now, I would lean towards WebSocket. It does what you need for an MMO just fine. http://www.websocket.org/

If you need IE support, there are wrapper libraries that emulate WebSocket using Flash. https://github.com/gimite/web-socket-js

You can also use the HTML5Labs IE prototype for WebSockets if you don't need any "regular" users on IE to run your game today. http://html5labs.interoperabilitybridges.com/prototypes/websockets/websockets/info
> 4 votes

# Answer
For the networking library, I would look at Socket.IO. It uses WebSockets (when possible) but, as seanmiddleditch mentioned, falls back on Flash (or something) for IE. Your server will use Node.js if you choose to use Socket.IO, which is a great choice in my opinion. For hosting, you can refer to the Stack Overflow question "Where can I host a Node.js app?"

As for graphics on the client, three.js looks awesome and it's on my todo list to play with, so I agree with that choice.
> 2 votes

---
Tags: 3d, networking, mmo, tools, browser-based-games
---


# Question
Title: How do I make magenta in my PNG transparent in HTML5/Canvas/JS?
I'm putting together a simple hex map to use within an HTML5 / Canvas / JS game and before I get round to sorting any custom graphics, I was wondering if anybody knew how to make the pink/magenta backgrounds transparent so that I can overlap my tiles?

Cheers!

# Answer
> 9 votes
As thedaian mentioned in his comment, converting the magenta pixels to transparent in JavaScript is going to be slow. You should convert your images to a suitable format beforehand.

ImageMagick can be really useful for this kind of tasks. Converting your tile with magenta background to an image with transparency is as simple as this:

```
convert myOpaqueTile.png -transparent "#FF00FF" myTransparentTile.png

```

This will convert your file with magenta background (`myOpaqueTile.png`) to a file with a transparent background (will be saved as `myTransparentTile.png`).

Of course you could also use Photoshop, GIMP or something like Paint.NET for this.

---

**Update:** If you want to do the whole thing in code (JavaScript), then look into the `getImageData` function of the HTML5 canvas element. Here's an article about canvas image manipulation.

And here's some sample code that will convert magenta pixels to transparent ones in JavaScript:

```
// source file to load
var file = "testData.png";

// color to make transparent. Magenta here...
var transparentColor = {
    r : 255,
    g : 0,
    b : 255
};

var img = new Image();
img.src = file;
img.onload = function(){
    // create a source canvas. This is our pixel source
    var srcCanvas = document.createElement("canvas");
    srcCanvas.width = img.width;
    srcCanvas.height = img.height;

    // create a destination canvas. Here the altered image will be placed
    var dstCanvas = document.createElement("canvas");
    dstCanvas.width = img.width;
    dstCanvas.height = img.height;

    // append the canvas elements to the container
    document.getElementById('container').appendChild(srcCanvas);
    document.getElementById('container').appendChild(dstCanvas);

    // get context to work with
    var srcContext = srcCanvas.getContext("2d");
    var dstContext = dstCanvas.getContext("2d");

    // draw the loaded image on the source canvas
    srcContext.drawImage(img, 0, 0);

    // read pixels from source
    var pixels = srcContext.getImageData(0, 0, img.width, img.height);

    // iterate through pixel data (1 pixels consists of 4 ints in the array)
    for(var i = 0, len = pixels.data.length; i < len; i += 4){
        var r = pixels.data[i];
        var g = pixels.data[i+1];
        var b = pixels.data[i+2];

        // if the pixel matches our transparent color, set alpha to 0
        if(r == transparentColor.r && g == transparentColor.g && b == transparentColor.b){
            pixels.data[i+3] = 0;
        }
    }

    // write pixel data to destination context
    dstContext.putImageData(pixels,0,0);
}

```

---
Tags: tiles, html-canvas, transparency
---


# Question
Title: What is a CPU-efficient cloth simulation technique for a 2D game?
Are there techniques for simulation of cloth and hair in an efficient (in other words, not too CPU-intensive) manner? I only need to calculate the key points as the drawing will be done in 2D.

# Answer
Verlet integration is relatively lightweight, and can be scaled easily by adjusting the number of total particles present in the cloth (so you can scale the simulation from a very smooth, 10,000 particle scenario to one that only uses nine "key" particles or so). The quality and verisimilitude of the simulation will suffer as you scale the system down, however.

The Jacobson article on Gamasutra discusses Verlet physics from a very basic perspective and builds upon that (he focuses on character physics, but the technique is applicable to cloth as well). Alternatively, here's a blog post (and a follow-up) on building cloth simulations with Verlet integration. You can find plenty of other resources using Google should you need further information (for example, this article, this collection of sample OpenGL implementations, et cetera).

The technique can be applied to hair as well, and you can similar scale it in that context -- you can either use several sets of "strands" of connected particles to simulate bands of hair, or simply treat it like cloth directly (with an appropriate, more hair-like texture).

If you have a GPU available, you could also look at offloading some of the computation on to the GPU to free up the CPU for other tasks; depending on the task balance in your game already, this may or may not be a feasible optimization for the CPU.
> 2 votes

---
Tags: 3d, physics, graphics
---


# Question
Title: How should I model exact 90-degree rotations in 3D?
I'm familiar with quaternions... have used them in the past to model arbitrary rotations in 3D, as for a plane flying around with full pitch/yaw/roll freedom. Works great.

Now I'm working on a 3D puzzle where the rotation is "quantized": all rotations are whole multiples of 90 degrees. I could use quaternions, but it seems like complexity overkill for this situation. And more importantly, I need to be able to test different orientations according to their quantized values, aligned to the three main axes. Quaternions (usually) use floating point values rather than integers, so if we compose several rotations and then compare the resulting orientation to a known orientation, it may not be straightforward to test whether a certain face is pointing a given direction, due to rounding.

Anyway, there may be an easier way to model this.

The puzzle is like "netwalk", but in 3D. So the requirements are:

* Be able to rotate a given piece +/-90 degrees, around a specified axis, updating its orientation state (which is modeled how?)
* Be able to query whether a particular piece, in its current orientation, is *connected* in a particular direction (e.g. has a tube touching the face that is in the positive X direction)
* For the latter we probably have an array of booleans that say whether the piece is *connected* in each direction in its "initial" orientation. But in order to make use of this, we need a way to rotate this initial state to the current orientation.
* Oh, we also need to be able to *display* each piece graphically in its updated orientation. But that could use a separate orientation state if necessary... it's a pretty standard feature of scene graph libraries.

Maybe I just need to implement an integer version of quaternions?

Thanks for any thoughts...

# Answer
The solution I'm leaning toward is this...

For the puzzle logic, I will have for each cell (or piece) an array of 6 directions, storing a boolean value isConnected.

When initializing a cell, this boolean array is initialized from the array for the archetype of the shape being placed in the call.

Whenever a given piece is rotated, I call a function `rotateFaces(rotation)` that permutes these 6 boolean face values according to whether `rotation` is `'+x'`, `'-x'`, `'+y'`, etc. Based on the axis it selects a sequence of four directions. Then the selected sequence is used to permute four of the six values in the array. E.g. if the rotation is `'+x'`, then the sequence of directions to permute are `+y, +z, -y, -z`. So the boolean value for `+y` is shifted to `+z`, and so on in a cycle.

To query whether a piece is *connected* in a given direction in its current orientation, we just query the boolean array for that direction.

That way I can avoid any floating point rounding issues, the math is all fairly simple, and the query (which will happen very often) is quick.

The graphic display of the pieces will most likely be handled separately via the scene graph library. I may see if I can "round" their orientation to be axis-aligned after each move is completed.
> 0 votes

# Answer
Frankly, I would continue to use quaternions if you are already using them and comfortable with them. It doesn't seem to me like it's worthwhile to build out a whole system -- if even it's a small one -- to handle fixed sets of rotations when you can simply do that on top of a system that handles arbitrary ones.

Furthermore, you can address the floating point issue by comparing with epsilon values -- that is, test if components are equal within a small tolerance. This is the general technique for comparing floating point values.

*However*, all that aside, you shouldn't be conflating game logic and render state by comparing the orientation quaternions of your render objects to decide where a particular game piece is facing. It is better to divorce the states and operations of the two domains as much as possible:

You could simply have an enumeration of possible orientations of your pieces (facing +Z, -Z, +X, -X, +Y, -Y). This alleviates most of your concerns, although you'd probably want a mapping of potential target rotations from any given rotation enumeration value, since you wouldn't have "real math" to work with any longer.

It would allow you to query for connectivity relatively easily since you could simply get the set of surrounding pieces in a fixed order that corresponded to the ordering of the enumeration, and then plug the piece's current orientation in to that result array to see which piece was in that direction (if any; you'd always have to return an array of the same size so you'd want to pad with null or empty values when there was no piece around).

When it's time to display a piece, you can trivially construct the orientation quaternion for the particular orientation enumeration and send that to the render subsystem.
> 5 votes

# Answer
There are only 24 possible orientations achievable by 90° rotations around coordinate axis, which form the rotation group of a cube, also known as the chiral octahedral symmetry group. Since there are only 24 elements, you could easily build a multiplication table for them. (In fact, you only need a 24 × 6 table, since only 6 of the elements are 90° rotations.)

The elements of the rotation group can also be naturally represented by 3×3 transformation matrices — in particular, those 3×3 matrices which:

* contain only the values -1, 0 and 1,
* have exactly one non-zero value in each row and each column, and
* have their determinant equal to 1 (rather than -1).

Among these matrices, the 90° rotations are those which swap two coordinate axes while negating one of them, i.e. those that have a single 1 on the diagonal and one 1 and one -1 off the diagonal.

This matrix representation allows you to use straightforward matrix multiplication to combine rotations, *and* to apply those rotations to point coordinates. Since all the elements of the matrices are integers, you don't need to worry about rounding errors.
> 3 votes

---
Tags: 3d, rotation, quaternion
---


# Question
Title: How does one get adjacency information in a geometry shader?
If you use triangle\_adjacency as the input type of a geometry shader, do you need to do something on the client side besides make the primitive mode triangle\_adjacency?

Basically what I'm asking do you need to do anything in your application to make the adjacency information available to the geometry shader besides setting the primitive mode in your draw commands?

# Answer
> 5 votes
Yes. You need to provide the adjacent vertices in the index buffer; they are not generated for you. See this article for the details.

---
Tags: opengl, glsl
---


# Question
Title: Resources about movement and simulation in multiplayer games
I am developing a multiplayer game, similar to Castle Crashers. This is the first multiplayer game I do so, before starting to code, I am trying to learn what's the best way to do it. I found some documents explaining how some old FPS (Half Life, Quake) work but I can't found anything newer or more similar to the game I am creating.

Do you know any resources to articles about this topic?

# Answer
> 2 votes
I start posting the links I found:

# Answer
> 0 votes
I watched this a couple of months ago.

http://www.gdcvault.com/play/1014345/I-Shot-You-First-Networking

It's a pretty interesting talk about syncing states in a networked environment.

---
Tags: networking, multiplayer, simulations, synchronization
---


# Question
Title: How can I achieve smooth animation of sprites between discrete tiles?
I'm currently learning game development with C# and XNA and my current assignment is to create a Pac-Man clone.

The game is partially tile based, which means that the level itself is built out of an array of tiles, but Pac-Man and the ghost just have a position to be drawn at. I've got the basic functionality down, such as building the level with a string and drawing Pac-Man and the ghost on the screen.

Pac-Man is currently represented by two positions: one is where he is in relation to the array of tiles (a Point, for example 9, 11), and one where the sprite is drawn (which is a Vector2). However, when trying to make the player be able to move Pac-Man (and Pac-Man is supposed to "glide" between tiles, not jump between them) it seems that his graphical position can not keep up with his tile position. It sort of lags behind.

This is hard to describe but here's some code to look over:

```
public PacMan(): base()
    {
        texture = Game1.pacManTexture;
        tilePosition = new Point(9, 11);
        position = new Vector2(tilePosition.X * spriteSize.X, tilePosition.Y * spriteSize.Y);

```

That is the constructor for Pac-Man.

```
else if (tileManager.playArea[tilePosition.X, tilePosition.Y - 1] is Tile) // if the  tile above Pac-Man is of the type Tile...
                {
                    tilePosition.Y -= 1; // decrement tilePosition by 1
                }

```

That is what happens if the player presses the Up key.

```
Vector2 tilePos = new Vector2(tilePosition.X * spriteSize.X, tilePosition.Y * spriteSize.Y);
        Vector2 direction = tilePos - position;
        if (direction.Length() != 0)
            direction.Normalize();
        position += direction;

```

And that is where the faulty magic happens. The graphical position of Pac-Man (the sprite) is being updated.

```
Rectangle pacManRectangle = new Rectangle((int)position.X, (int)position.Y, spriteSize.X, spriteSize.Y);
        Game1.spriteBatch.Draw(texture, pacManRectangle, new Rectangle(currentFrame.X * spriteSize.X, currentFrame.Y * spriteSize.Y, spriteSize.X, spriteSize.Y), Color.White);

```

And lastly, that happens in the Draw method.

If you need more information, just say so.

# Answer
I'm still somewhat new on the XNA scene myself, but I assume if your game is tile based you know the exact points (probably the center of the tiles) that pac-man needs to move to. There is probably some wild vector math you could do to calculate pac-man's speed so that he moves a little bit per update and arrives *perfectly* at said point, but you might settle on something like this:

```
position += speed * direction * elapsedGameTime;

```

This will set your pac-man sprite into motion and have it headed towards the point you want it to be at, at the speed (a float you can adjust?) you want him to walk, or roll, or whatever he does. Each update, you could then check pac-man's position.X and position.Y VS your point.X and point.Y. Once pac-man is going to go beyond that point, set his position directly to the point coordinates. You should probably do this position vs point check so that if pac-man has gone beyond the point, that the position is updated to the point coordinates before your Draw method (else Pac-man might appear to "jump back" a bit).
> 0 votes

# Answer
You probably just want to MathHelper.Lerp two Vector2 values. One value is the original tile, the other is the destination tile. The LERP float (last parameter) will be: (CurrentTime - TimeMovementStarted) / TimeToMoveBetweenTiles

Or, if you move according to deltas, you can set CurrentTime = 0 when the movement starts, then add the delta in each UPDATE according to the UPDATE gameTime. The equation becomes (since we zeroed to start): CurrentTime / TimeToMoveBetweenTiles.

After TimeToMoveBetweenTiles elapses, it's time to check player input again to see which square to go to now. (Or check more often if you want to be able to turn around - though if you do implement turn around, you need to know you're turning around and start subtracting from "CurrenTime" until it gets back to 0)

Note that you still should check the ACTUAL distance between an evil ghost and the player pacman as you don't want a ghost "eating" pacman just because it entered a square pacman is still leaving but mostly already out of (being chased closely).
> 0 votes

---
Tags: xna, c#, tiles
---


# Question
Title: Compress the variance in a set of numbers?
I'm not sure if there's a better way to ask that, but I have a hovercraft which hovers by imparting force at each of four corners. I'd like to clamp the maximum variance between the thrusters so if one corner hovers over something higher altitude, the effect is less dramatic.

For example, if I had 4-6-8-10, I might want it to compress to 4-5-6-7.

# Answer
> 3 votes
I would actually recommend normalizing towards the mean (average) rather than the lowest value.

```
base_values = {4, 6, 8, 10};

double ave = average(base_values); // ave is equal to 7

for(int i = 0; i < base_values.len; i++)
{
    base_values[i] = base_values[i] - (abs(ave - base_values[i]) / 2);
}

```

`abs(...)` is the absolute value function.

That will make going down jagged terrain look good, as well as going up.

# Answer
> 1 votes
From what you posted I see a pattern you could use. Here is some psudocode

```
values = {4,6,8,10}

lowest = 100 //or some other imposible high number
for each int in values {
 if int < lowest then lowest = int
}

for each int in values {
 value = value -((lowest-value)/2)
}

```

---
Tags: mathematics
---


# Question
Title: Looking for the reference tutorials for the joints in the Box2D for iphone
I can't find the tutorials of joints class in the Box2D for iPhone. I am unable to run a Testbed for iPhone Box2D.

```
(void)ccTouchesBegan:(NSSet *)touches withEvent:(UIEvent *)event
{
       if (_mouseJoint!=NULL)return;
       UITouch *mytouch=[touches anyObject];
       CGPoint location=[mytouch locationInView:[mytouch view]];
       location=[[CCDirector sharedDirector]convertToGL:location];
        b2Vec2 locationWorld=b2Vec2(location.x/PTM_RATIO,location.y/PTM_RATIO);
 //ristrict the player within the ground limit  keep stucking the player with grounditself.....
if (_playerFixture->TestPoint(locationWorld))
{
    b2MouseJointDef md;
    md.bodyA=groundBody;
    md.bodyB=_playerBody;
    md.target=locationWorld;
    md.collideConnected=true;
    md.maxForce=100.0f*_playerBody->GetMass();
    _mouseJoint=(b2MouseJoint *)_world->CreateJoint(&md);
    _playerBody->SetAwake(true);
}
}

-(void)ccTouchesMoved:(NSSet *)touches withEvent:(UIEvent *)event
{
if (_mouseJoint == NULL) return;
UITouch *myTouch = [touches anyObject];
CGPoint location = [myTouch locationInView:[myTouch view]];
location = [[CCDirector sharedDirector] convertToGL:location];
if (location.y<240.00&&location.y>=20.0f)
{
    b2Vec2 locationWorld = b2Vec2(location.x/PTM_RATIO, location.y/PTM_RATIO);
    _mouseJoint->SetTarget(locationWorld);
}
}

- (void)ccTouchesEnded:(NSSet *)touches withEvent:(UIEvent *)event
{
if (_mouseJoint)
{

 _world->DestroyJoint(_mouseJoint);
    _mouseJoint = NULL;

  }

}

```

# Answer
Emanuele Feronato has some great joint tutorials for box2d. The tutorials are in Actionscript 3, but the basic principles are the same.

BTW, the as3 port of box2d sticks pretty closely to the naming convention of the original c++ box2d, so you'll just have to change syntax a bit to use it on the iPhone.

http://www.emanueleferonato.com/category/box2d/
> 1 votes

# Answer
Some joint tutorials here: http://www.iforce2d.net/b2dtut/joints-overview
> 1 votes

---
Tags: iphone, box2d, cocos2d-iphone, physics-engine
---


# Question
Title: Box2D Raycast - Getting position / angle of edge hit
I'm casting a ray in Box2D using b2World.rayCast how can I get the normal of the wall which was hit? Or better yet - the line start and end points?

The information returned is: **Fixture** (fixture hit, and parent body)
**Point** ( Location of hit )
**Normal** (Normal pointing at new direction of ray - not the normal of the edge hit)
**Fraction** (0.0 - 1.0) of the point location along the array

However lets say I wanted to place something along the edge hit, previously I just iterated through the segments and did a line intersection test. However if the body is rotated this does not work.

How can I retrieve the line/edge information for the edge the ray hits with. For example, if i wanted to place texture along the wall or some kind of decal.

# Answer
> 2 votes
Here's what I ended up doing incase anyone else stumbled onto this.
This implementation will only work on rectangular shapes. Since those are stored in the same order in the shape every time. Im sure there's a way to figure out what the vertices map to in a custom shape though as well, but I don't know it.

After you perform the raycast, and retrieve the fixture information from box2d, perform your own a line-segment hit test on each of the edges in the fixture, first rotate the lines by the angle of the b2Body.

To perform this raytest, create a linesegment represented from your player to the point recieved from the raycast. If you like you can extrapolate it a tiny tiny bit more, just to make sure it connects.

Create 4 line segments from the fixture such that:

```
     /**
         * Creates a linesegment between points A and B and offsets them by a point
         * @param offset
         * @param a
         * @param b
         */
        FROM_VECTORS_AND_OFFSET: function( offset, a, b ) {
            var pointA = new b2Vec2(offset.x + a.x, offset.y + a.y);
            var pointB = new b2Vec2(offset.x + b.x, offset.y + b.y);
            return new LineSegment(pointA, pointB);
        },

        /**
         * Creates an array lines from a b2Body
         * @param {Box2D.Dynamics.b2Body} aBody
         * @return {Array} An array of lines
         */
        FROM_BODY: function( aBody ) {
            var bodyPos = aBody.GetPosition();
            var shape = aBody.GetFixtureList().GetShape();

            var lineA = FROM_VECTORS_AND_OFFSET( bodyPos, shape.m_vertices[0], shape.m_vertices[1] );
            var lineB = FROM_VECTORS_AND_OFFSET( bodyPos, shape.m_vertices[1], shape.m_vertices[2] );
            var lineC = FROM_VECTORS_AND_OFFSET( bodyPos, shape.m_vertices[2], shape.m_vertices[3] );
            var lineD = FROM_VECTORS_AND_OFFSET( bodyPos, shape.m_vertices[3], shape.m_vertices[0] );

            return [lineA, lineB, lineC, lineD];
        },

```

Rotate each line by the angle of the body such that:

```
rotateLinesegment: function(pointA, pointB, angle) {

    // Find the mid-point between A and B - i make a copy of pointA just to be safe
    var center = pointA.Copy();
    center.Add( pointB );
    center.Multiply( 0.5 );

    var na = pointA.Copy();
    na.Subtract(center);

    var nb = pointB.Copy();
    nb.Subtract(center);

    // Rotate each component in the vector by angle
    var rotateVector = function( v, angle ) {
        var s = Math.sin(angle);
        var c = Math.cos(angle);

        var nx = c * v.x - s * v.y;
        var ny = s * v.x + c * v.y;

        v.x = nx;
        v.y = ny;
    };

    // Rotate, then untranslate it back to center
    rotateVector(na, angle);
    na.Add( center );

    // Rotate, then untranslate it back to center
    rotateVector(nb, angle);
    nb.Add( center );

    pointA = na;
    pointB = nb;

    return {pointA: pointA, pointB: pointB}
}

```

Perform a line-line intersection on each line.

```
/**
* Intersects two lines
* @param line1
* @param line2
* @return Array of points where the lines intersect
*/
INTERSECT_LINES: function( line1, line2 ) {
    function intersectLineLine(a1, a2, b1, b2) {
        var result = [];
        var ua_t = (b2.x - b1.x) * (a1.y - b1.y) - (b2.y - b1.y) * (a1.x - b1.x);
        var ub_t = (a2.x - a1.x) * (a1.y - b1.y) - (a2.y - a1.y) * (a1.x - b1.x);
        var u_b = (b2.y - b1.y) * (a2.x - a1.x) - (b2.x - b1.x) * (a2.y - a1.y);

        if (u_b != 0) {
            var ua = ua_t / u_b;
            var ub = ub_t / u_b;

            // See if T is between 0.0 - 1.0
            if (0 <= ua && ua <= 1 && 0 <= ub && ub <= 1) {
                var x = a1.x + ua * (a2.x - a1.x);
                var y = a1.y + ua * (a2.y - a1.y);
                var point = new Box2D.Common.Math.b2Vec2(x, y);
                result.push(point);
            } else { // Lines are coincident... count anyway?

            }
        } else {
        }
        return result;
}

return intersectLineLine(line1._a, line1._b, line2._a, line2._b);
}

     // Somewhere after creating the lines in the raycast call
 for(var i = 0; i < lines.length; i++) {
    var aLine = lines[i];
    aLine.rotate( otherBody.GetAngle() );
    var result = INTERSECT_LINES( playerToTracer, aLine );
    if(result) {
        contactLine = aLine
    }
}

```

After all these steps, you will have the information about which line you collided with in the fixture.

# Answer
> 2 votes
Firstly, the normal returned by the raycast should in fact be the normal of the fixture hit, at the point it was hit - maybe something is going wrong if this is not the case.

If you just want to attach something to the fixture that was hit, at the correct location and orientation, you should be able to do it like this:

```
b2Fixture* hitFixture; //from raycast result
b2Vec2 hitPoint, hitNormal; //from raycast result

b2Vec2 bodyCoordOfHitPoint = hitFixture->GetBody()->GetLocalPoint( hitPoint );
b2Vec2 bodyCoordOfHitNormal = hitFixture->GetBody()->GetLocalVector( hitNormal );

```

Thereafter you can draw the decal using this body coord position, transformed by the current body transform. This would be enough if you just want to display something 'stuck onto' the fixture like you mentioned in the first post.

However if you really need to know which edge of the fixture was hit for some reason, then yeah you will need to do something more, like what you did. Since the raycast already knows which side of the polygon was hit, you could probably alter the Box2D source code to pass this back as part of the raycast results if you were concerned about efficiency.

---
Tags: box2d
---


# Question
Title: Why won't this ClanLib "Hello World" project build in Eclipse CDT?
I've been trying to get a simple Hello World working with ClanLib using CDT (Eclipse), but I'm just not getting it configured properly.

First, from the command line, I'm able to get it to run using this command:

```
g++ -o mygame mygame.cpp `pkg-config --cflags --libs clanCore-2.3 clanDisplay-2.3 clanGL-2.3 clanGL1-2.3 clanApp-2.3` -lpthread

```

So no problems there.

Anyways, I tried setting up the correct build settings in Eclipse, but I just don't know where I'm supposed to add the info for the libraries. I tried adding it in the linker section, that didn't work. I tried a bunch of other things, nothing seemed to work...

Help would be appreciated, possibly as comprehensive as possible... I'm open to alternatives to Eclipse too. And the only reason this is such a problem is because this is the first time I'm trying to start a bigger C++ project, and I decided perhaps it's best to use some tools to make it a little easier, rather than a basic text editor (especially for debugging).

Oh, and I'm running Ubuntu, if that makes a difference. I'm really surprised there aren't any tutorials for setting up ClanLib in a development environment as popular as Eclipse...

# Answer
There are two places you need to do this to be sure that things will work, both of them are under Project-\>Properties-\>C/C++ Build-\>Settings-\>(MinGW) C++ Linker (assuming you're using MinGW):

1. -\>Libraries: add name of each lib you need *without* `-l`.
2. -\>Miscellaneous-\>Linker flags: add name of each lib you need in this textfield *with* `-l` prepended in every instance.

And of course under Libraries, make sure you have set up your library search paths (usually "`yourlib/lib`" -- I would use absolute paths here, and make sure they're enclosed in double quotes.

PS. Check the Console window to see what Eclipse is outputting for the `g++` command.
> 1 votes

---
Tags: c++, eclipse
---


# Question
Title: What structure is best used to model maps for games like Bard's Tale / Dungeon Hack?
I would like to create or use an existing JavaScript engine to build a game in the spirit of Dungeon Hack, Eye of the Beholder and older Might & Magic games. Going off my memory playing these games there could be 6 different bitmaps to each cube, and each side may have an additional decoration or other game object overlay.

How should I model these maps in code?

# Answer
* Start off with a 2D array filled with nulls
* For a walkable space, put a Space object into that tile slot which can hold objects lying about.
* For a visible wall (at all visible from any direction), put a Features object into that tile slot.
* Else tile remains null if it is deep in solid rock (unused).
* Check players facing, and walk a sequence of tiles in front of them, from back to front, looking at each tile (Space or Features) and rendering that feature or space at the correct scale as you go. Do the same for 1-2 parallel rows of tiles to either side of the central one -- this will give you a broader field of view. (IIRC EoB and MM had 5 total, so 2 to either side). Obviously do nothing for null tiles.

Space objects will hold various sets (8-12, usually) of object piles: 2-3 for each side of the space tile, with one shared between adjacent sides, see EoB, Dungeon Master, Captive, Knightmare for objects lying on floors.

Features objects will hold 4 Facets and a Mountable object or two, per facet (torches, plaques, or sewer grates :)

The nice thing is that because you're using JS, you can use the same empty slots in the grid for either one of the two types of objects, since JS just sees all as Object anyway. Then you'll need to use hasOwnProperty to know whether you're looking at Space or Features, per tile.

PS. Capitalised names are just my descriptors for them, they are not intended as typenames, since JS doesn't care.
> 5 votes

---
Tags: architecture, javascript, maps
---


# Question
Title: What is a good file format for saving game data?
I need to save some custom game data. Map, player, etc.

All of them will have "sub objects". For example, a map and map will have an "array" of tiles. ie, hierarchical data. Hopefully nothing binary.

What would be a good format for these?

So far I'ved considered:

**Serailization:** This is FAST and easy, but tends to break when I change the underlying classes :(

**XML:** I really hate parsing this. My test case was over 100+ lines of code and seemed likes tons of "busy work" for even a very simple format.

**INI:** would be really clumsy for hierarchical data.

**Protobuf:** Never used it, but read you have to do a lot of manual mucking around and breaks if you change the class.

**Other options?** That's why I'm here!

Edit: this is Java btw.

Edit 2:

I settled on "Controlled Binary Serialization" (see below).

Pros:

* it's fast
* it's small (on disk) and can be easily compressed/decompressed during read/write.
* it's super easy to read/write from game and toolset.
* I can decide what to include/exclude of the object.
* Objects/Data can be nested.

Cons:

* Can't edit it by hand (like XML, YAML, etc)
* Can't easily read/modify it with scripts
* Java Serialization by default is pretty slow/bloated compared to other implentations, but it's stable and works

# Answer
> 39 votes
To display hierachical data, YAML or JSON would be good options. They are *far* simpler and easier to parse than XML.

Another option would be a "controlled" binary serialization process. Every object writes it's state out in a controlled way, i.e.

```
void player::save(savegame &sgm)
{
    sgm.write(this->position);
    sgm.write(other properties);
    inventory.save(sgm);
}

```

id Tech 4 (Quake 4 / Doom 3 engine) uses such an approach.

# Answer
> 10 votes
A well made binary format has really got all the advantages, it's fast, reasonably small, and as flexible as you make it.

Making a binary format you are bound by no rules, which is a great advantage, but ironically it's largely what has given binary file structures a bad name. XML, JSON and the like makes a lot of decisions for you, they are far from always optimal, but they are reasonably safe choices that will usually help you steer clear of some otherwise common problems.

Identify these problems, design your format with those in mind, and you can make a great binary format.

If you are not experienced/confident enough to make a binary format and the amount of data is small enough that the speed impact will be negligible, I suggest that you use JSON, it's simple, but does the job.

# Answer
> 8 votes
Your choice of file format is hugely dependent on your current **toolset** and the **game** you are intending to make. With that said...

Toolset is one of the most important factors when deciding a game file format. If you make a **binary format**, you have to always ensure that you **have the tools** to input your game data. This could be as simple as a hex editor, or as complex as Unreal Editor.

I guess the main advantage of XML, YAML, or any other language files, is that you **can edit it easily** via a text editor. And using an existing standard, it **ensures you can't go wrong**. But, this is **extremely tedious** when you have a thousand files, which brings me to my next point.

Game. *What kind of game are you making?* Why I say this will affect the file format? Because, if you are making something like 2D bomberman, you **could get away with a simple text file** like:

```
*********
*1     2*    1,2,3,4  - start point of players 1, 2, 3, 4
* + + + *    *        - walls
*       *    +        - crates
* + + + *
*3     4*
*********

```

In other words, **always go for the most obvious format for your specific data**. *RPGs are the most complex* game genre to make. They require lots of data. But *doesn't mean you have to stick a specific format*, be it binary or text-based for all data in the game.

* **Maps, particles, and other graphical stuff** tend to use a custom binary format. Because it's the *simplest way to implement* it. It's not humanly-sane to describe maps textually. Usually edited via map/level/particle editors.
* Players, items, enemies, skills and quests are **statistics that affect game balance**. They usually require lots and lots of input and tweaking. I like to do this by putting it in an XML file for ease of implementation, but yet having an object editor for the designers to play with. *Best of both worlds*.

Generally, you want to describe text with a text format, and graphics with a binary format. The following should give you an example:

```
<Skill>
    <Name>Fireball</Name>
    <Animation>fireball.dat</Animation> <!-- Graphics described in another file -->
    <Attack>1.3</Attack>
    <Cooldown>15</Cooldown>
</Skill>

```

To sum it up, it is to my fullest recommendation that if possible, you don't script your data, **unless absolutely necessary**. The end-user doesn't care about how awesome the format is, as long as the game is playable, that's all that matters.

Cheers, roy =)

# Answer
> 5 votes
BSON is pretty nice. http://bsonspec.org/. It is easier to parse then JSON and better at containing binary data, but still has a nice structure. It's somewhat similar to protocol buffers. The downside is that there dosent seem to be a lot of tool support for it outside of mongodb.

EDIT: MsgPack ( http://msgpack.org/ ) is also similar to BSON and seem to be gaining more traction.

# Answer
> 2 votes
What's happened to your custom binary data format? If you are afraid of raw serialisation, write your own system that writes fields as needed, and reads them back. No need for xml, which is indeed overly bulky and complex for situations where you don't need the transparency the format provides. Just define a well-specified file format and stick to it, leaving maybe some room for expansion of your data set in each record by padding them with null values (say you have a 100 byte record now, pad that to 150 for future use.
Add a version number and maybe a checksum so you can know what fields should be filled and have a sanity check for validity, and you're good to go.

# Answer
> 1 votes
You can mix XML or some other format with Base64 insertions for some specific data, and for fields you need readability you can use usual TEXT

---
Tags: java, file-format, xml, data, file
---


# Question
Title: What C++ features should I know about for a graphics programming job interview?
I really don't want to be boring, I searched a lot but didn't found a focused answer to this question. I wanted to focus on the role of C++ in graphics programming.

Can somebody explain, which are most likely/ most often used C++ features (such as data structures), which are used in graphics programming? I am supposed to have an interview on this topic, so please shed some light on the features I should emphasize for an interview specific to C++ graphics programming.

# Answer
For a job interview, I would suggest you **worry less about the ability to recite commonly-used features and techniques** (if you're doing this by rote, any good interviewer will see right through you and you'll fail the interview, and if they're not a good interviewer you probably don't want to be working for them).

Instead, since graphics programming is often a performance-critical area, **focus more on understanding the performance implications of common language features**. Understand things like:

* the performance characteristics of pass-by-reference versus pass-by-value.
* the importance of cache coherency and its impact on performance
* the cost of allocations during a frame and how to alleviate said cost
* how dynamic dispatch is typically implemented and what that means for performance

Bonus points if you can correctly demarcate what is a standard C++ guarantee and what is an implementation detail (virtual functions, for example, are the latter -- albeit a very common one).

Each of those topics is a great question on its own (although some more appropriate for StackOverflow than here), so if you want further direction in your study I recommend you post new questions.

Finally, a comment on the original thrust of your question: graphics programming is a language-agnostic domain. The algorithms used will vary widely depending on the kind of rendering one is after, the requirements and limitations of one's platform, and the individual effects one wants to achieve. The combination of all of that will dictate ideal data structures and techniques (although even with that much specificity, there's no obvious "best" choice) and thus what language features may ultimately be employed to achieve the desired results.
> 4 votes

---
Tags: c++, graphics, graphics-programming, interview
---


# Question
Title: Am I on the right track with this component architecture?
I've recently decided to revamp my game architecture to get rid of deep class hierarchies and replace them with configurable components. The first hierarchy I'm replacing is the Item hierarchy and I would like some advice to know if I'm on the right track.

Previously, I had a hierarchy that went something like this:

```
Item -> Equipment -> Weapon
                  -> Armor
                  -> Accessory
     -> SyntehsisItem
     -> BattleUseItem -> HealingItem
                      -> ThrowingItem -> ThrowsAsAttackItem

```

Needless to say it was starting to get messy and these was no easy solution to items that needed to be multiple types (i.e. some equipment is used in item synthesis, some equipment is throwable, etc.)

I then attempted to refactor and place functionality into the base item class. But then I was noting that the Item had alot of unused/superfluous data. Now I'm trying to do a component like architecture, at least for my items before attempting to do so to my other game classes.

Here's what I'm currently thinking for the component setup:

I have a base item class that has slots for various components (i.e. an equipment component slot, a healing component slot, etc. as well as a map for arbitrary components) so something like this:

```
class Item
{
    //Basic item properties (name, ID, etc.) excluded
    EquipmentComponent* equipmentComponent;
    HealingComponent* healingComponent;
    SynthesisComponent* synthesisComponent;
    ThrowComponent* throwComponent;
    boost::unordered_map<std::string, std::pair<bool, ItemComponent*> > AdditionalComponents;
}

```

All item components would inherit from a base ItemComponent class, and each Component type is responsible for telling the engine how to implement that functionality. i.e. the HealingComponent tells the battle mechanics how to consume the item as a healing item, while the ThrowComponent tells the battle engine how to treat the item as a throwable item.

The map is used to store arbitrary components that are not core item components. I'm pairing it with a bool to indicate whether the Item Container should manage the ItemComponent or if it's being managed by an external source.

My idea here was that I define the core components used by my game engine up front, and my item factory would assign the components that the item actually has, otherwise they are null. The map would contain arbitrary components that would generally be added/consumed by scripting files.

My question is, is this a good design? If not, how can it be improved? I considered grouping all components into the map, but using string indexing seemed unecessary for the core item components

# Answer
It seems like a very reasonable first step.

You're opting for a combination of generality (the "additional components" map) and lookup performance (the hard-coded members), which may be a bit of a pre-optimization -- your point concerning the general inefficiency of string-based look-up is well-made, but you can alleviate that by choosing to index components by something faster to hash. One approach might be to give each component type a unique type ID (essentially you're implementing lightweight custom RTTI) and index based on that.

Regardless, I would caution you to expose a public API for the Item object that allows you ask for any component -- the hardcoded ones and the additional ones -- in a uniform fashion. This would make it easier to change the underlying representation or balance of hardcoded/non-hardcoded components without having to refactor all the item component clients.

You might also consider providing "dummy" no-op versions of each of the hard-coded components and ensure that they are always assigned -- you can then use reference members instead of pointers, and you will never need to check for a NULL pointer before interacting with one of the hard-coded components classes. You will still incur the cost of the dynamic dispatch to interact with that component's members, but that would occur even with pointer members. This is more of a code cleanliness issue because the performance impact will be negligible in all likelihood.

I don't think it's a great idea to have two different kinds of lifetime scopes (in other words, I don't think the bool you have in the additional component map is a great idea). It complicates the system and implies that destruction and resource release isn't going to be terribly deterministic. The API to your components would be much clearer if you opted for one lifetime management strategy or the other -- either the entity manages the component lifetime, or the subsystem that realizes components does (I prefer the latter because it pairs better with the outboard component approach, which I will discuss next).

The big downside I see with your approach is that you are clumping all of the components together in the "entity" object, which actually isn't always the best design. From my related answer to another component-based question:

> Your approach of a using a big map of components and an update() call in the game object is quite sub-optimal (and a common pitfall for those first building these sorts of systems). It makes for very poor cache coherency during the update and doesn't allow you to take advantage of concurrency and the trend towards SIMD-style process of large batches of data or behavior at once. It's often better to use a design where the game object doesn't update its components, but rather the subsystem responsible for the component itself updates them all at once.

You're essentially taking the same approach by storing the components in the item entity (which is, again, an entirely acceptable first step). What you may discover is that the bulk of the access to components you are concerned about the performance of is just to update those, and if you elect to use a more outboard approach to component organization, where the components are kept in a cache-coherent, efficient (for their domain) data structure by a subsystem that understands their needs the most, you can achieve much better, more parallelizable update performance.

But I point this out only as something to consider as a future direction -- you certainly don't want to go overboard overengineering this; you can make a gradual transition through constant refactoring or you may discover your current implementation meets your needs perfectly and there's no need to iterate on it.
> 8 votes

---
Tags: c++, architecture, component-based
---


# Question
Title: How to draw objects that have a smaller Y axis first?
In my game there is a large 2D map of various objects. Example. As you see, upon creation objects of the same type (trees for example) are placed correctly, but objects of another type (enemies) are placed on top of the no matter the position. Now, how can I arrange that everything is drawn according to it's position?

Another example (the dog should be drawn before the tree, and not on top of it):

# Answer
> 3 votes
Assuming that you have an array containing every object that needs to be drawn. On each game loop you would loop through this array and call each object's corresponding draw() method to place it on the canvas. If you are doing it this way then you can use a sorting function on the array that will sort the array based on the object's Y axis value. So when the next game loop occurs the objects will naturally be drawn in the order that you need.

```
var gameObjects = [{y:0}, {y:1}, {y:20}, {y:-4}, {y:2}];
gameObjects.sort(function(a,b) { return a.y - b.y; });

console.log(gameObjects); //gives: [{y:-4}, {y:0}, {y:1}, {y:2}, {y:20}]

var l = gameObjects.length,
    c = 0;
while(c < l) {
    gameObjects[c].draw();
    c++:
};

```

This way objects with small Y values will be drawn first and the last object drawn will have the largest Y value.

# Answer
> 7 votes
I'm just going out on a limb here and assuming that your drawing is painter style, in that something drawing first will show up behind something drawn after it.

If that's the case, it's simply a matter of sorting your entities by y position before you draw. I'm assuming you have some mechanism of iterating through all of your entities. You'll have to sort every time the list get modified, which if you have continuously moving entities will probably be every frame.

There are a handful of optimizations you can do with this. For one, you probably want to discard objects that aren't in your viewport at all, first. It's pretty common to put entities in tiles and then only sort those tiles. But those can come afterwards, depending on your performance issues..

---
Tags: javascript, html5, html-canvas, screen
---


# Question
Title: Can DrawIndexedPrimitives() be used for drawing a loaded model mesh-wise?
I am using DrawIndexedPrimitives() for drawing a loaded 3D model by drawing each mesh part, but this process makes my application very slow. This is perhaps because of a very large number of vertex/index buffer data created in video memory.

That is why I am looking for a way to use the same method for each model mesh instead. The problem is that I don't know how I will set the textures of that mesh. Can anyone offer me some guidance?

# Answer
> 1 votes
Make a single texture atlas by combining all your mesh's textures into one, in any image editing program. Then you'll have to go into your 3D modeling program to set the texture atlas to all the parts of your model, and UV re-map. The re-mapping is not as daunting as you might expect- it'll usually just be a matter of rotating, proportional scaling and moving the groups of vertices until they fit with the new texture. Export the mesh with the new texture coordinates.

Combine your mesh parts into a larger one in runtime. When the models are being loaded, read each vertex buffer and index buffer and join them together to create one large vertex buffer and index buffer. This is a non-destructive change, as you still get to keep the individual mesh parts if you want to go back and make any further tweaks in the modeling program. Now with these new buffers, you only need one draw call and one texture change to render each model.

Your program sounds like it's drawing a complex or busy scene, so it may take some time to build the new vertex buffers dynamically. However, you'll just do this once each time they load in the program.

# Answer
> 0 votes
If the entire model uses only one texture, theoretically you can set that texture and draw the model's vertex buffer and index buffer in one call, since the entire model is stored in a single vertex and index buffer.

Except, when you load the model the indexes for various mesh parts will not be relative the vertex buffer as a whole, but rather the mesh part's vertex offset, making that impossible for no good reason. So to draw the entire model in one draw call you will have to create a new index buffer with corrected indexes.

---
Tags: xna
---


# Question
Title: How can I rotate about an arbitrary point in 3D (instead of the origin)?
I have some models that I want to rotate using quaternions in the normal manner, except instead of rotation about the origin, I want it to be offset slightly. I know that you don't say, in 3d space, that you rotate about a point; you say you rotate about an axis. So I'm visualizing it as rotating about a vector whose tail is positioned not at the local origin.

All affine transformations in my rendering / physics engine are stored using SQT (scale, quaternion, translation; an idea borrowed from the book *Game Engine Architecture*.) So I build a matrix each frame from these components and pass it to the vertex shader. In this system, translation is applied, then scale, then rotation.

In one specific case, I need to translate an object in world space, scale it, and rotate it about a vertex not centered at the object's local origin.

**Question:** Given the constraints of my current system described above, how can I achieve a local rotation centered about a point other than the origin? *Automatic upvote to anyone who can describe how to do this using only matrices as well :)*

# Answer
> 18 votes
### In short

You only need to change T in your SQT form.

Replace the translation vector `v` with `v' = v-invscale(p-invrotate(p))` where `v` is the initial translation vector, `p` is the point around which you want the rotation to occur, and `invrotate` and `invscale` are the inverses of your rotation and scale.

### Quick demonstration

Let `p` be the point around which you apply rotation `r`. Let `s` be your scaling parameters and `v` your translation vector. The final matrix transformation is `T(p)R(r)T(-p)S(s)T(v)` instead of `R(r)S(s)T(v)`.

What you want is new transformation parameters `v'`, `r'` and `s'` such that the final matrix transformation is `R(r')S(s')T(v')` and we have:

```
T(p)R(r)T(-p)S(s)T(v) = R(r')S(s')T(v')

```

Behaviour at infinity indicates that rotation parameters and scaling parameters cannot change (this could be demonstrated). We thus have `r = r'` and `s = s'`. The only missing parameter is therefore `v'`, your new translation vector:

```
T(p)R(r)T(-p)S(s)T(v) = R(r)S(s)T(v')

```

If these matrices are equal, their inverses are equal:

```
T(-v)S(-s)T(p)R(-r)T(-p) = T(-v')S(-s)R(-r)

```

This especially holds true for origin `O`:

```
T(-v)S(-s)T(p)R(-r)T(-p)O = T(-v')S(-s)R(-r)O

```

Scaling and rotating the origin yields the origin, whe thus get:

```
T(-v)S(-s)T(p)R(-r)(-p) = -v'

```

`v'` is the new translation vector you are looking for that lets you store your transformation in SQT form. It is probably possible to simplify the computation; but at least the required *storage* is not increased.

# Answer
> 16 votes
All of the canonical rotational formulas used to derive your rotation matrices are for rotation about the origin. If you would like instead to apply that rotation around a specific point, you must first offset the origin -- or, equivalently, move the object so the point you want to rotate about is at the origin.

Consider the 2D case first, because it is simpler and the technique scales. If you had a cube of width 2 centered on the origin and you wanted to rotate it 45 degrees about its center, that would be a trivial application of the 2D rotation matrix.

But if instead you wanted to rotate it around it's upper right corner (located at `1,1`) you'd first have to translate it so that corner was at the origin. This can be accomplished with a translation of `-1,-1`. Then you can rotate the object as before, but you must follow this up by translating it back (by `1,1`). So in general, to achieve the rotation matrix `R` for a rotation of `r` about point `P` you do:

```
R = translate(-P) * rotate(r) * translate(P)

```

where `translate` and `rotate` are the canonical translation/rotation matrices, respectively. As it happens, this scales trivially to 3D, which the exception of having to supply an axis to the rotation as well -- you could just always choose the canonical X, Y or Z axis rotation matrices, but that would be dull. You'll want to use the arbitrary axis-angle rotation matrix. Your final `R` in 3D is thus:

```
R = translate(-P) * rotate(a,r) * translate(P)

```

where `a` is a unit vector representing the axis of rotation and `P` is now a 3D point in model space representing the rotation point.

As it happens, quaternions can be converted to and from matrix representations, so you could do your concatenation that way should you so choose. Or you could just leave everything as matrices (quaternions have some nice advantages such as being easier to interpolate in a sane fashion, but whether or not you need that is up to you).

Also:

> So I'm visualizing it as rotating about a vector whose tail is positioned not at the local origin.

Strictly speaking, while vectors can be used to represent positions by considering them as displacements from an origin, vector's don't have positions themselves so it's a bit unusual to visualize one as such.

---
Tags: mathematics, matrix, rotation, quaternion
---


# Question
Title: How can I model the physics of an air blower?
I want to model simple lottery machine, it has got a bottom blower.

Do you know how can I get force applied to object above blower by air from blower, or equations to model this behavior?

Red arrow is blower "wind"

# Answer
In all cases, you will need a fluid simulation. However, there are several methods available out there, and the proper solution will depend on various parameters:

* is the simulation constrained? (the answer here in your case is *yes*)
* does the world affect the fluid? does the fluid affect the world? (*yes* to both because of the balls)
* are several types of fluid mixed? (the answer here is *no*, unless the air being blown is hot)
* do you have a lot of memory available?
* should the simulation be real-time?
* what is the desired accuracy versus performance?
* what is the desired realism? (often accuracy can be traded for performance at no cost of realism)

I suggest you start by reading Josh Stam’s Stable Fluids. It will probably not give you the immediate answer, but it will give you an idea of where to start. You should also check out computational fluid dynamics software implementations.

Since one of the major phenomenons causing the random result is turbulence, I would suggest going for a large eddy simulation.
> 5 votes

# Answer
I would suggest you utilize a physics engine, such as Bullet. It will save you a lot of work in the long run.

That said, if you want to get started writing your own physics simulation from scratch, you may want to check out the series of articles from Glenn Fiedler's blog that start here.
> 2 votes

# Answer
Use the Drag Equation with velocity varying as a function of distance from the blower. You might also introduce extra variability by varying the entire velocity field in a random (or periodic) way as a function of time.

You'll need to simulate standard collision dynamics for the balls as well (this is what produces the complex mixing).

As far as selecting which ball goes up the tube when the slot is opened, you'll mostly just pick the one closest to the internal end of the tube.

## Reference

A - the cross sectional area of the sphere (pi\*r^2)

rho (looks like 'p') - 1.22521 kg/m^3 (Density of Air, sea level, room temp)

C - 0.47 (Drag coefficient of a sphere)
> 0 votes

---
Tags: physics, simulations
---


# Question
Title: When should I talk to a lawyer about intellectual property for an indie team?
Let's say you have a team building a decent game and all is well technically and people-wise. You feel pretty sure you'll get to a product that can be sold. How does an indie studio (with good practices in this domain) typically manage the IP, esp. trademarking and copyrighting? When's the right time to do this, early or later?

# Answer
First get yourself a copy of Business and Legal Primer for Game Development. It is an invaluable resource, not just in the legal department. They have a chapter or two on this sort of thing, and it's comprehensive.

If you're in any doubt about the status of things or who will claim ownership, I'd do what Josh Petrie suggests, and right away.
> 7 votes

# Answer
Hire a lawyer. The earlier the better -- you should have done it already to draw up contracts concerning who retains what IP if people leave or disagree, et cetera.

See this article on the legal issues related to ad hoc, indie development teams (written by a real lawyer, which I am not, so my advice is not legal advice).
> 9 votes

---
Tags: legal, copyright, intellectual-property
---


# Question
Title: How do I generate terrain like that of Scorched Earth?
I'm a web developer and I am keen to start writing my own games.

For familiarity, I've chosen JavaScript and `canvas` element for now.

I want to generate some terrain like that in Scorched Earth.

My first attempt made me realise I couldn't just randomise the `y` value; there had to be some sanity in the peaks and troughs.

I have Googled around a bit, but either I can't find something simple enough for me or I am using the wrong keywords.

Can you please show me what sort of algorithm I would use to generate something in the example, keeping in mind that I am completely new to games programming (since making Breakout in 2003 with Visual Basic anyway)?

# Answer
> 18 votes
The midpoint displacement algorithm is exactly what you want.

That link can generate something like this:

Or like your image, depending on what parameters you use. There's C source available here.

# Answer
> 5 votes
How about using midpoint displacement algorithm possibly followed by a slight smoothing e.g. low pass filtering to remove too sharp spikes? This approach is not the same as in Scorched Earth, but is should provide similar results.

I believe that Scorched Earth simulated somehow the gravity and falling dirt. For example you can't have too steep hill because otherwise the dirt would fall down and create a less steep slope.

# Answer
> 1 votes
There is another approach you can use. You can add together a number of randomly generated sine waves and then scale the result to fit on your screen. It is really easy in practice and produces some nice results, although smoother and perhaps more artificial than your example screenshot.

You can see the source in javascript here. It is really easy to fiddle with some parameters to get different kinds of terrain.

https://github.com/fmstephe/Tankwars

---
Tags: javascript, procedural-generation, terrain
---


# Question
Title: How to efficiently store and display a tile map on the web?
# About

These are actually two questions in one. First of all I am looking for a way to efficiently store large amounts of tile data. The other aspect deals with querying the data set and displaying tiles. Let me give you some background first.

We are making a browser based multiplayer tycoon game using the CraftyJS library to render it to Canvas. In the background of the GUI we're running Yii Framework on PHP and it all connects to a Python random map generator and game engine.

This is how the first rough map render looks: https://i.stack.imgur.com/hqdLn.jpg

# Storing the map data

The game world is randomly generated each time the game starts. The size is 100x100 hexagonal tiles for each player. That means that for a three player game, there are 90.000 tiles created. Currently I just create a JavaScript array from which I render the map.

This works fine for rendering, but for any kind of interaction with the map we need to store which player owns the tile, what kind of structure is build on top of it, what's it's current price and so on. At first, at least for the prototype, we wanted to use MySQL, but after some testing, it's not exactly as fast as I'd like. Maybe an object store like MongoDB would be better suited for storing tile data instead of an SQL table. Or maybe something else?

# Displaying the map

Another problem I see is moving around the map. Currently I'm creating Crafty entities for each tile even if it's not in the viewport. This is slow, because even though Crafty renders only the ones in the viewport, it stores and possibly iterates through all the tiles on each render event. What I currently have is a drawn generated map which is very slow to load and stutters when you move around, now I'd like to make it playable.

My first idea was to load the displayed subset of tiles that are in the viewport. But when a player would move the viewport to a blank area, I'd need to query the server and wait for the response back, only then can the map be rendered. This would be fine in a native application, but it's laggy in a web game.

The way to get smooth performance from the map could be preloading a bigger subset of tiles into a javascript array and use it as a cache. The player would have a few screens "cached" and when he moves the viewport, I'd load more tiles to the JS "cache".

Am I headed in the right direction? I would love to get some more information from someone who has done something similar. I am new to game development, but have been going through a lot of sources over the last couple of weeks.

# Answer
**Gameplay**
First of all I'd like to ask you, do you actually need 10000 tiles per player? While I don't know what kind of game you are making it is generally true that large maps make long games. The largest map in Civilization 5 is 10240 tiles, and that only sorta works because you don't need to play on more than a fraction of it.

**Database**
You should not try to run a game like this off a database, you need to keep the data in application memory. You could use a database to back up the game. For a complete backup save a serialization of the game data, and then you can increment it by saving the orders given and then rerun those if the backup needs to be used.

**JavaScript storage**
As for the client, I'd say you better keep the entire map loaded, at least if you stick to the gazillion tiles having it all in a nice object tree might be a bit too much, so you should probably keep the data in a "semi-binary" encoded format. Strings work excellent for this kind of stuff, alternately, you can safely store unsigned integers up to 53 bits in a 64 bit float, stuff a lot of those in an array and I think you'll see a pretty modest memory footprint.

**JavaScript visualization**
While I won't say that you necessarily shouldn't use canvas, you actually don't need it for stuff like this. Set it all up as a bunch of img elements, and change the src property to display different parts of the map.

**Pro tip**
By the way, sometimes it is easier to share the seed used for generating it than sharing the whole map.
> 2 votes

# Answer
MySQL is not slow. Most likely you are performing naïve queries or have sub-optimal indexes. NoSQL approaches like MongoDB may be faster, maybe not. Your access pattern and choice of query is what really matters here. It's possible to give advice on how to improve performance, but not without seeing what you are already doing.

> The way to get smooth performance from the map could be preloading a bigger subset of tiles into a javascript array and use it as a cache.

Yes, of course. There's not much to add here - the client asks for tiles from the server, so you just have to ensure that the ones you ask for cover an area larger than the screen.

Addendum:

> we're running Yii Framework on PHP and it all connects to a Python random map generator and game engine.

If you're competent with Python then I'd advise that you ditch the PHP middleman. If you run your game as a Python process then you can keep your tile data in memory much more easily and reduce the MySQL accesses significantly. It helps that Python is a much saner language than PHP, too.
> 1 votes

---
Tags: maps, performance, html5, html-canvas
---


# Question
Title: How can I draw dashed or dotted lines with a pixel shader?
I am trying to draw the 2D graphics (like line, polyline, polygon etc.) using Direct3D for drawing I am using LINE\_LIST. Now I want to make the lines thicker and apply patterns to the line as described here.

I am able to draw the thick lines using a geometry shader to draw a quad but to apply patterns I need to write a pixel shader that will do all the stylization of line that is which fragment should be drawn and which fragment of line should be left behind.

I would really appreciate if, anybody could help in writing the pixel shader or provide me any reference to write it.

# Answer
> 3 votes
You may be interested in this paper on hardware-determined feature edges. In particular, the paper discusses techniques for texture parameterization of feature edges, which can be used to apply dotted/dashed stipple pattern textures to your lines.

It is probably possible to do this without that kind of texture parameterization (but still using texture coordinates to transport information about a particular fragment's position along the line segment in the pixel shader) and division to decide which bucket of size N the current fragment falls in to, and if that is an even bucket you color the fragment otherwise make it transparent.

You'd have to use the rate of change of the texture coordinates to determine whether the line's slope was such that the line was longer than it is taller (or the other way around) and use that to determine which axis to quantize into the buckets).

# Answer
> 1 votes
You could apply a texture containing a dash pattern to the line; when you convert it to a quad in the geometry shader, generate UVs too, proportional to the length of the line so that the dashes are a constant length. Then just use a regular texture-mapping pixel shader, with an alpha test or similar to discard the unwanted pixels.

If you're targeting hardware that has DX11 tessellation capabilities, you might also be able to use tessellation to subdivide the line and generate individual quads for each dash or dot. That would be more complex but might be useful in some circumstances. (Actually, you can do some tessellation in the geometry shader as well, though you're limited in the number of segments you can output for each input segment, and it's not as efficient as tessellation.)

---
Tags: directx11, slimdx
---


title: Where will my character stop?

text:
# Question
Title: Where will my character stop?
Many years ago I coded some AI for a budget pseudo-3d game. There was one calculation which I never really figured out the best way to do, and that was calculating where the enemy would end up if it stopped now. For example:

* The enemy is currently at X = 540.0.
* The enemy is moving right at 10 pixels per frame.
* When the enemy wants to stop, it's speed will drop by 1 pixel per frame until it reaches zero.

Is there a simple formula that would get me the position where the enemy ends up when he is fully stopped? I ended up precalculating and hardcoding the offset which worked for my needs but would have to be calculated separately for enemies with different speeds.

# Answer
I generally agree with John's answer. I'm going to offer a slightly modified formula (which adds an extra V/2 onto his value):

```
D = V / A * (V + A) / 2

```

With `V = 10` and `A = 1`, that gets **D** = `55`. This is exactly the result of

```
10 + 9 + 8 + 7 + .... + 3 + 2 + 1

```

which is the frame-by-frame motion of the enemy.

Here's kind of how you go about getting to that step.

1. **V**: Current Velocity = 10 pixels/frame, **A**: Current Acceleration = 1 pixels/frame^2
2. **T**: Time To Come to a Stop = V/A = 10 frames.
3. Distance Traveled in 10 frames = frame1 + frame2 + frame3 + ... = V +(V-A)+(V-2\*A) + ...
4. This is equal to T * V - A/2 * T * (T-1), which simplifies to the above equation.
> 7 votes

# Answer
I had the exact same issue when working on my game, and it took me forever to get the math right (bleh). So here it is:

```
minDistanceToStop = 0.5 * acceleration * Math.Pow(velocityLinear() / acceleration, 2.0);

```

Re-written into regular math:

```
(Acceleration / 2) * (linearVelocity / Acceleration)^2

```

Where acceleration in your case is 1, and linearVelocity is 10:

```
(1 / 2) * (10 / 1)^2
= 50 units to stop

```

**EDIT**

Jimmy's result and explanation are both correct. My formula requires that you also add half of the velocity.

```
minDistanceToStop = (0.5 * acceleration * Math.Pow(velocityLinear() / acceleration, 2.0)) + (velocityLinear() / 2);

```

or

```
((Acceleration / 2) * (linearVelocity / Acceleration)^2) + (linearVelocity / 2)
((1 / 2) * (10 / 1)^2) + (10 / 2)
= 55

```
> 6 votes

# Answer
Calculations about changing velocities is the entire point of calculus. I haven't done it in a while so I don't remember off the top of my head, but I think your situation is simply taking the integral of -1 (ie. the deceleration).
> 4 votes

# Answer
Isn't this constant acceleration motion?

```
X = Xi + V*t + (1/2) * a * (t^2)

```

Where:
X: Last position
Xi: Initial position
V: Velocity
t: Time
a: Acceleration

The only tricky part here is how to determine "t", since we slow down with an acceleration of -1, then we can calculate t = V/a , then t is 10.

so,
Xi: 540
V: 10
t: 10
a: -1

Put everything on:

```
X = 540 + 10*10 + (1/2) * (-1) * (10 ^ 2)
X = 540 + 100 + (-50)
X = 540 + 50
X = 590

```

The formula comes from by taking integration of acceleration: Check here
> 0 votes

---
Tags: ai, movement, mathematics
---


# Question
Title: In a browser, is it best to use one huge spritesheet or many (10000) different PNG's?
I'm creating a game in jQuery, where I use about 10000 32x32 tiles. Until now, I have been using them all separately (no sprite sheet). An average map uses about 2000 tiles (sometimes re-used PNG's but all separate divs) and the performance ranges from stable (Chrome) to a bit laggy (Firefox). Each of these divs are positioned absolutely using CSS. They do not need to be updated every tick, just when a new map is loaded.

Would it be better for performance to use spritesheet methods for the divs using CSS background-positioning, like gameQuery does?

Thank you in advance!

# Answer
> 49 votes
## My suggestion

Too many small PNGs will add a lot of network overhead (because of the size of the HTTP requests, but also the PNG header, and, probably even more importantly, the inability to compress efficently). On the other hand, one very large PNG has the drawbacks that it takes some time to load, and needs to stay permanently in memory (40 megabytes for 10,000 tiles) in a continuous chunk of memory.

I recommend **the middle ground: several reasonably sized PNGs, for instance 1024 tiles of size 32×32**. Maybe grouped by theme (for instance, a PNG with forest tiles, one with mountain tiles, another with city tiles -- I don't know the theme of your game, but you get the idea).

## Note about cache efficiency

Because of memory access efficiency, you should **never** make your spritesheets too wide. Blitting tiles from a 128×8192 image will always be faster than blitting from a 8192×128 image.

Imagine you want to blit the first tile in a 8192×128 image. For the sake of simplicity, assume 1 pixel is 1 byte. The first two lines of pixels are laid out this way (cells contain their byte number in memory):

```
┌────┬────┬───┬────┬──────────┬─────┐
│  0 │  1 │...│ 31 │   ....   │ 8191│ 1st line of pixels: bytes 0 to 8191
├────┼────┼───┼────┼──────────┼─────┤
│8192│8193│...│8223│   ....   │16383│ 2nd line of pixels: bytes 8192 to 16383
├────┼────┼───┼────┼──────────┼─────┤
│ .. │ .. │...│ .. │   ....   │ ... │

```

So in order to blit the **first line** of the first title, the browser engine will retrieve **bytes `0` to `31`**. To blit the **second line**, it will retrieve **bytes `8192` to `8223`**, and so on until the 32nd line where bytes **`253952` to `253983`** are retrieved.

The total number of processed bytes will be 32×32. However, the total memory range is more than 253984 bytes. On a modern CPU, this means 32 or 33 cache stalls. In contrast, if the image was 128×8192, the memory range would be only 4000 bytes, which means no more than two cache stalls.

Because today's CPUs are very fast, cache stalls are very expensive and hang computations. So using a 128×8192 image instead of a 8192×128 image is potentially 8 times as fast, in theory at least. In practice this will depend how the blitting is implemented: it is possible that the underlying engine itself splits images into tiles to reduce the problem.

This isn't easy to explain correctly and I didn't expect to elaborate much. I hope it makes sense!

# Answer
> 5 votes
One huge spritesheet is (likely) going to give you better performance, simply because one of the biggest causes of lag is the round trip from browser request to server to browser. 10,000 HTTP calls is going to take much, much longer than 1 HTTP call that returns a file that is 10,000 bigger.

There might be other things you can use to decrease lag, depending on the structure of the game and the HTML you're creating.

---
Tags: javascript, sprites, tiles, spritesheet
---


title: Box2D/Farseer Collision Detection

text:
# Question
Title: Box2D/Farseer Collision Detection
I am looking for literature - or a simple explanation - on how the Farseer (and for that reason, the Box2D) collision detection system works - specifically the logic that comes **after** the broadphase culling:

* What data structure does it use?
* How does it use that data structure to determine if a collision has occurred?
* How does it calculate the response normals?

**NB:** I am not asking how to use it, I merely want to know how it works as a matter of personal enlightenment.

# Answer
There is a small explanation of the Farseer 2.1 physics. It includes information on both SAT and Distance Grid detection.
> 0 votes

# Answer
I really recommend Real-Time Collision Detection by Christer Ericson

It'll answer all your questions, go buy, rent, steal this book.
> 1 votes

---
Tags: box2d, farseer-physics-engine
---


# Question
Title: How often to save player's state in persistent online games?
In online games, people prefer to log on and off whenever they want. Usually, their game achievements are seamlessly saved, on the server. That is not that difficult to achieve, but I am wondering how can be done in an efficient way that makes sense and will scale.

Does it make sense to save the player's coordinates and state with every time they send it? My node.js server can do that easily without blocking a response, and I want to employ a Mongo database, but maybe it's more appropriate to do that once a second and in a server-wide event, collecting all at once?

# Answer
> 13 votes
I have in mind a traditional MMORPG like World of Warcraft.

## Save after every command from each player and autonomous thing (e.g. NPC)

* Constant backup. The server could go down at any moment, and the state of the game is saved up to that moment (or as recent as possible, anyway).
* Impact to server performance; even if it's non-blocking (i.e. on another thread), even if the database is on another server, it is processing that you would otherwise not do. If it is non-blocking like you say, then another thread has to handle it, and that's a thread that could be occupied with something else.
* Increased disk I/O, thus increasing risk/rate of failure. This is especially a concern if you are using SSDs for storage, given their lower life.
* If you offload the database to another server, then increased bandwidth; this might be a concern if you are paying for bandwidth, and if it's not on a separate network card then it's taking up resources that could be better put to use handling player traffic.
* What happens if the server gets further and further behind in saving the state of these commands? I.e. if more commands come in than can be saved, so they pile up in a queue? Does this queue overflow and cause an error? Do you stop everything so the queue can catch up?
* It seems to me that this approach, while it sounds simple, would need to be carefully planned. For example, consecutive commands that rely on each other will need to be saved together; otherwise a failure could occur in the middle of the commands, and only one will be saved but not the other. Consider if two players execute a trade and two commands are saved to disk: "add 1 of the item to recipient" and "subtract 1 of the item from sender". If a failure happens after the first command but before the second command is saved, you have an item duplication. (if the order is reversed, then you have a lost item)

## Save everything periodically

* In case of a failure, the server will be somewhat out of date. Hopefully you use something like a journaled approach, so the most recent snapshot will at least be whole and consistent, and all the active players are set back by the same amount of time.
* Whatever database system you use might have an optimization for batch updating, which is more efficient (less overhead) than updating one at a time.
* If you opt instead for a binary file system, this method is dead simple. Make a new file, dump memory into it, throw a marker on the end which signals that the backup was fully completed. Once one backup completes, delete the previous backup (or don't).
* The backup process may also need to account for things mentioned in the last bullet point of the other section, such as saving in the middle of consecutive commands that should not be broken up. You might opt to lock the entire set of data, dump it to disk, and unlock it, but depending on how much time that takes, it could result in a pretty hefty pause or slowdown in the game.

## Save a character on logout (don't save anything else)

* The most important thing to a player is their character, which includes the items they have, the skills they've earned, their friends list, and so on. If they kill a monster and the loot is on the ground in front of them and then the server fails, they're going to be a little heartbroken at not having the chance to pick up their loot, but they'll get over it. So just save the important stuff, and don't sweat the small stuff. Don't save the positions of NPCs, for example; if the server goes down, when it comes back up, they'll spawn in the general area that they should be in. The exception, of course, is for any "smart" NPCs that for some reason need to remain in the place they were when the server went down.
* Furthermore, a player shouldn't be logged in for too many hours at a time (note that here I'm considering "going back to a lobby" as logging out). They will eventually need to take a bathroom break or get food or get interrupted by their parent/friend/whatever or sleep. So they really shouldn't realistically be logged on nonstop more than, say, 8 hours for even the most hardcore gamer. If a "player" is logged on for a really long period of time, there's a good chance that it's either multiple people or a bot, and neither one is desirable or normal.
* Also, your logout process should already be checking for things like the above-mentioned consecutive commands. It should essentially already be packing up the character, so it's obviously a prime time to dump it to disk.

## Closing thoughts

* Clearly I'm in favor of the last approach, but I tried to be unbiased about all three.
* It's difficult to say which of the first two methods is more wasteful. With the first method, if the character sends several move commands, these will each be saved to disk and overwritten, when clearly they could be packaged up into one. But with the second method, if you have half of your population standing around, their positions are being saved to disk even if they're the exact same since the last backup operation. In the third case, it is very possible that someone could log on and immediately log off, but most often, many things about the player will have changed so the wastefulness seems like it would be minimal.
* Keep in mind that this is entirely for backup in case of failure, and a failure should be absolutely minimized. It's good to handle this exception case, but in the end, if the server fails, some data is going to be lost and some players are going to be upset. So just implement whatever method you can, whatever you think is simplest or best, and continue on.
* Don't rely on this as the default save; put in a nice shutdown button on your server application, which gracefully closes connections and writes everything to the database. Use that on a normal basis.

Lastly, don't take this advice as absolute truth. I haven't written a multiplayer backup system. I *am* working on an online "game", which is why I have thought of this and wrote out my thoughts above, but I haven't gotten to the stage of implementing this yet. So this is written without actual experience, but after lots of reading and collecting knowledge about the topic.

# Answer
> 1 votes
I suppose it depends on the type of game an the amount of traffic between players and the server.

In an MMORPG, it would not make sense to save the players position every time they send the information to the server. It would make more sense to update when the player's current data is 'stale', so to speak. It might also be beneficial to save the player's state on major events such as crossing into new territory, defeating a boss or leaving a store.

In a turn-based game, it would definitely make sense to save the player's state every time they end their turn as well as after an opposing player's turn (save health loss, spell effects, etc).

Again, the answer depends entirely on scale and the capabilities of your server. It's all about finding the best balance and optimizing as much as possible without sacrificing quality.

# Answer
> 1 votes
If your only concern is when they log off, then one simple answer is to save their position when whatever conditions for them no longer existing in the game world (due to log off or disconnect) occur.

On a side note though, I would be somewhat wary of the client reporting to the server it's position, or at very least without some form of server side sanity check. If you already have this in place though, you can likely save that position on log off or disconnect as you don't have to worry about getting any data from the client directly.

---
Tags: performance, browser-based-games, node.js
---


# Question
Title: Different ways to store a 2D map/landscape in XNA
I was looking around at this site about eight months ago and wish I saved the location of this topic but I was wondering the different map rendering styles that you can do in XNA. The one style I looked at was using a text file to pull characters like "X" would be a monster and "O" would be the player. Is there another way with out an external file that I can put tiles from a sprite sheet to randomly create a map. Of course when dealing with random buildings I would have certain building designs so that if some one was playing they wouldn't see a building with half a wall missing.

This is for a top down 2D game.

# Answer
There are a lot of different ways to store this information. I would suggest using something standard, though. For instance a lot of opensource games use the TMX map format as used by the Tiled editor and several others.

TMX uses XML but can store its data in compressed form, as an array, or using a CSV layout. The storage method is for you to choose in the editor.
> 3 votes

# Answer
To add to the above answer Nick Gravelyn makes a very nice library for importing and rendering TMX maps. Takes about 10 lines of code to import it from Tiled and render it.

https://bitbucket.org/nickgravelyn/tiledlib
> 1 votes

---
Tags: xna, 2d, maps, procedural-generation, data
---