title: Sensor based vs. AABB based collision

text:
# Question
Title: Sensor based vs. AABB based collision
I'm trying to write a simple collision system, which will probably be primarily used for 2D platformers, and I've been planning out an AABB system for a few weeks now, which will work seamlessly with my grid data structure optimization. I picked AABB because I want a simple system, but I also want it to be perfect.

Now, I've been hearing a lot lately about a different method to handle collision, using sensors, which are placed in the important parts of the entity. I understand it's a good way to handle slopes, better than AABB collision.

The thing is, I can't find a basic explanation of how it works, let alone a comparison of it and the AABB method. If someone could explain it to me, or point me to a good tutorial, I'd very much appreciate it, and also a comparison of the advantages and disadvantages of the two techniques would be nice.

# Answer
> 5 votes
The basic concept, used for many years now, is to just send out ray (really, line segment) queries from your character. If the character has gravity applies or is moving donwards, shoot two rays from the bottom two corners of the character's collision box and see if anything is close. You can react differently depending on which of the two registers a hit.

You may need to experiment with the number of rays, the distance cut-off (how long of a line segment you're checking), and the exact placement. Putting them at the exact corners may be problematic, but putting them some number of pixels "in" from the corners may work better. You may want a third ray in the middle. Etc.

One nice effect of this is that, since you use a ray cast and not generic SAT, you can handle collisions nicer. With SAT you often get a sliding effect on slopes. You also can't automatically deal with characters running down a slope super well (they'll end up bouncing a bit; you can see this in modern 3D games, too, like Fallout) with plain SAT/bounding volumes.

Another benefit is that with the rays you can tell if only one side of the character is off a ledge and do a different "balancing on a ledge" animation (e.g., Sonic).

Lastly, with the rays you can get continuous collision (you can see if a collision is about to happen and when rather than resolving it after a collision). This has uses in many cases (e.g., the sliding-on-slopes problem I mentioned) and helps to avoiding tunneling of high-speed objects without using small time steps - just lengthen your rays.

You can use these rays when jumping or running, too. It's way better to send out a ray and know that your character can't walk left than to move left and then be pushed out of the wall. In the latter, you'll end up with a silly "running while against a wall" animation, you aren't able to easily have box pushing or the like, and so on. The rays let you know "can't run left, don't even animate running" as well as "to the left is a box, do push animation if it can move".

---
Tags: collision-detection, physics, collision-resolution, platformer, aabb
---


# Question
Title: How do I have an arrow follow different height parabolas depending on how long the player holds down a key?
i'm trying to throw an arrow in my game, but i'm having a hard time trying to realize how to make a good parabola.

What I need: The more you hold "enter" stronger the arrow goes. The arrow angle will be always the same, **45 degrees**.

This is what I have already have:

```
    private float velocityHeld = 1f;
    protected override void Update(GameTime gameTime)
    {
 private void GetKeyboardEvent()
        {
            if (Keyboard.GetState().IsKeyDown(Keys.Enter) && !released)
            {
                timeHeld += velocityHeld;
                holding = true;
            }
            else
            {
                if (holding)
                {
                    released = true;
                    holding = false;
                    lastTimeHeld = timeHeld;
                }
            }
        }

        if (released && timeHeld > 0)
        {
        float alpha = MathHelper.ToRadians(45f);
        double vy = timeHeld * Math.Sin(alpha);
        double vx = timeHeld * Math.Cos(alpha);

        ShadowPosition.Y -= (int)vy;
        ShadowPosition.X += (int)vx;
        timeHeld -= velocityHeld;
        }
        else
        {
            released = false;

        }
       }

```

My question is, what do I need to do to make the arrow to go bottom as it loses velocity (timeHeld) to make a perfect parabola?

# Answer
> 3 votes
You're already calculating the launch velocity; after launch, the X velocity of the object remains constant over time, and the Y velocity has constant downward gravitational acceleration applied to it over time. Then you simply apply the velocity as usual in a physics engine.

For more information, if you search for "parabolic trajectory", "ballistic trajectory" or "projectile trajectory" you'll find all kinds of articles and demos on the subject. For example, see Projectile motion on Wikipedia.

The standard treatment ignores air resistance, but you can incorporate that as well if you like; it only requires adding a drag force proportional to the negative of the object's current velocity. You can find this discussed many times on the Web as well.

---
Tags: xna, c#, algorithm, trajectory
---


# Question
Title: What is the practical use of IBOs / degenerate vertex in OpenGL?
Vertices in 3D models CAN get cut in the process of optimizing 3D geometry, *(degenerate vertices)* by 3D graphics software *(Blender, ...)* when exporting because they aren't needed when reusing a vertex for multiple triangles. (In the current case 3D data is exported from Blender as .ply and read by a simple application that displays the 3D model)

Every vertex has a few attributes like position, color, normal, tangent,... But the data for each vertex that is cut through the vertex sharing is lost and is missing in the vertex shader.

Modern shader techniques like Bump or Normal mapping require normals/tangents per vertex which are also cut.

**To use complex shader techniques IBOs must not be used? Or is there a way to use IBOs and retain the data per vertex that was origionally lost?**

# Answer
> 4 votes
Index buffers are useful because they reduce the amount of vertex data that the GPU must process. First of all, where vertices are reused across multiple triangles, only one copy of the vertex data is needed; since vertex data is typically much larger than index data, that means less memory consumed, and less memory bandwidth required to load the vertex data into the GPU's shader cores.

Second, GPUs have a vertex cache, where recently-transformed vertices are stored and the results can be re-used if that vertex is seen again soon. The index buffer is the tag for this cache - that is, the index is how the GPU tells whether a vertex is the same as one already in the cache.

Now, as you point out, sometimes vertices are not reused due to a UV seam, a hard edge (i.e. a seam in the normals), etc. So vertices must sometimes be duplicated, producing two vertices with the same position but different UVs, normals, etc. However, (a) this often only affects a fraction of the vertices in the mesh, and (b) the vertices still get reused a little.

For example, in a cube model with no UVs or normals, you'd have 8 vertices and 12 triangles, so each vertex would be reused on average 4.5 times (that's 12 * 3 / 8). Adding UVs and normals, so that every face of the cube requires its own vertices, you now have 24 vertices and 12 triangles, so each vertex is reused on average 1.5 times. You have lower vertex reuse, but you still have *some* reuse, so it's still worthwhile to use an index buffer.

# Answer
> 4 votes
You need to process exported models to be used in a game. Model editors like Blender or Max are not strictly intended for making real-time simulations. You can use tools like AssImp to read in models in various formats, do a number of post-processing steps (many are built in), and then save it in a format better fitted to your engine. One of these stages will be to properly map vertex position back to its attribute data for all vertices. This is required for a large number of formats which try to optimize for very different needs than high-speed rendering, such as optimizing storage space or something.

