title: Animation with 10 frames

text:
# Question
Title: Animation with 10 frames
I am making a game, and the animation class I made with 8 frames worked fine, but when I added 2 more frames, it messed up. Here is the code:

```
  using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Input;

namespace Cubiez
{
    class Player
    {
        public Texture2D playerTexture;
        private Rectangle playerRect;
        public Vector2 playerPosition;
        public Vector2 origin;
        public Vector2 velocity;

        public int currentFrame;
        public int frameHeight;
        public int frameWidth;

        float timer;
        float interval = 150;

        bool hasJumped;

        public Player(Texture2D newPlayerTexture, Vector2 NewPosition, int newFrameHeight, int newFrameWidth)
        {
            playerPosition = NewPosition;
            playerTexture = newPlayerTexture;
            frameHeight = newFrameHeight;
            frameWidth = newFrameWidth;
            hasJumped = true;
        }

        public void Update(GameTime gameTime)
        {
            playerPosition += velocity;

            playerRect = new Rectangle(currentFrame * frameWidth, 0, frameWidth, frameHeight);
            origin = new Vector2(playerRect.Width / 2, playerRect.Height / 2);
            playerPosition = playerPosition + velocity;

            if (Keyboard.GetState().IsKeyDown(Keys.Right))
            {
                velocity.X = 2f;
                AnimateRight(gameTime);
            }
            else if (Keyboard.GetState().IsKeyDown(Keys.Left))
            {
                velocity.X = -2f;
                AnimateLeft(gameTime);
            }
            else
            {

            velocity.X = 0f;
        }

        if (Keyboard.GetState().IsKeyDown(Keys.Space) && hasJumped == false)
        {
            playerPosition.Y -= 3f;
            velocity.Y = -4.5f;
            hasJumped = true;
        }

        if (hasJumped == true)
        {
            float i = 1;
            velocity.Y += 0.15f * i;
        }

        if (playerPosition.Y + playerRect.Height >= 450)
        {
            hasJumped = false;
        }

        if (hasJumped == false)
        {
            velocity.Y = 0f;
        }

    }

    public void AnimateRight(GameTime gameTime)
    {
        timer += (float)gameTime.ElapsedGameTime.TotalMilliseconds / 2;
        if (timer > interval)
        {
            currentFrame++;
            timer = 0;
            if (currentFrame > 3)
            {
                currentFrame = 0;
            }
        }
    }

    public void AnimateLeft(GameTime gameTime)
    {
        timer += (float)gameTime.ElapsedGameTime.TotalMilliseconds / 2;
        if (timer > interval)
        {
            currentFrame++;
            timer = 0;
            if (currentFrame > 6 || currentFrame < 3)
            {
                currentFrame = 6;
            }
        }
    }

    public void Draw(SpriteBatch spriteBatch)
    {
        spriteBatch.Begin();
        spriteBatch.Draw(playerTexture, playerPosition, playerRect, Color.White, 0f, origin, 1.0f, SpriteEffects.None, 0);
        spriteBatch.End();
    }

}

```

}

When I move right, the player animates perfectly, but when I move left, depending on what I change the numbers in the

```
if (currentFrame > 6 || currentFrame < 3)
            {
                currentFrame = 6;
            }

```

to, it either is no animation on one frame, or it turns right when he moves, or the player only animates part of it. If somebody could tell me what I am doing wrong, I would greatly apprieciate it. Thanks in advance :) Here is the image:

# Answer
> 1 votes
Change your AnimateRight to:

```
if (currentFrame > 5)
{
  currentFrame = 0;
}

```

And your AnimateLeft to:

```
if (currentFrame > 9 || currentFrame < 5)
{
  currentFrame = 5;
}

```

# Answer
> 5 votes
Let me update this based on your comments:

I'm guessing your right frame animations live between 0 and 3 and your left frame animations are between 4 and 6?

Clearly, as you know already, your `AnimateLeft()` function is bugged. Here, you're setting `currentFrame` to `6`, then on the next loop you increment to `7`. Then on the next update `currentFrame` is greater than `6` (it's `7`), so it's set back to `6`.

It seems more like you'd want something like this:

```
public void AnimateLeft(GameTime gameTime)
{
    timer += (float)gameTime.ElapsedGameTime.TotalMilliseconds / 2;
    if (timer > interval)
    {
        currentFrame++;
        timer = 0;
        if (currentFrame < 5 || currentFrame > 9)
        {
            currentFrame = 5;
        }
    }
}

```

You are incrementing `currentFrame`, and you want to go from frame 5 to frame 9 right? That's how you do it.

I should also note that you should really try to avoid the use of constants like that in your code. For starters you should pull them out and put them at the top of your code with nice names.

```
int RightAnimation_StartFrame = 0;
int RightAnimation_EndFrame = 4;
int LeftAnimation_StartFrame = 5;
int LeftAnimation_EndFrame = 9;

```

And it's always nice to try to generalize stuff like this:

```
public void Animate(GameTime gameTime, int startFrame, int endFrame)
{
    timer += (float)gameTime.ElapsedGameTime.TotalMilliseconds / 2;
    if (timer > interval)
    {
        currentFrame++;
        timer = 0;
        if (currentFrame < startFrame || currentFrame > endFrame)
        {
            currentFrame = startFrame;
        }
    }
}

```

Then you can use this to animate right:

```
Animate(gameTime, RightAnimation_StartFrame, RightAnimation_EndFrame);

```

# Answer
> 0 votes
If you change directions befor timer exceeds interval, the timer does not get reset to 0 so the amount of animation on a changed direction could be unpredictable.

I might try setting the timer to 0 each time the the input poll shows a key down:

EDIT: Actually, it be best if the timer were reset to 0 only when a different key key direction were selected.. But regardless it needs some mechanism to reset to zero when interupted in the middle of an animation.

---
Tags: xna
---


# Question
Title: How to detect what portion of a rectangle a point is in?
Say I have a rectangle and a point inside the rectangle. If the rectangle was split up diagonally, how could I tell which portion the point is in?

Here is a cute little mspaint diagram, where the portions are labeled with letters, and the point is shown with the red circle:

Also, if it helps, I am working in c++

# Answer
You basically just need to check the slope of the line from the bottom two corners rise over run. Here's some pseudocode

```
min = {x:10, y:10 } <- lower left corner of rectangle
max = {x:100,y:100} <- top right corner
width = max.x-min.x
height = max.y - min.y
string quadrant(Point p) {
    // if above-diagonal1, we are in quadrant A or B
    ab = (p.y - min.y) * width > height * (p.x - min.x)
    // if above-over-diagonal2, either quadrant A or D
    ad = (p.y - min.y) * width > height * (max.x - p.x)
    return (ab && ad   ? "A" :
            ab && !ad  ? "B" :
            !ab && !ad ? "C" : "D")
}

```

Here's an implementation in javascript
> 4 votes

# Answer
You can narrow down which quadrant the point is in, check whether the point is above/below center and left/right of center. That gives you 4 cases to check. Then you just need to determine which side of the bisecting line the point is on. A good answer for that is here.
> 2 votes

# Answer
# In short:

Split up the Rectangle into the 4 triangles (quadrant), then find which triangle the point is in.

# Explanation

Say we are given the Rectangle with the x, y, width, and height.

```
TL +--------------+ TR
   |              |
   |              |
   |      C       |
   |              |
   |              |
BL +--------------+ BR

```

We can then find all the points labeled:

```
TL: (x, y)  //topLeft
TR: (x + width, y)  //topRight
BL: (x, y + height)  //bottomLeft
BR: (x + width, y + height)  //bottomRight
 C: (x + width/2, y + height/2)

```

Then we create our 4 triangles (quadrants) using the same notation you have above:

```
a: (TL, TR, C)
b: (TL, BL, C)
c: (BL, BR, C)
d: (TR, BR, C)

```

Using these 4 triangles, check to see if the point is inside, if it is then you found your quadrant.

To find if a point is in a triangle you can use these:

## Method1:

```
  public boolean pointInTriangle(Point p)
  {
    Point a = points[0];
    Point b = points[1];
    Point c = points[2];

    double dot00 = dot(c.x - a.x, c.y - a.y, c.x - a.x, c.y - a.y);
    double dot01 = dot(c.x - a.x, c.y - a.y, b.x - a.x, b.y - a.y);
    double dot02 = dot(c.x - a.x, c.y - a.y, p.x - a.x, p.y - a.y);
    double dot11 = dot(b.x - a.x, b.y - a.y, b.x - a.x, b.y - a.y);
    double dot12 = dot(b.x - a.x, b.y - a.y, p.x - a.x, p.y - a.y);

    double invDenom = 1.0 / (dot00 * dot11 - dot01 * dot01);
    double u = (dot11 * dot02 - dot01 * dot12) * invDenom;
    double v = (dot00 * dot12 - dot01 * dot02) * invDenom;

    if ((u > 0) && (v > 0) && (u + v < 1))
      return true;
    return false;
  }

  public double dot(double x1, double y1, double x2, double y2)
  {
    return x1 * x2 + y1 * y2;
  }

```

## Method2:

```
  public boolean pointInTriangle2(Point p)
  {
    double invDenom = 1.0 / det(points[1], points[2]);
    double u = (det(p, points[2]) - det(points[0], points[2])) * invDenom;
    double v = -(det(p, points[1]) - det(points[0], points[1])) * invDenom;

    if ((u > 0) && (v > 0) && (u + v < 1))
      return true;
    return false;
  }

  public double det(Point p1, Point p2)
  {
    return p1.x * p2.y - p1.y * p2.x;
  }

```
> 0 votes

# Answer
In the case outlined above, take the distance of the point to all four sides of the rectangle, and also take the ratio of the width of the box to the height. If the ratio is greater than one, divide the horizontal distances by it, and if it is less than one, multiply the vertical distances by it. The lowest distance will correspond the triangle the point is is in.

In code: (haXe)

