# Question
Title: What is a simple deformer in which vertices deform linearly with control points?
In my project I want to deform a complex mesh, using a simpler 'proxy' mesh.

In effect, each vertex of the proxy/collision mesh will be a control point/bone, which should deform the vertices of the main mesh attached to it depending on weight, but where the weight is not dependant on the absolute distance from the control point but rather distance relative to the other affecting control points.

The point of this is to preserve complex three dimensional features of the main mesh while using physics implementations which expect something far simpler, low resolution, single surface, etc. Therefore, the vertices must deform linearly with their respective weighted control points (i.e. no falloff fields or all the mesh features will end up collapsed) - as if each vertex was linked to a point on the plane created by the attached control points and deformed with it.

I have tried implementing the weight computation algorithm in this paper (page 4) but it is not working as expected and I am wondering if it is really the best way to do what I want.

**What is the simplest way to 'skin'\* an arbitrary mesh, to another arbitrary mesh?**

\*By skin I mean I need an algorithm to determine the best control points for a vertex, and their weights.

# Answer
> 1 votes
One thing you could do, is generate the 3D Voronoi diagram of the vertices of the simple mesh. This will partition space into a number of cells, where everything inside a cell is closer to the vertex corresponding to that cell, than to any other vertex. You can then compute a 3D equivalent of the Delaunay triangulation, which will give you a set of tetrahedrons. Every point inside such a tetrahedron can be expressed as a linear combination of the four vertices of the tetrahedron.

For every vertex `p` in the high-resolution mesh, you can look up the tetrahedron that the point is in, which will give you four vertices of the simple mesh (call them `v0`, `v1`, `v2`, `v3`). If you translate every vector by `-v0`, it is possible to write the new point `p' = p - v0` as a linear combination of `v1'`, `v2'`, and `v3'`. This gives you a new eqation for `p'`, namely `p' = u * v1' + v * v2' + w * v3'`, where `u`, `v` and `w` are the weights. Now you can write the point `p` as `v0 + u * (v1 - v0) + v * (v2 - v0) + w * (v3 - v0)`. If the simple mesh is deformed, `v0`, `v1`, `v2` and `v3` will change, and `p` will change accordingly. This deformation will depend on at most fourr nearby simple vertices, and thus a deformation on one side of the simple mesh will have no effect on the other side of the high-resolution mesh (unlike the distance-based falloff, where every simple vertex still affects every high-resolution vertex).

Please note that this is *not* a simple way to skin the mesh. If you are looking for a simpler solution, I would suggest manually assigning weights to the vertices. (A package like Blender allows you to weight-paint vertices.)

---
Tags: physics, procedural-generation, 3d-meshes, skinning
---


# Question
Title: Getting Started with Component Architecture: DI?
**TLDR:** if I have entities like `Ship` and `Bullet` and components like `Positionable` and `Drawable`, should I create interfaces for each component and inject them into my entities using DI, or should I be doing something else?

(In this case, `Ship` would extend `IPositionable` and have an instance of a `PositionableComponent` which is injected by DI. Any calls to `ship.getX` or `ship.setX` would be implemented as `myPositionable.getX` or `myPositionable.setX`.)

---