So far as *degenerate* model data goes (more in the context of *degenerate triangles*) these are to make a single triangle strip in place of multiple triangle strips. Triangle strips are more efficient than triangle list and having a single draw call is significantly more efficient than several. A degenerate triangle allows a triangle strip to "jump" from one strip to another without breaking the stream of vertices. These degenerate triangles are never rendered, don't need vertex attribute data (of course something still needs to be filled in due to how the pipline works), and there's no need to worry about normal mapping or texture lookups for such triangles. Usually you don't actually use a degenerate vertex here, but it's possible (maybe necessary in some cases; I've never written an algorithm to optimize meshes like this myself).

If the data is truly being lost for some reason, try exporting in a differnt format.

# Answer
> 0 votes
If I'm understanding your question correctly you are asking, then yes it is possible by recombining the data into a per vertex data and then eliminating reused vertices.

~~You can definitely use Index Buffers with modern shader techniques - in fact I'd argue they are more useful as in modern shader techniques you probably won't have per vertex Normals/Tangents/Binormals/BiTangents anyway. Most of those in high end engines are probably written into a texture to be used in per-pixel lighting.~~

---
Tags: opengl, vertex
---


# Question
Title: How can I mod an item to take experience from a player in Minecraft?
I am creating a mod that has invincible tools which take experience from the player each time they are used.

Can someone please tell me how to make the tools take away the experience when used?

# Answer
You could look in the game code to find the code for enchanting. Since that takes away experience, it should tell you how, although it may be in levels. Also, you could look in the code for the anvil. In those, you should find variables for experience. You could probably subtract from those variables for every 2 or so blocks that you mine/dig/chop, like the vanilla tools do for their damage values. Also, i found a tutorial that could probably help you, in the Resources below.

I found this in the source code: entityplayermp.addExperienceLevel(). You could do entityplayermp.addExperienceLevel(-1) and could probably use entityplayermp.subtractExperienceLevel(1). I don't know if the second option would work.

Possible Solutions: What you can do, because in tools there is this:

```
onBlockDestroyed = "itemstack.damageItem(2)

```

you can do:

```
onBlockDestroyed = entityplayermp.addExperienceLevel(-1)

```

Another option is to write a new method. Instead of calling onPlayerDestroyBlock call onPlayerDestroyBlockWithXPick, which would include the code:

entityplayermp.addExperienceLevel(-1)

The disadvantage of this, though, is that you would have to replace all vanilla/modded blocks with your own version of them, to include the method.

Resources:

MCP (Mod Coder Pack) to decompile the code, if you haven't already.

The Forge Ore Dictionary: a dictionary of all common mods's items and vanilla items.

The Tutorial: A modding tutorial that i found, includes code for a pickaxe, among other things.

Disclaimer: This code may not work, even though i took it from credible sources, i may have made a mistake.
> 9 votes

# Answer
Two resources that will help you greatly:

You'll probably want to checkout MCP. I've used it a good amount and it's really nice. Spend a decent amount of time just reading the code before you start though. If you google MCP tutorials you'll get a lot of short easy tutorials to help you out.

Good luck!
> 0 votes

---
Tags: java, minecraft-modding, modding
---


# Question
Title: Frustum culling with third person camera
I have a third person camera that contains two matrices: view and projection, and two Vector3's: camPosition and camTarget. I've read up on frustum culling and it makes it seem easy enough for a first person camera, but how would I implement this for a third person camera? I need to take into effect the objects I can see behind me too. How would I implement this into my camera class so it runs at the same time as my update method?

```
    public void CameraUpdate(Matrix objectToFollow)
    {
        camPosition = objectToFollow.Translation + (objectToFollow.Backward *backward) + (objectToFollow.Up * up);
        camTarget = objectToFollow.Translation;

        view = Matrix.CreateLookAt(camPosition, camTarget, Vector3.Up);
    }

```

Can I just create another method within the class which creates a bounding sphere with a value from my camera and then uses the culling based on that? And if so, which value am I using to create the bounding sphere from?

After this is implemented, I'm planning on using occlusion culling for the faces of my objects adjacent to other objects. Will using just one or the other make a difference? Or will both of them be better? I'm trying to keep my framerate as high as possible

# Answer
> 2 votes
First of all, let's talk about culling as a performance optimisation. All the usual rules of performance optimisation apply: you should **measure it!** Are you below your performance target? And what's hurting your performance?

Basically: no point in including performance optimisations all willy-nilly.

That being said - maybe you've already measured it and you do have a performance problem. Object culling can help you stay within your batch limit. Occlusion culling individual faces is more likely to hurt performance than to help. For the class of performance problems that this optimisation *feels* like it should solve, early Z or occlusion queries are, perhaps, the correct optimisations to persue.

---

Now I've got all that out of the way, I have **good news**: frustum culling for a third-person camera is *exactly the same* as for a first-person camera. It's the same for basically any kind of camera.

You take your camera's matrix, which is `view * project`, and create a `BoundingFrustum` (MSDN), which you can then use to perform intersection tests for culling.

You're basically creating a cut-off pyramid extending from the camera - this shape:

http://i.msdn.microsoft.com/dynimg/IC47709.gif

And anything that intersects that shape is what will be visible within your camera volume. That shape is the same between both camera types.

---

The reason this works is because a camera matrix takes vertices in world space, moves them "in front" of the camera with `view` matrix, and then projects them (with your `project` matrix) into a region from (-1,-1,0) to (1,1,1) within which the GPU's rasterizer actually performs its rendering.

`BoundingFrustum` simply reverses that process - taking the corners of the raster space and unprojecting them back out into world space.

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


# Question
Title: Best way to determine surface normal for a group of pixels?
One of my current endeavors is creating a 2D destructible terrain engine for iOS Cocos2D (See https://github.com/crebstar/PWNDestructibleTerrain ). It is in an infant stages no doubt, but I have made significant progress since starting a couple weeks ago. However, I have run into a bit of a performance road block with calculating surface normals.

Note: For my destructible terrain engine, an alpha of 0 is considered to not be solid ground.

The method posted below works just great given small rectangles, such as n \< 30. Anything above 30 causes a dip in the frame rate. If you approach 100x100 then you might as well read a book while the sprite attempts to traverse the terrain. At the moment this is the best I can come up with for altering the angle on a sprite as it roams across terrain (to get the angle for a sprite's orientation just take dot product of 100 * normal * (1,0) vector).

```
-(CGPoint)getAverageSurfaceNormalAt:(CGPoint)pt withRect:(CGRect)area {

float avgX = 0;
float avgY = 0;
ccColor4B color = ccc4(0, 0, 0, 0);
CGPoint normal;
float len;

for (int w = area.size.width; w >= -area.size.width; w--) {
    for (int h = area.size.height; h >= -area.size.height; h--) {
        CGPoint pixPt = ccp(w + pt.x, h + pt.y);
        if ([self pixelAt:pixPt colorCache:&color]) {
            if (color.a != 0) {
                avgX -= w;
                avgY -= h;
            } // end inner if
        } // end outer if
    } // end inner for
} // end outer for

len = sqrtf(avgX * avgX + avgY * avgY);
if (len == 0) {
    normal = ccp(avgX, avgY);
} else {
    normal = ccp(avgX/len, avgY/len);
} // end if

return normal;
} // end get

```

My problem is I have sprites that require larger rectangles in order for their movement to look realistic. I considered doing a cache of all surface normals, but this lead to issues of knowing when to recalculate the surface normals and these calculations also being quite expensive (also how large should the blocks be?). Another smaller issue is I don't know how to properly treat the case when length is = 0.

So I am stuck... Any advice from the community would be greatly appreciated! Is my method the best possible one? Or should I rethink the algorithm? I am new to game development and always looking to learn new tips and tricks.

**EDIT:** This is a re-work of the getSurfaceNormal function to implement the 2nd algorithm as specified by Nathan. I am putting it here for purposes of feedback and to hopefully show in code what Nathan is talking about.

```
-(CGPoint)getSurfaceNormalAt:(CGPoint)pt withSquareWidth:(int)area {
// This method only looks at surface pixels

int avgX = 0;
int avgY = 0;
CGPoint normal;
float len;
ccColor4B color = ccc4(0, 0, 0, 0);

for (int w = area; w >= -area; w--) {
    int h = area;
    do {
        if ([self pixelAt:ccp(w + pt.x, h + pt.y) colorCache:&color]) {
            if (color.a != 0) {
                if (w < 0) {
                    avgX -= w;
                    avgY -= h;
                } else {
                    avgX += w;
                    avgY += h;
                }
                break;
            } // end inner if
        } // end outer if
        h--;
    } while (h >= -area);
} // end for
int perpX = -avgY;
int perpY = avgX;
len = sqrtf(perpX * perpX + perpY * perpY);
normal = ccp(perpX/len, perpY/len);

return normal;
}

```

# Answer
I think your basic idea is sound. I'll summarize what your current code is doing. To get the average normal within an area around a point, you're gathering all the pixels in a rectangle centered on that point. For all the pixels in the rectangle that are solid ground, you're averaging the vector from the pixel to the query point. Effectively you're calculating the vector from the center of mass of the nearby solid pixels, to the query point.

I have two general suggestions to speed this up. The first is that you don't need to look at *every single* pixel in the search area. You can probably get a pretty good approximation by using a sparse sampling: only look at a few isolated pixels, evenly distributed over the search area. For instance, you could step by units of 2 to 5 pixels instead of 1 pixel in your loop; that would give you a sparse grid sampling and that might well be good enough to get away with. Poisson disk sampling is also a common sparse sampling method, especially in pixel shaders for soft shadows, SSAO, etc. You precompute a Poisson disk pattern (just store the points in a static array in your code) and scale the pattern to the size of the desired search area at runtime.

The second suggestion is that you could probably replace the 2D search with a series of 1D searches. You don't really care what's under the ground, you just care what the orientation of the ground *surface* is, if I understand correctly. So you could pick a few points along the top of the search area, then just do a 1D search down from each starting point until you find a solid pixel. In ASCII art,

```
X   X   X   X
|   |   |   |
|   |   | ..*
| ..*...*....
*............

```

The X's are the starting points, the vertical bars are the 1D searches, the dots are the ground, and the stars are the ground points found by the searches. Once you have these points, you calculate the average vector from each of them to the center point, but negate the vector for the points to the left of the center, and leave it alone for the points to the right. That should prevent the average from coming out zero, and will give you a vector that points tangent to the terrain, to the right. Calculate the vector perpendicular to this one and you'll have your normal.
> 4 votes

---
Tags: performance, cocos2d, objective-c
---


# Question
Title: The most efficent ways for drawing lines all day long with OpenGL
I'd like to put a computer screen that is running an OpenGL programs in a room. It has to run all day long (not in the night).

I'd like to draw lines that are slowly fading in the background. The setting is simple: a uniform color background (say, black) and colored lines (say, white) that are slowly fading out.

With slowly I mean.. hours. Say that the first line I draw is with alpha 255 (fully visible), after one hours is 240. After 10 hours is 105.

One line could have 250 points and there will be like 300 line in one day.

For now I have done a prototype with very rudimentary method like:

```
glBegin( GL_LINE_STRIP );
iterator = point_list.begin();
for (++iterator, end = point_list.end(); iterator != end; ++iterator) {
    const Vec3D &v = *iterator;
    glVertex2f(v.x(), v.y());
}
glEnd();

```

More efficient method?

# Answer
> 5 votes
Efficiency when drawing a mere 300 lines is probably not something you need to worry too much about. Even the old OpenGL screensavers available with Windows 95 and which used Microsoft's software implementation were able to handle that kind of workload with ease, so I suggest that looking for a more efficient method of doing something that's already an incredibly lightweight task falls squarely into the realm of micro-optimization.

If glBegin/glEnd works fine for you in this use case, then by all means continue using it. Yes, be aware that it's not the best way of drawing stuff, but you're already going to have sub-millisecond frametimes, so why bother with a program like this? If you're already getting over 1000fps then being able to boost that to 2000fps really won't mean much at all. This isn't a performance-critical program, 10fps would be fine, 1fps would be fine. You've better things to be spending your time doing.

Remember - Quake used glBegin/glEnd back in 1996, had much heavier workloads than a mere 300 lines, and ran quite well despite that.

More important things here are that you don't accidentally fall back to software emulation, and that you don't chew through too much power while running this all day.

You can avoid software emulation by either drawing quads (if you need wide lines) or by strictly restricting yourself to width-1 lines (which are more likely to be hardware-accelerated).

For power-saving, this is one case where using Sleep in your main loop *is* appropriate (don't even think about using it to control framerate though; it's not for that, it's for power-saving). So by all means go stick a great big Sleep call in there; you're dropping alpha by 1/255 every *four minutes* so Sleeping for 15 or even 30 milliseconds between frames is *perfectly alright* here.

This is all in the spirit of fitting a solution to the problem, rather than trying to force the problem to meet a pre-concieved idea of what the solution should be, and the approach you've currently got is *fine* for the problem as you describe it.

---
Tags: opengl, 2d, optimization
---


# Question
Title: How to make image bigger than the screen to be slideable in the screen in monogame for windows phone 8?
(Idk if my title is correct, because when I google it, there is no related result I guess)

I am not sure how to explain it correctly, but I am making a plain 2D, tile based, tactic game in windows phone 8 using monogame. I want to make my map is "slideable". With "slidable" I mean I can draw larger images (in total) than my screen and then slide it so I can view a certain area of the drawn images

Example : I have a screen which dimension is 1280x720. I have a 1500x1500px image, which consists of 15 tiles, which is 100x100px each, which each tiles is redrawn each times the "Draw" is called. If the image is larger than the screen, the displayed area will be trimmed and of course, making a 220x780px area that is unseenable. The only way to see all of it is through "sliding" the screen around, so I can see all the area.

My question is : How to make that happen? Because in default, the screen is unslideable and the image remains trimmed.

Sorry if my question and explanation is not clear enough. Clarify it as much as you like. Thank you.

# Answer
> 0 votes
This is thecode from an old codeplex discussion:

```
image.position += gesture.Delta;

```

In my case :

I added this class level field :

```
Vector2 _delta;

```

with initial value of:

```
Vector2.Zero

```

Below is the code I added to my GameComponent update method :

```
while (TouchPanel.IsGestureAvailable)
{
    GestureSample geisture = TouchPanel.ReadGesture();
    switch (geisture.GestureType)
    {
        case GestureType.FreeDrag:

            {
                _delta += geisture.Delta;
            } break;
    }
}

```

And below is the code I added to my Game1 constructor

```
 TouchPanel.EnabledGestures = GestureType.FreeDrag;

```

Because I only want to detect FreeDrag.

I use the delta this way, in case you wanna know

```
object.position += _delta;

```

# Answer
> 1 votes
You need to, of course, program such behaviour.

The simpliest way to do that is just storing coordinates of your "camera", let's say, `x` and `y`.

When you slide left, `x` decreases, and when you slide right, `x` increases. When you slide up, `y` decreases, and when you slide down, `y` increases.

When you call "Draw", you draw your screen beggining from pixel with coordinates of `x` and `y`, and end with pixel with coordinates of `x + screen_width - 1`, `y + screen_height - 1`.

As your image is divided into tiles, you just need to find which tile the `x`, `y` pixel, and which other tile contains `x + screen_width - 1`, `y + screen_height - 1` pixel. Then do the same, just with tiles instead of pixels.

---
Tags: graphics, monogame, windows-phone-8
---


title: Matrix multiplication - Scene Graphs

text:
# Question
Title: Matrix multiplication - Scene Graphs
I wrote a MatrixStack class in C# to use in a SceneGraph. So, to get the world matrix for an object I am suposed to use:

```
WorldMatrix = ParentWorld * LocalTransform

```

But, in fact, it only works as expected when I do the other way:

```
WorldMatrix = LocalTransform * ParentWorld

```

Mi code is:

```
public class MatrixStack
{
    Stack<Matrix> stack = new Stack<Matrix>();
    Matrix result = Matrix.Identity;

    public void PushMatrix(Matrix matrix)
    {
        stack.Push(matrix);
        result = matrix * result;
    }

    public Matrix PopMatrix()
    {
        result = Matrix.Invert(stack.Peek()) * result;
        return stack.Pop();
    }

    public Matrix Result
    {
        get { return result; }
    }

    public void Clear()
    {
        stack.Clear();
        result = Matrix.Identity;
    }
}

```

Why it works this way and not the other? Thanks!

# Answer
As previously mentioned, matrix order matters with matrices, be sure to keep it consistent throughout your entire scene graph node update method.

I personally choose to use the order: M = T\*R\*S, to preserve non-uniform scaling and to preserve rotation in relation to translation.

```
model = worldTranslate * worldRotate * worldScale;

if(parentNode){
worldTranslate = parentNode->worldTranslate * translateMatrix;
/*
Other matrices here
*/

 } else {
worldTranslate = translateMatrix;
/*
Other matrices here
*/
}

if(!childNodes.empty()){
/*
Recursive update method
*/
}

```
> 2 votes

# Answer
Short answer - matrix multiplication is not commutative - A\*B != B\*A

Slightly longer answer - because matrix operations can be viewed as function compositions and function compositions aren't necessarily commutative - some matrix ops are commutative, say simple addition, but as soon as you add scaling or rotation..........

An even longer answer involves things like rings and I really try and stay away from number theory :-)
> 2 votes

# Answer
The order in which the matrix is represented in memory affects the order of multiplication.

Row/Column-major order

column-major (P\*V\*M)

row-major (M\*V\*P)
> 2 votes

---
Tags: c#, matrix, mathematics
---


# Question
Title: Basic shadow mapping fails on NVIDIA card?
Recently I switched from an AMD Radeon HD 6870 card to an (MSI) NVIDIA GTX 670 for performance reasons.

I found however that my implementation of shadow mapping in all my applications failed. In a very simple shadow POC project the problem appears to be that the scene being drawn never results in a draw to the depth map and as a result the entire depth map is just infinity, 1.0 (Reading directly from the depth component after draw (glReadPixels) shows every pixel is infinity (1.0), replacing the depth comparison in the shader with a comparison of the depth from the shadow map with 1.0 shadows the entire scene, and writing random values to the depth map and then not calling glClear(GL\_DEPTH\_BUFFER\_BIT) results in a random noisy pattern on the scene elements - from which we can infer that the uploading of the depth texture and comparison within the shader are functioning perfectly.)

Since the problem appears almost certainly to be in the depth render, this is the code for that:

```
const int s_res = 1024;

GLuint shadowMap_tex;

GLuint shadowMap_prog;
GLint sm_attr_coord3d;
GLint sm_uniform_mvp;

GLuint fbo_handle;
GLuint renderBuffer;

bool isMappingShad = false;

//The scene consists of a plane with box above it
GLfloat scene[] = {
    -10.0, 0.0, -10.0, 0.5, 0.0,
     10.0, 0.0, -10.0, 1.0, 0.0,
     10.0, 0.0,  10.0, 1.0, 0.5,

    -10.0, 0.0, -10.0, 0.5, 0.0,
    -10.0, 0.0,  10.0, 0.5, 0.5,
     10.0, 0.0,  10.0, 1.0, 0.5,
    ...
};

//Initialize the stuff used by the shadow map generator
int initShadowMap()
{
    //Initialize the shadowMap shader program
    if (create_program("shadow.v.glsl", "shadow.f.glsl", shadowMap_prog) != 1)
        return -1;

    const char* attribute_name = "coord3d";
    sm_attr_coord3d = glGetAttribLocation(shadowMap_prog, attribute_name);
    if (sm_attr_coord3d == -1) {
        fprintf(stderr, "Could not bind attribute %s\n", attribute_name);
        return 0;
    }

    const char* uniform_name = "mvp";
    sm_uniform_mvp = glGetUniformLocation(shadowMap_prog, uniform_name);
    if (sm_uniform_mvp == -1) {
        fprintf(stderr, "Could not bind uniform %s\n", uniform_name);
        return 0;
    }

    //Create a framebuffer
    glGenFramebuffers(1, &fbo_handle);
    glBindFramebuffer(GL_FRAMEBUFFER, fbo_handle);

    //Create render buffer
    glGenRenderbuffers(1, &renderBuffer);
    glBindRenderbuffer(GL_RENDERBUFFER, renderBuffer);

    //Setup the shadow texture
    glGenTextures(1, &shadowMap_tex);
    glBindTexture(GL_TEXTURE_2D, shadowMap_tex);

    glTexImage2D(GL_TEXTURE_2D, 0, GL_DEPTH_COMPONENT, s_res, s_res, 0, GL_DEPTH_COMPONENT, GL_FLOAT, NULL);

    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP_TO_EDGE);
    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP_TO_EDGE);

    return 0;
}

//Delete stuff
void dnitShadowMap()
{
    //Delete everything
    glDeleteFramebuffers(1, &fbo_handle);
    glDeleteRenderbuffers(1, &renderBuffer);
    glDeleteTextures(1, &shadowMap_tex);

    glDeleteProgram(shadowMap_prog);
}

int loadSMap()
{
    //Bind MVP stuff
    glm::mat4 view = glm::lookAt(glm::vec3(10.0, 10.0, 5.0),
                                 glm::vec3(0.0, 0.0, 0.0),
                                 glm::vec3(0.0, 1.0, 0.0));

    glm::mat4 projection = glm::ortho<float>(-10,10,-8,8,-10,40);

    glm::mat4 mvp = projection * view;

    glm::mat4 biasMatrix(
        0.5, 0.0, 0.0, 0.0,
        0.0, 0.5, 0.0, 0.0,
        0.0, 0.0, 0.5, 0.0,
        0.5, 0.5, 0.5, 1.0
    );

    glm::mat4 lsMVP = biasMatrix * mvp;

    //Upload light source matrix to the main shader programs
    glUniformMatrix4fv(uniform_ls_mvp, 1, GL_FALSE, glm::value_ptr(lsMVP));

    glUseProgram(shadowMap_prog);
    glUniformMatrix4fv(sm_uniform_mvp, 1, GL_FALSE, glm::value_ptr(mvp));

    //Draw to the framebuffer (with depth buffer only draw)
    glBindFramebuffer(GL_FRAMEBUFFER, fbo_handle);
    glBindRenderbuffer(GL_RENDERBUFFER, renderBuffer);
    glBindTexture(GL_TEXTURE_2D, shadowMap_tex);
    glFramebufferTexture2D(GL_FRAMEBUFFER, GL_DEPTH_ATTACHMENT, GL_TEXTURE_2D, shadowMap_tex, 0);

    glDrawBuffer(GL_NONE);
    glReadBuffer(GL_NONE);

    GLenum result = glCheckFramebufferStatus(GL_FRAMEBUFFER);
    if (GL_FRAMEBUFFER_COMPLETE != result) {
        printf("ERROR: Framebuffer is not complete.\n");
        return -1;
    }

    //Draw shadow scene
    printf("Creating shadow buffers..\n");

    int ticks = SDL_GetTicks();

    glClear(GL_DEPTH_BUFFER_BIT); //Wipe the depth buffer
    glViewport(0, 0, s_res, s_res);

    isMappingShad = true;

    //DRAW
    glEnableVertexAttribArray(sm_attr_coord3d);
    glVertexAttribPointer(sm_attr_coord3d, 3, GL_FLOAT, GL_FALSE, 5*4, scene);

    glDrawArrays(GL_TRIANGLES, 0, 14*3);

    glDisableVertexAttribArray(sm_attr_coord3d);

    isMappingShad = false;

    glBindFramebuffer(GL_FRAMEBUFFER, 0);

    printf("Render Sbuf in %dms (GLerr: %d)\n", SDL_GetTicks() - ticks, glGetError());

    return 0;
}

```

This is the full code for the POC shadow mapping project (C++) (Requires SDL 1.2, SDL-image 1.2, GLEW (\>1.5) and GLM development headers.)

initShadowMap is called, followed by loadSMap, the scene is drawn from the camera POV and then dnitShadowMap is called.

I followed this tutorial originally (Along with another more comprehensive tutorial which has disappeared as this guy re-configured his site but used to be here (404).)

I've ensured that the scene is visible (as can be seen within the full project) to the light source (which uses an orthogonal projection matrix.) Shader utilities function fine in non-shadow-mapped projects. I should also note that at no point is the GL error state set.

What am I doing wrong here and why did this not cause problems on my AMD card?

(System: Ubuntu 12.04, Linux 3.2.0-49-generic, 64 bit, with the nvidia-experimental-310 driver package. All other games are functioning fine so it's most likely not a card/driver issue.)

# Answer
Solved. The problem as it happened was with alpha testing. Which makes a lot of sense:

In the code alpha testing is enabled on initialization and then isn't actually used. Removing it (and using the below mentioned matrix fix) fixes shadow mapping completely. The solution is to disable alpha when shadow mapping and re-enable it when rendering the scene with alpha. So my main loop looks more like this:

```
while (running) {
    glDisable(GL_ALPHA_TEST);

    //Shadow mapping

    glEnable(GL_ALPHA_TEST);

    //Standard draw
}

```

Although I'm not certain on this and have yet to find documentation on it I imagine the problem was probably caused by alpha testing on a non-existent colour buffer. While my AMD card coped with that just fine the NVIDIA card would always fail the GL\_GREATER alpha test because retrieving alpha from a non-existent colour buffer would yield unpredictable results.

There was also a small issue with matrices; the order of multiplication was the wrong way round so where I'd written:

```
glm::mat4 mvp = view * projection;

```

It should've been:

```
glm::mat4 mvp = projection * view;

```
> 2 votes

---
Tags: c++, opengl, linux, nvidia, amd
---


title: Rubik's cube array rotation

text:
# Question
Title: Rubik's cube array rotation
I'm about to make a 3D Rubik's cube based game in Flash AS3 and Away3d.

I don't really know how to manage the 2D arrays of the Rubik's cube.

For example, how do I rotate the corresponding arrays if I rotate a side, or just rotate a middle part?

In this stage I also don't know how to rotate those smaller cube parts all together if a side is rotating. First I was thinking of "groups" ( like in sketchup or 3ds max, blender), but that would be tricky, because the group components would change every time.

So I was thinking of just rotating each individual piece along a global axis. However, I just know the Away3d functions to rotate the cube of his local X , Y or Z axis, but how to rotate in global axis?

Does anyone know of a algorithm for doing these types of rotations?

# Answer
Since you're dealing with arrays, there doesn't have to be any actual rotations. You're just moving data around inside the arrays. For example imagine the top loop of such an array. It combines 4 of those 2D arrays into a strip. Like so:

The coordinates represent the 3D position of the cube being represented. There are of course duplicates for the corners where two faces of the same cube are represented.

Now, if we were to rotate the top layer, we don't have to do any rotating, we just shift data through the arrays:

There may be very clever ways to do this, but there's also brute force simple ways. Create a function for each axis X,Y and Z. Each of these `RotateAround` functions will take an input for which layer to rotate (1, 2, 3).

So for example, the `RotateAroundY(1)` call will do exactly as the image above shows. It will take the first row (from the top) of the Xplus, Zminus, Xminus, Zplus faces, and shift all their values through each other.

Another example, `RotateAroundX(2)` will take the second row of the (from the left) of the Yplus, Zminus, Yminus, ZPlus faces and shift all their values through each other.
> 2 votes

---
Tags: 3d, algorithm, rotation
---


# Question
Title: How'd they do it: Millions of tiles in Terraria
I've been working up a game engine similar to Terraria, mostly as a challenge, and while I've figured out most of it, I can't really seem to wrap my head around how they handle the millions of interactable/harvestable tiles the game has at one time. Creating around 500.000 tiles, that is 1/20th of what's possible in Terraria, in my engine causes the frame-rate to drop from 60 to around 20, even tho I'm still only rendering the tiles in view. Mind you, I'm not doing anything with the tiles, only keeping them in memory.

**Update**: Code added to show how I do things.

This is part of a class, which handles the tiles and draws them. I'm guessing the culprit is the "foreach" part, which iterates everything, even empty indexes.

```
...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        foreach (Tile tile in this.Tiles)
        {
            if (tile != null)
            {
                if (tile.Position.X < -this.Offset.X + 32)
                    continue;
                if (tile.Position.X > -this.Offset.X + 1024 - 48)
                    continue;
                if (tile.Position.Y < -this.Offset.Y + 32)
                    continue;
                if (tile.Position.Y > -this.Offset.Y + 768 - 48)
                    continue;
                tile.Draw(spriteBatch, gameTime);
            }
        }
    }
...

```

Also here is the Tile.Draw method, which could also do with an update, as each Tile uses four calls to the SpriteBatch.Draw method. This is part of my autotiling system, which means drawing each corner depending on neighboring tiles. texture\_\* are Rectangles, are set once at level creation, not each update.

```
...
    public virtual void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        if (this.type == TileType.TileSet)
        {
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position, texture_tl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 0), texture_tr, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(0, 8), texture_bl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 8), texture_br, this.BlendColor);
        }
    }
...

```

Any critique or suggestions to my code is welcome.

**Update**: Solution added.

Here's the final Level.Draw method. The Level.TileAt method simply checks the inputted values, to avoid OutOfRange exceptions.

```
...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        Int32 startx = (Int32)Math.Floor((-this.Offset.X - 32) / 16);
        Int32 endx = (Int32)Math.Ceiling((-this.Offset.X + 1024 + 32) / 16);
        Int32 starty = (Int32)Math.Floor((-this.Offset.Y - 32) / 16);
        Int32 endy = (Int32)Math.Ceiling((-this.Offset.Y + 768 + 32) / 16);

        for (Int32 x = startx; x < endx; x += 1)
        {
            for (Int32 y = starty; y < endy; y += 1)
            {
                Tile tile = this.TileAt(x, y);
                if (tile != null)
                    tile.Draw(spriteBatch, gameTime);

            }
        }
    }
...

```

# Answer
> 58 votes
Are you looping through all 500,000 tiles when you're rendering? If so, that's likely going to cause part of your problems. If you loop through half a million tiles when rendering, and half a million tiles when performing the 'update' ticks on them, then you're looping though a million tiles each frame.

Obviously, there's ways around this. You could perform your update ticks while also rendering, thus saving you half the time spent looping through all those tiles. But that ties your rendering code and your update code together into one function, and is generally a *BAD IDEA*.

You could keep track of the tiles that are on the screen, and only loop through (and render) those. Depending on things like the size of your tiles, and screen size, this could easily cut down the amount of tiles you need to loop through, and that would save quite a bit of processing time.

Finally, and perhaps the best option (most large world games do this), is to split your terrain into regions. Split the world into chunks of, say, 512x512 tiles, and load/unload the regions as the player gets close to, or further away from, a region. This also saves you from having to loop through far away tiles to perform any sort of 'update' tick.

(Obviously, if your engine doesn't perform any sort of update tick on tiles, you can ignore the part of this answers that mentions those.)

# Answer
> 5 votes
I see one huge mistake here not handled by any of the answers. Of course you should never draw and iterate over more tiles then you need too. What's less obviously is how you actually define the tiles. As i can see you made a tile class, i always used to do that too but it's a huge mistake. You probably have all sorts of functions in that class and that creates a lot of unnecessary processing.

You should only iterate over whats really necessary to process. So think about what you actually need for the tiles. To draw 'm you only need a texture, but you do not want to iterate over an actual image since those are large to process. You could just make a int\[,\] or even a unsigned byte\[,\] (if you do not expect more then 255 tile textures). All you need to do is iterate over these small arrays and use a switch or if statement to draw the texture.

So what do you need to update? The type, the health and the damage seems sufficient. All of these can be stored in bytes. So why not make a struct like this for the update loop:

```
struct TileUpdate
{
public byte health;
public byte type;
public byte damage;
}

```

You could actually use the type to draw the tile. So you could detach that one (make a array of it's own) from the struct so you do not iterate over the unnecessary health and damage fields in the draw loop. For updating purpose you should consider a wider area then just your screen so the game world feels more alive (entities change position off screen) but for the drawing of things you just need the tile that are visible.

If you keep the above struct it only takes 3 bytes per tile. So for saving and memory purpose this is ideal. For processing speed it does not really matter if you use int or byte, or even long int if you have a 64 bit system.

# Answer
> 2 votes
There's different encoding techniques you could use.

RLE: So you start with a coordinate (x,y) and then count how many of the same tile exist side-by-side (length) along one of the axies. Example: (1,1,10,5) would mean that starting at coordinate 1,1 there are 10 tiles side-by-side of tile type 5.

The massive array (bitmap): each element of the array holds onto the tile type that resides in that area.

EDIT: I just came across this excellent question here: Random seed function for map generation?

The Perlin noise generator looks to be like a good answer.

# Answer
> 1 votes
You should probably partition the tilemap as already suggested. For example with Quadtree structure to get rid of any potential processing(e.g. even simply looping through) of the unnecessary(not visile) tiles. This way you only process what might need processing and increasing the size of the dataset(tile map) does not cause any practical performance penalty. Of course, assuming that the tree is well balanced.

I don't want to sound dull or anything by repeating the "old", but when optimizing, always remember to use the optimizations supported by your toolchain/compiler, you should experiment with them a bit. And yes, premature optimization is the root of all evil. Trust your compiler, it knows better than you in most cases, but always, **always** measure twice and never ever rely on guesstimates. It's not about having the fast implementation of the fastest algorithm as long as you don't know where the actual bottleneck is. That's why you should use a profiler to find the slowest(hot) paths of the code and focus on eliminating(or optimizing) them. Low-level knowledge of the target architecture is often essential for squeezing out everything the hardware has to offer, so study those CPU caches and learn what a branch predictor is. See what your profiler tells you about cache/branch hits/misses. And as using some form of a tree data structure shows, it's better to have intelligent data structures and dumb algorithms, than the other way around. Data comes first, when it comes to performance. :)

# Answer
> 1 votes
Isn't it all about too many draw calls? If you put all your maps tile textures int a single image - tile atlas, there will be no texture switching while rendering. And if you batch all your tiles into a single Mesh it should be drawn in one draw call.

About the dynamic aditing... Maybe quad tree isn't such a bad idea. Assuming that tiles are being put into leaf and non-leaf nodes are just batched meshes from its childrens, root should contain all tiles batched into one mesh. Removing one tile requires nodes updates (mesh rebatching) up to the root. But at every tree level there is only 1/4th of the mesh rebatched wchich shouldnt be that much, 4\*tree\_height mesh joins?

Oh and if you use this tree in clipping algorithm you will render not always root node but some of its children, so you dont even have to update/rebatch all nodes up to root, but up to the (non-leaf) node you are rendering at the moment.

Just my thoughts, no code, maybe its nonsense.

# Answer
> 0 votes
@arrival is right. The problem is the draw code. You're buildIng an array of 4\*3000+ *draw quad* commands (24000+ *draw polygon* commands) per frame. Then these commands are processed and piped to the GPU. This is rather bad.

There are some solutions.

* Render big blocks (for example, screen size) of tiles into a static texture and draw it in a single call.
* Use shaders to draw the tiles without sending the geometry to the GPU every frame (i.e. store the tile map on the GPU).

# Answer
> 0 votes
What you need to do, is split the world into regions. Perlin noise terrain generation can use a common seed, so that even if the world isnt pregenerated, the seed will form part of the noise algo, which nicely seams the newer terrain into the existing parts. This way, you dont need to calculate more than a small buffer ahead of the players view at a time (a few screens around the current one).

In terms of handling things such as plants growing in areas far away from the players current screen, you can have timers for example. These timers would iterate through say files storing information about the plants, their position etc. You simply need to read/update/save the files in the timers. When the player reaches those parts of the world again, the engine would read in the files as normal, and present the newer plant data on screen.

I used this technique in a similar game I made last year, for harvesting and farming. The player could walk far away from the fields, and on returning, the items had been updated.

# Answer
> -2 votes
I've been thinking about how to handle that much zillions of blocks and the only thing that comes to my head is the Flyweight Design Pattern. If you don't know, I deeply suggest reading about it: might help a lot when it comes to saving memory and processing: http://en.wikipedia.org/wiki/Flyweight\_pattern

---
Tags: xna-4.0, frame-rate, memory-efficiency
---


# Question
Title: Pathfinding results in false path costs that are too high
I'm trying to implement pathfinding in a game I'm programming using this method. I'm implementing it with recursion but some of the values after the immediate circle of tiles around the player are way off. For some reason I cannot find the problem with it. This is a screen cap of the problem:

The pathfinding values are displayed in the center of every tile. Clipped blocks are displayed with the value of 'c' because the values were too high and were covering up the next value. The red circle is the first value that is incorrect. The code below is the recursive method.

```
//tileX is the coordinates of the current tile, val is the current pathfinding value, used[][] is a boolean
//array to keep track of which tiles' values have already been assigned
public void pathFind(int tileX, int tileY, int val, boolean[][] used)
{
    //increment pathfinding value
    int curVal = val + 1;

    //set current tile to true if it hasn't been already
    used[tileX][tileY] = true;

    //booleans to know which tiles the recursive call needs to be used on
    boolean topLeftUsed = false, topUsed = false, topRightUsed = false, leftUsed = false, rightUsed = false, botomLeftUsed = false, botomUsed = false, botomRightUsed = false;

    //set value of top left tile if necessary
    if(tileX - 1 >= 0 && tileY - 1 >= 0)
    {
            //isClipped(int x, int y) returns true if the coordinates givin are in a tile that can't be walked through (IE walls)
            //occupied[][] is an array that keeps track of which tiles have an enemy in them
            //
            //if the tile is not clipped and not occupied set the pathfinding value
            if(isClipped((tileX - 1) * 50 + 25, (tileY - 1) * 50 + 25) == false && occupied[tileX - 1][tileY - 1] == false && !(used[tileX - 1][tileY - 1]))
            {
                pathFindingValues[tileX - 1][tileY - 1] = curVal;

                topLeftUsed = true;

                used[tileX - 1][tileY - 1] = true;

            }

            //if it is occupied set it to an arbitrary high number so enemies find alternate routes if the best is clogged
            if(occupied[tileX - 1][tileY - 1] == true)
                pathFindingValues[tileX - 1][tileY - 1] = 1000000000;

            //if it is clipped set it to an arbitrary higher number so enemies don't travel through walls
            if(isClipped((tileX - 1) * 50 + 25, (tileY - 1) * 50 + 25) == true)
                pathFindingValues[tileX - 1][tileY - 1] = 2000000000;
    }

    //top middle
    if(tileY - 1 >= 0 )
    {
            if(isClipped(tileX * 50 + 25, (tileY - 1) * 50 + 25) == false && occupied[tileX][tileY - 1] == false && !(used[tileX][tileY - 1]))
            {
                pathFindingValues[tileX][tileY - 1] = curVal;

                topUsed = true;

                used[tileX][tileY - 1] = true;

            }

            if(occupied[tileX][tileY - 1] == true)
                pathFindingValues[tileX][tileY - 1] = 1000000000;

            if(isClipped(tileX * 50 + 25, (tileY - 1) * 50 + 25) == true)
                pathFindingValues[tileX][tileY - 1] = 2000000000;
    }

    //top right
    if(tileX + 1 <= used.length && tileY - 1 >= 0)
    {
            if(isClipped((tileX + 1) * 50 + 25, (tileY - 1) * 50 + 25) == false && occupied[tileX + 1][tileY - 1] == false && !(used[tileX + 1][tileY - 1]))
            {
                pathFindingValues[tileX + 1][tileY - 1] = curVal;

                topRightUsed = true;

                used[tileX + 1][tileY - 1] = true;

            }

            if(occupied[tileX + 1][tileY - 1] == true)
                pathFindingValues[tileX + 1][tileY - 1] = 1000000000;

            if(isClipped((tileX + 1) * 50 + 25, (tileY - 1) * 50 + 25) == true)
                pathFindingValues[tileX + 1][tileY - 1] = 2000000000;
    }

    //left
    if(tileX - 1 >= 0)
    {
            if(isClipped((tileX - 1) * 50 + 25, (tileY) * 50 + 25) == false && occupied[tileX - 1][tileY] == false && !(used[tileX - 1][tileY]))
            {
                pathFindingValues[tileX - 1][tileY] = curVal;

                leftUsed = true;

                used[tileX - 1][tileY] = true;

            }

            if(occupied[tileX - 1][tileY] == true)
                pathFindingValues[tileX - 1][tileY] = 1000000000;

            if(isClipped((tileX - 1) * 50 + 25, (tileY) * 50 + 25) == true)
                pathFindingValues[tileX - 1][tileY] = 2000000000;
    }

    //right
    if(tileX  + 1 <= used.length)
    {
            if(isClipped((tileX + 1) * 50 + 25, (tileY) * 50 + 25) == false && occupied[tileX + 1][tileY] == false && !(used[tileX + 1][tileY]))
            {
                pathFindingValues[tileX + 1][tileY] = curVal;

                rightUsed = true;

                used[tileX + 1][tileY] = true;

            }

            if(occupied[tileX + 1][tileY] == true)
                pathFindingValues[tileX + 1][tileY] = 1000000000;

            if(isClipped((tileX + 1) * 50 + 25, (tileY) * 50 + 25) == true)
                pathFindingValues[tileX + 1][tileY] = 2000000000;
    }

    //botom left
    if(tileX  - 1 >= 0 && tileY + 1 <= used[0].length)
    {
            if(isClipped((tileX - 1) * 50 + 25, (tileY + 1) * 50 + 25) == false && occupied[tileX - 1][tileY + 1] == false && !(used[tileX - 1][tileY + 1]))
            {
                pathFindingValues[tileX - 1][tileY + 1] = curVal;

                botomLeftUsed = true;

                used[tileX - 1][tileY + 1] = true;

            }

            if(occupied[tileX - 1][tileY + 1] == true)
                pathFindingValues[tileX - 1][tileY + 1] = 1000000000;

            if(isClipped((tileX - 1) * 50 + 25, (tileY + 1) * 50 + 25) == true)
                pathFindingValues[tileX - 1][tileY + 1] = 2000000000;
    }

    //botom middle
    if(tileY + 1 <= used[0].length)
    {
            if(isClipped((tileX) * 50 + 25, (tileY + 1) * 50 + 25) == false && occupied[tileX][tileY + 1] == false && !(used[tileX][tileY + 1]))
            {
                pathFindingValues[tileX][tileY + 1] = curVal;

                botomUsed = true;

                used[tileX][tileY + 1] = true;

            }

            if(occupied[tileX][tileY + 1] == true)
                pathFindingValues[tileX][tileY + 1] = 1000000000;

            if(isClipped((tileX) * 50 + 25, (tileY + 1) * 50 + 25) == true)
                pathFindingValues[tileX][tileY + 1] = 2000000000;
    }

    //botom right
    if(tileX  + 1 <= used.length && tileY + 1 <= used[0].length)
    {
            if(isClipped((tileX + 1) * 50 + 25, (tileY + 1) * 50 + 25) == false && occupied[tileX + 1][tileY + 1] == false && !(used[tileX + 1][tileY + 1]))
            {
                pathFindingValues[tileX + 1][tileY + 1] = curVal;

                botomRightUsed = true;

                used[tileX + 1][tileY + 1] = true;

            }

            if(occupied[tileX + 1][tileY + 1] == true)
                pathFindingValues[tileX + 1][tileY + 1] = 1000000000;

            if(isClipped((tileX + 1) * 50 + 25, (tileY + 1) * 50 + 25) == true)
                pathFindingValues[tileX + 1][tileY + 1] = 2000000000;
    }

    //call the method on the tiles that need it
    if(tileX - 1 >= 0 && tileY - 1 >= 0 && topLeftUsed)
        pathFind(tileX - 1, tileY - 1, curVal, used);

    if(tileY - 1 >= 0 && topUsed)
        pathFind(tileX , tileY - 1, curVal, used);

    if(tileX + 1 <= used.length && tileY - 1 >= 0 && topRightUsed)
        pathFind(tileX + 1, tileY - 1, curVal, used);

    if(tileX - 1 >= 0 && leftUsed)
        pathFind(tileX - 1, tileY, curVal, used);

    if(tileX  + 1 <= used.length && rightUsed)
        pathFind(tileX + 1, tileY, curVal, used);

    if(tileX  - 1 >= 0 && tileY + 1 <= used[0].length && botomLeftUsed)
        pathFind(tileX - 1, tileY + 1, curVal, used);

    if(tileY + 1 <= used[0].length && botomUsed)
        pathFind(tileX, tileY + 1, curVal, used);

    if(tileX  + 1 <= used.length && tileY + 1 <= used[0].length && botomRightUsed)
        pathFind(tileX + 1, tileY + 1, curVal, used);

}

```

# Answer
> 3 votes
I believe that problem in your code is with "used". You are not trying to find shortest path or cheapest. You are searching for first path you can find.

You implemented DFS algorithm (depth-first-search). Everytime you grab tile to the top left and update it's state and it's neighbors. Then you take tile to the top left from this tile and again. And it goes to the end of map. Then it goes to the top as much as it can. Then it will explore tiles in some other ways. It's definitely not growing in all direction at the same time.

Anyway: Solution may be to implement BFS (breadth-first-search) - you will put your tiles to some queue instead of processing them immediately. You shouldn't update value in neighbors, but instead just put that neighbor to the end of the queue. When you push it from queue, you will update it's value.

The best (and maybe - for you - simplest) way is to implement something like Dijkstra's algorithm \- don't use "used" variable, instead try to update value everytime - if it's higher or equal than stored value, then stop. If it's lower, update value in tile and proceed to neighbors (again - compare value). But Dijkstra is probably also more suitable with BFS-based search, not DFS.

---
Tags: java, 2d, path-finding, recursion
---


title: Rotate 2d sprite towards pointer

text:
# Question
Title: Rotate 2d sprite towards pointer
I'm using Crafty.js and am trying to point a sprite towards the mouse pointer.

I have a function for getting the degree between two points and I'm pretty sure it works mathematically (I have it under unit tests). At least it responds that the degree between { 0,0} and {1,1} is 45, which seems right.

However, when I set the sprite rotation to the returned degree, it's just wrong all the time. If I manually set it to 90, 45, etc, it gets the right direction..

I have a jsfiddle that shows what I've done so far.

Any ideas?

# Answer
> 4 votes
With some experimentation, your angle appears to be inverted, but otherwise correct. Negating your angle works:

```
obj1.rotation = -Engine.degree(pos2, pos1);

```

And the modified jsFiddle.

---
Tags: 2d, javascript, rotation, crafty, mathematics
---


# Question
Title: How to manage a multiplayer asynchronous environment in a game
I'm working on a game where players can setup villages, which can contain defending units. Any of these units (each on their own tiles) can be set to "campaign" which means they are no longer defending but can now be used to attack other villages. And each unit on a tile can have up to a 100 health. So far so good. Oh and it's all asynchronous so even though the server will be aware that your village is being attacked, you won't be until the attack is over.

The issue I'm struggling with, is the following situation.

Let's say a unit on a tile is being attacked by a player from another village. The other player see's your village and is attacking your units. You don't know this is happening though, so you set your unit to campaign and off you go to attack another village, with the unit which itself is actually being attacked by this other player. The other player stops attacking your village and leaves your unit with say a health of 1, which is then saved to the server. You however have this same unit are attacking another village with it, but now you discover that even though it started off with a 100 health, now mysteriously it only has 1...

Solutions? Ideas?

**Edit**

The simplest solutions are often the best. I referred to Clash of clans below, well after a bit more digging it seems that in CoC you can only attack players that are offline! ha, that almost solves the problem. I say almost because there's still the situation where a players village could be in the process of being attacked when they come back online, still need to address that.

**Edit 2**

A solution to the "What happens when a player is attacking your village and you come online" issue, could be the attacking player just get's kicked out of the village at that point and just get's whatever they had won up to that point, it's a bit of a fudge but it might work.

# Answer
Some ideas to resolve this situation and possibly report the events to the user.

**Idea 1**

You can display a kind of event log to the player that he knows what happend to their units in the meantime.

**Idea 2**

The units which got attacked and which health are below a threashold say 50 HP don't take part in the next battle and must heal themself or stay at your village for fighting for death.

**Idea 3**

Implement a 3 state logic of the units

* Defending
* Pending
* Attacking/campaign

so the 2nd state is used to

* resolve all taken damages ( Defending -\> Attacking/campaign )
* resolve all damages given (possibly not needed?)

so to change the mode the state must pass the "pending"/resolving state.

With that this problem doesn't appear.
> 1 votes

---
Tags: multiplayer
---


# Question
Title: Multithreading in lwjgl getting rid of sleep.
I'm trying to use multithreading in my game. However, I can't seem to get rid of the sleep.

If I don't it's a blank screen, as there is no time for the computer to actually render the triangleMob as it can't access getArrayList(), in my main class I have a TriangleMob arraylist. If I delay it, then it can access the previousMob and it renders. If I don't, then it's blank screen.

Can I get rid of the delay? Also, is this a bad way to multithread?

Surely, this should be fast. I need multithreading so can you please not suggest not using it.

```
public class TriangleMob extends Thread implements Runnable {

        private static int count=0;

        private int objectDisplayList;
        private static ArrayList<TriangleMob> previousMob = new ArrayList<TriangleMob>();
        private static ArrayList<TriangleMob> currentMob = new ArrayList<TriangleMob>();
        private static ArrayList<TriangleMob> laterMob = new ArrayList<TriangleMob>();

        private Vector3f position = new Vector3f(0f,0f,0f);
        private Vector3f movement = new Vector3f(0f,0f,0f);

        public TriangleMob()
        {

                // Create the display list
                CreateDisplayList();

                count++;
        }

        public TriangleMob(Vector3f position)
        {

                // Create the display list
                CreateDisplayList();

                this.position = position;
                count++;
        }

        private void CreateDisplayList()
        {
                objectDisplayList = glGenLists(1);
                glNewList(objectDisplayList, GL_COMPILE);
                {
                        double topPoint = 0.75;
                        glBegin(GL_TRIANGLES);
                        glColor4f(1, 1, 0, 1f);
                        glVertex3d(0, topPoint, -5);
                        glColor4f(0, 0, 1, 1f);
                        glVertex3d(-1, -0.75, -4);
                        glColor4f(0, 0, 1, 1f);
                        glVertex3d(1, -.75, -4);

                        glColor4f(1, 1, 0, 1f);
                        glVertex3d(0, topPoint, -5);
                        glColor4f(0, 0, 1, 1f);
                        glVertex3d(1, -0.75, -4);
                        glColor4f(0, 0, 1, 1f);
                        glVertex3d(1, -0.75, -6);

                        glColor4f(1, 1, 0, 1f);
                        glVertex3d(0, topPoint, -5);
                        glColor4f(0, 0, 1, 1f);
                        glVertex3d(1, -0.75, -6);
                        glColor4f(0, 0, 1, 1f);
                        glVertex3d(-1, -.75, -6);

                        glColor4f(1, 1, 0, 1f);
                        glVertex3d(0, topPoint, -5);
                        glColor4f(0, 0, 1, 1f);
                        glVertex3d(-1, -0.75, -6);
                        glColor4f(0, 0, 1, 1f);
                        glVertex3d(-1, -.75, -4);

                        glEnd();
                        glColor4f(1, 1, 1, 1);
                }
                glEndList();
        }

        public static int getCount() {
                return count;
        }

        public Vector3f getMovement() {
            return movement;
        }

        public Vector3f getPosition() {
            return position;
        }

        public synchronized int getObjectList() {
            return objectDisplayList;
        }

        public synchronized static ArrayList<TriangleMob> getArrayList(){
            if(previousMob != null) {
                return previousMob;
            }

            previousMob.add(new TriangleMob());

            return previousMob;
        }

        public synchronized  void move(Vector3f movement) {

                // If you want to move in all 3 axis
                position.x += movement.x;
                position.y += movement.y;
                position.z += movement.z;

        }

        public synchronized void render() {
            glPushMatrix();

            glTranslatef(-position.x, -position.y, -position.z);

            glCallList(objectDisplayList);

            glPopMatrix();
        }

        public synchronized static void setTriangleMob(ArrayList<TriangleMob> triangleMobSet) {
            laterMob = triangleMobSet;
        }

        private synchronized void setPreTriangleMob(ArrayList<TriangleMob> currentMob2) {
            previousMob = currentMob2;
        }

        public void run(){
            while(true) {
                if(laterMob == null) {
                    currentMob = laterMob;
                    System.out.println("Copying");
                }

                for(int i=0; i<currentMob.size(); i++) {
                    currentMob.get(i).move(new Vector3f(0.1f,0.01f,0.01f));
                }

                setPreTriangleMob(currentMob);

                try {
                    sleep(1L);
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
        }
    }

```

# Answer
> 0 votes
Your TriangleMob thread starves the render thread. Nice. The Synchronized keyword on a method uses the object the method belongs to as monitor/lock object. This is probably not what your want. You even have synchronized static method. Why? This will use the class object as lock. Very bad.

Only synchronize on objects (better seperate monitor objects) that threads need to share.

Your render thread needs the list of items it should render. Your Mob thread updates this list. Minimize the time the lock is used, so both threads have a chance to access the list.

Also each TriangleMob Object in your example updates and reads the same synchronized static lists, which worsens the thread starvation issue.

Create seperate manager classes for rendering and updating the game state. Each manager has a list of game objects. Then you only need to synchronize when you push the updated game state (read mob list) to the render manager. Better put the updated game state in a shared object from which the render manager reads. The shared object handles the synchronization of its data.

Why even use multithreading? Have you tried a single threaded approach first? Multithreading is notoriously hard and is one of the problem computer science hasn't solved very well yet. You will have to deal with shared state which must be synchronized to avoid concurrent reads and writes. You will run into deadlocks, thread starvation and other nice issues. All issues which are hard to diagnose and fix. Even it works the performance might be worse than a singlethreaded approach due to suboptimal locking (have I mentioned that multithreaded programming is hard? ;-) )

Keep it simple.

---
Tags: java, lwjgl, multithreading
---


title: Better solution for boolean mixing?

text:
# Question
Title: Better solution for boolean mixing?
Sorry if this question has been asked in the past, but searching Google and here didn't yield relevant results, so here goes.

I'm working on a fragment shader that implements both conditional/boolean diffuse and bump mapping (that is to say, you don't *need* a diffuse texture or a normals texture, and if they're not present, they're simply changed to default values).

My current solution is to use a uniform float to say "mix amount". For example, computing the diffuse texel works as:

```
// Compute diffuse amount scaled by vCol
// If no texture is present (mDif = 0.0), then DiffuseTexel = vCol
// kT[0] is the diffuse texture
// vTex is the texture co-ordinates
// mDif is the uniform float containing the mix amount (either 0.0 or 1.0)
vec4 DiffuseTexel = vCol*mix(vec4(1.0), texture2D(kT[0], vTex), mDif);

```

While that works great and all, I was wondering if there's a better way of doing this, as I will never have any use for in-between values for funky effects. I know that perhaps the best solution is to simply write separate shaders for mDif=0.0 and mDif=1.0, but I'd like a more elegant solution than splicing shaders before compiling or writing multiple shader files and keeping each one updated.

Any ideas are greatly appreciated. =)

# Answer
Branching should be sufficiently fast on modern cards that you don't need to worry about it, and you can always profile it if you think there's a bottleneck. Branching will also make for somewhat more readable code, since your intent is much clearer, and the code you're currently using does imply the possibility of a "25% mix" between the two, for example.

Your current example also causes the texture to be sampled, even if it would be the "default" value, which you could avoid with an actual branch, potentially.

But there's really nothing *horrible* with your current solution, and if you have a need to support cards/versions that are old enough that branching *isn't* very fast, it's probably better.
> 4 votes

---
Tags: glsl, fragment-shader
---


title: Efficient Way to Draw Grids in XNA

text:
# Question
Title: Efficient Way to Draw Grids in XNA
So I am working on a game right now, using Monogame as my framework, and it has come time to render my world. My world is made up of a grid (think Terraria but top-down instead of from the side), and it has multiple layers of grids in a single world. Knowing how inefficient it is to call SpriteBatch.Draw() a lot of times, I tried to implement a system where the tile would only be drawn if it wasn't hidden by the layers above it. The problem is, I'm getting worse performance by checking if it's hidden than when I just let everything draw even if it's not visible. So my question is: how to I efficiently check if a tile is hidden to cut down on the draw() calls?

Here is my draw code for a single layer, drawing floors, and then the tiles (which act like walls):

```
public void Draw(GameTime gameTime)
    {
        int drawAmt = 0;

        int width = Tile.TILE_DIM;
        int startX = (int)_parent.XOffset;
        int startY = (int)_parent.YOffset;

        //Gets the starting tiles and the dimensions to draw tiles, so only onscreen tiles are drawn, allowing for the drawing of large worlds
        int tileDrawWidth = ((CIGame.Instance.Graphics.PreferredBackBufferWidth / width) + 4);
        int tileDrawHeight = ((CIGame.Instance.Graphics.PreferredBackBufferHeight / width) + 4);
        int tileStartX = (int)MathHelper.Clamp((-startX / width) - 2, 0, this.Width);
        int tileStartY = (int)MathHelper.Clamp((-startY / width) - 2, 0, this.Height);

        #region Draw Floors and Tiles
        CIGame.Instance.GraphicsDevice.SetRenderTarget(_worldTarget);
        CIGame.Instance.GraphicsDevice.Clear(Color.Black);
        CIGame.Instance.SpriteBatch.Begin();

        //Draw floors
        for (int x = tileStartX; x < (int)MathHelper.Clamp(tileStartX + tileDrawWidth, 0, this.Width); x++)
        {
            for (int y = tileStartY; y < (int)MathHelper.Clamp(tileStartY + tileDrawHeight, 0, this.Height); y++)
            {
                //Check if this tile is hidden by layer above it
                bool visible = true;
                for (int i = this.LayerNumber; i <= _parent.ActiveLayer; i++)
                {
                    if (this.LayerNumber != (_parent.Layers - 1) && (_parent.GetTileAt(x, y, i + 1).Opacity >= 1.0f || _parent.GetFloorAt(x, y, i + 1).Opacity >= 1.0f))
                    {
                        visible = false;
                        break;
                    }
                }

                //Only draw if visible under the tile above it
                if (visible && this.GetTileAt(x, y).Opacity < 1.0f)
                {
                    Texture2D tex = WorldTextureManager.GetFloorTexture((Floor)_floors[x, y]);
                    Rectangle source = WorldTextureManager.GetSourceForIndex(((Floor)_floors[x, y]).GetTextureIndexFromSurroundings(x, y, this), tex);
                    Rectangle draw = new Rectangle(startX + x * width, startY + y * width, width, width);

                    CIGame.Instance.SpriteBatch.Draw(tex, draw, source, Color.White * ((Floor)_floors[x, y]).Opacity);
                    drawAmt++;
                }
            }
        }

        //Draw tiles
        for (int x = tileStartX; x < (int)MathHelper.Clamp(tileStartX + tileDrawWidth, 0, this.Width); x++)
        {
            for (int y = tileStartY; y < (int)MathHelper.Clamp(tileStartY + tileDrawHeight, 0, this.Height); y++)
            {
                //Check if this tile is hidden by layers above it
                bool visible = true;
                for (int i = this.LayerNumber; i <= _parent.ActiveLayer; i++)
                {
                    if (this.LayerNumber != (_parent.Layers - 1) && (_parent.GetTileAt(x, y, i + 1).Opacity >= 1.0f || _parent.GetFloorAt(x, y, i + 1).Opacity >= 1.0f))
                    {
                        visible = false;
                        break;
                    }
                }

                if (visible)
                {
                    Texture2D tex = WorldTextureManager.GetTileTexture((Tile)_tiles[x, y]);
                    Rectangle source = WorldTextureManager.GetSourceForIndex(((Tile)_tiles[x, y]).GetTextureIndexFromSurroundings(x, y, this), tex);
                    Rectangle draw = new Rectangle(startX + x * width, startY + y * width, width, width);

                    CIGame.Instance.SpriteBatch.Draw(tex, draw, source, Color.White * ((Tile)_tiles[x, y]).Opacity);
                    drawAmt++;
                }
            }
        }

        CIGame.Instance.SpriteBatch.End();

        Console.WriteLine(drawAmt);
        CIGame.Instance.GraphicsDevice.SetRenderTarget(null); //TODO: Change to new rendertarget instead of null
        #endregion
    }

```

So I was wondering if this is an efficient way, but I'm going about it wrongly, or if there is a different, more efficient way to check if the tiles are hidden.

EDIT: For example of how much it affects performance: using a world with three layers, allowing everything to draw no matter what gives me 60FPS, but checking if its visible with all of the layers above it gives me only 20FPS, while checking only the layer immediately above it gives me a fluctuating FPS between 30 and 40FPS.

# Answer
> 1 votes
The first thing I would consider is exactly how many times you're going to call `SpriteBatch.Draw()` in each frame. You might find that it's not as inefficient as you think and sometimes the simplest implementation is good enough.

That said, there are lots of ways to optimize your code and rather than trying to spell it out here I suggest you read this great answer.

At a guess, without being able to see your project structure, I would say you might be hitting the batch limit because you're using too many textures. The solution is to use texture atlases (aka sprite sheets).

Okay, now to the real meat of your problem. You seem to be doing a lot of work inside your loops. It concerns me that you have a 3rd loop inside your first 2 loops to check the layer visibility and that you repeat nearly identical code after drawing floors to draw tiles.

It's also hard to tell if `GetTileAt`, `GetFloorAt`, `GetTileTexture`, `GetSourceForIndex` or `GetTextureIndexFromSurroundings` are efficient operations. If any of them are not, it's going to affect performance because your repeating them for every tile twice.

Some other things you can do is move any calculations outside the loops that don't need to be repeated more than once. For example:

```
int xMax =  (int)MathHelper.Clamp(tileStartX + tileDrawWidth, 0, this.Width)
for (int x = tileStartX; x < xMax; x++)

```

But honestly, I don't think your problem is going to be solved by a few simple tweaks. I'm guessing that most of the tiles don't change between frames so I would consider re-factoring the code to pre-calculate as much information as possible before getting into the draw calls.

You could take a look at some open source tile rendering engines like xTile because they are already reasonably efficient, or better yet you might be able to use tIDE in your project and get the benefit of map editor.

Last but not least, if you have access to a performance profiler, use it to help you find the problems. Doing it by eye is hard at best and even the experienced guys use profilers.

---
Tags: xna, monogame, grid, efficiency
---


title: Collision for mobile game

text:
# Question
Title: Collision for mobile game
I'm writing a little game in as3 using Starling, and I need to check collision between 2 boats that can rotate. I don't need the pixel perfect collision, but bounds collision is not enough too. The boat look more or less like this:

I was thinking about create one square on the back of the boat and a triangle on the front, than for each boat, check if the square collide with the other boat square or triangle, and the same for the triangle.

I just don't know how to do that, I don't know if it's possible with the Shape.hitTest, or if it's the best way to do that.

What can I do?

# Answer
> 1 votes
You can treat each boat as a rectangle, and then check for collisions as they rotate using projected axis.

There is an excellent class for doing just that, by Jozef Chút'ka, available at GitHub.

You can also check out his blog post about it: http://blog.yoz.sk/2010/11/4-000-000-rectangle-collisions-per-second/

```
package sk.yoz.math
{
    public class FastCollisions
    {
        public static function rectangles(
            r1p1x:Number, r1p1y:Number, r1p2x:Number, r1p2y:Number,
            r1p3x:Number, r1p3y:Number, r1p4x:Number, r1p4y:Number,
            r2p1x:Number, r2p1y:Number, r2p2x:Number, r2p2y:Number,
            r2p3x:Number, r2p3y:Number, r2p4x:Number, r2p4y:Number):Boolean
        {
            if(!isProjectedAxisCollision(r1p1x, r1p1y, r1p2x, r1p2y,
                r2p1x, r2p1y, r2p2x, r2p2y, r2p3x, r2p3y, r2p4x, r2p4y))
                return false;

            if(!isProjectedAxisCollision(r1p2x, r1p2y, r1p3x, r1p3y,
                r2p1x, r2p1y, r2p2x, r2p2y, r2p3x, r2p3y, r2p4x, r2p4y))
                return false;

            if(!isProjectedAxisCollision(r2p1x, r2p1y, r2p2x, r2p2y,
                r1p1x, r1p1y, r1p2x, r1p2y, r1p3x, r1p3y, r1p4x, r1p4y))
                return false;

            if(!isProjectedAxisCollision(r2p2x, r2p2y, r2p3x, r2p3y,
                r1p1x, r1p1y, r1p2x, r1p2y, r1p3x, r1p3y, r1p4x, r1p4y))
                return false;

            return true;
        }

        public static function isProjectedAxisCollision(
            b1x:Number, b1y:Number, b2x:Number, b2y:Number,
            p1x:Number, p1y:Number, p2x:Number, p2y:Number,
            p3x:Number, p3y:Number, p4x:Number, p4y:Number):Boolean
        {
            var x1:Number, x2:Number, x3:Number, x4:Number;
            var y1:Number, y2:Number, y3:Number, y4:Number;
            if(b1x == b2x)
            {
                x1 = x2 = x3 = x4 = b1x;
                y1 = p1y;
                y2 = p2y;
                y3 = p3y;
                y4 = p4y;

                if(b1y > b2y)
                {
                    if((y1 > b1y && y2 > b1y && y3 > b1y && y4 > b1y) ||
                       (y1 < b2y && y2 < b2y && y3 < b2y && y4 < b2y))
                        return false;
                }
                else
                {
                    if((y1 > b2y && y2 > b2y && y3 > b2y && y4 > b2y) ||
                       (y1 < b1y && y2 < b1y && y3 < b1y && y4 < b1y))
                        return false;
                }
                return true;
            }
            else if(b1y == b2y)
            {
                x1 = p1x;
                x2 = p2x;
                x3 = p3x;
                x4 = p4x;
                y1 = y2 = y3 = y4 = b1y;
            }
            else
            {
                var a:Number = (b1y - b2y) / (b1x - b2x);
                var ia:Number = 1 / a;
                var t1:Number = b2x * a - b2y;
                var t2:Number = 1 / (a + ia);

                x1 = (p1y + t1 + p1x * ia) * t2;
                x2 = (p2y + t1 + p2x * ia) * t2;
                x3 = (p3y + t1 + p3x * ia) * t2;
                x4 = (p4y + t1 + p4x * ia) * t2;

                y1 = p1y + (p1x - x1) * ia;
                y2 = p2y + (p2x - x2) * ia;
                y3 = p3y + (p3x - x3) * ia;
                y4 = p4y + (p4x - x4) * ia;
            }

            if(b1x > b2x)
            {
                if((x1 > b1x && x2 > b1x && x3 > b1x && x4 > b1x) ||
                   (x1 < b2x && x2 < b2x && x3 < b2x && x4 < b2x))
                    return false;
            }
            else
            {
                if((x1 > b2x && x2 > b2x && x3 > b2x && x4 > b2x) ||
                   (x1 < b1x && x2 < b1x && x3 < b1x && x4 < b1x))
                    return false;
            }
            return true;
        }

        public static function pointInRectangle(px:Number, py:Number,
            r1x:Number, r1y:Number, r2x:Number, r2y:Number,
            r3x:Number, r3y:Number, r4x:Number, r4y:Number):Boolean
        {
            var a:Number, x:Number, y:Number;
            if(r1x == r2x)
            {
                x = r1x, y = py;
                if(y > (r1y > r2y ? r1y : r2y)) return false;
                if(y < (r1y < r2y ? r1y : r2y)) return false;
            }
            else if(r1y == r2y)
            {
                x = px, y = r1y;
            }
            else
            {
                a = (r1y - r2y) / (r1x - r2x);
                x = (py - r2y + r2x * a + px / a) / (a + 1 / a);
                y = py + (px - x) / a;
            }

            if(x > (r1x > r2x ? r1x : r2x)) return false;
            if(x < (r1x < r2x ? r1x : r2x)) return false;

            if(r2x == r3x)
            {
                x = r2x, y = py;
                if(y > (r2y > r3y ? r2y : r3y)) return false;
                if(y < (r2y < r3y ? r2y : r3y)) return false;
            }
            else if(r2y == r3y)
            {
                x = px, y = r2y;
            }
            else
            {
                a = (r2y - r3y) / (r2x - r3x);
                x = (py - r3y + r3x * a + px / a) / (a + 1 / a);
                y = py + (px - x) / a;
            }

            if(x > (r2x > r3x ? r2x : r3x)) return false;
            if(x < (r2x < r3x ? r2x : r3x)) return false;
            return true;
        }
    }
}

```

I hope that helps. Cheers!

---
Tags: collision-detection, flash
---


# Question
Title: How can I compile SM 3.0 effects in D3D11 in SlimDX?
```
var bytecode = ShaderBytecode.CompileFromFile("shaders\\testShader.fx", "fx_5_0", ShaderFlags.None, SlimDX.D3DCompiler.EffectFlags.None, null, null, out str);
var effect = new SlimDX.Direct3D11.Effect(gpu.Device, bytecode);

```

This works fine but if I try to use another shader model like 4.0 or 3.0 it throws an error on the new effect creation:

```
E_FAIL: An undetermined error occurred (-2147467259)

```

How do I compile older shaders? And I've read about device context but I can't find any information on how to use them to maintain DX9 compatibility.

# Answer
"fx\_5\_0" refers to the *effect* file version, not the shader profile. Basically it's just telling the HLSL / effect compiler which version of syntax to allow.

You actually control which shader profiles are used when you use the CompileShader function inside your techniques in the effect, like so:

```
technique11 RenderSceneWithTexture1Light
{
    pass P0
    {
        SetVertexShader( CompileShader( vs_4_0_level_9_3, RenderSceneVS( 1, true, true ) ) );
        SetGeometryShader( NULL );
        SetPixelShader( CompileShader( ps_4_0_level_9_3, RenderScenePS( true ) ) );
    }
}

```

That extra "\_level\_9\_3" at the end specifies that you're making use of the 10level9 functionality. You can see what each feature level supports here.

Unfortunately, there is no feature level that corresponds to SM 3.0 hardware. Your options are to stick with SM 2.x support in feature level 9\_3 or to jump up to full D3D10-era SM 4.0.
> 3 votes

---
Tags: directx, directx11, directx9, slimdx
---


# Question
Title: Can I count all the allocated textures in D3D11?
Is it somehow possible to get the count of all texture objects on a device?

# Answer
> 2 votes
No, not really.

If the debug layer is enabled, you can utilize ID3D11Debug::ReportLiveObjects. But this will produce a debug-output report of *all* live objects, it's not easily accessible your code for parsing. It's also going to require the debug layer, which means you're not going to be able to use it on shipping applications to make meaningful decisions within your program.

You can consider using PIX, or the VS 2012 graphics debugger, which can provide information about allocated resource counts. But again, that's not something you can utilize in your own code on shipping products.

If you need this information to make an actual, important decision at runtime within your game (and I'd be curious what that decision is), you will need to track it yourself by wrapping the creation of all resources (like textures) you want to count.

---
Tags: directx11
---


# Question
Title: Why would an online MMO throttle actions per day?
I started playing Die2Nite and was surprised that it has such a strict limit on the number of actions per day. After a while, I figured it was just part of the charm.

I also started playing Magic Duel and it has a similar mechanic that limits the amount of actions per day.

Is there a game design principle behind a decision to limit actions per day in an MMO?

# Answer
Some reasons I can think of, some of which may or may not apply to your specific examples:

* Monetization: limiting the amount of actions in an addictive free to play game, and then offering to unlock more actions by paying money is a common way to monetize games.
* Game balance: by limiting the amount of actions a player can make in a day, you can force players to think more about their strategies, instead of simply giving advantage to players who endlessly grind on your game. Think of this as the extrapolation of the "1 move per player" rule of most board games.
* Regulations: some countries, like South Korea, have regulations that online game providers have to follow. I think some games have to limit the amount of time players can be connected per day.

You have to be careful though, because if your game is not fun enough, or if players begin to feel helpless, the fact that you can only do so much in a determined period of time could lead to your ruin.
> 15 votes

# Answer
In most MMOs without such a constraint, success in the game depends solely on how much time someone spends on it.

This makes these games very frustrating for people who have full-time jobs and thus can not compete with those who have time to play several hours each day.

By limiting the actions per day you level the playing field between these people and make the game enjoyable for both types of players.

Related question: MMORPG design for time-limited players

Related South Park episode: http://www.southparkstudios.com/full-episodes/s10e08-make-love-not-warcraft
> 2 votes

---
Tags: mmo
---


# Question
Title: What benefits does a game design degree have for a hobby game programmer?
I am interested in studying game design, not because I want a job in the games industry, but because I am interested in the subject itself. I read the following questions, but they mostly deal with the effects on your career in game industry.

First I thought a game development degree could be beneficial. But from the websites of colleges that offer such degrees, I feel like its more about basic programming with examples from games.

This college offers game design degrees, for example.

My question is, can I benefit from such a degree when I already have a degree in Computer Science, I already know programming, I'm already developing a game and finally, I have this site to help me when I get stuck?

# Answer
> 4 votes
I think that you can *absolutely* benefit from expanding your knowledge base and experience, especially as concerns other disciplines within the industry you work in (as a professional or a hobbyist).

*However*, if you are talking about spending years of your life and tens of thousands of dollars to do so, and you're not really expecting to take that investment and capitalize on it to achieve a return (which is to say: get a job as a game designer), it's probably a waste of that time and money(\*).

You'd be better offer perusing the curriculum of any interesting-looking programs and investigating the relevant topics on your own, in this case.

(\*) True, some people spend a lot of time and money on hobbies, but that doesn't mean you should spend that money unwisely. "Game design" and "game development" degrees can be an unwise expenditure even for somebody who wants a career in the field; they are often very poor or have very poor reputations within the industry.

# Answer
> 0 votes
Some thoughts to consider:

Doing a full time study includes probably a lot of stuff that you are already familiar with as a programmer, or that will not help you at all since the study will probably include some subjects that are not related to game programming at all.

You only get relevant information from people that are at least working part of their time in the game industry. A teacher working full time at school, and not having any hobby game projects, is not really a person I would want to learn from. Except mathematics or physics, which is theoretical stuff that doesn't change suddenly.

If you not need the degree, you could eventually only sit in some courses. (Nobody would have noticed someone who wasn't registered, at the place where I used to study ;-) ) Pick the topics that interest you, and maybe make some contacts with some student's so they can let you know which subjects are interesting.

Studying in the web and joining some groups and working on Mods, could probably be even more helpful. Working in a good group will let you recognize some commonly used technics and such.

A good point to get common knowledge about game design would be Books I guess.

---
Tags: game-design, education
---


# Question
Title: How can I determine if a cube is adjacent to another cube, and optimize its buffers if so?
I'm trying to optimize the rendering of a collection of cubes, (based on an answer I was given to another question I asked). I understand the logic behind occlusion culling, but I'm having trouble with the code.

When I create a cube, I want to determine if that cube is touching another existing cube, and if so I don't want to generate the redundant data in my vertex or index buffers.

I'm planning on making a method that I call from my cube constructor so that everytime I create a cube, these checks are made, and neither occluded face is ever drawn.

How would I go about this?

# Answer
> 1 votes
It sounds like you're taking a very OOP approach to this problem, when really you should be taking a more functional approach (just the approach - we're not going "all-in" here - we're basically just applying functions to buffers).

Instead of a cube `class` (reference type) with a constructor that gets "created", simply have a cube `struct` (value type) with a *very* small memory footprint. This could be as simple as an `int` that indicates what kind of cube it is. The important thing is to, like an integer, have a "zero" value that represents an empty space.

Then create an array of these. For simplicity you can use a 3D array. Later on you might want to consider a 1D array (slightly faster in .NET) and trying to read through it while touching as little memory as possible. But for now this will do - it is far better than allocating thousands of cube objects flung all over heap memory!

The position of each cube is implicitly defined by its position in the array.

Then, taking a functional approach, you transform that "cube" data into "vertex" data for a given chunk (or the whole world, if it's small enough). A method to do that transformation might have code that looks a little something like this:

```
for(int y = 0; y < height; y++)
{
    for(int x = 0; x < width; x++)
    {
        for(int z = 0; z < depth; z++)
        {
            if(x-1 >= 0 && cubes[x-1, y, z])
                AddFace(x, y, z, Face.Left);
            if(x+1 < width  && cubes[x+1, y, z])
                AddFace(x, y, z, Face.Right);

            if(z-1 >= 0 && cubes[x, y, z-1])
                AddFace(x, y, z, Face.Back);
            if(z+1 < depth  && cubes[x, y, z+1])
                AddFace(x, y, z, Face.Front);

            if(y-1 >= 0 && cubes[x, y-1, z])
                AddFace(x, y, z, Face.Bottom);
            if(y+1 < depth  && cubes[x, y+1, z])
                AddFace(x, y, z, Face.Top);
        }
    }
}

```

This takes advantage of the fact the cube data is stored in a spatially meaningful way.

I'll leave `AddFace` as an exercise. But basically it should append appropriate vertices and indices to a `List` of faces for the whole chunk. Which you'd then use to `SetData()` to your chunk's `VertexBuffer` and `IndexBuffer` (via `ToArray()`).

(As mentioned in comments in our discussion over here, you can save yourself the copying that `ToArray()` does by using an array directly, instead of a `List`, and manually managing your count and capacity. Take a look at the code in this answer)

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