```
static function createBox(offsetX:Float, offsetY:Float, width:Int, height:Int):Void
{
    var box:Sprite = new Sprite();
    var lineThickness:Float = 2.0;
    var lineDefaultColor:Int = 0;
    var lineClosestColor:Int = 0x00CC00;
    var boxwidth:Int = width;
    var boxheight:Int = height;
    var boxOffsetX:Float = offsetX;
    var boxOffsetY:Float = offsetY;
    stage.addChild(box);

    var closest:Int = 0; // top=0, right=1, bottom=2, left=3, for the sides

    stage.addEventListener(Event.ENTER_FRAME, function(e:Event):Void
    {
        var mx:Float = stage.mouseX;
        var my:Float = stage.mouseY;
        //See if the pointer is inside the box
        //        x1                           x2                     y1                      y2
        if (mx > boxOffsetX && mx < boxOffsetX + boxwidth && my > boxOffsetY && my < boxOffsetY + boxheight)
        {
            var ratio:Float = boxwidth / boxheight;
            //                            x1
            var distLeft:Float = mx - boxOffsetX;

            //                             x2
            var distRight:Float = (boxwidth + boxOffsetX) - mx;

            if (ratio > 1)
            {
                distLeft /= ratio;
                distRight /= ratio;
            }

            var minHorizDist:Float = Math.min(distLeft, distRight);
            //                           y1
            var distTop:Float = my - boxOffsetY;
            //                                 y2
            var distBottom:Float = (boxOffsetY + boxheight) - my;

            if (ratio < 1)
            {
                distTop *= ratio;
                distBottom *= ratio;
            }

            var minVertDist:Float = Math.min(distTop, distBottom);

            var minDist:Float = Math.min(minHorizDist, minVertDist);

            switch(minDist)
            {
                case distLeft:
                    closest = 3;
                case distRight:
                    closest = 1;
                case distTop:
                    closest = 0;
                case distBottom:
                    closest = 2;
            }
        }
        else
        {
            //if the pointer is outside the box
            closest = -1;
        }

        //...flash specific drawing stuff...
    });
}

```

Swfup crops the swf, unfortunately, but here's a demo.

complete source, I'd use FlashDevelop and the haXe compiler to build.
> 0 votes

---
Tags: c++, collision-detection
---


# Question
Title: How do I make a low pass filter (average of readings over time) for compass?
I'm making a prototype for android that pulls compass data from the phone. I want to stabilize it so it is less jerky, by taking the average of the last couple of readings.

I have done this for accelerometer readings with great success, but adding every measurement to a queue and then collapsing it and dividing it by the queue size (= calculating the average) but for angles this is different.

If my measurements are for example:

> 350, 359, 360

I could calculate the average as 356.3

But if my measurements are

> 350 359, 1

Then my average is 236 which is a radically different angle.

Is there any way you guys can think of I could deal with this?

# Answer
You could convert each angle to a 2D vector and sum the vectors, then convert the result back to an angle.

In pseudocode:

```
totalVector = [0, 0]
for each angle:
    vector = [cos(angle), sin(angle)]
    totalVector += vector
if length(totalVector) < aSmallNumber:
    # error, angles are all over the place so there's no meaningful average
avgAngle = atan2(totalVector.y, totalVector.x)

```
> 6 votes

---
Tags: geometry
---


# Question
Title: Opengl create tunnel TRIANGLES and texture coords on a 3d path
I have a path, lets say a bezier, or a circle.

I d like to make a continously 3d cylinder (tunnel) on it (R=0.5f)

How can I calculate tha TRIangles (TRIANGLE\_STRIP) coordinate, and the texture coords right?

# Answer
> 4 votes
You need normal and binormal for each point in your curve, as illustrated in this picture as *n* and *b*:

You can calculate the tangent *t* from the curve, it's the first derivative. If the derivative is not available, you can approximate it with a direction vector from previous sample point to the next one. Binormal is simply a cross product from tangent and normal. The only problem is how to define the normal. Normals can be arbitrary, but it should always be on the "same side of the curve" so that adjacent vertices in the tube are close to each other and not jumping around. Four ways to calculate the normal comes to my mind.

1. Manually define also normals for each control point in your curve and interpolate from those.
2. Define an *up*-vector or something similar in the world and calculate the normal from cross product of the up vector and tangent. In this case the curve must not go directly upwards. I used this myself recently, and it seemed to work well.
3. Choose the first normal arbitrarily and calculate the next normals always so that it is as close to the previous as possible.
4. If your curve lies in a plane, which is the case for a circle, you can use the plane normal directly.

When you have the normals and binormals, you can generate the tunnel vertices simply with a linear combination of those vectors.

```
for (i = 0; i < pointCount; i++) {
    angle = 2 * PI * i / pointCount;
    tunnelPoint[i] = curvePoint + (normal * cos(angle) + binormal * sin(angle)) * radius;
}

```

Texture coordinates are simple to calculate if your points are evenly distributed or the stretching is not a problem. If those are a problem, you need to numerically first calculate the length of the curve and then also numerically find the correct texture coordinate for any given point in the curve. This gives the *u* part. *v* part is simply `i / pointCount` in the code above.

---
Tags: opengl, 3d-meshes
---


# Question
Title: Should I call the garbage collector during loading screen?
SO, I read a bit on Garbage Collection lately, out of curiosity, and there is something that is repeated quite often: garbage collection can lead to sudden slow down of the program, depending of the "depth" of the collection.

But in video games, there is a moment where the user can't really notice a small lag: loading screen. So, I thought, it might be useful to proceed to full garbage collection during a loading phase (via Collect()), having to wait a second or two longer should not really impact the user.

My question is, is it really useful, or are there no real benefit to doing this?

# Answer
> 13 votes
### Yes, call it as the last thing you do when loading.

This will maximize the time between the level starting and the first lag due to a GC.

You should also be trying to minimise allocations in general too though so you don't get any more lags during a level.

See Poor performance on 360 and WP7 and Twin Paths To Garbage Collector Nirvana

---
Tags: c#
---


# Question
Title: Using Ninject for DependencyInjection on Xbox, noticable impact?
This *may* be classed as a slightly subjective question but there is very little information on this at the moment, so I just thought I would ask here incase anyone has any experience with this.

I am working on a simple(ish) game for XNA at the moment, but there are quite a few situations where I am wishing I had dependency injection available. Take an example of having a map object which relies upon a tile collection to draw things to the screen, this could be a list of tiles or a spatially partitioned object which would optimise the drawing and update routines. There are lots of other parts where I would rather move the responsibility of binding my application together to a higher level, hence a DI configuration step.

So I know you *can* use Ninject on XNA with Windows/Xbox/Win7Phone, however I was just wondering if you have any noticeable impact (that is the subjective part). As Ninject must store in memory all its possible bindings ready to dish them out whenever required, although most of the instantiation would be done within IFactory based implementations for relevant entities etc, but I am just worried that Ninject may impose a small performance impact upon loading and storing the bindings in memory.

I am assuming the notice is barely worthwhile noting providing you are just binding your topmost elements and your factory implementations and not making it create EVERYTHING for you, but just wanted to know if anyone had used it before on a major project and any pros/cons they found doing things this way rather than just hard-coding your application composition in your game (or other class).

(I wanted to add the Ninject keyword but dont have enough rep to do so on here)

# Answer
> 1 votes
If you only need a very limited set of an IoC's functionality you could simply create your own -- especially if you are concerned about the impact. Then you could design it to exactly meet your needs. It could for instance be solved very easily using a static class (God forbid! ;-) that keeps the references you need.

---
Tags: xna, xbox360, configuration, dependency-injection
---


# Question
Title: Authentication for a multiplayer game via sockets
I'm implementing a custom binary protocol for a new multiplayer game I'm working on. Its a turn-based strategy game so timing doesn't really matter. I've currently got the basic data sync portion of the system complete, and I was wondering how user login/logout and encryption is typically done for MMORPG games or similar.

* Can you recommend a scheme for secure/secret password transmission during login? ( Diffie-Hellman key exchange?)
* How do I implement strong encryption for data packets? (AES 128-bit? .. or whatever scheme this post refers to as "encryption stronger than you are likely to crack")
* Are there datagram format schemes that help to harden the game server to replay attacks, invalid data packets and the like?

# Answer
# Answers

* SRP \- Secure Remote Password - This is based on Diffie-Hellman. The idea is that you can do a **mutual** password check without actually ever transferring the password or any information that can be used to derive it. Even though it's secure over the wire you should still hash and salt your passwords as your server must never store them in plain text.
* The advantage of SRP is that once it completes it also gives you a mutually negotiated encryption key that an attacker would not have been able to deduce given the data you have transferred. This means that you are free to use a symmetric encryption algorithm (like AES) once the user is authenticated.
* Assuming you are using UDP with your own reliable/ordered (connection-orientated) implementation on top of it: encrypt the entire UDP playload - including your 'packet sequence number'. If your system is designed correctly it will automatically reject replayed messages and an intruder won't be able to change the packet sequence number because it's encrypted (thus a replay is possible - but it would be automatically ignored).

# Thoughts

Should your authentication be secure? Absolutely. Make no compromises in terms of security when a password is in question. Thus you should be definitely be considering the first bullet in my answer.

Should your data be secure? Only if it is an in-game purchase/micro-transaction - and then why not just use something tried and true like HTTPS. Encrypting your game traffic is not likely a viable solution for the following reasons:

* It is complete paranoia.
* It is going to add CPU time overhead on your server, unless you can purchase (expensive) hardware encryption modules.
* It doesn't matter how much security you provide for your data over the wire - someone could hijack the client process and intercept messages the moment before they are encrypted and sent. This is not only a possibility but infinitely more possible as it as **substantially** easier to inject code compared to intercepting packets. If you are doing this for cheat prevention you are completely and utterly wasting your time.
    + In terms of password security there is unfortunately nothing you can reasonably do about a hijacked system, the client has become hostile. Blizzards WoW dongles are designed to deal with this - but I am not sure how secure that is (especially if you leave it plugged in).

**Please,** if you are encrypting for cheat prevention abandon it. You are going to come up short - I gave you have the information in the event that you are not. Remember that you can selectively encrypt packets by the first byte in the packet being and indicator of whether the rest is encrypted: although, once again, I would stick to HTTPS if you need to do things like credit card transactions: they are extremely infrequent and HTTPS is designed by experts - unlike something you or me designed.

All of that said, Blizzard do actually encrypt their WoW traffic. The main reason this broke is because someone, who is likely a complete amateur, decided that they would try their hand at a home-grown encryption algorithm; this panned out really well. Even if you do use industry standard algorithms there is a good chance that someone will reverse-engineer your code and simulate it - once the client enters their password there is no telling that an unsupported system is connected.
> 15 votes