I just moved away from MVC towards something more component-architecture-*like*. I have no concept of messages yet (it's rough prototype code), objects just get internal properties and values of other classes for now.

That issue aside, it seems like this is turning into an aspect-oriented-programming challenge. I've noticed that all entities with, for example, a `position` component will have similar properties (get/set X/Y/Z, rotation, velocity).

Is it a common practice, and/or good idea, to push these behind an interface and use dependency injection to inject a generic class (eg. PositionComponent) which already has all the boiler-plate code?

(I'm sure the answer will affect the model I use for message/passing)

**Edit:** The DI model I'm proposing is as follows.

* Create entity classes like `Ship` and `Bullet`
* Create interfaces to represent these components. Eg. I can expect a `PositionableComponent.getX` method.
* Create component classes like `PositionableComponent`, `DrawableComponent` which implement my interface
* Entities like `Ship` will have components like `PositionableComponent`. They will implement the methods by internally keeping an instance of a `positionalbleComponent` and redirecting all interface calls to the component.
* My DI framework will (presumably automatically) wire up components by interface, eg. `Ship._positionableComponent = new PositionableComponent()`. This is how NInject works, which is the only framework I've ever used (and I'm working in Haxe now).

This will allow me to work on a higher level (ships contain components), and reduce boilerplate code (component implementations), but introduces duplicate code (redirecting to the internal component). Since I'm working in Haxe, I *may* be able to avoid writing that boilerplate by hand.

However, the advantage is that I can override component behaviours. If `undeadMonster.IsAlive()` should return true when its HP is above -100 (instead of 0), I can easily code this, and the change becomes very visible from the code level.

But I'm not sure if I'm solving this correctly.

# Answer
I'm not sure if you really understand how a component system should work, since you talk about things like "entity classes" and their interfaces. A component system does not consist of classes. It consists of data and behavior. Please bear with me here.

In an entity system, all objects in the game are entities. An entity is not a class, it doesn't even have to be an object. It can be just a little blob of data, usually an identifier with a list of components, but it can even be limited to just a unique identifier. All you need it something to tie together a bunch of behaviors (the different components) and some data (used by those components).

Components are not necessarily classes or objects either, though they can be and often are structs or objects with some component specific data. Essentially though, a component just labels an entity as having particular data and/or behavior. An entity (let's say "player") with a positionable component has a position in the world. This does not mean there is a "Player" class with a "position" field. It just means there is an entity which has (as in requires, not as in maintains) position data stored somewhere and this position data is accessible by other code (eg other components). It doesn't matter where this data is stored, as long as it is somehow accessible. It could be stored in a database, in a table called "PositionableData" under the "position" column in the row identified with the "player" entity. The "player" entity could just be a unique integer value, and all components that are part of "player" have a table in the DB with the component data for "player" in that integer value's respective row. Another possibility is a struct PositionableComponent which has a "position" field. The entity would have a list of components, one of which would be the PositionableComponent.

Now there are lots of ways to implement an entity system, but most good systems are not object oriented. In fact the reason entity systems were created in the first place is to avoid the ugly and confusing inheritance trees of object oriented "game objects". Besides that, you talk about overriding component behaviors. You don't want to do that! Components should be the building blocks of an entity, defining its behavior. If you want to change certain behavior, just remove the component responsible, or add another component that undoes some of the first one's actions. That's the sort of flexibility that component systems are all about.

Suppose you want to give some NPC in the game god power. In your system, you could create a class for that NPC and override the function that returns the amount of life to always return 100% life. But now you're catering to just one situation and writing game specific code in one specific class. Please don't do that. Write a "Invincible component" that makes sure the entity has 100% life. Now, you can add that component to that NPC, but you can also create a god mode by temporarily adding that component to your player and removing it later. You get so much more flexibility with this system.

I hope this helps. Please let me know if I'm not clear enough :)
> 4 votes

# Answer
In an object-oriented system, component based design tends to be pretty straightforward.

First, you have a list of Component classes. These will probably derive from a base Component class that sets up the common interface and functionality for all components. These Component classes will tend to be concrete, rather than abstract. You won't have different types of Position component, for example: you will have just one. There's no reason for different objects to store position differently.

You then will have the Composition class (which often is just the same as your GameObject class, especially if you're only using component based design for game objects and not other parts of your engine architecture). At the simplest level, the Composition class is just a collection of Component objects. That's it. It has some helpers to add, remove, and query the Component objects stored in the container.

Your Component classes should be designed along useful functional boundaries. There is *no reason* to have a separate Position and Rotation component, for example. These are updated together by physics, they are access together by graphics, they are accessed together by game logic physics queries (ray casting, etc.). Just make a single Transform component that handles position, rotation, scale, and matrix generation. Making tons of smaller, "simpler" components will just mean that actually using your components will become a huge pain in the rear. Try to think of the things that you honestly don't need for every game object, or which need to be switched out and changed on a functional level for different game objects. The AI module in use is a good example. The physics model is NOT a good example, because a physics engine generally always uses the same concept of a Body and current physics states for all objects, and alters behavior based on data like mass, friction material, etc.

You should also avoid using code to decide what data can decide for you. DO NOT make one Component for enemies with 100 health and another for enemies with 1000 health. Likewise, from a code perspective, it doesn't matter in the slightest that undead monsters die at -100 and living ones don't; that's just a number. It's data. Use data to define those differences in your Health component, rather than different implementations of the component. You don't need a Health interface, because there is zero reason to ever have more than one implementation of the Health component. Different monsters will just have different MaxHealth and MinHealth member variables stored in the Health component, depending on when they die and what they start at. (Of course, replace MinHealth/MaxHealth with what variables make the most sense to you and solve your specific design problems).

If you rely entirely on components rather than data for design issues, you are not really buying yourself much. The entire point of component based design in games is that it allows rapid iteration and dynamic runtime composition of new and interesting behaviors. In other words, it allows data-driven composition of behavior. You need to embrace data-driven design. Anything and everything that you can pull out of code and put into a data file is a win. It means you can tweak values without recompiling. If you put a tiny bit of effort in, it means you can tweak values without even restarting the game or current level!

So far as dependency injection in particular, it is a natural part of using a component based design. It allows for your game object factory to create components as runtime from a file loaded from disk (e.g., a "blueprint" or "archetype" file). It allows you to entirely remove the concept of hard-coded classes like NPC or Ship or Bullet and instead use a data file to define what components those classes are made up. Or, if you want a hybrid approach, it would allow the object factory to decide from a data file which components to inject into your specific classes (NPC or Bullet, etc.) based on which blueprint data file was used to construct the object instance.

The flexibility there is that it lets you rapidly create new variations of a base class. Maybe you have Bullet with a ton of bullet-specific behavior. Now you can just define a bunch of different bullet types in a text file, and your game object factory can use composition to create instances of Bullet with those different configurations. The data file specifies the components and any data members for those components (e.g., the MinHealth/MaxHealth for the Health component). Then if you decide you want a new gun powerup for your Ship that fires a new kind of Bullet, you quite possibly don't need to edit a single line of code. You can create a Gun archetype, whose FireBullet component just has a data member that specifies which Bullet archetype it fiels. You have a new PowerUp archetype with a data member specifying which Gun it adds to your Ship. You have a new Bullet archetype that specifies the graphics parameters (texture, etc.) and any special physics logic and what kind of damage it does (either through components or through serialization support on your base Bullet object).

tl;dr version: data-driven design top to bottom, larger components split at functional boundaries, focus on what makes it easier to iterate your design and experiment with new ideas rather than on academic idealism (e.g., avoid "entity system" nonsense).
> 2 votes

# Answer
> **TLDR:** if I have entities like Ship and Bullet and components like Positionable and Drawable, should I create interfaces for each component and inject them into my entities using DI, or should I be doing something else?

Usually, no.

This sounds like an unnecessary layer of indirection. If there will only ever be a single type of PositionalComponent (which is useful to enforce, since an entity's transform data is so foundational to a game, it should be reliable and predictable without much effort).

Even if you could dynamically add these getX and setX functions (which you seem to be suggesting is a feature of haXe?) those property names are ambiguous. Why not just set via `shipEntity.position.setX()`? And there doesn't really need to be a DI setup to instantiate a new PositionComponent for a shipEntity that needs it. If an entity doesn't have a position component, either don't dynamically add that attribute, or do some null checks.

I say "usually" because for specific instances of specialized implementations of abstract types, DI could have some use.
> 0 votes

---
Tags: component-based, dependency-injection
---


# Question
Title: How do I rotate a sprite so that it is 'pointing' in the direction it is moving?
I have a sprite, e.g a missile, heading in a certain direction (using a velocity vector). How do I figure out its how much to rotate it so that it gets drawn 'pointing' in the direction it is heading?

# Answer
> 15 votes
The angle you need to rotate by is the the angle your velocity vector makes with the positive x-axis.

This angle can be calculated using the inverse tan of the slope of the vector. In XNA, we use the Math.Atan2 function. Give the function the y coordinate and the x coordinate of the velocity vector (**in that order**). Atan2 will return an angle between +PI/2 and -PI/2. (+180 to -180 degrees) depending on the vector. Vectors below the x-axis (pointing down) have a negative angle. Vectors above the x-axis (pointing up) have positive angle.

Use this angle in your draw method to rotate the sprite.

```
    public void UpdateSprite(GameTime gameTime, GraphicsDeviceManager graphics)
    {
        // Move the sprite by speed, scaled by elapsed time.
        spritePosition += spriteSpeed * (float)gameTime.ElapsedGameTime.TotalSeconds;

        //figure out the angle that the sprits velocity vector is making with the
        //positive x-axis
        //Atan2 will return an angle (in radians) from -PI to +PI

        angle = (float)Math.Atan2(spriteSpeed.Y , spriteSpeed.X);
        flip = SpriteEffects.None;
        if (spriteSpeed.X < 0)
        { //for cases when the sprite is moving right to left, the rotation angle will be >90deg or < -90deg,
          //so the sprite will be drawn upside down.
          // fix this by flipping the sprite vertically
            flip = SpriteEffects.FlipVertically;

        }
    }

    public void Draw(GameTime gameTime, SpriteBatch spriteBatch)
    {
        if(!alive) return;

        spriteBatch.Draw(myTexture, spritePosition, null, Color.White, angle, spriteOrigin, 1,flip, 1);

    }

```

In my example I used a duck sprite, which if rotated by more than PI/4 (90deg) will start to look 'upside-down'. This might not be a problem for some spites if they do not have 'correct' orientation. (e.g. a missile), but things like aeroplanes or birds might look 'wrong'. Fix this issue by flipping the sprite vertically if the sprite is moving right to left (rotation is not in range -PI/4 to PI/4).

We can check for this either by looking at the angle to see if it is greater than PI/4 or less than -PI/4, OR, equivalently, we can simply check which direction along the x-axis the sprite is moving. If it is moving right to left it will have a negative x-component, this is the way I check in the code above.

---
Tags: xna, 2d, rotation, vector
---


# Question
Title: Shadow mapping: what is the light looking at?
I'm all set to set up shadow mapping in my 3d engine but there is one thing I am struggling to understand. The scene needs to be rendered from the light's point of view so I simply first move my camera to the light's position but then I need to find out which direction the light is looking. Since its a point light its not shining in any particular direction. How do I figure out what the orientation for the light point of view is?

# Answer
Generally, the approach for a point light which is shining light in all directions is to produce 6 shadow maps one for each axis.

So you have your camera look along the +x, -x, +y, -y,+z and -z axes to make 6 shadow maps to create a cube map. Each axis's 'view' will be rendered with a 45deg field of view.

\[edit\]

You can of course check each of the light's 'view' frustums for collision against the real view frustum. If it doesn't collide, then no need to generate the SM for that side of the cube map.

A lot of this work can be handled quite quickly by the geometry shader see here, but there is no such thing as a free lunch.

Realistically, if you have many lights, you will need to somehow limit the number of lights which are casting shadows either by;

1. sort your lights in some priority order, perhaps based on brightness or some game context
2. have you lights cast shadows only over a limited distance, so only lights within a certain radius of the camera cast shadows
3. combination of 1 & 2 (2 is really a special case of 1 anyway)
> 1 votes

---
Tags: opengl, shadows, shadow-mapping
---


title: How do patches in games work?

text:
# Question
Title: How do patches in games work?
Console and PC games have patches sometimes to fix bugs which the developers missed/didn't have time to fix.

My question is how do these work?

Sometimes the patch files are a few megabytes in size. I don't understand how a small file can alter a complied program.

# Answer
> 30 votes
There are multiple ways to do this, the simplest would be to XOR the two files and compress them (GZIP or so forth). The theory behind this is that hopefully you can get a large sequence of zeroes (long sequences of the same values compress well).

You can take that concept further and try and find areas of the two files where the data is identical and omit it entirely.

Finally, you could use the structure of each type of file to your advantage. For example, in an EXE you could package each method individually (only ones that have changed) and reconstitute the EXE yourself during patch application; keep in mind, however, that this is very likely in the realm of overkill and may not be worth the effort (the gain over a simple bdiff might not justify the extra complexity that could break in the wild). As another example you could use diff files for scripts.

However, most patching systems in the wild take the simplest route: they just package files that have changed - they don't attempt to only package changes within those files (probably for good reason, most game content is compressed already and **creating patches against high entropy or compressed data won't work at all**).

# Answer
> 15 votes
The executable code of a game doesn't always reside just in the executable, often it is divided into several dynamic libraries (for example the game, graphics and sound engines), the actual executable, and possibly many scripts for various purposes.

A patch could be fixing issues in any single one of these parts without warranting change in all of them.

A different approach than replacing all changed files could be to simply do a binary diff on them, and only packackge the actual differences to be redistributed.

(That will of course only work on files you can guarantee won't be changed by the user.)

# Answer
> 2 votes
Normally they use a third-party binary diff system to distribute patches to the game data. The executables are typically small enough to be trivially distributed entirely.

Most modern games have hundreds of megs of game data (mostly textures, models, levels data etc). These require patching quite often. As far as I know, the publishers normally have a standard proprietary way of doing this.

Needless to say, there are open-source examples. Some Linux distributions (Fedora?) use binary diffs for their patches. You can investigate those and read their source code or documentation.

# Answer
> -1 votes
Modern `diff` algorithms can efficiently find byte sequences that are common between two binaries. Not surprisingly, if you think about it. File compression relies on finding identical byte sequences too.

Once you have the list of identical byte sequences, you just need to send the old and new offsets, the length, and of course anything that's completely new. On the receiving side, it's then a straightforward assembly. Copy the bits you need to keep from the old file, fill in the new bits.

Creating the patch becomes even easier if your linker can spit out a MAP file which lists the offsets of every function in the file.

---
Tags: console, pc, patching
---


# Question
Title: Polygonal Triangulation - algorithm with O(n log n) complexity
I wish to triangulate a polygon I only have the outline of `(p0, p1, p2 ... pn)` like described in this question: How do you triangulate an arbitrary polygon? and this webpage: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/algorithm2.html

I do not wish to learn the subject and have a deep understanding of it at the moment. I only want to see an effective algorithm that can be used out of the box. The one described in the site seems to be of somewhat high complexity O(*n*) for finding one ear. I heard this could be done in O(*n* log *n*) time. Is there any well known easy to use algorithm that I can translate port to use in my engine that runs with somewhat reasonable complexity?

The reason I need to triangulate is that I wish to feel out a 2d-outline and render it 3d. Much like we fill out a 2d-outline in paint. I could use sprites. This would not serve cause I am planning to play with the resulting model on the z-axis, giving it different heights in the different areas.

I would love to try the books that were mentioned, although I suspect that is not the answer most readers are hoping for when they read this Q & A format. Mostly I like to see a code snippet I can cut and paste with some modifications and start running.

# Answer
> 1 votes
Not sure if this is the answer you seek, since you mention 3D. But I used Poly2Tri (alternate link) once to convert parametric curved shapes to triangles and it worked fine. I'm saying this because you need an easy implementation, and using this library I did it in an afternoon.

# Answer
> 2 votes
Velcro Physics (formerly Farseerer physics) has six different triangulators. You can check them here.

They're under the folder: `/src/VelcroPhysics/Tools/Triangulation/`

# Answer
> 2 votes
I have actually implemented it myself with a simple scanline algorithm. It doesnt grant the *best* results, but its good enough for me. From what I remember:

1. You just have to sort your vertices along the X.
2. Create column spans with the ordered vertices (thus, making it monotone polygons).
3. And finally, find the diagonals lines connecting the vertices along the spans.

Is it clear?

**EDIT**: Please dont mind the mess: http://code.google.com/p/bzk3/source/browse/#svn%2Ftrunk%2Fsource%2Fcommon%2Fsrc%2Fbr%2Fodb%2Flibsvg (look for it at svn/trunk/source/common/src/br/odb/libsvg/)

In fact, I used to provide a standalone runnable jar just for that. More details at: https://sites.google.com/site/montysprojects/current-projects/svgtriangulator

---
Tags: triangulation
---


title: Sprite batching seems slow

text:
# Question
Title: Sprite batching seems slow
I have implemented a sprite batching system in OpenGL which will batch sprites based on their texture. However, when I'm rendering ~5000 sprites all using the same texture I'm getting roughly 30fps.

The process is as followed

* Create sprite batch which also create a VBO with a set size and also creates the shaders as well
* Call begin and initialise the render mode (at the moment just setting alpha on)
* Call Draw with a sprite. This checks to see if the texture of the sprite has already been loaded and if so it just creates a pointer to the batch item and adds the new sprite coords. If not then it creates a new batch item and adds the sprite coords to that; it adds the batch item to the main batch. If the max sprite count is reached render will be called
* Call end which calls render to render the left over sprites in the batch, and also resets the buffer offset
* Render loops through each item in the batch and will bind the texture of the batch item, map the data to the buffer and then draw the array. The buffer will then be offset by the amount of sprites drawn.

I have a feeling that it could be the method I'm using to store the batched sprites or it could be something else that i'm missing but I still can work it out.

The class files are at these URLs:

On top of this, I'm also getting a weird issue where two sprites are batched on after the other the second sprite will use the same coordinates as the last. But, the one that is drawn after it is fine. I can't seem to find what is causing this issue.

# Answer
Searching through 5000 elements every time you add a element could already become a CPU bottleneck. *You are dealing with real-time graphics here, so if it takes a few ms it's already too much.* Iterating over 5000 elements is probably much less than a ms, but iterating 5000 times over up to 5000 elements quickly adds up. Say iterating over 5000 elements takes 0.02 ms, now you do that 5000 times that's already 100ms, 10 fps. For the iterating alone.

I would suggest you to do the sorting only once, e.g. shortly before you are drawing them.

Another option would be to just check the last or the last few sprites in the list, it's quite a simplification but still should be able to optimize most cases.

Edit: Oh just noticed that you are using a std::map as data structure. It iterates over it's elements to find stuff. std::unordered\_map is a alternative which makes use of hashing and can access elements in constant time.
> 2 votes

# Answer
You have lots of inefficiencies in there. (When I say 'slow' below, I mean 'relatively slow'.)

* Iterating over a std::map is slow, because the data is sprinkled around memory and requires indirections. Ideally you would use a contiguous data structure like a std::vector if you need to iterate over it often.
* Lookups in a std::map (eg. `m_BatchItems[Sprite->getTexture()]`) are fairly slow.
* Allocating memory is slow. Ideally you wouldn't be calling `new MLBatchItem::batchInfo` in the middle of a draw operation. But if `m_BatchItems` was a vector instead, you could just push\_back the new batchInfo and no extra memory would have to be allocated if the capacity was big enough.
* Deallocating memory is slow. You shouldn't call `delete it->second` in your rendering function. Again, if this data was stored in a vector or similar you can deallocate all of it instantly rather than bit by bit.

Ideally, what you would do might be more like this:

* preallocate your batches based on the textures your game uses. You probably know these at load time so you don't need to create them dynamically.
* fill the batches outside of the draw/render code by adding the information whenever a new sprite is added to the game, and removing it when the sprite is removed.
* each batch would contain a vector of BatchInfo, with capacity set fairly large to begin with to reduce memory allocations.
* at render time, for each batch, iterate over the vector of batchinfo objects.
* if you really need to limit batching to 1000 sprites, instead of using multiple batches, use 1 batch but render it 1000 items at a time.
> 1 votes

# Answer
I just want to add to the other good answers, that your graphics card fill rate could also be affecting this. What I mean is that if your sprites are large, drawing 5000 of them will fill the whole window several times (or they will fill the same area 5000 times). A graphics card can fill only so many pixels per second. As a quick test, reduce the size of each sprite (e.g. to 10x10), and see if your performance improves.

If this turns out to be the case, it means you will need some kind of culling mechanism so that as few covered (behind others) sprites are drawn.
> 1 votes

---
Tags: opengl, spritebatch, vbo
---


# Question
Title: 3D rotation matrices deform object while rotating
I'm writing a small 3D renderer (using an orthographic projection right now).

I've run into some trouble with my 3D rotation matrices. They seem to squeeze my 3D object (a box primitive) at certain angles.

Here's a live demo (only tested in Google Chrome): http://dl.dropbox.com/u/109400107/3D/index.html

The box is viewed from the top along the Y axis and is rotating around the X and Z axis.

These are my 3 rotation matrices (Only rX and rZ are being used):

```
var rX = new Matrix([
        [1, 0, 0],
        [0, Math.cos(radiants), -Math.sin(radiants)],
        [0, Math.sin(radiants), Math.cos(radiants)]
    ]);

    var rY = new Matrix([
        [Math.cos(radiants), 0, Math.sin(radiants)],
        [0, 1, 0],
        [-Math.sin(radiants), 0, Math.cos(radiants)]
    ]);

    var rZ = new Matrix([
        [Math.cos(radiants), -Math.sin(radiants), 0],
        [Math.sin(radiants), Math.cos(radiants), 0],
        [0, 0, 1]
    ]);

```

Before projecting the verticies I multiply them by rZ and rX like so:

```
vert1.multiply(rZ);
vert1.multiply(rX);

vert2.multiply(rZ);
vert2.multiply(rX);

vert3.multiply(rZ);
vert3.multiply(rX);

```

The projection itself looks like this:

```
bX = (pos.x + (vert1.x*scale));
bY = (pos.y + (vert1.z*scale));

```

Where "pos.x" and "pos.y" is an offset for centering the box on the screen.

I just can't seem to find a solution to this and I'm still relativly new to working with Matricies.

You can view the source-code of the demo page if you want to see the whole thing.

# Answer
> 4 votes
The problem is in the vector/matrix multiplication code (Vector3.prototype.multiply):

```
    this.x = ((vector3.rows[0][0] * this.x) + (vector3.rows[0][1] * this.y) + (vector3.rows[0][2] * this.z));
    this.y = ((vector3.rows[1][0] * this.x) + (vector3.rows[1][1] * this.y) + (vector3.rows[1][2] * this.z));
    this.z = ((vector3.rows[2][0] * this.x) + (vector3.rows[2][1] * this.y) + (vector3.rows[2][2] * this.z));

```

You are modifying the this.x, and then using the modified value for subsequent multiplication! Multiply with the original vector values and *then* set the new values on the vector, eg:

```
            var new_x, new_y, new_z;
            new_x = ((vector3.rows[0][0] * this.x) + (vector3.rows[0][1] * this.y) + (vector3.rows[0][2] * this.z));
            new_y = ((vector3.rows[1][0] * this.x) + (vector3.rows[1][1] * this.y) + (vector3.rows[1][2] * this.z));
            new_z = ((vector3.rows[2][0] * this.x) + (vector3.rows[2][1] * this.y) + (vector3.rows[2][2] * this.z));

```

# Answer
> 0 votes
I think that you are doing multiplication out of order. I believe you first have to combine the matrices and only then perform the transform. Basically:

transform = rZ * rY;

and then:

vert1.multiply(transform);

---
Tags: 3d, mathematics, matrix, rotation, vector
---


# Question
Title: What is the process for getting a dev-kit for Xbox 360 to allow native coding
I'm curious about the process of getting a Xbox 360 dev-kit.

What are the requirements? Do you have to have a track record in game development. Can indie gamers get one. How much does it cost? Is there special hardware?

# Answer
Basically, RTFM.

So either you work for a *certified Xbox 360 publisher*, and/or you're already in contact with a *Developer Account Manager*, but that would mean that you're already an established developer so you wouldn't be asking this question.

Or you request to join the *Registered Developers Program* that allows indies to access devkits and the XDK. This is done simply via email. This seems to be less restrictive, but you'll still have to prove that you can make proper games (e.g. you have "personnel with significant previous professional game development industry experience"), sign an NDA, and probably purchase a devkit.
> 2 votes

# Answer
You need to have money and you need to have a publisher with several published AAA titles.

It is indeed a special piece of hardware - nowadays not so much because of the actual hardware (which is slightly different), but because it gives you more freedom when running games (dev mode, debugging, etc.)

It's pretty pointless for indies anyway. However if you only want to experiment with native 360 stuff and not release a game, I believe there are some legally gray areas that allow you to do that.
> 0 votes

---
Tags: xbox360
---


# Question
Title: Advices fo starting a video game design career
I'm 24 and have a passion for video games and game-design. I've decided I want to design video games as my career.

I have no experience with designing video games or coding but I'm interested and willing to learn. I want a job at any level but what would I need to land a job?

I have no college experience and I have no money. What is a cheap school, or do I really need to go to school for this, or can I learn on my own? Is it possible to do this with no money? I'm literally broke but I want this so bad I feel like its the only career I'll enjoy.

I want to call up company's and ask them what they are looking for in someone they want to hire, is that a good idea?

Also I don't know the history of video game design and I don't want to sound like a dummy when someone says something about this field or talks about a famous designer and I have no idea who they're talking about. So what is key info when it comes to this field and where should I find it?

Hopefully some of you guys and girls can help me out: I know in the future I will create something everyone will enjoy and you guys will remember when you gave me advice and I will always remember you guys for helping me. I'm gifted I know I am and I want to share my gift with the rest of the world by making games that change the Industry. Help me out please.

# Answer
You said "*I have no experience with designing video games or coding*", but you haven't said what you're able to do... I hope you have at least a very deep IT knowledge. To do career in videogame-industry is very hard, most of the times you should start with an indie game (http://en.wikipedia.org/wiki/Indie\_game). If you gain success with that you can then report it in your CV or you can start your own business.

Anyway, if you need money you should work in a different industry and try to develop your game in your free time.
> 4 votes

# Answer
In case you haven't checked it out yet, this is a site that is very good to read when a person has questions like yours:

http://sloperama.com/advice.html
> 3 votes

---
Tags: game-design, game-industry
---


title: Text on a model

text:
# Question
Title: Text on a model
I am trying to put some text on a `Model` and I want it to be dynamic. Did some research and came up with drawing the text on the texture and then set it on the model. I use something like this:

```
public static Texture2D SpriteFontTextToTexture(SpriteFont font, string text, Color backgroundColor, Color textColor)
{
    Size = font.MeasureString(text);
    RenderTarget2D renderTarget = new RenderTarget2D(GraphicsDevice, (int)Size.X, (int)Size.Y);
    GraphicsDevice.SetRenderTarget(renderTarget);

    GraphicsDevice.Clear(Color.Transparent);

    Spritbatch.Begin();
    //have to redo the ColorTexture
    Spritbatch.Draw(ColorTexture.Create(GraphicsDevice, 1024, 1024, backgroundColor), Vector2.Zero, Color.White);
    Spritbatch.DrawString(font, text, Vector2.Zero, textColor);
    Spritbatch.End();

    GraphicsDevice.SetRenderTarget(null);

    return renderTarget;
}

```

When I was working with primitives and not models everything worked fine because I set the texture exactly where I wanted but with the model (RoundedRect 3D button). It now looks like that:

Is there a way to have the text centered only on one side?

# Answer
You need to modify your model so that the UV (texture) coordinates place the texture at the correct location.

---

It's *possible* that setting the texture address mode to clamp may (sort-of) solve your issue. But this *also* depends on your model having the correct UV coordinates to make it work.

```
GraphicsDevice.SamplerStates[0] = SamplerState.LinearClamp;

```

(The default mode is wrap, which will cause texture coordinates outside the range of 0..1 to wrap around when addressing the texture. Clamp will duplicate the edge pixels outwards, outside that range.)
> 6 votes

---
Tags: xna, textures, models, text
---


title: AndEngine player, background and camera

text:
# Question
Title: AndEngine player, background and camera
I'm developing a 2D shooter using AndEngine. At the moment I'm trying to make the camera follow the player. As I've understood the common approach is to use the `SmoothCamera` zooming it and setting the chased entity. The problem is that the camera follows the player WITH background moving also (`RepeatingSpriteBackground`), so it looks like the player doesn't move at all though the actual position changes. So I don't really get how to make the camera follow the player and have the background not moving. Thanks in advance.

# Answer
> 0 votes
Simplest approach would be to put the player sprite in a container at center of the container (X:0, y:0), and if he gets some speed, move him away from the center on distance equal to his speed. For example if you move right, you would first gain vx = 0.1 and move him to x:0.1 in the container, then vx = 2 and his distance would be 2 pixels on right from center of the container, and in the end when he's running vx = 10, he would be 10 pixels away from center. If the player character changes his speed smoothly, this will grant you a smooth camera follow effect.

You could multiply velocities by a constant value to make the effect stronger.

---
Tags: java, android, andengine
---


# Question
Title: Which are the cons of using only non-member functions and POD?
I'm creating my own game engine. I've read these articles and this question about DOD and it was written to not use member functions and classes. I also heard some criticism to this idea.

I can write it using member functions or non-member functions it would be similar. So what are the benefits/cons of that approach or when the project grows, does any of these approaches give clearer and better manageable code?

With POD & non-member functions I don't have to make struct members public I can still use object id outside of engine like OpenGL does with all it's stuff, so It's not about encapsulation.

POD \- plain old data

DOD - data oriented design

# Answer
> I can write it using member functions or non-member functions it would be similar.

That's not the way to approach DOD. That's just the C syntax of object-oriented code. DOD means thinking about data before writing your code. OOP is often (but not always) the other way around.

Example: You're going to have 10000 visible, colliding particle objects in your game.

**OOP**: I'll start by making a Particle class. Each particle will have a "collide" function. Just so it integrates in the world, each particle will be an Entity too. The Collide function will be virtual because Entity has an abstract virtual Collide function. The Render function will be similarly designed.

**DOD**: Since we've got a lot of particles, it would make sense to store them closely together to minimize the time it takes to process them. There will be a collision processing function that handles all particles at once and can be optimized in any way, if necessary. To further optimize memory access, particle data will be separated into rendering, physics and common data arrays, depending on the actual data that is used. If particle count is going to be increased, these things will be considered: reducing size of color data, making some of the variable equal or at least non-integrated (curves/equations) for all particles (allowing to remove them from data).

Obviously DOD takes a lot more time and thinking. How much it's worth depends on the project. These days, when everything is calculated in one library or another, it might not matter much. But if you want to make something truly impressive, it's basically DOD-way or the highway.
> 6 votes

# Answer
Following an object-oriented design is preferred for most larger projects. Most games are about interactions between different objects in a game world, so I consider OOP to be especially suitable for game development.

When you design classes, you should generally declare all their variables private and manipulate them through public getter and setter methods (or getter and setter member functions, when you prefer that term).

Why?

Imagine you have some game object with a public variable. Imagine that you change and access it in a bazillion places all over your code.

Now imagine that one day you realize, that whenever this variable changes, something else needs to happen (show it on the GUI, report it to a server via network or whatever). Or when it changes, something else needs to be changed too (changing the size changes the mass, changing the temperature changes the color or similar interactions).

Now you would have to check your whole code for every case where this variable is changed and add code to do the above. And when you forget just one, you will have a bug.

But when the variable would be private, you could just add the above behavior to the setter method and you could be sure that the code will be executed whenever the variable is changed, no matter where and for what reason.

And that's just one simple reason why following object-oriented paradigms makes your project much more maintainable and reduces the likeliness of bugs. There are a lot of other design patterns in object-oriented programming which help you to structure your code in a much cleaner and flexible way. I could write a whole book about it here, but there already are enough of those. Like this very famous one:

http://www.amazon.com/Patterns-Elements-Reusable-Object-Oriented-Software/dp/0201633612
> 0 votes

---
Tags: design-patterns, dod
---


# Question
Title: Get world coordinate under mouse (at a ground plane for Warcraft 3 like movement)
I want to let a unit follow the mouse like in any RTS (Warcraft 3, Starcraft, ...). For that I have a "ground plane" which is defined through 2 vectors, the X and Z axis. Now I need to get the world coordinate of the mouse click on this plane in order to move the unit. I'm using OGRE & C++.

How can I get the coordinates of the mouse click on the ground plane?

# Answer
> 4 votes
This is known as 3D picking, and usually involves some kind of raycast from a point in screen space (the cursor position) in the camera's forward vector direction.

For some Ogre tutorials, check those links:

# Answer
> 2 votes
Since you're using Ogre then you should probably read those ogre3d.org links, but if you want to know the math behind the intersect algorithm, here it is:

http://softsurfer.com/Archive/algorithm\_0104/algorithm\_0104B.htm#Line-Plane%20Intersection

When I do that I also use a bit from http://softsurfer.com/Archive/algorithm\_0104/algorithm\_0104.htm

---
Tags: c++, ogre, coordinates, picking, strategy
---


# Question
Title: Why does the X Y Z translations now rotate along with my static meshes?
So I was making a map for UT3, using the Unreal 3 Editor provided, and all was going well.

However I was doing some work with InterpActors and Vehicle Spawners, when I must have hit a key by mistake (or other wise somehow changed something) by mistake.

Now the X Y Z translations that are used to move objects around in the editor will rotate along with the object (Ive put images down below to help show what I mean)

This is very annoying because it also changes the direction the arrow keys move a rotated object, in the example below, the Down arrow key will now move the object to the right.

How can I fix this?

(Note both images are taken from the same viewpoint)

Before Rotation:

After Rotation:

P.S. If someone could please provide me with the correct / better name for the X Y Z "things" it would be much appreciated, thanks!

# Answer
The thing you're referring to is known as the "gizmo". The reason it's facing the direction of the gizmo is because it's in local space and not world space.

To change it just click on the drop down box (location shown in image) and click World
> 2 votes

---
Tags: unreal, map-editor
---


# Question
Title: How does Minecraft render its sunset and sky?
In Minecraft, the sunset looks really beautiful and I've always wanted to know how they do it.

Do they use several skyboxes rendered over eachother? That is, one for the sky (which can turn dark and light depending on the time of the day), one for the sun and moon, and one for the orange horizon effect?

I was hoping someone could enlighten me... I wish I could enter wireframe or something like that but as far as I know that is not possible.

# Answer
I'm going to gamble on the fact that you really want to know how to achieve a *similar* effect, and not specifically how Minecraft does it, which wouldn't be an on-topic question.

> Do they use several skyboxes rendered over eachother? That is, one for the sky (which can turn dark and light depending on the time of the day), one for the sun and moon, and one for the orange horizon effect?

You don't need that much geometry -- a single skybox and some geometry for the sun/moon is sufficient. Skyboxes are generally rendered in such a fashion as to ensure they are always the same distance from the eye, thus giving them the "infinitely far away" effect. The same thing can be applied to the geometry for the sun and moon, except you'll also want to transform the sun and moon by some global time value.

That same global time value feeds in to the skybox effect, which can be done with a shader that modulates between day and night textures (or just colors if you want to be simple) based on the time.

To get the "orange glow" on the horizon you'll want to also modulate in some vertex (or pixel) colors on the textures. Atmospheric scattering and perspective play a large part in determining these effects in the real world, and several papers exist presenting various ways of simulating those variables in software. The paper A Practical Analytical Model for Daylight is one I've personally used and implemented (dead image links there, you'll want to make sure you get the PDF on the linked site).

The Virtual Terrain Project has a section of curated links to relevant papers as well.
> 9 votes

---
Tags: lighting, minecraft-modding, sky
---


title: Collision detection, stop gravity

text:
# Question
Title: Collision detection, stop gravity
I just started using Gamemaker Studio and so far it seems fairly intuitive. However, I set a room to "Room is Physics World" and set gravity to 10. I then enabled physics on my player object and created a block object to match a platform on my background sprite.

I set up a Collision Detection event for the player and the block objects that sets the gravity to 0 (and even sets the vspeed to 0). I also put a notification in the collision event and I don't get that either. I have my key down and key up events working well, moving the player left and right and changing the sprites appropriately, so I think I understand the event system.

I must just be missing something simple with the physics. I've tried making both and neither of the objects "solid". Pretty frustrating since it looks so easy.

The player starting point is directly above the block object in the grid and the player does fall through the block. I even made the block sprite solid red so I could see it (initially it was invisible, obviously).

# Answer
> 1 votes
Okay I technically answered the original question. I had to create a collision detection event for the block as well as the player. I didn't put any action in other than a comment. Now he falls and lands as you would expect.

In short, you need the following: 1. Room Physics enabled 2. Player and Block object physics enabled 3. Collision events for BOTH player \> block and block \> player.

The only problem is, once the player lands the left/right movement doesn't work, but that's for another question...

---
Tags: collision-detection, game-maker
---


title: What is the best way to learn Cocos2D?

text:
# Question
Title: What is the best way to learn Cocos2D?
I've messed around with iPhone development for a couple years now. I've done some contract work. I want to get into Cocos2D to develop a game idea that I have.

I was wondering what might be the best/quickest way to get up in running in cocos2d?

I've thought about a book, but I wondering if that is needed? I'm the type of guy that just wants to know what everything does and is suppose to be used for.

Any ideas?

# Answer
> 5 votes
Try this: http://www.learn-cocos2d.com/

# Answer
> 1 votes
This blog is an awesome resource for starting out with Cocos2d iPhone development. Great examples with full code. It is also updated regularly.

http://www.raywenderlich.com/

# Answer
> 1 votes
I second Ray's site. I've learned many a thing from there.

I'm also reading through Learning Cocos2D which was actually written by Ray Wenderlich too (along with Rod Strougo). It covers both chipmunk and Box2D. Search the app store for 'Space Viking' - that's the app it build with you through the book.

---
Tags: cocos2d-iphone
---


# Question
Title: What sort of data should be sent for mouse-based movement in a multiplayer game?
I'm new to the Multiplayer Rodeo here so please bear with me...

I am just getting started and I'm trying to figure out how to deal with movement. I've looked at the question Best way to implement mouse-based movement in MMOG which gives me a pretty good idea, but I'm still struggling with what kind of data should be sent to the server.

If a player is on position \[x:0, y:0\] and I click with the mouse on \[x:40, y:40\] to start movement, what information should I send to the server? Should I calculate the position based on velocity on client side and just send the expected location? Or should I send current location and velocity and direction? When the server is updating the clients on the players' whereabouts, should the position be sent only, and the clients expected to interpolate/predict movement, or can the direction sent from the client (instead of just coordinates) be used.

My concern(or confusion) is regarding the ping/lag frequency of data update and use of a predictive algorithm, as I'd like the movement to be smooth even with a high latency, and prevent ability to cheat(though that's not the top priority).

# Answer
You are starting to ask very important and complicated questions. First some general wisdom... In order to reduce the load on the server you should do as much as possible on the client. And in order to eliminate cheating, you should do as much on the server. As you see, these are diametrically opposite, and you will be in a constant conflict between these two rules.

So, going by the first rule, you should calculate everything on the client, and only send results to the server. This will produce smooth gameplay, as the lag is eliminated, and your server will be able to support many more players. Down side is, people will hack your code, and make their characters fast, powerful and all seeing.

Going with the second rule, server will receive only the intention of the command, and will calculate everything, verify if the motion can be attempted etc. This will be fair to all players, and you will be free to enforce rule for maximum enjoyment. Down side is that client will see results only when the server calculates them and sends the data back. Lag galore, and the server will be hard pressed to support 100's, but probably 10's of players. (unless you are doing a card game)

So, you will need to find middle ground. One possible way is for client to send the intention of command to the server, then itself calculate the move and start the motion, the server will calculate the motion as well and send the result back. The client should be coded so that server results always override its own, that way whenever server updates the move client 'snaps back' to the server state. This way client performance will be smooth, the game will be fair as it is checked by the server, and the only side effect is that user will see a temporary 'glitch' when server sends an update which differs from clients own precalculated position. These glitches will depend heavily on quality of prediction in your code.

You still have a down side that the server will do a lot of work. Depending how far you want to go, you can reduce server load by actually using client calculated results, and verifying some percentage of the moves, basically testing if you trust the clients results.
> 7 votes

# Answer
There are a few options, but probably the "standard" approach would be:

* As soon as you detect the mouse click, transmit the command to the server (a message equivalent to "move to 40,40")
* Give some immediate visual feedback (e.g. an animation at the clicked-on point)
* Wait for the server to process the move command and return a confirmation of the movement
* Perform animation based on the confirmed movement back from the server

The more advanced option is to have the client start animating the movement using a predictive algorithm as soon as the click is made, typically by replicating the logic that would be used by the server. This however causes two big complications:

* You need to reconcile potential differences when you finally get communications back from the server. e.g. it might turn out that the move was actually impossible (e.g. someone else cast a "freeze" spell on you a millisecond before) and you therefore need to snap the animation back to the frozen position.
* There are timing issues if you start the movement on the client before the movement actually starts at the server. What is the "definitive" time? Typically you want to treat the server timings as authoritative, but then the client is probably constantly running a small amount ahead in terms of animation.
> 3 votes

---
Tags: multiplayer, movement, mouse
---


# Question
Title: $0.99 or Free with Virtual goods - Revenue Model for mobile games
I'm trying to decide between a paid game and a free to play game. Is there research on the pros and cons of each one. I would really appreciate some concrete data on this and not just opinions. This is for mobile (currently iOS with Android later) game.

# Answer
There are quite a few resources to refer to. First thing to note is that 93% of the top 100 grossing games use in-app purchasing so that by itself means something. Here is a research by flurry showing the dominance of in-app purchase dominance as a monetization model for mobile games. This is from about a year ago and the trend became stronger since:

Part of the reasons why free 2 play works well:

* It allows you to generate virality and traction with the free players
* It allows users to get addicted to the game before deciding how much to pay. In turn this increases the chance they will pay more - $14 on average according to flurry.

On the flip side - you should keep in mind that Virtual goods requires more effort to develop and optimize and you should probably invest some time reading game design resources that deal with building virtual economies. Here are some resources on that:

Still working on getting you more resources and will edit that in shortly.
> 15 votes

# Answer
It depends on the game you are trying to make, the decision is made before the game is made not after. F2P that involves micro transaction and monetization is integrated into the game design, does your game use boost to speed up game progression? does it offer something new and rewarding to the players after purchasing parts of the game, if you design the game using F2P model then the revenue model is naturally F2P.

On the other hand if you design your game with tradition content, levels or expansion it is naturally fit for one purchase. Some time this can work well for small projects especially if your game doesn't concern player persistence in the world.
> 2 votes

---
Tags: iphone, ios, mobile, monetization
---


# Question
Title: multipass shadow mapping renderer in XNA
I am wanting to implement a multipass renderer in XNA (additive blending combines the contributions from each light). I have the renderer working without any shadows, but when I try to add shadow mapping support I run into an issue with switching render targets to draw the shadow maps. When I switch render targets, I lose the contents of the backbuffer which ruins the whole additive blending idea.

For example:

```
Draw()
{
    DrawAmbientLighting()
    foreach (DirectionalLight)
    {
        DrawDirectionalShadowMap() // <-- I lose all previous lighting contributions when I switch to the shadow map render target here
        DrawDirectionalLighting()
    }
}

```

Is there any way around my issue? (I could render all the shadow maps first, but then I have to make and hold onto a render target for each light that casts a shadow--is this the only way?)

# Answer
> 2 votes
In XNA, setting a a render target (including the backbuffer) clears it. This is because preserving the contents of the buffer requires a slow copy operation on the Xbox 360. The PC version just uses the same behaviour to make porting easier.

You can override this behaviour by passing `RenderTargetUsage.PreserveContents` to the constructor of `RenderTarget2D`.

To set it on the backbuffer, respond to `PreparingDeviceSettings` and modify `GraphicsDeviceInformation.PresentationParameters.RenderTargetUsage`.

If it's possible, without requiring more targets or draw operations (and it usually is), it's better to re-order your draw function so you don't have to re-set targets you've already rendered to.

More info in this blog post.

---
Tags: xna, lighting, shadow-mapping
---


# Question
Title: what is the best way to use loops to detect events while the main loop is running?
I am making an "game" that has pathfinding using pygame. I am using Astar algo.

I have a main loop which draws the whole map. In the loop I check for events. If user press "enter" or "space", random start and end are selected, then animation starts and it will try to get from start to end.

My draw function is stupid as hell right now, it works as expected but I feel that I am doing it wrong. It'll draw everything to the end of the animation. I am also detecting events in there as well. What is a better way of implementing the draw function such that it will draw one "step" at a time while checking for events?

User can press "space" to randomly choose start/end coords, then the app will animate it. Or, user can choose the start/end by left-click/right-click.

During the animation, the user can also left-click to generate blocks, or right-click to choose a new destiantion.

Where I am stuck at is how to handle the events while the app is animating. Right now, I am checking events in the main loop, then when the app is animating, I do event checks again. While it works fine, I feel that I am probably doing it wrong.

What is the proper way of setting up the main loop that will handle the events while the app is animating?

In main loop, the app start animating once user choose start/end. In my draw function, I am putting another event checker in there.

```
def clear(rows):
    for r in range(rows):
        for c in range(rows):
            if r%3 == 1 and c%3 == 1:
                color = brown;
                grid[r][c] = 1;
                buildCoor.append(r);
                buildCoor.append(c);
            else:
                color = white;
                grid[r][c] = 0;
            pick_image(screen, color, width*c, height*r);

    pygame.display.flip();
    os.system('cls');

# draw out the grid
def draw(start, end, grid, route_coord):
    # draw the end coords
    color = red;
    pick_image(screen, color, width*end[1],height*end[0]);
    pygame.display.flip();

    # then draw the rest of the route
    for i in range(len(route_coord)):
        # pausing because we want animation
        time.sleep(speed);

        # get the x/y coords
        x,y = route_coord[i];
        event_on = False;

        if grid[x][y] == 2:
            color = green;
        elif grid[x][y] == 3:
            color = blue;

            for event in pygame.event.get():
                if event.type == pygame.MOUSEBUTTONDOWN:
                    if event.button == 3:
                        print "destination change detected, rerouting";
                        # get mouse position, px coords
                        pos = pygame.mouse.get_pos();

                        # get grid coord
                        c = pos[0] // width;
                        r = pos[1] // height;

                        grid[r][c] = 4;
                        end = [r, c];
                    elif event.button == 1:
                        print "user generated event";
                        pos = pygame.mouse.get_pos();

                        # get grid coord
                        c = pos[0] // width;
                        r = pos[1] // height;

                        # mark it as a block for now
                        grid[r][c] = 1;
                        event_on = True;

            if check_events([x,y]) or event_on: # there is an event
                # mark it as a block for now
                grid[y][x] = 1;

                pick_image(screen, event_x, width*y, height*x);
                pygame.display.flip();

                # then find a new route
                new_start = route_coord[i-1];
                marked_grid, route_coord = find_route(new_start, end, grid);

                draw(new_start, end, grid, route_coord);
                return; # just end draw here so it wont throw the "index out of range" error
        elif grid[x][y] == 4:
            color = red;
        pick_image(screen, color, width*y, height*x);
        pygame.display.flip();

    # clear route coord list, otherwise itll just add more unwanted coords
    route_coord_list[:] = [];

clear(rows);

# main loop
while not done:
    # check the events
    for event in pygame.event.get():
        # mouse events
        if event.type == pygame.MOUSEBUTTONDOWN:
            # get mouse position, px coords
            pos = pygame.mouse.get_pos();

            # get grid coord
            c = pos[0] // width;
            r = pos[1] // height;

            # find which button pressed, highlight grid accordingly
            if event.button == 1:
                # left click, start coords
                if grid[r][c] == 2:
                    grid[r][c] = 0;
                    color = white;
                elif grid[r][c] == 0 or grid[r][c] == 4:
                    grid[r][c] = 2;
                    start = [r,c];
                    color = green;
                else:
                    grid[r][c] = 1;
                    color = brown;
            elif event.button == 3:
                # right click, end coords
                if grid[r][c] == 4:
                    grid[r][c] = 0;
                    color = white;
                elif grid[r][c] == 0 or grid[r][c] == 2:
                    grid[r][c] = 4;
                    end = [r,c];
                    color = red;
                else:
                    grid[r][c] = 1;
                    color = brown;

            pick_image(screen, color, width*c, height*r);

        # keyboard events
        elif event.type == pygame.KEYDOWN:
            clear(rows);

            # one way to quit program
            if event.key == pygame.K_ESCAPE:
                print "program will now exit.";
                done = True;

            # space key for random start/end
            elif event.key == pygame.K_SPACE:
                # first clear the ui
                clear(rows);

                # now choose random start/end coords
                buildLoc = zip(buildCoor,buildCoor[1:])[::2];
                #print buildLoc;

                (start_x, start_y, end_x, end_y) = pick_point();
                while (start_x, start_y) in buildLoc or (end_x, end_y) in buildLoc:
                    (start_x, start_y, end_x, end_y) = pick_point();
                    clear(rows);

                print "chosen random start/end coords: ", (start_x, start_y, end_x, end_y);

                if (start_x, start_y) in buildLoc or (end_x, end_y) in buildLoc:
                    print "error";

                # draw the route
                marked_grid, route_coord = find_route([start_x,start_y],[end_x,end_y], grid);
                draw([start_x, start_y], [end_x, end_y], marked_grid, route_coord);

            # return key for user defined start/end
            elif event.key == pygame.K_RETURN:
                # first clear the ui
                clear(rows);

                # get the user defined start/end
                print "user defined start/end are: ", (start[0], start[1], end[0], end[1]);
                grid[start[0]][start[1]] = 1;
                grid[end[0]][end[1]] = 2;

                # draw the route
                marked_grid, route_coord = find_route(start, end, grid);
                draw(start, end, marked_grid, route_coord);

            # c to clear the screen
            elif event.key == pygame.K_c:
                print "clearing screen.";
                clear(rows);

            # go fullscreen
            elif event.key == pygame.K_f:
                if not full_sc:
                    pygame.display.set_mode([1366, 768], pygame.FULLSCREEN);
                    full_sc = True;
                    rows = 15;
                    clear(rows);
                else:
                    pygame.display.set_mode(size);
                    full_sc = False;

            # +/- key to change speed of animation
            elif event.key == pygame.K_LEFTBRACKET:
                if speed >= 0.1:
                    print SPEED_UP;
                    speed = speed_up(speed);
                    print speed;
                else:
                    print FASTEST;
                    print speed;
            elif event.key == pygame.K_RIGHTBRACKET:
                if speed < 1.0:
                    print SPEED_DOWN;
                    speed = slow_down(speed);
                    print speed;
                else:
                    print SLOWEST
                    print speed;

        # second method to quit program
        elif event.type == pygame.QUIT:
            print "program will now exit.";
            done = True;

    # limit to 20 fps
    clock.tick(20);

    # update the screen
    pygame.display.flip();

```

# Answer
> 6 votes
Just separate the events from the drawing. The normal method is to redraw all the time, not to wait for something to change. Normally your loop should be like this:

```
while loop:
    check events:
        # find routes, block path, whatever
    update things:
        # change the state of the game
    draw()

```

You shouldn't be thinking in terms of drawing one step at a time. If you have a thing that changes in steps, change that thing over a period of time, and while you're doing that, keep drawing whatever the current state of the thing is.

# Answer
> 3 votes
**You need to redraw every time in your main loop (even if no event has occurred)**, don't wait for any event or change to occur. Don't make your draw functionality dependent on events.

In your main loop

1. Check for events and make changes
2. Draw (even if nothing is changed)

---
Tags: game-loop, events, pygame
---


# Question
Title: Should I always be checking every neighbor when building voxel meshes?
I've been playing around with Unity3d, seeing if I can make a voxel-based engine out of it (a la Castle Story, or Minecraft).

I've dynamically built a mesh from a volume of cubes, and now I'm looking into reducing the number of vertices built into each mesh, as right now, I'm "rendering" vertices and triangles for cubes that are fully hidden within the larger voxel volume.

The simple solution is to check each of the 6 directions for each cube, and only add the face to the mesh if the neighboring voxel in that direction is "empty". Parsing a voxel volume is BigO(N^3), and checking the 6 neighbors keeps it BigO(7\*N^3)-\>BigO(N^3).

The one thing this results in is a lot of redundant calls, as the same voxel will be polled up to 7 times, just to build the mesh.

My question, then, is:

Is there a way to parse a cubic volume (and find which faces have neighbors) with fewer redundant calls? And perhaps more importantly, does it matter (as BigO complexity is the same in both cases)?

# Answer
Yes, you can make fewer calls. You can give each voxel data containing it's face information. Then go through and set the face data of all the voxels. The simple solid or not situation produces 4 cases:

```
for each voxel
  for each face not set
    if thisVoxel is solid
       if oppositeVoxel is solid
          // both voxels are solid and touching, no faces
          set thisFace to zero
          set oppositeVoxelFace to zero
       else
          // this voxel is solid, other is not, this voxel has a face
          set thisFace to one
          set oppositeVoxelFace to zero
    else
       if oppositeVoxel is solid
          // this voxel is not solid, other is, other has face
          set thisFace to zero
          set oppositeVoxelFace to one
       else
          // both voxels are not solid no faces
          set thisFace to zero
          set oppositeVoxleFace to zero

```

As you can see, you'll cut out at least one check for the opposite voxel by setting both at the same time. Ensure that you only loop over faces not set. This will reduce the number of checks you need to do.

Additionally, when rebuilding the mesh, you can reuse almost all the face data. When a voxel is added or removed, reset it's face data and the face data of those voxels surrounding it.

You probably realize that this is a trade off. You either get faster execution, or more memory usage. This will take more memory.
> 2 votes

# Answer
I made some progress in my marching cube implementation where I kept the previous slice of the YZ plane to prevent needing to resample a value twice, but this was to reduce the number of calls when using perlin noise and similar. If your voxel data is stored as an array I doubt there is much you can do to reduce the number of queries.

I suggest you go ahead with the simplest solution that works, and then after its made simply measure how long it really takes to make the mesh. This is not something you will be doing every frame after all, and creating the mesh can be done in a separate thread to prevent stalling the game when you need to recreate a mesh, or load a new section.
> 1 votes

---
Tags: voxels
---


title: Should Vector3 inherit from Vector2?

text:
# Question
Title: Should Vector3 inherit from Vector2?
I'm creating a couple of classes `Vector2` (X & Y) and `Vector3` (X, Y & Z), but I don't know whether to make `Vector3` inherit from `Vector2`, or whether to re-implement the member variables `m_x` and `m_y` again? What are the pros and cons of each side (inheritance vs redefinition).

**Edit:** I'm using C++ (VS2010).

# Answer
> 47 votes
No it shouldn't. The only thing you'd be using from the inheritance is the `x` and `y` components. The methods used in a `Vector2` class wouldn't be useful in a `Vector3` class, they would likely take different arguments and perform operations on a different number of member variables.

# Answer
> 8 votes
There's a curious thing you can do with C++ (You didn't specify a language, and this answer is mostly because I think it's nice to see alternatives, though I don't really believe this is useful in most cases.)

Using templates you can do something like this:

```
template <class T, class S, int U>
class VectorN
{
    protected:
        int _vec[U];
    public:
        S& operator+=(const S c)
        {
            for(int i = 0; i < U; i++)
            {
                _vec[i] += c.at(i);
            }
            return (S&)*this;
        }
        int at(int n) const
        {
            return _vec[n];
        }
};

template <class T>
class Vec2 : public VectorN<T,Vec2<T>,2>
{
    public:
        T& x;
        T& y;
        Vec2(T a, T b) : x(this->_vec[0]), y(this->_vec[1])
        {
            this->_vec[0] = a;
            this->_vec[1] = b;
        }
};

template <class T>
class Vec3 : public VectorN<T,Vec3<T>,3>
{
    public:
        T& x;
        T& y;
        T& z;
        Vec3(T a, T b, T c) : x(this->_vec[0]), y(this->_vec[1]), z(this->_vec[2])
        {
            this->_vec[0] = a;
            this->_vec[1] = b;
            this->_vec[2] = c;
        }
};

```

and this can be used like this:

```
int main(int argc, char* argv[])
{

    Vec2<int> v1(5,0);
    Vec2<int> v2(10,1);

    std::cout<<((v1+=v2)+=v2).x;
    return 0;
}

```

Like I said, I don't think this is useful, and it will probably complicate your life when you try to implement dot/normalize/other stuff and try to be generic with any number of vectors.

# Answer
> 7 votes
Regardless of speed, the first question you should ask yourself when doing *any* inheritance is if you're going to be using them polymorphically. More specifically, is there any situation where you can see yourself using a `Vector3` as if it were a `Vector2` (which, by inheriting from it, you're explicitly saying that a Vector3 "is-a" Vector2).

If not, then you shouldn't use inheritance. You shouldn't be using inheritance to share code. That's what components and external functions are for, not that you'd be sharing any code between them anyway.

That being said, you might want easy ways to *convert* `Vector3`s to `Vector2`s, and in that case you can write an operator overload that will implicitly truncate the `Vector3` to a `Vector2`. But you shouldn't inherit.

# Answer
> 5 votes
No, since every method will need to be overridden as well you will have no use of actually inheriting from it.

If something, they could both implement a Vector interface. However, since you probably don't want to add/sub/dot/dst between a Vector2 and Vector3 this will have unwanted side effects. And having different parameters etc. would be a hassle.
So I really cannot see any pros of inheritance/interface in this case.

An example is the Libgdx framework, where Vector2 and Vector3 have nothing to do with each other, other than having same type of methods.

# Answer
> 2 votes
If you plan to use SIMD arrays are likely the best. If you still wish to use operator overloading you can consider using an interface/mixin to access the underlying array - for example, here is a starting point that has only the (untested) `Add`.

Notice how I haven't provided `X`/`Y`/`Z`, each `VectorX` class would inherit directly from this one - for the same reasons specified by other people. Still, I have seen arrays used as vectors many times in the wild.

```
#include <xmmintrin.h>

class Vector
{
public:
    Vector(void)
    {
        Values = AllocArray();
    }

    virtual ~Vector(void)
    {
        _aligned_free(Values);
    }

    // Gets a pointer to the array that contains the vector.
    float* GetVector()
    {
        return Values;
    }

    // Gets the number of dimensions contained by the vector.
    virtual char GetDimensions() = 0;

    // An example of how the Vector2 Add would look.
    Vector2 operator+ (const Vector2& other)
    {
        return Vector2(Add(other.Values));
    }

protected:
    Vector(float* values)
    {
        // Assume it was created correctly.
        Values = values;
    }

    // The array of values in the vector.
    float* Values;

    // Adds another vector to this one (this + other)
    float* Add(float* other)
    {
        float* r = AllocArray();

#if SSE
        __m128 pv1 = _mm_load_ps(Values);
        __m128 pv2 = _mm_load_ps(other);
        __m128 pvr = _mm_load_ps(r);

        pvr = _mm_add_ps(pv1, pv2);
        _mm_store_ps(r, pvr);

#else
        char dims = GetDimensions();
        for(char i = 0; i < dims; i++)
            r[i] = Values[i] + other[i];
#endif

        return r;
    }

private:

    float* AllocArray()
    {
        // SSE float arrays need to be 16-byte aligned.
        return (float*) _aligned_malloc(GetDimensions() * sizeof(float), 16);
    }
};

```

*Disclaimer:* My C++ might suck, it's been a while since I used it.

# Answer
> 1 votes
Another serious con to having Vec3 inherit from Vec2 or, arguably, to having both inherit from a single Vector class: your code will be doing a *lot* of operations on vectors, often in time-critical situations, and it's very much in your best interests to make sure that all of those operations are as fast as they can be - much more so than it is for many other objects that aren't quite so universal or low-level. While a good compiler will do its best to flatten out any inheritance overhead, you're still relying more on the compiler there than you'd like to; instead, I would build them as structs with as little overhead as possible and possibly even try and make most of the functions that use them (with the exception of things like operator+ which can't really be helped) be globals rather than methods on the struct. Early optimization is generally recommended against, and with excellent reason, but in a circumstance like this where you can be sure that vector operations will almost certainly be a substantial chunk of your runtime, it's worth a bit of effort up front to design for efficiency.

---
Tags: c++, architecture
---


# Question
Title: Why doesn't MoveBy work in this example?
I'd like to run an action on a sprite using the MoveBy action. After lots of attempts, I can't achieve the goal... I have issues with the MoveBy in 2 different projects, so maybe I'm missing something in the setup... But I can't figure what!

The instruction is like this:

```
this.platform1Sprite.runAction(cc.MoveBy.create(1, cc.p(200, 0)));

```

I don't get any error, simply it doesn't work. platform1Sprite is a Sprite. But even with a LabelTTF it doesn't work:

```
var MoveToAction = cc.MoveTo.create(2.5, cc.p(size.width / 2, size.height / 2));
this.creditLabel.runAction(MoveToAction);

```

For this last snippet, you can view my complete code here: http://pastebin.com/fGbW4LLH.

The code I linked is somehow similar to the helloHTML5World official example, line 112 has the runAction method applied to a LabelTTF. The official example works, mine doesn't... I can't understand what's the difference!

# Answer
> 2 votes
I found out the problem! :)

In "credits.js" you need to change:

```
onEnter:function() {
},

onExit: function() {
},

```

to

```
onEnter:function() {
    this._super();
},

onExit: function() {
    this._super();
},

```

Hope this works for you!

-Edit-
The reason actions were not running is because 1) the engine was not being notified of any of the objects in the layer and 2) the scheduler/actions were not being resumed for said layer.

*CCNode.js*'s onEnter( ), called through *CCLayer.js*'s onEnter( ):

```
onEnter:function () {
    this._isRunning = true;//should be running before resumeSchedule
    this._arrayMakeObjectsPerformSelector(this._children, cc.Node.StateCallbackType.onEnter);
    this.resumeSchedulerAndActions();
},

```

---
Tags: cocos2d-x
---


# Question
Title: How do you ensure consistent experience across multiple graphics cards (or even driver versions)?
So I was writing a simple 2D game with OpenGL and SDL and had this problem when there was awful tearing when running in windowed mode (even though I explicitly asked SDL\_SetVideoMode to use double buffering). Didn't worry about it all too much because most of the time the game grabs the entire screen, windowed mode is just for debugging.

Anyway, yesterday I updated my nVidia drivers and tearing disappeared, the game runs smooth and looks nice in windowed mode too. I can see how the problem may be in the graphics driver, but this leads to a question.

Obviously, professional game developers have to deal with a lot of different hardware/software configurations. What are the techniques they use to make sure the game looks the roughly the same on different graphics cards or even the same model of graphics card, but with different driver versions?

# Answer
There are no techniques beyond keeping the differences in mind and always looking out for more (testing often on various hardware/software configurations).

As for the tearing problem, it's all about VSync. The driver update probably had it turned on by default. Double buffering is just the act of swapping buffers to avoid waiting while the display is redrawn. Tearing occurs exactly because the buffer swap occurs in the middle of the screen repaint operation.

To enable VSync in OpenGL, you need to use this extension in Windows, specifically the "wglSwapIntervalEXT" function, interval=1 would mean that buffer swap will wait for repainting of one frame, interval=2 means 2 frames etc. And interval=0 is the default "do not wait unless driver thinks differently" setting. Frame count per second equals your monitor's refresh rate setting.

X Window system (Linux, Mac) needs this extension.

P.S. You can also try SDL\_GL\_SetAttribute(SDL\_GL\_SWAP\_CONTROL, 1); Some say it doesn't work in windowed mode though.
> 1 votes

# Answer
Stuff looks the same on different drivers **due to DirectX and OpenGL**. That was the point of those API's, to abstract the graphics device from the programmer so he doesn't have to worry about it.

The tearing you see is likely your VSYNC setting, being set to OFF, and it's plausible that installing the new driver set it back to ON.

If your VSYNC setting was not set to synchronize the graphics device draw with the refresh interval, then tearing can occur.
> 0 votes

---
Tags: graphics, hardware, pc
---


# Question
Title: Are there existing FOSS component-based frameworks?
The component based game programming paradigm is becoming much more popular. I was wondering, are there any projects out there that offer a reusable component framework? In any language, I guess I don't care about that. It's not for my own project, I'm just curious.

Specifically I mean are there projects that include a base `Entity` class, a base `Component` class, and maybe some standard components? It would then be much easier starting a game if you didn't want to reinvent the wheel, or maybe you want a `GraphicsComponent` that does sprites with Direct3D, but you figure it's already been done a dozen times.

A quick Googling turns up Rusher. Has anyone heard of this / does anyone use it? If there are no popular ones, then why not? Is it too difficult to make something like this reusable, and they need heavy customization? In my own implementation I found a lot of boilerplate that could be shoved into a framework.

# Answer
> 50 votes
> If there are no popular ones, then why not?

Because there is nothing resembling a consensus on how such a framework would operate.

On a thread on Gamedev.net I determined that when people talk about component-based game systems there are actually at least 8 possible permutations of how they expect them to work, based on 3 different factors:

**Inboard vs. outboard** \- should components be aggregated into an entity, or should they be part of a subsystem and only associated by an entity ID?

**Static vs. dynamic composition** \- should entities consist of a known set of components (eg. 1 Physics, 1 Animation, 1 AI, etc) that can communicate in code via well-known interfaces, or can entities have arbitrary quantities of components added to them (with associated strategies for locating other components of interest)

**Data on component vs data on entity** \- Should data be held by the component that primarily operates upon it? Or should data be stored on the entity in a shared space, accessible by all components?

Beyond that there are further questions over how the components should communicate (via the shared data? Via function pointers? Via signals/slots? Or not at all?), how they should update (in a fixed order based on component type? a per-entity order defined at creation time? based on a topological sort of component interdependencies?), etc.

Each of these choices are completely arbitrary, and anything you can do with one system can be done with the other. But the way in which you have to code it is quite different in each case. And people seem to have strong opinions over which way works best for them.

Right now people are still too caught up in the idea that components are somehow a replacement for object orientation (which they're not) and also imagining that they're a massive change from how games were traditionally made (which again, they were not - people have factored out the various subsystems in their entities for ages), so there's a lot of hyperbole and not much agreement. Maybe in a few years things will have settled down and people will settle on one or two fairly standard approaches.

# Answer
> 10 votes
There's a wiki that's gathering examples of all these:

http://entity-systems.wikidot.com/

...along with explanations of the differences between the different approaches.

# Answer
> 4 votes
Check these frameworks I found out related to this architecture...

www.burgerengine.com

PushButtonEngine

Arthemis Framework - https://github.com/artemis-esf/artemis-framework/tree/master/src/com/artemis

Having a look at Unity Api. You can find a lot of stuff regarding the Component based architecture. (Will update the list as soon as I find somemore...)

Update:

```
      https://code.google.com/p/spartanframework/

```

This explains about entity systems in a good way... http://piemaster.net/2011/07/entity-component-primer/

# Answer
> 2 votes
There is Push Button Engine for Flash: http://pushbuttonengine.com/

And there is Panda3D for c++/python: panda3d dot com (sorry I'm only allowed 1 url per post as a n00b)

I'm sure there are tons more out there :)

---
Tags: component-based
---


# Question
Title: How to create an extensible rope in Box2D?
Let's say I'm trying to create a ninja lowering himself down a rope, or pulling himself back up, all whilst he might be swinging from side to side or hit by objects. Basically like http://ninja.frozenfractal.com/ but with Box2D instead of hacky JavaScript.

Ideally I would like to use a rope joint in Box2D that allows me to change the length after construction. The standard Box2D `RopeJoint` doesn't offer that functionality.

I've considered a `PulleyJoint`, connecting the other end of the "pulley" to an invisible kinematic body that I can control to change the length, but `PulleyJoint` is more like a rod than a rope: it constrains maximum length, but unlike `RopeJoint` it constrains the minimum as well.

Re-creating a `RopeJoint` every frame using a new length is rather inefficient, and I'm not even sure it would work properly in the simulation.

I could create a "chain" of bodies connected by `RotationJoint`s but that is also less efficient, and less robust. I also wouldn't be able to change the length arbitrarily, but only by adding and removing a whole number of links, and it's not obvious how I would connect the remainder without violating existing joints.

This sounds like something that should be straightforward to do. Am I overlooking something?

**Update**: I don't care whether the rope is "deformable", i.e. whether it actually behaves like a rope, or whether it collides with other geometry. Just a straight rope will do. I can do graphical gimmicks while rendering; they don't need to exist inside the physics engine. I just want something a `RopeJoint` whose length I can change at will.

# Answer
> 3 votes
Ok, I naively assumed that LibGDX wrapped all of Box2D, so this would be purely a Box2D problem.

It turns out that vanilla Box2D, at least in trunk, has a function called `b2RopeJoint::SetMaxLength`. I've added it and got a pull request merged within minutes. It is now available (and working) in LibGDX nightlies.

# Answer
> 2 votes
If you want a "deformable" rope, that isn't possible in box2d, as box2d is a rigid body physics engine; check soft body dynamics, I would sugest the Bullet library.

A "simpler" solution using box2d would be to "emulate" the variation of length by hiding some of the rope (with fixed length) outside the visible world / not drawing some of the rope.

This would work like pulling the top extremity (b) of the rope (c) up/downwards. I would add some static objects (a) so that the ninja doesn't escape the visible world for too long...

---
Tags: box2d
---


# Question
Title: Having a list of rooms with theirs connection to each other, how do I find isolated room groups?
I'm trying to create a small roguelike and went as far as random generating rooms and corridors. Each room is an instanced object and contain an arraylist of the others rooms connected by a corridor.

I can single out unconnected rooms but how can I know the rooms that are connected only to each other but not to most of the others, forming an island?

to illustrated better the problem here is an image from the console on a bogged level. Rooms 5 and 6 are connected only to each other. What algorithm can I use to detect that?

# Answer
> 14 votes
Start with a full list of rooms. Pick a starting room. Navigate from that room to all connected rooms. For each room you visit, remove it from the list of rooms and add it to a list *A*. Once you've visited all your connections, any rooms remaining on the list are not connected to the starting room or any of the rooms on list *A*.

You can then continue by selecting a room from what remains of the full list, and navigating again. This time adding to list *B*. Continue this process until you have no more rooms on the original list. You now have lists of all the connected room sets.

Problems like this are easily adapted to graph theory problems. For example, the problem you've described above directly relates to connectivity.

# Answer
> 9 votes
Your collection of rooms is essentially a graph, and your problem boils down to finding connected components ("islands") in that graph.

A simple way to find connected components is to do BFS (breadth-first search) from each vertex. Doing BFS from a vertex A will get you all the vertices in the connected component which vertex A belongs to.

So, basically, you start with an arbitrary vertex, do a BFS and mark each encountered vertex as a member of the 1st "island". Then you move on to the next unmarked vertex and do a BFS again, this time labeling encountered vertices as members of the 2nd "island", and so on.

# Answer
> 4 votes
You can picture the rooms as vertices on a directed graph. By doing that, you will be able to apply well known algorithms to solve your problem.

Dijkstra's algorithm, for example, produces a shortest path tree for a given starting vertex on a graph. This tree will contain all the reachable vertices from the starting point. You can then deduce that the vertices not present in the tree are part of other islands. You can apply the algorithm to these vertices in order to get trees representing every island.

---
Tags: java, algorithm
---


# Question
Title: Why doesn't Unity's OnCollisionEnter give me surface normals, and what's the most reliable way to get them?
Unity's on collision event gives you a Collision object that gives you some information about the collision that happened (including a list of ContactPoints with hit normals).

But what you don't get is surface normals for the collider that you hit. Here's a screenshot to illustrate. The red line is from `ContactPoint.normal` and the blue line is from `RaycastHit.normal`.

Is this an instance of Unity hiding information to provide a simplified API? Or do standard 3D realtime collision detection techniques just not collect this information?

And for the second part of the question, what's a surefire and relatively efficient way to get a surface normal for a collision?

I know that raycasting gives you surface normals, but it seems I need to do several raycasts to accomplish this for all scenarios (maybe a contact point/normal combination misses the collider on the first cast, or maybe you need to do some average of all the contact points' normals to get the best result).

My current method:

1. Back up the `Collision.contacts[0].point` along its hit normal
2. Raycast down the negated hit normal for `float.MaxValue`, on `Collision.collider`
3. If that fails, repeat steps 1 and 2 with the non-negated normal
4. If that fails, try steps 1 to 3 with `Collision.contacts[1]`
5. Repeat 4 until successful or until all contact points exhausted.
6. Give up, return `Vector3.zero`.

This seems to catch everything, but all those raycasts make me queasy, and I'm not sure how to test that this works for enough cases. Is there a better way?

**EDIT** If this really is just the way things are with 3D collision, an overview of why in the general case would be just as welcome as something specific to Unity.

# Answer
This really is just the way things are with collision. Not just 3D, but also 2D. Take the following example:

The green and red AABBs are colliding, and the contact manifold is the blue area. The contact points will be in the blue area somewhere (exactly where can vary with algorithm, but the corners where the blue/red/green meets are ideal-ish).

What surface normal should be returned? The top edge of the red AABB or the left edge? If the green box is falling down, maybe we can reasonably guess the top edge. if it's moving right, maybe we can reasonably guess the left edge. What if it was moving down and right? Do we take the axis of least penetration? The velocity axis of greatest speed? Some heuristic of both? What if the boxes would have collided exactly on the corners?

Extend this to a complex 3D surface potentially made up of 100s of tris/faces. You're still only going to have a small number of ideal-ish contact points. What surface normal should be returned? The average surface normal over the whole tri-mesh (which doesn't make sense for most objects)? The points directly "under" the colliding box's corners (which aren't well defined for most other shapes)? Do you try to find the closest face to the contact points generated (which would require a second pass, since contact points are not calculated directly from any mesh faces)? If you do find the closest face, do you take the face's normal or do you interpolate the face's vertices at the point of contact to get the correct normal for "smooth" objects?

Really, the primary problem is that the contact points aren't *all* the contact points. In many cases, that would be an infinite set of points, after all. They're just a few points that are distributed well that make it reasonably feasible to approximate physical reaction by applying forces at said points to push the colliding objects around in a reaslitic-ish manner. The specific points/locations of actual object contact are abstracted away behind a simplified mathematical model. Hence, the idea of a specific surface normal of contact simply doesn't make much sense in the general case.

Of course, with more specific constraints and limitations on your objects, world, and motion, you can create alternative collision algorithms that can tell you about surface normal. In the 2D case above, if we assume that the boxes never rotate and that we know the relative velocity and last position of each, would could use continuous collision detection to find out exactly when they would collide and which features collided, supplying us with the exact feature where collision occured, which could then be used as a contact/collision/surface normal. Platformer games are built entirely on such assumptions and special tricks (Which is why using a general physics library like Box2D or Havok or the light never produces the kind of tight, precise control you find in classic platformers like Mario or Sonic; I wouldn't want to say it's impossible, but... it's impossible).

General Newtonian physics libraries, like that used in Unity3D, can't make those kinds of simplifications and assumptions. Therefor, you don't get collision surface normals, you get a contact manifold, generally simplified down to contact points, and that's it.
> 14 votes

---
Tags: collision-detection, mathematics, unity, raycasting
---