# Question
Title: How do I Fallback to Older DirectX Versions?
I had a feeling that it would be easier to tackle this problem before I got too deep into development (unless, of course if that's a bad idea/the hard way, please inform me...). I'm creating my game to be run ideally on DirectX 11, however, I want to offer it on DirectX 10, and I'm unsure if it is worth offering it for DirectX 9 for XP users. I'm not too sure how this fallback even works, as I can't find many articles on the internet. If someone could give me an in-depth article, that would be great.

I've read a little about how since DirectX11 is completely absent on XP, it is hard to even check for support. Someone mentioned having multiple applications for each version, is this a good idea?

Thanks to anyone who can point me in the right direction here.

# Answer
> 5 votes
You can target any hardware you like with the D3D11\_FEATURE\_LEVEL enum. This allows you to use the Direct3D11 API to target D3D10 and D3D9 hardware, with some limitations, which could be significantly easier than coding a separate D3D10 and D3D9 renderer. However, you must code an explicit Direct3D9 renderer to target Windows XP.

# Answer
> 1 votes
Well if I'm not mistaken, you must directly target each version mainly due to the differences between each version, especially between dx9 and dx10/11. Also, at this point I'd say it's safe to move to DX 11. By the way, DX 9 is Windows XP, DX 10 is Vista, and DX 11 is Vista SP1, Win 7, and Win 8.

# Answer
> 1 votes
Unless this is a commercial project ignore XP/D3D9 and just write for D3D11. And ignore any device below D3D\_FEATURE\_LEVEL\_10\_0 because there are very few D3D11 machines with only a D3D9 video card. Even if it is a commercial project you should only target D3D9/XP/older hardware if you need large numbers of buyers to make money - and that depends on the game. The Steam and Unity web player have a lot of information that can help you make that decision.

Even if you do decide that D3D11 is the only API you need to target right now, you may want to leave the door open to other APIs in future. That might lead you to think that abstracting the D3D11 API behind your own set of interfaces and objects would be a good idea. Well, maybe. Doing so has a cost and getting the abstraction right without knowing much about the other APIs is hard.

If you do go this way aim for a high level abstraction (e.g. it should deal with things like models and instances) and NOT just a thin layer over D3D11 (which would be things like buffers and draw calls). You want to leave the implementation free to call the target API efficiently instead of trying to emulate some other API.

---
Tags: directx
---


# Question
Title: Creating new games on Android and/or iPhone
I have a succesfull Facebook poker game that is running very nicely. I was asked if I can port my game to other platforms - mainly mobile devices (phones as well as tablets, would tablets need a separate version)?

I am currently a PHP programmer (and game designer) and I simply don't have the time to learn Android or other languages - so I have decided to pay third parties to port the game for me (if possible).

1. Which programming language is needed for the following four devices - Android phone, iPhone, iPad and tablets?
2. Can they all run off a central SQL database? If no then I don't think I'm interested.
3. Do any of these run Flash?
4. Have I covered all my main bases here?

For example is programming for an Android phone that much different from programming for an Andorid tablet? They will have slightly different graphics (because the tablet has a greater screen area might as well use it) but does either version need to be developed separately, from scratch?

Same goes for iPhone/iPad, do they really need to be programmed separately if the only difference is the graphics?

# Answer
> 2 votes
Often you can "port" a web-based application to a mobile device by just providing a mobile version of the webpage. iOS and Android both provide various mechanisms to "install" a webpage (or portable site) onto the device; iOS supports HTML5 offline storage, and Android allows you to bundle up your pages into an application bundle that is then served by a WebView. However, this will only work for static content; dynamic content (such as that generated by a PHP application) will still have to run from a webserver, and the user will need to have a data connection to use it.

As far as Flash support goes, you can install Flash on Android, but users will generally be unhappy about it.

If the game is particularly successful and you want to allow offline operation and have it run well on a variety of devices and you don't want to learn Java, your best bet is probably to hire someone else to port it for you.

# Answer
> 0 votes
I don't have first hand experience with it, but I'd like to mention a framework I've read about:

http://www.haxenme.org/

Quoting the about page:

> NME is a **free**, open-source framework that enables development for **iOS, Android, webOS, BlackBerry, Windows, Mac, Linux and Flash Player from a single codebase**. Unlike most cross-platform frameworks, NME applications are not written in a low-level language (like C or C++) and does not require a virtual machine or runtime (like Java and Adobe AIR) in order to run on a target platform.

The language that powers it is supposedly very similar to ActionScript 3 which I assume someone with Flash experience will already know.

---
Tags: android, ios, facebook, porting
---


# Question
Title: Mixing XNA and Silverlight gives wierd graphics
I making a small 3dgame which is made as a Silverlight and XNA app, but when I draw the sprites the graphics becomes all wierd.

All my primitive types are rendered correctly, but my 3d models are just wierd

My Draw is like this when silverlight is set to draw

```
private void OnDraw(object sender, GameTimerEventArgs e)
{
    // Render the Silverlight controls using the UIElementRenderer
    elementRenderer.Render();

    // Clear the screen to a solid color
    SharedGraphicsDeviceManager.Current.GraphicsDevice.Clear(Color.CornflowerBlue);

    switch (gameState)
    {
        case GameState.ChooseStarter:
            TextBlockStatus.Text = "Find Starting Player";
            break;
        case GameState.PlaceBrick:
            TextBlockPlayer.Text = (playerTurn == PlayerTurn.PlayerOne) ? "Player One" : "Player Two";
            TextBlockState.Text = "Place Brick";
            foreach (IGraphicObject obj in _3dObjects)
            {
                obj.Draw(cameraPosition, e);
            }
            break;
        case GameState.GiveBrick:
            TextBlockState.Text = "Give Brick";
            break;
    }

    spriteBatch.Begin();
    // Using the texture from the UIElementRenderer,
    // draw the Silverlight controls to the screen
    spriteBatch.Draw(elementRenderer.Texture, cameraProjection, Color.White);
    spriteBatch.End();
}

```

This gives me this output

If I comment the spritebatch lines out I get the correct output, except the silverlight text is of course not shown

I am not entirely sure what to look for except that zero vector I am giving to the spritebatch, but if thats the source I have no idea what I am supposed to set it as epspecially when its a 2d vector

# Answer
> 2 votes
Since the objects appear in the wrong order, this is most likely because the depth buffer is disabled at the time of drawing.

That's actually something that `SpriteBatch` does and you need to restore it manually. See this link for more information on the problem, as it also covers all the other device states that are also changed by `SpriteBatch`.

In this particular example, in order to reenable the depth buffer, just add the following line to the end of your `OnDraw` method:

```
GraphicsDevice.DepthStencilState = DepthStencilState.Default;

```

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


# Question
Title: Repairing back-facing triangles without user input
My 3D application works with user-imported 3D models. Frequently, those models have a few vertices facing into the wrong direction. (For example, there is a 3D roof and a few triangles of that roof are facing inside the building). I want to repair those automatically.

We can make several assumptions about these 3D models: they are completely closed without holes, and the camera is always on the outside.

My idea: Shoot 500 rays from every triangle outwards into all directions. From the back side of the triangle, all rays will hit another part of the model. From the front side, at least one ray will hit nothing.

Is there a better algorithm? Are there any papers about something like this?

# Answer
I think you can do this just by examining the index list.

For each occurrence of each edge in the index list (an edge should never appear more than twice, and exactly twice for a closed model):

If the indices that define the edge appear in the same order more than once, then you've found a winding order disagreement.

```
0---1
|  /|
| / |
|/  |
3---2

```

This quad could be defined by the index list (0,1,3,1,2,3), where the faces are (obviously) (0,1,3) and (1,2,3).

Note that the shared edge (1,3) appears in opposite order - (1,3) and (3,1) - which is required for the faces to have the same winding order. If you saw something like:

(0,1,3),(2,1,3), where the edge(1,3) appears in the same order in both faces, then they face opposite directions and one of them needs to be flipped.

Pick one of the faces that contains the edge and flip it by swapping the position of two of the indices within the list.

Repeat until you've traversed the entire list.

The only issue I can see here is if the edge you start with is backwards/part of a face that is wound in the wrong direction, in which case you'd wind up with a model that's backwards. However, you can try and detect that by counting the number of faces that you've flipped, and, if you reach a certain threshold - say, half of the total faces in the model - pick one of the faces that you've flipped - any one will do - and start over.

**Follow-up**

I didn't mention this before, but it might be wise to start with one face, then adjust the faces to which it is connected, and the ones to which *those* are connected, etc., however I have a weird feeling that that level of logic is unnecessary. As long as an edge is never flipped twice, everything should agree after a single pass. *Feel free to point out or relay experience or problems with this method*
> 9 votes

# Answer
If we assume that *most* face normals are correct, then you can query the surrounding face normals and dot them with the current face. If the dot product is negative, the normal is facing the wrong way.

You may have to add some heuristics in there where (this is just an e.g.) if 4 of the 5 surrounding face normals are facing one way (their dot product is positive) then your heuristic assumes that the surrounding face #5 is facing the wrong way.
> 7 votes

---
Tags: 3d, algorithm, models, geometry
---


# Question
Title: Intersection points of plane set forming convex hull
Mostly looking for a nudge in the right direction here. Given a set of planes (defined as a normal and distance from origin) that form a convex hull, I would like to find the intersection points that form the corners of that hull. More directly, I'm looking for a way to generate a point cloud appropriate to provide to Bullet.

Bonus points if someone knows of a way I could give bullet the plane list directly, since I somewhat suspect that's what it's building on the backend anyway.

# Answer
Okay, so I found something that works for me. First off, I'm using this equation to find the intersection point of three planes. (If the denominator is 0 there's no intersection.) I have to loop through all the planes multiple times, but in my case I'm doing it as a pre-process so it's not a big deal.

Just because three planes of the hull intersect, however, does not mean the intersection actually reside on the hull itself. In order to weed out the outliers I test the point to see if it lies "inside" the hull, within a reasonable margin of error. The algorithm for that is pretty simple:

```
function pointInHull(planes, point) {
    for (i = 0; i < planes.length; i++) {
        plane = planes[i];
        dist = point.dot(plane.normal) - plane.distance;
        if (dist > 0.01) return false; // indicates the point lies in outside the hull
    }

    return true;
}

```