# Answer
I think my last comment to Jonathan's otherwise excellent answer is worth expanding into an answer of its own:

If you don't have a lot of crypto experience, you shouldn't try to design your own encryption layer if you can avoid it. If you *do* have a lot of crypto experience, you should know better than to design your own encryption layer if you can avoid it.

Instead, try to find an existing, standardized and well tested crypto library that does what you need. In your case, I'd recommend **GnuTLS**, which, according to Wikipedia, provides both TLS-SRP authentication (RFC 5054) and secure UDP communication with DTLS (RFC 6347). The former takes care of logging in, while the latter protects the secure channel thus formed from both eavesdropping and active attacks, and can even protect you from replay attacks.
> 2 votes

---
Tags: multiplayer, security, encryption, protocol, binary
---


# Question
Title: Strategy/City Builder browser game - technical details
I actually have multiple questions into one. Hopefully someone can hit all of them.

I wanted to give a try at a massively multiplayer web based game. Basically, the game would have similarities to Evony, or Eve Online (a much scaled down version). The idea is it would be a mostly real time city builder (like Evony) that allows complex actions between players (like Eve Online but without the graphics and much scaled down). It would sort of be like a database game. I want it to be able to support around 500 people simultaneously online off one server.

However, I have multiple issues that I want to pin down before I actually start writing the code.

1. Continuous database updating

The database has to be continuously updated on a small time interval to reflect the passage of time in the game verse. Furthermore, the effects of all actions will have to be calculated as well. Right now I'm thinking about using mysql with events using the innoDB engine to do this. Is there a better/faster approach to this?

1. Continuous graphical updating

Certain details (such as "time till completion" etc when building something) need to be continuously updated on the user interface. I'm thinking about having each page in the user interface continuously make ajax calls for the information. Again, is there a better/faster way?

Thanks

# Answer
# Database Updating

You should really use a message queue \- chances are your SQL DB will fall over when you hit it with this level of concurrency (deadlocks etc.). I have heard that RabbitMQ is quite good. Remember that once your data is in the MQ it's as good as it being in a database - MQs are just designed to process a lot of messages and allow other systems to take it easier under load and have as much ACID assurance as SQL does. So just queue your player commands into one end and update your DB when you dequeue off the other.

*You might find PostgreSQL performs better, at this point critical optimizations that most other DBs have are only experimental in MySQL.*

# UI Updating

In general if you should use one of several methods depending on what the server and client support (in order of preference):

* WebSockets
* Server Events
* Forever Frame
* Long Polling
* Polling (your current idea)

Frameworks like SignalR deal with all this complexity for you (really, SignalR is just pure awesomeness).

# Combining the Two

In terms of your question as a whole here is how I would deal with things. A throbber would be anything, possibly make the building/whatever transparent or display a spinner over it. It basically tells the player - "if you close your browser now these things might never happen".

```
Player issues command --> Update player UI with throbber --\
                      /------------------------------------/
            Send command to server
                      |
   Remove throbber when server acknowledges
                      |
      Enqueue the command into the MQ
                      |
                      +<------------------------\
                      |                         |
                      V                         |
            +------------------+                |
            | RABBIT MQ        |                |
    /------>|                  |                |
    |       +------------------+                |
    |                  V               Additional commands?
    |                  |               e.g. update building % done
    |                  |                        |
    |    Perform logic associated with command -/
    |                  |
    |           Update database
    |                  |
    \------Acknowledge MQ message
                       |
                       |
        Send message to interested/online
             players via SignalR
                       |
                       V
                     Babes

```
> 7 votes

---
Tags: mmo, databases, sql
---


title: libGDX Multitouch Controls

text:
# Question
Title: libGDX Multitouch Controls
Has anyone had any trouble implementing multitouch on-screen controls in libGDX, such as multiple joysticks? I've tried and I can't seem to get libGDX to play nice with multitouch/multiple pointers on screen at once. I am currently using a `Stage` with my joystick class extending `Actor` and they are detecting hits just fine, but when I touch one it interferes with the other. Any examples, or tips? I should note, that when I am using just one of the joysticks that they work as intended.

# Answer
> 2 votes
Turns out this was a device independent problem (See comments above) and the issue posted to Google Code can be found here. There was actually no problem with the code in libGDX. I'm Posting this as an answer rather than deleting so that people like me can find the answer before ripping their hair out.

---
Tags: android, java, input, libgdx, multitouch
---


# Question
Title: Help learning how to create tile based games in java and or C#
I want to get into 2d based gaming design and creation however, I really do not know where to start. I know java and c# but not how to use them in an efficient way. I'd like to create 2d tile based games such as mario or pokemon. Is there a good place to learn how to do this?

thanks,

Euden

# Answer
> 1 votes
Even though your question is a bit abstract, I myself had the same question some time ago.

This is what I consult you to do:
First of all, try making a small game, like a board game. I for example did my version of Reversi, in Java. Later on I moved to Snake. And now I'm developing my own maze based dungeon game.

Try this site to see some examples of some 2d games made in Java.

**Edit:**
A quick google search led me here, where you can view the source code of a "super mario" like game in C.

Hope it helps.

---
Tags: 2d
---


title: Efficient Bullet Firing Class

text:
# Question
Title: Efficient Bullet Firing Class
I've been struggling with this for a while. I have been trying to create a bullet pool class for a game I have made that doesn't cause a significant fps drop.

I have tried creating a bullet pool and have also tried dynamically creating and deleting bullets, both of which drop the fps of the game around 10-15.

I ran a test a few days ago and just put a return statement in the bullet pool's `firebullet` function, which represented the logic leading up to this, function calling, etc.

This only dropped the fps 2-4. If I can fire bullets without dropping the fps more than another 2-3, I would be satisfied. My bullets are `autorelease` objects that are a subclass of a `ccnode`.

I create a `ccsprite` and a box2d b2body for each one. I am working on the ios platform. Any thoughts on how to make this more efficient? Has anyone managed to do something similar to this?

