title: OpenGL 3D Camera

text:
# Question
Title: OpenGL 3D Camera
And here I am again, looking for help with my OpenGL camera once again. This is starting to get embarrassing. Anyway, here's the deal: I think my OpenGL First Person free roaming camera is starting to work correctly. I can draw objects, see them, and my coordinate system is set up as expected. Great. I solved the gimbal lock issue by fixing the UP vector to be the Y unit vector and restricted the camera's rotation to no more than PI/2 and -PI/2 up/down. All of this is used to build the modelview matrix, which I invert and set at the beginning of every frame. Sweet. It can move in all directions and seems to work just fine.

That is until I try to change the projection settings. For whatever reason, no matter what I do, my clipping plane is always around +50.0 Z, regardless of the OpenGL calls I attempt. If I move the camera around and move it into certain positions, rotating the camera causes my objects to disappear and reappear. They tend to appear on the edges of the screen, and disappear near the center. In order to facilitate a better answer, allow me to state my assumptions:

* glFrustum only needs to be called ONCE. OpenGL maintains the Projection Matrix and AUTOMATICALLY multiplies the Modelview and Projection Matrices during rendering.
* The math on the gluPerspective page and glFrustum pages is correct, despite the gluPerspective matrix listing seemingly containing 19 elements when OpenGL only uses 16 of those.
* I'm assuming that the INVERSION of my camera's Modelview Matrix is somehow screwing with my Projection frustum. I have to bet it's something to do with how the rotation is being calculated.

Has anyone seen this kind of behavior before? Where should I look to start tracking down the problem? Am I doing this completely wrong?

Here is the step-by-step code:

```
// -[[ When my application is ready, this code is run only once ]]-

glMatrixMode(GL_PROJECTION);
glLoadIdentity();

fieldOfVision = 60.0f;
aspect = 1.5f;
near = 0.1f;
far = 100.0f;

ymax = near * tan(degreesToRadians(fieldOfVisionY));
ymin = -ymax;
xmin = ymin * aspect;
xmax = ymax * aspect;

glFrustum(xmin, xmax, ymin, ymax, near, far);

glEnable(GL_DEPTH_TEST);

// -[[ That should setup the viewing volume such that the field of view is 120.0 degrees, the near plane is at 0.1 and the far plane is at 100.0.  For whatever reason, my clipping plane is ALWAYS around 50.0, even if I set the far plane to 1000.0.  Additionally, I can move around objects using this camera and cause them to clip out by rotating the camera. Does this code snippet need to be run more than once?  I was pretty sure that OpenGL takes care of storing the Projection Matrix for the pipeline. ]]-

// -[[ The next chunk of code is performed at every frame. ]]-

glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT | GL_STENCIL_BUFFER_BIT);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();

// Pos, forward, and up are 3D vectors and forward and up are normalized before the modelview matrix is processed.

side = crossProduct(forward, up);

GLfloat m[] =
{
side.x, side.y, side.z, 0,
up.x, up.y, up.z, 0,
-forward.x, -forward.y, -forward.z, 0
pos.x, pos.y, pos.z, 1
};

m = matrixInvert(m);

// Multing onto the Modelview Identity
glMultMatrix(m);

foreach object
{
glPushMatrix();
object.translate();
object.rotate();
object.scale();
object.draw();
glPopMatrix();
}

glPushMatrix();
renderInterface();
glPopMatrix();

GLenum err = glGetError();
if (err != GL_NO_ERROR)
{
reportError();
}

glFlush();

// -[[ End per-frame drawing.  It looks right to me, but please let me know what I am doing wrong!  Thank you very much for your time and consideration! ]]-
</code>

```

# Answer
Do you set the correct current matrix prior to update the projection matrix (using glMatrixMode())? Please provide a snippet of your code where you set the projection / modelview matrices.

It should look something like this:

```
// Setup projection - needs to be done only if the projection
// params change, but doesn't hurt to do on every frame
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluPerspective(...);

// Setup view transform matrix (the view part from model-view)
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
gluLookAt(...);

// Draw scene
for each object:

// Setup model transform matrix (the model part of model-view)
glMatrixMode(GL_MODELVIEW);
glPushMatrix();

glTranslate(); // finally, translate object into position
glRotate(); // then rotate object
glScale(); // first scale object

[draw object]

// optionally draw sub-objects (if you have a scene graph / transform hierchy)

glPopMatrix();

```
> 1 votes

---
Tags: opengl, 3d, graphics, graphics-programming, camera
---


title: RTS Game AI Thread

text:
# Question
Title: RTS Game AI Thread
I have a project to make a real-time strategy game from scratch. I am still at the early planning stage, but I have been programming a little to see the mechanics.

I know how to program. I also have a good idea of how I will structure the game classes and the Rule-Based (state-machine) AI for the computer player.

I want to develop Doctrines, which will give a specific behavior to a specific unit (but can be used on many units at the same time), such as Scout, Follow Mission Route, hold Position (attack any approching enemy or retreat if overwhelmed), etc...

The doctrines will only apply to the units, so it will have a unit perspective, and not be aware on the whole map sitatuation.

The Computer AI will analyse the entire visible map and decide on which soctrine to assign each unit depending on another set of rules.

I am doing this in C# with OpenGL.

For now, I don't have much, only a few things in tests before I begin my main conception. I have a game loop where all the game processing (where I will call the update mouvement, combat, rendering, etc, one after the other) will happen, it is called very often if the Application.Idle event.

Now, I was wondering. Since there will be a lot of things to process in the gameloop, should the Computer AI and the Units select their actions in that loop or will it be too slow?

If I want all things to be simultaneous, Should I create a separate Thread for the computer AI? Or even a separate thread for every unit?

I don't have much experience with multi-threading. What would be the best approach for this?

# Answer
What does "from scratch" mean? Can you use something like XNA instead with DirectX?

You should be rendering something between 30 and 60 frames per second to have fluid motion. There is really no need to have more fps.

If rendering + logic takes less less than the 16ms that 60fps gives you, then there should be no need for an AI thread.

If you won't have enough time between rendering the frames then you are going to have to think really carefully on what *must* be updated every frame and what does not.

I'd guesstimate that the "doctrines" part should be as simple and efficient as possible so that it can be updated every frame, at least for visible units and other units nearby. The units that do not influence the visible units directly can be updated less frequently (and, correspondingly, with a greater delta T).

The main AI has more work to perform, as it has to process all the units on the map and figure out a strategy, so it should require most of the computation time. It is the first candidate for a separate thread.

Note that you might want to add another layer between the two, something like an squad level AI. Basically, each unit's AI should make sure the unit responds "intelligently" to the immediate situation, so it needs to be fast and responsive. The squad AI is responsible for the "intelligent" actions of several units, spread across several seconds, like finding a bridge if the squad needs to cross a river. And the main AI should direct the actions of lots of squads over a long period of time.

Especially if you don't have a lot of experience, don't do threading if you don't have to. This will be complicated as it is without an extra burden. You can learn multithreading as a separate project, or as an extension of this one once it is in a *working* state. Good luck!
> 3 votes

# Answer
Have a separate thread for AI. But not for every unit since it would consume too much OS resources and synchronization would be a nightmare.

Make sure the AI thread would find an opportunity to execute. Don't take it lightly, if the main thread does too many things, it may never find that opportunity! If you simply give higher priority to AI thread, then the game becomes unresponsive, which is unacceptable.

So, carefully select sync points and/or events in main loop and allow the AI thread to complete its calculations while the main thread stops. For example, if the user unit sees another AI unit, sync it, so your unit sees an updated unit vice versa.
> 0 votes

# Answer
I am also working on a RTS game from scratch. I haven't tested it yet, but my idea was to run unit AI in the main game loop for all units that are currently visible to the player (in the part of the screen that the player actually see's or near the border of that screen), as it is more likely that the player will move the screen a bit.

The other units are checked in a separate thread, and I have two priorities: 1. Units that are in places which are visible to the user if he moves the screen there. 2. Units that are in hidden areas (not yet explored and "fog of war").

For units in the seconds priority, i run the loop less often, and compensate by moving them retrospectively when needed.
> 0 votes

# Answer
Whether you need to multithread or not, it might be a good idea to prepare the AI to be multithreaded.

Your main thread would update the world, tick the physics, etc, and then would populate a data structure that represents the AI's view of the world: position of units, state of resources, etc. This data structure would cache the main systems, rather than just hold pointers to them. This is sometimes called a synchronisation point.

Pass this data structure to the AI, and only allow it to reason on the contents of this structure. If you find the AI needing more info, add it to the structure. In AI parlance this is often called a blackboard but could also be referred to as a cache. Never let the AI write to the cache, the output should come through a seperate data structure.

This setup will allow you to parallelise the game because the AI no longer has any direct dependency on the other game systems. Those systems don't need to be threadsafe and you should never get locks. You can safely run the renderer or something while the AI whirrs away.

As a secondary benefit, you can in future extend the cache by decaying the information you get from the other systems over time, simulating uncertainty rather than exact knowledge.
> 0 votes

---
Tags: c#, ai, multithreading
---


title: Populating Sprites

text:
# Question
Title: Populating Sprites
I am making a android game, it's a tower/base defense like type of game (yea I know it is kind of confusing), I was wondering if anyone knows a good way to have the attacking sprites randomly generate without the number of sprites being higher than the level. I want the attack sprites to equal the level. I have 2 sprite types that I want to be generated, I just don't know how to make it to where one of the two randomly comes. Ex: you on level 4 and Sprite A spawns and then 3 others right after it but which version you get is random.