Since no planes will ever intersect inside the hull (that's what makes it convex!) this gives me all the edge points.

So the basic code is something like this:

```
pointCloud = [];

for (i = 0; i < planes.length; i++) {
    p1 = planes[i];

    for (j = i+1; j < planes.length; j++) {
        p2 = planes[j];

        for (k = j+1; k < planes.length; k++) {
            p3 = planes[k];

            point = getPlaneIntersectionPoint(p1, p2, p3);

            if(point && pointInHull(planes, point)) {
                pointCloud.push(point);
            }
        }
    }
}

```

I certainly wouldn't recommend trying this in a realtime situation, but as an offline process it's fine.
> 2 votes

# Answer
A brute-force approach would be:

1. For each pair of planes, find their line of intersection (skip if the planes are parallel).
2. Clip this line by all the other planes, i.e. intersect it with them and keep track of the interval on the line that's inside them. If this interval become empty, skip it and go on to the next line.
3. Add the endpoints of the clipped line segment to the point cloud.

The trouble is that if you have n planes, this takes O(n^3) time, and will generate each point several times (once for each edge that touches it).

After a bit of googling I found that this process is referred to as "vertex enumeration" and there is a paper about a smarter and faster way to do it here. It says it will generate verts for n planes in O(n\*v) time, where v is the number of vertices generated. I haven't read the paper in detail, but it looks complicated and uses a bunch of linear programming theory.
> 0 votes

---
Tags: geometry, bullet-physics
---


# Question
Title: Need ideas on how to give my levels structure
I am making an iOS game for a project at school. It is going to be a tiny bit like Fruit Ninja, as in it will have different things on the screen, and when you hit them, they die, and you get points. The trouble is that unlike Fruit Ninja, my game will have different types of sprites, all doing different things (moving different places, doing different things, etc). The one thing that is bad about having all of these sprites that do different things is that it is hard for them to look neat on the screen all together. I was planning on having a couple of different gamemodes:

**Time Trial**
You have 120 seconds to kill as many sprites as possible.

**Survival**
You have three lives, every time you try to hit a sprite and miss, you lose a life.

**????**
Whatever I think of.

I am a rookie to game design in general, and I don't know the best way to make my game look good, and play well. I could have all of these sprites on the screen at the same time, or I could have them come in waves, for example 10 of sprite\_a come on, and once they are killed, 10 of sprite\_b come on, etc...

Please give me your opinion about which one I should code. If you have any other suggestions for either a third gamemode, or a completely different way to make the levels, feel free to tell me.

# Answer
> 1 votes
Tricky mode: you make a little file format to describe, on a timeline, what sprite(s) appear and where. Your main game code reads this file at the beginning and merely plays it back over time while your main loop runs.

And by file format I mean **really simple**, like repeated lines of "time spriteType location." Once you have this setup, follow Imi's advice and test iteratively until it feels good.

If you make it so you can stop your main loop, reload the data file and then play some more you can quickly turn around sprite changes without having to code or recompile anything.

Most games of this type work in patterns and combinations. For an extreme example of sprites and patterns google "Bullet Hell." For example, the yellow sprite always flies straight no matter what and the red sprite wobbles up and down. Keep the patterns for each kind of sprite the same so the player can Learn how to play and mix up the experience by adding new sprite types and combining them on screen simultaneously.

You'll notice in older sprite games like this where avoidance and hitting them is important any particular screen **never has a lot of different sprites** but instead changes them as you progress. You've noticed the opposite, shove them all on the screen and it's ugly and chaotic.

---
Tags: iphone, sprites, ios, cocos2d, level-design
---


# Question
Title: The ship "shudders" in scrolling Asteroids
In my Asteroids game the user can scroll through space. When scrolling, the ship is drawn in the centre of the window. I use interpolation. I scroll the window uing `glOrtho`, centering it around the centre of the ship. On my first machine (7 years old, Windows XP, NVIDIA), I am doing 50 updates and 76 frames per second. This is smooth. My other machine an old compaq laptop (Pentium III) with Linux and Radeon OpenGL driver delivers 50 updates and 30 frames per second. The ship regularly seems to "shudder" back and forth when at maximum thrust. When you position the mouse cursor beside the ship it is obvious that its relative position in the window changes. Also, the stars seem blurred into short "lines".

Playing the game in non-scrolling mode, the ship moves within the window, `glOrtho` is therefore not called repeatedly and there is no problem.

I suspect a bug in my positioning of the ship and the window but I have dumped out these values and they seem to only go forward, not forward-back-forward. The driver *does* support double buffering. I guess if it is my bug I need to slow the frame-rate down to debug properly. My question: is this an obvious driver bug or is the slower machine uncovering a bug in my stuff and if so, some debugging tips would be appreciated. I am drawing in world co-ordinates and letting `OpenGL` do the scaling and translation so if I had a quick way of verifying what pixel co-ordinates OpenGL produces for the ship centre, that would help clarify this.

# Answer
> 5 votes
I had this problem too in my game which just uses SDL. For me, the issue was the camera was updated before the player's new position was updated. Since, his movement is time-based(not constant) sometimes he 'jumps' ahead and appears to stutter. So I just had to change the order of updating.

* update Active Player
* update camera position
* update everything else (but do not re-update active player)

For me, everything is drawn off-setted based on camera's position, but the camera is based on the active player's position. It was a simple fix, but it took me a long time to find since I was blaming time-based movement. Anyways hope this helps.

Edit: I'd like to clarify that this only happens when the camera is tracking the player. Also, A fixed timestamp should fix this problem since there is no time difference between when the camera is drawn and when the player is drawn, but the player should still be updated first, otherwise the player will look like it is always one from ahead of the camera(if that makes sense).

# Answer
> 1 votes
"I have dumped out these values and they seem to only go forward"

I think you should dump ship's screen coordinates not logical "in game" ones.. If I understand correctly, ship's screen coords should stay the same, am I right?

# Answer
> 0 votes
It appears that calling `glOrtho` for panning is not recommended. Not sure why. Based on some advice from stack overflow, I have fixed this problem by instead maintaining the ship at origin 0,0 all the time and translating everything else in the world by the ships *real* displacement from the origin. The window set up by `glOrtho` remains constant, changing only if there is a zoom.

---
Tags: c++, opengl, 2d, coordinates
---


title: 3D Huge mesh rendering

text:
# Question
Title: 3D Huge mesh rendering
I am writing a program, that as input, I have a huge (10^6 elements) 3d mesh (with hexagonal shaped elements), and I want to realtime render it, but not as real-time as a game. It just can show the scene and rotate, zoom and pan. The most important point is, I don't need any special lighting nor any shadows. Also, the objects to render are static, and they do not move. My object hasn't any textures.

I've read about `ray tracing` methods, but I don't know if there is any good libraries for this purpose, or I have to implement everything by myself.

Thanks a lot.

# Answer
> 2 votes
How large is the mesh?

Modern graphics cards can render huge amounts of triangles very quickly. So one thing you could do is use an existing 3D engine and just plug your model into it. Another idea would be to take your model, convert it into a format that some renderer can use (e.g. a raytracer like POVray) and render it with that. But it all depends on the visuals you'd like to achieve. If reflections are important, raytracing surely is the way to go. If you just need a simple 3D visualization, go ahead with a 3D engine.

---
Tags: rendering, 3d-meshes, raytracing
---


# Question
Title: Android device - C++ OpenGL 2: eglCreateWindowSurface invalid
I am trying to debug and run OGLES on Native C++ in my Android device in order to implement a native 3D game for mobile smart phones. The point is that I got an error and see no reason for that. Here is the line from the code that the debugger complains:

```
    mSurface = eglCreateWindowSurface(mDisplay,
                                      lConfig, mApplication->window, NULL);

```

And this is the error message:

```
    Invalid arguments ' Candidates are:
        void * eglCreateWindowSurface(void *, void *,
                                      unsigned long int, const int *) '

```

--x--

Here is the declaration:

```
    android_app* mApplication;

    EGLDisplay mDisplay;
    EGLint lFormat, lNumConfigs, lErrorResult;
    EGLConfig lConfig;
    // Defines display requirements. 16bits mode here.
    const EGLint lAttributes[] = {
        EGL_RENDERABLE_TYPE, EGL_OPENGL_ES2_BIT,
        EGL_BLUE_SIZE, 5, EGL_GREEN_SIZE, 6, EGL_RED_SIZE, 5,
        EGL_SURFACE_TYPE, EGL_WINDOW_BIT, EGL_RENDER_BUFFER, EGL_BACK_BUFFER,
        EGL_NONE
    };
    // Retrieves a display connection and initializes it.
    packt_Log_debug("Connecting to the display.");
    mDisplay = eglGetDisplay(EGL_DEFAULT_DISPLAY);
    if (mDisplay == EGL_NO_DISPLAY) goto ERROR;
    if (!eglInitialize(mDisplay, NULL, NULL)) goto ERROR;
    // Selects the first OpenGL configuration found.
    packt_Log_debug("Selecting a display config.");
    if(!eglChooseConfig(mDisplay, lAttributes, &lConfig, 1,
        &lNumConfigs) || (lNumConfigs <= 0)) goto ERROR;
    // Reconfigures the Android window with the EGL format.
    packt_Log_debug("Configuring window format.");
    if (!eglGetConfigAttrib(mDisplay, lConfig,
        EGL_NATIVE_VISUAL_ID, &lFormat)) goto ERROR;
    ANativeWindow_setBuffersGeometry(mApplication->window, 0, 0, lFormat);
    // Creates the display surface.
    packt_Log_debug("Initializing the display.");
    mSurface = eglCreateWindowSurface(mDisplay, lConfig, mApplication->window, NULL);

```

--x--

Hope someone here can shed some light on it.

# Answer
> 0 votes
Your `lFormat` (and possibly `mDisplay` too) is not a pointer. You need to pass it as a pointer, using the reference operator (`&`) You might need to cast it too to match the `void*` on the function signature.

---
Tags: c++, android, mobile, opengl-es2
---


# Question
Title: How does the rectangle bounds (x,y,width,height) in libgdx work?
I cant work out how to use the rectangle bounds in libgdx I am currently using the superJumper example and have 2 or 3 examples with that are:

```
<!--this is the pause button in the top right corner-->
pause Bounds = new Rectangle(320 - 64, 480 - 64, 64, 64);

<!--this is a rectangle resume button in the middle of the
page in the menu that comes up when the pause button is pressed.-->
resume Bounds = new Rectangle(160 - 96, 240, 192, 36);

```

Basically my question is aimed at the `360 -64` and `160 -96` because I don't know why this is used. I need to create a rectangle that covers the left side of the screen and the same on the right. I want to create some on screen buttons, I have already created the actions for these buttons and I have managed to get them to work but I can't move the rectangles to where I want.

# Answer
The two first numbers is the position of the lower left corner, the reason that they in some cases are written as one number minus another is to make it clear that the position is offset from a position other than (0,0), in the first case the upper right corner, which happens to be at position (319,479), the screen having the resolution or virtual resolution of 320x480. The third and fourth numbers are simply the width and height of the rectangle.

For a rectangle to the left you would use something like: `new Rectangle(0, 0, 64, 480);` for a rectangle that is 64 pixels wide and cover the entire screen height. For just a part of this bar you could do something like: `new Rectangle(0, 128, 64, 64);` for a rectangle that is 64 by 64 and 128 pixels off the bottom of the screen.
> 1 votes

---
Tags: android, libgdx
---


# Question
Title: Canvas tile grid, hover effects, single tilesheet, etc
I'm currently in the process of building both the client and server side of an HTML5, canvas, and WebSocket game.

This is what I have thus far for the client: http://jsfiddle.net/dDmTf/20/

### Current obstacles

1. The hover effect has no idea what to put back after the mouse leaves. Currently it's just drawing a "void" tile, but I can't figure out how to redraw a single tile without redrawing the whole map.
2. How would I go about storing multiple layers within the `map` variable? I was considering just using a multi-dimensional array for each layer (similar to what you see as the current array), and just iterating through it, but is that really an efficient way of doing it?
3. Currently the "borders" encroach on one another. I'm not sure what I'm doing wrong? If you hover over and off of the bordering "tree" tiles, you'll notice how it removes part of the neighboring tiles border. This shouldn't need to happen.
4. Outside of the map, what would be an elegant way of adding Players to the render scene? I've seen a few places that recommend you use multiple canvas's, would you recommend that since they'll probably be moving much more? In addition to that, how can I confine player movement to the grid, similar to how in the pokemon gameboy games, when you tap the left arrow, you always move one "space" that direction. It's not a halfway type deal.
5. Camera. What would be a good way about adding a "camera" to the equation, so the viewport can pan around a larger map area?
6. Obstacles. In the newer version of the map, you'll notice an empty obstacles array. Assuming players get added well, what do you think would be good for adding movement obstacles?

### Side note

The tile sheet being used for the jsfiddle display is only for development. I'll be replacing it as things progress in the engine.

If you guys have any pointers for my JavaScript, feel free. As I'm more or less learning advanced usage as I go, I'm sure I'm doing plenty of things wrong.

**Note:** I will continue to update this post as the engine improves, but updating the jsfiddle link and updating the obstacles list by striking things that have been solved, or adding additions.

### Edit

Updated link from http://jsfiddle.net/dDmTf/7/ to http://jsfiddle.net/dDmTf/17/ \- this handles the "hover" problem, and it's been striked out.

### Edit

Updated link from http://jsfiddle.net/dDmTf/17/ to http://jsfiddle.net/dDmTf/19/ \- fixes the out of bounds issue with the tiles

### Edit

Updated link from http://jsfiddle.net/dDmTf/19/ to http://jsfiddle.net/dDmTf/20/ \- adds multiple layers to the equation

# Answer
I wouldn't call it an elegant solution or anything but at least it succeeds in solving the hovering problem without having to redraw the entire map. It redraws a 3x3 radius around the last mouse position instead, since that's the amount of tiles affected by your hover rectangle. Here's the **new fiddle** and below are the changes I made to the original one.

1. Extracted the inner part of your `renderMap` method to a separate method:

```
Renderer.prototype.renderTileAt = function(map, tilesheet, i, j) {
    var row = i * this.tilesize;
    var col = j * this.tilesize;
    if(map && (i in map) && (j in map[i])) {
        this.drawTile(tilesheet, col, row, map[i][j][0], map[i][j][1]);
    } else {
        this.drawCellRect('#333', col, row);
    }
}

Renderer.prototype.renderMap = function(map, tilesheet) {
    for(var i = 0; i < (this.getHeight() / this.tilesize); i++)
        for(var j = 0; j < (this.getWidth() / this.tilesize); j++)
             this.renderTileAt(map, tilesheet, i, j);
}

```
2. Since the red border "eats" into neighbour tiles I draw a 3x3 radius around the last mouse position instead:

```
if((lastX !== null && lastX != x) || (lastY !== null && lastY != y)) {
    var lastI = lastY / renderer.tilesize;
    var lastJ = lastX / renderer.tilesize;
    for(var i=lastI-1; i<=lastI+1; ++i)
        for(var j=lastJ-1; j<=lastJ+1; ++j)
            renderer.renderTileAt(map, sprite, i, j);
}

```

As for adding layers, yes just add a third dimension to your map array with how many layers you need.

**Edit 1**

Another alternative that would simplify the hover problem would be to draw the hover rectangle a little smaller so that it doesn't eat into the neighbours. For instance:

```
Renderer.prototype.drawHoverRect = function(color, x, y) {
    this.context.save();
    this.context.lineWidth = 2;
    this.context.strokeStyle = color;
    this.context.translate(x, y);
    this.context.strokeRect(1, 1, this.tilesize-2, this.tilesize-2);
    this.context.restore();
}

```

Also, make `drawCellRect` call `clearRect` at the top of the method. With both of those changes, instead of drawing the 3x3 region above, a single call is enough:

```
renderer.renderTileAt(map, sprite, lastY / renderer.tilesize, lastX / renderer.tilesize);

```

Updated fiddle **here**.

**Edit 2**

Yet another improvement, this time to the entire mouse move event handler (assuming the changes above are already in place):

```
var lastX = 0;
var lastY = 0;

canvas.addEventListener('mousemove', function(e) {
    var x = (e.pageX / renderer.tilesize) | 0;
    var y = (e.pageY / renderer.tilesize) | 0;
    if(lastX == x && lastY == y) return;
    renderer.renderTileAt(map, sprite, lastY, lastX);
    renderer.drawHoverRect('red', x * renderer.tilesize, y * renderer.tilesize);
    lastX = x;
    lastY = y;
})

```

It uses a trick found here to cast to int. I also got rid of those null checks and replaced them with a default value that does not do much harm. Once again, **updated fiddle here**.
> 3 votes

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


title: Make Sprite Jump Upon a Platform

text:
# Question
Title: Make Sprite Jump Upon a Platform
I have been struggling to make a game like Doodle Jump where the sprite jumps on a platform. So how do you make a sprite jump upon platforms in XNA? Th platforms are represented by a list of positions like `Public platformList As List(Of Vector2)`

This is the collision detection under `update()`

```
        Dim mainSpriteRect As Rectangle = New Rectangle(CInt(mainSprite.Position.X), CInt(mainSprite.Position.Y), mainSprite.texture.Width, mainSprite.texture.Height)
         'a node is simply a class with the texture and position'
        For Each _node As Node In _gameMap.nodeList
            Dim blockRect As Rectangle = New Rectangle(CInt(_node.Position.X), CInt(_node.Position.Y), _BlocksTexture.Width, _BlocksTexture.Height)

            If mainSpriteRect.Intersects(blockRect) Then
                'what should I do here? For example velocity and position?'
            End If

            If (_node.Position.Y > 800) Then
                nodeList.Remove(_node)
            End If

        Next

```

# Answer
You need a vector representing your velocity. This vector will modify your position every time the update method is called.

Then in every update check if the player is not touching a platform. If he is not then modify the velocity vector by some positive Y amount (this is gravity)

Once you have that all you need to do is detect when the player collide swith a platform and modify the velocity with a negative Y value (this is your jump)
> 1 votes

---
Tags: xna, sprites, windows-phone-7, spritebatch
---


title: Flip rotation matrix

text:
# Question
Title: Flip rotation matrix
I'm doing character control with kinect. I need to mirror the joint orientation because the character faces the player. Somehow by Googling through internet I've done it and everything works very well. But I have little idea about how the math works, here's my code:

```
//-------------------------------------------------------------------------------------
Ogre::Quaternion JointOrientationCalculator::buildQuaternion(Ogre::Vector3 xAxis, Ogre::Vector3 yAxis, Ogre::Vector3 zAxis)
{
    Ogre::Matrix3 mat;
    if(isMirror)
    {
        mat = Ogre::Matrix3(xAxis.x, yAxis.x, zAxis.x,
                            xAxis.y, yAxis.y, zAxis.y,
                            xAxis.z, yAxis.z, zAxis.z);
        Ogre::Matrix3 flipMat(1, 0,  0,
                              0, 1,  0,
                              0, 0, -1);
        mat = flipMat * mat * flipMat;
    }
    else
    {
        mat = Ogre::Matrix3(xAxis.x, -yAxis.x, zAxis.x,
                           -xAxis.y, yAxis.y, -zAxis.y,
                           xAxis.z,  -yAxis.z, zAxis.z);
    }

    Ogre::Quaternion q;
    q.FromRotationMatrix(mat);

    return q;
}

```

When I need to mirror/flip it by axes z I calculate `mat = flipMat * mat * flipMat;` but I don't understand how this equation works.

# Answer
> 1 votes
That matrix corresponds to the sequence of operations of (1) flipping the z-axis; (2) performing the original rotation; and (3) flipping the z-axis again. You can look at it as switching between "Kinect space" and your on-screen camera space, doing the rotation, then converting back to the original space. The resulting composite operation is the desired rotation, but in the flipped space.

Conceptually, it's similiar to what you'd do to rotate around a specified pivot point: you'd translate the pivot to the origin, then do the rotation, then undo the translation to return the pivot to its original location. In general you'd have a formula like inverse(matPivot) * matRotate * matPivot. However, in the case of your flip, `flipMat` is its own inverse, so the inverse() call is unnecessary. (By the way, a transform that is its own inverse is called an involution.)

---
Tags: matrix, rotation, quaternion, kinect
---


# Question
Title: UDK/ UnrealScript class interaction? HUD advice?
Beginner basics requested here, While i'm familiar with the basics of OOP programming i've just started looking as UnrealScript for a game i had made in the UDK editor up to now.

I have a class that extends UTHUD and another that extends UDKPAWN. I have the pawn destroyed when its been shot 3 times and some basic helloworld text displaying in my HUD but i'm completely lost as to how one would get some sort of feedback between the two classes going on?

What i would like to do to start off, is have some text that says something like "Amount of baddies killed: 0" Displayed on the HUD which would then increment each time the player destroyed one of my pawns.

I'm sorry if this is an inappropriate question but i've never really worked within a framework like this before and wasn't sure where to go for help to get my footing. All advice appreciated!

# Answer
First i created my own class that extended UTPlayerReplicationInfo and had a variable baddiesKilled.

Then in my game type class i added this line to default properties:

```
PlayerReplicationInfoClass = class'myPlayerReplicationInfo'

```

Then in the HUD class:

```
function DrawGameHud()
{
local myPlayerReplicationInfo PRI;

PRI = myPlayerReplicationInfo(PawnOwner.PlayerReplicationInfo);

Canvas.SetPos(Canvas.ClipX/2,Canvas.ClipY/6);
Canvas.SetDrawColor(255,60,210,255);
Canvas.Font = class'Engine'.static.GetLargeFont();
Canvas.DrawText("Baddies Killed=" + PRI.baddiesKilled);

}

```

Hope someone finds this useful.
> 0 votes

---
Tags: gui, unreal, udk
---


title: Flickering water effect

text:
# Question
Title: Flickering water effect
I have downloaded completely different samples with water effects (in XNA) and I've noticed that they all exhibit a common problem: when the camera direction (only the direction, not the position) moves, a noticable and annoying flicker occurs where the water meets terrain. I'm curios to find out more about this. Why does it happen? Does it have a name? And what can I do about it?

# Answer
> 3 votes
It's named **Z-fighting**. You can google a lot information about it. For example here on wiki. In short: your water and terrain plane are in the same distance from camera (they are coplanar). If you move your camera (direction), float results differ a bit, so sometimes (I mean: some pixels) it chooses water to be drawn, sometimes it chooses terrain.

And you can solve this problem easily - just move your water plane a bit above or under the terrain, if they have the same "height" (they are coplanar).

# Answer
> 0 votes
It is floating-point prcision error, you can fix that by not changing view matrix, if it has change only for little, if X or Y mouse rotation is less then 0.1 then use old view.

# Answer
> 0 votes
This problem can also be solved by using a logrithmic z-buffer which can be done in your shader, and is very very easy to implement.

---
Tags: xna, effects, water
---


# Question
Title: Direct3D9 application won't write to depth buffer
I've got an application written in D3D9 which will not write any values to the depth buffer, resulting in incorrect values for the depth test. Things I've checked so far:

* D3DRS\_ZENABLE, set to TRUE
* D3DRS\_ZWRITEENABLE, set to TRUE
* D3DRS\_ZFUNC, set to D3DCMP\_LESSEQUAL
* The depth buffer is definitely bound to the pipeline at the relevant time
* The depth buffer was correctly cleared before use.

I've used PIX to confirm that all of these things occurred as expected. For example, if I clear the depth buffer to 0 instead of 1, then correctly nothing is drawn, and PIX confirms that all the pixels failed the depth test. But I've also used PIX to confirm that my submitted geometry does not write to the depth buffer and so is not correctly rendered.

Any other suggestions?

# Answer
Turns out that I didn't set the projection matrix in the fixed function pipeline- not something I thought was necessary when using a shader.
> 0 votes

# Answer
Make sure that your depth buffer is set up correctly in your present parameters. Check the depth range specified in your viewport.
> 0 votes

---
Tags: directx9, depth-buffer
---


title: Ledge grab and climb in Unity3D

text:
# Question
Title: Ledge grab and climb in Unity3D
I just started on a new project. In this project one of the main gameplay mechanics is that you can grab a ledge on certain points in a level and hang on to it.

Now my question, since I've been wrestling with this for quite a while now. How could I actually implement this? I have tried it with animations, but it's just really ugly since the player will snap to a certain point where the animation starts.

# Answer
> 3 votes
I would do it something like this, assuming I wanted to specifically control the grab locations...

1. Use a player model that can be a ragdoll
2. Place a small invisible entity at spots that can be grabbed.
3. When the player jumps up, have their hands go upwards
4. If the player's hands come within a certain trigger distance of an invisible grab spot, a "grab" occurs

To handle a grab...

1. Let the player's body model keep moving on it's normal jump course
2. Ragdoll move the hands to the grab location
3. When the hands reach the grab location, lock them in place (they "grab")
4. Let the body now become a ragdoll with the hands pinned to the grab spot

To handle a pull up from a ledge...

1. Since the player's hands are pinned at the exact climb spot, you are all set for a "climb up" animation
2. Play the "climb up" animation

I'm playing pretty loose here with the details of how one moves & controls the ragdoll I admit. The idea though is to get those hands pinned onto the grab spot and let the player hang there pinned by the hands to the grab spot.

# Answer
> 2 votes
There is a tutorial on how to implement simple IK http://freespace.virgin.net/hugo.elias/models/m\_ik.htm .

# Answer
> 0 votes
3D buzz have a 3rd person character system tutorial which includes a climbing system. It's under the "Integrating Maya Characters"

http://www.3dbuzz.com/vbforum/sv\_videonav.php?fid=3e87b1f570fc9c24ab89ad850ec2f71b

I haven't watched all the videos yet but the final result looks good and I'm sure could be extended to include other aspects of climbing.

---
Tags: animation, unity, javascript
---


# Question
Title: Unsure how to decide ray intersection interval
I'm coding an intersection algorithm with AABB, as found here. However, I'm absolutely unsure what to pass in as `t0` and `t1`. The paper states that it's a ray intersection interval, but the only material I've been able to find on this is that it's some kind of guess or bound as to the final values. Any suggestions as to how to define `t0` and `t1`?

# Answer
I actually used this implementation myself. As far as I remember t0 and t1 are like the "clipping planes". So t0 you would think of as the ray origin or eye/camera position. So you might use t0 = 0.0 or t0 = 0.0 + epsilon. The idea being, if an intersection occurs *behind* the ray origin, the intersection point will be t \< t0 and therefore is not the intersection you are looking for.

Now, for t1 is it sort of a guess. This is the furthest distance that you want to allow an intersection to occur. Usually when building a ray tracer you specify a maximum distance (or maximum ray length), beyond which you ignore any intersections. So you might specify t1 to be this distance as well.

Hope that helps.
> 2 votes

# Answer
The explanation of the math goes something like this:

A line can be represented as two points, call them A and B. Any point on a line can be represented with a parametric equation L(t) = A + t(AB), where (AB) is the vector from A to B (that is, B - A). If you work through that, you see that L(0) = A and L(1) = B. For t=0, you get A + 0(AB) = A, and for t=1, you can A + 1(AB) = A + 1(B - A) = A + B - A = B.

Now let's think about what a line, ray, and line segment really are. A line is an infinite series of points that contains a reference point and for which all points can be formed by adding that reference point to a scalar multiple of a vector. Which is exactly what L(t) = A + t(AB) says.

A ray however is a a line in which the scalar multiple must be positive. So R(t) = A + t(AB) for all t \>= 0. A ray is contained in a line, but a negative t value plugged into the equation would give you a point on the line that is "behind" the ray's reference point. That is, if your ray starts at (1,1) and goes in the direction (1,0), and you put in t=-1, you get (1,1) + -1(1,0) = (0,1), which is clearly to the left of the reference point while the ray is pointing to the right.

A line segment is similar, except that now the t value must be constrained to \[0,1\]. That is, LS(t) = A + t(AB) for all t in \[0,1\]. If you put a t value larger than 1 in, you'll get a point "past" the point B. So if your line segment goes from (1,0) to (5,0), and you plug in t=1.5, you get (1,0) + 1.5((5,0)-(1,0)) = (1,0) + 1.5(4,0) = (7,0), which is clearly farther to the right than the rightmost point of the line segment.

Remember, however, that for all three line-like objects, the only thing you need to represent them is a single point and a vector. In the case of a line, the vector can be pointing either "left" or "right" along the line, because t can literally be any scalar value. In the case of a ray, the vector must point in the direction the ray points, but it doesn't matter how long the vector is, because t can be any non-negative value, including infinity. In the case of a line-segment, the vector must be the vector from the first end-point to the second end-point, because t must be constrained to \[0,1\] and the reference point plus the vector must be equal to the second end-point.

The AABB intersection code you're looking at is working with a Ray object, but that object is really just a point and a vector. Since we know that a point and a vector can represent a line, a ray, or a line segment, we see that the code is actually valid for any line-like object; the use of the name Ray is just a tad misleading.

Since the only differences between a line, ray, or line segment is what range the t values must be constrained to in its parametric form, and since the AABB intersection test is calculating the t value for the parametric form, the code will work for all three objects. The t0 and t1 values are the limits of t value required. So for a line, t0 and t1 should be -infinity and +infinity (-FLT\_MAX and +FLT\_MAX are reasonable and reliable alternatives in C/C++ code). For a ray, the values should be 0 and +infinity. For a line segment, the values should be 0 and 1.

Note that in the case of the line segment, the t values assuming that the vector provided really will point from A to B. If the Ray object you're using always normalized its vector, then the line segment equation becomes LS(t) = A + len(AB)\*t\*v for all t in \[0,len(AB)\]. In other words, if the vector passed to the test is normalized, pass in 0 for t0 and the distance between the two end-points of the line segment for t1.

To summarize: for a ray, pass in t0=0 and t1=+infinity (or FLT\_MAX).
> 1 votes

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


# Question
Title: How to wire finite state machine into component-based architecture?
### State machines seem to cause harmful dependencies in component-based architectures.

How, specifically, is communication handled between a state machine and the components that carry out state-related behavior?

**Where I'm at:**

* I'm new to component-based architectures.
* I'm making a fighting game, although I don't think that should matter. I envision my state machine being used to toggle states like "crouching", "dashing", "blocking", etc.
* I've found this state-management technique to be the most natural system for a component-based architecture, but it conflicts with techniques I've read about: Dynamic Game Object Component System for Mutable Behavior Characters It suggests that all components activate/deactivate themselves by continually checking a condition for activation.
* I think that actions like "running" or "walking" make sense as states, which is in disagreement with the accepted response here: https://gamedev.stackexchange.com/a/7934
* I've found this useful, but ambiguous: How to implement behavior in a component-based game architecture? It suggests having a separate component that contains nothing but a state machine. But, this necessitates some kind of coupling between the state machine component and nearly all the other components. I don't understand how this coupling should be handled. These are some guesses:

**A.** *Components depend on state machine:*
Components receive reference to state machine component's `getState()`, which returns an enumeration constant. Components update themselves regularly and check this as needed.

**B.** *State machine depends on components:*
The state machine component receives references to all the components it's monitoring. It queries their `getState()` methods to see where they're at.

**C.** *Some abstraction between them*
Use an event hub? Command pattern?

**D.** *Separate state objects that reference components*
State Pattern is used. Separate state objects are created, which activate/deactivate a set of components. State machine switches between state objects.
* I'm looking at components as implementations of *aspects*. They do everything that's needed internally to make that aspect happen. It seems like components should function on their own, without relying on other components. I know some dependencies are necessary, but state machines seem to want to control all of my components.

# Answer
> 7 votes
The overview is fairly light, but check out these slides from a presentation I did for New Game Conf last year:

https://docs.google.com/presentation/d/110MxOqut\_y7KOW1pNwIdcccisIA3ooJwVR-xm-ecuc4/view

(see pertinent images below)

The gist of the technique is to combine the action list pattern (explained -- somewhat poorly -- in the slides) with behavioral state machines that act upon a component-based game entity.

It is in essence the same as creating a special composition system just for AI behavior, geared towards the kinds of inter-behavioral integration you need for simpler AI systems.

My favorite part of that particular game was how we could create entirely new types of enemies by simply selecting from a list of pre-written behaviors, put them into the action list for the game object (residing in a BrainComponent) in the order of desired priority, and everything just worked. With an action list that allows for Blocking/NonBlocking actions, this can do some really cool things despite how simple it all is to implement.

Even behaviors like "stun" where really just a StunBehaviorAction pushed onto the top of action list stack; if the stun behavior become activated (after observing that the game object's EarsComponent heard a stunning shockwave attack) then it set its internal state to Stunned, told the AnimationComponent to play the stun animation, and set its action state to Blocking, and its timer to a stun timeout pulled from the game object's EnemyParametersComponent. Since it was Blocking and at the top of the action list, none of the other BehaviorAction's in the action list would get their update method called, so they would essentially be switched off. When the timeout expired, the StunBehaviorAction set its state back to Idle and its action state to NonBlocking.

The other behaviors we implemented were almost all implemented with a single internal state machine. The only two that didn't have state machines, in fact, were the PatrolPathBehaviorAction (it would push a series of PathAction's onto the action list if it was idle, which in turn pushed MoveAction's) and the GuardHomeBehaviorAction (always at the bottom of the action list, and would always just push a PathAction back to the enemy's home location). Every other behavior was a state machine.

# Answer
> 3 votes
At a previous company I worked for we had a component-based system with state-based AI. We had an AI component that controlled all behavior for that object/unit. When the AI was active, like wandering, attacking, etc, it would receive an update each frame to do any logic that was needed. When the AI was idling or not moving the component was deactivated and not updated each frame. The component, while deactivated, could still receive event-based messages, so it would receive a message for something like a player entering its aggro radius, and could respond to that by reactivating the AI component so that it could do frame-based updates.

The AI component has sub-components, that it could create and destroy on the fly, based on what type of actions it was performing. For example if it was wandering it could create a wandering sub-component and update that each frame while wandering, and then if aggro'd while wandering it would close that sub-component and open an attack sub-component. The AI component should be independent of all other components on an object. For example, we had an input component, that would simply query for movement values on a unit. The query it made was something that both human and AI objects would respond to. This allowed the AI component to simply set movement values on itself during things like wandering, that the input component could pick up on, just as a human controllable component would set values that the input component could pick up on. Things like this allow the AI component to be independent of any other component on the object.

# Answer
> 1 votes
It's a little unclear what you mean by components as your terms are very vague with no concrete examples. Often game entities are built using composition rather than inheritence. Thus you could make them into something that can take damage by adding a health component to the entity or you could make them animate by adding an animate component. One could also put the AI in such a component. There will be decision making logic in your AI component and if you're concerned about coupling that to much of the other code in the system you could collect the information into a blackboard which the AI logic is only allowed access to. There is also the issue of dependencies on the output of AI system. Basically your AI is controlling an entity and that control needs an interface. One useful concept is that of a controller or gamepad. Your AI can fill out a similar structure that a player gamepad would fill out (though it might have some extra "buttons" for specific abilities). Now this structure could then be passed to your animate component which would interpret it and select the appropriate animations to play. Different AI sub-components could even be writing to different fields of the structure or to the same fields with different priorities. Aiming and walking for example.

---
Tags: architecture, ai, component-based, fsm
---


title: Image Processing in game engines

text:
# Question
Title: Image Processing in game engines
I'm going to try and use GEGL to allow real-time texture manipulation on an open-source 3D game engine.

What are the most common and most needed operations used on images, textures in game engines?

Thank you!

# Answer
> 1 votes
Well generally image manipulation would be kept to a minimum because it's expensive and, if it's done, it's probably done with a shader.

That said, general things might include color replacement and maybe putting two images together.

However, these are generally not done in real time. Most of the effects are done on what you see and images are already in their ready state.

---
Tags: textures, image
---


# Question
Title: Realtime rendering using a ray tracing engine
I want to render an object that has a mesh with one million hexagonal elements(100 * 100 * 100).

Lights, shadows and textures is not important and each element has a solid color. and finally, the actions I want to have, is simply rotating the object, zooming and panning.

I am wondering what ray tracing engine is better for my conditions. or, do I have to take another approach?

any help will be appreciated.

# Answer
> 2 votes
Since lights and shadows are not important, I'd suggest going with any 3D engine that works with your programming language. Raytracing would be overkill and certainly slower than hardware acceleration.

---
Tags: rendering, 3d-meshes, raytracing
---


# Question
Title: The best algorithm enhancing alpha-beta?
I'm studying AI. My teacher gave us source code of a chess-like game and asked us to enhance it. My exercise is to improve the alpha/beta algorithm implementing in that game. The programmer already uses transposition tables, MTD(f) with alpha/beta+memory (MTD(f) is the best algorithm I know by far). So is there any better algorithm to enhance alpha-beta search or a good way to implement MTD(f) in coding a game?

# Answer
I'll answer generally then more specifically. First, in my experience when a professor asks is there a better way.. I immediately go to the book and look for things the author noted as shortfalls of the algorithm in question. Second, I look at optimizations that have helped me in the past.

For a tree searching algorithm like alpha-beta I would look at adding a heuristic that reduces the number of searches or causes it to look in more likely locations first.

I would assign weights to paths that can be taken in the tree based on past results. If a path has resulting in a higher score in the past, the it's probably a good path to take again. So long story short, add heuristics to the paths and choose to go with those so the algorithm can terminate earlier.

Note that I don't really remember much about the specific algorithm, just that it is a tree and the naive approach to it does not involve this heuristic.
> 6 votes

# Answer
You didn't mention null move pruning or late move reductions. They're fairly easy to implement and are even more effective at reducing the search size than alpha-beta pruning. Search extensions are also important to mitigate the horizon effect; quiescence search in particular is a very important component for a chess AI.
> 4 votes

# Answer
Look into move ordering and principle variation search
> 1 votes

---
Tags: algorithm, ai, chess
---


# Question
Title: How to effectively gather info about how players play my HTML5 game?
I'm finishing another HTML5 game, and this time I'd like to do some spying business on the players... Mostly just basic stuff: when they are playing, for how long, what upgrades they are buying the most and so on. Now, my first idea was just to collect this information during the gameplay, and then have a Javascript function fire when they close the tab/browser, and said function would send it to my server via Socket.io. This, of course, wouldn't work, because anyone who takes a look at the code would realize it and could start sending a tonne of false info which would mess up my statistics.

Questions:

* Is there a way to effectively do this?
* If yes, what kind of info should I be looking for, aside from stuff I already mentioned?

# Answer
> 3 votes
You can simply gather all the info you need into some convenient form, such as JSON or something, then send it at some stage in a XmlHttpRequest, whenever you feel is appropriate.

Yes, people COULD forge requests and send loads of crap, but they probably won't. And you can record the IP address of each recipient, and if an unlikely amount of responses come from one address, you can just disregard them all.

It is highly unlikely that you will have any problems. Those eleet haxxors have better things to do than skew your stats. Really.

# Answer
> 0 votes
Well this is much easier in a multiplayer game where things are validated but you could probably do the same thing.basically, male a log of all actions and periodically send it to the server. (or when he/she logs in or out. You could also encrypt the data or obfuscate your code. But, since you're using html it's not fool proof.

---
Tags: game-design, statistics
---


title: OpenGL ES 2 on Android: native window

text:
# Question
Title: OpenGL ES 2 on Android: native window
According to OGLES specification, we have the following definition:

```
EGLSurface eglCreateWindowSurface(EGLDisplay display,
                                  EGLConfig config,
                                  NativeWindowType native_window,
                                  EGLint const * attrib_list)

```

More details, here: http://www.khronos.org/opengles/documentation/opengles1\_0/html/eglCreateWindowSurface.html

And also by definition:

```
int32_t ANativeWindow_setBuffersGeometry(ANativeWindow* window, int32_t width,
                                         int32_t height, int32_t format);

```

More details, here: http://mobilepearls.com/labs/native-android-api

I am running Android Native App on OGLES 2 and debugging it in a Samsung Nexus device. For setting up the 3D scene graph environment, the following variables are defined:

```
struct android_app {
    ...
    ANativeWindow* window;
};
android_app* mApplication;
...
mApplication=&pApplication;

```

And to initialize the App, we run the commands in the code:

```
ANativeWindow_setBuffersGeometry(mApplication->window, 0, 0, lFormat);
mSurface = eglCreateWindowSurface(mDisplay, lConfig,
                                  mApplication->window, NULL);

```

Funny to say is that, the command ANativeWindow\_setBuffersGeometry behaves as expected and works fine according to its definition, accepting all the parameters sent to it. But the eglCreateWindowSurface does no accept the parameter mApplication-\>window, as it should accept according to its definition. Instead, it looks for the following input:

```
EGLNativeWindowType hWnd;
mSurface = eglCreateWindowSurface(mDisplay,lConfig,hWnd,NULL);

```

As an alternative, I considered to use instead:

```
NativeWindowType hWnd=android_createDisplaySurface();

```

But debugger says:

```
Function 'android_createDisplaySurface' could not be resolved

```

Is 'android\_createDisplaySurface' compatible only for OGLES 1 and not for OGLES 2?

Can someone tell if there is a way to convert mApplication-\>window? In a way that the data from the android\_app get accepted to the window surface?

# Answer
Are you sure you are using egl.h header from Android NDK? In Android NDK EGLNativeWindowType is defined in eglplatform.h file (it is included from egl.h):

```
#elif defined(__ANDROID__) || defined(ANDROID)
#include <android/native_window.h>
...
typedef struct ANativeWindow*           EGLNativeWindowType;

```

As you can see EGLNativeWindowType has correct type - ANativeWindow\*
> 3 votes

---
Tags: c++, android, opengl-es2, mobile
---


# Question
Title: Difference between the terms Material & Effect
I'm making an effect system right now (I think, because it may be a material system... or both!). The effects system follows the common (e.g. COLLADA, DirectX) effect framework abstraction of Effects have Techniques, Techniques have Passes, Passes have States & Shader Programs.

An effect, according to COLLADA, defines the equations necessary for the visual appearance of geometry and screen-space image processing. Keeping with the abstraction, effects contain techniques.

Each effect can contain one or many techniques (i.e. ways to generate the effect), each of which describes a different method for rendering that effect. The technique could be relate to quality (e.g. high precision, high LOD, etc.), or in-game-situation (e.g. night/day, power-up-mode, etc.). Techniques hold a description of the textures, samplers, shaders, parameters, & passes necessary for rendering this effect using one method.

Some algorithms require several passes to render the effect. Pipeline descriptions are broken into an ordered collection of Pass objects. A pass provides a static declaration of all the render states, shaders, & settings for "one rendering pipeline" (i.e. one pass).

Meshes usually contain a series of materials that define the model. According to the COLLADA spec (again), a material instantiates an effect, fills its parameters with values, & selects a technique. But I see material defined differently in other places, such as just the Lambert, Blinn, Phong "material types/shaded surfaces", or as Metal, Plastic, Wood, etc.

In game dev forums, people often talk about implementing a "material/effect system". Is the material not an instance of an effect? Ergo, if I had effect objects, stored in a collection, & each effect instance object with there own parameter setting, then there is no need for the concept of a material... Or am I interpreting it wrong?

Please help by contributing your interpretations as I want to be clear on a distinction (if any), & don't want to miss out on the concept of a material if it should be implemented to follow the abstraction of the DirectX FX framework & COLLADA definitions closely.

# Answer
> 6 votes
These terms are not set in stone and every company and every piece of software may use them slightly differently. However, I believe that the most common meaning of "material" is just what you mentioned, i.e. an effect together with specific parameter values and textures to be bound to that effect, and applied to specific triangles or meshes of objects.

For example, Blinn-Phong shading could be an effect and various metals, plastics, woods, and many other materials could be made using Blinn-Phong shading with different textures, different specular values, etc. However, skin would require a different effect because it needs subsurface scattering features that the basic Blinn-Phong effect doesn't provide.

In a game engine, effects and materials would typically be two separate classes. An effect class would hold the compiled GPU code for the shaders, some information about the parameters and textures it supports/requires, and some logic that is common to all materials using that effect - for instance, technique selection logic (e.g. use the shadow map technique when drawing in the shadow map, select a quality level based on the object's distance to the camera, etc.), and logic for setting parameters that don't depend on the material (e.g. transformation matrices, global lighting parameters, etc.)

The material class would typically contain a reference to an effect, references to any relevant texture images, and a list of parameter values.

It wouldn't be good to have an effect instance for every material because then you'd be duplicating all the information (particularly the shader GPU code) unnecessarily. Moreover, you might want to have different lifetimes and loading models for the effects vs the materials. For example, you might load all the effects when your game starts up, but load materials for each level only when you load the level.

---
Tags: opengl, graphics, directx, graphics-programming, collada
---


title: Triangle Picking Picking Back faces

text:
# Question
Title: Triangle Picking Picking Back faces
I'm having a bit of trouble with 3D picking, at first I thought my ray was inaccurate but it turns out that the picking is happening on faces facing the camera and faces facing away from the camera which I'm currently culling.

Here's my ray creation code, I'm pretty sure the problem isn't here but I've been wrong before.

```
    private uint Pick()
    {
        Ray cursorRay = CalculateCursorRay();
        Vector3? point = Control.Mesh.RayCast(cursorRay);
        if (point != null)
        {
            Tile hitTile = Control.TileMesh.GetTileAtPoint(point);
            return hitTile == null ? uint.MaxValue : (uint)(hitTile.X + hitTile.Y * Control.Generator.TilesWide);
        }
        return uint.MaxValue;
    }

    private Ray CalculateCursorRay()
    {
        Vector3 nearPoint = Control.Camera.Unproject(new Vector3(Cursor.Position.X, Control.ClientRectangle.Height - Cursor.Position.Y, 0f));
        Vector3 farPoint = Control.Camera.Unproject(new Vector3(Cursor.Position.X, Control.ClientRectangle.Height - Cursor.Position.Y, 1f));
        Vector3 direction = farPoint - nearPoint;
        direction.Normalize();
        return new Ray(nearPoint, direction);
    }

    public Vector3 Camera.Unproject(Vector3 source)
    {
        Vector4 result;

        result.X = (source.X - _control.ClientRectangle.X) * 2 / _control.ClientRectangle.Width - 1;
        result.Y = (source.Y - _control.ClientRectangle.Y) * 2 / _control.ClientRectangle.Height - 1;
        result.Z = source.Z - 1;
        if (_farPlane - 1 == 0)
            result.Z = 0;
        else
            result.Z = result.Z / (_farPlane - 1);
        result.W = 1f;
        result = Vector4.Transform(result, Matrix4.Invert(ProjectionMatrix));
        result = Vector4.Transform(result, Matrix4.Invert(ViewMatrix));
        result = Vector4.Transform(result, Matrix4.Invert(_world));
        result = Vector4.Divide(result, result.W);
        return new Vector3(result.X, result.Y, result.Z);
    }

```

And my triangle intersection code. Ripped mainly from the XNA picking sample.

```
    public float? Intersects(Ray ray)
    {
        float? closestHit = Bounds.Intersects(ray);
        if (closestHit != null && Vertices.Length == 3)
        {
            Vector3 e1, e2;
            Vector3.Subtract(ref Vertices[1].Position, ref Vertices[0].Position, out e1);
            Vector3.Subtract(ref Vertices[2].Position, ref Vertices[0].Position, out e2);

            Vector3 directionCrossEdge2;
            Vector3.Cross(ref ray.Direction, ref e2, out directionCrossEdge2);
            float determinant;
            Vector3.Dot(ref e1, ref directionCrossEdge2, out determinant);
            if (determinant > -float.Epsilon && determinant < float.Epsilon)
                return null;
            float inverseDeterminant = 1.0f/determinant;
            Vector3 distanceVector;
            Vector3.Subtract(ref ray.Position, ref Vertices[0].Position, out distanceVector);

            float triangleU;
            Vector3.Dot(ref distanceVector, ref directionCrossEdge2, out triangleU);
            triangleU *= inverseDeterminant;
            if (triangleU < 0 || triangleU > 1)
                return null;
            Vector3 distanceCrossEdge1;
            Vector3.Cross(ref distanceVector, ref e1, out distanceCrossEdge1);
            float triangleV;
            Vector3.Dot(ref ray.Direction, ref distanceCrossEdge1, out triangleV);
            triangleV *= inverseDeterminant;
            if (triangleV < 0 || triangleU + triangleV > 1)
                return null;

            float rayDistance;
            Vector3.Dot(ref e2, ref distanceCrossEdge1, out rayDistance);
            rayDistance *= inverseDeterminant;
            if (rayDistance < 0)
                return null;
            return rayDistance;
        }
        return closestHit;
    }

```

I'll admit I don't fully understand all of the math behind the intersection and that is something I'm working on, but my understanding was that if rayDistance was less than 0 the face was facing away from the camera, and shouldn't be counted as a hit.

So my question is, is there an issue with my intersection or ray creation code, or is there another check I need to perform to tell if the face is facing away from the camera, and if so any hints on what that check might contain would be appreciated.

\**Edit the working UnProject method.

```
public static Vector3 UnProject(ref Matrix4 projection, Matrix4 view, Size viewport, Vector3 mouse)
    {
        Vector4 vec;

        vec.X = 2.0f * mouse.X / (float)viewport.Width - 1;
        vec.Y = -(2.0f * mouse.Y / (float)viewport.Height - 1);
        vec.Z = mouse.Z;
        vec.W = 1.0f;

        Matrix4 viewInv = Matrix4.Invert(view);
        Matrix4 projInv = Matrix4.Invert(projection);

        Vector4.Transform(ref vec, ref projInv, out vec);
        Vector4.Transform(ref vec, ref viewInv, out vec);

        if (vec.W > float.Epsilon || vec.W < float.Epsilon)
        {
            vec.X /= vec.W;
            vec.Y /= vec.W;
            vec.Z /= vec.W;
        }

        return vec.Xyz;
    }

```

# Answer
This isn't a complete answer in itself, but this wouldn't fit into the comments below your question.

If believe this part of the `Intersects` function is what should be disallowing reverse facing triangles to be given as a result:

```
float triangleU;
Vector3.Dot(ref distanceVector, ref directionCrossEdge2, out triangleU);
triangleU *= inverseDeterminant;
if (triangleU < 0 || triangleU > 1)
    return null;

```

If this code was taken from the XNA sample, then you can be almost certain that the code from the sample is not part of the problem you're seeing, so either you have changed something in the sample code itself, or you're passing unexpected data into the methods from the sample. I can't pinpoint exactly where the problem is, but my best guess is that it lies somewhere in the `Camera.Unproject` function where the result is being modified.
> 2 votes

---
Tags: 3d, picking
---


# Question
Title: Translate the ModelView matrix, or change vertex coordinates?
If I have a simple 2D scene and I want to move the objects inside the scene on the X and Y axis, should I send OpenGL the original vertex coordinates with each move and apply a ModelView matrix transform, or should I simply send the updated coordinates?

Since the scene is simple and there are really not that many vertices, I'm not using vertex buffers.

# Answer
> 4 votes
The proper way to do it is to use the ModelView matrix to move your object. The object's vertices are defined in the local space of the object, and it's generally good practice not to disturb the data.

This scales well to complex 3D objects and animation because the joint transforms and ModelView matrix operations can be done much faster in a shader than in software. Even if your scene is simple, it's good to adhere to the proper methods.

UPDATE: It's still ok to modify the ModelView matrix outside of the shader. For each object, this only means that we'll do 2 or 3 matrix-matrix multiplications per-frame outside of a shader, and then N matrix-vector multiplications inside the shader, where N is the number of vertices in the object.

---
Tags: opengl
---


title: GLSL subroutine not being used

text:
# Question
Title: GLSL subroutine not being used
I'm using a gaussian blur fragment shader. In it, I thought it would be concise to include 2 subroutines: one for selecting the horizontal texture coordinate offsets, and another for the vertical texture coordinate offsets. This way, I just have one gaussian blur shader to manage.

Here is the code for my shader. The {{NAME}} bits are template placeholders that I substitute in at shader compile time:

```
#version 420

subroutine vec2 sample_coord_type(int i);
subroutine uniform sample_coord_type sample_coord;

in vec2 texcoord;
out vec3 color;

uniform sampler2D tex;
uniform int texture_size;

const float offsets[{{NUM_SAMPLES}}] = float[]({{SAMPLE_OFFSETS}});
const float weights[{{NUM_SAMPLES}}] = float[]({{SAMPLE_WEIGHTS}});

subroutine(sample_coord_type) vec2 vertical_coord(int i) {
    return vec2(0.0, offsets[i] / texture_size);
}

subroutine(sample_coord_type) vec2 horizontal_coord(int i) {
    //return vec2(offsets[i] / texture_size, 0.0);
    return vec2(0.0, 0.0); // just for testing if this subroutine gets used
}

void main(void) {
    color = vec3(0.0);

    for (int i=0; i<{{NUM_SAMPLES}}; i++) {
        color += texture(tex, texcoord + sample_coord(i)).rgb * weights[i];
        color += texture(tex, texcoord - sample_coord(i)).rgb * weights[i];
    }
}

```

Here is my code for selecting the subroutine:

```
blur_program->start();
blur_program->set_subroutine("sample_coord", "vertical_coord", GL_FRAGMENT_SHADER);
blur_program->set_int("texture_size", width);
blur_program->set_texture("tex", *deferred_output);
blur_program->draw(); // draws a quad for the fragment shader to run on

```

and:

```
void ShaderProgram::set_subroutine(constr name, constr routine, GLenum target) {
    GLuint routine_index = glGetSubroutineIndex(id, target, routine.c_str());
    GLuint uniform_index = glGetSubroutineUniformLocation(id, target, name.c_str());
    glUniformSubroutinesuiv(target, 1, &routine_index);

    // debugging
    int num_subs;
    glGetActiveSubroutineUniformiv(id, target, uniform_index, GL_NUM_COMPATIBLE_SUBROUTINES, &num_subs);
    std::cout << uniform_index << " " << routine_index << " " << num_subs << "\n";
}

```

I've checked for errors, and there are none. When I pass in `vertical_coord` as the routine to use, my scene is blurred vertically, as it should be. The `routine_index` variable is also 1 (which is weird, because `vertical_coord` subroutine is the first listed in the shader code...but no matter, maybe the compiler is switching things around)

However, when I pass in `horizontal_coord`, my scene is STILL blurred vertically, even though the value of `routine_index` is 0, suggesting that a different subroutine is being used. Yet the `horizontal_coord` subroutine explicitly does not blur.

What's more is, whichever subroutine comes first in the shader, is the subroutine that the shader uses permanently. Right now, `vertical_coord` comes first, so the shader blurs vertically always. If I put `horizontal_coord` first, the scene is unblurred, as expected, but then I cannot select the `vertical_coord` subroutine! :)

Also, the value of `num_subs` is 2, suggesting that there are 2 subroutines compatible with my `sample_coord` subroutine uniform.

Just to re-iterate, all of my return values are fine, and there are no glGetError() errors happening.

Any ideas?

# Answer
> 6 votes
After a lot of pain, I figured out that I was indirectly calling glUseProgram() twice with my framework. The first time, to set the subroutine, the second time, in the draw() method of my shader program object. Apparently subroutine selection *do not* persist in shader program state, so it was being reset on the second call.

Hopefully this saves someone some time! :)

---
Tags: opengl, shaders, glsl
---


title: Lightning whip particle effects

text:
# Question
Title: Lightning whip particle effects
I'm currently using Mercury Particle Engine for the particle effects in my game, and I'm trying to create a sort of lightning whip - basically a lightning effect bound to a line that curves when the player moves. I know how to use the editor, and I have particle effects working in game. However, I'm completely lost as to where I should start for this specific particle effect.

Perhaps if I could find the code for it in a different particle engine, I could convert it, but I can't seem to find that either. What I did find was a lot of tutorials for creating the lines associated with lightning programmatically, which doesn't help in this case because I don't want it to be rigid. Perhaps it would be more like some sort of laser beam with crackling effects around it? I'm running into a wall as far as even beginning to implement this goes.

# Answer
Despite lightning consisting out of free electrons and ions I'm not sure if a particle effect is the way to go here. What you typically see is strands of electricity writhing about in a static (pun not intended) manner, it will be very hard to obtain this kind of visual effect by using a particle system alone:

Furthermore, it is advisable to use a particle system solely for visual effect, because it's expensive to check individual particle collisions in a lot of cases and you're better off simulating the associated gameplay effects in another way.\[1\]

So, if you haven't done so already, you should create the gameplay effect for the whip first, by applying the techniques mentioned in the answer to 2D Rope Collision Detection, but instead of drawing a rope, use the curve based on the resulting positions as a custom emitter for spark-like particles.

This way you get a whip which behaves the way you want to (based on the physics parameters), efficient collision detection with enemy spaceships and your desired lightning particle effect.

**Update:** If you just want to achieve the effect in Super Stardust Delta (as shown in the image you linked, and throughout this movie), you could have the whip curve emit brightly lit (in the case of the game: reddish) particles which die relatively quickly, and make sure they start out smaller the further along the curve they are away from the space ship.

Alternatively, to add more realistic "squiggles", instead of drawing a rope texture, use a variation of the technique described in the lightning whip movie I linked earlier: http://www.youtube.com/watch?v=grQCOzrdlXs#t=173s

1. Get an animated lightning texture, something like this:
2. And draw it multiple times along the curve, making use of blending, distracting particle effects like this and animation offsetting to cover up transition areas.

*Alter-alternatively*, draw a number of curves instead of just one, using slightly perturbed points and different weight parameters, to simulate the lightning strands (giving an effect comparable to the image above). Though the result on itself won't be as chaotic as lightning usually looks, you might still be able to come up with a nice effect by tweaking the emitter to more erratically dispense the lightning sparks.
> 3 votes

---
Tags: xna, particles
---


# Question
Title: How to stop a tap event from propagating in a XNA / Silverlight game
I have a game with Silverlight / XNA game where text and buttons are created in Silverlight while 3d is done in XNA.

The Silverlight controls are drawn ontop of the 3D and I dont want a click on a button to interact with the 3D underneath

So I have

```
private void ButtonPlaceBrick_Tap(object sender, GestureEventArgs e)
{
    e.Handled = true;

```

But my gesture handling on the 3d objects still runs even though I have set handled to true.

```
private void OnUpdate(object sender, GameTimerEventArgs e)
{
    while (TouchPanel.IsGestureAvailable)
    {
         // Read the next gesture
         GestureSample gesture = TouchPanel.ReadGesture();
         switch (gesture.GestureType)

```

How am I supposed to stop it from propagating?

# Answer
The best solution is to define a region that contains your controls and if the touch position is inside it, do nothing in your XNA code since the event is already processed by Silverlight controls.
> 1 votes

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


title: Incorrect results for frustum cull

text:
# Question
Title: Incorrect results for frustum cull
Previously, I had a problem with my frustum culling producing too optimistic results- that is, including many objects that were not in the view volume. Now I have refactored that code and produced a cull that should be accurate to the actual frustum, instead of an axis-aligned box approximation. The problem is that now it never returns anything to be in the view volume.

As the mathematical support library I'm using does not provide plane support functions, I had to code much of this functionality myself, and I'm not really the mathematical type, so it's likely that I've made some silly error somewhere. As follows is the relevant code:

```
class Plane {
public:
    Plane() {
        r0 = Math::Vector(0,0,0);
        normal = Math::Vector(0,1,0);
    }
    Plane(Math::Vector p1, Math::Vector p2, Math::Vector p3) {
        r0 = p1;
        normal = Math::Normalize(Math::Cross((p2 - p1), (p3 - p1)));
    }
    Math::Vector r0;
    Math::Vector normal;
};

```

This class represents one plane as a point and a normal vector.

```
class Frustum {
public:
    Frustum(
        const std::array<Math::Vector, 8>& points
        )
    {
        planes[0] = Plane(points[0], points[1], points[2]);
        planes[1] = Plane(points[4], points[5], points[6]);
        planes[2] = Plane(points[0], points[1], points[4]);
        planes[3] = Plane(points[2], points[3], points[6]);
        planes[4] = Plane(points[0], points[2], points[4]);
        planes[5] = Plane(points[1], points[3], points[5]);
    }
    Plane planes[6];
};

```

The points are passed in order where (the inverse of) each bit of the index of each point indicates whether it's the left, top, and back of the frustum, respectively. As such, I just picked any three points where they all shared one bit in common to define the planes.

My intersection test is as follows (based on this):

```
bool Intersects(Math::AABB lhs, const Frustum& rhs) const {
    for(int i = 0; i < 6; i++) {
        Math::Vector pvertex = lhs.TopRightFurthest;
        Math::Vector nvertex = lhs.BottomLeftClosest;
        if (rhs.planes[i].normal.x <= -0.0f) {
            std::swap(pvertex.x, nvertex.x);
        }
        if (rhs.planes[i].normal.y <= -0.0f) {
            std::swap(pvertex.y, nvertex.y);
        }
        if (rhs.planes[i].normal.z <= -0.0f) {
            std::swap(pvertex.z, nvertex.z);
        }
        if (Math::Dot(nvertex - rhs.planes[i].r0, planes[i].normal) < 0.0f) {
            return false;
        }
    }
    return true;
}

```

Also of note is that because I'm using a left-handed co-ordinate system, I wrote my `Cross` function to return the negative of the formula given on Wikipedia.

Any suggestions as to where I've made a mistake?

Edit: I changed my intersection test somewhat. No change, though.

# Answer
Turns out that the plane definitions were wrong. Once I re-ordered the vertices and used the correct ones for each plane, the test functioned exactly as expected. Thanks!
> 0 votes

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


# Question
Title: Storing game objects with generic object information
In a simple game object class, you might have something like this:

```
public abstract class GameObject {

    protected String name;
    // other properties
    protected double x, y;

    public GameObject(String name, double x, double y) {

        // etc
    }

    // setters, getters
}

```

I was thinking, since a lot of game objects (ex. generic monsters) will share the same name, movement speed, attack power, etc, it would be better to have all that information shared between all monsters of the same type.

So I decided to have an abstract class "ObjectData" to hold all this shared information. So whenever I create a generic monster, I would use the same pre-created "ObjectData" for it. Now the above class becomes more like this:

```
public abstract class GameObject {

    protected ObjectData data;
    protected double x, y;

    public GameObject(ObjectData data, double x, double y) {

        // etc
    }

    // setters, getters

    public String getName() {

        return data.getName();
    }
}

```

So to tailor this specifically for a Monster (could be done in a very similar way for Npcs, etc), I would add 2 classes. Monster which extends GameObject, and MonsterData which extends ObjectData. Now I'll have something like this:

```
public class Monster extends GameObject {

    public Monster(MonsterData data, double x, double y) {

        super(data, x, y);
    }
}

```

This is where my design question comes in. Since MonsterData would hold data specific to a generic monster (and would vary with what say NpcData holds), what would be the best way to access this extra information in a system like this? At the moment, since the data variable is of type ObjectData, I'll have to cast data to MonsterData whenever I use it inside the Monster class.

One solution I thought of is this, but this might be bad practice:

```
public class Monster extends GameObject {

    private MonsterData data; // <- this part here

    public Monster(MonsterData data, double x, double y) {

        super(data, x, y);

        this.data = data; // <- this part here
    }
}

```

I've read that for one I should generically avoid overwriting the underlying classes variables.

What do you guys think of this solution? Is it bad practice? Do you have any better solutions? Is the design in general bad? How should I redesign this if it is?

Thanks in advanced for any replies, and sorry about the long question. Hopefully it all makes sense!

# Answer
Separating out data that is shared across instances from data that is unique per-instance is a fairly common approach but which is done in a variety of ways. Many think of that as the Flyweight pattern, where the container becomes less 'heavy' due to effectively outsourcing the shared data.

It starts getting less useful when you begin deriving different types of game object and different types of data though, because you end up trying to store some very different data objects in the base class, which can't make full use of the data (because much of it is specific to the derived class).

As usual with many programming problems, if inheritance is proving a bit awkward, you should just use composition instead. Lumps of data aren't a good match for inheritance because only the methods work equally well on base and derived classes, but you're not really using any methods that apply to both. So, I wouldn't derive MonsterData from ObjectData; I would make MonsterData contain an ObjectData. Then I pass the MonsterData to the Monster constructor, and that constructor passes the ObjectData member to the GameObject constructor via super().

Personally, I have made systems like this before and found them to work well, but often the structure gets in the way of future features - such as when you want to create a monster that is 10% stronger than a normal one, or one with a slightly different title. You sometimes end up migrating things out of the data blocks and into the main class, one by one. Or, you can just abandon this structure, and make complete copies of data from templates instead, knowing that you can change absolutely any part of the object after or during creation if you need. Then you're using something more like the Prototype pattern where new objects are made via copying. This is usually less efficient in memory terms but often more flexible.
> 7 votes

---
Tags: java, data-structure
---


title: More efficient in range checking

text:
# Question
Title: More efficient in range checking
I am going to use a specific example in my question, but overall it is pretty general. I use java and libgdx.

I have a ship that moves through space. In space there is debris that the ship can tractor beam in and and harvest. Debris is stored in a list, and the object contains it own x and y values. So currently there is no way to to find the debris's location without first looking at the debris object. Now at any given time there can be a huge (1000+) amount of debris in space, and I figure that calculating the distance between the ship and every single piece of debris and comparing it to maximum tractor beam length is rather inefficient.

I have thought of dividing space into sectors, and have each sector contain a list of every object in it. This way I could only check nearby sectors. However this essentially doubles memory for the list. (I would reference the same object so it wouldn't double overall. I am not CS major, but I doubt this would be hugely significant.) This also means anytime an object moves it has to calculate which sector it is in, again not a huge problem.

I also don't know if I can use some sort of 2D MAP that uses x and y values as keys. But since I am using float locations this sounds more trouble than its worth.

I am kind of new to programming games, and I imagined there would be some eloquent solution to this issue.

# Answer
> 7 votes
Your idea of dividing the space into sectors is the right way to go. There are a lot of data structures that push this idea very far, and you probably need one of the following:

The idea of these structures is to divide the space recursively. There are many more possibilities, including k-d trees.

Once all your debris are stored in the structure, you need to iterate over all children of the structure; if the whole child is farther than the tractor beam length, skip it; if it isn't, check each of its own children.

# Answer
> 7 votes
Your line of thought about dividing the space into sectors is exactly what you need. There are several different data structures and algorithms that can be used, but for this particular scenario I recommend the one described on the following link - **Spatial Hashing** (which is basically just a *grid*):

Just to clarify, **spatial hashing** works better for worlds where objects are **small** and have roughly the **same size** (so that you can pick a bucket size) and **sparsely distributed** (so that the objects are distributed between a lot of different buckets). From your description that seemed to be the case (debris in space), hence my suggestion.

On the other hand, a **quadtree** (or octree) while more complex, works better than spatial hashing for when objects can have **large size differences** (so that fitting them into the buckets is harder) and are mostly **clustered** together (which means they'd mostly occupy the same buckets). If that happens to be the case, you can find more information on the subject at the end of this answer.

Now, transcribing the essential portions of the article, you divide your world into sectors, or buckets:

And keep a list of objects for each bucket. The article is using a dictionary / hash table to store the buckets, but I don't really see the advantage in his example, since all the buckets are allocated when the game starts, and are referenced by an integer index. I'd say a regular array would do.

Next you need a way to translate one position in the world, into the appropriate bucket index in the array. In the article he uses:

```
int hashid = (int)((Math.Floor(position.X / CellSize)) +
                   (Math.Floor(position.Y / CellSize)) * width);

```

To find which buckets an entity should be placed in, and granted that objects won't be larger than a bucket, do the above for each of the four corners and add the object to the resulting buckets.

Finally, to get close objects, find the bucket you're currently in, and iterate over that and other adjacent buckets if needed.

I've written a few answers related to the broader topic of space partitioning, which like I said, encompasses a lot of different techniques (e.g. quadtree/octree, bsp tree, r-tree, bounding volume hierarchies):

# Answer
> 2 votes
At lower level optimization you can compare distance squared instead of distance. if (range^2 \< distance^2) saves expensive sqrt. If you don't need to compare O(N^2) range checks this might be enough optimization for you. Reading linear data is fast. Doing simple range check (its just sum, dot and compare) is fast as hell you probaly just want simple and efficient code. If N is really large then spatial stuff is once again good choise but then you need to use time coherency too to gain something.

Putting debris to buckets is O(N) too so you dont lose nothing but you gain memory efficiency and simpler code which mean faster devepment and easier debuggin.

You can do this kind of math with linear data (even with mobile devices) around 100k without even noticing the time used, computers are fast with these kind of things.

# Answer
> 0 votes
Assuming this is 2D, you can have a box2d sphere trigger around the ship and corresponding bodies on the debris and check when the bodies collide? If it's 3D, I think the bullet support is now available as well?

---
Tags: java, collision-detection, libgdx
---


title: 2D Tile based Game Collision problem

text:
# Question
Title: 2D Tile based Game Collision problem
I've been trying to program a tile based game, and I'm stuck at the collision detection.

Here is my code (not the best ^^):

```
void checkTile(Character *c, int **map)
{
     int x1,x2,y1,y2;

     /* Character position in the map */
     c->upY     = (c->y)                / TILE_SIZE; // Top left corner
     c->downY   = (c->y + c->h)         / TILE_SIZE; // Bottom left corner
     c->leftX   = (c->x)                / TILE_SIZE; // Top right corner
     c->rightX  = (c->x + c->w)         / TILE_SIZE; // Bottom right corner

     x1         = (c->x + 10)           / TILE_SIZE; // 10px from left side point
     x2         = (c->x + c->w - 10)    / TILE_SIZE; // 10px from right side point
     y1         = (c->y + 10)           / TILE_SIZE; // 10px from top side point
     y2         = (c->y + c->h - 10)    / TILE_SIZE; // 10px from bottom side point

     /* Top */
     if (map[c->upY][x1] > 2 || map[c->upY][x2] > 2)
         c->topCollision = 1;
     else c->topCollision = 0;

     /* Bottom */
     if ((map[c->downY][x1] > 2 || map[c->downY][x2] > 2))
         c->downCollision = 1;
     else c->downCollision = 0;

     /* Left */
     if (map[y1][c->leftX] > 2 || map[y2][c->leftX] > 2)
         c->leftCollision = 1;
     else c->leftCollision = 0;

     /* Right */
     if (map[y1][c->rightX] > 2 || map[y2][c->rightX] > 2)
         c->rightCollision = 1;
     else c->rightCollision = 0;
 }

```

That calculates 8 collision points

My moving function is like that:

```
 void movePlayer(Character *c, int **map)
 {
    if ((c->dirX == LEFT && !c->leftCollision) || (c->dirX == RIGHT && !c->rightCollision))
    c->x += c->vx;

    if ((c->dirY == UP && !c->topCollision) || (c->dirY == DOWN && !c->downCollision))
        c->y += c->vy;

    checkPosition(c, map);
 }

```

and the checkPosition:

```
void checkPosition(Character *c, int **map)
{
checkTile(c, map);

if (c->downCollision) {
    if (c->state != JUMPING) {
        c->vy = 0;
        c->y = (c->downY * TILE_SIZE - c->h);
    }
}

if (c->leftCollision) {
    c->vx = 0;
    c->x = (c->leftX) * TILE_SIZE + TILE_SIZE;
}

if (c->rightCollision) {
    c->vx = 0;
    c->x = c->rightX * TILE_SIZE - c->w;
}
}

```

This works, but sometimes, when the player is landing on ground, right and left collision points become equal to 1. So it's as if there were collision coming from left or right.

Does anyone know why this is doing this?

# Answer
> 0 votes
Got it, once you get the complete problem description it is elemental.

What happens is that the character end up penetrating the ground by more than 10px after landing due to the speed being greater than 10px per frame, thus causing the lower right and left collision checks to hit the ground. You do move the character up again, but you still decide to stop horizontal movement based on a collision check made before this move. You could just insert another `checkTile` in the middle of `checkPosition`.

You should also check before resetting speed to 0 that the character is actually moving in the expected direction, otherwise you can in rare cases get a situation where the character collide with and is halted by an object behind it.

Ain't you supposed to do something about roof collisions in the `checkPosition` code?

---
Tags: collision-detection, tilemap
---


# Question
Title: Making XNA Play Nice With 3DS Max, Boundiing Spheres
I'm using 3DS Max 2010 with the KW x-porter plugin, which outputs a .X file (just downloaded the very latest version).

Been getting some odd results: http://www.picvalley.net/u/2930/2265240220441812321333990933PAStFeSONWQslOrMQC5q.PNG

Looks like the culling is screwed up. Note, that models I make in Milkshape don't seem to be having these problems.

I've also tried to export an FBX file from 3DS Max 2010 and have been getting similar results.

What are your suggestions in terms of exporting \*.3DS models to a workable XNA form? What tools do you use?.

To be clear, the model in question has none of these defects when viewed from similar angles in 3DS Max 2010.

http://www.picvalley.net/u/2563/151728957814855401111333991302mSvEJ03Zv22GwHFgIhiV.PNG

Any ideas on this oddity would also be appreciated!

**Edit 1 -- Add'l issue** Forgot to mention, that the model otherwise seems alright, but that rotation seems to double -- in other words, when I scroll my camera view left to right, the model (whose draw I give the camera for the view and perspective matrices w/ BasicEffect seems to rotate twice as much as models I draw natively in XNA

# Answer
> 2 votes
Looks like you don't have depth testing enabled. Put this code before drawing your model:

```
GraphicsDevice.DepthStencilState = DepthStencilState.Default;

```

---
Tags: xna-4.0, models, 3dsmax, culling, fbx
---