# Answer
> 2 votes
Your idea about creating a pool is good (if you actually know that the creation/destruction is what's dragging down your fps) but not implemented efficiently. Simply use an array of pointers, no need for the NSMutableArray which is not useful at all. Create a global variable which is an array of pointers to your bullet objects. During startup loop over the array and assign them the individual bullet objects. Add a boolean flag to each bullet object which says if the bullet is in use or not. You avoid memory fragmentation and more importantly, memory operations at all.

This mechanism has the drawback of having a linear search when adding a bullet to the scene because you need to search for a bullet object with the boolean flag set to false. Since bullets tend to live not very long, start the search from the index position of where you created the last bullet + 1 (and wrap around in the array). But for 20-30 objects the linear search should not really be a problem, I've had linear searches for several arrays of 50-100 and that's never the bottleneck. You might want to keep a total counter at least for debug versions to know you don't ever overflow the array of active bullets and keep looping forever searching a valid position.

Now, if even *this* is too slow or you are scaling to thousands, I would ditch objects and create an array of structures which guarantees memory cache locality. Also, the boolean flag saying an object is free/used would be moved to a separate array. Having all the booleans in a separate structure helps the cache locality and you will have less CPU penalty than jumping around the whole structure block looking for the correct boolean offset (you could even use bit arrays for the separate on/off structure).

Having said this, I've rarely found my *logic* loop taking more than 20-30% of the time allocated for a frame, most of it going to the graphic loop, so I would first really look at the general performance of your game and see if you are not doing something wrong somewhere else. Remember that optimization is the root of all evil, be evil only in moderate amounts.

# Answer
> 1 votes
Use a swap / remove system. When you iterate over your list of current bullets, you will encounter one which is dead. Swap this with the bullet at the end of the list, and decrement the count of exiting bullets. This way, your pool of bullets will always be contiguous. If you want to go for greater efficiency, use an SoA rather than AoS system; your bullets are stored as a series of parrallel arrays, so one array for all the positions, one for all the velocities, and so on. This guarantees cache efficiency.

---
Tags: iphone, box2d, cocos2d-iphone, ios, bullet-physics
---


# Question
Title: Automatic weapon recoil with that "Counter Strike"-feel
How would you do it?

I already found this function for an impulse (helped by math.SE). It works for single shots, but not for automatic weapons.

Any ideas?

# Answer
Just combine the individual shots' impulses? Something like this:

You could of course add realism:

Particularly when firing on automatic, humans have a tendency to get used to the recoil. Basically, there is some factor that decreases the recoil impulse down to some point. The first shot recoils hard and the following shots add to the kick, but each with decreasing force, until some saturation in the soldier's capability for holding the gun steady is reached. This could be done with a function that modulates that impulse function based on the time since the last shot and the number of shots taken in the same chain of automatic fire.

A slight random factor is also always present in reality.
> 6 votes

# Answer
well basically, just have some kind of (semi-randomized) rotation that will cause the gun to jerk in an upward direction, and just apply it for every shot
> 3 votes

---
Tags: mathematics, physics, first-person-shooter
---


# Question
Title: XNA spritebatch drawing to the centre of screen
I have bit of a silly problem.

Is is possible to use SpriteBatch.Draw() method to draw to the centre of screen using coords from the beginning of window (So resolution 800x600 would use 400;300) instead of coords from the beginning of the Game coordinates? Right now I'm doing calculations to keep the object in the centre of screen but I'm wondering if theres easier method how to solve this.

I tried googling, but either this hasn't been discussed anywhere or I'm using wrong keywords in search.

Thank you.

# Answer
I find your question very confusing but I believe that this will do what you want. Assuming you want the center of the object to be draw to the center of the screen irregardless of resolution.

```
var screenCenter = new Vector2(
    GraphicsDevice.Viewport.Bounds.Width / 2,
    graphicsDevice.Viewport.Bounds.Height / 2);
var textureCenter = new Vector2(
    Texture2D.Width / 2,
    Texture2D.Height / 2);
SpriteBatch.Draw(Texture2D, screenCenter, null, Color.White, 0f, textureCenter, 1f, SpriteEffects.None, 1f)

```
> 5 votes

# Answer
The best way to do this would be to use the GameWindow class found in Window member of your Game class.

```
Vector2 ScreenCenter = new Vector2(
    Game1.Window.ClientBounds.Width / 2,
    Game1.Window.ClientBounds.Height / 2);

```

That should get you the center point for the SpriteBatch object.
> 1 votes

# Answer
You can get the width and height of the window from the Graphics device manager. Assign the values to some variables and draw based off of that.

```
 width = graphics.PreferredBackBufferWidth;
 height = graphics.PreferredBackBufferHeight;

```

And then to draw it you would just base it off those values:

```
spriteBatch.Draw(texture, new Vector2(width / 2, height / 2), Color.White);

```
> 0 votes

# Answer
If you want to draw your object in the very center, u can use (pseudocode, see above for implementations)

```
(screenWidth - objectWidth) / 2;
(screenHeight - objectHeight) / 2;

```
> 0 votes

---
Tags: xna, c#, camera, coordinates
---


# Question
Title: What is the best way to handle "Fangame" licensing?
( I understand that this is a subjective question. My goal is obtaining some personal feedback from other game designers )

I wish to develop a digital version of an existing board game. What would be the "best" course of action regarding contacting the original game designer?

Some additional information:

* This is not a question about copyright. My understanding is that this is something that I can do as long as I do not use copyrighted material.
* I have a recently obtained a masters in informatics and computing engineering and have a serious interest in pursuing a career in game design and development.
* The game in question is a board game for which there is no digital version on my medium of choice.

# Answer
Random thoughts...

**Contact them before you do any work**

If you do all the work and THEN contact them and they say no, you now have a game you can't do anything with. A good learning exerciser, but not a very efficient way to run a business if you see yourself as one. If they say no, be mentally prepared to rm -r -f the code and walk away and move on to some other idea.

On the other hand if they say yes to something before you start, then you can proceed and not risk all your work is for naught.

If you ignore their "no", then you are really at risk of legal trouble. The act of asking will put you on their radar big time.

And what if you just don't ask? Maybe they never know, maybe they do but don't care, or maybe they just take you to court. Getting taken to court is like them saying no, with the added fun of you probably owing them something.

**Are they a publisher?**

See if they accept submissions from outside developers - something a lot of publishers would do by nature of being a publisher. If they do, then present your electronic version of their game as a proposed product. Again, because your proposal is so tied to their product, them saying "no" leaves you with not many options.

One way to approach them would be to ask them if they would be willing to let you do a prototype, with the agreement that they get to make the decision whether to allow it or not. Then at least you've decreased the risk of throwing everything away. If you do this though, make sure that they don't end up owning your demo. You don't want them to say, "No thanks" and then turn around and use your work for free and leverage it to their advantage.

**Consider asking to license their content**

One way to present the idea of developing the game is to ask them if they would be willing to license their IP for a project. The terms of the license might include money up front, a percentage of income from your work, or a combination of the two. It also no doubt means you will have zero path to using their IP except through them. You're not going to be able to open source your game if you decide to stop working on it for example.

**Don't ask them to take risks**

When you pitch something to them, make sure it's you taking on the risk, not them. Or at least be willing to equally take on risk. Don't ask them to pay you to develop the game for example. Set it up so that if it does fail, you lose, not them. Someone with strong business and negotiating savvy could probably work that a bit more evenly, but it sounds like you're not bringing a lot to the table. I.e., you're not a studio with 10 years experience and 5 published titles.

**Do your homework**

Has anyone ever done a version of this game before? Maybe the company did it internally and failed, or it was deemed not a good idea. If so, find out why if you can and learn. Maybe a third party was developing the game in the past and went out of business? Maybe the company just plain hates video games and are board game purists? Get names of people at the company, read their Facebook and Twitter posts, blog posts, and see if there is anything about them on Moby Games. Find out if they ever talk about games and in what way (positive, negative, wishful, cynical, etc.). It's not spying, it's homework that may give you a big hint about how to present things.

**Be careful about the impression you create**

As an additional comment, be very careful how you present yourself. You sound like you're not yet a game developer, but want to be one. If you tell them that, they may not see you as a viable author. On the other hand if you have examples of existing work to show them, or prototypes of concepts that aren't for release, this may show them you are capable. Have something you can show them as an example of what you can do. Additionally if you are thinking of selling this game yourself (with their permission), be prepared to have a business plan.
> 3 votes

# Answer
There are several cases before in both people having or not having problems with the owners of the game. The most known one is Vassal Engine, which supports a lot of game modules playing games from a lot of different companies.

Rule of thumb is that you should not automatize actions, the game should be played online the same way it would be played physically so it is not actually a better version; and leave the rules or some skill descriptions out so the game is unplayable unless someone has the original game (or has decent googling skills). If you can replace the assets and the game is not from Fantasy Flight Games you are pretty safe ignoring this RoT.

And to be honest if all you want is to play the game I'd save myself the hassle and remake it in Vassal itself, or in GameMaker. If you want to learn, pick an engine of your choice like XNA, Cocos2D or SDL and stick with it.
> 4 votes

---
Tags: licensing
---


# Question
Title: Transform coordinates from 3d to 2d without matrix or built in methods
Not to long ago i started to create a small 3D engine in javascript to combine this with an html5 canvas.

One of the issues I run into is how can you transform 3d to 2d coords. Since I cannot use matrices or built in transformation methods I need another way.

I've tried implementing the next explanation + pseudo code: http://freespace.virgin.net/hugo.elias/routines/3d\_to\_2d.htm

Unfortunately no luck there. I've replace all the input variables with data from my own camera and object classes.

I have the following data: An object with a rotation, position vector and an array of 4 3d coords (its just a plane) a camera with a position and rotation vector the viewport -\> a square 600 x 600 surface. The example uses a zoom factor which I've set as 1

Most hits on google use either matrix calculations or don't implement camera rotation. Basic transformation should be like this: screen.x = x / z * zoom screen.y = y / z * zoom

Can anyone point me in the right direction or explain to me howto achieve this?

edit: Thanks for all your posts, I haven't been able to apply all this to my project yet but I hope to do this soon.

---

Ok after playing around a while some issues still remain. I've created a new projection matrix:

```
    var w = (2 * nearPlane) / viewportWidth;
    var h = (2 * nearPlane) / viewportHeight;
    var q = farPlane / (farPlane - nearPlane);

    this.ProjectionMatrix = $M([
      [w, 0, 0, 0],
      [0, h, 0, 0],
      [0, 0, q, 1],
      [0, 0, (nearPlane * farPlane) / (nearPlane - farPlane), 0]
    ]);

```

where viewport = 600 * 450

and near plane = 0.5 and far plane = 500

the original code for drawing the vertices is this:

```
 var comboMatrix = world.WorldMatrix.x(camera.ViewMatrix);
    for (i = 0; i != this.NumberOfPolygons; i++) {
        var transformedVertices = new Array(verticesPerPolygon);
        var valid = new Boolean(1);
        for (j = 0; j != verticesPerPolygon; j++) {

            currentVertex = this.Mesh[i][j].x(comboMatrix);

            currentVertex.elements[0][0] = currentVertex.elements[0][0] / currentVertex.elements[0][2];
            currentVertex.elements[0][1] = currentVertex.elements[0][1] / currentVertex.elements[0][2];

            if (currentVertex.elements[0][0] < -1 || currentVertex.elements[0][0] > 1 || currentVertex.elements[0][1] < -1 || currentVertex.elements[0][1] > 1) {
                valid = new Boolean(0);
                break;
            }

            // Process Viewport Mapping Transformation
            currentVertex.elements[0][0] = currentVertex.elements[0][0] * 300 + 300;
            currentVertex.elements[0][1] = -currentVertex.elements[0][1] * 300 + 300;

            transformedVertices[j] = currentVertex;
        }

        // Draw the polygon
        if (valid == true) {
            this.DrawQuad(context, transformedVertices, true, new Boolean(0), new Boolean(1));
        }
    }

```

which kinda works since the letter H is drawn on my screen. Moving the camera however makes parts of the letter stop being drawn whenever one of the vertices is outside a 300 * 300 region. I'm assuming this has something to do with a very basic implementation of a projection in these lines:

```
            currentVertex.elements[0][0] = currentVertex.elements[0][0] * 300 + 300;
            currentVertex.elements[0][1] = -currentVertex.elements[0][1] * 300 + 300;

```

Can anybody help me out howto change this piece of code so it works with my projection matrix?

I've tried removing the last 2 lines and changing transformedVertices\[j\] = currentVertex; into transformedVertices\[j\] = currentVertex.x(projection); with no result.

# Answer
**Linear Algebra Library**

Although you can do all the calculations without using matrices, using them makes everything *significantly* easier. For starters, if you don't want to implement matrices and vectors yourself, I've successfully used the following library before:

Sylvester - Vector and Matrix Math for Javascript

You can just copy and paste the packed version of the library at the top of your code - it's a one liner.

If after this you still intend to do this without matrices, the process is pretty much the same as I'm going to show, but you'll have to unroll all of the matrices multiplications yourself into their own separate expressions, and run them separately.

**Example**

As for an example of how to use it, I've digged up some old code of mine which you can try below:

http://jsfiddle.net/JMa9b/

I'm not sure how much that will be helpful to you though. The code is a mess - it was done many years ago when I was just starting to learn about 3D, and it was pretty much just me messing around trying to get some 3D image rendered from scratch. Also, I didn't even know Javascript, so I was just making it up as I progressed, so disregard anything that looks wrong language wise.

**More Info**

The most relevant is the way I calculate the world matrix that is rotating the object:

```
var cx = Math.cos(rotX);
var sx = Math.sin(rotX);
var cy = Math.cos(rotY);
var sy = Math.sin(rotY);
var cz = Math.cos(rotZ);
var sz = Math.sin(rotZ);

var rotXMatrix =$M([
  [1,0,0,0],
  [0,cx,sx,0],
  [0,-sx,cx,0],
  [0,0,0,1]
]);

var rotYMatrix = $M([
  [cy,0,-sy,0],
  [0,1,0,0],
  [sy,0,cy,0],
  [0,0,0,1]
]);

var rotZMatrix = $M([
  [cz,sz,0,0],
  [-sz,cz,0,0],
  [0,0,1,0],
  [0,0,0,1]
]);

var translationMatrix = $M([
  [1,0,0,0],
  [0,1,0,0],
  [0,0,1,0],
  [posX,posY,posZ,1]
]);

worldMatrix = Matrix.I(4);
worldMatrix = worldMatrix.x(rotXMatrix);
worldMatrix = worldMatrix.x(rotYMatrix);
worldMatrix = worldMatrix.x(rotZMatrix);
worldMatrix = worldMatrix.x(translationMatrix);

```

Adding scaling would have been pretty easy too. For instance, for a uniform scale, it would be something like:

```
var scaleMatrix=$M([
  [scale,0,0,0],
  [0,scale,0,0],
  [0,0,scale,0],
  [0,0,0,1]
]);

```

The most important thing is that when creating the `World Matrix` for your objects, you must multiply these individual matrices in the correct order, which is scale, rotation and translation.

As for the `View Matrix` for your camera, it's somewhat similar to the World Matrix, but everything is done the other way around. You negate the rotation angles and the positions , and multiply the matrices together in the *inverse* order as the one above.

I got the formulas from here by the way (they can be slightly different in OpenGL though).

**Notes on Perspective**

For the perspective projection I'm simply taking the view space X and Y components and dividing by Z. That works in a simple "toy" case like this, but if you want to deal with other parameters such as the aspect ratio, field of view, near and far planes, etc, you'll want to do it with a matrix too. For example, a matrix such as this (taken from DX documentation):

```
2*zn/w  0       0              0
0       2*zn/h  0              0
0       0       zf/(zf-zn)     1
0       0       zn*zf/(zn-zf)  0

```

The way to use such a matrix is that you take your coordinates in view space (after applying the world and view matrix) with an added 1 as the fourth component, i.e. `(x,y,z,1)`, multiply that by the projection matrix, and then *homogenize* the result back into 3D by dividing everything by W, i.e. `(x,y,z,w)=(x/w,y/w,z/w)`.

And by the way, the simplest perspective matrix possible is something like:

```
1 0 0 0
0 1 0 0
0 0 1 1
0 0 0 0

```

Which basically discards the W component and stores Z on it. Then when you homogenize the result is the same as dividing by Z, which is what I did directly in my code.
> 7 votes

# Answer
Two alternatives I'd recommend:

**A)** Calculate all the matrices by hand. It doesn't require any matrix4 classes or anything, just a lot of math. You'd have to calculate something like