# Answer
I presume you're running in Android's flavor of Java, so

For generating random numbers, see this.

You'll need to setup a loop, which will load your extra sprites:

```
// you may wish to use a seed, so you can re-generate these numbers later, this depends on your use
Random gen = new Random();
for(int i = 0; i < currentLevelNumber; i++)
{
    double r = generator.nextGaussian();

    if(r > 0)
        // sprite type A
    else
        // sprite type B
}

```

I'm assuming you already know how to load, draw, and update sprites. If not, start here.
> 1 votes

---
Tags: java, android, game-mechanics
---


# Question
Title: What is a good flat file format for storing a 2D tile map that can grow infinitely in any direction?
I am creating a simple map engine that will automatically expand in any direction with procedurally-generated content as needed.

What is a good way to store map data, anchored at a 0,0 origin so that a rectangular subset of map data can be loaded quickly and efficiently from any point on the map?

I have an idea that maybe I should chunkify the map into distinct sectors and then use some sort of header format to identify where in the file a specific sector is stored. Is this a good technique or are there better, more efficient techniques that I can look at?

# Answer
> 7 votes
I would advise against using a single flat file for theoretically infinite amounts of data.

If you have a theoretically infinite amount of data then you need **random access**, which means **multiple files** or a database - or an indexed flat-file format, which involves re-solving the indexing problems *already solved* by file systems or a database.

If you spread your chunks across multiple files, getting the chunk at (-110, 5000) is just a matter of saying "%APPDATA%/game/map/-110/5000.dat" (or some other filename if you want to begin compressing them). Databases just need a query. If a chunk doesn't have any data, you can just not store anything. A single flat file doesn't offer the speed and convenience of random access right off the bat.

