# Question
Title: What is the better approach to redraw a static background scene for game?
Take for an example I have the background scene of a game which should remain static for an interval.Then for every time redrawing the scene,is it better for me to store the color buffer for every pixel on the viewport and redrawing using the stored color buffer or to applying a texture to the whole background or to draw the triangular,quad meshes?

# Answer
**In short:** If you are developing for a modern machine, you usually can redraw everything that should be on the screen, the only exception being images that are difficult to compute/are computed once every few frames because of perfomance hit.

**Detailed:** Try rendering the static parts just like the dynamic. *Premature optimization is the root of all evil*, and you should generally avoid it. Measure the timings, and there's huge chance you won't even need to cache the background at all.

If, however rendering the background is expensive, you should use FBO to store the data. The method of putting it back on the screen *depends on the type of game you're writing*, however textured quad rendered with basic fragment shader shouldn't be too slow compared to direct pixel-copy. It will also allow you to reduce the size of the background, if you feel that storing whole screen is too much.
> 7 votes

# Answer
Assuming you can draw on the buffer effectively and you're using a 'clean' scene (only the stuff you want in the background permanently) to render the initial background, **using the buffer should be a faster way of rendering the composite scene**. This is especially true if the background isn't a simple image file but rather a separate redering. Even if you are just using a bilboard image in the back of the scene, rendering the polygons and textures to the image buffer is much higher up in the graphics pipeline.
> 0 votes

---
Tags: opengl
---


# Question
Title: Recommended method towards making custom maps for a 2d game?
I am planning on making a 2D game, however different from my last personal projects I want this one to have enhanced graphics, with custom-designed levels. My previous 2d platformers were tile-based, in which I made a map editor for to create levels.