```
NDC_Coordinates=PerspectiveDivide(Projection*Cameraview*Modelview*Vector)

```

The `Modelview` one is optional, so it'll be the `CameraView` that will probably contain all the annoying rotation and translation stuff.

**B)** Make a *Doom*-style renderer. I won't elaborate much here because there are tons of resources online:
> 1 votes

# Answer
Well those are for 3D transformations/rotations, to convert from 3D to 2D (to draw on a screen), xp = x * scale / (z + scale) yp = y * scale / (z + scale)

where scale is a depth scaling factor (500 for example) after that, generally you would add that to half the screen dimensions to center it

read above for in 3D manipulation
> 1 votes

# Answer
Another alternative other then Sylvester which is already mentioned is gl-matrix which is meant to be a fast implementation of matrices vectors and quaternions in javascript. That should be most of what you need.
> 1 votes

---
Tags: 3d, javascript, matrix
---


title: ID3D Query Where should I put them?

text:
# Question
Title: ID3D Query Where should I put them?
I'm currently trying to time different parts of my rendering to see how long it takes. I've got the queries working and I'm getting some results.

My question is where should I actually start and end the query?

If the query is wrapped around the `ID3D11DeviceContext::VSSetShader` function will this tell me how long it took to set the vertex shader? Or will the tell me how long it took to call the function in c++?

I am trying to query the GPU and as far as I know the pipeline isn't executed until I call the `ID3D11DeviceContext::DrawIndexed` function.

Do I need to do the queries in the shader code?

# Answer
The timestamp queries measure time on the GPU, not the CPU. So if you wrap them around a VSSetShader call it's measuring the time required by whatever that call translates to on the GPU.

The GPU pipeline may not actually start running until you call Present. Doing a draw call probably doesn't make the GPU do anything immediately; it queues up a command into an internal buffer, which is not actually handed off to the GPU until required e.g. by Present. Actually, everything in the ID3D11DeviceContext class works this way, including queries.

The typical way to use queries would be to fire off a bunch of them in one frame and then reap the results two or more frames later. You use multiple sets of queries to get data about all frames (i.e. double-buffering). I actually wrote a detailed article about using GPU queries for timing, which explains all this in detail and includes sample code.

I don't understand what you mean by "do the queries in the shader code".
> 5 votes

---
Tags: directx, timing
---


# Question
Title: How do music and ambient sound influence gameplay flow?
I've been thinking about whether music helps or distracts from achieving "flow" when playing a game. Does it enhance or distract from it?

*Angry Birds*, *Temple Run* and *Doodle Jump* seem to achieve great flow without music (or with ambient/percussion-only music). But then again, some games use music but seem to also achieve flow, such as *Tiny wings*.

Has this been researched? How can I maximise flow with in-game audio?

# Answer
It's essentially just a balancing act and can go either way. It's not really affecting any 'flow' as you say, but more the feel/ambiance of a game. Say you are working on a game and currently it has no background music. If there is a long span between any sort of action when you are just running around, you would probably want to add something to fill that space because it might feel a bit boring just listening to your footsteps. If you are making some sort of action game, it could help with suspense to add in some heavy drum hit changes when something happens.

You could think of game music just like they do with movies. There are times when the music fits, and times when it doesn't.

For games such as Angry Birds and Doodle Jump, there is really no need to add music as it could feel a little distracting while you are concentrating.
> 2 votes

---
Tags: music, user-experience
---


title: Bounding boxes in octrees

text:
# Question
Title: Bounding boxes in octrees
I've seen that octrees are often used for things like frustum culling and collision detection in 3D. But I'm just not sure how the algorithm works at all. Surely the whole principle of the octree breaks when you try to use bounding boxes, because any given box could be stored in one node but actually overlap the space represented by another node. In addition, I'm not sure how this can possibly work for looking up bounding boxes rather than points, because again, you could be stuck looking up into virtually all the nodes, defeating the purpose.

So how on earth do octrees cope with bounding boxes?

# Answer
> 13 votes
An Octree (3D) uses the same concepts as a Quadtree (2D). If you read and understand the wikipedia article on Quadtrees, you should be able to apply the same concepts into 3D.

Both of these trees allow you to use area-based lookups that can greatly reduce the number of comparisons required to figure out what objects are in a certain area. This can be useful for vis-culling, or even for collisions, depending on your game.

The basic concept is that the world-space is divided up into "buckets": squares for 2D or cubes for 3D. With an empty world, you start with a single square or cube bucket that covers the entire world. As you add objects to the world, you start at the root node and work your way into the tree based on the location and size of the object. If the destination bucket reaches capacity, you subdivide it by splitting squares into 4 smaller squares (Quadtree), or splitting cubes into 8 smaller cubes (Octree). Each object you add to world is only inserted as deep in the tree as it can physically fit completely inside the bucket's bounds. If an object does not fit inside the bounds of the current bucket, you must move the object to the smallest parent bucket that it does completely fit inside. Using trees like this allows you quickly disregard massive chunks of your world with only a few bound checks, instead of comparing against each object in your world.

Note that using either a Quadtree or Octree is overkill if you do not have a lot of objects in your world. There are also open-source solutions to both.

# Answer
> 3 votes
n-trees are the most famous but not the *only* spatial partitioning system available. There are many, many others. A bit more information about the data you have would go a long way toward finding the best choice. Do your boxes change size, or move around? How big are they? How many are there? Do you have a lot of insertions / removals?

---
Tags: collision-detection, algorithm
---


# Question
Title: Writing via content pipeline in Xbox game project
I'm creating an Xbox application and I have this problem with the content pipeline. Loading .xnb files is not a problem but I can't seem to find any helpful tutorials on writing via the content pipeline. I want to write an XML whenever the user presses a custom made "save" button. I've searched the web for "saving game sate" etc. but so far I haven't found a solution for my case.

So, summarized: is there a way to write data (in XML format) via the content pipeline, if my Save() method is called?

Cheerz

# Answer
## No

You can't save data on the xbox via the content pipeline.

You can however use other methods (standard .net once you've got a file stream). See here for an example: https://stackoverflow.com/questions/3723287/good-example-of-xna-4-0-to-save-game-data

See also: http://robotfootgames.com/xna-tutorials/92-xna-tutorial-savingloading-on-xbox-360-40

---

The content pipeline is for build time files (they are compiled).
See What is the content pipeline (MSDN).

It works well when you want to perform a lot of pre-processing to go from your original file (maybe an image file) to your runtime class (like a Texture2D with mipmap levels), but that's not the only way to load files on the xbox (so you don't have to save to the XNB format).
> 2 votes

---
Tags: xna, xna-content-pipeline, xbox, savegame
---


# Question
Title: Why use random numbers when it comes to rewards and stats?
Many games use random numbers for things like attack damage, gold loot, or monster type being spawned. It is obvious that random numbers allow you to generate content to make games more re-playable, but I am talking about specific things. For example: In DOTA, when you kill a monster you get a random amount of gold in between x and y where x and y never change. When you attack anything you have a chance to do damage within a range such as 52-60. How would making the gold drops static change the game?

I feel like the random numbers enhance the game-play, but I am having trouble understanding why. Does anyone know any reasons why random numbers can make game-play better when used with things like damage or loot? I'm hoping for answers that don't attribute it to luck being a good thing.

# Answer
> 50 votes
I want to start by making a distinction between *frequent* random elements and infrequent ones.

If you're playing a game where you attack something once every 5-30 seconds, then damage happens frequently. If you're playing a game where you attack less frequently than that, maybe once every minute, then it is *not* frequent.

As an example, table-top RPGs, by the nature of being a board game played by human beings who have to do math and talk to each other, does not qualify as "frequent". Your RPG gaming group would be exceedingly fast if you make an attack roll every 1 minute; you're probably looking more at 3-5 minutes. And that's just for the time you're in combat; the time spent out of combat involves no attack rolls, and it can take just as long. So maybe half of your RPG time is spent out of combat (depending on the group, of course). Let's say you get one attack roll every 10 minutes.