In a single file of arbitrary size, for fast random access you must have a guarantee for the position of any chunk of data, which means using an index (since a raw binary search through your data chunks hurts performance, and creating a grid in your file with "blank" spots gives you Byte56's problem). Once you develop an indexing system, give it efficiency and write yourself an API, you've recreated something like the file system or a database. Unless you actually gain something out of doing that it probably isn't worth the investment. For instance, Steam benefits massively from their GCF/NCF file formats.

If you want some security on your saves, it's still possible to do that. For instance, you can encrypt each individual chunk. In order to prevent them getting deleted, you could have a central hash based on existing saved data. If the saved data doesn't match up to the hash (and your program didn't cause the change), a chunk's been deleted.

# Answer
> 4 votes
The solution used most often seems to be to split into lots of files, however your question does imply a single file only. The only sensible option for this (in my opinion) is to emulate a very simple file system inside that single file. It's not actually terriby hard to do, but you really should consider using multiple files if you can.

If you have to stick to one file, then you might find inspiration for your implementation from the ext2 fs. http://en.wikipedia.org/wiki/Ext2 I know it helped me make some good decisions when I had to implement a simple FS for a game.

But really, for any growing map, it's usually better just to use a file for each "accessed" chunk.

# Answer
> 4 votes
I implemented a chunking system for my game when I was fiddling with infinite worlds (not sure if I'll keep them or not). For use with a single file, at first I used the chunk's world position to calculate a byte offset into the file. This assumes a static chunk size, or at least a static maximum. However, if the user were to head off in one direction for a while, this file would become pretty sparse for it's size, since there were large areas of land that hadn't been generated yet so there was blank spaces in the file.

I also tried a two file system. One file holds a map of "chunk position" to "chunk file offset" pairs. The second holds all the chunks. When a new chunk is generated, it simply goes on the end of the chunk file, and it's offset is stored in the position-\>offset file. This one was an issue when you had a LOT of chunks and finding the offset in the position-\>offset file took a bit of time. If you find it feasible, you can load the position-\>offset data into a hash-map on load, to have quick access.

I'm using the second one option for now, but may switch to something else if I find that the performance is lacking. Maybe with this information you'll be able to create something that works for you. Good luck!

---
Tags: tiles, maps
---


# Question
Title: How to balance a ball on a rotating plane?
I'm doing some research and I really don't want a physics engine when a simple mechanism will do. I have a ball that will be balanced on a plane. The ball will always be "stuck" to the plane and never roll off of it. The player/user will be moving this plane vertically up and down, changing its angle (rotating it some) and changing it's length. What I want is for the ball to roll along the plane as the user is interacting with the plane.

For example, player touches a surface with two fingers, touch 1 is the plane starting vector and touch 2 is the plane ending vector. The player can then move the two fingers around (increasing/decreasing the length of the plane) as well as move their fingers vertically and horizontally changing the planes position in 2d space. While doing this the ball moves along the plane with normal gravity trying to pull the ball down to the ground.

Does anyone have any idea on how to approach this? I started to think that this would be simple but then figuring in the dynamically changing length of the plane I got a bit lost.

I'll be doing this in XNA or Silverlight.

# Answer
I don't know if I understand your problem correctly, but here is how I would go with the constraints that I understood:

I guess you could simply apply gravity to the ball, then resolve the collision with the plane by moving the ball above the plane perpendicularly to the surface, making the ball move along the plane based on the orientation of the surface.

If you want to prevent the ball from falling from the plane, then just restrict its position when it gets to the borders of the plane.

As for the dynamic changing length, the only problem that I would see is when the user would want to make the plane smaller than it actually is when the ball is at the border. You could just solve this by moving the ball along with the new border.
> 7 votes

---
Tags: xna, c#, physics, game-mechanics
---


title: OpenGL ES GL_FIXED versus GL_FLOAT

text:
# Question
Title: OpenGL ES GL_FIXED versus GL_FLOAT
I am writing an app for Android, using OpenGL ES 1.x

I am confused as to whether I should use GL\_FLOAT or GL\_FIXED, the priority being performance regarding GPU operations(does GL\_FIXED need to be converted etc. ex: GL\_FIXED fits EXACTLY with the precision I need but if it is converted to a float then using it is pointless).

This book seems to say that it is ALWAYS preferable to use GL\_FIXED for vertices: "The major exception is with vertex data, which should never be given in floating point..." Here (paragraph right above the subtitle "Vertex data")

But I have seen others saying floating point is better..

# Answer
> 3 votes
In commercial game development for TV game consoles, we never store vertex positions on disc or network as floats, because if more than 8 or 10 bits of precision is needed, a model can be subdivided until each piece requires only 8 or 10 bits.

So for speed of download or loading from a disc, floats lose out to fixed point.

As for speed of rendering, this is an issue only when vertex shading is bottlenecked by vertex buffer read bandwidth, which is actually not likely unless your vertices are really fat beyond just the position being 3x32 bits.

---
Tags: android, opengl-es
---


# Question
Title: Is there any way to embed browser component into game for facebook Authentication?
Say I have desktop game and I like to make it social, for that I need browser component embedded into my game ( c++ openGL) for the Authentication part. Is there any framework for that?

# Answer
I never tried myself, but you can find some C++ libraries.
> 2 votes

---
Tags: facebook
---


title: Chrome Angry Birds engine?

text:
# Question
Title: Chrome Angry Birds engine?
Was Chrome AngryBirds game made using html5 canvas? And if yes: what kind of engine did they use?

# Answer
> 14 votes
Yes. ForPlay.

WebGL and Canvas 2D code paths exist for maximum performance and platform support respectively. The ForPlay GWT library helps with the abstraction. See the Google IO presentation Kick-Ass Game Programming with Google Web Toolkit for details.

# Answer
> 6 votes
It is based on WebGL (which means canvas is used, but not the standard canvas environment). As iOS uses OpenGL I think they ported that to javascript.

# Answer
> 4 votes
Inspecting the page element gives me `<canvas width="1024" height="768"></canvas>` so I guess that means it is canvas.

As for the engine, I assume they ported their iOS one.

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


# Question
Title: rendering a spritebatch to a temporary buffer and then offset that to the main screen
I've been trying to figure out how to do this but I have a bunch of screens, each with their own `Draw` method. However, I'd like to render all sprites offset by the screen position without altering their locations before I do the drawing.

So, if I render a sprite on a screen at 0,0 but the screen itself is offset to 50,50 it still renders to a window position of 0,0 instead of to the window position of 50,50.

I've been thinking about rendering each screen to their own texture and then rendering that texture to the main spriteBatch - but reading another question you could lose a lot of information such as alpha transparency

Any help will be appreciated to get me on the right path. Thanks.

Update: Also I'd prefer it to be recursive so that screens within screens are also offset appropriately.

# Answer
Use `GraphicsDevice.Viewport` to set the current viewport, which is effectively a canvas with its own coordinate space (i.e. `SpriteBatch.Draw()` will use the viewport's coordinates).

The viewport is defined in terms of window coordinates, so in order to have a recursive solution you'll need a class which keeps track of the translation of its own coordinate space to the window coordinates.

Something like the following:

```
Class CustomWindow
{
  CustomWindow mParent;
  int mX, mY, mWidth, mHeight; // Relative to the parent window
  Viewport mViewport; // Must be absolute coordinates, relative to the main window.
  void OnCustomWindowMoved()
  {
    mViewport.Width = mWidth;
    mViewport.Height = mHeight;
    if (mParent == null)
    {
      mViewport.X = mX;
      mViewport.Y = mY;
    }
    else
    {
      mViewport.X = (mParent.mViewport.X + mX);
      mViewport.Y = (mParent.mViewport.Y + mY);
    }
  }
}

```
> 2 votes

# Answer
I think you could change the view port between calls. This would do exactly what your asking (window position would be shifted).
> 1 votes

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


# Question
Title: Do game companies usually provide their artists/modelers with drawing tablets?
Or do you have to provide your own? How essential are tablets for game development?

# Answer
Of course tablets are essential for cg artists. Even in the smallest company artist have company (and big) tablets.

I can't imagine company which would ask you for bringing your own, maybe some garage startup...

As a employe you will make money to your company, they will take care about your equipment - so you are optimized and comfortable to make even more money for them :-)
> 7 votes

# Answer
Totally depends on the company. I doubt there's a standard for this, since this would be up to the artists preference. My work provided me with a ergonomic keyboard when I asked for one. So the best you can do is ask when you're hired, or if it's critical to you, make it a condition of your employment.
> 3 votes

# Answer
I am going to try and suggest the underlying question is along the lines of "What technologies are good for an artist who wants to get into game design/development" as opposed to do companies provide tablets.

In general use whatever technologies allow you to do your best work. If that is a tablet drawing surface then so be it. If a company likes your work they will hire you and provide the interface you are most comfortable with.

Now to wrap it around to the originally posted question, the company I previously worked for Did buy tablets for the artists who requested them which was just under half of them. But this did extend to every department with their interfaces. Natural keyboards, mice even displays and audio devices as needed were provided.
> 2 votes

# Answer
If the company feels it will make you more productive and in turn that this enhanced productivity will recoup the cost in a reasonable amount of time they will buy you almost anything job related.
> 1 votes

---
Tags: art, game-industry
---


# Question
Title: What I need to do to integrate in game micro payments for virtual goods in desktop games?
Does anyone here have experience in implementing in game payments , does such thing is possible ? Where should I look in to?

# Answer
You should be able to implement Paypal payment using their SOAP API ( http://tinyurl.com/6k447de ) and any C++ SOAP library such as Apache Axis ( http://ws.apache.org/axis in C++/Java ) or gSOAP ( http://www.cs.fsu.edu/~engelen/soap.html in C/C++ ). Google Checkout doesn't seem to support SOAP at the moment through.

However, I think that the easiest and comfortable way to implement in game payments is by adding an html layer into you game ( Qt Webkit is such an example: http://doc.qt.nokia.com/4.7/qtwebkit.html, and Awesomium: http://awesomium.com ) , and to develop an online item store on your website. Thus players can browse and buy items from inside and from outside your game using their account.

Anyway you will have to connect your server to save the items bought by players, so they can delete/crash and reinstall their game without loosing what they paid for.

Note: I never tried it myself, those are only hints to help you in your quest as nobody answered yet.

---

Edit: I added Awesomium ( http://awesomium.com ) as example for html layer api. "Awesomium, is the first full featured, windowless web-browser framework". It seems very interesting, powerful and clean. Furthermore it's Free for Indies companies (under $100k income last year).
> 3 votes

---
Tags: monetization, casual-games
---


# Question
Title: Tiled based map collision detection problem
I'm working on a tile-based Mario clone.

This works all fine when walking and falling. But when the player jumps near a wall and walks to the right in the air, then the player get stuck on the wall. The player sprite falls again when the player releases the key.

The setup is pretty easy and i can't find the problem. The map is build up as a 2D array with map blocks. A block can be solid or not. Player can't move trough solid objects, duh..

In the game loop:

* the player's location gets updated (gravity, movement ect.)
* check the map on collisions. When a collision is found in the Y, then the player location gets updated so it's above or below the block (depending the direction of the player), then the collision box gets updated with the new location. Then the same process for the X.
* The collision box gets updated to the new location (a free location). The box is adjusted so that it's little higher to get the block below the player to check if he's landed. This is to change the state of the player, from flying sprite to idle ect.

I also tried to switch the X and Y check so that the player is moved on the X line. Then when the player moves the movement goes very laggy. When i push and release the button to move, then the player moves faster but in chucks. Very trippy..

Does anyone sees the error or can give me a better collision algorithm for this?

## UPDATE (didn't updated the code)

I swaped the x and y check method and implemented the isonland variable. So when walking and jumping against walls works perfect. Only now, when the player jumps Mario get set back when landed. This because the X check method goes first and adjust Mario's position.

How can I solve that?

Map class update method:

```
public void update(int timeElapsed) {
        //update entities
        for(Entity entity : _mapEntities) {
            entity.update(timeElapsed);
        }

        //update objects
        for(MapObject mapObt : _mapObjects) {
            mapObt.update(timeElapsed);
        }

        //check for collisions
        checkMapCollision();
    }

```

Entity (abstract) update method:

```
public void update(int timeElapsed) {
        _velocity = new Vector2d(0.0F, 0.0F);

        //add gravity
        _velocity.y = Map._GRAVITY_PER_SEC * timeElapsed;
    }

```

Mario (extends entity) update methos:

```
@Override
    public void update(int timeElapsed) {
        super.update(timeElapsed);

        if(_state == STATES.IDLE) {

        } else if(_isMoving) {
            _marioSmallWalk.update(timeElapsed);
        }

        if(_state == STATES.JUMPING) {
            setVelocityY(getVelocity().y + _jumpSpeed);

            _jumpSpeed += _JUMP_DECREASE * timeElapsed;

            //falling?
            if(getVelocity().y > 0) {
                setState(STATES.FALLING);
            }
        }

        if(_isMoving) {
            double walkSpd = (_WALK_SPEED_SEC * timeElapsed);

            if(getFacing() == FACING.LEFT) {
                walkSpd = -walkSpd;
            }

            setVelocityX(getVelocity().x + walkSpd);
        }

        //falling?
        if(getVelocity().y > (Map._GRAVITY_PER_SEC * timeElapsed) + 1.0F) {
            setState(STATES.FALLING);
        }

        setPosition((int)(getX() + getVelocity().x), (int)(getY() + getVelocity().y));
    }

```

Map class CheckMapCollision method:

```
public void checkMapCollision() {
        //enteties move so check it
        for(Entity entity : _mapEntities) {
            //get the corners
            Rectangle bounds = entity.getBounds();
            Block[] corners = getCornerBlocks(bounds);
            Vector2d dir = entity.getDirection();

            //moving down
            if(dir.y > 0) {
                if(corners[2].isSolid() || corners[3].isSolid()) {
                    Rectangle blkBounds = null;

                    if(corners[2].isSolid()) {
                        blkBounds = corners[2].getBounds();
                    } else {
                        blkBounds = corners[3].getBounds();
                    }

                    entity.setPositionY(blkBounds.y);
                }
            } else {
                if(corners[0].isSolid() || corners[1].isSolid()) {
                    Rectangle blkBounds = null;

                    if(corners[0].isSolid()) {
                        blkBounds = corners[0].getBounds();
                    } else {
                        blkBounds = corners[1].getBounds();
                    }

                    entity.setPositionY(blkBounds.y + blkBounds.height + bounds.height);
                }
            }

            bounds = entity.getBounds();
            corners = getCornerBlocks(bounds);

            //moving to the right
            if(dir.x > 0) {
                if(corners[1].isSolid() || corners[3].isSolid()) {
                    Rectangle blkBounds;

                    if(corners[1].isSolid()) {
                        blkBounds = corners[1].getBounds();
                    } else {
                        blkBounds = corners[3].getBounds();
                    }

                    entity.setPositionX(blkBounds.x - (bounds.width-entity.getCurrentSprite().getOffsetX())-1);
                }
            } else {
                if(corners[0].isSolid() || corners[2].isSolid()) {
                    Rectangle blkBounds;

                    if(corners[0].isSolid()) {
                        blkBounds = corners[0].getBounds();
                    } else {
                        blkBounds = corners[2].getBounds();
                    }

                    entity.setPositionX(blkBounds.x + blkBounds.width + (bounds.width/2));
                }
            }

            bounds = new Rectangle(bounds.x, bounds.y, bounds.width, bounds.height+1);
            corners = getCornerBlocks(bounds);

            //moving down
            if(dir.y > 0) {
                if(corners[2].isSolid() || corners[3].isSolid()) {
                    Rectangle blkBounds = null;

                    if(corners[2].isSolid()) {
                        blkBounds = corners[2].getBounds();
                    } else {
                        blkBounds = corners[3].getBounds();
                    }

                    entity.landed();
                    System.out.println("landed");
                }
            }
        }
    }

```

# Answer
I have found out what I was doing wrong.

The key lies in **when** you update the position. What i did wrong was that I did the 'change positions first and then check and adjust' method, and I had to do it in the order, check and then update.

My previous code did the following:

* update entities locations with velocity.
* check for collisions and update the entities locations.

This resulted in that after the player jumped, Mario's location was changed in the update method so that the collision box would be in the ground tiles. Then the collision method changed the X position to the x of the left bottom corner and then the y would move it to above the ground tile. This means that Mario get shifted back a few pixels every time the player would land from a jump.

I have tried to swap the X and Y check methods, but then the problem just changes to something else (the wall hug).

Now the solution, I have changed it to the following:

* update entities velocity.
* collision method
    + try to place the entity on the X with the velocity, if failed, change it as best as posible.
    + try to place the entity on the Y with the velocity, if failed, change it as best as posible.

Now the X get checked/changed first and then the collision box is updated with the new entity location. Then the Y get checked/changed.

This works like a charm :)
> 1 votes

# Answer
You sprite character gets snagged on the intersections between two tiles. See the following diagram, which depicts the situation at the start of your collision routine.

Mario was moved to the right due to player controls. This will place the sprite in the three tiles. Then, you perform the collision detection on downwards Y. Notice the point in the blue circle: this will detect a collision with the second block and tries to resolve it by setting the Y coordinate to the upper bound of that block, effectively suspending Mario in mid-air.

As soon as the player releases the key to move Mario to the right, the sprite will not move into the wall, and the point that previously would detect a collision, will not register a hit. This will allow Mario to fall to the ground.

The quick and dirty resolution to this problem is resolving X collisions first, and only apply gravity when the player is not on the ground. If you would keep the gravity, the same problem would occur when walking around (this is the 'trippy' behaviour you have seen already after swapping the X and Y check ;) ).
> 8 votes

---
Tags: java, collision-detection, tiles
---


title: Midpoint Displacement Algorithm

text:
# Question
Title: Midpoint Displacement Algorithm
This question has come mainly out of **sheer desperation**, after spending several hours trying to figure out the problem.

If you cast your eyes to the picture above, you should see that my midpoint displacement algorithm algorithm is working (somewhat) successfully; in producing a somewhat coherent noise pattern.

However, it is leaving behind a black dotted grid on the image, and I have no idea why. I can foresee this being an issue in the math, but I just cannot see it; nor was this pointed out in any online resources as a possible issue; so any help will be appreciated as to hunting down this bug.

```
unsigned char** mdp(unsigned char** base, unsigned base_n, unsigned char r) {
    size_t n = (2 * base_n) - 1;

    unsigned char** map = new unsigned char*[n];
    for (unsigned i = 0; i < n; ++i) map[i] = new unsigned char[n];

    // Resize
    // 1 0 1
    // 0 0 0
    // 1 0 1
    for (size_t i = 0; i < n; i += 2) {
        for (size_t j = !(i % 2 == 0); j < n; j += 2) {
            map[i][j] = base[i / 2][j / 2];
        }
    }

    // Diamond algorithm
    // 0 0 0
    // 0 X 0
    // 0 0 0
    for (size_t i = 1; i < n; i += 2) {
        for (size_t j = 1; j < n; j += 2) {
            unsigned char& map_ij = map[i][j];

            unsigned char a = map[i - 1][j - 1];
            unsigned char b = map[i - 1][j + 1];
            unsigned char c = map[i + 1][j - 1];
            unsigned char d = map[i + 1][j + 1];
            map_ij = (a + b + c + d) / 4;

            unsigned char rv = std::rand() % r;
            if (map_ij + r < 255) map_ij += rv; // EDIT: <-- thanks! the bug! `map_ij + rv`, not `r`
            else map_ij = 255;
        }
    }

    // Square algorithm
    // 0 1 0
    // 1 0 1
    // 0 1 0
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = (i % 2 == 0); j < n; j += 2) {
            unsigned char& map_ij = map[i][j];

            // get surrounding values
            unsigned char a = 0, b = a, c = a, d = a;
            if (i != 0) a = map[i - 1][j];
            if (j != 0) b = map[i][j - 1];
            if (j + 1 != n) c = map[i][j + 1];
            if (i + 1 != n) d = map[i + 1][j];

            // average calculation
            if (i == 0) map_ij = (b + c + d) / 3;
            else if (j == 0) map_ij = (a + c + d) / 3;
            else if (j + 1 == n) map_ij = (a + b + d) / 3;
            else if (i + 1 == n) map_ij = (a + b + c) / 3;
            else map_ij = (a + b + c + d) / 4;

            unsigned char rv = std::rand() % r;
            if (map_ij + r < 255) map_ij += rv;
            else map_ij = 255;
        }

    }

    return map;
}

```

If you have any tips or resources other than http://www.gameprogrammer.com/fractal.html and http://www.lighthouse3d.com/opengl/terrain/index.php?mpd2 for fractal based terrain generation, I would appreciate them as comments also.

**Edit:**

This is the new image, as per Fabians suggestion (ty), however it still has some strange quirks, which you should be able to see straight away (small 'dimples' everywhere).

What could be causing this strange behavior? Updated source code: http://www.pastie.org/1924223

**Edit:**

Many thanks to Fabian in finding the bounds check error, for those interested, here is the current solution as 512x512 png. And current source code (modified by Fabian).

# Answer
The algorithm recursively adds a value, but the value can be positive or negative (normally +-1 / (2^octave) )

If you start at zero and only add positive values, then you can only go up, and that is why you're seeing the vertices pulled down.

try starting at 127 rather than zero for the four corners, and also try signed char (then checking your bounds both top and bottom)

EDIT

so, two more things need to change in the main (64\>\>i) to get the half effect at each octave, and also your output function (the one that maps the final\[\]\[\] tp the imgdta\[\], you just need to put in

> imgdta\[(i * n) + j\] = 128 + final\[i\]\[j\];

rather than the if else block.

another thing, I'm not sure why, but your bounds check is failing (that's lines 38 and 65) if you remove the check totally, you notice some new dark blobs too, so i reckon you might need to promote to a larger type before doing the bounds check if you want the more noisy picture you get with "64/i".

ANOTHER EDIT

just found out what it was, you're comparing against 'r', not 'rv', in the bounds check. Here's the fixed code: http://pastie.org/1927076
> 12 votes

# Answer
Two things that jump out:

1. Do you have a compelling reason to do this in fixed-point? There's nothing wrong with it per se, and there are plenty of reasons for using it (most notably memory requirements if you're planning on going up towards a HUGE map), but I would definitely start with a floating-point version of the algorithm and convert it to fixed-point after you've got it working; that should, if nothing else, eliminate one plausible source of errors (in particular, I suspect your clamping may be causing problems, and the conditions for when to add/substract rv).
2. While it's hard to tell from the code I see, it doesn't seem like your randomized height displacement is scaling with the level, and that combined with the issue in (1) may be causing some of the problems - you shouldn't be displacing by the same amount at each level.

Oh, and one non-algorithmic thing: I strongly recommend not doing allocations in your mdp() function; pass in two different already-allocated arrays and do the iteration 'in-place', going from one to the other. If nothing else, this'll let you ping-pong back and forth as you do the layers rather than having to allocate a new array each time out.
> 3 votes

# Answer
Further to the above, you're currently not deleting the memory that you're allocating. To remedy this, change line 104 from:

```
for (unsigned i = 1; i < 6; ++i) final = mdp(final, n, 64 / i);

```

to

```
for (unsigned i = 1; i < 6; ++i) {
  signed char** new_final = mdp(final, n, 64 / i);
  for (unsigned i = 0; i < n; ++i)
    delete[] final[i];
  delete[] final;
  final = new_final;
}

```

and add this after writing out to the tga file:

```
for (unsigned i = 0; i < n; ++i)
  delete[] final[i];
delete[] final;

```
> 0 votes

---
Tags: c++, procedural-generation, terrain
---


title: Developing a card game framework

text:
# Question
Title: Developing a card game framework
What sort of design patterns and ideas might one use to build a somewhat general purpose card game framework?

This stems from I made an attempt to build a clone of the popular Steve Jackson game "Munchkin". Because of the nature of that game I ended having to hard code so many card functionalities that the development became chaotic and over-bearing. I had wanted to build something general but ended up with just to many classes with to many overridden functions and switch statements to determine behavior.

I was curious what someone with more experience in design would handle such a task of building a general purpose card game framework, or at least something that could be extended. Or is it best that if I want to make a simulation of a card game like Munchkin, i'm stuck making a specific framework.

I would like to use C#.

**EDIT**

I would like to clarify somewhat of what i'd eventually like to achieve. I'd like a framework where I can basically implement phases with custom functionality (phase 1: draw cards, phase 2: apply upkeep rules, phase 3: play cards, phase 4: resolve, etc).

I think then defining a ruleset would be wise which would be coupled with both the cards and the phases.

Then, the cards would be defined and I suppose tied to the rules so for instance a rule might be "During upkeep phase, lose 1 token". However, a card that the player has might provide "Don't lose any tokens during the upkeep phase". So it would be nice to be able to tie this together but within the guts of the framework.

I suppose this might be way out of my league as well.

# Answer
> 6 votes
I would have used some kind of script language as LUA or Python to define each special behaviors or card.

This way you can define a "generic" engine, and keep the cards particularities away from the main code, into some small and easily editable scripts.

The main advantage of script languages over XML or some other "static" data is that script languages can "create" their own behaviors using the public methods offered by the engine.

*Example: suppose your engine offer the methods "setDommage(target,dmg)" and "setVisualEffect(nameOfFxLuaScript)" etc. You can have a cards doing something like this peuso-code*

```
------Card1 -- A simple fireball-----
// Fire ball
setDommage(target, 37);
setVisualEffect("fireBall.lua");

------Card2 -- A multitype ball (outch it hurts!)-----
// Fire ball
setDommage(target, 37);
setVisualEffect("fireBall.lua");

// Ice ball
if( player.protectionAgainstIce == false )
{
    setDommage(target, 102);
    setVisualEffect("iceBall.lua");
}

// thunderbolt
while( player.Alive )
{
    setDommage(target, 1005);
    setVisualEffect("thunderBolt.lua");
}

```

**The both cards use the same engine methods**, *but they don't do the same things. The behaviors can also use data gathered from the engine (like the player list to loop over them) and for, if etc. statements.*

The second but not the least advantage, is that it doesn't need to be compiled. You can modify you LUA script and reload it directly without recompiling your game. It's very nice for testing and iterating until you find the good settings.

The third advantage is that, anyone that can learn script language can create new cards/behaviors as long as you provide a list of the public methods shared by the engine (and as long as you don't encode the LUAs). And as anyone knows, the community is incredible when you give them nice tools ;)

---

Here is a LUA wrapper for C#: http://luaforge.net/projects/luainterface/

---
Tags: c#, architecture, card-game
---


title: XNA Aquatic Distortion Effect

text:
# Question
Title: XNA Aquatic Distortion Effect
I'm currently developing a 2D, top-down Windows Phone 7 game involving the surface of a pond. I'm trying to make the surface feel like actual water (as opposed to just a blue background with sprites drawn on top of it), and one of the effects I'm looking into is a sort of aquatic distortion effect. Basically, something similar to the first few seconds of this: http://youtu.be/1BpRsjF7QTM?t=3m17s

Any idea on how to do this in XNA? I'm sure I could figure out how to apply the answer to my particular application, but if it helps, my game involves a lot of ripples and I'd like to specifically distort the areas around and just behind the expanding sprite-based ripples.

Thanks!

# Answer
> 5 votes
Render your scene to a render target.

Render your render target to the screen on a procedurally-generated full-screen mesh with animated vertices or texture coordinates.

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


# Question
Title: How optimal do you think maintianing states in a sprite class?
Currently i'm working on a sprite system which will have frames which make animations.

Usually a sprite contains current position, current frame number to be displayed in the running animation, etc... This is what I mean is STATE.

Let's say there are 100 NPC characters in a game which will have different animations running at any time.If we are maintaining the state in Sprite class, we usually create 100 sprites and draw it as each sprite has its own state.

But I feel the same thing can be done like this, Imagine, position and animation state is separated from the Sprite class.When ever we want to draw we will just set it and draw the frame at certain position.With this approach there is no need to have 100 sprite instances.We can make the exact above situation with one single sprite instance.

For me I feel separating the "state" kills encapsulation.But at the same time it will have a benefit in terms of huge memory!

Please give your Pros/Cons on this kind of approach?

# Answer
I assume all your classes use a pointer to the sprite-sheet/texture, so that the actual sprite-bitmap-data takes up memory space just once.

Assuming this, it really isn't going to help you much (concerning memory usage) to have the `NPC` and the `Sprite` class separated. Although I think separating the two can still be a good idea if you look at it the following way:

`Sprite` or `SpriteSheet` class:

* is a helper class that will be initiated with a pointer to the sprite-sheet data and the desired frame-size
* allows definition of "animations" which are basically collections of frames (or UV coordinates)
* handles playback/looping of animations
* doesn't know anything about game states

`NPC` class

* depending on your design, this could either be a subclass of `Sprite` or hold a pointer to a `Sprite` instance (I would choose the latter).
* implements the NPC behavior
* will trigger/play animations depending on state (utilizing a `Sprite` instance)

I think this is quite the opposite of "killing" encapsulation. So in summary: I would recommend to separate your classes, but not because of memory-concerns...
> 3 votes

# Answer
You are correct. We do the same type of thing in our engine. There is a sprite object that can organize your images into pages (texture file) and groups. A group has frames of animation taken from the texture from a grid or if you want to pack more data into the optimal space, you can specify the sprite via a rect. There is an entity object which is made from a sprite group and they exist as instances in the game world having position and size. This allows for efficient management of objects for your game. Multiple entities can efficiently use the one sprite object.
> 0 votes

---
Tags: sprites, design-patterns
---


# Question
Title: How to manage all the NPC/AI objects on the server?
I'm writing a simple MMO, and currently have the the server-client architecture in place for multiple users to see each other and be able to move around together...now its time to add enemies.

Was wondering if anyone had links to articles that discussed how to best handle the hundreds of NPC objects that need to be managed in the world. I've done some searching and couldn't find much info about how this is typically done.

The two methods of structuring the implementation I can think of:

1. Holding all the instantiated NPC objects in a list, and having an NPC Thread loop through them sequentially and see if each has any logic that needs to be processed and perform necessary actions. I'm not sure if the performance of this design would be sufficient?
2. Event based system. Create a method in the NPC class that processes AI/Logic on it, have this method be called when an associated event is signaled, either on a timer for non interacted AI functionality (such as wandering), or signal the event externally from the packet handler (player moving nearby, or player attacking within range).

Is either of these approaches the correct way? What other methods of doing this exist?

# Answer
As always, architecture depends on your requirements. How many mobs are you going to have? How complex is their AI? What does it react to? How often does it change its state? Answer these questions, and you'll have a much better understanding of what you want and how to get that.

Generally, you'd want to have at least some kind of event system. AI is usually defined in terms of events: "When A happens, do B"; and if you don't have events in actual code, you'd have to somehow translate these definitions.

In my experience, you can get away with a simple loop implementation when you have few and really simple mobs (contrary to what the other answer seems to suggest). For example, in our current game we have hundreds of small instances with each having 10 mobs at most. And these mobs are dead-stupid; AI of 99% of them can be described in one sentence: "Am I attacking anyone? If not, attack closest player." In this case a simple loop is more than enough - twice a second we check for a new target (and a few other things for the rare "smart" mobs), and that does it.

However, when you have more and/or smarter mobs, naive approach stops working. For AI to react to some stimulus, you'd have to write code that detects it inside your AI loop. For example: suppose your mob should do something "when hit by a player". With a loop approach, there's no easy way to determine the mob was hit. When the AI is running, you can check that mob's health diminished since last tick, or that the mob is currently targeted by someone. But you cannot detect actual hits without resorting to hacks, like saving each hit info somewhere for AI to access it later.

Secondly, a naive loop always runs, no matter what happens. When you have lots of mobs, you want the AI to run as fast as possible.. and the fastest code is the code that never runs at all. If you have mobs that are not active, you want them to not run AI, or only run it sporadically (as in, wandering mob AI should only run when it decides where to go next).

With event-based approach, you can have you other subsystems send AI events whenever convenient, eliminating problem of "detecting hits". Of course, some events would still require detecting code: most notorious example is the "approach" event. And when you don't run your AI routine in a loop when nothing happens, you gain performance.

You can also use a hybrid approach. Instead of handling AI events immediately, you can stuff them into some kind of queue. Then, when AI routine runs (in a loop), it removes events from this queue and handles them one by one. With this architecture, AI performance might be a bit slower, but it is more predictable; also, you can guarantee that all AI runs on a single thread (which might be tricky otherwise). This kind of loop can also be easily throttled by skipping some events (for example, each AI iteration only handles three most recent events, discarding the rest). Or events might be prioritized, and less-important ones discarded if AI is found to be lagging.

Overall, the "loop with events queue" approach is probably the most flexible. But I want to reiterate: don't just choose it blindly as "the best". Think about your requirements first, and some simpler approach may turn out to be better.
> 5 votes

# Answer
It will depend on the number of enemies you have and how active they will be.

If you have lots of enemies, but they don't do much most of the time, an event system might be better. If you have enemies that are usually doing something the loop may work best since it factors out the complexity of the event system and because if events were in place they would be constantly firing anyway.
> 2 votes

---
Tags: architecture, ai, mmo, server, entity-system
---


title: MySql Database design for Facebook game

text:
# Question
Title: MySql Database design for Facebook game
I'm at the planning stages for a facebook game, it will be similar to farmville, but will feature parks. I've been a Flash game dev for many years but all this database stuff is new to me so I'm having trouble getting my head around what's the best way to handle the data.

I know I need a table for the players, so that's straightforward.

Each player can grow crops/flowers and/or harvest trees etc that are already in the parks. The way I'm setting it up is that the parks are made up of 2 layers, or 2 2D arrays, the bottom array or ground tile array is just big tiles, and in a 8x8 grid, so that seems pretty straightforward as well, just store 16 entries for each part in a "parks ground tile table", but first question about that. Those 16 entries would correspond to each park, so would I still use the auto increment on the ID, or some other kind of ID to represent them as a group somehow? I'm just thinking of what's the fastest way to grab those 16 from the database.

Next onto the trickier stuff which is the 2nd layer of the park or the items/objects/crops 2d array. Each player has to have their own version of this 2D array, so first qusetion is how do I set that up in the database? I was thinking maybe having a "park items array" and then each feature (tree, crop) etc for each player would just be stored in that array, but I can see that getting huge really quick, so not sure how to do that? or if the size of that would be an issue?

Then on top of that, each player can maintain multiple parks :p...again what would be the best database design to maintain all of those?

Thanks for any help!

# Answer
> 2 votes
I'd really suggest teaming up with someone who's got database experience and have them work this out with you. If you're out to create a Facebook game, it's not just about data storage formats like you are talking about, but also how your database is designed for security, stability and performance.

The best thing you could have happen as a game developer is have a big success on your hands with lots of players. The worst thing you can have happen as a game developer is a big success with lots of players, and a back-end system that's not designed to handle it.

Put it another way. You don't need a MySQL database for your game, you need a system your game can communicate with *in a secure way* to get and set data values related to a game session. This may or may not be via MySQL. Your game *definitely* shouldn't be written to directly talk to the database, but rather go via a web services (or other) proxy that can authenticate all requests and handle them in an appropriate manner.

# Answer
> 1 votes
I would probably design it like this (you can add more fields where required..):

`Player`

* *PlayerID*
* Nickname

`Park`

* *ParkID*
* *PlayerID* (Foreign Key)
* Name

`ParkObject`

* *ObjectID*
* Flash Class identifier

`GroundLayer` is a many-many relation table between `Park` and `ParkObject`

* *ParkID* (Foreign Key)
* *ObjectID* (Foreign Key)
* Index (position in the array)

`UpperLayer` again, a many-many relation between `Park` and `ParkObject`

* *ParkID* (Foreign Key)
* *ObjectID* (Foreign Key)
* Index (position in the array)

**Edit:** Edited in the index/position for `GroundLayer` and `UpperLayer` (this is to determine the location of the tile in the 2D array)

# Answer
> 0 votes
I would make a table called "park\_ground\_state" in that table, you would have:

* park\_ground\_state\_ID int auto-increment
* state\_data char\[16\] not nullable
* player\_ID int foreign key to the player table

Since you probably don't need to query the park cells separately, you can just grab them all at the same time from a char array.

It seems odd to some people to store separate entities in the same field, but in reality, the park state is a datastructure. In this case an array. You just want to grab the whole array at once and you never query on elements of the array from the database.

---
Tags: architecture, facebook, data-structure, casual-games, databases
---


# Question
Title: ERROR: The application bundle does not contain a valid identifier
I'm getting this error "The application bundle does not contain a valid identifier" after my application successfully compiles.This error prevents my game from launching on the phone or the simulator. I have no idea how to fix this as I was following this tutorial How To Make A Space Shooter iPhone Game using Cocos2d.

# Answer
This could be because the bundle identifier has invalid characters in it or no characters in it. The bundle identifier is found in the Info.plist file.

This is what constitues a valid application bundle identifier:

> The bundle identifier string identifies your application to the system. This string must be a uniform type identifier (UTI) that contains only alphanumeric (A-Z,a-z,0-9), hyphen (-), and period (.) characters. The string should also be in reverse-DNS format. For example, if your company’s domain is Ajax.com and you create an application named Hello, you could assign the string com.Ajax.Hello as your application’s bundle identifier. The bundle identifier is used in validating the application signature. source (apple developer)

This may also be of use:

> An identifier used by iOS and Mac OS X to recognize any future updates to your app. Your Bundle ID must be registered with Apple and unique to your app. Bundle IDs are app-type specific (either iOS or Mac OS X). The same Bundle ID cannot be used for both iOS and Mac OS X apps. source
> 1 votes

---
Tags: cocos2d-iphone, ios
---


title: GML and C/C++ language question

text:
# Question
Title: GML and C/C++ language question
Is GML (Game Maker Language) script is clipped in C/C++ language, and GML wrote the code to Visual Studio C++, it will always be correct, because it is just under C++ language features?

I think that a bit wrong to have written that question could be to ask yet another generation of weeks. But if correct, is not need to ask again.

# Answer
> 5 votes
GML is a distinct language developed for Game Maker. It bears some similarity to C and C++ on the surface, in terms of its syntax (keywords, grammar and structure), but it is otherwise unrelated to C++ -- it certainly is not a sub- or super-set of the C or C++ languages. GML differs from C(++) in a lot of ways... for example it does not require variable declaration, has a much simpler memory allocation model, and several additional extra language constructs (such as the "with" block).

You could write your GML code within Visual Studio, but it wouldn't work well. You might get syntax hilighting, but VS could not compile GML in general and using Game Maker itself to author GML is a far better idea since the tool and the language are tightly integrated.

---
Tags: c++, c, game-maker
---


# Question
Title: How do I determine which card is underneath the currently-dragged card in a card game?
I'm developing a card game. My custom control works great, but I need help to solve this:

When I move a card (my custom control) over another card I need to know which card is underneath. Once I know that, I'll be able to put in logic for game rules.

**EDIT**

I'd like to have some event in cardcontrol like: OnOtherCardControlOver() but I have some difficulty to figure it out.

# Answer
Since you said your game is free form (i.e. no predefined stacks) your problem basically turns into a collision detection one.

Basically your cards are going to have a position on the board and a size. From there you need to iterate over all the other cards on the board and determine what cards you're overlapping.

If you define your cards to be rectangles and don't allow rotation, the problem gets pretty easy.

Basically you would calculate the 4 corners of your card by offsetting from the card's position half the size of the card, and plugging those numbers in to this formula: https://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other/2696876#2696876. You can either decide to go for a naive solution (i.e. "do they overlap at all", or go for the area calculation to figure out which card is the "most" covered and use that one.

The problem gets a little more difficult if you can have cards stacking on top of each other. You'd basically have to do the same test but in order from top to bottom, where every time you put a card down you assume it's on a higher layer.
> 2 votes

# Answer
if i understood is what is game goning to look like, i suggest you keep some kind of stack in for each pile of cards you have in the screen, then use your custom control to move cards from one stack to another, using stacks would also have prevent you from unwanted changes where you pick a card from the ones underneath others,

with the new information you gave i think you could still use some kind of stack but now every control has a stack of other controls underneath it. you can also make an array of all your card controllers and when trying to check if some card is underneath another see if their bounding boxes collide. and if so which one was there first (you can use time for the second check)
> 3 votes

---
Tags: c#, card-game
---


title: c++ visualization

text:
# Question
Title: c++ visualization
Is there a C++ programming language knowledge to check the little tool where the introduction of C++ code would be nice to get something on the screen, similar to the "Processing" http://www.processing.org only with C++ language? I know the "Cinder" http://libcinder.org, but perhaps there should be a lot of code to write something to the screen? I just want to continue to learn C++ and tested by the knowledge I have, but I still can not write a complete program. Game Maker would be very appropriate, but the GML is a different language than C++

# Answer
> 1 votes
I can't really tell if you're asking for a simple windowing/graphics API or an API to assist in the procedural generation of images / "creative coding." C++ doesn't have either as part of its standard library.

If its the first thing, GLUT and its ilk allow you to get a window up and running for using OpenGL relatively quickly and is useful for quick-and-dirty prototyping. SFML is the modern de-facto successor to the popular SDL library... and there's this one I just stumbled across while doing some quick research for this question.

For the second case, I'm not aware of many. In addition to Cinder, there's openFrameworks and (maybe) this haXe thing.

# Answer
> 0 votes
i guess you can also use winBGIm it's very simple (only if you are trying to work with MinGW) and you can also find it's port here http://www.cs.colorado.edu/~main/bgi/visual/ and if you want to work with specificaly with cisual studio 2010 i think the best way is to use windows GDI it's also as you can see an easy to learn visual tool (this program directly draw on the screen you can also add some code to create a window first!):

```
/* *********************************************
* A simple gdi program
* ***********************************************/

#include <Windows.h>

void GdiOut(HDC hdc);

int WINAPI WinMain(
  HINSTANCE hInstance,
  HINSTANCE hPrevInstance,
  LPSTR lpCmdLine,
  int nCmdShow
  )
{
 HDC hdc = GetDC(NULL);
 GdiOut(hdc);
 ReleaseDC(NULL, hdc);

 return 0;
}

/* Show how to use the basic GDI functions */
void GdiOut(HDC hdc)
{
 HPEN hPen, hPenOld;
 HBRUSH hBrush, hBrushOld;

 //Initial colors
 BYTE bRed = 0;
 BYTE bGreen = 0;
 BYTE bBlue = 0;

 //Pen color
 COLORREF cPen = RGB(bRed, bGreen, bBlue);
 //Set the brush color based on the pen color. It is purple partial to blue.
 COLORREF cBrush = RGB(233,GetGValue(cPen), 255);
 //Create the pen.
 hPen = CreatePen(PS_SOLID, 10, cPen);
 //Create the brush.
 hBrush = CreateSolidBrush(cBrush);
 //Select the pen and brush. Just like set the drawing arguments.
 hPenOld = (HPEN)SelectObject(hdc, hPen);
 hBrushOld = (HBRUSH)SelectObject(hdc, hBrush);

 //Draw a triangle
 MoveToEx(hdc, 30, 10, NULL);
 LineTo(hdc, 10, 50);
 LineTo(hdc, 50, 50);
 LineTo(hdc, 30, 10);
 //Use the old pen
 SelectObject(hdc,hPenOld);
 //Draw and fill an ellipse
 Ellipse(hdc, 10, 60, 110, 160);

 //Release the resources
 DeleteObject(hPen);
 SelectObject(hdc, hBrushOld);
 DeleteObject(hBrush);

}

```

---
Tags: c++, visualization
---


title: Determine animation frame from interval

text:
# Question
Title: Determine animation frame from interval
I have an array of sprites that are displayed in-order to make an animation. There is code in an update loop that has access to a value 'time' indicating how far along the animation is. Time is a float between 0 and 1 inclusive. It uses this value to calculate which frame to display.

```
update(time) {
  frames // An array of animation frames
  current_frame_index = time / animation_length
  display_frame(frame[current_frame_index])
}

```

This works if you assume that each frame is displayed for the same amount of time.

I would like to enhance this by allowing frames to have arbitrarily defined durations. So if I have a set of frames and durations:

```
name           duration

frame_one      0.2
frame_two      1.1
frame_three    1.0
frame_four     0.75
frame_five     1.4

```

and a value indicating the animation's progress, how can I determine which frame to display?

Thanks!

# Answer
though james answer is right you can also get to where you want using my implementation

```
void update(float dt)
{
    nextframe -= dt;
    while (nextframe < 0)
    {
        nextframe += frametime[frame_index];
        display_frame(frame[frame_index]);
    }
}

```
> 3 votes

# Answer
While probably not that optimized, this would move to the next frame when the time value was beyond the sum of the durations of each frame.

```
update(time)
{
    frames // an array of animation frames
    fFrameLength = 0;
    foreach(frame in frames)
    {
        fFrameLength += frame.duration
        if ( time * animation_length < fFrameLength )
            display_frame(frame)
    }
}

```
> 2 votes

# Answer
Usually what I do in these kinds of situations is basically do what you do in the first loop, but insert an abstraction between "frame number" and "texture asset" (or UVs, if you will).

Basically, change `frames[current_frame_index]` to do a lookup in a table that you define for a given animation. You can set up a data structure that still works in "frames", but maybe with a higher frame rate to give you more precision.

A simple example would be something like this:

```
animation_frame | texture_index
0               | 0
1-8             | 1
9-12            | 2
etc

```

You can convert that to a list so you can do a lookup by animation frame index into texture index.
> 1 votes

---
Tags: 2d, animation, cocos2d-iphone, timer
---


# Question
Title: How do games make fire and smoke effects?
I was wondering around, searching internet about particle system and fire effects but I haven't found any good answers. On some games I have realized that some sort of movie is being shown as the fire, which is pretty good but not for the fires which are close to the viewer. Please let me know how to make realistic fire and smoke effect in a game. Also if you have a good sample code or good description of how to make these kinds of cool fires please note them too.

# Answer
> 6 votes
How to create prerendered effect is another question. You can create fires, smoke etc in Autodesk Maya. It has very strong fluid solver (fluids means fire, smoke, nebulas or even fog ...). This can be also putted into sequence of files and played.

**For real smoke/fire etc. simulation**, you can implement physically correct (or very near to it) fluid solver is based on 3D grid and Navier-Stokes equations - which refers to volumetric rendering. Lots of techniques exists, but to make long story short - it is possible on the gpu - and it is very fast.

Simulation is little harder, but basicly it is computing new values for each voxel based on some settings - Great for gpgpu computing. Volume rendering is that possible with taking lights in scene into account. Using opacity maps, such Fourier opacity maps, which are one of the newest (paper from 2010). Result can be see here (this is volumetric rendering in our engine, with shadows using Fourier opacity maps, number in the left upper corner says number of FFT coefficients):

# Answer
> 5 votes
Such effects are done with particle systems. Basically it's a big collection of 2D images that move as a group.

In both cases the individual images have alpha transparency so that they look like blobs instead of squares. For fire the sprites usually have add blend while smoke particles generally don't.

---
Tags: opengl, c, effects, particles
---


# Question
Title: Literature about Open World Games, Freedom to Choose
I'm doing a diploma thesis about the development of games with freedom to choose or open world.

Topics will be i.e. development issues in programming and the design itself, mechanics etc.

For that I need literature and lot's of it. Do you have any suggestions?

# Answer
> 6 votes
Designing Ethical Dilemmas - Slides and Audio http://designrampage.blogspot.com/2009/06/designing-ethical-dilemmas-slides-and.html

Interesting Mechanics by Brian Green http://psychochild.org/?cat=248

Design lessons by Brian Green http://psychochild.org/?cat=12

Games and storytelling, includes controlled branches - Ruben R. Puentedura, Ph.D http://hippasus.com/resources/gameandlearn/slides/7\_GamesAndStorytelling.pdf

Permanent Death - The Complete Saga (play-through with one life in an open world, no restart) http://drgamelove.blogspot.com/2009/12/permanent-death-complete-saga.html

---
Tags: game-design, software-engineering, game-mechanics, books, open-world
---


# Question
Title: detecting the coordinates where a bullet hits a mesh
I have a lot of complex objects in a scene and I'm looking for an efficient way to find which object a fired bullet hits, and to find the hit coordinates.

It would be best if there was a lightweight library to do this.

It seems that PhysX can do this, but I didn't find a way except to give every face in every mesh a PhysX system, and that seems to become a bottleneck.

# Answer
PhysX can pre-process your collision meshes into it's own optimised collision structures (probably a series of convex meshes). The process is called cooking, and it is described in a blog here: http://actuated.wordpress.com/2010/06/26/mesh-collision-in-physx/
> 4 votes

# Answer
So I guess that your initial attempt is to iterate through all meshes in your scene, for each mesh, check all triangles if they intersect, right? The brute-force way.

I'm not sure if there's a lightweight library for you to solve your problem, but the problem is quite a large discussing area.

I would suggest using a bounding-volume structure, such as a KD-Tree used in 3 dimensions. Christer Ericsson suggests an implementation in his book "Realtime Collision Detection" which is cache-friendly and memory efficient. I've implemented his suggestion in a project and indeed it did turn out very well. The task of creating a KD-tree together with splitting your meshes into well-balanced tree's is covered in depth by Ingo Wald (http://www.sci.utah.edu/~wald/Publications/index.html). I suggest you read up on there. The Surface Area Heurestic (SAH) is considered (one of?) the best algorithms for KD-splitting, Ingo Wald covers it in one of his publications (http://www.sci.utah.edu/~wald/PhD/index.html).

There are a variety of freeware KD-tree's out there, I haven't really looked into kdtree at google-code (http://code.google.com/p/kdtree/) but it looks pretty decent. There's some interesting tutorials (http://www.autonlab.org/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf?branch=main&language=en) that you can read.

Good luck!
> 4 votes

# Answer
I just once stuck with some collision testing like this and the answer was to pack object near each other into groups, then check a simple sphere collision test for every group and if the bullet hits a specific group then check if it realy hits acual object(now using faces) it may still take some time but is far more optimized than a standard face collision checking. and you can make some groups of groups and so on to speedup your collision testing even more.
> 3 votes

# Answer
I really can recommend the OpenDynamics, an open source physics library, with loads of examples and its pretty straightforward. It also works easily with plain old C.

As far as I can remember, OpenDynamics supports some kind of mesh loading. Otherwise, you have to create the faces for the physics themselves.

There are other nice free physics engines I have looked through (did not try them yet):

There are also some pyhsics engine for 2D only: Box2D and chipmunk I tried and are great also.
> 2 votes

---
Tags: 3d, collision-detection, coordinates
---


# Question
Title: Tile based collision detection failing when player is going too fast
I'm creating a side scroller and I'm have a problem with my collision detection.

The collision detection works perfect when the player is falling at a constant speed, but when I implement more realistic gravity the player falls too fast - resulting in that the collision will be checked with the tiles under the floor/platform causing the player to be able to jump through platforms.

The way my update and collision works is like following:

* Update entities velocity (no position change)
* Check for collisions (first x, then y)
    + if collision, then move the entity as close as possible, otherwise set the position with the velocity.

The collision method works like this:

* Get the four corners of the player.
* Get from that four corners the tiles.
* Collision check.

How can I solve this problem?

## UPDATE

Added the code to make it more clear.

The main loop:

```
_frames_a_sec = 60;
public void run() {
        while(true) {
            long timeElapsed = System.currentTimeMillis() - _lastUpdate;
            _lastUpdate = System.currentTimeMillis();

            if(timeElapsed > 80) {
                timeElapsed = 80;
            }

            update((int)timeElapsed);

            try {
                Thread.sleep((1000/_FRAMES_A_SEC));
            } catch(Exception ex) { }
        }
    }

```

Map update method:

```
public void update(int timeElapsed) {
        //update entities
        for(Entity entity : _mapEntities) {
            entity.update(timeElapsed);
        }

        //check for collisions
        checkMapCollision();
    }

```

Entity (abstract) update method:

```
public void update(int timeElapsed) {
        _velocity.x = 0.0F;

        if(!_isOnLand) {
        //add gravity
        _velocity.y += Map._GRAVITY_PER_SEC * timeElapsed;
    } else {
        _velocity.y = 0.0F;
    }
}

```

Mario (extends Entity) update method:

```
@Override
    public void update(int timeElapsed) {
        super.update(timeElapsed);

        if(_state == STATES.IDLE) {

        } else if(_isMoving) {
            _marioSmallWalk.update(timeElapsed);
        }

        if(_state == STATES.JUMPING) {
            setVelocityY(getVelocity().y + _jumpSpeed);

            _jumpSpeed += _JUMP_DECREASE * timeElapsed;

            //falling?
            if(getVelocity().y > 0) {
                setState(STATES.FALLING);
            }
        }

        if(_isMoving) {
            double walkSpd = (_WALK_SPEED_SEC * timeElapsed);

            if(getFacing() == FACING.LEFT) {
                walkSpd = -walkSpd;
            }

            setVelocityX(getVelocity().x + walkSpd);
        }

        //falling?
        if(getVelocity().y > (Map._GRAVITY_PER_SEC * timeElapsed) + 1.0F) {
            setState(STATES.FALLING);
        }
    }

```

Map Collsion check method:

```
public void checkMapCollision() {
    for(Entity entity : _mapEntities) {
        placeEntityAtX(entity);
        placeEntityAtY(entity);
    }
}

```

X check method:

```
private void placeEntityAtX(Entity entity) {
        Vector2d dir = entity.getDirection();
        Rectangle bounds = entity.getBounds();
        boolean positionSet = false;

        bounds = new Rectangle((int)(bounds.x + dir.x), bounds.y, bounds.width, bounds.height);
        Block[] corners = getCornerBlocks(bounds);

        if(dir.x > 0) {
            if(corners[1].isSolid() || corners[3].isSolid()) {
                Rectangle blkBounds;

                if(corners[3].isSolid()) {
                    blkBounds = corners[3].getBounds();
                } else {
                    blkBounds = corners[1].getBounds();
                }

                entity.setPositionX(blkBounds.x - (bounds.width-entity.getCurrentSprite().getOffsetX())-1);
                positionSet = true;
            }
        } else if(dir.x < 0) {
            if(corners[0].isSolid() || corners[2].isSolid()) {
                Rectangle blkBounds;

                if(corners[2].isSolid()) {
                    blkBounds = corners[2].getBounds();
                } else {
                    blkBounds = corners[0].getBounds();
                }

                entity.setPositionX(blkBounds.x + blkBounds.width + (bounds.width/2) + 1);
                positionSet = true;
            }
        }

        if(!positionSet) {
            //set the original position
            entity.setPositionX((int)(entity.getX() + dir.x));
        }
    }

```

and the y:

```
private void placeEntityAtY(Entity entity) {
        Vector2d dir = entity.getDirection();
        Rectangle bounds = entity.getBounds();
        boolean positionSet = false;

        bounds = new Rectangle(bounds.x, (int)(bounds.y + dir.y), bounds.width, bounds.height);
        Block[] corners = getCornerBlocks(bounds);

        //moving down
        if(dir.y > 0) {
            if(corners[2].isSolid() || corners[3].isSolid()) {
                Rectangle blkBounds = null;

                if(corners[2].isSolid()) {
                    blkBounds = corners[2].getBounds();
                } else {
                    blkBounds = corners[3].getBounds();
                }

                entity.setPositionY(blkBounds.y);
                entity.landed();
                positionSet = true;
            }
        } else if (dir.y < 0) {
            if(corners[0].isSolid() || corners[1].isSolid()) {
                Rectangle blkBounds = null;

                if(corners[0].isSolid()) {
                    blkBounds = corners[0].getBounds();
                } else {
                    blkBounds = corners[1].getBounds();
                }

                entity.setPositionY(blkBounds.y + blkBounds.height + bounds.height);
                entity.roof();
                positionSet = true;
            }
        } else {
            if(!corners[2].isSolid() && !corners[3].isSolid()) {
                entity.falling();
            }
        }

        if(!positionSet) {
            //set the original position
            entity.setPositionY((int)(entity.getY() + dir.y));
        }
    }

```

# Answer
> 7 votes
I know of two ways that will solve this problem.

**First method: Fixed Time Step Physics**

You can use fixed timestep physics with a high enough frequency that you will detect all the collisions.

What this means is that you will decide on a physics update delta, e.g. 1/60th of a second. Then for each frame of your game you'll calculate how much time has passed since the last frame, divide this by the physics update delta. This is how many physics updates you have to do that frame. In other words, instead of doing a single physics update and then collision check, you will be doing many smaller updates.

* **Pros:** This is probably the easiest solution to implement
* **Cons:** May not be practical, depending on how small your collision items are, and how fast they move.

See this question which compares fixed and variable timestep (and there's some useful links in the question itself).

**Second method: Swept Collision Detection**

You can to calculate the vector between the current position of the player and the projected position of the player, and do your collisions between this line and the platforms.

* **Pros:** Would work even with very very fast moving and small bodies.
* **Cons:** Movement in reality due to gravity won't be a straight line, sweeping/integrating the path of multiple accelerating bodies is potentially a difficult maths problem.

# Answer
> -1 votes
Up the physics update rate until it works, it doesn't have to coincide with the framerate. I'd always do my timing like:

```
physicsStep=25
physicsdivider=3
nextUpdate=currentTime()*physicsdivider
while(1){
    while(nextUpdate<currentTime()*physicsdivider){
        doPhysics()
        nextUpdate+=physicsStep
    }
    doRender()
}

```

Edit: Updated the code to do 120 rather than 100 Hz as that will be a little smoother on screens running 60 Hz.

What happens is that the inner loop repeats until the physics have caught up with the current time, only then is frame rendered. With v-Sync enabled on a 60 Hz monitor the result should be this:

```
render   00 ms
physics
physics
render   17 ms
physics
physics
render   33 ms
...

```

With exactly 120 physics updates per second, and 60 render updates per second

If the video card is too slow to do 60 Hz some of the render updates will be dropped, but the physics will still be exactly the same with 120 updates per second.

This only works well as long as the physics can stay comfortably within the allotted time of 8 1/3 ms per updated. You should try timing a physics update to get an idea of how close to being a problem this is.

By the way, I can't find the render and flip commands in your code. In any case, simply calling a sleep 16 ms once for every update is a very poor method of timing, that way you are invariably going to drop frames.

---
Tags: collision-detection, tiles
---


title: Skin Editing/Overlaying bullet holes

text:
# Question
Title: Skin Editing/Overlaying bullet holes
You see, especially in FPS games, when a bullet hits a wall or a character, etc. You end up with the bullet hole.

Is this usually done with the actual skin temporarily changing, or just an overlay of another image (or something totally different)?

Could anyone give me pointers on how to go about this? I'm using XNA (C#)

# Answer
> 5 votes
A naive solution would be to use a small quad positioned and rotated to match the surface where the bullet hit with a transparent texture of a bullet hole.

There are some more advanced techniques involved if you want the hole to clip properly if you shoot near an edge of a wall, or if you shoot something rounded.

These are called "decals" if you want to look into more details. Here's a blog post that goes into some of those techniques. http://blog.wolfire.com/2009/06/how-to-project-decals/

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


# Question
Title: Languages for creating 3d / 2.5d enviroments
I want to pick up a language that will allow me to create 2d/3d game environments. I come from web development using PHP, JS, XML and ideally I want to be able to integrate with those languages. I want to deploy to the web and to PC / Mac.

I'm considering Java, Actionscript 3, or some variant of C.

I'm pretty good at picking new languages up so that isn't a consideration.

I have briefly tried Java and ActionScript 3 and the problem is that I'm having difficulty seeing what the strengths of each language are (that is without learning the entire language anyway).

So if a few people could champion their tool of choice, what strengths/weaknesses it offers for game development (feel free to include commercial advantages!), that would certainly help me, it may help others too.

# Answer
> 3 votes
I would firmly vote for Unity3D. The environment is great, it is fast, it can deploy to all of those platforms (plus iOS I believe).

You can also reuse your JavaScript skills to script it (as well as C#, if you want).

In terms of 2.5D, you'll just want to fix the camera along an axis.

# Answer
> 0 votes
If you intend to deploy to the Web and to make it multiplatform there is no better choice than X3D (formerly VRML), see Web3D. It is ISO for Web3D graphics, all mayor 3D tools have export for that format and being an international standard longevity is guaranteed and, what is most important, it is royalty free. Even WebGL will be supported. Internal scripting is subset of JavaScript and there is EAI for virtually any programming language but most of code online is Java and C++. Leading X3D engine, Bitmanagement Contact3D is on line with latest game engines (multitexturing, shaders, nurbs etc.) can be used as standalone app or as a plugin for all mayor web browsers.

---
Tags: 3d, 2.5d
---


# Question
Title: Component based game design and sharing mesh data
Lets say you make a game engine, and you have several GameObjects and every GameObject have a list of components that you can add or remove.

Lets say there is a MeshComponent who has vertices, normals etc. If several GameObjects have the same MeshComponent, there will be a lot of memory waste. Of course there are many ways to implements this but I want some good advice how to solve this? How do components share data that is not going to be modified?

# Answer
> 3 votes
I would assume you want a different structure for a MeshComponent than, say, a HealthComponent.

Consider some kind of AssetManager or ResourceManager that holds the resources - be it a mesh, a map, or a texture (probably different managers) - and your MeshComponent holds a reference or a pointer. All the meshes will share the same actual mesh.

You may have some system like this: (since there is no language given, this is C# - C++ or other non managed languages would need pointers somewhere)

```
ResourceCache<Mesh> meshManager = new ResourceCache<Mesh>();
meshManager.Load("sphere");
Entity e = Entity.Create(); //Factory
e.AddComponent("Mesh", new MeshComponent(meshManager.GetReferenceTo("sphere"));

```

The only problem arises if you want any kind of mesh deformation. You'll probably either want to store a list of changed vertex data OR a whole new set of mesh data. Probably the former.

# Answer
> 3 votes
You need to make the distinction between "component" and "asset".

Basically, you would have some kind of renderer component attached to your game object that references a mesh (by a handle or by pointer or whatever) and uses that. It's just like how you reference textures by ID instead of having everything that needs a texture have all the pixel data.

---
Tags: component-based
---


title: Want to develop android game

text:
# Question
Title: Want to develop android game
I want to develop a 3D multiplayer game for android , what is the best game engine , what is the best software to create 3d objects to import them to android ?

Thank you .

# Answer
This question explains how to load models into android.

A quick google search for Android 3D Engines gave me:

jPCT-AE

Unity3D now does Android - this is a great option, but I believe you have to pay. It probably is the 'best' engine by any means..except cost.
> 1 votes

---
Tags: android
---