However, I am wondering the best way to implement custom designed maps? For say, some grass is a litter higher than others, flowers here and there, cool drawings and structures along the way, etc. instead of just the same old tiles over and over again. I am thinking but I just can't grasp the idea of how to implement it. I have seen it done in other games and am interested to see how they accomplish it, but can't get my hands on some source code. :(

# Answer
> 11 votes
There are many different types of level systems, most of which are customized specifically for a single game. This answer will not cover every implementation detail of these systems, but rather an abstracted explanation of each.

**Tile-based**

Although most tile-based systems are very shallow and are incapable of supporting much detail, it is possible to overcome this. At the core, a tile-based system is a two-dimensional array of cells, each filled with a piece of data that details it's contents.

The first action most designers take to add detail to a tile-based system is to add layers. Layers allow you to have multiple grids of cells stacked on top of each other, giving you the opportunity to add things such as shadows and things that are raised vertically off the ground, such as the crown of a tree or a tall lamp post.

Also, most tile-based systems use tile sets. Tile sets are palettes of data that the level system can use to store tile information. This allows you to more efficiently support a higher number of tiles, because if you need more room, you can just add another tile set.

You can add detail to each tile via metadata. For example, you might have only one "grass" tile. Instead of making new tiles for each height of grass, you can simply add metadata that describes this height.

**Arbitrary Placement Level**

Although a bit more complicated than a tile-based system, an arbitrary placement system gives you free control over the location of objects. Basically, every object in the level is given a position, rotation, and scale. So instead of having a list of cells that contain objects, you now have a list of objects that contain positional data.

Since each object contains it's own set of data, it is possible to store graphical information for each object. For example, instead of using a tile set to store the graphics for each type of tile, each object can now contain unique graphical data, such as the name of an image file.

Because the objects can intersect with each other, you will need to give each tile (along with it's X and Y position) a Z position, which is essentially it's layer. Objects with a higher (or lower, if you choose) Z position are drawn last, so that only the most prominent objects are shown on top, and all background objects are drawn behind these.

Arbitrarily placed objects can also have arbitrary sizes, allowing you to specify a long stretch of grass as one object, instead of have several tiles stored in several cells. Thus, an arbitrary placement system uses less memory than a tile-based system (usually). Also, things other than terrain may be stored in the level data, such as enemy placement, dynamic lights, and events. Although it is possible to make a tile-based system that included these features, it is almost certainly more difficult.

**Conclusion**

As you can see, both tile-based and arbitrary placement systems have their advantages, so it might be hard to choose between them. However, there is no reason you cannot have both. You can make a tile-based system as the base, and store all of your basic terrain in that, and then you can specify an arbitrary placement system on top of that, for adding objects that cannot be represented in a tile-based system.

In the end, the only way to get more detail into a level system is to force it in. Add more layers and tile attributes to your tile-based systems, and overlay an arbitrary placement system on top of that for the fine details.

---
Tags: c++, 2d, game-design
---


# Question
Title: Can i make money with my Android Engine or should I focus on game-making?
I have dedicated past few month to developing my own android 2d engine. You can see its description, demo and tutorials.

While working on the engine I believed it to be better then most available alternatives ( such as andengine, etc. ) and that people would love to use it in their games and, hopefully, would give me some royalties.

Yet as I started posting about my engine on other forums, it start looking like people are only interested in free/opensource engines.

Based on your experience, what do you think, is there some way for me to make money with that engine or should I forget about selling it and more focus on making games with it myself?

# Answer
> 2 votes
In my personal opinion, only cross-platform engines or specialized engines (e.g. a Soft body physics engine) will sell.

Also, I couldn't understand the features of your engine from your website. It looks like a level editor with physics functionality. If it does have more features, you need to have a "Features" section in your website. How does it handle multiple screen resolutions and aspect ratios? What is the minimum Android version supported? Have you developed a full game using the engine?

# Answer
> 1 votes
Look at this Javascript game engine called Impact: http://impactjs.com/. I think that engines in general, if done correctly, will sell.

---
Tags: android
---


# Question
Title: Undeclared Scope in Rock Paper Scissors Simple Game
```
#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;
bool win;
int winnings;
int draws;
int loses;
string comChoice;
string playerChoice;

void winGame () {
cout << "You won! Play again?" <<endl;
cout << "Type y/n" <<endl;
                    char x;
                    cin >> x;
                        if (x == 'y') {
                        beginGame();
                        } else if ('n'){
                        cout << "Game Stopped." <<endl;
                        cout << "Number of Draws: " <<draws << endl;
                        cout << "Number of Loses: " <<loses << endl;
                        cout << "Number of Wins: " << winnings << endl;
                        win = true;
                        }
}

void drawGame (){
    ++draws;
    cout << "Draw! Try again" << endl;
return;
}

void lose () {
cout << "You lose! Try again?" <<endl;
                cout << "Type y/n" <<endl;
                    char feedback;
                    cin >> feedback;
                        if (feedback == 'y') {
                        beginGame();
                        } else if ('n'){
                        cout << "Game Stopped." <<endl;
                        cout << "Number of Draws: " <<draws << endl;
                        cout << "Number of Loses: " <<loses << endl;
                        cout << "Number of Wins: " << winnings << endl;
                        }
}

void beginGame() {
cout << "Welcome to the Rock, Paper and Scissors Game!" <<endl;
    cout << "Let's begin. Type <rock, paper, scissors> for your choice!" <<endl;
    cin >> playerChoice;
    srand(time(0));
    int randomizer = 1+(rand()%3);
        if (randomizer == 1)
        comChoice = "rock";
        if (randomizer == 2)
        comChoice = "paper";
        if (randomizer == 3)
        comChoice = "scissors";

            do {
                if (playerChoice == comChoice) {
                drawGame();
                }

                if (playerChoice == "rock" && comChoice == "paper")
                ++loses;
                lose();

                if (playerChoice == "rock" && comChoice == "scissors")
                ++winnings;
                winGame();

                if (playerChoice == "paper" && comChoice == "rock")
                ++winnings;
                winGame();

                if (playerChoice == "paper" && comChoice == "scissors")
                ++loses;
                lose();

                if (playerChoice == "scissors" && comChoice == "rock")
                ++loses;
                lose();

                if (playerChoice == "scissors" && comChoice == "paper")
                ++winnings;
                winGame();

            }while (win != true);

}

int main () {
beginGame();
return 0;
}

```

# Answer
> 4 votes
Your `winGame` function calls the `beginGame` function which doesn't exists yet. So you need to declare it before even if you write the function later in the code.

Furthermore you don't use braces in your multi-lines conditional statements, so I had to fix that too. And finally I modified the `drawGame` function to avoid infinite loop because of the braces modifications.

```
#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;
bool win;
int winnings;
int draws;
int loses;
string comChoice;
string playerChoice;

void beginGame(); // forward declaration of the missing function

void winGame ()
{
    cout << "You won! Play again?" <<endl;
    cout << "Type y/n" <<endl;
    char x;
    cin >> x;
    if (x == 'y') {
        beginGame();
    } else if ('n') {
        cout << "Game Stopped." <<endl;
        cout << "Number of Draws: " <<draws << endl;
        cout << "Number of Loses: " <<loses << endl;
        cout << "Number of Wins: " << winnings << endl;
        win = true;
    }
}

void drawGame ()
{
    ++draws;
    cout << "Draw! Try again" << endl;
    //return;
    beginGame();
}

void lose ()
{
    cout << "You lose! Try again?" <<endl;
    cout << "Type y/n" <<endl;
    char feedback;
    cin >> feedback;
    if (feedback == 'y') {
        beginGame();
    } else if ('n'){
        cout << "Game Stopped." <<endl;
        cout << "Number of Draws: " <<draws << endl;
        cout << "Number of Loses: " <<loses << endl;
        cout << "Number of Wins: " << winnings << endl;
    }
}

void beginGame()
{
    cout << "Welcome to the Rock, Paper and Scissors Game!" <<endl;
    cout << "Let's begin. Type <rock, paper, scissors> for your choice!" <<endl;
    cin >> playerChoice;
    srand(time(0));
    int randomizer = 1+(rand()%3);
    if (randomizer == 1)
    comChoice = "rock";
    if (randomizer == 2)
    comChoice = "paper";
    if (randomizer == 3)
    comChoice = "scissors";

    do {
        if (playerChoice == comChoice)
        {
            drawGame();
        }

        if (playerChoice == "rock" && comChoice == "paper")
        {
            ++loses;
            lose();
        }

        if (playerChoice == "rock" && comChoice == "scissors")
        {
            ++winnings;
            winGame();
        }

        if (playerChoice == "paper" && comChoice == "rock")
        {
            ++winnings;
            winGame();
        }

        if (playerChoice == "paper" && comChoice == "scissors")
        {
            ++loses;
            lose();
        }

        if (playerChoice == "scissors" && comChoice == "rock")
        {
            ++loses;
            lose();
        }

        if (playerChoice == "scissors" && comChoice == "paper")
        {
            ++winnings;
            winGame();
        }

    } while (win != true);

}

int main ()
{
    beginGame();
    return 0;
}

```

There is still more stuff to fix, but I hope that helps. You should give more consideration to your questions however.

# Answer
> 0 votes
You need to work on how you ask questions, because as it is now, you're not even asking anything.

You probably want to know why the program doesn't compile, and I will tell you this: how would a function know about another function if you didn't tell the program that it exists yet (in C++)?

---
Tags: c++
---


# Question
Title: Algorithm to reduce a bitmap mask to a list of rectangles?
Before I go spend an afternoon writing this myself, I thought I'd ask if there was an implementation already available --even just as a reference. The first image is an example of a bitmap mask that I would like to turn into a list of rectangles. A bad algorithm would return every set pixel as a 1x1 rectangle. A good algorithm would look like the second image, where it returns the coordinates of the orange and red rectangles. The fact that the rectangles overlap don't matter, just that there are only two returned.

To summarize, the ideal result would be these two rectangles (x, y, w, h): `[ { 3, 1, 2, 6 }, { 1, 3, 6, 2 } ]`

# Answer
> 7 votes
I don't know any algorithm for that specific problem, but here's an idea how you could tackle this:

1. Let `X` and `Y` be `0`
2. Search and increment `(X, Y)` in your bitmap and visit each pixel from left to right, from top to bottom until you hit an unvisited foreground pixel.
3. Search from `(X, Y)` to the right, until you hit a background pixel or an already visited pixel. Keep the amount of found pixels as `WIDTH`. Set `HEIGHT` to `1`.
4. Start another search at (`X, Y + HEIGHT)` and search `WIDTH` pixels. If all these pixels belong to the foreground, increase `HEIGHT` by `1`.
5. Repeat step **3** until you hit a background pixel in the search. Then you add the rectangle (formed by `X, Y` and `WIDTH`, `HEIGHT`) to the list of found rectangles and mark all the pixels it encloses as visited.
6. Increment `X` by `WIDTH` and continue your search (go to step **2**). Your search ends when you reached the bottom right pixel of your bitmap.

The algorithm would produce 3 rectangles for your specific example. To get a result with only 2 rectangles, you would have to alter step **3** so that it only stops at a background pixel and ignores already visited pixels. This however would potentially result in a lot of overlapping rectangles. So step **3** could be optimized further by keeping track of unvisited and visited foreground pixels. If the last pixel (before the background pixel) is a visited pixel, use the last unvisited foreground pixel to get the `WIDTH`.

**Update:** I went ahead and implemented the algorithm I proposed. Here's an interactive demo where you can try it yourself (click "Play flash full screen", if the display is too small).

Controls: Click and drag in the black area to draw pixels. Hold `Shift` and draw to erase. Double-click to clear the canvas.

Here's the full source of the flash demo.

# Answer
> 3 votes
This problem is underspecified. Because you've provided a single, simplistic example, you have missed some of the important logical possibilities and corner cases here (or, you just haven't explicitly excluded them). For instance, since you don't mention the proposed application for this, you haven't specified what is more important: Breaking up the entire map into exclusive rectangles that have as large *an area* as possible (the Packing Problem, which has an arbitrary number of solutions), or simply getting edge-matched rectangles in each of x and y, as you seem to imply above. I assume the latter.

Consider the case where you fill in each of the 4 tiles that sit immediately in the corners of the "plus-sign"-shaped bitmask you've drawn above (\[2, 2\] being the topmost). Now what are the optimal rectangles? Considering just columns, Would you prefer narrower, longer rects with slimmer ones to the sides, or the large, broader square which could now be found in the middle of the image, with squat squares above and below?

Anyway, assuming longest-possible edge-matched rects, take this as a first-attempt solution:

* Break the bitmask down into columns. Each column starts at some value y0 and ends at some other value y1. Store each column as a (y0, y1) tuple in a list.
* Columns: Evaluate the list. Find where adjacent tuples have the same y0 AND y1 between them (eg. column A starts at y0=1 and ends at y1=4; so does column B). For as long as each consecutive column DOES have these the same, increment the width of a rectangle you have created to represent these, by one. As soon as they DO NOT, end this rectangle and store it, and create a new one for any subsequent column groups.

Repeat both of the above steps for rows, exactly as for columns (using x0 and x1 instead, and a separate list, of course).

You should now have some lists of cleanly-edged rectangles. They may however not be optimal for your application; if this is the case, you will need a system of heuristics that enables more efficient packing. See the Packing Problem for more.

---
Tags: 2d, algorithm, sprites
---


title: How to cull liquids

text:
# Question
Title: How to cull liquids
I use culling on my Tiles in my 2D Platformer (XNA), so only ones needed are drawn on screen. Thats easy to do.

However, My Liquid tiles (Water, lava, etc) require an Update Method aswell as the normal Draw, which does checks against tiles, makes it flow, etc.

So how should I cull liquid updates in my game? Not culling is to slow, culling only on screen looks awkward when you move.

What do you think would be best for the player? Maybe someway of culling the visible tiles PLUS also adding the width/height of the viewport to start culling tiles at a fast enough rate in front of the player so it dosent look awkward when moving? (Not sure how to do this though, something with MaxSpeed of player and width of screen)

# Answer
> 4 votes
Generally, you *should not* “cull” physics updates in your game with respect to the screen, except perhaps to a very limited extent — things not moving when they are off-screen is now seen as archaic. What you need to do instead is make the updates more efficient.

You state that you have tile-based liquids. I assume they are flowing around by checking their neighbor tiles and converting those into liquid tiles, or other similar local rules. Here is a technique for optimizing such updates which saves time when most of your liquids are stationary, but the environment will sometimes change to allow it to flow.

* Have a set/list of “currently moving liquids” — this is a list of tile positions.
* Whenever *any* tile changes its state in a way that might affect liquids, check if it or its neighbors are liquid; for any tile that is, put it on the list of moving liquids.
* When you update the level,

1. Save the current “moving liquids” list aside, and clear the original list.
    2. For each tile in the saved list, perform its update. If the liquid flows, then that update will of course cause one or more tiles to be added to the just-cleared list for further processing next frame.

That's it! In this way, no CPU time is spent on liquid that is not moving.

(If you have levels where the liquid starts flowing as soon as it is loaded, then you need only make sure it gets onto the list; you can do this either by putting *every* liquid tile on the list as the level is loaded, or by having a premade list of initially-flowing-water tiles.)

---
Tags: 2d, tiles, platformer, culling, user-experience
---


title: Simple game in Android

text:
# Question
Title: Simple game in Android
In `C#` is there something like XNA which gives `update` or `draw` or other classes and methods for operating on vectors and matrices that works for Android? I want to make a very simple 2D game for Android, and I don't want to have to use Unity.

# Answer
Try ExEn or MonoGame. They both implement the XNA API on top of Mono for Android.
> 1 votes

# Answer
Your best bet is to look up Android game engines. There are some free ones out there, a quick google search should help.
> 0 votes

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


# Question
Title: Estimate angle to launch missile, maths question
I've been working on this for an hour or two now and my maths really isn't my strong suit which is definitely not a good thing for a game programmer but that shouldn't stop me enjoying a hobby surely?

After a few failed attempts I was hoping someone else out there could help so here's the situation.

I'm trying to implement a bit of faked intelligence when the A.I fires it's missiles at a target in a 2D game world. By predicting the likely position the target will be in given it's current velocity and the time it will take the missile to reach it's target. I created an image to demonstrate my thinking: https://i.stack.imgur.com/WCd0U.png which also contains the logic I use for accelerating the missile after launch.

The ship that fires the missile can fire within a total of 40 degree angle, 20 either side of itself, but this could likely become variable.

My current attempt was to break the space between the two lines into segments which match the targets width. Then calculate the time it would take the missile to get to that location using the formula. So for each iteration of this we total up the values and that tells us the distance travelled, ad it would then just need compared to distance to the segment.

```
startVelocity * ((startVelocity * acceleration)^(currentframe-1)

```

So for example. If we start at a velocity of 1f/frame with an acceleration of 0.1f the formula, at frame 4, would be

```
1 * (1.1^3) = 1.331

```

But I quickly realized I was getting lost when trying to put this into practice.

Does this seem like a correct starting point or am I going completely the wrong way about it?

Any pointers would help me greatly. Maths really isn't my strong suit so I get easily lost in these matters and don't even really know a good phrase to search for with this.

So I guess in summary my question is more about the correct way to approach this problem and any additional code samples on top of that would be great but I'm not averse to working out the complete code from helpful pointers.

# Answer
I'll start off by saying: you're not going to be the very best in game programming if you don't have a strong grasp of mathematics. Even so, math should not prevent you from becoming a good game programmer, as there are many ways of avoiding math, such as using a specialized library or just getting a friend to help you program calculations.

*Now, as for the real question:*

First, given the starting position, velocity, and acceleration of the target, it is possible to find the **distance from the ship to the target** as a function of time.

Second, you also know the starting position, velocity, and acceleration of the missile, so you can also find the **distance from the ship to it's missile** as a function of time.

Now that you have a function representing the distance from **ship to target** and from **ship to missile**, all you have to do is find out when these two distances are equal. This will give you the **time at which the missile hits the target**.

Once you have this time, calculate where the target will be at this time and target that location.

**EASY MODE:**

Given the very complex nature of this system, and the fact that you really only need an approximation, you do not actually need to solve this complex equation. Instead, you can guess the time like this:

`time = targetDistance / missileVelocity`

And then

`targetPosition += targetVelocity * time`

Where `targetPosition` and `targetVelocity` are vectors in your choice of dimensions.

(obviously these variables are local only, you shouldn't be modifying the actual position of the target here)

Once you have done this, the `targetPosition` should be somewhat further in from of where it started. Now **calculate the time it would take for the missile to hit this new point**, and calculate **where the ship will be at this new time** (starting from the original position). **The second time you do this, the change in position should be much smaller than the first.** Simply repeat this process until the change in distance is below a certain threshold, or until you have looped through it enough times. The final result should be very close to the "perfect" spot, and it's much more efficient than doing all the math above.

Basically, the idea here is that you can avoid all of the really complicated math by performing a short series of educated guesses, and the result is almost the same.
> 2 votes

# Answer
The problem here is that you have an accelerating missile--the simple math doesn't work.

A simplistic answer is that the position of the missile is 1/2 * acceleration * time * time. (This is evident if you understand calculus, it's hard to follow otherwise.) However, this won't produce the right answer because in reality your missile is accelerating in a jerky fashion (an update each frame), not smoothly.

It may be good enough, if it's not I would simply precalculate the missile's performance and refer to the stored results when you need them.
> 0 votes

---
Tags: mathematics, xna-4.0
---


# Question
Title: How to port animation from one skeleton to another?
While I need to do this in a Blender3D modeler script, the math should be similar for other modelers or realtime engines.

Blender3D specific terminology:
Armature = skeleton
EditBone = rest pose bone (stores the rest pose matrix)
PoseBone = can store a different pose (animation matrix) for each frame of your animation

I need to share animations (Blender Actions) between Armatures which have EditBones with same names and which have the same positions, but can have different (rest pose) angles and scales. Plus the Armatures might have different bone hierarchy (bone parenting/ no bone parenting).

Why I need this:
I've made an importer/exporter for a 3d format for a game. The format doesn't store enough info to connect/parent the bones, which makes posing/animating character models in a 3d modeller nearly impossible (original model files for the 3d modeler don't exist, this is for modding).
As there are only 2 character skeleton types in the game, I decided to optionally allow to generate the bone from a hardcoded data in the model importer and undo that in the exporter. This allows to easily pose the model for checking weights, easily create weights, makes it easier for Blender to generate automatic weights and of course makes animating possible.

This worked perfectly: the importer optionally generated the Armature itself and the exporter removed those changes, so the exported model works with existing animations in the game. But now I'm writing an importer and exporter for the game's animation format and here come the problems of:

1. Trying to make original animations work in Blender with my "custom" (modified) Armature
2. Trying to make animations created by using the "custom" (modified) Armature work with the original models in the game (and Blender).

Constraints or bone snapping inside Blender won't work as they don't care that the bones have different angles in the rest pose, they will still face the same direction.

It seems I just need to get the "difference" between the EditBone matrices of all EditBones for the two Armatures somehow and apply that difference to PoseBone matrices of all PoseBones, for all frames of my animation. I need to know how to get that difference and how to apply it.

BTW, PoseBone matrices are relative to rest pose, they are by default

```
[1.000000, 0.000000, 0.000000, 0.000000](matrix [row 0])
[0.000000, 1.000000, 0.000000, 0.000000](matrix [row 1])
[0.000000, 0.000000, 1.000000, 0.000000](matrix [row 2])
[0.000000, 0.000000, 0.000000, 1.000000](matrix [row 3])

```

So the question is: How to get the difference between two bone (EditBone) matrices to apply that difference to the animation matrices (PoseBone matrices)?

Please be easy on the matrix math.

# Answer
You don't mention how your source animation data is constructed, so I'm going to have to be a bit vague about the details.

From your input data you should be able to construct both the bind pose and animated pose matrices for each bone in two different coordinate spaces: world space (absolute position and orientation for the bone relative to the world origin), and local space (position and orientation relative to the coordinate space given by the parent bone).

Going from local space to world space is just a matter of concatenating the local matrix for a bone with its parent's world matrix (which can be computed the same way, recursively). A root bone's local and world matrices are identical.

`bone.world_matrix = bone.local_matrix * bone.parent.world_matrix`

Going the other way, from world space into local space, you concatenate the bone's world matrix with the inverse of the parent's world matrix:

`bone.local_matrix = bone.world_matrix * bone.parent.world_matrix.inverted()`

The pose bone matrix\_basis is computed from the difference between the bind pose and the animated pose:

`matrix_basis = bind_pose_matrix.inverted() * animated_bone_matrix`

As you mentioned, Blender stores animations relative to the bind pose (in the pose bone matrix\_basis). Both the edit bone and pose bone matrices are in local space in Blender. If your bones are all "flat" and not in a hierarchy you don't have to worry about this step, since then all matrices are in world space.

Let's assume you have two armatures, A and B, with different bind poses but otherwise compatible skeletons (same bone lengths and hierarchy, etc). You also have an animation X, given for armature A. Now you want to transfer poses from animation X onto armature B. The easiest way is to take the final position of each bone in armature A and use that exact same position for the corresponding bone in armature B.

Compute the world space matrices for each bone in armature A (you may have this from your input format already):

`a.world_matrix = a.local_matrix * a.parent.world_matrix`

Then pretend that these matrixes belong to armature B instead. Compute new local space matrices for armature B. These steps are important, since you can't reuse armature A's local matrices for armature B, if the hierarchies differ, but the absolute matrices should still be okay.

`b.local_matrix = a.world_matrix * b.parent.world_matrix.inverted()`

Now you can compute a new matrix\_basis for each bone in armature B by comparing the local space bone matrix in its animated pose to the bind pose:

`pose_bone_b.matrix_basis = edit_bone_b.matrix.inverted() * b.local_matrix`.
> 1 votes

# Answer
I just tested the above answerer's solution and it works, but only if your new Armature doesn't have a bone hierarchy (parent/child bones).

Here's how exactly to do it in Blender (2.49):

```
matrix_basis = old_armature.bones[bone_name].copy().invert() * old_animation_matrix # old_animation_matrix should be the one from the file
new_animation_matrix = new_armature.bones[bone_name].matrix['ARMATURESPACE'].copy() * matrix_basis
pose.bones[bonename].localMatrix = new_animation_matrix * new_armature.bones[bonename].matrix['ARMATURESPACE'].copy().invert()

```

But if you do this for an Armature which has parent/child bones, then animations will screw up as assigning animations to parent bone will make the child bones transform as well.

There must be a solution for that case as well.
> 0 votes

---
Tags: animation, matrix, blender, skeletal-animation, rigging
---


# Question
Title: How to prioritize related game entity components?
I want to make a game where you have to run over a bunch of zombies with your car. When moving around, the zombies have a few things to take into consideration:

* When there's no player around they might just roam about randomly. And even when some other component dictates a specific direction, they should wobble to the left and right randomly (like drunk people). This implies a small, random, deviation in their movement.
* They should avoid static obstacles. When they see they are headed towards a wall, they should reorient themselves.
* They should avoid the car. They should try to predict where the car will be based on its velocity and try to move out of the way.
* When they can, they should try to get near the player.

All these types of decisions they have to do seem like they should be implemented in different components. But how should I manage them? How can I give different components different weights that reflect the importance of each decision (in a given situation)?

I would need some other component that acts as a manager, but do you have any tips on how I should implement it? Or maybe there's a better solution?...

# Answer
> 1 votes
First of all, you need to separate the AI and the actions the creature can take. The "wobbliness" you desire can be implemented in a `MoveForward` function, relieving the AI from having to worry about it.

Secondly, I recommend a `behavior-based` AI. You keep a list of behaviors, probably subclasses of a `BaseBehavior` object, sorted in the order of importance. In your case, it'd probably be something like the following:

* Kill player
* Avoid car
* Avoid wall
* Move towards player
* Wander

Each behavior would have a function called `WantsActive`, which would return `true` if the behavior needed to be used. (For example, `KillPlayerBehavior` would only return `true` when the player was in range.) Every time `Update` is called, you loop through the list of behaviors, calling `WantsActive` on each and stopping when one returns `true.`

This one would have its `Execute` function called, resulting in the creature performing that behavior. If you wanted it to be able to perform multiple behaviors in one frame, you could even check the return value of `Execute`, with `true` meaning "no more actions" and `false` meaning "continue with next behavior." When the manager got `false` in this case, it'd just resume the `WantsActive` loop where it left off.

This approach is nicely object-oriented, it avoids hard-coding behaviors within the `Creature` class, and it is very easily extendable with new behavior classes, even at runtime. The same manager can work with any number of different behavior combinations.

You might want to Google subsumption architecture.

# Answer
> 1 votes
This is a very simplistic finite-state machine solution (ZombieBrainModule.Update() specifically) set up in a components-based style, but it should get you on the right track. Note that I use the word "module" and not "component" below so as to avoid confusion with Unity's built-in components, which as gajet suggested, are not needed.

```
using UnityEngine;

//drop this on each zombie-representative GameObject in the Unity IDE
public class ZombieController : MonoBehaviour
{
    ZombieBrainModule ai;
    LifeModule life;
    WeaponModule weapon;
    //etc.

    void Start()
    {
        ai = new ZombieBrainModule(this.transform, life, weapon);
    }

    void Update()
    {
        ai.Update(); //think about what I, Zombie, intend to do (in this case, motion + weapon actions) and store these
        life.Update(); //eg. for regeneration?
        //etc.
    }

}

public abstract class Module
{
    public abstract void Update();
}

using UnityEngine;

public class ZombieBrainModule
{
    private LifeModule life;
    private WeaponModule weapon;

    public ZombieBrainModule(this.transform, life, weapon);
    {
        this.life = life;
        this.weapon = weapon;
        this.transform = transform;
    }

    public void Update()
    {
        //Pseudocode; a very simplistic finite state machine.

        if near a wall
            avoid nearest wall;
        else
            if player nearby
                if player in car
                    run away from player;
                else
                    if life.remaining > 25% //clever zombie!
                        go toward player;
                        if player within firing range
                            weapon.fire;
                    else
                        run away from player;
            else
                wander;
    }
    //to keep things simple, I avoided heavy class hierarchies, but you could easily use a base Entity class which holds refs to the various modules, from which Zombie and Player would derive.

```

**Note** This excludes the zombie from avoiding walls when he is doing something else. If you want wall avoidance to also happen whilst the zombie is avoiding the player or chasing them, you will need to take some sort of an average of the two vector directions the zombie is being pulled toward. For instance, you might aim for a total float weighting of 1.0f, so you apply your wall avoidance weighted as 0.3f of that, and your player seek (or avoid) as 0.7f of that. After normalising the influence vectors (call 'em `wallInfluence` and `playerInfluence`), multiply each respective one by it's fractional weight, then sum the two vectors for the final motion vector by which you will update your zombie's `transform.position`. Some of these influence weights may vary continuously based on other factors, eg. proximity to the player or his one-and-a-half tons of roaring 70's muscle car.

---
Tags: unity, ai, movement, component-based
---


# Question
Title: How to create reproducible probability in map generation?
So for my game, I'm using perlin noise to generate regions of my map (water/land, forest/grass) but I'd also like to create some probability based generation too. For instance:

```
if(nextInt(10) > 2 && tile.adjacentTo(Type.WATER))
    tile.setType(Type.SAND);

```

This works fine, and is even reproduceable (based on a common seed) if the nextInt() calls are always in the same order. The issue is that in my game, the world is generated on demand, based on the player's location. This means, that if I explore the map differently, and the chunks of the map are generated in a different order, the randomness is no longer consistent.

How can I get this sort of randomness to be consistent, independent of call order?

Thanks in advance :)

# Answer
> 4 votes
This is simple, create a `new Random()` object for each chunk, using that chunk's position as the seed.

If you think of `Random` as a really (really) long series of numbers, the seed is just where to start iterating through. So, if you always set the seed before generating the chunk, you'll always get the same integers, in the same order.

**EDIT**

> But how do you ensure that each chunk gets a unique seed?

It's not too critical to get a unique seed for each chunk, unless you want to try to guarantee that each chunk is unique from the last. I say try because even if each seed is unique it doesn't necessarily guarantee the random numbers you get will be different. If your world has a maximum size, you can get a unique `long` from each position in the world with a method like this:

```
public long positionToLong(int x, int y, int z, int maxY, int maxZ) {
    return (x * (MaxZ * maxY)) + (y * maxZ) + z;
}

```

If it doesn't have a maximum size, you can use some algorithm like:

```
public long positionToLong(int x, int y, int z) {
    return x + y + z + (x*x) + (y*y) + (z*z);
}

```

Then you can do additional things to strive for unique seeds, like add the distance from the center of the world.

I should mention how I do this in my game. Since I'm generating terrain shape along with terrain type, I wanted to ensure that I'd have continuity between chunks. I did that by using a single world seed. Then the Perlin noise function takes the absolute world position as an input. This makes the transition between chunks seemless, which will not be the case if you're randomly generating each chunk distinct from the others.

# Answer
> 1 votes
I'm not sure if there's any commonly practiced method of accomplishing this, but here's what I usually do for things like this:

Since you are already using a Perlin noise function, you can simply use Perlin noise to get the seed for each chunk. Whenever you need to generate a new chunk, simply feed that chunk's coordinates into the Perlin function, and use the returned value as the seed for that chunk. This means you'll need to reseed your random number generator every time a chunk is generated, or you can simply create a new instance of the generator if it's a class.

Essentially, whenever I need to generate consistent data in arbitrary positions, I use a Perlin noise function because it's reasonably fast and consistent.

---
Tags: java, procedural-generation, random
---


title: Scaling window contents in Pyglet?

text:
# Question
Title: Scaling window contents in Pyglet?
I'm trying to scale a window's contents so that every pixel displays at a multiple of it's normal size. Basically I want to achieve larger pixels without scaling each and every individual sprite. This question is very similar to this one, however that only scales a single sprite. How should I go about this?

# Answer
> 1 votes
Ended up figuring out the answer myself through trial and error, solution follows.

You need to import openGL to get access to the scaling function:

```
from pyglet.gl import *

```

Next, toss in the following code after your game's window has been initialized:

```
#These arguments are x, y and z respectively. This scales your window.
glScalef(2.0, 2.0, 2.0)

```

At this point your resolution will double, but your window will stay the same size. You can correct this easily by doubling your window's width and height. Furthermore, your textures will appear blurry, so we need to fix that. We need to set parameters for the textures in your on\_draw() function:

```
def on_draw(self):
        self.clear() #clears the screen
        #The following two lines will change how textures are scaled.
        glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST)
        glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST)
        self.label.draw() #blits the label to the screen

```

You should now have pixels displaying at double their original size.

---
Tags: python, pyglet
---


# Question
Title: How to perform efficient 2D picking in HTML5?
I'm currently using an R-Tree for both picking and collision testing. Each entity on screen has a bounding box for collisions and a separate one for picking. Since entities may change position very frequently, both trees must be updated/reordered once per frame.

While this is very efficient for collisions, because the tree is used in hundreds of collision queries every frame, I'm finding it too costly for picking, because it only gets queried when the user clicks, thus leading to a lot of wasted tree updates.

What would be a more efficient way to implement picking without as much overhead?

# Answer
> 2 votes
As Steven Stadnicki suggested in his comment, and what is also suggested in a related question over at stackoverflow, just do a linear search without any hierarchy.

---
Tags: 2d, javascript, html5, picking
---


# Question
Title: Better way to go up/down slope based on yaw?
Alright, so I got a bit of movement code and I'm thinking I'm going to need to manually input when to go up/down a slope. All I got to work with is the slope's normal, and vector, and My current and previous position, and my yaw.

Is there a better way to rotate whether I go up or down the slope based on my yaw?

```
Vector3f move = new Vector3f(0,0,0);
move.x = (float)-Math.toDegrees(Math.cos(Math.toRadians(yaw)));
move.z = (float)-Math.toDegrees(Math.sin(Math.toRadians(yaw)));
move.normalise();

        if(move.z < 0 && slopeNormal.z > 0 || move.z > 0 && slopeNormal.z < 0){
            if(move.x < 0 && slopeNormal.x > 0 || move.x > 0 && slopeNormal.x < 0){
                move.y += slopeVec.y;
            }
        }

        if(move.z > 0 && slopeNormal.z > 0 || move.z < 0 && slopeNormal.z < 0){
            if(move.x > 0 && slopeNormal.x > 0 || move.x < 0 && slopeNormal.x < 0){
                move.y -= slopeVec.y;
            }
        }

        move.scale(movementSpeed * delta);
        Vector3f.add(pos, move, pos);

```

# Answer
> 1 votes
According to your current code, both the x- and the z-component of my movement need to be pointing up the slope for me to start climbing. Consider a slope with the normal (0,1,-1) normalised, and my horizontal motion (0,0,1). I would not pass the conditions in the x-direction, even though I'm going straight up the hill. I doubt that's what you're trying to accomplish.

The dot product will tell you whether you're going up or down and by how much:

```
horizontaldotproduct = move.x * slopeNormal.x + move.z * slopeNormal.z;
move.y = -horizontaldotproduct / slopeNormal.y;

```

The movement vector will now point along the surface, but leaves the x- and z-components alone. You may want to resize the vector to maintain absolute speed or compensate for gravity etc.

This method is anisotropic. It uses some shortcuts based on what is horizontal and what is vertical. As a result, it requires your terrain does not have vertical or overhanging surfaces and is quite limited in true 3D situations, such as bouncing from or rolling off surfaces.

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


# Question
Title: What fluid simulation system is used in iPhone games?
Does anybody know what kind of system developers are using for fluid simulation in iPhone games? It doesn't seem like they're using a Navier-Strokes simulation to me.

# Answer
Check out the blog: http://mediocregames.wordpress.com/

Posts like this might help you: http://mediocregames.wordpress.com/2011/09/08/getting-the-water-flowing/

They are the makers of Sprinkle: http://itunes.apple.com/us/app/sprinkle-water-splashing-fire/id447791438?mt=8 https://play.google.com/store/apps/details?id=com.mediocre.sprinkle&hl=en
> 2 votes

# Answer
My game is 2D so I'm using a particle emitter to get a water effect.

If you're looking at using a 3d engine see:

http://benbritten.com/2009/05/19/fun-with-unity/

The particle emitter I'm using can be found on 71squared.

Also see:

Top down water view, cocos2d
> 2 votes

---
Tags: iphone, physics, water
---


# Question
Title: What is an acceptable GC frequency for a SlimDX/Windows/.NET game?
I understand that the Windows GC is much better than the Xbox/WP7 GC, being that it's generational and multithreaded -- so I don't need to worry quite as much about avoiding memory allocation.

SlimDX even has some unavoidable functions that generate some amount of garbage (specifically, MapSubresource creates DataBoxes), yet people don't seem to be too upset about it.

I'd like to use some functional paradigms to write my code too, which also means creating objects like closures and monads.

I know premature optimization isn't a good thing, but are there rules of thumb or metrics that I can follow to know whether I need to cut down on allocations? Is, say, one gen 0 GC per frame too much?

One thing that has me stumped is object promotions. Gen 0 GCs will supposedly finish within a millisecond or two, but if I'm understanding correctly, it's the gen 1 and 2 promotions that start to hurt. I'm not too sure how I can predict/prevent these.

# Answer
> 3 votes
The desktop GC implementations in .NET are somewhat less deterministic than the implementations on the Xbox, so even if there were any rules of thumb that specified particular numbers of collections per frame (there aren't, the most likely applicable rule is still "a few as is reasonable") they'd be a little harder to hit.

Your best bet is to program normally -- perhaps a bit conservatively with respect to allocations and GC induction -- and don't spend a whole lot of time worrying about it. If you profile frequently you can determine where bottlenecks start to creep in to your game and address them then. There are plenty of excellent profiling tools for .NET applications, including CLR profiler and WinDBG with SOS.dll (both free, the latter is rather difficult to use though) and ANTS Memory Profiler (non-free, but it's awesome and so are the rest of the Red Gate tools).

You're correct that there are methods in SlimDX that "force" allocations and it hasn't really been a huge deal. It's a tradeoff -- even if SlimDX didn't allocate a heap object (DataBox) in that case, it would still need to allocate a stream object anyway, or some of the memory that backed the stream, otherwise the library would have to either provide a much more difficult-to-use interface to the mapped memory or worse, would have to jump through some extra marshalling hoops that would probably more negatively impact performance more frequently.

However, if you do find a scenario where the heap allocations performed by SlimDX are a performance issue, please file a bug. The developers (I don't work on it any more) would be happy to address it, I'm sure.

> One thing that has me stumped is object promotions. Gen 0 GCs will supposedly finish within a millisecond or two, but if I'm understanding correctly, it's the gen 1 and 2 promotions that start to hurt. I'm not too sure how I can predict/prevent these.

The higher the generation, the more expensive it is. You don't want to predict or avoid the actual collections -- it's usually impractical to try. What you want to do is avoid the scenarios that create undue pressure on the collector and allow the heuristics used by the implementation to do their thing. This means *don't* try to outsmart the collector by forcing a `GC.Collect()` now and then, et cetera. Microsoft has a lot of documentation about the collector and its behavior, this page is a good start. Rico Mariani also writes about GC issues frequently, for example, this is pretty interesting.

---
Tags: .net, memory-efficiency
---


# Question
Title: Will my game engine be compatible with physics engines?
My engine supports scene handling, cameras, and has a renderer. Also, it has a class called `Drawable`, which has the position, the shape and the picture of an object. The picture property has width, height, rotation and a draw method. All game objects are supposed to inherit from this `Drawable` class, and are added to the scene, along with a map (a collection of Tiles, that also inherit from `Drawable`), lights, and so on and so forth.

The shape property of a `Drawable` is a `Polygon`, a collection of user defined vertices around the position of a `Drawable`. This is a relative coordinate system, so `[0, 0]` is the position of the `Drawable`.

With this setup, will the users of my engine (which will *probably* only be me) still be able to integrate physics engines such as Box2DJS into their games?

# Answer
From what I can see there are two ways of doing this.

The first option is to build your engine around the the idea of composition. The idea being that an end users game won't inherit anything you have made, but will hold instances of the relevant classes in objects they want to construct. For example;

```
Enemy
{
    Drawable Draw;
}

```

The other options is to just pick a physics engine that works with your system and add it in. It limits the end uses choice, but you may also find people appreciate it more because you can then change your engine interface to allow for easier creation of complex objects for which a physics engine in necessary.
> 1 votes

---
Tags: physics
---


# Question
Title: How to run around another football player
I have finished a simple 2D one-on-one indoor football Android game. The thing that it seemed so simple to me, a human being, turned out to be difficult for a computer: how to go around the opponent …

At the moment the game logic of the computer player is that if it hits into the human player will step back few points on the pixel greed and then try again to go towards the ball. The problem is if the human player is in-between then the computer player will oscillate in one place, which does not look very nice and the human opponent can use this weakness to control the game. You can see this in the photo – at the moment the computer will go along the red line indefinitely.

I tried few ideas but it proved not easy to do it when both the human player and the ball are constantly moving so at each step computer would change directions and “oscillate” again. Once when the computer player reaches the ball it will kick it with certain amount of random strength and direction towards the human’s goal.

The question here is how to formulate the logic of going around the ever moving human opponent and how to translate it into the co-ordinate system and frame by frame animation… any suggestions welcome.

# Answer
First I will state that A\* sounds like a lot of trouble. It is a pathfinding algorithm, great if you need to find a path, but this is simple obstacle avoidance. A\* also requires recomputation every time the environment state changes, which is every frame in a real time game, or you'll need to use some clever variation that adapts to change.

I don't know how all of your game logic works so it's a little hard to give super-specific advice, but one solution that may be perfectly appropriate is using a potential function, an inverse-square function that calculates a repulsive force based on how close the two agents are to each other. The closer they get, the stronger the repulsive force. It's easy to work with because you don't have to do any high-level path calculation, you just let your agents try to go where they want to go, then calculate the potential force and add it to their movement vectors to displace their movement around obstacles.

The basic equation is (constant / (distanceToObstacle)^2) Compute this and use it to displace your agents' movement vectors opposite the direction to the obstacle. Being an inverse function, the further they are from the obstacle the smaller the force (insignificant beyond a short distance), the closer they get the larger the force, and it grows very quickly so the closer two guys get to each other, the more the repulsive force displaces their movement. You will need to mess around with the constant value and possibly try a cubic function or other exponent instead of square to get the right look. I used this in a space combat game and found inverse square worked well for ship/ship avoidance, as it gave the right effect of looking like the guys were driving around each other to avoid an impact, but for ship/planet avoidance a cubic function was better as I got a close-hugging path without oscillation. One thing that's particularly nice about dist^2 is that it's computationally cheap and often cached anyway for basic collision testing, etc.

I learned the technique from a section in AI For Game Developers. I didn't come up with any great looking resources in a quick search but you can probably find something free with a more complete explanation than mine.
> 5 votes

# Answer
As silly as this may sound, I think you should try using the A\* search algorithm.

The Wikipedia page has quite a nice example:

What you want to do in your game is define a grid of possible locations for the AI player and have the player come up as an area of really high resistance. The algorithm will try to find the shortest route between it and the ball. If a player is in between, it tries to find the shortest route to the ball *around* the obstruction.
> 3 votes

# Answer
The easier solution may be to step a few pixels back and aside *in a random direction*. Not only will this typically solve your problem, but the unpredictability of the behavior is harder for the human player to counter or exploit.
> 2 votes

# Answer
My first instinct would be this:

Draw a line between the human and the computer players, get the angle of this.

decide whether you're going to circle above or below (random? whether your y is above his?)

Add/subtract say 15 degrees from this angle depending on which direction you want to go

Using the human player as the origin draw a line in this new direction (either the same length as the original line or some minimum?)

find the coordinates of the other end of the line

move towards there

repeat every few frames

no idea how well this would actually work though
> 1 votes

---
Tags: java, game-design
---


# Question
Title: How can I better implement A star algorithm with a very large set of nodes?
I'm making a game with nodejs in which many enemies must converge on the player as the player moves around a relatively open space (right now it is an open field with few obstacles, but eventually there may be some small buildings in the field with 1 or 2 rooms). It's a multiplayer game using websockets, so the server needs to keep track of enemies and players.

I found this javascript A\* library which I've modified to be used on the server as a nodejs module. The library utilizes a Binary Heap to track the nodes for the algorithm, so it should be pretty fast (and indeed, with a small grid, say 100x100 it is lightning fast).

The problem is that my game is not really tile-based. As the player moves around the map, he is moving on a more or less 1-to-1 per-pixel coordinate system (the player can move in 8 directions, 1 or 2 pixels at a time).

In preliminary tests, on an 800x600 field, the path-finding can take anywhere from 400 to 1000 ms. Multiply that by 10 enemies and the game starts to get pretty choppy.

I have already set it up so that each enemy will only do a path-finding call once per second or even as slow as once every 2 seconds (they have to keep updating their path because the players can move freely). But even with this long interval, there are noticeable lag spikes or chops every couple of seconds as the enemies update their paths.

I'm willing to approach the problem of path-finding differently, if there's another option. I'm assuming that the real problem is the enormous grid (800x600). It also occurs to me that maybe the large arrays are to blame, as I've read that V8 has trouble with large arrays.

# Answer
Each pixel doesn't have to be its own node in your navigation mesh/graph. You should be able to subdivide areas by sections, and each section becomes a node in the graph for the A\* algorithm. This leaves you with far fewer nodes and much faster searches, however you do have to calculate how to move through these nodes naturally with AI, as you won't just want to walk from node center point to node center point.

Here's a decent paper explaining how navmeshes can help solve issues like you're talking about: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html
> 9 votes

# Answer
Here is another good resource, how A\* search was used in Left 4 Dead (A popular game by Valve). It contains some overlap with Nic's answer, but is still interesting.

http://www.valvesoftware.com/publications/2009/ai\_systems\_of\_l4d\_mike\_booth.pdf
> 3 votes

---
Tags: path-finding, node.js
---


title: Convert a .fbx to a .x model

text:
# Question
Title: Convert a .fbx to a .x model
I'm trying to convert a .fbx model to a .x for use in my DirectX 9 project. Does anyone know of any software to allow me to do this?

Been googling for a few days and not really found anything that has allowed me to do this.

# Answer
> 1 votes
Blender can import .fbx files and output .x files.

---
Tags: directx9, fbx
---


title: JigLibX collision detection only once

text:
# Question
Title: JigLibX collision detection only once
I'm trying to implement collision detection using the latest JiglibX. I am working off of this example. I chose creating a callback. I'm trying to detect a collision only once. When the object falls through, the callback is invoked multiple times, not only once. Is there any way how to ignore other calls? Thanks for advice.

# Answer
> 1 votes
What you need is to create a system to manage this for you. I have a list of bodies that each body is colliding with at any given time, I build this list based on the events I receive from JigLibX. At the end of each physics simulation step I update the list. Any new entries in the list that weren't there during the last step are new collisions, and I will send out an event for each of those that I find. Any collisions that were there during the last step that aren't there now are collisions that have ended, and I send out an event for all of those. And any collisions that I receive that were already in the list I do nothing for. Here's a visualization

```
Simulation Step #      Collision pairs
1                      1<->2, 1<->3, 2<->4
2                      1<->3, 2<->4, 2<->5

```

My list for collisions is currently empty before step 1. After step one my list looks like:

```
Body    Collisions with
1       2, 3
2       1, 4
3       1
4       2

```

After simulation step 2, my list looks like this:

```
Body    Collisions with
1       3
2       4, 5 (new)
3       1
4       2
5       2 (new)

```

You can see here we have a collision in the above list that is new (2\<-\>5), I would send out events for that collision. There is also a collision from the first list that is no longer in the list after step 2, and that is 1\<-\>2, which I would send out events for as well.

Using a system like I've described above means that you only have to receive a collision event when a new collision occurs, or when a collision ends.

You can see this system implemented in the QuickStart Game Engine, which uses XNA with JigLibX, it's a free download.

I don't know of any way to make JigLibX not send collision events each frame. Each physics engine I've used did this every frame (simulation step).

---
Tags: c#, collision-detection, xna-4.0, jiglibx
---


title: FreeType2 Crash on FT_Init_FreeType

text:
# Question
Title: FreeType2 Crash on FT_Init_FreeType
I'm currently trying to learn how to use the FreeType2 library for drawing fonts with OpenGL. However, when I start the program it immediately crashes with the following error: "(Can't correctly start the application (0xc000007b))"

Commenting the FT\_Init\_FreeType removes the error and my game starts just fine. I'm wondering if it's my code or has something to do with loading the dll file.

My code:

```
#include "SpaceGame.h"
#include <ft2build.h>
#include FT_FREETYPE_H

//Freetype test
FT_Library library;

Game::Game(int Width, int Height)
{

    //Freetype
    FT_Error error = FT_Init_FreeType(&library);
    if(error)
    {
        cout << "Error occured during FT initialisation" << endl;
    }

```

And my current use of the FreeType2 files. Inside my bin folder (where debug .exe is located) is: freetype6.dll, libfreetype.dll.a, libfreetype-6.dll. In Code::Blocks, I've linked to the lib and include folder of the FreeType 2.3.5.1 version. And included a compiler flag: -lfreetype

My program starts perfectly fine if I comment out the FT\_Init function which means the includes, and library files should be fine.

I can't find a solution to my problem and google isn't helping me so any help would be greatly appreciated.

# Answer
> 0 votes
I don't see any problems with your code.

There's a few approaches I'd take to fix this problem. First, and easiest - print out the value of "error". Then figure out what that error code means. That may give you a very strong hint.

Next, assuming you're on Windows and you're still thinking it may be a dll error, grab Process Explorer. Turn it on, filter it to your application, and use that to ensure that it's finding and reading the dll. If it's not reading your dll, or it's reading some different and incompatible dll located somewhere else, then that gives you a good hint for where to focus your efforts.

After that, well, libfreetype is open-source. Grab it and start adding debug instrumentation to it. A good starting point is to look for the error code that you found in the first step and see what returns that error - that may make the problem obvious.

Finally, make a new minimal project that does nothing but initialize Freetype. If that doesn't work, it's not your code, it's the installation. If that does work, then put initialization lines in your code to figure out when the initialization *stops* working.

# Answer
> 0 votes
If you're looking for a quick fix, try this library: freetype-gl

But if you want to do it on your own (which I can understand, because I'm building my own font library too), try compiling Freetype from source and linking against that. That way you *know* it can't be because of incompatible library versions or CRT's. Bonus: you can debug *inside* the library.

Other than that, I can't help you much further. Freetype 2.3.5 works fine for me in Visual Studio 2008.

---
Tags: opengl, rendering, sdl, text
---


title: Ray Picking Problems

text:
# Question
Title: Ray Picking Problems
I've read so many answers on here about how to do Ray Picking, that I thought I had the idea of it down. But when I try to implement it in my game, I get garbage.

I'm working with LWJGL.

Here's the code:

```
public static Ray getPick(int mouseX, int mouseY){
    glPushMatrix();

    //Setting up the Mouse Clip
    Vector4f mouseClip = new Vector4f((float)mouseX * 2 / 960f - 1, 1 - (float)mouseY * 2 / 640f ,0 ,1);

    //Loading Matrices
    FloatBuffer modMatrix = BufferUtils.createFloatBuffer(16);
    FloatBuffer projMatrix = BufferUtils.createFloatBuffer(16);
    glGetFloat(GL_MODELVIEW_MATRIX, modMatrix);
    glGetFloat(GL_PROJECTION_MATRIX, projMatrix);

    //Assigning Matrices
    Matrix4f proj = new Matrix4f();
    Matrix4f model = new Matrix4f();
    model.load(modMatrix);
    proj.load(projMatrix);

    //Multiplying the Projection Matrix by the Model View Matrix
    Matrix4f tempView = new Matrix4f();
    Matrix4f.mul(proj, model, tempView);
    tempView.invert();

    //Getting the Camera Position in World Space.  The 4th Column of the Model View Matrix.
    model.invert();
    Point cameraPos = new Point(model.m30, model.m31, model.m32);

    //Theoretically getting the vector the Picking Ray goes
    Vector4f rayVector = new Vector4f();
    Matrix4f.transform(tempView, mouseClip, rayVector);
    rayVector.translate((float)-cameraPos.getX(),(float) -cameraPos.getY(),(float) -cameraPos.getZ(), 0f);
    rayVector.normalise();
    glPopMatrix();

    //This Basically Spits out a value that changes as the Camera moves.
    //When the Mouse moves, the values change around 0.001 points from screen edge to edge.
    System.out.format("Vector: %f %f %f%n", rayVector.x, rayVector.y, rayVector.z);

    //return new Ray(cameraPos, rayVector);
    return null;
}

```

I don't really know why this isn't working. I was hoping some more experienced eyes might be able to help me out.

I can get the camera position like a champ, it's the vector the rays going in that I can't seem to get right.

Thanks.

**EDIT:**

knight666,

I translated your code, and here's what I came up with:

```
public static Ray getPick(int mouseX, int mouseY){
    glPushMatrix();

    //Setting up the Mouse Clip
    Vector2f mouseClip = new Vector2f((mouseX / 960f) * 2f - 1f, (mouseY / 640f) * 2f - 1f);

    //Loading Matrices
    FloatBuffer modMatrix = BufferUtils.createFloatBuffer(16);
    FloatBuffer projMatrix = BufferUtils.createFloatBuffer(16);
    glGetFloat(GL_MODELVIEW_MATRIX, modMatrix);
    glGetFloat(GL_PROJECTION_MATRIX, projMatrix);

    //Assigning Matrices
    Matrix4f proj = new Matrix4f();
    Matrix4f model = new Matrix4f();
    model.load(modMatrix);
    proj.load(projMatrix);

    //Multiplying the Projection Matrix by the Model View Matrix
    Matrix4f tempView = new Matrix4f();
    Matrix4f.mul(proj, model, tempView);
    tempView.invert();

    //Getting the Camera Position in World Space.  The 4th Column of the Model View Matrix.
    //model.invert();
    Point cameraPos = new Point(-model.m30, -model.m31, -model.m32);

    //Getting Mouse Position in 3D Space
    Vector4f pOne = new Vector4f(mouseClip.x, mouseClip.y, -1f, 1f);
    Vector4f pTwo = new Vector4f(mouseClip.x, mouseClip.y,  1f, 1f);
    Vector4f nearPoint = new Vector4f();
    Vector4f farPoint = new Vector4f();
    Matrix4f.transform(tempView, pOne, nearPoint);
    Matrix4f.transform(tempView, pTwo, farPoint);

    Vector3f pOneNorm = new Vector3f(pOne.x / pOne.w, pOne.y / pOne.w, pOne.z / pOne.w);
    Vector3f pTwoNorm = new Vector3f(pTwo.x / pTwo.w, pTwo.y / pTwo.w, pTwo.z / pTwo.w);

    Vector3f rayVector = new Vector3f();
    Vector3f.sub(pTwoNorm, pOneNorm, rayVector);

    rayVector.normalise();

    glPopMatrix();

    return new Ray(cameraPos, rayVector);
    //return null;
}

```

Unfortunately, I'm getting a ray with the vector of (0,0,-2) that doesn't change when I move the mouse.

As I understood it, Matrix4f.transform(matrix, vector, newVector) is the same as newVector = matrix * vector. Unfortunately in LWJGL, I can't use the former. I'm not sure if that's the case of what's going wrong or not.

I appreciate the help!

**Edit #2**

Here's the current method, with Byte56's updates:

```
public static Ray getPick(int mouseX, int mouseY){
    float windowWidth = 960f;
    float windowHeight = 640f;

    float aspectRatio = windowWidth / windowHeight;

    //get the mouse position in screenSpace coords
    double screenSpaceX = ((float) mouseX / (windowWidth / 2) - 1.0f) * aspectRatio;
    double screenSpaceY = (1.0f - (float) mouseY / (windowHeight / 2));

    double viewRatio = Math.tan((float) Math.PI / 4.0f / 2.00f);

    screenSpaceX = screenSpaceX * viewRatio;
    screenSpaceY = screenSpaceY * viewRatio;

    float NearPlane = 1f;
    float FarPlane = 100f;

    //Find the far and near camera spaces
    Vector4f cameraSpaceNear = new Vector4f((float) (screenSpaceX * NearPlane), (float) (screenSpaceY * NearPlane), (float) (-NearPlane), 1);
    Vector4f cameraSpaceFar = new Vector4f((float) (screenSpaceX * FarPlane), (float) (screenSpaceY * FarPlane), (float) (-FarPlane), 1);

    //Unproject the 2D window into 3D to see where in 3D we're actually clicking
    //Loading Matrices
    FloatBuffer modMatrix = BufferUtils.createFloatBuffer(16);
    FloatBuffer projMatrix = BufferUtils.createFloatBuffer(16);
    glGetFloat(GL_MODELVIEW_MATRIX, modMatrix);
    glGetFloat(GL_PROJECTION_MATRIX, projMatrix);

    // Assigning Matrices
    Matrix4f proj = new Matrix4f();
    Matrix4f model = new Matrix4f();
    model.load(modMatrix);
    proj.load(projMatrix);

    // Multiplying the Projection Matrix by the Model View Matrix
    Matrix4f tempView = new Matrix4f();
    Matrix4f.mul(proj, model, tempView);
    tempView.invert();

    Vector4f worldSpaceNear = new Vector4f();
    Matrix4f.transform(tempView, cameraSpaceNear, worldSpaceNear);

    Vector4f worldSpaceFar = new Vector4f();

    Matrix4f.transform(tempView, cameraSpaceFar, worldSpaceFar);

    //calculate the ray position and direction
    Vector3f rayPosition = new Vector3f(worldSpaceNear.x, worldSpaceNear.y, worldSpaceNear.z);
    Vector3f rayDirection = new Vector3f(worldSpaceFar.x - worldSpaceNear.x, worldSpaceFar.y - worldSpaceNear.y, worldSpaceFar.z - worldSpaceNear.z);

    rayDirection.normalise();

    Point p = new Point(rayPosition.x, rayPosition.y, rayPosition.z);

    return new Ray(p, rayDirection);
}

```

Here is my gluPerspective method call:

```
FIELD_OF_VIEW = 30;
gluPerspective(FIELD_OF_VIEW, 960f / 640f, 1f, 100f);

```

And my glLookAt method call. The method references a custom Point Object that moves with the player. The matrix is Pushed, LookedAt, and Popped every Render. The values u, v, i, & j are determined and changed to be able to rotate the "camera" around the point. The gluLookAt Call always comes before the attempt to make a ray.:

```
gluLookAt(
            //Camera Set Above the Reference Point
            (float) (lookAtPoint.getX() + u), (float)(lookAtPoint.getY() + v), (float) lookAtPoint.getZ() + zZoom,
            //The Reference Point
            (float) lookAtPoint.getX(), (float) lookAtPoint.getY(), (float) lookAtPoint.getZ(),
            //Setting the Up Vector
            i, j, 0f);

```

If I negate the vector, it's still off. The X axis is counting what should be a movement of 1 as a movement of approx 0.03.

# Answer
> 3 votes
OK, so I found your problem. I don't, however, know why it's the problem.

I plugged your code into mine, everything was the same except the matrices. The matrices retrieved from OpenGL did not match the ones I was generating. So, if you would, try upgrading your camera class to generate those matrices for you.

There's a few functions you'll need:

```
Matrix4f result = new Matrix4f();
...
Matrix4f CreateLookAt(Vector3f position, Vector3f direction, Vector3f up) {
    Vector3f.cross(up, direction, rightVector);
    rightVector = (Vector3f) rightVector.normalise();

    result.m00 = rightVector.x;
    result.m10 = rightVector.y;
    result.m20 = rightVector.z;
    result.m30 = -(Vector3f.dot(rightVector, position));

    result.m01 = up.x;
    result.m11 = up.y;
    result.m21 = up.z;
    result.m31 = -(Vector3f.dot(up, position));

    result.m02 = direction.x;
    result.m12 = direction.y;
    result.m22 = direction.z;
    result.m32 = -(Vector3f.dot(direction, position));

    return result;
}

private Matrix4f glhFrustumf2(Matrix4f matrix, float left, float right, float bottom, float top, float znear, float zfar) {
    float temp, temp2, temp3, temp4;
    temp = 2.0f * znear;
    temp2 = right - left;
    temp3 = top - bottom;
    temp4 = zfar - znear;
    matrix.m00 = temp / temp2;
    matrix.m01 = 0.0f;
    matrix.m02 = 0.0f;
    matrix.m03 = 0.0f;
    matrix.m10 = 0.0f;
    matrix.m11 = temp / temp3;
    matrix.m12 = 0.0f;
    matrix.m13 = 0.0f;
    matrix.m20 = (right + left) / temp2;
    matrix.m21 = (top + bottom) / temp3;
    matrix.m22 = (-zfar - znear) / temp4;
    matrix.m23 = -1.0f;
    matrix.m30 = 0.0f;
    matrix.m31 = 0.0f;
    matrix.m32 = (-temp * zfar) / temp4;
    matrix.m33 = 0.0f;
    return matrix;
}

Matrix4f CreatePerspectiveFieldOfView(float fov, float aspect, float zn, float zf) {
    float ymax, xmax;
    ymax = (float) (zn * Math.tan(fov * Math.PI / 360.0));
    xmax = ymax * aspectRatio;
    Matrix4f result = new Matrix4f();
    glhFrustumf2(result, -xmax, xmax, -ymax, ymax, zn, zf);

    return result;
}

```

Then when updating your view and projection you'll use:

```
view = CreateLookAt(position, direction, upVector);
projection = CreatePerspectiveFieldOfView(ViewAngle * zoomFactor, (float) WindowX / (float) WindowY, NearPlane, FarPlane);

```

Then there's the picking code:

```
public Ray GetPickRay(int mouseX, int mouseY) {
    float windowWidth = WindowX;
    float windowHeight = WindowY;

    double screenSpaceX = (mouseX / (windowWidth / 2) - 1.0f) * aspectRatio;
    double screenSpaceY = (1.0f - mouseY / (windowHeight / 2));
    double viewRatio = Math.tan(((float) Math.PI / (180.f/ViewAngle) / 2.00f)) * zoomFactor;

    screenSpaceX = screenSpaceX * viewRatio;
    screenSpaceY = screenSpaceY * viewRatio;

    cameraSpaceNear.set((float) (screenSpaceX * NearPlane), (float) (screenSpaceY * NearPlane),
            (-NearPlane), 1);
    cameraSpaceFar.set((float) (screenSpaceX * FarPlane), (float) (screenSpaceY * FarPlane),
            (-FarPlane), 1);

    tmpView.load(view);
    invView = (Matrix4f) tmpView.invert();
    Vector4f colonySpaceNear = new Vector4f();
    Matrix4f.transform(invView, cameraSpaceNear, colonySpaceNear);

    Vector4f colonySpaceFar = new Vector4f();

    Matrix4f.transform(invView, cameraSpaceFar, colonySpaceFar);

    rayPosition.set(colonySpaceNear.x, colonySpaceNear.y, colonySpaceNear.z);
    rayDirection.set(colonySpaceFar.x - colonySpaceNear.x,
            colonySpaceFar.y - colonySpaceNear.y, colonySpaceFar.z - colonySpaceNear.z);

    rayDirection.normalise();

    return new Ray(rayPosition, rayDirection);
}

```

Finally, when you're drawing your scene, you'll load in your camera matrices.

```
glMatrixMode(GL_PROJECTION);
glLoadMatrix(UtilFunctions.MatrixToFloatBuffer(COLONY.Camera.projection));
glMatrixMode(GL_MODELVIEW);
glLoadMatrix(UtilFunctions.MatrixToFloatBuffer(COLONY.Camera.view));

```

Phew! That should keep you busy for a bit and hopefully solve your problem!

# Answer
> 2 votes
I'm not used to coding in Java, but I managed to fix it for you using code from Horde3D.

```
// Algorithm courtesy of Horde3D
// h3dutPickRay

public static Ray getPick(int mouseX, int mouseY)
{
    // Mouse position in NDC [-1, 1]

    Vector2f mouse_ndc = new Vector4f(
        (float)(mouseX / 960f) * 2f - 1f,  // TODO: Hardcoded viewport
        (float)(mouseY / 640f) * 2f - 1f,
    );

    // Get matrices

    FloatBuffer projMatrix = BufferUtils.createFloatBuffer(16);
    glGetFloat(GL_PROJECTION_MATRIX, projMatrix);
    Matrix4f proj = new Matrix4f();
    proj.load(projMatrix);

    FloatBuffer modMatrix = BufferUtils.createFloatBuffer(16);
    glGetFloat(GL_MODELVIEW_MATRIX, modMatrix);
    Matrix4f model = new Matrix4f();
    model.load(modMatrix);

    // Build inverse MVP

    Matrix4f inverse_mvp = new Matrix4f();
    Matrix4f.mul(proj, model, inverse_mvp);
    inverse_mvp.invert();

    // Ray starts at camera

    Vector3f ray_origin(
        -model.m30,
        -model.m31,
        -model.m32
    );

    // Get positions in NDC space

    Vector4f p0 = inverse_mvp * Vector4f(mouse_ndc.x, mouse_ndc.y, -1f, 1f);
    Vector4f p1 = inverse_mvp * Vector4f(mouse_ndc.x, mouse_ndc.y,  1f, 1f);

    // Normalize to 3D coordinates

    Vector3f p0_norm(
        p0.x / p0.w,
        p0.y / p0.w,
        p0.z / p0.w
    );

    Vector3f p1_norm(
        p1.x / p0.w,
        p1.y / p0.w,
        p1.z / p0.w
    );

    // Get ray direction

    Vector3f ray_direction = p1 - p0;
    // ray_direction.normalize(); // optional

    // Finish

    return new Ray(ray_origin, ray_direction);
}

```

---
Tags: lwjgl, picking
---


# Question
Title: Attaching two objects and changing their world matrices accordingly
I'm having a hard time wrapping my head around the transformations required to bind two objects together in either a two-way or one-way relationship. I will need to implement both types.

For the first case, I want to be able to 'couple' two ships together in space. The ships have different mass, of course. Forces applied to either ship will use combined mass and moment of inertia to calculate and move both ships. The trick is, being sure that the point at which they are coupled remains the same, and they don't move at all relative to each other.

The second case is similar: I want a ship to be able to enter the atmosphere of a planet and move relative to the planet. The planet will be orbiting the sun, which is fixed at 0,0,0. Essentially, when the ship is sitting still outside of the atmosphere, the planet will move past it on its course-- but when the ship is sitting still inside the atmosphere, it moves and rotates with the planet, so that it is always relative to the horizon. Essentially, the vertices which make up the ship are now transformed just like the ones that make up the planet, *except* that the ship can move itself around relative to the planet.

I get the feeling I can implement both of these with the same code. Essentially, I am thinking of giving each object (which I call Fixtures) a list of "slave" Fixtures onto which that Fixture's world matrix is imposed. So, this would be the planet imposing its world on any contained ships. In the case of coupling, I would simply make each ship a slave of the other, somehow.

Obviously I can't just multiply the ship's world matrix by the planet's, or each ship by the others. What I'd like some help with is what calculations to make in order to get a nice, seamless relative world to the other object. I was thinking maybe I could just multiply the world of the slave by the inverse of the master, but then when you couple two ships you would lose all that world data. So, perhaps I need an intermediate "world" which is the absolute world, but use a secondary "final world" to actually transform the objects?

# Answer
In a typical hierarchy situation, the child transform offers relative rotation & translational differences from the parent transform. In your case, a ship may be a child to another ship, or it may be a child to a planet. So for 1st case, let's say shipB is joining shipA. They are positioned correctly where they will be joined. Prior to joining, they both have their own independent transforms. After joining, shipB becomes a child of shipA.

```
    //this occurs at joining:
    Vector3 offset = shipB.transform.Translation - shipA.transform.Translation;//creates a global space offset
    offset = Vector3.Transform(offset, Matrix.Invect(shipA.transform)); // converts offset to shipA's local space.

    shipB.transform = Matrix.Identity; // shipB offers no rotation relative to shipA.
    shipB.Translation = offset;

    //when drawing shipA:
    effect.World = shipA.transform;

    //when drawing shipB:
    effect.World = shipA.transform * shipB.transform; //typical parent/child concatenation in a row major transform API like Xna.
    /*
 since shipB's transform's rotational section (the 3x3 rotation section) is the identity matrix, it will not rotate B relative to A,
    but will offset translation per shipA's local rotation
*/

```

When removing the joint to allow both ships to fly freely on their own:

```
shipB.transform = shipA.transform;
Vector3 currentOffset = (shipA.transform.Right    * offset.X) +
                        (shipA.transform.Up       * offset.Y) +
                        (shipA.transform.Backward * offset.Z);
shipB.transform.Translation += currentOffset;

//draw shipA
effect.Worls = shipA.transform;

//draw shipB
effect.World = shipB.transform; // no longer a child.

```

For planet to ship relationship, it is similar to joining shipB to shipA but each frame, the ship can maneuver.

```
//this occurs at joining:
Vector3 offset = ship.transform.Translation - planet.transform.Translation;//creates a global space offset
offset = Vector3.Transform(offset, Matrix.Invect(planet.transform)); // converts offset to planet's local space.

ship.transform = Matrix.Identity;
ship.Translation = offset;

//each frame you would manipulate the ship's matrix thusly:
ship.transform.Translation += ship.transform.Forward * velocity * elapsedTime; // or whatever

//then when drawing planet:
effect.World = planet.transform;

//when drawing ship:
effect.World = planet.transform * ship.transform; //back to a parent/child concatenation here

```
> 1 votes

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


# Question
Title: How can I improve my isometric tile-picking algorithm?
I've spent the last few days researching isometric tile-picking algorithms (converting screen-coordinates to tile-coordinates), and have obviously found a lot of the math beyond my grasp.

I have come fairly close and what I have is workable, but I would like to improve on this algorithm as it's a little off and seems to pick down and to the right of the mouse pointer.

I've uploaded a video to help visualize the current implementation: http://youtu.be/EqwWcq1zuaM

My isometric rendering algorithm is based on what is found at this stackoverflow question's answer, with the exception that my x and y axis' are inverted (x increased down-right, while y increased up-right).

Here is where I am converting from screen to tiles:

```
// these next few lines convert the mouse pointer position from screen
// coordinates to tile-grid coordinates. cameraOffset captures the current
// mouse location and takes into consideration the camera's position on screen.
System.Drawing.Point cameraOffset = new System.Drawing.Point( 0, 0 );
cameraOffset.X = mouseLocation.X + (int)camera.Left;
cameraOffset.Y = ( mouseLocation.Y + (int)camera.Top );

// the camera-aware mouse coordinates are then further converted in an attempt
// to select only the "tile" portion of the grid tiles, instead of the entire
// rectangle. this algorithm gets close, but could use improvement.
mouseTileLocation.X = ( cameraOffset.X + 2 * cameraOffset.Y ) / Global.TileWidth;
mouseTileLocation.Y = -( ( 2 * cameraOffset.Y - cameraOffset.X ) / Global.TileWidth );

```

Things to make note of:

* mouseLocation is a System.Drawing.Point that represents the screen coordinates of the mouse pointer.
* cameraOffset is the screen position of the mouse pointer that includes the position of the game camera.
* mouseTileLocation is a System.Drawing.Point that is supposed to represent the tile coordinates of the mouse pointer.

If you check out the above link to youtube, you'll notice that the picking algorithm is off a bit. How can I improve on this?

# Answer
> 10 votes
What you need is some good old fashioned matrix math.

Let's say you have two spaces:

* World space - where the tiles reside
* Screen space - where the mouse pointer is

You want to check the mouse coordinates against the tiles. But first, you will have to convert your mouse coordinates from *screen coordinates* to *world coordinates*.

That sounds harder than it is. Let's pretend the tiles are not laid out isometrically, but in a grid. Like this:

I've added numbers that represent the tiles in memory. For example, `0` would be `m_Tiles[0]`.

Here, it's easy to see which tile is selected. In pseudocode:

```
vec2 pos = mouse.pos - tileset.pos_upperleft;
int index = ((pos.y / tileset.tile_height) * 2) + (pos.x / tileset.tile_width);

```

In this case, that gives us an index of 2, which is correct.

But watch what happens when we rotate the tileset 45 degrees:

Now we're selecting a different tile altogether! How can we fix this? Well, in two ways:

* Rotate the tileset to fit the screen coordinates (world space to screen space)
* Rotate the mouse coordinates to fit the world coordinates (screen space to world space)

We're going for the first method here. It's great for 2D selection because it allows us to keep the rest of the math the same.

First, let's build a matrix that defines the transformation of our tileset. We want to rotate the tileset by 45 degrees, so we'll take a 3x3 matrix (2D matrix) and add a rotation. Then we inverse the result. Think of it this way: to go from world space to screen space, we must rotate by 45 degrees. So to go the other way around, we must rotate by -45 degrees.

Now the code becomes:

```
mat3x3 transform = mat3x3.identity();
transform.rotate(45.0);
transform.inverse();

vec2 tileset_transformed_pos = transform * vec3(tileset.pos_upperleft.x, tileset.pos_upperleft.y, 1.0);

vec2 pos = mouse.pos - tileset_transformed_pos;
int index = ((pos.y / tileset.tile_height) * 2) + (pos.x / tileset.tile_width);

```

As you can see, we use the transform matrix to transform the upperleft corner of the tileset. Now the tileset coordinates are in the same space as the mouse coordinates.

But we're not there yet. The tiles are also squashed a bit. The same effect can be achieved by scaling the matrix by a certain amount:

Here I've scaled the whole tileset on the y-axis to 63%, which looks remarkably like an isometric projection. The full pseudo-code:

```
mat3x3 transform = mat3x3.identity();
transform.rotate(45.0);
transform.scale(1.0, 0.63);
transform.inverse();

vec2 tileset_transformed_pos = transform * vec3(tileset.pos_upperleft.x, tileset.pos_upperleft.y, 1.0);

vec2 pos = mouse.pos - tileset_transformed_pos;
int index = ((pos.y / tileset.tile_height) * 2) + (pos.x / tileset.tile_width);

```

Obviously you will have to tweak this a bit, but it should give you a sense of where to begin.

# Answer
> 0 votes
Seems that adding or substracting 0.5f to your calcs would do the trick... you only should be careful with negative tile coords, then should negate the sign of 0.5f

Here you a are a video where I show how it's done (code included)

though I'm working in 3D projecting to isometric 2D, the facts are the same.

# Answer
> 0 votes
I'm implementing a tile editor for isometric tiles, like you, and I'm having a problem with XNA and the GraphicsDeviceControl Microsoft gives as an example. The thing is I want to read the Mouse state (wich is read in the Update method in a classic Game class), but the class GraphicsDeviceControl doesn't implement it so I can't override it. What can I do? And sorry for my english if it's kinda weird, thanks!

# Answer
> 0 votes
After taking a closer look at the programmed algorithm and what I had on paper, I had left out a modification on the Y-axis before the conversion. I needed to subtract half of the tile height during the stage where I adjust the mouse position to take the camera into account.

The final algorithm looks like this:

```
// these next few lines convert the mouse pointer position from screen
// coordinates to tile-grid coordinates. cameraOffset captures the current
// mouse location and takes into consideration the camera's position on screen.
System.Drawing.Point cameraOffset = new System.Drawing.Point( 0, 0 );
cameraOffset.X = mouseLocation.X + (int)camera.Left;
cameraOffset.Y = ( mouseLocation.Y + (int)camera.Top ) - ( Global.TileHeight / 2 );

// the camera-aware mouse coordinates are then further converted in an attempt
// to select only the "tile" portion of the grid tiles, instead of the entire
// rectangle. this algorithm gets close, but could use improvement.
mouseTileLocation.X = ( cameraOffset.X + 2 * cameraOffset.Y ) / Global.TileWidth;
mouseTileLocation.Y = -( ( 2 * cameraOffset.Y - cameraOffset.X ) / Global.TileWidth );

```

This provides the accuracy I was looking for in my zone editor. Although, knight666's answer looks much more elegant (and makes more sense), re-writing the input and drawing code isn't something I feel like spending time on for the editor. I will, however, attempt to use his answer for the game.

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


# Question
Title: Rendering output to arbitary quadrilateral
I want to render output on a device to an arbitary quadirlateral, i.e. project texture on to a quad. What are the possible ways I could implement it?

Till now, I have investigated:

* Drawing textured quadrilateral - Quads look odd as they are composed of triangles, and the distortion looks odd. The issue I'm facing has been discussed here and here as well.
* Setting transformation on device - Need help in getting this implemented.
* Pixel shaders - Not able to implement the desired effect.

Any help would be much appreciated.

# Answer
> 1 votes
Don't if it will help you or not but if you want to implement it with pixel shader see if the shader below can help you.

```
/// <summary>Explain the purpose of this variable.</summary>
/// <minValue>0,0/minValue>
/// <maxValue>1,1</maxValue>
/// <defaultValue>0,0</defaultValue>
float2 LeftTop :register(C0);
/// <summary>Explain the purpose of this variable.</summary>
/// <minValue>0,0/minValue>
/// <maxValue>1,1</maxValue>
/// <defaultValue>0,1</defaultValue>
float2 LeftBottom :register(C1);
/// <summary>Explain the purpose of this variable.</summary>
/// <minValue>0,0/minValue>
/// <maxValue>1,1</maxValue>
/// <defaultValue>1,0</defaultValue>
float2 RightTop :register(C2);
/// <summary>Explain the purpose of this variable.</summary>
/// <minValue>0,0/minValue>
/// <maxValue>1,1</maxValue>
/// <defaultValue>1,1</defaultValue>
float2 RightBottom    :register(C3);

sampler input : register(s0);

float3x3 Adjoint(float3x3 m)
{
    float3x3 adj;

    // Calculate the adjoint matrix
    adj._11 = m._22*m._33 - m._23*m._32;
    adj._12 = m._13*m._32 - m._12*m._33;
    adj._13 = m._12*m._23 - m._13*m._22;

    adj._21 = m._23*m._31 - m._21*m._33;
    adj._22 = m._11*m._33 - m._13*m._31;
    adj._23 = m._13*m._21 - m._11*m._23;

    adj._31 = m._21*m._32 - m._22*m._31;
    adj._32 = m._12*m._31 - m._11*m._32;
    adj._33 = m._11*m._22 - m._12*m._21;

    return adj;
}

float4 Projection(float2 uv)
{
    float a,b,c,d,e,f,g,h;

    //setting variable names as variable names in algorithem
   float x0,x1,x2,x3,y0,y1,y2,y3;
   x0=LeftTop.x;
   y0=LeftTop.y;
   x1=RightTop.x;
   y1=RightTop.y;
   x2=RightBottom.x;
   y2=RightBottom.y;
   x3=LeftBottom.x;
   y3=LeftBottom.y;

   //If the polygon is Parallegoram
    a=x1-x0;
    b=x2-x1;
    c=x0;
    d=y1-y0;
    e=y2-y1;
    f=y0;
    g=0;
    h=0;

    float x3minusx0 = x3-x0;
    float SigmaX=(b - x3minusx0);
    float y3minusy0 = y3- y0;
    float SigmaY=( e - y3minusy0);

    //If the polygon is not a Parallegoram the following changes need to be done to the variables
    //if( SigmaX!=0 || SigmaY!=0)
    {
        float DeltaX1=-b;
        float DeltaX2=x3-x2;
        float DeltaY1=-e;
        float DeltaY2=y3-y2;
        float2x2 mat1 = {DeltaX1,DeltaX2,DeltaY1,DeltaY2};
        float denom = determinant(mat1);
        float2x2 mat2 = {SigmaX,DeltaX2,SigmaY,DeltaY2};
        g= determinant(mat2) / denom;
        float2x2 mat3= {DeltaX1,SigmaX,DeltaY1,SigmaY};
        h= determinant(mat3) /denom;
        a+=g*x1;
        b=(x3minusx0)+h*x3;
        d+=g*y1;
        e=y3minusy0+h*y3;
    }

    float3x3 ProjectionMatrix3x3= {a,d,g,b,e,h,c,f,1};
    float3x3 AdjoitOfProjectionMatrix3x3= Adjoint(ProjectionMatrix3x3);

    float3 inputVector=float3(uv.x,uv.y,1);
    float3 outputVector= mul(inputVector,AdjoitOfProjectionMatrix3x3);

   float2 FoundPoint;

   //Converting homogenious point to noramal 2D cordinate
   FoundPoint.x=outputVector.x/outputVector.z;
   FoundPoint.y=outputVector.y/outputVector.z;

   //some point grater than 1
   if(FoundPoint.x <0 || FoundPoint.y<0 || FoundPoint.x > 1 || FoundPoint.y > 1 )
   {
        return float4(0,0,0,0);
   }
   else
   {
        return tex2D(input, FoundPoint);
   }
}

float4 main(float2 uv: TEXCOORD) : COlOR
{
  return Projection(uv);
}

technique TransformTexture {
  pass P0     {
    PixelShader  = compile ps_2_0 main();
  }
}

```

# Answer
> 1 votes
One way to map a square/rectangular texture to an arbitrary quad is projective interpolation. I've written an article showing how to do this.

The short version: you interpolate UVs across the quad in a way analogous to how GPUs do it for perspective-correct rendering (which, as you may have noticed, does *not* produce a visible seam between the two triangles). To do this, you need to calculate a false "depth" value for each vertex of the quad, and do the interpolation using homogeneous coordinates based on this "depth". Full details are in the article linked above.

---
Tags: directx, windows, .net
---


title: Game Development Institute?

text:
# Question
Title: Game Development Institute?
Can you suggest a game development Institute? I am a newbie programmer and is really interested in developing my own game using C++ or other programming language. I would like to enroll my self in an institution who offers this kind of course?

# Answer
You can start with any decent programming course, get the basics down then specialize in one of the fields which are important for games like computer graphics, AI, networking, etc... There are a lot of game courses popping up these days not all of them great quality.

A lot of them focus more on game design than game development, which is strange because for every 5 designers you need 40 developers and 100 artists (I just made up that estimate but it's somewhere in that range).

Source: personal experience, I followed a BSc Computing Science and will now start on my MSc doing the Game & Media development track of another university's Computing Science course
> 2 votes

# Answer
I am also interested in game development. You can actually learn them online. There are a lot of game development forums and online tutorials around. But if you are really interested in enrolling yourself in an institution, this thread suggested one http://www.techyv.com/questions/basic-questions-regarding-game-development
> 0 votes

# Answer
Train2Game (http://www.train2game.com) offer a games developer course. It is a distance learning course and covers C++ as well as basics of game design. I've been doing it for a few months and it's not too bad.
> 0 votes

---
Tags: education
---


# Question
Title: Strange mesh import problem with Assimp and OpenGL
Using the assimp library for importing 3D data into an OpenGL application. I get some strange problems regarding indexing of the vertices:

If I use the following code for importing vertex indices:

```
for (unsigned int t = 0; t < mesh->mNumFaces; ++t)
    {
        const struct aiFace * face = &mesh->mFaces[t];
        if (face->mNumIndices == 3)
        {
        indices->push_back(face->mIndices[0]);
        indices->push_back(face->mIndices[1]);
        indices->push_back(face->mIndices[2]);
        }
    }

```

I get the following result:

Instead, if I use the following code:

```
for(int k = 0; k < 2 ; k++)
    {
        for (unsigned int t = 0; t < mesh->mNumFaces; ++t)
        {
            const struct aiFace * face = &mesh->mFaces[t];
            if (face->mNumIndices == 3)
            {
            indices->push_back(face->mIndices[0]);
            indices->push_back(face->mIndices[1]);
            indices->push_back(face->mIndices[2]);
            }
        }
    }

```

I get the correct result:

Hence adding the indices twice, renders the correct result?

The OpenGL buffer is populated, like so:

```
glBufferData(GL_ELEMENT_ARRAY_BUFFER,
             indices->size() * sizeof(unsigned int),
             indices->data(),
             GL_STATIC_DRAW);

```

And rendered as follows:

```
glDrawElements(GL_TRIANGLES,
               vertexCount*3,
               GL_UNSIGNED_INT,
               indices->data());

```

# Answer
> 4 votes
The second Argument of the glDrawElements function should be the number of indices and not the number of vertices.

It should look something like this: glDrawElements(GL\_TRIANGLES, indices-\>size(), GL\_UNSIGNED\_INT, indices-\>data());

If you have more vertices than indices, this would explain your problem. Because you try to draw more indices than which are actually stored in the buffer unless you put the indices twice.

---
Tags: c++, opengl, 3d-meshes, assimp
---