Compare this with any videogame RPG. In fact, let's go straight for Diablo. In a 4 hours session, how many attacks have you made against monsters? In a 4 hour session, you've probably killed more stuff than the table-top group even *encounters* in an entire campaign.

What does this mean? Well, for the table-top player, each roll *matters*. It matters a *lot*. Each roll is precious, so you spend a lot of time maximizing the potential of each roll. You spend time acquiring weapons, items, and buffs to make each roll matter as much as possible. Those 9.5 minutes between attack rolls are there to ensure that when it comes time to roll for attack, you get the best bonuses and circumstances possible.

Some table-top players have dice superstitions (though some only do them in jest). Dice are hallowed among some table-top players, for they live and die based on them.

For the Diablo player, the random element means... nothing. Each roll doesn't matter that much, because 2 seconds later, you'll just make another one. If that attack did minimum damage, that's fine because you're about to make another one.

The only time it might matter is that you might run into a streak of bad luck. But really, how can you notice when you're making attacks once every 2 seconds, and many of your attacks are hitting a half-dozen monsters? Can you truly say that any particular death you may have suffered was due to bad damage rolls, rather than just too many enemies all attacking you?

Therefore, I submit the following idea:

* In order for the random element to truly matter, it *must* be infrequent.

Poker is a good example. How long does it take for a hand to play out? 2 minutes or so, maybe 1.5. That's long enough to really consider the statistics of the matter. You have time to think about it, make decisions around it, etc. And to do that, you need *time*.

So if it doesn't matter, why does Diablo have random damage? My guess? Because that's how table-top RPGs did it. Simple idolatry: game developers looked at table-top games and just copied them without thinking about whether it actually mattered anymore.

Indeed, you can see how poorly this is done by looking at the ranges of damage. In table-top D&D, your damage range is *huge*. A 1d20 weapon has an absolutely massive damage range. It could hit as as ineffectively as a 1d4 weapon. Or it could hit harder than a 2d8 weapon. You don't know, and you won't know until you roll.

What does a large damage range give you? This is where you start getting into psychology. At this point, it's truly gambling. The player wielding a 1d20 weapon *wants* that 20. He can smell it. But he's not going to get it. He's not going to get it often. But sometimes he is. And sometimes, not always, but *sometimes*, that 1d20 weapon will hit big when he needs it.

And sometimes, you'll roll a 1 when you really needed high damage. The highest of highs and the lowest of lows.

What is the most consistent damage weapon you can get in D&D? Maybe a 2d6 weapon; very consistently rolls 7-8s. But a 1d20 averages 10.5s, 2d10 average 10.75 on a bell-curve, and 2d12 averages 12.75 on a shallower bell. If you don't want to gamble in D&D, you're going to have to settle for lower damage. It may be more consistent, but it's lower.

Notice that once you start giving weapons +X bonuses, effectively increasing the minimum damage, the preferred weapon changes. That 2d6 weapon with a +4 bonus is in many ways better than a 1d20+4 weapon.

Videogame RPGs (unless they are direct ports of D&D or some other table-top rules) will have much smaller damage ranges. They'll have the equivalent of 1d10+40 damage. A large base damage, but with some small variation at the top.

Gambling in this system just isn't as important. The reason why is quite simple: a 1d10+40 weapon is guaranteed to do at least 41 damage. It might do 50, but that's only 9 damage up from 40.

In smoothing out the damage curve, it takes away the lowest of lows. But it *also* takes away the highest of highs. Can you imagine cheering that your 1d10+40 weapon did max damage against a dragon with 500 Hp? Now imagine your 1d20 weapon did max damage against a 100 Hp Beholder. That's a pretty big difference.

Therefore, I submit the following idea:

* In order for the random element to truly matter, the range of values must be *large*, relative to the smallest guaranteed value.

So, why is the gold looted from a monster in DotA random? Because it's "supposed" to be random. Not because of any clever design, meticulous planning, whatever. You could make it not random and change virtually nothing about how the game plays out.

Yes, you would be able to know for a fact how many enemies of that type it takes to get the money to buy X. But since the range distribution is so small, you already know the *maximum* number you have to kill. So you must have a plan to deal with the eventuality that you will need to kill that many. Therefore, all that changing it to a fixed number does is turn it from a probability into a certainty.

Let's say something costs 250 gold. So, worst-case, that's 5 monsters that drop from 52-60 gold. But best-case, that's... 5 monsters. So if they dropped 56 gold, it would change *nothing*.

But let's say you're talking about a 1000 gold item. Worst-case, that's 20 monsters. Best case, that's 17. On average, it's 18. But, since it takes so many monsters, the highs and lows will average out. So you're much more likely to need 18 than you are to need 20. Again, changing it to the average changes *nothing*.

The ultimate evidence of this can be seen in the various WarCrafts. WarCraft 2 used random damage, with a large base and a smaller range. So did WarCraft 3.

And while it owes a very great deal to WarCraft 2 in terms of design, StarCraft specifically has *no random damage* at all. The only random numbers used in StarCraft (multiplayer) matches are when attacking high ground.

You might have heard of StarCraft: the single most widely played eSports game *in the world*. More than WC2 and WC3 put together.

To summarize, I would say this. If you want random elements to matter:

1. Make them infrequent, so that the player plans around the random events and can anticipate them.
2. Make the range of randomness broad, so that the player is actually gambling and can get into the spirit of that psychology.

# Answer
> 33 votes
There is one very simple, and very good reason for why games use random numbers for rewards. The Skinner Box. Basically, what this says is that humans (and other animals) get a lot more endorphins when rewards are randomised than if they're either always the same, or if there's a (very obvious) sequence. More endorphins mean people are happier, and that often seems to translate to "more fun", even though in some/many/all cases, it might not actually be "fun".

# Answer
> 6 votes
Imagine Diablo without random damage. The player run into a horde of skeletons each with 50 HP, the player with current level, equipment etc. deal 24 damage on each hit, so it takes exactly 3 hits to kill a skeleton, but the player is basically forced to waste the majority of the 3rd hit, which is a quite unsatisfactory experience.

The way Diablo is designed the makers can't know exactly what stats the player will enter a given battle with, but they do have an approximate expectation to help them set the difficulty. However, in the described scenario they can't know if the player is good enough to kill the skeletons in 2 hits or have to use 3, which means that the difficulty will be very different for the two scenarios and ultimately either too hard in one case or too easy in the other.

If the player does random damage and deal somewhere from 16 to 32 damage per hit then it will on average take a little more than 2.5 hits to kill a skeleton. Slightly worse or better stats will change this number a little, but the range is much narrower than the 2 or 3 hit case, thus it is easier to make a suitable difficulty.

Sure there are other ways of solving this issue, but random damage does it just fine, and it helps a little in the way of filling the games Skinner box quota as well.

# Answer
> 3 votes
It gives the game a bit more of challenge and strategy. If you know you have to kill 10 enemies to get 100 gold, then you know exactly how the game will play out. However, if you have the chance of earning more or less of something randomly, then those kind of predictions aren’t as accurate and possibly more “fun".

Imagine playing a game level where you always know there will be an enemy jump out from behind one bush. If you die, or have to restart, you know that enemy will be there every time and so you’ll be prepared. This works for some games but it can become boring for some players.

# Answer
> 3 votes
How you display the random numbers to the player can make a huge difference in perception and acceptance. If you show them the random number generator as dice for example, or randomly drawing a card from a deck, it's random, but they feel like they are somehow in control. If you treat the random number generator simply as a pure black box call to some math function, it's not the same emotionally. Purely from a mathematical point of view, it's identical - but emotionally to the player it's another matter.

Dice for example are very acceptable random number generators, because even though they ARE random, players are much more prone to place emotional weight on the results of a roll. Players groan or cheer based on if they roll a low or high number. Even if they rationally understand it makes no difference, subconsciously many will feel like they somehow can influence the outcome of dice by shaking a bit longer, blowing on them, etc.

If you'e ever played a game like DnD, think about how you hold your breath a bit when the DM rolls for wandering monsters. Or if they are rolling for random treasure and it comes up "20" on a 20 sided dice, meaning "special treasure". It's far more exiting that way, with a lot more anticipation of the results.

So in a way, using random numbers *that the player feels they can control* (even if they can't), makes them feel more in control and thus not just being tugged along some "random" path of events by a blackbox random number generator. They "get lucky" and get the "special reward" sometimes, and they aren't upset if they get an average reward. And even if they get the "low roll" sucky reward, they blame the dice, not the game.

# Answer
> 2 votes
This is a must-read article by Greg Costikyan: "Randomness - Blight or Bane".

Basically the argument is that randomness opens up the set of possibilities in a game, making it less predictable, harder to master, and making each playthrough novel.

Some example quotes:

*"To properly simulate war, therefore, unpredictability is essential, and the easiest way to ensure unpredictability is to harness the power of randomness \[...\] In other words, a wargame that contains no random elements is, by nature, a poorer simulation than one that incorporates randomness."*

*"Just as war is too complex to simulate accurately through an entirely non-random system, so are almost all real-world phenomena, at least addressed at a high level, and thus a degree of randomness increases the simulation's fidelity."*

*"the strategy of Poker is based on its randomness. Without random card allocation, it would be an entirely different, and inferior game. The strategy of Poker lies in understanding the statistical nature of the game, and managing statistical outcomes."*

*"adding a random element to any game creates a risk that the outcome will depend on luck rather than strategy; but it also helps to break open a symmetrical game, which is essential to prevent it from degenerating into strategic gridlock."*

---
Tags: game-design, random
---


title: How to make a model impressive

text:
# Question
Title: How to make a model impressive
I am importing a model from 3DS Max 2011 which has been rendered by 3rd party renderer Vray. I believe that fbx does not support Vray information.

So, my questions are: . What others ways are there to make the model impressive? . What are my other options?

Also please note that I am very new to the world of XNA, so please elaborate the suggestion.

# Answer
I think you are confusing the purpose of a 3D modelling package like 3ds max in the field of game development. For art, you ultimately want the 2D image, but for games, you just want the 3D mesh (and animations).

Yes the model may have been rendered using Vray in 3ds max, but that would have just given you a 2d image, which was generated by performing lots of prettifying calculations on top of the basic ones of just drawing the 3D model onto an image. But thats that, all Vray gives you is a beautiful 2D *image*, which is perfect for artists.

What a game does is import the *geometry* you created using your 3D modelling package, then render it using its *own* graphics rendering engine. This rendering is usually very fast and efficient, as it needs to do it many times a second. It can definitely also be beautiful, but you need to balance rendering extras (like quality of shadows and screen space ambient occlusion) with performance.

I recommend that you read up on the Graphics Pipeline, It really gives you a clear idea of how your computer gets your 3D model onto your 2D screen. There are many great tutorials out there (like this one), so look till you find one that explains it to you clearly. Im sure there are also questions involving the graphics pipeline on this site itself.

*(Added on edit, thanks George Duckett for reminding me:)* Also read up on Shaders, it is natural next step after you have got the gist of the graphics pipeline. Popular shader languages are HLSL, GLSL, and Cg (if you decide to learn one, I highly recommend Cg for many reasons, eg. cross-platform)

I'm sure that you ultimately want to improve the quality of your game's appearance - Since you are doing it in XNA, read up on the rendering engine behind XNA (this page seems ideal), and look for ways to make your graphical rendering impressive!

Good luck :)
> 4 votes

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


