# Question
Title: Should I write my own physics engine, because of networking integration?
I'm currently developing a top down, realtime, zombie shooter. I'm coding this in Java, using JBox2D as my physics engine. I have been coding the networking this week, and am now up to the physics synchronization.

I'm planning to use the predictive client/authoritative server model, where the client is free to move, as long as the server approves of it later. This involves the client sending packets containing movement data to the server, and the server calculating latency, and re-simulating the world from an older state.

My problem is, my current physics engine, JBox2D (basically a port of Box2D), doesn't support rolling back the world, and apparently isn't that easy to serialise the world data. I have 2 solutions, I could either modify/extend my current physics engine, or write my own.

Reasons for writing my own physics engine -

* I can remove unnecessary features. In a top down game, I only really need collision mechanics, and handling forces. No gravity is involved.
* I can understand the code better, and it would \[most likely\] be easier to implement roll back functions

Reasons for extending/modifying JBox2D

* Writing my own physics engine, would be a significant amount of work, which could be cumbersome
* JBox2D has a widely supportive community, that can help me with my dev
* JBox2D, has specific optimizations, for things like collision detection, which make it useful
* Some work as already been done on this, but little code has been shared

So what are your opinions. This is my first game, and I am no way a professional game developer. If anyone could provide some links to work already done in the area (preferably using JBox2D/Box2D/Java).

# Answer
> 7 votes
Collision detection in 2D is so damn simple I don't know why you would even bother using a physics engine in the first place. And since all handling forces are straight forward or on a curve (no falling, altering diagnals etc.) Personally it's a no brainer to me which you should pick. Making your own is simple. Collision:

account for the 3 possible collisions that can happen in 2 rectangles:

1. Edge to edge: Pretty simple, you get the axis of a single edge, and another and you decide whether they occupy either the same space or near enough to it.
2. Edge to corner: This will easily be the most common if you have rotating shapes. Luckily, it's also quite simple to implement.
3. Corner to corner: This will happen so rarely that it's not even worth implementing. The reason for that, is that 2 things would have to be moving in exactly opposite directions on the same exact axis down to your engines last calculated decimal. Now, if everything rotates by 45 or 90 degrees, this MAY (even still probably not) be worth including

---

EDIT: As commented, I'm far less familiar with this matter, and should not be consulted about the bullet/projectile collision.

When I have worked with bullets in 2D space, I used a sort of pathing that worked in both straight line and curved where I would throw the projectile using the physics engine (that I did not make from scratch) and use standard collision.

Read about building this from scratch in the comments.

---

**EDIT:** **Trust me,** regardless of which, you will need some form of dead reckoning in your games engine, because of the projectiles and how many projectiles could be on screen at any given time. You ABSOLUTELY do not want to update every single bullet on screen per frame at it's given location. But it's a great way to make a game unplayably slow :D! You should only ever update these things:

* A projectile is being thrown
* The direction it's being thrown at
* Whether or not it's curved
    + And if so, what is the function of the curve
* What projectile it is (This accounts for the graphic, effects, damage, everything)

Now update the data in the engine accordingly to that data, rather than on the server for each damn projectile, and send out packet data for every single bullet. (Imagine doing that with even just 2 machine guns on screen! Jesus!)

---
Tags: java, physics, networking, box2d
---


title: Chessboard colors with VBO

text:
# Question
Title: Chessboard colors with VBO
I am trying to draw a chessboard pattern using VBO. Geometrywise, I have it implemented and working nicely. However, I have come to the point where I want to color up the board and I have realized that I cannot do it because vertices should be black and white at the same time, depending which square they are drawing. So, looks like I cannot create a color array the same way I create a vertex array.

Any ideas how I can sort this out? Is there anyway to assign two colors to the same vertex, and select one or another depening on the actual square being rendered?

This is the code I am using so far, which is generating a nice "white to black" diagonal pattern instead of the chessboards-like.

```
glGenBuffersARB(1, &VBOfloorVerticesAndNormals);
glBindBufferARB(GL_ARRAY_BUFFER_ARB, VBOfloorVerticesAndNormals);
glBufferDataARB(GL_ARRAY_BUFFER_ARB, numVertices*sizeof(float), vertices, GL_STATIC_DRAW_ARB);

glGenBuffersARB(1, &VBOcolors);
glBindBufferARB(GL_ARRAY_BUFFER_ARB, VBOcolors);
glBufferDataARB(GL_ARRAY_BUFFER_ARB, numColors*sizeof(float), colors, GL_STATIC_DRAW_ARB);

glGenBuffersARB(1, &VBOfloorIndex);
glBindBufferARB(GL_ELEMENT_ARRAY_BUFFER_ARB, VBOfloorIndex);
glBufferDataARB(GL_ELEMENT_ARRAY_BUFFER_ARB, numIndices*sizeof(int), indices, GL_STATIC_DRAW_ARB);

glEnableClientState(GL_VERTEX_ARRAY);
glBindBufferARB(GL_ARRAY_BUFFER_ARB, VBOfloorVerticesAndNormals);
glVertexPointer(3, GL_FLOAT, 0, 0);

glEnableClientState(GL_COLOR_ARRAY);
glBindBufferARB(GL_ARRAY_BUFFER_ARB, VBOcolors);
glColorPointer(4, GL_FLOAT, 0, 0);

glIndexPointer(GL_UNSIGNED_SHORT, 0, 0);
glDrawElements(GL_QUADS, numIndices, GL_UNSIGNED_INT, 0);

glDisableClientState(GL_VERTEX_ARRAY);
glDisableClientState(GL_COLOR_ARRAY);

glBindBufferARB(GL_ARRAY_BUFFER_ARB, 0);
glBindBufferARB(GL_ELEMENT_ARRAY_BUFFER_ARB, 0);

```

And this is the pattern I get:

# Answer
> 4 votes
You should have duplicate vertices on corners. That is a common practice.

In the end you will have 2 vertice arrays, one for black and one for white cells. If my math serves me well - 64 vertices in each array.

# Answer
> 1 votes
I can think of a few ways of making a chessboard pattern.

1. Texture. The easiest method. Make a 2x2 texture with wrap uv, point sampling mode and fill a quad with that, repeating the texture several times.
2. 64 separate 4 vertex quads (i.e, duplicated vertices, like @Krom mentioned)
3. Use flat shading, where the color of the polygon is taken from the first (or last) vertex of the polygon. Tricky, and you either need old enough or new enough opengl to do it.

---
Tags: opengl, vbo
---


title: Simple noise generation

text:
# Question
Title: Simple noise generation
I'm looking to generate noise that looks like this:

(images courtesy of Understanding Perlin Noise)

I'm basically looking for noise with lots of small "ripples". The following is undesirable:

Are there any **simple** ways to do this? I've been looking at perlin and simplex for a week now and I can't seem to ever get it to work in JavaScript, or when I do, I don't have the correct parameters to generate such images, or it is excruciatingly slow.

I understand that the 3 images I posted could probably be achieved by the same algorithm but at a different scale, but I don't need that algorithm. I just need a very simple algorithm to achieve something like in the first image ideally. Maybe some kind of blurring would do the job, but I can't manage to have results.

I'm developing this in JavaScript but any kind of code or even a simple and detailed explanation will work.

# Answer
> 18 votes
While the existing answers provide a good way to achieve what the images in the question show, the comments revealed that the goal is to generate an image as shown below:

This type of noise is quite different from the noise shown in the images of the question, as it forms close isolated blobs.

Turns out that this kind of noise is called *turbulence* which (according to this CPU Gems article) is implemented as follows (where `noise` is your Perlin-noise function returning values from -1..1):

```
double turbulence(double x, double y, double z, double f) {
    double t = -.5;
    for ( ; f <= W/12 ; f *= 2) // W = Image width in pixels
        t += abs(noise(x,y,z,f) / f);
    return t;
}

```

When you get 2D noise from an existing Perlin-noise implementation, you can just use the `abs` value of the noise to get the desired *turbulence* noise.

The JavaScript code that was used to generate the image above can be found in this jsFiddle.

# Answer
> 17 votes
Your example images look a lot like pink noise. It is generated like this:

* First, we have some sort of smooth random noise. Usually, this is achieved by calculation pseudo-random values at points with integer coordinates, and the interpolating these values somehow. The result at this stage looks like this:
* Next, we take this noise and "squeeze" it, increasing its frequency. The simplest formula for this is n2(x,y)=n1(x*f,y*f). In this way, noise pattern is squeezed f times in both directons. Better noise algorithms also rotate and/or translate noise pattern at this step, in order to break up regularities.
* Then, this squeezed pattern is multiplied by some value (less than 1) and added to first pattern. In effect, we add small higher-frequency variation on top of low-frequency pattern. The result looks kinda like this:
* Steps 2 and 3 may be repeated a number of times, adding finer and finer detail. the net result *usually* looks just like your example with the red cross. However, notice that we have 3 parameters in our algorithm to play with:

+ Octave count - or, in other words, number of steps in generation. More steps means finer detail in the resulting pattern.
    + Persistence. It's that value that is multiplied in every step. Usually, persistence is between 0 and 1. High persistence values usually produce "noisy" patterns with lots of little detail. Low persistence creates smooth patterns with subtle detail.
    + Lacunarity. It's the "squeeze" coefficient we use every step. Lacunarity works a bit like peristence, but not exactly. Low lacunarity produces smoother patterns, and high lacunarity creates more sharp and high-contrast ones.

Here are some examples:

High persistence:

High lacunarity:

Low lacunarity:

Playing with these parameters is not the only thing you can do. One nice technique that can add character to noise patterns is to use *perturbation*, that is, add some noise to input coordinates of your noise function.

For example, suppose you have some function that generates noise given coordinates and random seed: `Noise(x,y, seed)`. Than you can use something like `Noise(x+Noise(x,y,234), y+Noise(x,y,6544), seed)` to obtain perturbed value. This can lead to patterns like this (perturbation is applied to circular pattern here, not to noise):