# Question
Title: Can I use music I made in GarageBand or FL Studio in a commercial game?
I'm a beginning developer and I'd like to make music for my game. I've searched this question on the site, and when it comes to music in games, I see many people suggesting programs like *FL Studio*, *Reaper*, *GarageBand*, etc.

What are the legal implications of using music made with them in a commercial game? Is it okay to use music I've created on my computer with one of these programs (I was thinking of FL Studio) in a game I plan to profit from?

# Answer
> 7 votes
As far as I know: as long as you **pay for the software** (not pirate it by, for example, downloading it via bit torrents) you can use it. However, for example, if in GarageBand you use existing audio loops/samples, you may have to check for clearance with the creator or owner of the rights to the samples.

---
Tags: legal, music, licensing
---


title: Unity 3D vs openGL

text:
# Question
Title: Unity 3D vs openGL
i'm interrested in starting to learn abit about graphics programming through game development and i'm wondering what the pros/cons are when using Unity 3D over using something like C++ & openGL

# Answer
asking Unity3D vs. C++ & OpenGL is like asking whether to buy a Car vs. or a Wheel. You either know how to build a car using it's parts or you need to use already built cars out there!
> 6 votes

# Answer
Unity 3D is an integrated development environment for game development. C++ and openGL are just tools you can use for game production.

It's hard to compare them because of that. For starters I'd suggest you finding a 2D game library for your favourite language and only then switching to c++ / openGL when you feel ready.
> 0 votes

---
Tags: c++, unity
---


# Question
Title: How do I show an interviewer that I have past experience?
While researching some of the development companies I'd like to work for in the future, one thing kept catching my eye; they all wanted previous AAA experience I will have an enormous struggle obtaining. I currently live in an area with no AAA developers nearby, so an internship is next to impossible. Is this requirement a killer, or can this be looked past if I have an 8-year degree? (I am planning on getting a Masters in Computer Science or a similar field anyway for permanent job security.)

If this requirement is that important, I have also heard that you can compensate by having a homemade demo of a game you created on your own. If this is true, how complex must it be? As involved as an indie game? Deeper? Must it be in 3D?

I know this is a few questions too many for one post, but I'd appreciate any advice (preferably for people who have hired other developers in the past or have bypassed a similar issue.)

# Answer
> 26 votes
I work in security software for a large company. If I saw an 8-year degree I wouldn't even bother reading the rest of the résumé. Degrees don't teach you how to program, experience does. Make a game.

# Answer
> 19 votes
Obviously they wouldn't be able to get enough employees if the AAA industry only allowed people in who are already in the AAA industry, so you can ignore that requirement. What you can't ignore is that you have got to show them something that you have made. If I were to decide you'd have spend the majority of those 8 years programming, which would have left you with a decent portfolio on top of all that much needed experience.

It doesn't have to be 3D to count, it doesn't even have to be a game, though the closer to your desired job function, the better. On the other hand the quality of what you make is probably more important than what it is, so make something that you are confident making.

And if you are not used to programming be prepared to scrap and start over a lot, you are not going to put out the needed quality while learning to do so.

# Answer
> 9 votes
You can do a game with your resumee:

http://rickrocket.de/df/

---
Tags: demo, interview
---


title: Implementing a "tech tree"

text:
# Question
Title: Implementing a "tech tree"
Writing for android, but this is an abstract question for any OO language. Is there a "best-practice" for implementing a `TechTree`?

Here is an example:

```
    Vegetation  ->v     Strawberries        ->      BioDome
    Livestock   ->      Biomass

```

In this example, both Vegetation and Livestock are required for Biomass, but only Vegetation is required for Strawberries.

I have brainstormed a handful of implementations, but I'm not very confident with any of them. I will probably be loading the techs from XML, if that matters.

Is there a "best-practice"for implementing tech trees?

# Answer
Tech trees are basically DAGs. Representing it in xml in a way that won't set your hair on fire is pretty simple:

```
<tech name="Biomass">
    <depends>Vegetation</depends>
    <depends>Lifestock</depends>
    <!-- more stuff: description, bonuses, etc... -->
</tech>

```

Simply read the XML, turning it into an object graph, and use standard techniques for getting the available techs.

This is mostly metadata, and it really, really, really shouldn't reside in your code. You can use search and replace for XML too!
> 10 votes

# Answer
It's a pretty simple nested loop: to find available technologies you loop through all the possible technologies, and for each possible tech you loop through all the unlocked technologies to see if the requirements are fulfilled.

In your XML you just define what the requirements are for each tech, and then loop through that XML data when doing the looping I described above.
> 5 votes

# Answer
One solution is to simulate bit fields using EnumSets. An EnumSet uses bit-wise arithmetic for operations that involve the whole set, which means it is very fast. If you are using a language that does not have these features, you could implement something like this using regular bit fields.

---

## Implementation 1

First, have an enum like this:

```
public enum TechType { NONE, VEGETATION, STRAWBERRIES, BIODOME, LIVESTOCK, BIOMASS; }

```

Then you can implement the individual Tech classes:

```
public class VegetationTech implements Tech {
    public TechType type = TechType.VEGETATION;
    public static Set<TechType> prerequisites = EnumSet.of(TechType.NONE);

    @Override
    public Set getPrerequisites() {
        return prerequisites;
    }

    @Override
    public TechType getType() {
        return type;
    }
}

public class BiomassTech implements Tech {
    public TechType type = TechType.BIOMASS;
    public static Set<TechType> prerequisites = EnumSet.of(TechType.VEGETATION,
                                                           TechType.LIVESTOCK);

    @Override
    public Set getPrerequisites() {
        return prerequisites;
    }

    @Override
    public TechType getType() {
        return type;
    }
}

```

Then set up your Player class to check the tech tree for prerequisites before adding a tech or whatever you want:

```
public class Player {
    public Set<TechType> currentTechs;

    public Player() {
        currentTechs = EnumSet.of(TechType.NONE);
    }

    public boolean addTech(Tech tech) {
        if (currentTechs.containsAll(tech.getPrerequisites())) {
            currentTechs.add(tech.getType());
            return true;
        }
        return false;
    }
}

```

---

## Implementation 2

Use case: when techs do not have to be dynamic class objects.

```
public enum Tech {
    NONE            (null,                      0),
    VEGETATION      (EnumSet.of(NONE),          1),
    LIVESTOCK       (EnumSet.of(NONE),          1),
    STRAWBERRIES    (EnumSet.of(VEGETATION),    3),
    BIODOME         (EnumSet.of(STRAWBERRIES),  5),
    BIOMASS         (EnumSet.of(VEGETATION,
                                LIVESTOCK),     4);

    private final Set<Tech> prerequisites;
    private final int turnsRequired;

    Tech(Set<Tech> prerequisites, int turnsRequired) {
        this.prerequisites = prerequisites;
        this.turnsRequired = turnsRequired;
    }
    public Set<Tech> prerequisites() {
        return prerequisites;
    }

    public int turnsRequired() {
        return turnsRequired;
    }
}

```

Here you can add as many parameters as you want, such as a thumbnail icon and description string or whatever.

Then you could schedule research jobs through the Player class:

```
public class Player {
    private Set<Tech> techsKnown;

    public Player() {
        techsKnown = EnumSet.of(Tech.NONE);
    }

    public boolean researchTech(Tech tech) {
        if (techsKnown.containsAll(tech.prerequisites())) {
            addResearchJob(tech, tech.turnsRequired());
            return true;
        }
        return false;
    }

    ...

    public void researchJobDone(Tech tech) {
        techsKnown.add(tech);
    }
}

```

A benefit to this is you could easily combine the methods into a generic "Constructable/Researchable" interface and have the Tech enum and Building class implement it. Then the player could "startWorkOn" either polymorphically.
> 3 votes

---
Tags: architecture
---


# Question
Title: Can I leverage the fact that my scene is often static to improve OpenGL (JOGL) performance?
My scene is drawn based on the location of several (often several million) vertices (kept in VBO's) and a camera. I can easily tell in my code when my scene has changed and when it hasn't. There are also some odd cases such as the window being resized, but I believe I can easily enumerate and handle those as well.

Can I (in user code or through some OpenGL property) leverage this to increase the performance when the scene is static? Clearly when the scene is changing, all of the math must be done to properly calculate what should be rendered. But when the scene is static, that picture isn't changing each frame.

I've tried implementing something in my code to do this, but the result is a flickering scene (and I'm not entirely sure why). Basically I check to see if anything has changed and if it hasn't I simply return from the `display(GLAutoDrawable drawable)` function that is invoked by the JOGL FPSAnimator.

I feel like this is probably a common problem that should have a standard solution. However, I haven't been able to find anything so far.

# Answer
You can render the scene to a FBO when it changes, and render the FBO to the screen every frame. It's a little more effort than just enabling a property, but still quite straightforward to implement. This approach also allows you to render something on the background and foreground independent of the scene.

**edit:** Check this tutorial on using FBOs. You need to do the following initialization steps:

1. Create and bind a Frame Buffer Object
2. Create a Renderbuffer Object same size as the screen. Bind it to GL\_DEPTH\_COMPONENT. Renderbuffers are buffers that you are **not** using as a texture. In this case you need a Renderbuffer for depth buffer.
3. Create a texture same size as the screen. Specify the format to include alpha channel, if you want to render something behind the scene also.
4. Attach both the Renderbuffer object and the texture to the FBO (*Attaching images to FBO*)

When rendering the scene to the FBO:

1. Bind the Frame Buffer Object
2. Render the scene
3. Bind 0 to restore normal screen rendering

When rendering the FBO to the screen:

1. Bind the texture attached to the FBO
2. Render a full-screen quad. Provide texture coordinates for each vertex spanning the whole texture range.

This should be enough for you. If you still need further help, I can try to provide working code sample when I have time.
> 3 votes

---
Tags: opengl, performance, jogl
---


title: A* and Space partitioning

text:
# Question
Title: A* and Space partitioning
I'm planning on implementing A\* in my game for pathfinding, I understand the basics of how the algorithm works but I was wondering, other than finding the start and end nodes Are there any benefits to placing the navigation graph into a tree? It seems to me that it wouldn't really benefit any as each node has a list of connections to other nodes. But I recall reading an article about pathfinding a while back and it suggested using a space partition tree, I believe it suggested an AABB tree to be exact.

If A\* wouldn't benefit would any of the algorithms benefit from such a thing?

And no, sadly I can't find the article again.

# Answer
Space partitioning would be useless for A\* in an established graph.

Spatial partitioning speeds collision checking, which is useful when *constructing* a graph that you navigate with A\*. In a static environment, you should be pre-calculating the graph. In a dynamic environment, you will need to do some collision-checking on-the-fly to, at the very least, discover when edges have been broken by changes, and to find new paths.
> 1 votes

---
Tags: algorithm, path-finding, binary-space-partitioning
---


title: Preventing banding textures in DirectX

text:
# Question
Title: Preventing banding textures in DirectX
I have a 3D scene that I've tried rendering in Direct3D 10 and using WPF's 3D framework. Obviously, going directly to Direct3D is producing far better performance but I am getting banding which doesn't appear using the same scene in WPF.

Does anyone have any tips on removing this type of artifact? It's obviously possible because WPF doesn't have it... If you have any questions about my Direct3D setup I will be please to add that information.

WPF:

Direct3D:

# Answer
> 2 votes
It looks like in the D3D version the mipmaps for the texture are screwed up, with the banding appearing in the first mip level past the base one.

If you're using D3D/WPF's built-in mip generation, perhaps WPF is using a better-quality downsampling filter than D3D. Since your base texture looks like it has a lot of bright and dark lines, I could see a poor filter giving odd results.

---
Tags: directx, textures
---


title: Update single entry in GLSL array

text:
# Question
Title: Update single entry in GLSL array
I have an array in my vertex shader like this:

```
uniform mat4 MeshTransforms[20];

```

At the moment I'm just updating the entire array of matrices like so:

```
int meshTransforms = ARBShaderObjects.glGetUniformLocationARB(shader, "MeshTransforms");
ARBShaderObjects.glUniformMatrix4ARB(meshTransforms, false, UnitTransformMatrices);

```

Where `UnitTransformMatrices` is a float buffer containing the transform matrices of some units.

I'd like to just update a single matrix in the array (just update one unit transform matrix). So how can I overwrite a single matrix in the middle of the matrix array?

This is using the LWJGL, so I'm limited to the functionality it provides.

# Answer
> 2 votes
From `glGetUniformLocation`. In the description section, the element operator '\[\]' may be used to select elements within arrays. So you would grab the location

```
GLuint location = glGetUniformLocation( vertexShader , "variable[element]" );

```

Then from `glUniform`.

```
glvoid glUniformMatrix4fv( location , count , bool Transpose ,  const GLfloat *value);

```

Location is from above, count is the number of elements you plan on changing( sequentially from "location") and the rest you know.

I am not aware of the limitations you have in place with LWJGL, but am only hoping to set you on the right track to show you what's possible so you can check out your own documentation.

---
Tags: opengl, glsl, lwjgl
---


# Question
Title: What is the best way to exploit multicores when making multithread games?
Many people suggest to write a program, and then start optimizing it. But I think that when it's coming to multithreading with multicore, a little think ahead is required.
I've read about using threads, and experienced it myself during some courses at the university (still a student).

The big question is simple, but a bit abstract:

> What thread related steps in game design do I need to take, **before** implementation?

Now trying to be more *specific*. Let's say, as an example, that I'm making a small board game (like Monopoly) that I want to be multithreaded.
My goal Is that this multithreaded game will exploit the best of the multicore system, lets say 4-6 cores (like in i7 processors).

My answer to this question at the moment is, one thread for each of these four basic components:

* GUI
* User Input / Output
* AI (computer rival)
* Other game related calculations (like shortest path from A to B, or level up status change)

I'm not an expert (yet!), and I'm sure there are better answers out there.
Any suggestion, answer, different approach will be helpful.

**Some thoughts:**
Maybe splitting the main database is a good way.. (or total disaster.. )

# Answer
It's usually not a great idea to try and have different subsystems on different threads, because safe communication between them is often too expensive. I wouldn't want to have to use a mutex every time I recorded a mouse movement, for example. And putting AI in a separate thread creates a game design problem in real-time games; does this risk making the AI more responsive or more powerful on more powerful computers? One exception is for audio and specifically the primary buffer handling - it's common to have that in another thread because it's important that audio is being handled in a timely manner and avoids dropouts; but luckily this is usually done for you by most audio libraries.

Generally the best approach is to implement the game as a series of tasks which the different threads can execute in parallel. This scales well to as many threads as you have. You would still usually have the input-update-render loop, but the update section (and the data-processing part of the rendering) can often be split into many distinct tasks that operate on discrete pieces of data.

The most important game design concern when using such an approach is to think about how things can be updated in isolation - you can't have one of object A's update tasks altering object B or even trying to query the present state of object B, as object B may be getting altered in a different thread at the same time. So you could:

* Ensure items that depend on each other are always processed by the same thread, perhaps by packing them into the same task;
* Keep 2 copies of each object's state so that you can always safely read from the old one while amending the new one;
* Send a copy of object B to object A's update task (which is basically an ad-hoc version of the previous approach);
* Make changes via some sort of transaction and apply them via optimistic locking, repeating if it fails (which again basically copies the object and uses versioning and locking to see whether it's safe to write back into the original).

These are all pretty tricky to get right, which is why you need to think ahead as you said.
> 5 votes

# Answer
You are talking about game engine design not game design.. but getting to the topic.

Multithreading makes sense when you have logical tasks which can be divided into parts (or one logical task dividable into sub-tasks).

Normally in single threaded game you would:

1. check user input
    * Normally os makes this "multithreded" for you as in typical situation you are just notified about clicks, touches and key presses (on mobile), and\or you polls input state like mouse position and key press state - but I don't think it is worth to put input check code into separate thread, because if your os is sending you input events, then it already is on separate thread and you just adds additional layer of complexity. Again, if you poll for input device state every frame, then your code afterwards probably depends heavily on that state, so even if you put polling in separate thread, your main thread would have to wait for the results.
2. compute ai actions and "other game related calculations" as you named it.
    * Here you can experiment with multithreading. Think about producers and consumers pattern. For example once in a while you have a queue of units from which your code could grab objects and initiate a "computePathCommand" for each object in different thread.
3. render game and ui
    * This should be tested but I don't think you will gain much if anything by pushing triangles to OpenGL or DirectX from separate threads simultaneously. From http://www.opengl.org/wiki/OpenGL\_and\_multithreading: "..it doesn't improve performance. GL function calls go to the driver and the driver collects the function calls into command lists, which finally get sent to the GPU. Usually there is just 1 GPU so there is no performance increase."

So to sum it up. Multithreading make sense mostly in the "calculations" part, think about dividable tasks in your game, prepare those tasks, create threads which will work on those tasks\*, wait for threads to finish, render/draw the results, repeat :).

* Aditional tip - creating more threads than cpu cores, will not bring you performance increase.
> 2 votes

# Answer
One thing I haven't seen in any answers yet is a split-and-join tactic. This works particularly well when there are numerous cores available (like the PS3's SPUs), or where excessive IO blocking would cause the CPU to be underutilized.

If you have a lot of work that can be calculated independently, you can spawn several threads (or a thread pool) to do the work, give each thread some work, then wait for them all to finish (join) and then move on. This has the advantage of being a fairly localized design change (most of the other things talked about so far have very far-reaching design considerations). However, it can be difficult to find a situation where something like this would actually work and pay off.
> 2 votes

# Answer
What you have isn't a bad way to start, but I'd make the UI thread the main game thread as well. Work out a strong messaging system with commands and command queues for the different threads to communicate so that you minimize the number of synchronization points.

Other places that could be threaded depending on your implementation:

* Sound
* Physics/Animation
* Resource Loading
* Networking

Basically think of different subsystems and think, "Would it be bad if this system was one to two frames out of sync with this other system." If it isn't then they could be off-loaded.

And for some of the answers above, Multi-threaded rendering doesn't mean rendering from multiple threads usually, but rather moving the rendering from the main game thread so that you are not locking the FPS of the renderer to the FPS of other parts of the system.
> 1 votes

# Answer
Interesting question!

Here's my input:

Maybe monopoly isn't the best example for intensive needs for computation, but i get your point. Also, it's a good idea to plan the architecture as thoroughly as possible, and sooner, rather than later!

I'd say that the best use for multicores should be paralelization of AI calculations, as they are the most resource-hungry aspects i can think of, other than graphics (except if you somehow decide to have an extremely detailed 3d monopoly board). But from here, any solution is deeply linked to the game you're coding.

What do you mean by "splitting the main database"?
> 0 votes

# Answer
I invoke the Wisdom of the Ancients:

## Yoda says

> Bad premature optimisation is. Exceptions this does not have.

## Brian Kernighan says

> Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.

Threading is optimisation. It's *very clever* optimisation.

Do it only once it becomes necessary or you will wind up writing, debugging and pondering all things inconsequential. Certainly don't *start* with it!
> -2 votes

---
Tags: multithreading
---