If you want to learn more, I suggest you take a look at libnoise (C++) or CoherentNoise (C#). Unfortunately, I don't know of any Javascript noise-generation library.

# Answer
> 6 votes
Code is commented. Credit goes to Sean McCullough. http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf

```
// Ported from Stefan Gustavson's java implementation
// http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf
// Read Stefan's excellent paper for details on how this code works.
//
// Sean McCullough banksean@gmail.com

/**
* You can pass in a random number generator object if you like.
* It is assumed to have a random() method.
*/
var SimplexNoise = function(r) {
if (r == undefined) r = Math;
  this.grad3 = [[1,1,0],[-1,1,0],[1,-1,0],[-1,-1,0],
                                 [1,0,1],[-1,0,1],[1,0,-1],[-1,0,-1],
                                 [0,1,1],[0,-1,1],[0,1,-1],[0,-1,-1]];
  this.p = [];
  for (var i=0; i<256; i++) {
this.p[i] = Math.floor(r.random()*256);
  }
  // To remove the need for index wrapping, double the permutation table length
  this.perm = [];
  for(var i=0; i<512; i++) {
this.perm[i]=this.p[i & 255];
}

  // A lookup table to traverse the simplex around a given point in 4D.
  // Details can be found where this table is used, in the 4D noise method.
  this.simplex = [
    [0,1,2,3],[0,1,3,2],[0,0,0,0],[0,2,3,1],[0,0,0,0],[0,0,0,0],[0,0,0,0],[1,2,3,0],
    [0,2,1,3],[0,0,0,0],[0,3,1,2],[0,3,2,1],[0,0,0,0],[0,0,0,0],[0,0,0,0],[1,3,2,0],
    [0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],
    [1,2,0,3],[0,0,0,0],[1,3,0,2],[0,0,0,0],[0,0,0,0],[0,0,0,0],[2,3,0,1],[2,3,1,0],
    [1,0,2,3],[1,0,3,2],[0,0,0,0],[0,0,0,0],[0,0,0,0],[2,0,3,1],[0,0,0,0],[2,1,3,0],
    [0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],
    [2,0,1,3],[0,0,0,0],[0,0,0,0],[0,0,0,0],[3,0,1,2],[3,0,2,1],[0,0,0,0],[3,1,2,0],
    [2,1,0,3],[0,0,0,0],[0,0,0,0],[0,0,0,0],[3,1,0,2],[0,0,0,0],[3,2,0,1],[3,2,1,0]];
};

SimplexNoise.prototype.dot = function(g, x, y) {
return g[0]*x + g[1]*y;
};

SimplexNoise.prototype.noise = function(xin, yin) {
  var n0, n1, n2; // Noise contributions from the three corners
  // Skew the input space to determine which simplex cell we're in
  var F2 = 0.5*(Math.sqrt(3.0)-1.0);
  var s = (xin+yin)*F2; // Hairy factor for 2D
  var i = Math.floor(xin+s);
  var j = Math.floor(yin+s);
  var G2 = (3.0-Math.sqrt(3.0))/6.0;
  var t = (i+j)*G2;
  var X0 = i-t; // Unskew the cell origin back to (x,y) space
  var Y0 = j-t;
  var x0 = xin-X0; // The x,y distances from the cell origin
  var y0 = yin-Y0;
  // For the 2D case, the simplex shape is an equilateral triangle.
  // Determine which simplex we are in.
  var i1, j1; // Offsets for second (middle) corner of simplex in (i,j) coords
  if(x0>y0) {i1=1; j1=0;} // lower triangle, XY order: (0,0)->(1,0)->(1,1)
  else {i1=0; j1=1;} // upper triangle, YX order: (0,0)->(0,1)->(1,1)
  // A step of (1,0) in (i,j) means a step of (1-c,-c) in (x,y), and
  // a step of (0,1) in (i,j) means a step of (-c,1-c) in (x,y), where
  // c = (3-sqrt(3))/6
  var x1 = x0 - i1 + G2; // Offsets for middle corner in (x,y) unskewed coords
  var y1 = y0 - j1 + G2;
  var x2 = x0 - 1.0 + 2.0 * G2; // Offsets for last corner in (x,y) unskewed coords
  var y2 = y0 - 1.0 + 2.0 * G2;
  // Work out the hashed gradient indices of the three simplex corners
  var ii = i & 255;
  var jj = j & 255;
  var gi0 = this.perm[ii+this.perm[jj]] % 12;
  var gi1 = this.perm[ii+i1+this.perm[jj+j1]] % 12;
  var gi2 = this.perm[ii+1+this.perm[jj+1]] % 12;
  // Calculate the contribution from the three corners
  var t0 = 0.5 - x0*x0-y0*y0;
  if(t0<0) n0 = 0.0;
  else {
    t0 *= t0;
    n0 = t0 * t0 * this.dot(this.grad3[gi0], x0, y0); // (x,y) of grad3 used for 2D gradient
  }
  var t1 = 0.5 - x1*x1-y1*y1;
  if(t1<0) n1 = 0.0;
  else {
    t1 *= t1;
    n1 = t1 * t1 * this.dot(this.grad3[gi1], x1, y1);
  }
  var t2 = 0.5 - x2*x2-y2*y2;
  if(t2<0) n2 = 0.0;
  else {
    t2 *= t2;
    n2 = t2 * t2 * this.dot(this.grad3[gi2], x2, y2);
  }
  // Add contributions from each corner to get the final noise value.
  // The result is scaled to return values in the interval [-1,1].
  return 70.0 * (n0 + n1 + n2);
};

// 3D simplex noise
SimplexNoise.prototype.noise3d = function(xin, yin, zin) {
  var n0, n1, n2, n3; // Noise contributions from the four corners
  // Skew the input space to determine which simplex cell we're in
  var F3 = 1.0/3.0;
  var s = (xin+yin+zin)*F3; // Very nice and simple skew factor for 3D
  var i = Math.floor(xin+s);
  var j = Math.floor(yin+s);
  var k = Math.floor(zin+s);
  var G3 = 1.0/6.0; // Very nice and simple unskew factor, too
  var t = (i+j+k)*G3;
  var X0 = i-t; // Unskew the cell origin back to (x,y,z) space
  var Y0 = j-t;
  var Z0 = k-t;
  var x0 = xin-X0; // The x,y,z distances from the cell origin
  var y0 = yin-Y0;
  var z0 = zin-Z0;
  // For the 3D case, the simplex shape is a slightly irregular tetrahedron.
  // Determine which simplex we are in.
  var i1, j1, k1; // Offsets for second corner of simplex in (i,j,k) coords
  var i2, j2, k2; // Offsets for third corner of simplex in (i,j,k) coords
  if(x0>=y0) {
    if(y0>=z0)
      { i1=1; j1=0; k1=0; i2=1; j2=1; k2=0; } // X Y Z order
      else if(x0>=z0) { i1=1; j1=0; k1=0; i2=1; j2=0; k2=1; } // X Z Y order
      else { i1=0; j1=0; k1=1; i2=1; j2=0; k2=1; } // Z X Y order
    }
  else { // x0<y0
    if(y0<z0) { i1=0; j1=0; k1=1; i2=0; j2=1; k2=1; } // Z Y X order
    else if(x0<z0) { i1=0; j1=1; k1=0; i2=0; j2=1; k2=1; } // Y Z X order
    else { i1=0; j1=1; k1=0; i2=1; j2=1; k2=0; } // Y X Z order
  }
  // A step of (1,0,0) in (i,j,k) means a step of (1-c,-c,-c) in (x,y,z),
  // a step of (0,1,0) in (i,j,k) means a step of (-c,1-c,-c) in (x,y,z), and
  // a step of (0,0,1) in (i,j,k) means a step of (-c,-c,1-c) in (x,y,z), where
  // c = 1/6.
  var x1 = x0 - i1 + G3; // Offsets for second corner in (x,y,z) coords
  var y1 = y0 - j1 + G3;
  var z1 = z0 - k1 + G3;
  var x2 = x0 - i2 + 2.0*G3; // Offsets for third corner in (x,y,z) coords
  var y2 = y0 - j2 + 2.0*G3;
  var z2 = z0 - k2 + 2.0*G3;
  var x3 = x0 - 1.0 + 3.0*G3; // Offsets for last corner in (x,y,z) coords
  var y3 = y0 - 1.0 + 3.0*G3;
  var z3 = z0 - 1.0 + 3.0*G3;
  // Work out the hashed gradient indices of the four simplex corners
  var ii = i & 255;
  var jj = j & 255;
  var kk = k & 255;
  var gi0 = this.perm[ii+this.perm[jj+this.perm[kk]]] % 12;
  var gi1 = this.perm[ii+i1+this.perm[jj+j1+this.perm[kk+k1]]] % 12;
  var gi2 = this.perm[ii+i2+this.perm[jj+j2+this.perm[kk+k2]]] % 12;
  var gi3 = this.perm[ii+1+this.perm[jj+1+this.perm[kk+1]]] % 12;
  // Calculate the contribution from the four corners
  var t0 = 0.6 - x0*x0 - y0*y0 - z0*z0;
  if(t0<0) n0 = 0.0;
  else {
    t0 *= t0;
    n0 = t0 * t0 * this.dot(this.grad3[gi0], x0, y0, z0);
  }
  var t1 = 0.6 - x1*x1 - y1*y1 - z1*z1;
  if(t1<0) n1 = 0.0;
  else {
    t1 *= t1;
    n1 = t1 * t1 * this.dot(this.grad3[gi1], x1, y1, z1);
  }
  var t2 = 0.6 - x2*x2 - y2*y2 - z2*z2;
  if(t2<0) n2 = 0.0;
  else {
    t2 *= t2;
    n2 = t2 * t2 * this.dot(this.grad3[gi2], x2, y2, z2);
  }
  var t3 = 0.6 - x3*x3 - y3*y3 - z3*z3;
  if(t3<0) n3 = 0.0;
  else {
    t3 *= t3;
    n3 = t3 * t3 * this.dot(this.grad3[gi3], x3, y3, z3);
  }
  // Add contributions from each corner to get the final noise value.
  // The result is scaled to stay just inside [-1,1]
  return 32.0*(n0 + n1 + n2 + n3);
};

```

Also, if you use a PRNG with that you can easily get easy re-instateable results

```
/*
  I've wrapped Makoto Matsumoto and Takuji Nishimura's code in a namespace
  so it's better encapsulated. Now you can have multiple random number generators
  and they won't stomp all over eachother's state.

  If you want to use this as a substitute for Math.random(), use the random()
  method like so:

  var m = new MersenneTwister();
  var randomNumber = m.random();

  You can also call the other genrand_{foo}() methods on the instance.

  If you want to use a specific seed in order to get a repeatable random
  sequence, pass an integer into the constructor:

  var m = new MersenneTwister(123);

  and that will always produce the same random sequence.

  Sean McCullough (banksean@gmail.com)
*/

/*
   A C-program for MT19937, with initialization improved 2002/1/26.
   Coded by Takuji Nishimura and Makoto Matsumoto.

   Before using, initialize the state by using init_genrand(seed)
   or init_by_array(init_key, key_length).

   Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
   All rights reserved.

   Redistribution and use in source and binary forms, with or without
   modification, are permitted provided that the following conditions
   are met:

     1. Redistributions of source code must retain the above copyright
        notice, this list of conditions and the following disclaimer.

     2. Redistributions in binary form must reproduce the above copyright
        notice, this list of conditions and the following disclaimer in the
        documentation and/or other materials provided with the distribution.

     3. The names of its contributors may not be used to endorse or promote
        products derived from this software without specific prior written
        permission.

   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
   A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

   Any feedback is very welcome.
   http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
   email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
*/

var MersenneTwister = function(seed) {
  if (seed == undefined) {
    seed = new Date().getTime();
  }
  /* Period parameters */
  this.N = 624;
  this.M = 397;
  this.MATRIX_A = 0x9908b0df;   /* constant vector a */
  this.UPPER_MASK = 0x80000000; /* most significant w-r bits */
  this.LOWER_MASK = 0x7fffffff; /* least significant r bits */

  this.mt = new Array(this.N); /* the array for the state vector */
  this.mti=this.N+1; /* mti==N+1 means mt[N] is not initialized */

  this.init_genrand(seed);
}

/* initializes mt[N] with a seed */
MersenneTwister.prototype.init_genrand = function(s) {
  this.mt[0] = s >>> 0;
  for (this.mti=1; this.mti<this.N; this.mti++) {
      var s = this.mt[this.mti-1] ^ (this.mt[this.mti-1] >>> 30);
   this.mt[this.mti] = (((((s & 0xffff0000) >>> 16) * 1812433253) << 16) + (s & 0x0000ffff) * 1812433253)
  + this.mti;
      /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
      /* In the previous versions, MSBs of the seed affect   */
      /* only MSBs of the array mt[].                        */
      /* 2002/01/09 modified by Makoto Matsumoto             */
      this.mt[this.mti] >>>= 0;
      /* for >32 bit machines */
  }
}

/* initialize by an array with array-length */
/* init_key is the array for initializing keys */
/* key_length is its length */
/* slight change for C++, 2004/2/26 */
MersenneTwister.prototype.init_by_array = function(init_key, key_length) {
  var i, j, k;
  this.init_genrand(19650218);
  i=1; j=0;
  k = (this.N>key_length ? this.N : key_length);
  for (; k; k--) {
    var s = this.mt[i-1] ^ (this.mt[i-1] >>> 30)
    this.mt[i] = (this.mt[i] ^ (((((s & 0xffff0000) >>> 16) * 1664525) << 16) + ((s & 0x0000ffff) * 1664525)))
      + init_key[j] + j; /* non linear */
    this.mt[i] >>>= 0; /* for WORDSIZE > 32 machines */
    i++; j++;
    if (i>=this.N) { this.mt[0] = this.mt[this.N-1]; i=1; }
    if (j>=key_length) j=0;
  }
  for (k=this.N-1; k; k--) {
    var s = this.mt[i-1] ^ (this.mt[i-1] >>> 30);
    this.mt[i] = (this.mt[i] ^ (((((s & 0xffff0000) >>> 16) * 1566083941) << 16) + (s & 0x0000ffff) * 1566083941))
      - i; /* non linear */
    this.mt[i] >>>= 0; /* for WORDSIZE > 32 machines */
    i++;
    if (i>=this.N) { this.mt[0] = this.mt[this.N-1]; i=1; }
  }

  this.mt[0] = 0x80000000; /* MSB is 1; assuring non-zero initial array */
}

/* generates a random number on [0,0xffffffff]-interval */
MersenneTwister.prototype.genrand_int32 = function() {
  var y;
  var mag01 = new Array(0x0, this.MATRIX_A);
  /* mag01[x] = x * MATRIX_A  for x=0,1 */

  if (this.mti >= this.N) { /* generate N words at one time */
    var kk;

    if (this.mti == this.N+1)   /* if init_genrand() has not been called, */
      this.init_genrand(5489); /* a default initial seed is used */

    for (kk=0;kk<this.N-this.M;kk++) {
      y = (this.mt[kk]&this.UPPER_MASK)|(this.mt[kk+1]&this.LOWER_MASK);
      this.mt[kk] = this.mt[kk+this.M] ^ (y >>> 1) ^ mag01[y & 0x1];
    }
    for (;kk<this.N-1;kk++) {
      y = (this.mt[kk]&this.UPPER_MASK)|(this.mt[kk+1]&this.LOWER_MASK);
      this.mt[kk] = this.mt[kk+(this.M-this.N)] ^ (y >>> 1) ^ mag01[y & 0x1];
    }
    y = (this.mt[this.N-1]&this.UPPER_MASK)|(this.mt[0]&this.LOWER_MASK);
    this.mt[this.N-1] = this.mt[this.M-1] ^ (y >>> 1) ^ mag01[y & 0x1];

    this.mti = 0;
  }

  y = this.mt[this.mti++];

  /* Tempering */
  y ^= (y >>> 11);
  y ^= (y << 7) & 0x9d2c5680;
  y ^= (y << 15) & 0xefc60000;
  y ^= (y >>> 18);

  return y >>> 0;
}

/* generates a random number on [0,0x7fffffff]-interval */
MersenneTwister.prototype.genrand_int31 = function() {
  return (this.genrand_int32()>>>1);
}

/* generates a random number on [0,1]-real-interval */
MersenneTwister.prototype.genrand_real1 = function() {
  return this.genrand_int32()*(1.0/4294967295.0);
  /* divided by 2^32-1 */
}

/* generates a random number on [0,1)-real-interval */
MersenneTwister.prototype.random = function() {
  return this.genrand_int32()*(1.0/4294967296.0);
  /* divided by 2^32 */
}

/* generates a random number on (0,1)-real-interval */
MersenneTwister.prototype.genrand_real3 = function() {
  return (this.genrand_int32() + 0.5)*(1.0/4294967296.0);
  /* divided by 2^32 */
}

/* generates a random number on [0,1) with 53-bit resolution*/
MersenneTwister.prototype.genrand_res53 = function() {
  var a=this.genrand_int32()>>>5, b=this.genrand_int32()>>>6;
  return(a*67108864.0+b)*(1.0/9007199254740992.0);
}

/* These real versions are due to Isaku Wada, 2002/01/09 added */

```

# Answer
> 0 votes
Use pre-generated textures, or put a perlin noise texture generator on a server and query it for perlin noise images.

---
Tags: algorithm, javascript, procedural-generation, perlin-noise
---


# Question
Title: How do you calculate if 2 lines are facing toward or away?
Given the 4 points describing 2 line segments, how do you calculate if line A is towards or away from line B?

The 2 lines have a fixed length, and can be measured as distance from x1/y1 to x2/y2.

# Answer
Let `A` and `B` be two points on the black line. Let `C` and `D` be your blue segment. The sign of the `z` coordinate of cross product `AB^AC` tells you whether `C` is "left" or "right" of the black line. Similarly, cross product `AB^CD` tells you whether `CD` steers "left" or "right" of the black line.

We don't really want to know whether it's left or right; all we want is to make sure they're the same direction or the opposite direction, that's why we multiply the two values.

The following pseudocode should therefore work:

```
z1 = (xB-xA)*(yC-yA) - (yB-yA)*(xC-xA);
z2 = (xB-xA)*(yD-yC) - (yB-yA)*(xD-xC);
z3 = z1 * z2;

if (z3 < 0)
    ; /* Pointing towards (BUT maybe even crossing) */
else if (z3 > 0 || z2 != 0)
    ; /* Pointing away */
else
    ; /* Parallel */

```

I am afraid I need some time to write a proper solution for the Bezier curve. Is the following situation towards or away?
> 11 votes

# Answer
Assuming start point is the green circle, and end point is the red arrow

Compute the distance between the start point as DS and the black segment, and do the same for the end point (red arrow) as DE. If DS\>DE, then the segment is pointing toward. if DE\>DS, it is pointing away. If both are equal, the two are parallels.

You can find how to compute the distance from a point to a segment here, and to a quadratic bezier curve here. However, depending of the shape of the bezier curve, it might return weird results (the curve can be crossing itself)
> 2 votes

---
Tags: mathematics, geometry, lines, beziers, curves
---


# Question
Title: Simple speed deceleration with variable time step?
When you use a fixed time step you can call speed=speed\*0.95 to emulate speed deceleration in a simple way.

I want to do the same thing with variable time step.

I wish to have a simple function speed=f(speed,dt); where dt is the time step since last frame.

# Answer
I would like to make an exact version of David's answer. Since I copied so much from him, I'm making this community wiki.

### TL;DR

```
static float ApplyFriction(float value, float friction, float dt)
{
    return value * pow(friction, dt);
}

```

### Why is it important?

It is often good to make approximations. But approximations are only good **when they are good**. You should only make approximations when you know their domain of validity.

Using a linear approximation of the above formula, iterating at 60 fps for a 5% speed decrease every second gives you an error under 0.2%.

But what if you want to iterate *at 30 fps for, say a 35% speed decrease every second*? Then you get an error of more than 20%! Surely that's no longer acceptable.

### Explanation

First realize that:

```
speed = speed * friction;

```

Is equivalent to (taking some notation liberties here):

```
log(speed) = log(speed * friction);

log(speed) = log(speed) + log(friction);

```

Then simply apply the timestep:

```
log(speed) = log(speed) + log(friction) * dt;

```

Which is equivalent to:

```
log(speed) = log(speed) + log(pow(friction, dt));

log(speed) = log(speed * pow(friction, dt));

speed = speed * pow(friction, dt);

```
> 10 votes

# Answer
**I'm leaving this post as reference and context for Sam's answer, but you should use his version instead.**

---

**TL;DR**

Here's your function (in C#) where I took the liberty to add the friction as a parameter instead of hard-coding it:

```
static float ApplyFriction(float value, float friction, float dt)
{
    return value - value  * (1f - friction) * dt;
}

```

You might also want to do a speed=Max(0,speed) afterwards.

**Explanation**

So you'd like speed to reduce 5% per second instead of per frame? That's easy enough to approximate.

First realize that:

```
speed = speed * friction;

```

Is equivalent to:

```
speed = speed - speed * (1 - friction);

```

Then simply apply the timestep:

```
speed = speed - speed * (1 - friction) * dt;

```

While not giving exactly perfect results because the friction is applied as a percentage of the value during each individual step instead of the initial value at each second, in practice the difference is insignificant, as you may check with this sample test:

http://ideone.com/JkJ2I (with 60 evenly spaced frames)

or

http://ideone.com/XKfSw (with an unknown number of variable frames adding up to 1 second)

Where an initial speed of 1000 and a friction value of 0.95 yielded:

* 950 when applying it with fixed time step.
* 951.2092 when applying it with variable time step over the course of 60 frames in a second.

That's about 0.1% divergence i.e. they're equivalent for pratical purposes.
> 2 votes

# Answer
If there is a force on an object causing it to decelerate, the deceleration causes a linear-decrease, not exponential:

```
//Do this every frame - make 'acceleration' negative to decelerate
speed = speed + acceleration

```

If you want the force to stop when the car stops (like with car-brakes), make sure to constrict `speed` to being `>= 0`
> 1 votes

---
Tags: algorithm, fixed-timestep
---


# Question
Title: Objective-C or C++ of game engine header file for iOS developers?
We've developed a game engine written in C++. Now we are preparing our game engine for iOS developers.

I guess that many game developers use C++ or Objective-C for their game apps. So I think we should expose the API of our library in both Objective-C (@class blahblah) header files and in C++ (class blahblah) header files.

Am I on the right track? If not, what is the most recommended way of exposing the API for our library?

# Answer
> 3 votes
Since one can use C++ libraries in Objective-C also, there's actually no need to create special Objective-C header files.

Box2D for example is a pure C++ physics engine but is used in a lot of games, even ones written in Objective-C.

The only caveat (for developers using your library) is that

> you still need to instruct the compiler to build all files that use C++ headers as Objective-C++ rather than Objective-C.

(as per Sam's comment)

# Answer
> 1 votes
You can use Objective-C++ by naming your files with the extension `.mm`. This way, you can use both Objective-C classes(NSString, UIView) and c++ classes(classes in your c++ engine).

There is no need to rewrite your engine on Objective-C.

# Answer
> 0 votes
I had the same issue 2 years ago. What I end up doing is adding some additional functionality written in Obj-C where I host my engine. I limit my use of ObjC to creating UIView with OpenGL support, translating touch events to engine touch events, some file system calls to get the application data folder. All this exists only in my Engine project. In the apps themselves I write only in C++ using C++ interfaces.

---
Tags: ios, objective-c
---


# Question
Title: How to go orthographic instead of perspective view in XNA with CreateOrthographicOffCenter?
Using these view and projection values:

```
var eye = new Vector3(0, 0, 10f);
var view = Matrix.CreateLookAt(eye, Vector3.Zero, Vector3.Up);
var projection = Matrix.CreatePerspectiveFieldOfView(MathHelper.PiOver4, GraphicsDevice.Viewport.AspectRatio, 1.0f, 1000f);

```

and then applying world rotation to the effects with this matrix:

```
var rotation = Matrix.CreateRotationX(-MathHelper.PiOver2)*Matrix.CreateRotationY(MathHelper.PiOver2);

```

I am able to render my animated model:

But simply changing projection matrix to something like this:

```
var projection = Matrix.CreateOrthographicOffCenter(0, GraphicsDevice.Viewport.Width, GraphicsDevice.Viewport.Height, 0, 1.0f, 1000.0f);

```

Renders pure CornBlue screen. I don’t see my model at all. What should I do to make it visible?

# Answer
> 5 votes
To summarize, you probably want to use the CreateOrthographic method instead:

```
var projection = Matrix.CreateOrthographic(GraphicsDevice.Viewport.Width, GraphicsDevice.Viewport.Height, 1.0f, 1000.0f);

```

Or if you still wanted to use CreateOrthographicOffCenter, change to the following values instead:

```
var projection = Matrix.CreateOrthographicOffCenter(-GraphicsDevice.Viewport.Width/2f, GraphicsDevice.Viewport.Width/2f, -GraphicsDevice.Viewport.Height/2f, GraphicsDevice.Viewport.Height/2f, 1, 10000);

```

If I remember correctly CreateOrthographicOffCenter maps the view space origin to the top-left corner of your viewport, *and* it also inverts the Y axis so that it increases donwards. This is ideal for 2D stuff, just like using the SpriteBatch class

**(Edit)** With CreateOrthographicOffCenter you specify the left/right/top/bottom/far/near extents of the viewable area directly. The order in which you specify these parameters also dictate the direction of the corresponding axes. E.g. it is frequent for 2D games to invert the Y axis so that it points downards.

Since you were specifying a top/left value of 0, the viewing space origin was being mapped to the top left corner of the screen instead of the center of the screen as you probably intended. And the order in which you specified the bottom/top parameters also inverted the Y-axis which would make the model appear rendered upside down.

On the other hand CreateOrhographic maps the view space origin into the *middle* of your viewport which is probably what you wanted to do.

So I believe you're just not seeing the model because its position lies outside the viewport after being projected. Just switch to the other function and it should start working (as long as your model is within viewing range).

For reference, here's what I got when I used the same scene and only changed the projection between each screenshot (with values similar to the OP):

---
Tags: xna, 3d
---


# Question
Title: Handling random with unique chance in Python
Okay, let's say you have a handful of enemies, each with their own 'rarity' to spawn. For example:

```
monsterlist = []

snake = 'snake', 60
wolf = 'wolf', 80
antlion = 'antlion', 30

monsterlist.append(snake, wolf, antlion)

```

Now I want to spawn one at random:

```
totalchance = 0

for monster in monsterlist:
    totalchance += monster[1] #add each monster's rarity to totalchance
chance = random.randint(0, totalchance)

if chance <= targetlist[0][1]: #chance is <= than first entry's rarity
    #spawn first monster
elif chance <= targetlist[0][1] + targetlist[1][1]: #chance <= second target's rarity
    #spawn second monster
#etc

```

Assuming you have a large amount of monsters in monsterlist, this is going to take stupid amounts of code just to calculate chance to spawn, I like to assume there's a less annoying way to do this, right?

# Answer
**You want to use a weighted choice algorithm.** Here's some code. *(I modified my own working code to fit your case, but it should work)*:

**Ignoring the definition of `WeightedChoice()` for the moment, using `WeightedChoice()` is simple:**

```
# The weighted list of monsters. Each item is a tuple: (VALUE, WEIGHT)
monsterlist = (
    ('snake', 60),
    ('wolf', 80),
    ('antlion', 30),
)

# do this (again) each time monsterlist changes:
weightedChoice = WeightedChoice(monsterlist);

# do this each time you want to grab a random monster:
print(weightedChoice.next())

```

**Now the definition of `WeightedChoice()`.** Based on Weighted random generation in Python. Refer to this blog post for a detailed explanation and comparison to other weight choice algoritms.

```
import random
import bisect

# Returns a random value, considering the weights of each item.
class WeightedChoice(object):
    def __init__(self, weights):
        self.totals = []
        self.weights = weights
        running_total = 0

        for w in weights:
            running_total += w[1]
            self.totals.append(running_total)

    def next(self):
        rnd = random.random() * self.totals[-1]
        i = bisect.bisect_right(self.totals, rnd)
        return self.weights[i][0]

```
> 10 votes

# Answer
Assuming the list of monsters and their rarities doesn't change during gameplay too often, you can precompute the `totalchance` variable and also a list of the partial sums, that is, the sums of the rarities of the first n monsters. Something like this:

```
# During initialization
totalchance = 0
partialsums = []
for monster in monsterlist:
    totalchance += monster[1]
    partialsums.append(totalchance)

# When spawning a monster
import bisect
chance = random.randint(0, totalchance)
monsterindex = bisect.bisect_left(partialsums, chance)
monstertospawn = monsterlist[monsterindex]
# Spawn an instance of monstertospawn...

```
> 5 votes

# Answer
If I'm understanding your question correctly, you are concerned about the complexity of your spawning code. You could probably benefit from some sorting. Start by sorting your spawn table by "rarity." Whenever your code wants to determine whether "by chance" something spawns or not, you could "roll the dice" and iterate through your sorted list to quickly find the "rarest" object that could spawn given your "roll."

Also, this is a good example of an algorithm that could be later optimized. I would suggest you just write it and later on when your game has taken shape, profile the game and see if this function is even consuming a considerable amount of time. If it's not, optimizing it will realize you virtually no gains.
> 2 votes

# Answer
*I don't really know python at all.*

If your monster list changes often classical weighted chance probably won't work for you, at least if you are pedantic about performance. The problem lies in calculating the maximum chance; you need to iterate over the list at least twice to get the value.

# Option 1: Custom List

By creating a custom list class you can skip one loop over the values.

Let's say for instance we have some `MonsterList` class that you can use as follows:

```
monsterlist = MonsterList()
monsterlist.add('snake', 60);
monsterlist.add('troll', 80); # problem?
monsterlist.add('antlion', 30);

```

The internal representation would actually be:

```
[
  { 'snake', 0 } # 0
  { 'troll', 60 } # 0 + 60
  { 'antlion', 140 } # 0 + 60 + 80
  # 0 + 60 + 80 + 30 = 170
]

```

In other words the list would be keeping track of an internal total as you create it. To get a value you have a further two sub-options, in both cases you will need to choose a value between 0 and 170 (the current internal total).

**Linear Search** (`O(n)`)

Simply loop over the list until the current item has a value less than the random value.

**Binary Search** (`O(log2N)`)

Extend the internal representation to the following:

```
[
  { 'snake', 0, 60 } # 0
  { 'troll', 60, 140 } # 0 + 60
  { 'antlion', 140, 270 } # 0 + 60 + 80
  # 0 + 60 + 80 + 30 = 170
]

```

Now perform your basic binary search over the list, stopping when the random value is within the range in the internal representation.

*This works because of the way we add values to the list; the running total is guaranteed to be sorted.*

# Option 2: Multiple Additions

Another option is to add each monster to the list multiple times, however, depending on how granular the weights could be you could land up with a rather large list - so this would be a memory-performance trade-off.

```
monsterlist = []

snake = 'snake'
troll = 'troll'
antlion = 'antlion'

# snake is twice as likely to appear in comparison to antlion.
# troll is three times as likely to appear in comparison to antlion.
# troll is 1.5 times as likely to appear in comparison to snake.
monsterlist.append(snake, snake, troll, troll, troll, antlion)

```

Getting a value from that list would merely involve choose a random index (given the count) and indexing the list directly (`O(1)`).
> 1 votes

# Answer
If the list of monster frequencies changes very frequently, you can't do much better than this. (Although keeping the list sorted in decreasing order of frequency, and keeping track of the total frequency so you don't need to recompute it, lets you avoid traversing the whole list most of the time.)

If the list *doesn't* change very often, there's a trick that lets you do fast lookups at the cost of some precalculation. I'll write up a better description of it here later when I have more time, but in the mean time take a look at this old Usenet thread ("Seeking reference for O(1) random variable lookup algorithm" in sci.crypt.random-numbers).

Finally, I second stephelton's advice: don't spend too much time optimizing this before you've profiled your code and found out how much time it's actually taking.
> 0 votes

---
Tags: python, random
---


# Question
Title: What resources can I use to determine if the name of my game violates any copyrights or trademarks?
I'm a indie/hobbyist game developer. How do I check that I'm not infringing any copyrights or trademarks when I release my game?

I'm not making megabucks so it's not financially feasible to get professional legal help for each game.

I asked recently if I can reuse the name of an old arcade game (Crazy Balloon), but this got me thinking about future games where I might not even be aware of something similar that existed before.

So, are there any tools or resources that you can recommend to check myself (due diligence I think it's called).

# Answer
> 12 votes
In the United States, the USPTO's TESS service lets you search trademarks.

Not violating copyright is trivial - do not copy a work unless you have explicit permission to.

In the United States, due diligence is not a practice that applies to individual creators and performing due diligence improperly (i.e. without a lawyer or licensed authority) rather than not doing it at all puts you at greater financial risk.

# Answer
> 5 votes
The first step is understanding the difference between copyright and trademarks.

Trademarks are a system for marking (distinguishing) one type of goods from another. \[quote\]From Wikipedia: A trademark, trade mark, or trade-mark\[1\] is a distinctive sign or indicator used by an individual, business organization, or other legal entity to identify that the products or services to consumers with which the trademark appears originate from a unique source, and to distinguish its products or services from those of other entities. \[/quote\]

Google is a trademark. The trademark ‘Google’ is not copyrighted. You cannot copyright words, nor can you generally copyright name. You can copyright characterizations. For instance, you cannot copyright ‘Harry Potter’, however, ‘Harry Potter, a wizard, etcetera’ can be protected. At what point is a bit murky. Example: it isn’t enough that ‘Harry Potter A’ and Harry Potter B’ both be boys. The movie Troll (1986) introduced the name Harry Potter, years before the book. Further, even though there are over 100 various Harry Potter trademarks now associated with the Rowling’s character, these trademarks cannot prevent anyone from having a character named Harry Potter. What they can prevent is the use of the phrase Harry Potter to mark any conflicting goods. Stay with me a bit here.

Troll is being remade. Even though the makers of Troll did not trademark Harry Potter, they can still use the name. What they cannot do it infringe on various ‘Harry Potter’ trademarks and call their movie Harry Potter Meets the Trolls, or Harry Potter VS Trolls, etc. This is not a matter of who used the name first. Trademarks protect how your goods (product) is represented in the marketplace.

An additional aspect of trademarks to remember is that trademarks are by area. So even if you find a trademark with the same name it may not prevent use if it only covers an unrelated area. For instance, registering a trademark for ‘Vehicles’ doesn’t mean someone cannot use that same word or phrase for clothing. This is why if one looks carefully at X-Men trademarks you’ll see various types of separate registration by Marvel/Fox/Etcetera to cover, not only comics, but entertainment, toys, games, and even cakes.

Copyright protects intellectual property. What some refer to as artistic or creative expression. Literally, it is the copyright owner’s right to control who can use the artist’s work. A list of the users of this site wouldn’t fall under copyright, but certain expressions of that list might. The standard example is that the information in a phonebook, the data, is not protected, but the form and layout may be.

---

The easiest way to avoid trademark issues is to make up something. That’s what Google did. You’ll still have to check to make sure someone else didn’t make it up first. Combining words can help, Balloony, Ballunacy, Ballunatic Attack, etc.

The easiest way to avoid copyright issues it to make your own art from scratch. Or Google copyright free, public domain, free art, royalty-free etcetera. Non-professional artists are often quite willing to allow you to use their artwork if you ask permission.

# Answer
> 1 votes
Recently I saw that EA Games has game in App Store called Tetris. In the seller description it says the following:

> Seller: Electronic Arts Inc. Tetris ® and © 1985~2011 Tetris Holding. Tetris logos, Tetris theme song and Tetriminos are trademarks of Tetris Holding. The Tetris trade dress is owned by Tetris Holding. Licensed to The Tetris Company. Game Design by Alexey Pajitnov. Original Logo Design by Roger Dean. All Rights Reserved. Tetris Game Code © 2011 Electronic Arts Inc. EA and the EA logo are trademarks of Electronic Arts Inc.

# Answer
> -3 votes
I don't think there is any quick way to check license infringing. But, there are way to avoid it.

* first just don't google around and download stuff from where ever you hit. If you like any content, then look for license agreement around the download page. If you don't find any then look for contact information and ask them about it.(only if you know that the hosting site owner, is the owner of that asset)
* secondly, never ever download from file sharing web site or torrents. Like rapidshare, megaupload, demonoid etc etc. They just host the file. There is no way to know who does it belong to or where did it came from.
* it always ,a wise decision to ask a lawyer, but as you said, it not possible for every indie developers out there. But, sometimes if you get confused(very frequently) then you should go for it. Save you ass before its busted.
* lastly, *don't ever assume its ok to use it*. License infringing can end up in jail time and/or fine(depending of the country you are in).
* sometimes, some decent attitude can lead to indecent situation. Like if you name your game "X Edge", then Edge Game can sue you. Like they did to EA for the game Mirrors Edge. Edge game lost the case.But Edge games don't allow anyone to use the word *Edge* to any games.

BUT, this goes for **game resources**, FOR **GamePlay patent** you should read this. I know may sound weird at first, but Mitch Lindgren gave us a nice answer over there.

---
Tags: legal, copyright
---


# Question
Title: What is a good starting platform for a teenage game programmer?
My son (15) has decided that he wants to pursue a career as a games programmer. I've said that he should get started now with a simple game. He has no programming experience yet, but I am a programmer (business apps, not games) so I can teach him programming, but what would be a good platform for him to start on? Initially I'm looking for something that can provide quick results, to keep his enthusiasm up.

What would you suggest?

# Answer
> 30 votes
XNA is a good solution for a fairly confident programmer. It would be a good goal to aim for in the future.

The Unreal Development Kit is a way to get results far more quickly and easily, and might be a good place to start. **Comments have indicated that the UDK is actually a pretty *bad* alternative, so I can't recommend it.**

Unity is an alternative, it will run on phones which is something UDK can't do (as far as I know). So if he's into programming games for phones, perhaps unity would be better?

# Answer
> 21 votes
I'm also 15, so I guess that could help? :P

I've recently started learning Python (been doing C++ for a year or so), and I'm finding it much easier to learn than C++. There're a lot fewer pitfalls, and you need little code to get something on the screen - what I find makes you want to continue.

And there are wrappers like Pygame and Pyglet over SDL/OpenGL for the graphics side.

Before he starts making simple games, I would advise learning a language for at least a couple of months. (Of course, text based games like guess the number and hangman are good exercises during this time)

# Answer
> 13 votes
A bit of an unorthodox answer here:

Starcraft II Galaxy Editor.

You can make almost any game within Starcraft 2.

It also teaches most programming constructs like loops and if statements in a GUI-centric way.

Once he's confident with the basics, you can have him script stuff.

If he's good at it, and finds this interesting, he will love proper game programming.

# Answer
> 10 votes
I would roughly divide game development tools into three broad categories:

1. Easy to learn and use, but limited. Game Maker, Game Salad, RPG Maker, Adventure Game Studio all fall into this category.
2. Powerful, but with a steep learning curve. C++ and other "hardcore" programming languages fit here.
3. Intermediate languages, generally scripting languages like Lua, Python, and ActionScript, which split the difference by requiring you to actually write some code but taking care of the more obscure details like memory management for you.

For people with no programming experience, I usually advise they start in the first category, just to get started doing SOMETHING. When they feel comfortable with a given authoring tool but are really feeling like the limitations are outweighing the benefits, it's time to learn something in the next category up.

# Answer
> 9 votes
I know this will date me somewhat, but growing up I really enjoyed P-Robots. There's a really simple goal (beat the other robots), a simple API, and a short amount of time between changes to code and seeing the results. It segues into AI, design patterns, and even larger-scale code structure (some of these robots can get pretty big -- and what about sharing code between robots?). If you can find something similar but newer it would be a good way to get the "getting started programming" part. Suggestions:

Once that's done, consider going for a really simple 2D scrolling shooter, platformer, or similar "arcade-style" game -- you can use SDL or XNA or whatever's most familiar. Even getting a pong clone up and running in these is not *entirely* trivial. This gives you a small echo of what it's like to build something "ground up".

After this, explore: a mod to an existing 3d game (a new object, or a bot, or something) to give a little insight into larger engines.

The keys, from what I've seen, seem to be:

* rapid iteration: the ability to see results quickly
* prototypes: many small experiments to get breadth of experience and confidence (okay, how would we do a marble game? how about space invaders? etc)
* exploration: learning to love looking into how other peoples' games are built, tweaking them, etc

# Answer
> 6 votes
My advice is to make web-based games. Why? Well, first of all, JavaScript is a beautiful language that will teach him all of the basic concepts of programming and you actually can make a great, competent and cross-platform game with it. It will also qualify him for many more things other than just making games... If you, for some reason, wouldn't like your son to get into web-development, then I suggest using Python, with a module called PyGame. I also have experience with that, and I'ts awesome. What I **don't** suggest is starting out with C/C++, that's what I did and it's awful and might get him unmotivated for programming altogether.

On another note, you're probably an awesome father, congratulations!

# Answer
> 5 votes
Mindstorms Roboter are really cool. We got some NXT's in school, and last week we started with programming things like follow a line, and that stuff. You can get easily results.

Also i found www.3dgamestudio.de a while ago. I didn't got more into it, but it was really interesting. You can programm with lite-C which is:

> Lite-C is a programming language for multimedia applications and computer games, using a syntax subset of the C programming language with some elements of the C++ programming language

At the http://tutorial.3dgamestudio.net/ you get into it. And there are also a level, model and terrain Editor.

ps: I am 16 and started with a friend programming a website and customizing a programmed game server. So this could also be interesting for him.

# Answer
> 4 votes
I can't suggest this enough, but **building his own levels for his favorite game of choice**.

For someone of that age/ skill level, they should start **by building levels in their favorite game engine of choice**.

Many great games come with a level editor that allow many degrees of freedom.

***RPG***: Obsidian's NWN 2 electron toolset series, Elder scrolls

***RTS***: Warcraft III's level editor is a fantastic RTS editor and even spun off it's own ***game*** ( league of legends and heroes of newerth ).

***FPS's***: Hammer for half-life 2. Counterstrike was originally a half-life mod.

Start here. Building levels for your favorite game is probably the best place to start.

# Answer
> 3 votes
Although all the information here is helpful, I wanted to mention that the STEM Challenge (a national game competition promoted by the White House and ESA ) has some suggestions about platforms http://www.stemchallenge.org/about/Default.aspx

Gamestar Mechanic, Gamemaker, Kodu, Scratch, PBS KIDS Ready To Learn Stream

I have a feeling that there are community resources about these platforms specifically as it relates to STEM.

See also this excellent tutorial about python and pygame (which is also an online book) http://inventwithpython.com/chapters/ here's the PDF of the sequel to the book specifically about pygame http://inventwithpython.com/blog/making-games-with-python-pygame/

Here's another NYT article http://www.nytimes.com/2011/11/10/technology/personaltech/computer-programming-for-children-minus-cryptic-syntax.html?\_r=2&sq=mitchel+resnick&st=cse&adxnnl=1&scp=1&adxnnlx=1322489239-tMp1Wjl9FUcI8rLaJ6cbOw

Update: here is a slashdot discussion http://ask.slashdot.org/story/11/12/27/152228/ask-slashdot-tools-for-teaching-high-school-kids-how-to-make-games

# Answer
> 2 votes
As Martin mentioned, the UDK is probably the fastest way to get something working as it comes with so many premade things like AI, models and also a wealth of books. It has a very good map editor, and the language is Java-esque (and ECMA-script like).

An alternative might be to try doing games in Flash or Silverlight - start off with simple 2D games. Whatever genre of games he likes dictates the toolkit.

# Answer
> 2 votes
Game Maker is an excellent choice for people with no programming experience. It has a free version and a relatively cheap paid version. It allows you to quickly make games with a drag-and-drop interface, but includes support for more advanced scripting.

# Answer
> 1 votes
Coming from a 14 year old, this advice might be useful. I find, the best way to choose a platform, is the platform most suited to the purpose. I've made this post many times before.

From Reddit\-

> Choose a language that suits your purpose. Most gamers don't care about what language the game is programmed in. They care if they can play it or not. They care if it runs fast on their computer. They care if the game isn't 10gb in size. They don't care if its an exe or jar.

Look at games such as Minecraft. Sure its written in Java, a language that has an extremely small market share in the game dev industry. Do the consumers care though? No. They care about the functionality.

However, since your son doesn't have any experience in programming, I suggest learning a language that is fast to code such as Python, or using an existing platform, such as XNA. Personally I love Slick2D with Java, but I guess thats my preference...

# Answer
> 0 votes
I was introduced to programming at a young age (younger than 15), and my Dad decided to use VB (1.0). We made a twisted version of pong using a timer object and GDI drawing. I liked that because we started with a blank canvas and were able to learn the basics of programming structures while trying to make something fun.

Today, I think I would choose XNA and pick a simple 2D game. C# and XNA are fairly straight forward and they leave you with plenty of room to grow, and they are free.

# Answer
> -4 votes
If he just wants to make games then he should use XNA, Unreal, Unity etc. If he wants to be a games programmer then he should learn C/C++ and OpenGL/SDL or D3D first.

XNA, Unreal, Unity etc are great for making games but really bad at doing far too much for you. I'm sure people will disagree with me on this, but these basically turn you into a lazy programmer and when the time comes to learn things like points in C++ it'll be more difficult because you went with the easier options first.

Peronally I never suggest anthing other C/C++ as the first language to learn if you want to be a games programmer. The main reason is that even if you go and learn C#/XNA , if you're seriously about becoming a games developer you will have to know C or C++ at some stage because no one will hire you otherwise. So if they're serious about the profession then you're only delaying learning what's expected from you.

---
Tags: platform
---


# Question
Title: 2D XNA Tile Based Lighting. Ideas and Methods
I am currently working on developing a 2D tile based game, similar to the game 'Terraria'. We have the base tile and chunk engine working and are now looking to implement lighting. Instead of the tile based lighting that terraria uses, I want to implement point lights for torches, etc.

I have seen Catalin Zima’s shader based shadows, and this would be perfect for the torches (point lights). My problem here is that the tiles on the surface of the world need to be illuminated, doing this by a big point light is firstly extremely expensive, but also doesn't look right.

What I need help with (overall) is...

1. To have a surface that is illuminated regardless of torches, etc.
2. To also have point lights, or smooth tile lighting similar to Catalin Zima’s shader based shadows.

Looking forward to your replies. Any ideas are appreciated.

# Answer
> 4 votes
**Finding the surface and applying ambient light**

To find which tiles are on the surface and should receive some ambient light, in a very simple way, how about doing a one dimensional (vertical only) flood fill starting from the sky?

In other words, you start at the top of your world, one column at a time, and search downwards until you hit a solid tile. All tiles that you search this way (including the solid tile) will be considered as being on the surface and get a constant light contribution added to them (i.e. you draw them a bit lighter).

For example something like this (where # is a solid tile, and . is a tile that will receive ambient light):

```
..........................
..........................
..........................
..........................
..........................
.....##########.###.......
..############ .#####.....
.#########     #########..
.#########  ############..
#####      ###############
##########################
##########################
##########################

```

Then just do the torches and everything else as point lights.

Finally, while I don't feel it's necessary, but if you also wanted to have the sun cast shadows on the surface, you should model it as a directional light rather than a point light (since the sun is "infinitely large and infinitely far away" for practical purposes). That basically means that every shadow will be coming from the same direction (i.e. forming the same angle).

**Adding some shading on the surface with Ambient Occlusion**

*Method 1*

If you'd like to add some variation to the lighting on the surface so that not every tile has the same brightness, you could try to compute some sort of ambient occlusion factor for the "surface tiles".

The easiest way, without having to rely on raycasting, would be to simply count the number of neighboring tiles that can block the sun light.

The basic idea is for each solid tile on the surface, count how many other solid tiles there are in the immediate surroundings (at the same level and above it). Use this number as a factor to decide how much light it should recieve.

For example:

```
.#.#.    .....
.#@#.    .#@#.
#####    #####

```

Consider the @ a solid tile. In the first example there's 4 solid tiles surrounding the @ while in the second example there's only 2. Thus the @ in the first example would be drawn darker than the @ on the second example.

This method has the disadvantage of only working on the surface, and being a somewhat crude approximation.

*Method 2*

Another alternative that will give better results but be a lot more expensive, would be to start with the entire world illuminated, and then for each tile do a series of raycasts towards the sky (in several directions, all along the hemisphere surrounding and above the tile) and count how many collided with terrain. Then darken the tile depending on the number of collisions.

This would allow ambient light to sip into caves and shed a little light into the underground too which would look pretty cool.

The biggest disadvantage besides having to do the raycasts is that you would need to compute this for every tile, not just the surface ones.

**Make the shading continuous instead of tile-based**

For this you'll need to use a pixel shader and do the previous calculations per vertex instead of per tile.

Each tile will be a quad, so start by calculating and storing how much light reaches each individual vertex of the quad. This could be for stored for instance instance as a grayscale vertex color (ranging from \[0,0,0\] to \[1,1,1\]).

Then simply read this color back in your pixel shader (which will automatically interpolate it across your quad's surface for you due to gouraud shading) and multiply it by the color you have read from the texture. This will allow smooth gradients within your tiles.

# Answer
> -1 votes
Does this answer your question?

“But how do I get global (ambient) lighting (with or without shadows)? I don’t want the rest of the “world” (background) to be pitch black.” Just render a quarter-strength (64,64,64) quad over the ShadowCaster map.

---
Tags: xna, c#, xna-4.0, lighting, shadows
---


# Question
Title: ELO algorithm for handling people who don't play often
I'm using the ELO algorithm to rank players in an ongoing pong competition. Most players play every day, but we've got one player who hasn't played in a month. My algorithm currently only tracks scores over the last 30 days, and as a result, this player is rapidly rising through the ranks, despite having never played. He lost a bunch of his first games, but won most of his last few games, which means that his losses are dropping off the charts and his score is going up as a result.

Obviously, my plan to drop off scores after 30 days isn't working. What other methods can I use to penalize players for not playing often?

The only thing I've come up with thus far is to reduce the points based on percentage that is based on the days of inactivity (i.e. if a user hasn't played in a week, his points are only worth 70% of normal, and he would have to play X times to get back up to 100% points).

However, this seems too arbitrary. Does anyone have any better ideas or suggestions for handling inactive players in an otherwise active environment?

Thanks in advance.

# Answer
> 18 votes
It sounds like you're storing the points awarded for each match, and then 'expiring' those point adjustments over time. Which, as you've noticed, is open to easy exploitation.

In a standard ELO implementation, your ELO score is forever; it does not 'decay' over time, as having points leave the ranking system in this way will eventually lead to overall score deflation (ie: 1500 will no longer mean 'average').

Remember that ELO rankings are not "points" in the way that game players usually think of them; they are an attempt at ranking a player's level of skill relative to other players, they are not a reward. These points should not be taken away as a punishment to the player, because they're the only tool you have to try to match players against opponents of a similar skill level. The only thing which should affect these values - ever - are wins and losses against other ranked players.

The approach taken by most games which want to stop players from achieving a high score and then vanishing, never to play again, is to have an activity requirement for the leaderboard display; if a player hasn't played a game in 30 days (or whatever), they simply don't show up in leaderboards until they do. When the player returns and plays another ranked match, they return with their full ELO ranking, exactly as if they had never left. If their skill level has changed relative to other active players in the interim, the game will quickly notice that and adjust their ranking, through the standard process of winning and losing matches against opponents.

# Answer
> 4 votes
Algorithms like Elo and TrueSkill determine a player's skill based on the result of each game played, *without* respect to the passage of time. However, both algorithms come with an "uncertainty" factor -- in the case of Elo, there is a `K Factor` that is usually set high for new players, such that their Elo rating will converge on their "true" skill rating quickly. After a set time or a set number of games, the `K Factor` is normally reduced, so that the rating changes less between games.

What you're seeing is likely typical Elo behaviour (depending on your Elo implementation): your player has played fewer games than his competitors, which makes him a "new player" with a higher `K Factor`; since he's winning his games, the algorithm sees him as a higher-skilled player and awards him a higher ranking!

Note that ranking algorithms are generally used only for comparisons between players, and *not* to determine the outcome of competitions, given their behaviour. Given you want to reward participation, I'd recommend scoring players in the competition another way. Some suggestions:

* Score players based on the number of wins.
* Assign point values to wins/losses, e.g. 2 points for a win, 1 point for a loss.
* Only count the player's best X games in a given week/month.
* Require players to play a minimum number of games to "qualify".

Note that none of these solutions will give a completely "fair" result, as players who play more will have a higher score than players who don't. The only way to ensure fairness is for players to play an identical number of games.

# Answer
> 0 votes
I don't know about the ELO algorithm, but how about instead of penalizing people who don't play often, you *reward* people who play often? For instance if you made your score something like:

```
Score = (Wins / Losses) * (Total Games Played) * Some_Scale_Factor

```

Then people who play often would probably end up playing more games and having more chances at achieving an higher score.

And another thing that you might want to change is to prevent the purging of old scores from having an impact on the player's total score. That's the main reason why that player is rising in the ranks (and also why he'll eventually fall completely off the charts).

Also, people who play seriously for a while and achieve a great track record, probably won't be happy knowing that their achievements will eventually fade away and disappear. That system is seriously discouraging.

This is easily fixed just by keeping a cache of each player's "total games played" and "win/lose ratio", even after you delete the scores themselves.

With that information you can easily deduce back how many wins and losses the player had and update them accordingly whenever he plays again.

---
Tags: leaderboards, ranking
---


# Question
Title: How is animation handled in non-immediate OpenGL?
I'm a newbie to modern OpenGL. I'm comfortable with the immediate OpenGL methodology, but I've never done any serious use of VBOs. My question is about animation. In immediate mode, to achieve animation you just have to stream different vertex positions (interpolated from keyframes) in object space.

How is this achieved in non-immediate OpenGL? Obviously, uploading fresh VBO data for each frame is sure going to hog the graphics bus. I haven't found any literature about the modern way to do it. Thinking about it, I came to several options:

* **Attributes:** animation as a 3d offset. For each frame, a different (possible interpolated) offset attribute is passed for each vertex, applied to the same vertex each keyframe.
* **Indices:** storing keyframes as absolute vertices and accesing them through indexing, using a different set of vertices for every keyframe. I find this approach impossible, since you can't access adjacent keyframes and therefore can't interpolate between them. Also, seems like a bad idea for procedural animation.
* **Texture:** this might be very stretchy but sounds like a good solution for me. Again, animation is thought as an xyz offset for each vertex. Each keyframe can be stored in a 1D texture where the dimension maps to vertexID.If I'm not mistaken, in OpenGL 4.0 you can access textures from any shader, so you could read this texture from the vertex shader and apply each vertex transformation. A 2D texture could hold several frames. You still perform interpolation (and if interpolation works for textures outside of fragment shader, which I'm not sure of, you can linearly interpolate for free!) This could be applied to more complex animation systems like bone animation without much effort.

Am I overthinking this? Can anyone shed some light?

# Answer
> 5 votes
> I haven't found any literature about the modern way to do it.

That's generally because the "modern way" to have character animation is to use skeletal bone weighing, not vertex blending.

However, if you insist on doing vertex blend-based animation, you can. The simplest way is to simply send the two keyframes you want to blend between as the attributes. You have position data for all of the various keyframes; just use `glVertexAttribPointer` (or `glVertexPointer` if you insist) to pick specific keyframes. Since each keyframe should have its position data stored in the same order (for corresponding positions), they can use the same index list for rendering.

The shader gets two "position" attributes, one for the keyframe in front of the current time and one for the keyframe after. You would also pass a uniform that specifies how much of a blend to do between them. You compute the new position as a blend between the two keyframes, and then do the usual transforms from there.

---
Tags: opengl, animation, vbo
---


title: Feasibility of an XNA game on PC

text:
# Question
Title: Feasibility of an XNA game on PC
A friend and I are doing a 2D XNA game. Thus far, the API seems really cool and performance is acceptable. My question is more towards the release of it though. As other developers how have done games, how well have they done for you on PC (as far as downloads, sales, etc)? I know the statistics about the Xbox360 from seeing it personally but, I was curious as to how successful these were on PC?

# Answer
I don't have any stats to compare the differences between XNA and non-XNA game sales - I'd suggest that data is impossible to come by - but I imagine it would show there is no difference for equivalent games. So let me answer your question with a run through of the major issues specific to distribution of XNA games on PC (particularly online):

---

First of all: For an XNA game to run the system needs to have installed: the XNA Framework, and the .NET Framework.

The XNA Framework is a fairly small download, easy to install, but will requires admin privileges - so will cause a UAC prompt as well as a EULA prompt. The framework is not upwards or downwards compatible - but can be installed side-by-side. (ie: a XNA 3.1 game needs XNA 3.1 and won't run on XNA 4.0).

The .NET Framework 2.0 is bundled on Vista and above, so I recommend targeting that (Project Properties -\> Target Framework). \[UPDATE: XNA 4 requires .NET 4, so this won't work any more\]

The .NET 3.5 installation is very, very slow - I recommend avoiding it. I'm not sure about the full 4.0 installation, but the 4.0 Client Profile install is fast enough if you need newer .NET features (you probably don't - you can still use lambdas and extension methods in .NET 2.0).

A .NET Framework install will of course cause a UAC and EULA prompt. It can also cause a reboot.

---

Currently the "standard" way to distribute XNA games is with ClickOnce. You can do an online install - the downside is that your user gets a small "bootstrap" installer executable that pulls all the loose game files from your website. Alternately you can just distribute all those loose files and the installer in a zip. Neither of these is a self-contained executable file like users expect from most games.

A major pain of ClickOnce is that it will display several warnings about downloading unsigned software, which can look quite scary.

Another other downside of ClickOnce is that you don't have much control over things like, for example, what start menu entries you have.

The upside to using ClickOnce is that it's very easy to set up, and it will automatically download and install the required frameworks from Microsoft's website.

I am under the impression that these issues with ClickOnce can be solved by using an MSI instead - and it can still automatically download and install the required frameworks. I'm afraid I don't have specific instructions for this on hand.

---

If you do your own installation, or no installation at all, you need to be aware that your game executable will crash with an extremely unhelpful error message if the required frameworks are missing!

---

Oh, and your install might be a bit bigger (or a lot, if you include frameworks). If you're using XNA's built in content stuff (and why not, it's there and it's easy) your user might have more to download because the files aren't compressed as well as they might be if you handled it yourself (especially audio).

---

That's about it. Once the game is installed you're in pretty much an identical situation to any other game using native DirectX (ie: most of them).

(If you're doing something like CD-ROM distribution, instead of online distribution, you may face some of the same issues I described - but you can put everything that would otherwise need to be to be downloaded onto your CD instead, including the required frameworks.)

If you're doing downloadable shareware you're basically trying to get users along a chain from finding out about your software, to playing the demo, to buying the full game. The downside of XNA is that it makes the installation step in this chain a bit harder to polish - but it's still possible.

(IMO the upside of easier development and XBox compatibility is well worth it.)

So to bring this back around to your question: using XNA might make a tiny difference - but not enough that it matters. So any stats you find about PC game sales should be applicable to XNA games on PC.
> 25 votes

# Answer
It's been more than a year since this topic was created, and since then there's been quite a bit of development on the XNA side. For instance, here's a list with a few popular XNA games that have been released for PC and are currently being sold on Steam:

...and these are only the ones I happened to buy and noticed that they used the XNA runtime - I'm sure there are more of them that I'm unaware of.

And in case you don't know them, *Terraria* sold an amazing amount of copies (if you couldn't tell from the "over one million copies sold" disclaimer on the link above), remaining in Steam's best sellers list for a long time. And *Bastion*... well it just won three Spike VG Awards (incluiding best downloadable game of the year) a few days ago.

I also urge you to check the other games. *Chime* is an amazing casual/music game providing an extremely relaxing zen-kind of experience. And Sequence is a really original mix of DDR and RPG (with some music by Ronald Jenkees for those who know him). Finally, Magicka is an action RPG similar to Diablo which is also pretty cool.

I suppose that should say something about the feasibility of using XNA for developing PC games.
> 5 votes

# Answer
No idea on actual stats, but it might be worth seing if you can find anything about blueberry garden and flotilla. Both are written with XNA and both are avalible on steam. Flotilla even has some steamworks (just friendlist i believe) support built in
> 1 votes

# Answer
By creating your game using XNA, you are not going to hurt your sales too much. (Granted, users on Mac/Linux won't be able to play). What is going to be a bigger factor is the advertising, teasers, demo, and actual game play.

Most windows users are going to have everything they need to play your game. If you want to be really cautious I ubelieve you can have the installer check for requirements such as .net, xna runtime, directX, etc... And prompt them to install it.

Essentially, don't think that by using XNA, pure DirectX, or Direct3D that you will get bigger sales. You do get a bigger audience, but that doesn't equate to sales.

Focus on making a great game, invest some money in advertising (create a Facebook fan page and see if you can create some buzz there), spend time making a good teaser video, and most of all build a fun demo.
> 1 votes

---
Tags: xna, xbox360, pc
---


# Question
Title: How should I proceed next with my programming skills?
I am currently studying at University of technology in Brno (Czech Republic). This semester is almost over and I might say I have some knowledge of C. Since I went to this school just for the purpose to become a game programmer I would like to start programming a game asap.

My school project are almost done so I have been thinking about writing something already (story driven game running in terminal ^^). But this won't satisfy me.

My question is how should I proceed next? I did my homework and went trough similar questions but I didn't get the answer. I hope this question won't be closed. People are usually mentioning C++, C#, OpenGL and others and I simply don't know which one to choose.

I am currently interested only in 2D games and that won't change for some time. I don't want my game to run on a mobile device **yet** and I want to make games for PC and Mac, not for consoles obviously. Which language does fit my needs the best?

# Answer
Since you seem to know a bit of C, you could always try to use C++ with SFML, or C with SDL for 2D games. It frees you from having to handle OpenGL directly. It's also cross-platform on the PC, Mac and Linux.

Since you have no wish to bring your game to mobile distribution, I suggest that you stay away from Javascript for the time being. It is not very appropriate for graphically rich or long-drawn out games like the adventure/story games you mentioned you wanted to do.

However, if you just want to create some basic games for experience, then of course, go for Javascript! Javascript seems to have a lot of potential and is capable well enough for simple arcade games.
> 1 votes

# Answer
I would recommend to try C++ for the following reasons:

* it continues being relevant for a long time, so it would be useful in multiple scenarios. Even Windows 8 will support Metro-style apps development with C++;
* it is pretty much a standard in traditional mainstream gamedev;
* it is easier to move from C++ to modern languages than the other way.
> 1 votes

# Answer
I would start with java because it is a multi-platform language that can run on any Operating System and it is very similar to c++. It is also widely used in 2d and 3d games over the internet usually as browser based games, e.g. Runescape and if you ever wanted to migrate over to the android mobile device it would be simple, because android apps are written in java. Also you might want to try DevianArt for the concept art of your games. You can find an artist who will draw sprites,portraits,start screens and pretty much everything else, for reasonable prices or maybe even free.But to really get started just go to you tube and look up some game development tutorials i recommend TheNewBoston because he teaches free tutorials on Game Development in many different languages.

Hope all this helps you on your decision!
> 0 votes

---
Tags: 2d, software-engineering, c
---


# Question
Title: How can I specify which enemies to spawn for each round in a tower defense?
I am making a TD game in Unity, and I would like to know the most common approach to spawning enemies each round. I have more than 200 rounds per map, just like Fieldrunners.

Is it some kind of hardcoding, say for 25 rounds and then repeat the same waves with harder enemies, or maybe logic/algorithm based on rounds, where it'll give number of enemies and type of enemies which will spawn in that round.

I have 8 type of enemies. I want to implement a function/equation which inputs round number and outputs "number of enemies" and "enemy type" keeping the difficulty level which is round numbers.

for e.g if input: 50th round, output: enemy type1, large no. of enemies, if the input: 2nd round, output: enemy type 1, less number of enemies

# Answer
Well, it depends on your choice of the game dynamics. You can opt to hard-code whatever sequence/level of enemies you want to dish out to the player, or you could have an adaptive controller that uses its AI to take the game to a challenging level, no matter how expert you are. Say, player A completes the first (perhaps hard-coded) level in 2 minutes, taking no damage. Your AI takes the time used to clear up the level, and the damage taken in the level (make up a simple formula using these two or perhaps other game variables) and then take the result to set the subsequent level enemy's health, armor etc.

Say, number of enemies in round n = ((n * 50)/time taken to complete level\[n-1\]) - (30 * damage taken)

So, our great player A completes the level in 2 minutes, no damage taken: no. of enemies for level two: ((2 \*50)/2) - (30 \*0) = 50 enemies

You can use a similar scheme for health, armor, speed etc.

As far as the types of enemies is concerned, I'll answer that later, I have a class scheduled to begin in 20 minutes :D
> 2 votes

# Answer
Here is how I do it:

I have a method named `setupWave` which initiates a round or wave:

```
- (void) setupWave {
    // remainingCount is the number of enemies that will be spawned in the current wave
    remainingCount              =   (int)((((waveCount + 1)/2.0) + ((gameDifficulty + 1)/1.5)) * 3);
    // dieCount is used to find when the wave ends
    dieCount                    =   remainingCount;

    [self                           stepAI];
}

```

this method `stepAI` creates an enemy and calls itself after a delay till the remainingCount != 0

```
- (void) stepAI {

    // code to initialize the enemy object goes here

    // you can adjust the enemy parameters like health, range, etc., based on current wave as below:
    tmpAttacker.maxHealth       =   BASEHP + (BASEHP / 10.0) * waveCount;

    remainingCount--;

    // calls the `stepAI` again after some delay to spawn next enemy, until remainingCount reaches 0
    if (remainingCount > 0) {
        [self runAction:[CCSequence actions:
                         [CCDelayTime actionWithDuration:TIMEBETWEENUNITS], //for delay
                         [CCCallFunc actionWithTarget:self selector:@selector(stepAI)], //calls itself again
                         nil]];
    }
}

```

this method gets invoked when the enemy dies:

```
- (void) attacker:(id)sender diedWhile:(AttackerState)tState {
    dieCount--;

    // if the die count reaches 0, that is after all the enemies in current wave are dead,
    // initiate the next wave after some delay
    if (dieCount == 0) {
        waveCount++;
        [self runAction:[CCSequence actions:
                         [CCDelayTime actionWithDuration:TIMEBETWEENWAVES], // for delay
                         [CCCallFunc actionWithTarget:self selector:@selector(setupWave)],
                         nil]];
}

```

All the coding is in Objective-C, I will change into pseudo code, if this is harder to understand.
> 2 votes

# Answer
There are different approaches to this. The one where you (as the game-designer) have most control, would be to define the exact types and amount of enemies for each round.

Of course you can also make this range based (to save you from defining each round separately), so basically:

* round 01 - 10: Spawn 10 x enemyA and 5 x enemyB
* round 11 - 20: Spawn 10 x enemyB and 5 x enemyC
* etc.

However, this type of ranged-based spawning won't provide much variation. Another approach would be based on probabilities (or weights). Something like:

* *enemyA* (ground) has weight `1.0` at round 1, `0.5` at round 10 and `0.0` at round 20
* *enemyB* (flyer) has weight `0.0` up to round 11, `1.0` at round 12 and `0.0` at round 13

Then you interpolate the weight given the current round. So with the above definition, *enemyA* has a weight of `0.75` at round 5.

Given the amount of enemies to spawn per round (you might want to ramp this up for later rounds) you can determine the unit mix by the given weights. As you can see, you can also make enemies appear only in one round (as shown with *enemyB*). If you design this carefully, you should be able to control the distribution of enemies nicely (and with good variations) without having to hard-code each round.
> 2 votes

---
Tags: unity, tower-defense
---


# Question
Title: How to handle similar actions in derived actors (inheritance)
I have a base class called `Attacker` that has a `update` method. The `update` method moves attacker through an array of waypoints as given below:

```
- (void) update:(ccTime)dt {
    if(state == kMove) {
        // code to move to next waypoint
        // on reaching the next waypoint, update the next waypoint variable
        // if the final waypoint is reached, then stop the movement of attacker
    }
}

```

So, the base class takes care of simple waypoint movement logic. Now I derive a few classes like `Rifleman`, `MachineGunner`, `Engineer` from the `Attacker` class.

Now I want each of the derived class to do a specific action on reaching the final waypoint. For eg., I want the Rifleman to change to attack stance, the machine gunner to deploy and setup his gun, the engineer to start constructing a defense.

How do I achieve this? My current idea is to check for final waypoint condition in the `update` method of each of the derived class and do the corresponding action.

```
- (void) update:(ccTime)dt {
    [super update:dt];
    if(state == kMove) {
        // if the final waypoint is reached, then do class specific action
    }
}

```

Is there any better way of doing this?

# Answer
If by "if the final waypoint is reached, then do class specific action" you mean just calling the "endFunction" then yes, polymorphism will do the rest. That is, if you implement "endFunction" in every subclass or have a default one in the superclass.
> 2 votes

# Answer
The simplest solution I can think of is to create a virtual function for whenArrivedAtFinalWaypoint, call that from update, and implement that for the child classes.
> 4 votes

---
Tags: architecture, polymorphism
---


# Question
Title: Implementing the Game State Management example into my game
I am creating a game using Visual Studio and trying to add the game state management example. I have added all the files from the example into my game but need to add in something to make it run the menu before the game starts. Any ideas on what I need to add, I've hit a blank.

# Answer
> 2 votes
I'm going to go out on a limb, and guess that you are trying to implement the following:

http://create.msdn.com/en-US/education/catalog/sample/game\_state\_management

The code should be self-explanatory, but the main idea is that you need to initialize a ScreenManager object in your main game class in order to be able to use the system. Take a look at the code below, and make sure you have something similar set up.

```
 ScreenManager screenManager;
 protected override void LoadContent()
 {
       screenManager = new ScreenManager(this);
       Components.Add(screenManager);
       screenManager.AddScreen(new BackgroundScreen(), null);
       screenManager.AddScreen(new MainMenuScreen(), null);
 }

```

---
Tags: xna, microsoft
---


title: Find sub-graphs in a graph

text:
# Question
Title: Find sub-graphs in a graph
The initial problem I'm trying to solve is for pac-man, but of course there must be thousands of other situations with the same problem. I consider the pac-man grid to be a graph (two ways of doing this: either each grid square is a vertex, OR each "intersection" is a vertex and the "hallways" are the edges), and try to find a path that eats all the food (not worrying about ghosts for the moment).

I've noticed that certain grids can be clearly separated into sub-grids, where there is a single bottleneck that must be crossed in order to get into/out of the sub-grid. This of course translates into being able to partition the graph into two sub-graphs that share a single node and no edges.

What algorithms exist for finding these sorts of sub-graphs (that are "pinched off" from the rest of the graph by a single vertex)? I'm looking for a quick run-down of what's out there, as a starting point for further research.

# Answer
**Keeping things simple**

I don't know the exact context of your problem, but I give below the most accurate solution possible given the specific question you've asked. However, if you want to keep things simple, it is better to construct the graph yourself. In that way, there is no need for you to identify subgraphs, since in creating them within a larger planar surface (the bounds of the maze) and inserting them into that "template" supergraph, you already know what the subgraphs are... similar to how Diablo builds its levels. The only (minor) problem there is that you are using a planar grid, so you would need to be sure that the supergraph can accommodate each subgraph as you place it, and that they connect door-to-door.

**Short answer to your stated question**

You need to look into toplogical graph minors, graph isomorphism, and how to find Hamiltonian cycles, since cycles are, in fact, the sub-graphs you are seeking (see explanation below). The basic problem of cycle detection is not too hard, but is costly to calculate, O(n^2). These links should indicate to you the basis of intelligently identifying the subgraphs you mention. However see my long answer for more detail, because graph theory is quite demanding.

**Long answer to your stated question**

I think you are oversimplifying and/or underspecifying the problem.

Consider any graph that is:

1. Homogenous, i.e. its nodes and edges are equal in every sense, no weighting for instance;
2. Acyclic, i.e. a tree.
3. Purely topological. (I like to think of topology-only graphs as bits of snapped elastic band connected together in a certain way. It has variable embeddings and/or directedness, depending on how you hold it up, and the lengths of individual sections are variable -- it's the *sequences* of connections that is important.)

With such a graph, I think you will see that it becomes impossible to identify subgraphs easily without much more specific criteria than you've given; an example might be, "seek subgraphs in v where at least one edge connects to a leaf node".

One factor that tends to make subgraphs identifiable (i.e. the clumping you see) to the human mind, is cycles. (Another factor is branches on a treelike structure, but *only if* the embedding can be recognised visually, as being treelike.) For instance, this maze is (ambiguously) acyclic, and you will notice no real clumping here, except for at the top right:

....If considered as a pure grid, then the area beneath the entrance at the top right would be considered a cycle of 4 vertices (grid cells); but if you considered the maze in a purely topological sense, you might consider that to be a simple dead end, and thus non-cyclic. Already, you may be beginning to see how your identification and elimination process must work.

...In Pacman, it immediately becomes clear where you are seeing subgraphs -- and there are a great many of them. In fact it's much like the IQ questions where you are asked, "How many triangles are there in this picture?"

So, algorithm? Through a conservative edge-reduction approach on a planar, 4-connected 2D grid, one quickly ends up with a graph like Pacman's, containing cycles. Cycles, or clumps of cycles (since a cycle may contain subcycles) are the "sub-grids" which you mention, connected by bottlenecks or chokepoints, depending on your chosen terminology. We first identify these cycles, then reduce them down to a single vertex which acts as a placeholder. Rinse, repeat. What this then gives you is a "skeleton" graph where each cyclic minor is reduced down to a single derived vertex. (Please see diagrams here, I cannot link SVG) However, because you may now have long chains of 2-connected vertices, you can take this a step further, by eliminating redundant vertices and edges in the resultant chains, resulting in the complete toplogical minor (or in layman's terms, essential connective/structural essence) of your original supergraph. This basically tightens up the "pinch points"you mention. Whether you will need this additional step or not, depends on what you are trying to achieve.

The wikipedia link diagrams the two-step process I outline above, using the dotted lines to show cycle-removal, and grey lines to show redundant edge removal. It also dips a toe into discussion of algorithm to find minors, but ***bear in mind as you read that***: From what I understand of your problem, you will wish to seek and eliminate/excise any cyclic minors within your supergraph, which is a *far* simpler problem than looking for more specific subgraphs in a given supergraph, such as seeking non-planar Kuratowski subgraphs to ensure graph planarity, the latter being something you will never have to attempt if you start with a maximally connected 2D grid and simply reduce from there.
> 5 votes

---
Tags: algorithm, graph, search
---


# Question
Title: How to rotate a moving canvas in Android
I am developing an Android game. In this game some trains are moving on tracks. I am able to move trains horizontally and vertically using two train images for horizontal train and vertical train separately.

Now I want to move a train that is coming on horizontal track to vertical, I want to visualize it as it is now taking turn and moving on vertical track.

How can I do this, do I need to use so many images for each turning pixel, or is there any other way to turn the train?

Please suggest.

# Answer
You can rotate the whole Canvas Object. Just look at the Canvas documentation in Android SDK Documentation Canvas.

You might want to to something like:

```
canvas.save();
canvas.rotate(90);
canvas.drawBitmap(...);
canvas.restore();

```

First, you save the current Canvas (or Matrix), then you rotate the whole thing, draw the image, and then you restore the Canvas orientation. Your drawing operations will be saved. One more thing: There is a method

```
canvas.rotate(degree, px, py)

```

this will rotate the canvas around the point (px,py). Could be better suited for your needs.
> 2 votes

---
Tags: android, html-canvas
---