# Question
Title: Is storing all game objects in a single list an acceptable design?
For every game I've made, I just end up placing all my game objects (bullets, cars, players) in a single array list, which I loop through to draw and update. The update code for each entity is stored within it's class.

I've been wondering, is this the right way to go about things, or is a faster more efficient way?

# Answer
> 27 votes
There is no one right way. What you're describing works, and is presumably fast enough that it doesn't matter since you seem to be asking because you're concerned about the design and not because it's caused you performance issues. So it is *a* right way, sure.

You could certainly do it differently, by for example keeping a homogenous list for each object type or by ensuring everything in your heterogenous list is grouped together such that you have improved coherency for the code that is in-cache or to allow parallel updates. Whether you'd see any appreciable performance improvement by doing this is difficult to say without knowing the scope and scale of your games.

You could also further factor out the responsibilities of your entities -- it sounds like entities both update and render themselves at the moment -- to better follow the Single Responsibility Principle. This can increase the maintainability and flexibility of your individual interfaces by decoupling them from one another. But again, whether or you'd see a benefit from the extra work that would entail is hard for me to say knowing what I know of your games (which is basically nothing).

I would recommend not stressing too much about it, and keep in the back of your head that it might be a potential area for improvement if you ever notice performance or maintainability issues.

# Answer
> 16 votes
As others have said, if it's fast enough, then it is fast enough. If you are wondering if there is a better way, the question to ask yourself is

*Do I find myself iterating through all of the objects but only operating on a subset of them?*

If you do, then that is an indication that you may want have multiple lists holding only relevant references. For instance if you are looping through every game object to render them but only a subset of objects need to be rendered, it may be worth keeping a separate Renderable list for only those objects that need to be rendered.

This would cut down on the number of objects you loop through and skips the unnecessary checks because you already know all of the objects in the list are to be processed.

You'd have to profile it to see if you are getting much of a performance gain.

# Answer
> 8 votes
It depends almost entirely on your **specific game** needs. It can work perfectly for a simple game, but fail on a more complex system. *If it's working for your game, don't worry about it or try to over engineer it until the need arises.*

As for why the simple approach may fail in some situations, it's hard to summarize that in a single post, since the possibilities are endless and depend entirely on the games themselves. Other answers have mentioned for instance that you might want to group objects sharing responsibilities together into a separate list.

That's one of the most common changes you might be doing depending on your game design. I'll take the chance do describe **a few other** (more complex) examples, but remember there are still many other possible reasons and solutions.

For starters, I'll point out that updating your game objects and rendering them *may have different requirements* in some games, and therefore need to be handled separatedly. Some possible problems with updating and rendering game objects:

**Updating Game Objects**

Here's an excerpt from Game Engine Architecture which I would recommend reading:

> In the presence of inter-object dependencies, the phased updates technique described above must be adjusted a little. This is because inter-object dependencies can lead to conflicting rules governing the order of updating.

In other words, in some games it's possible for objects to depend on each other and require a specific order of updating. In this scenario, you might need to devise a more complex structure than a list to store objects and their inter-dependencies.

**Rendering Game Objects**

In some games, scenes and objects create a hierarchy of parent-children nodes and should be rendered in the correct order and with transformations relative to their parents. In those cases, you might need a more complex structure like a **scene graph** (a tree structure) instead of a single list:

Other reasons might be for instance, using a spatial partitioning data structure to organize your objects in a way that improves the efficiency of performing view frustum culling.

# Answer
> 4 votes
The answer is "yes, this is fine." When I worked on big iron simulations where performance was non-negotiable, I was surprised to see everything in one big fat (BIG and F-A-T) global array. Later I worked on an OO system and got to compare the two. Although it was super ugly, the "one array to rule them all" version in single-threaded plain old C *compiled in debug* was several times faster than the "pretty" multithreaded OO system *compiled -O2* in C++. I think a bit of it had to do with excellent cache locality (in both space and time) in the big-fat-array version.

If you want performance, one big fat global C array is going to be the upper bound (from experience).

# Answer
> 2 votes
Basically what you want to do is make up lists as you need them. If you redraw terrain objects all in one go, a list of just them could be handy. But for this to be worth while you'd need tens of thousands of them, and many 10,000's of things that are *not* terrain. Otherwise perusing your list-of-everything and using an "if" to pull out terrain objects is plenty fast enough.

I've always needed one master list, regardless of how many other lists I've had. Usually I make it a Map, or keyed table, or dictionary, of some sort so I can randomly access individual items. But a simple list is a lot simpler; if you don't randomly access game objects you don't need the Map. And the occassional sequential search through a few thousand entries to find the right one won't take long. So I'd say, whatever else you do, plan to stick with the master list. Consider using a Map if it gets big. (Though if you can use indexes instead of keys, you can stick with arrays and have something a lot better than a Map. I always ended up with big gaps between index numbers, so I had to give it up.)

A word about arrays: they are unbelievably fast. But when they get up around 100,000 elements they start to give Garbage Collectors fits. If you can allocate the space once and not touch it afterward, fine. But if you are continually expanding the array, you are continually allocating and freeing large chunks of memory and are apt to have your game hang for seconds at a time and even fail with a memory error.

So faster and more efficient? Sure. A Map for random access. For really large lists, a Linked List will beat an array if and when you *don't* need random access. Multiple maps/lists to organize the objects in various ways, as you need them. You could multi-thread the updating.

But it's all a lot of work. That single array is fast and simple. You can add other lists and things only when needed, and you probably won't need them. Just be aware of what can go wrong if your game gets big. You might want to have a test version with 10 times as many objects in as in the real version to give you an idea of when you are headed for trouble. (Only do this if your game *is* getting big.) (And don't try the multi-threading without giving it a lot of thought. Everything else is easy to get started with and you can do as much or as little as you like and back off any time. With multi-threading you'll pay a big price to get in, the dues for staying in are high, and it's hard to get back out.)

In other words, just keep doing what you're doing. Your biggest limit is probably your own time, and you are making the best possible use of that.

# Answer
> 1 votes
I've used a somewhat similar method for simple games. Storing everything in one array is very useful when the following conditions are true:

1. You have a small number or known maximum of game objects
2. You favor simplicity over performence (i.e.: more optimized data structures such as trees aren't worth the trouble)

In any case, I implemented this solution as a fixed-sized array that contains a `gameObject_ptr` struct. This struct contained a pointer to the game object itself, and a boolean value representing whether or not the object was "alive".

The purpose of the boolean is to speed up creation and deletion operations. Instead of destroying game objects when they are removed from simulation, I would simply set the "alive" flag to `false`.

When performing calculations on objects, the code would loop through the array, performing calculations on objects marked as "alive", and only objects marked "alive" are rendered.

Another simple optimization is to organize the array by object type. All bullets, for example, could live in the last *n* cells of the array. Then, by storing an int with the value of the index or a pointer to the array element, specific types could be referenced at a reduced cost.

It should go without saying that this solution is not good for games with large amounts of data, as the array will be unacceptably large. It is also not suitable for games with memory constraints that prohibit unused objects from taking up memory. The bottom line is that if you have a known upper limit on the number of game objects you will have at one point in time, there is nothing wrong with storing them in a static array.

This is my first post! I hope it answers your question!

# Answer
> 0 votes
It is acceptable, although unusual. Terms like "faster" and "more efficient" are relative; typically you would organize game objects into separate categories (so one list for bullets, one list for enemies, etc.) to make the programming work more organized (and thus more efficient) but it's not like the computer will loop through all the objects faster.

# Answer
> 0 votes
You say single array and objects.

So (without your code to look at) I'm guessing they're all related to 'uberGameObject'.

So maybe two problems.

1) You may have a 'god' object - does tonnes of stuff, not really segmented by what it does or is.

2) You iterate through this list and casting to type? or unboxing each. This has a big performance penalty.

consider breaking up different types (bullets, bad guys, etc) into their own strongly typed lists.

```
List<BadGuyObj> BadGuys = new List<BadGuyObj>();
List<BulletsObj> Bullets = new List<BulletObj>();

 //Game
OnUpdate(gameticks gt)
{  foreach (BulletObj thisbullet in Bullets) {thisbullet.Update();}  // much quicker.

```

# Answer
> 0 votes
I can propose some compromise between general single list and separate lists for each object type.

Keep reference to one object in multiple lists. These lists are defined by base behaviors. For example, `MarineSoldier` object will be referenced in `PhysicalObjList`, `GraphicalObjList`, `UserControlObjList`, `HumanObjList`. So, when you process physics, you iterate through `PhysicalObjList`, when process damaging from poison - `HumanObjList`, if Soldier dies - remove it from `HumanObjList` but keep in `PhysicalObjList`. To make this mechanism working you need to organize automatic insertion/removing object when it's created/deleted.

Advantages of the approach:

* typed organization of objects (no `AllObjectsList` with casting on update)
* lists are based on logics, not on object classes
* no problems with objects with combined abilities (`MegaAirHumanUnderwaterObject` would be inserted into corresponding lists instead of creating new list for its type)

PS: As for self-updating, you will meet problem when multiple objects are interacting and each of them depends on others. To solve this we need to affect object externally, not inside self-update.

---
Tags: software-engineering
---


# Question
Title: Google Sketchup pro exporter/importer for MD5 model format?
Where can I find google sketchup pro MD5 (The doom3 model format) exporter/importer? If there isn't one what modeling program can I use to export/import MD5 models?

# Answer
> 1 votes
I don't know of an MD5 importer/exporter for SketchUp, but you could use Blender along with the MD5 import/export scripts available here to convert between MD5 and a format that SketchUp supports.

---
Tags: 3d, models, file-format
---


# Question
Title: Resuming swapped out RenderTarget2D in XNA
Hopefully this will be a simple answer, but as RenderTarget2Ds are Texture2Ds under the hood I was wondering how it handles swapping in and out.

Lets say you create a default one and assign it as the render target at the start of your Game.Render(). Then at a few points during your render process a new RenderTarget is swapped in, rendered to and then kept as a texture for later and the original one is then put back in. Some more rendering occurs and another entity swaps in its own RenderTarget, puts it in another texture and then swaps back to the default RenderTarget, and finally everything is rendered and done.

Now as the RenderTarget2D is a Texture2D without setting preserve mode on the RenderTarget will you be able to swap it out and swap it back in without losing your current contents of the RenderTarget?

I know there are some issues with the Preserve settings for RenderTargets on the Xbox, but if the render targets are being stored as a class member somewhere, are they subject to different rules?

I am sure the answer is, they obey the RenderTargetUsage behaviour, and will be subject to the same rules regardless of how they are stored in the game, but I just wanted to be sure.

# Answer
> Hopefully this will be a simple answer, but as RenderTarget2Ds are Texture2Ds under the hood I was wondering how it handles swapping in and out.

RenderTarget2Ds are not Texture2Ds under the hood. A RenderTarget2D is more of a backbuffer that saves the resulting Texture2D to a separate bit of GPU memory when its resolved.

> Now as the RenderTarget2D is a Texture2D, without setting preserve mode on the RenderTarget2D will you be able to swap it out and swap it back in without losing your current contents of the RenderTarget?

No. Unless you have PreserveMode on all of the RenderTargets2D share the same bit of memory. When the RenderTargets2D is switched it is resolved into a bit of memory also on the GPU that is used when treating it as a Texture2D. However, the shared bit of memory is completely cleared each time.

> I know there are some issues with the Preserve settings for RenderTargets on the Xbox, but if the render targets are being stored as a class member somewhere, are they subject to different rules? I am sure the answer is, they obey the RenderTargetUsage behaviour, and will be subject to the same rules regardless of how they are stored in the game, but I just wanted to be sure.

RenderTargets2D is a convenient abstraction for a ton of stuff happening in the GPU, so nothing you do is going to alter the behavior specified by the RenderTargetUsage enum. The issues with the PreserveContents setting is that its very slow compared to the others. Too slow for the XBox or WP7 in many cases.
> 1 votes

---
Tags: xna
---


# Question
Title: transform touch/click coordinates(2D) into 3d coordinates
I would like to convert touch/click input (2D coordinates) to 3D coordinates by dropping the Z axis (would like to move only up/down, left/right (Z is the axis for depth).

The problem is that the coordinates i get from input (2d) aren't corelated with the 3d actual space.

Does XNA provide a way to do this?

# Answer
You want to have a look at this: http://msdn.microsoft.com/en-us/library/microsoft.xna.framework.graphics.viewport.unproject.aspx
> 1 votes

---
Tags: xna
---


# Question
Title: Large Blob of landmass in Minecraft Terrain Engine in XNA
I am creating a Minecraft Terrain engine in XNA, and want to create a large blob/cluster of blocks, in a random sort of blob thing, shaped somewhat like the stuff under the Volume Rendering heading on the following page:

http://paulbourke.net/geometry/blob/

This post might be somewhat like my post How can I generate floating land masses for a Minecraft-like engine? but I believe this is an entirely different because this is more of a 3D approach rather then 2D, also I would prefer it without the crater bits ;).

# Answer
Perlin Noise can be done in 3D just the same as 2D.

Heres a video of it being used with some terrain.

Try making 3d perlin noise as a bunch of block clouds. But remove any blocks below a specific level of noise (the higher the level the smaller and more island like he landmasses would be). It might also be an idea to apply a kind of 3D blur to help prune out small single blocks. Maybe you might want blocks to 'fall' if there is a block within a specific number of blocks below them.

Chances are you want to scale/'flatten' the noise vertically to ensure you get flatter landmasses.

You can overlay several noise's at different resolutions/properties, that allows you to generate some large islands and little ones. Some will merge together too. More noise generations with other thresholds could be used to make different block types. Other another level of noise could forgot the flattening and produce mountains.

Things like trees, water and caves entrances are a bit more tricky since you would need to check to see if they make sense placed where they are(ie trees/caves appear only on top of an island rather than floating in free space).

It might be an idea to look at turning another perlin noise into some kind of probability point distribution, ie a higher value for noise means there is a %10 chance of a tree at that point. Once you have that point you trace down until you find a valid block where you plant the tree provided it meets the conditions required for a tree (ie there is enough space above it. It's on a dirt block, lighting levels, water nearby or whatever.

Of course there are also things like biomes which would be more noise.

Going this route you will want to be sure of of how fast you can produce perlin noise in the numbers you want since you will be making a lot of it. Also find out how much memory it will take, some noise can just be added onto the other noise but other types would require it's own separate overlay.

It might be worth looking and seeing if you can generate the noise using Shaders, OpenCL , DirectX's Compute shaders, or CUDA if possible but if your planning on releasing this commercially you may be limited by what you can use depending on what requirements you want to support. Of course you can produce 2 different generators provided they both use the same algorithm. At the very least you probably want to thread it.

You will also want some flexible noise manipulation functions like blur, stretch, recale values, subnoise.
> 2 votes

---
Tags: algorithm, procedural-generation, minecraft-modding, random, voxels
---


# Question
Title: Creating a vertexbuffer to define vertices arranged in a grid with the view for easy editing later
I'm using the marching square algorithm (2D version of marching cubes) to generate vertices.

I end up with vertices arranged in a grid.

I want to enable destructible terrain, and the way i was planning on doing this was to start simple - have one vertex buffer with the whole map, and edit the bits that change. In cases where I need to remove vertices I was thinking about just making them transparent so I can still render the whole map in one go.

Firstly, is this approach reasonable?

Secondly, I want to design my VB so that if I need to change vertices in 3x3, 5x5 or 7x7 etc. grids the locations of the vertices in the VB are close together.

Now, from university I vaguely remember an image compression algorithm that walked the image in an unusual way, which i think could apply. Basically it walked in a U / horseshoe direction. It would place a U over the image, large enough to cover the whole thing, then it would break the U up into 4 quadrants, and use a smaller U to walk those, and so on until it got down to the pixel level, or in my case it got down to a single grid unit.

Does this sound feasible? What is that algorithm called? (I can't remember the name and haven't found via general searching).

# Answer
It is feasible and the algorithm is called quadtree, for future reference, the 3D version is called octree and is essentially the same algorithm. You would likely store the vertexbuffer as several buffers in this method however, this way recreating part of the scenery will be less complicated and can be done by simply recreating one of the vertexbuffers. A google search should net you many tutorials and examples on both of these. Hope it helps.
> 1 votes

---
Tags: xna, c#, terrain, image, vertex
---


title: Abstracting entity caching in XNA

text:
# Question
Title: Abstracting entity caching in XNA
I am in a situation where I am writing a framework in XNA and there will be quite a lot of static (ish) content which wont render that often. Now I am trying to take the same sort of approach I would use when doing non game development, where I don't even think about caching until I have finished my application and realise there is a performance problem and then implement a layer of caching over whatever needs it, but wrap it up so nothing is aware its happening.

However in XNA the way we would usually cache would be drawing our objects to a texture and invalidating after a change occurs. So if you assume an interface like so:

```
public interface IGameComponent
{
    void Update(TimeSpan elapsedTime);
    void Render(GraphicsDevice graphicsDevice);
}

public class ContainerComponent : IGameComponent
{
    public IList<IGameComponent> ChildComponents { get; private set; }

    // Assume constructor

    public void Update(TimeSpan elapsedTime)
    {
        // Update anything that needs it
    }

    public void Render(GraphicsDevice graphicsDevice)
    {
        foreach(var component in ChildComponents)
        {
            // draw every component
        }
    }
}

```

Then I was under the assumption that we just draw everything directly to the screen, then when performance becomes an issue we just add a new implementation of the above like so:

```
public class CacheableContainerComponent : IGameComponent
{
    private Texture2D cachedOutput;
    private bool hasChanged;
    public IList<IGameComponent> ChildComponents { get; private set; }

    // Assume constructor

    public void Update(TimeSpan elapsedTime)
    {
        // Update anything that needs it
        // set hasChanged to true if required
    }

    public void Render(GraphicsDevice graphicsDevice)
    {
        if(hasChanged)
        { CacheComponents(graphicsDevice); }
        // Draw cached output
    }

    private void CacheComponents(GraphicsDevice graphicsDevice)
    {
        // Clean up existing cache if needed
        var cachedOutput = new RenderTarget2D(...);
        graphicsDevice.SetRenderTarget(renderTarget);
        foreach(var component in ChildComponents)
        {
            // draw every component
        }
        graphicsDevice.SetRenderTarget(null);
    }
}

```

Now in this example you *could* inherit, but your Update may become a bit tricky then without changing your base class to alert you if you had changed, but it is up to each scenario to choose if its inheritance/implementation or composition. Also the above implementation will re-cache within the rendering cycle, which may cause performance stutters but its just an example of the scenario...

Ignoring those facts as you can see that in this example you could use a cache-able component or a non cache-able one, the rest of the framework needs not know. The problem here is that if lets say this component is drawn mid way through the game rendering, other items will already be within the default drawing buffer, so me doing this would discard them, unless I set it to be persisted, which I *hear* is a big no no on the Xbox. So is there a way to have my cake and eat it here?

One simple solution to this is make an ICacheable interface which exposes a cache method, but then to make any use of this interface you would need the rest of the framework to be cache aware, and check if it can cache, and to then do so. Which then means you are polluting and changing your main implementations to account for and deal with this cache...

I am also employing Dependency Injection for alot of high level components so these new cache-able objects would be spat out from that, meaning no where in the actual game would they know they are caching... if that makes sense. Just incase anyone asked how I expected to keep it cache aware when I would need to new up a cachable entity.

# Answer
> 1 votes
You are not specifying if this is a 2D or 3D project, in 2D you are unlikely to run into any problems since modern graphics cards can handle much more complex scenarios, and in 3D just a simple turn of the camera would invalidate all your static terrain.

In theory your solution would work (not sure about the XBox part though) but in practice it will either be premature optimization since your never going to use it, or its going to actually slow things down since just the smallest camera change would necessitate invalidating the caches.

TLDR; Don't worry about it until you run into performance issues, in 2D cases you would need A LOT of sprites before you need to consider simplifying the rendering and in 3D cases you might want to look at OcclusionQueries or Octrees (for starters, there are way more options).

---
Tags: xna, textures, rendering
---


# Question
Title: I need help with 2D collision response (of stacking rotating polygons, with friction and gravity, for a game)
Hi I am looking for suggestions on how to write a collision response for game programming purpose (so not a scientific simulation). I am dealing with 2D polygons that are rotating, and I want them to be able to stack. I also want friction and gravity. I have a detection mechanism that returns the separating axis, how long the polygons are overlapping, and up to 2 points of contact. For the response, I am currently using an impulse-based response, which main idea is:

1. find the separating axis, length of overlap, and the point of contact (if there are two, pick a random point between to simulate averaged force. i believe there are better ways than this)
2. separate the object (modifying their positions, taking into account of their masses. i do not separate them completely though, to keep track that they are colliding to reduce jitter)
3. calculate normal force based on the coefficient of restitution as if there is no friction.
4. calculate friction, as if there is no normal force. I also assume that the direction of the friction is the same throughout the collision.
5. apply the two forces (which result in a rather inaccurate result, since each force is calculated as if the other is not present. for non-rotating bodies though, this method is exact)

I am aware that this method requires the coefficient of friction to be sufficiently small due to the assumption that the direction of friction stays the same in a collision.

Also, the result is visually satisfying if gravity is not present. However, when there is gravity, objects on ground jitter and drift (even with zero coefficient of restitution)! It also happens for stacking objects. Larger coefficient of restitution and gravity increase the jittering.

I hope you can help me with this. Some things i would like to know more about is how to handle collision with two point of contacts (how to end up having an object sitting still on the ground?), how to reduce, and prevent if possible, jitter and drift (do people use the most accurate method possible, or is there a trick to overcome this?), and how to handle multiple objects collision (for example, in the case of stacking objects, how do I check collisions between all of them and keep them all stable at every frame so they don't jitter?). A total reformulation of my algorithm is also welcomed, as long as it works. Another thing to note is that I am not making a Physics game, so I only need a visually satisfying response (though a realistic response is preferable, if it is not performance-heavy). But surely jittering and drifting objects on flat ground are not at all acceptable. In addition, I am a Physics student, so feel free to talk about impulse and whatever needed.

Finally, I'm sorry for the long post. I tried to be as concise as I can. Thank you for reading it!

EDIT

It seems what I didn't manage to come up all this time is to separate resting contact as a class of its own and how to solve them. Currently reading the paper suggested by Jedediah. More suggestions on the topic are welcome :)

CASE CLOSED

After reading various papers referenced in the paper, successfully implemented simultaneous impulse method (referring to the original paper by Erin Catto, \[Catt05\]). Thanks maaaan!! The paper is wonderful. The current system is visibly much better than the previous.

Still haven't separated resting contact as a class of its own though, which brings me to my next question. Love you all! Haha (sorry, I'm just so happy thanks to you).

# Answer
Google "resting contact" -- physics engines typically handle it as an explicit state, rather than allowing objects to collide continuously, which causes jitter. Check many sources. There are a variety of approaches and none of them are easy, unfortunately.

This paper serves as a good overview of all aspects of physics simulation, including resting contact.
> 3 votes

# Answer
Take a look at SAT. Separating axis theorem. Also this is nice website http://www.metanetsoftware.com/technique/tutorialA.html Doesn't seem to explain everything that you have asked, but a good part of it.
> -1 votes

---
Tags: 2d, collision-detection, rotation
---


title: Concerning The Minecraft Skybox

text:
# Question
Title: Concerning The Minecraft Skybox
I was wondering how does the stars in night time in minecraft work, are they point sprites? And are they placed on a texture or just randomly placed on some far away location.

**EDIT 1:**

OK, well, with the imformation gathered concerning the minecraft skybox I now know that the stars are not directly textured onto a sphere but are individial quads placed some set distance (the radius of the sphere) from the player.

The problem is now I will I go about getting a random position on that sphere (not in it and not too far out of it). And how will I get rotation for it to face the player? One user suggested normalising a random Vector3 then multiplying it by the spheres radius which I think, simply won't work. Also another suggested that I use the formular: "1 = x^2+y^2+z^2", I don't know how I would use this to find a random position on a sphere either.

**EDIT 2:**

OK, I haven't tested this or anything but from all the imformation gathered from PrinceCharles anwser it should be something like this:

```
            float x = (float)random.NextDouble() * 2 - 1;
            float y = (float)random.NextDouble() * 2 - 1;
            float z = (float)Math.Sqrt((double)(1f - x * x - y * y));

            Vector3 randomPoint = new Vector3(x, y, z);

            if (randomPoint.Length() != 0)
            {
                randomPoint.Normalize();
                Vector3 pointOnSphere = randomPoint * radius;

                                  // Position     Rotation
                stars.Add(new Star(pointOnSphere, new Vector3(0, 0, 0)));
            }

```

The reason for the "\* 2 - 1" is to give the random a range of -1 to 1. I think that is correct...

**EDIT 3:**

One side of the map:

The other:

Any ideas?

Thanks :)

# Answer
> 3 votes
You want hemisphere point picking, which is not trivial to get right.

It is **incorrect** to pick uniform `x`, `y` and `z` coordinates and normalise them.

It is **also incorrect** to pick uniform angle values.

I believe the less computationally expensive method is derived from Marsaglia’s sphere point picking algorithm:

```
float x1, x2, p, q;
do
{
    x1 = (float)random.NextDouble() * 2.0f - 1.0f;
    x2 = (float)random.NextDouble() * 2.0f - 1.0f;
    p = x1 * x1 + x2 * x2;
} while (p > 1.0f);
q = 2.0f * sqrt(1.0f - p);

return Vector3(x1 * q, x2 * q, abs(1.0f - 2.0f * p));

```

Note: if you get rid of the `abs()` you get full sphere picking, which might be useful, too.

# Answer
> 6 votes
They're not point sprites because of:

* Minecraft doesn't used GLSL, and you can't easily do variable sized (or rotated) point sprites without shaders.
* Point sprites can't be partially clipped at the edge of a screen, while Minecraft's stars can be.

They're just boring old white polygons placed camera facing as if on the inside of a sphere with a bit of blending. Nice effect.

# Answer
> 1 votes
Probably just part of your question:

The mathematical definition of a unit sphere (e.g. 1 unit radius) is 1 = x² + y² + z²

Therefore to find a random point on a sphere you can choose any two of the variables in that equation and calculate the third. What's important here is, that x,y,z must be in the range of -1 to 1 - As mentioned the sphere has radius 1.

So lets say i randomly chose x = 0.5 and y = -0.75 then to calculate z we have to solve:
z = SQRT(1 - x² - y²)
z = SQRT(1 - 0.5² - 0.75²)
z = SQRT(1 - 0.25 - 0.5625)
z = SQRT(0.1875)
z = 0.4330

This vector (0.5, 0.75, 0.433) lies on a sphere with radius 1 and can then be multiplied by any scaling factor to get a point on a bigger/smaller sphere.

Hope that helps!

**EDIT 1:**

I haven't tested this either but from what Kevin Reid and BiAiB mentioned this will give you a uniformed distribution (over a whole sphere):

```
        float x = (float)random.NextDouble() * 2 - 1;
        float y = (float)random.NextDouble() * 2 - 1;
        float z = (float)random.NextDouble() * 2 - 1;

        Vector3 randomPoint = new Vector3(x, y, z);
        if(randomPoint.Length() != 0)
          Vector3 pointOnSphere = randomPoint.Normalize();

```

To find a point on a half sphere (depending on your orientation of the world) choose one coordinate from 0 to 1:

```
        float z = (float)random.NextDouble();

```

To get a bigger/smaller sphere multiply the `Vector3` with the desired `sphereRadius`

```
          Vector3 pointOnSphere = randomPoint.Normalize() * sphereRadius;

```

---
Tags: xna, minecraft-modding, random, fixed-point
---


# Question
Title: How to separate colliding objects without creating more collisions
Suppose I use a simple discrete collision detection system where I move all objects then check for collisions. I want any colliding objects to be separated (of course) and assigned appropriate response velocities (bounce, slide, stop, etc.).

When I have a pair of colliding objects, how do I separate them without ending up with one or both of them colliding with other objects?

# Answer
This is not an easy problem to solve in general. In a physics engine it would be handled by the contraint solver. There are many different types of constraint solvers, but one of the easiest to understand is a sequential impulse solver.

Erin Catto gave a nice explanation of a sequential impulse solver at several previous GDC's, they can be downloaded from the Box2D download page, see the GDC 2009 one for example.
> 8 votes

# Answer
The only way you can keep this from happening is to prevent penetration in the first place. Before you move an object you make sure it's a legal move. Note that this means you must move your objects one at a time to avoid the case of two objects moving into each other.

If no penetration occurs you don't have to reset any positions and thus you won't trigger any secondary penetrations.
> 3 votes

# Answer
What I usually do is the following:

When you separate objects and you end up with more collisions, you just iterate again, until a maximum amount of steps is reached or the objects penetrate less than a predefined threshold.
> 2 votes

---
Tags: collision-detection, collision-resolution
---


# Question
Title: Creating an unbiased deterministic collision resolution order
I'm working on a game with a replay system, so I need the game logic to be deterministic. A part of this is collision detection and I'm having a bit of a conceptual problem here. (I'm programming in Python but I think my question is more general than that.)

I need collisions to be solved in a deterministic *unbiased* order. For example, it would be unfair if collisions would always be solved first for the red team, because e.g. they would always collide with (and thus pick up) ammo first. I can't imagine I'm the first person experiencing this problem.

The way the engine works is somewhat as follows:

**Until no objects colliding:**

* Find overlapping objects and separate them
* Add the object pair to a "collided" *set* (so no duplicates).

**Finally:**

* **Sort** the "collided" set based on some property.
* Iterate through "collided" set and tell each object pair that they collided with the other object.

Is there a way to sort the set for this final iteration while keeping it fair?

Things that won't work:

* Memory location (python's default for sorting objects) because this is nondeterministic.
* Internal object ID's, because these ID's are always lower for the "red team", as they are added first.
* X/Y coordinates, don't give a complete sorting order, because objects can have identical positions, additionally, this is biased because the "red team" spawns at X=0.

# Answer
You could use a hash function applied to the object ID as a sort key. This would randomize the order but ensure it was the same order on every run of the game. However, this would still be biased in a way because objects that happened to get small hash values would always solve first. There just wouldn't be any particular pattern to which objects those were. To solve this you might incorporate the frame count or timestep count since the beginning of the game into the hash, so that the hashes will effectively be re-randomized each frame.

Using a hash is a lot like using a seeded RNG and only extracting one number from it. The Python library includes the CRC32 hash (in the zlib module), which may suffice for your purposes.
> 3 votes

# Answer
I would use a random number generator because they are in fact deterministic. Here's the doc for the Python random generator: http://docs.python.org/library/random.html

How it would work is that you'd want to seed the random number generator using the same seed for actual game as for the replay (save the value in the replay). You'll only want to seed it once per game/replay and you need to use the same random number generator through the entire system (or multiples if you save and restore each seed). As long as you are retrieving the same count of random numbers, it will produce the same sequence, so make sure you are using a fixed time-step in your game and everything will work fine.

See here for more information on fixed vs variable time-steps: When should I use a fixed or variable time step? I think you'll need a fixed time-step if you want the replay to be exact.
> 2 votes

# Answer
Without seeing the code, I am having trouble conceptualizing the problem. That said, here are a few ideas that may or may not be useful:

* You mentioned the second step is 'Add the object pair to a "collided" set'. Could you add a sort key during this step?
* How about keeping track of elapsed seconds, ticks, or turns since the start of the game and using that as a seed for "random"? Assuming you have a repeatable/predictable number here, the random number will be deterministic.
> 0 votes

---
Tags: collision-resolution, replays
---


# Question
Title: Dealing with occlusion in an isometric sandbox game
Imagine a 3D sandbox game like Minecraft with third-person isometric graphics. If the camera only moves in two dimensions, and doesn't rotate, then a large portion of the world will always be occluded e.g. caves, areas behind mountains and buildings, etc. Obviously this isn't acceptable.

I'm trying to figure out how such a game could deal with this issue while preserving certain properties: the world must be entirely buildable/destructible and must extend *in some manner* along all three axes. Other than that, nothing is off the table.

I can't think of any simple culling algorithm that wouldn't either leave too much occluded or needlessly cull things. Which features are visible where seems to be a very high level design issue. If you are underground, you don't want to see the ground above you at all. But some small objects you probably never want culled, even when standing behind them.

And it's not at all clear what you would want to do with medium-sized objects, like buildings... perhaps make them translucent when the player walks behind them. But how would such objects be classified? And how would you distinguish the outside of the building from the inside? You probably don't want the inside of buildings to become visible when you walk behind them.

If the player can place objects anywhere, what happens if they place an object behind an occluder? Is it now impossible to interact with this object without destroying the thing in front of it, even when the player is standing right next to it? What about important features on back-facing surfaces? Are they never rendered at all?

It seems to me that isometry is just not capable of practically representing arbitrary three dimensional architecture, which suggests that the game needs to be designed in such a way that arbitrary architecture can't be built. Rather, it needs to be constrained to some kind of 2.5D model, where occluded things simply cannot exist. But how could a world like that feel consistent and logical to the player while they dig and build in it?

# Answer
**Deciding which criterion to start with**

I'd say the reason you're asking the question in the way you have (i.e. not a single question but many smaller ones), is because you have various explicit requirements that you have not reconciled: culling what should be culled, not culling what shouldn't be culled, and using alpha where you need foreground objects to not obscure key gameplay objects in the midfield. I guess you're less-than-willing to start down a path that might not fit your exact requirements. But sometimes, *experimentation is the only way* to get rolling. Choose to implement ONE of these. To start with, draw EVERYTHING, just allow overdraw for now -- given a limited world height, even heavy overdraw should not grind your FPS too badly (unless you're writing in ActionScript or JavaScript, and the overdraw is major), because you're looking toward the ground, not toward some far horizon. Even so, I provide a solution for isometric occlusion culling below. Anyway, from drawing everything, you will find that it's much easier to simply move toward achieving your other two criterion. *You need a base to experiment with*.

**Foreground alpha**

I assume you don't want the player to be hidden behind walls. How about enemies? Items? Controls (including ones situated on back-facing walls)? I'll have to assume all, for the purposes of responding.

Whatever is directly between your ortho camera and any gameplay-critical entities, must be made transparent OR culled completely from the view.

For walls near to your player, simply make surface voxels transparent (never consider non-surface voxels for rendering). You need to determine the silhouette of the entire clump that would occlude, and render it only as a silhouette at a single alpha (say 10%). If you were to simply treat each voxel as being at a given alpha, their transparencies might combine to be so opaque so that you would hardly see the critical entities beyond them.

You furthermore mentioned the insides of buildings, which could equally be seen as other rooms (if eg. your game was in a dungeon environment). The best way to deal with this is to keep a list of bounding boxes describing other rooms, and use these for additional zone-based culling. This could be the same as, or separate from, your level chunks. I would recommend it be separate as chunks should ideally be based on a uniform grid in order to keep processing times uniform regardless of where in the world you are. Using non-uniform bounding boxes can mess with this.

**Culling what is definitely occluded by opaque objects**

Consider a standard isometric engine. Occlusion is often not explicitly handled, because the degree of occlusion is minimal enough in most cases that we can afford to ignore it. In your case, however, it is necessary to know what *not* to draw. This is a perfect application of the reverse painter's algorithm. Determine the lines of voxel "bases" closest to the lower edge of your screen. In each such "tile" along this line, there exists a column of voxels. Draw each voxel in this column, from the base point near the bottom of the screen, upwards. Proceed to the next row above it, and repeat, till you've drawn all rows in the scene. As for knowing what NOT to draw, this image represents the tile base positions on your screen (the bottoms of all voxels at sea level):

```
* * * * * * *
 * * * * * *
* * * * * * *
 * * * * * *  <- Second last row
* * * * * * * <- Baseline row

```

Do you see how the second last row's voxel bases are offset from the baseline's? Every second row's tile centre lies exactly between the next and previous line's x-centres? Same thing, with graphics:

Because of this, the first (leftmost) tile column in the second-from-last line is only occluded if the first AND second tile columns in the baseline BOTH exceed the height of the column that lies behind/between them. If they are equal, then you won't see the sides of the voxel behind, but you will see it's top -- so it will still need to be drawn. If less than both, it is completely occluded.

This solution will not entirely eliminate overdraw (since you still need to draw a whole column even if only one of the two in front of it is occluding it), but it certainly will make a major difference. For complete elimination of overdraw at a per-pixel level, see below.

Dealing with overhangs / floating voxels shouldn't be too hard to figure out given the above.
> 4 votes

# Answer
I have considered this problem myself and the only solution I have been able to come up with is to allow rotating the camera (or more technically correct, the map).

This will let you see the player/items that are in range (by removing anything that is blocking your observer line of sight), and it also lets you interact with any item even if you are deep underground, because the things that are between you as the observer and the player is removed, so if you want to interact with any of the blank stuff, you just rotate the camera, and make the other side transparent instead.

I've thought of how to make this as unnoticeable (hassle-free) as possible, and one or two hotkeys near the wasd keys may be appropriate (C or V rotates the map 90 degrees, and as a result the wasd keys change orientation, but this is not noticeable, because "up" is still "up", even though internally the direction is a different one.)
> 1 votes

---
Tags: isometric, minecraft-modding, voxels, occlusion
---


# Question
Title: Algorithm for generating levels for shooting game
I have a shooting game made in Java. It's based on time, i.e you have to shoot the objects before the time runs out. Everything is working fine, except that I'm trying to implement an algorithm to generate levels. I implemented one that increases the number of game objects and increase their speed, but I don't know how to give the player an appropriate time based on these factors to provide an appropriate challenge for the player.

# Answer
> 1 votes
Part of the increase in challenge will come from reducing the reaction and aiming/firing time that you allow the player to take.

What I would suggest starting with is assuming a large amount of time per object. Let's say 5 seconds or something like that. You probably also want some initial buffer time.

So if there are 20 objects in the scene, and you start with a 5 second per-object allocation of time, and a 5 second initial buffer, your level ends up being (20 * 5) + 5 = 105 seconds.

To increase the challenge, reduce the amount of time. Since the game will get significantly harder you probably want to slow down the reduction in time over time instead of using something like a straight linear function. Something like amount of time per object = f(x) = 5 - ln(x) would be a place to start.

You can also start staggering your levels. Say, a set of 5 levels uses the same reaction time, but increases the speed. Then the next block resets the speed but uses a lesser reaction time.

# Answer
> 1 votes
I think the main thing is to make your own algorithm and tweak it. Consider first a high-level; how do you want the speed, number of objects, etc. to grow? Is it a linear curve? Exponential curve? etc.

Start with something basic like that (eg. `number of enemies = level ^ 2`), and tweak coefficients until you feel that it's suitable.

# Answer
> 0 votes
lets say it takes `x` seconds to shoot down a game object is a specific level, where `x` should be calculated based on the object speed / hit points / etc., in that particular level.

let `n` be the number of game objects in a particular level. then you give `n*x + bonus` seconds.

hope it helps...

---
Tags: algorithm, level-design
---


# Question
Title: Cocos2d: how to add anchor points to CCSpriteBatchNode
I am doing some tests with animations in Cocos2D using sprite-sheets. The animation works ok except that the anchor-point is in the center. I need to put it in the bottom. With the code below i am not able to add an anchor-point to my sprites, after quite a few tests.

Would someone nice be able to help me with this?

```
-(id) init {

    if((self = [super init])) {

        [[CCSpriteFrameCache sharedSpriteFrameCache] addSpriteFramesWithFile:@"ratHammer.plist" textureFile:@"ratHammer.pvr.ccz"];
        CCSpriteBatchNode *spriteSheet = [CCSpriteBatchNode batchNodeWithFile:@"ratHammer.pvr.ccz"];
        [self addChild:spriteSheet];
        NSMutableArray *walkAnimFrames = [NSMutableArray array];
        for (int i = 0; i <= 5 ; ++i) {
            [walkAnimFrames addObject:[[CCSpriteFrameCache sharedSpriteFrameCache] spriteFrameByName:[NSString stringWithFormat:@"ratHammer_anim%d.png", i]]];
    }

    CCAnimation *walkAnim = [CCAnimation animationWithFrames:walkAnimFrames delay:0.1f];

    CGSize winSize = [CCDirector sharedDirector].winSize;
    self.bear = [CCSprite spriteWithSpriteFrameName:@"ratHammer_anim0.png"];
    _bear.position = ccp(winSize.width/2, winSize.height/2);
    self.walkAction = [CCRepeatForever actionWithAction:
                       [CCAnimate actionWithAnimation:walkAnim restoreOriginalFrame:NO]];
    [_bear runAction:_walkAction];
    [spriteSheet addChild:_bear];

}
return self;

}

```

# Answer
You can modify the anchor point location by setting the `anchorPoint` property of your sprite.

The anchor-point should be given as `CGPoint` and is normalized to `0..1` for both axes. Per default it's at `0.5, 0.5`. The lower left would be `0.0, 0.0`.

To set the anchor point to the lower left, you would use something like this:

```
[spriteSheet setAnchorPoint: ccp(0.0f, 0.0f)];
[_bear setAnchorPoint: ccp(0.0f, 0.0f)];

```

If you need further information, here are the relevant API docs.
> 2 votes

---
Tags: cocos2d, objective-c, spritesheet
---


# Question
Title: In tools development, what languages and technologies are currently in use?
I am an aspiring tools developer currently in university. Normally I use both C++ and C# to and from but as my time at university is coming to an end, what language and technologies are worth focusing on? With tools I'm not only thinking simple data-file editors, but level editors and such as well.

I have tried searching in numerous places but generally I only find questions regarding what language or tools to use for game development. As I want to create the tools rather than use them, the answers don't necessarily apply.

Seeing as C++ still seems to be the language of choice in the gaming industry, is it also still the primary language for tools? If so, what UI and core libraries are most prominent? wxWidgets and stl/boost? Plain Win32?

Or - if C++ is being phased out in favor of "easier" languages like C# - is WinForms the right pick, or is the industry moving towards WPF? Maybe scaleform internally as well?

In short, is there anything I absolutely need to know to not be just an expensive chair heater?

# Answer
> 6 votes
> In short, is there anything I absolutely need to know to not be just an expensive chair heater?

Yes, that you are asking the wrong kinds of questions. Technology and requirements will change and you will be required to adapt. Don't worry too much about learning the "proper" language or technology. Learn to think and to solve problems. At best you will be minimally competent when you graduate anyhow.

That said, there are no industry standards for this sort of thing. In my experience, C# is gaining quite a lot of ground within the industry for tools work. But there are still tools written in C++, in pure Win32, in WxWidgets or some other GUI framework. Just as with C# you'll have teams writing tools in Windows Forms, WPF, GUI toolkits built on those (such as DevExpress). Many times you will be interfacing with the extensive existing game-side APIs as well. You may be using Python or Dephi.

Working in tools provides a wealth of options, even more than working in the game-side code itself (which, as you note, *is* almost exclusively C or C++ these days). Certainly exposing yourself to a broad array of languages and technologies while you are in school is a good idea, but I would strongly urge you to do so because you are interested in that language or technology for its own sake rather than because you're guessing that it will be the "right" thing to know come job application time. It's actually surprisingly easy to tell in an interview if a candidate was exploring a technology because he or she had a passion for it, or if he or she was just doing it to stick it on a resume.

---
Tags: gui, tools
---


# Question
Title: Rendering a lot of Models at once with XNA
In an hexgrid based game, I render all terrain tiles as a separate model, reusing the same texture objects on all similar tiles. The tiles is a pretty simple model.

When the terrain is set to be at 20x20 or more (so 400 tiles), the game really slows down. The "slowdown point" is about the same on my i5 laptop or my i7 desktop. The game takes around 30megs in the memory. Here is how the render looks like :

The way I render each tile is the following :

```
foreach (ModelMesh mesh in ModelSupport.Meshes)
{
    foreach (BasicEffect effect in mesh.Effects)
    {
        effect.EnableDefaultLighting();
        effect.World = transforms[mesh.ParentBone.Index]
            * mScale * mRotationY * mPosition;
        effect.View = Camera.ViewMatrix;
        effect.Projection = Camera.ProjectionMatrix;
    }

    mesh.Draw();
}

```

Any suggestion of how I could optimize the rendering of a large amount of models?

# Answer
> 10 votes
I believe you want hardware instancing.

http://xbox.create.msdn.com/en-US/education/catalog/sample/mesh\_instancing

# Answer
> 1 votes
If you're really rendering each tile as a static hexagonal model, then you're wasting a lot of resources on the side faces that will not be visible.

Think about doing it like Minecraft, instead: generate the side faces programmatically (or create them as separate models from the top), and include each face only if its tile is *higher than its neighbor* in that direction, and make them no taller than necessary. Take a reasonably-sized bunch of such computed tiles and put them all in one vertex array.

---
Tags: xna, c#, rendering, models, optimization
---


title: OpenGL relative 2D camera

text:
# Question
Title: OpenGL relative 2D camera
Some days ago, I've felt a need to add a camera to my game, it's a puzzle. That would let me move the board, zoom in and etc. This gave me control to do boards muuuch larger, soon, more complex puzzles.

But today when i was implementing such a toolbar, I've found which problems the camera gave me too.

In logic, it is simple. I want the toolbar to be fixed, and the board be free. That is, when I zoom in, the board zoom, but the toolbar stays.

My camera code look as follows:

```
    public void Camera::draw(GL10 gl) {
    gl.glMatrixMode(GL10.GL_PROJECTION); // Select the projection matrix
    gl.glLoadIdentity(); // Reset the projection matrix
    gl.glOrthof(0.0f, width * zoom, 0.0f, height * zoom, 0.0f, 1.0f);

    // Translating
    gl.glMatrixMode(GL10.GL_MODELVIEW);
    gl.glLoadIdentity();
    gl.glTranslatef(-position.X, -position.Y, 0);
}

```

Very simple, but stills functional.

To draw a scene I do the following:

```
public void Game::draw(GL10 gl) {
    camera.draw(gl);
    currentLevel.board.draw(gl);
}

```

I've came with the problem to add the toolbar.

```
public void draw(GL10 gl) {
    toolbar.draw(gl);
    camera.draw(gl);
    currentLevel.board.draw(gl);
}

```

I've thought about letting it came first than the camera draw, so it would be fixed. I was wrong.

Nice images examples for you:

*A normal board*

*The effect expected for zoom in, just the board zooms*

*The effect that i got when i zoom in everything zooms, even the draw that came before the camera.*

You can think of this as a camera that supports HUD. I saw people solving this by using a scale factor instead of using glOrthof. But this would mess all my coordinate system. Are there any other alternative for me? If so, how can I implement it?

# Answer
> 3 votes
It looks like your problem is that your not resetting your GL\_PROJECTION matrix after you draw the zoomed in board.

Then next render loop its still using the zoomed in projection matrix. When it draws the next board it will set the projection matrix to the same thing again.

Either set it to the default unzoomed matrix at the beginning of the loop or after you draw the board.

Otherwise you can use glPushMatrix and glPopMatrix to store and revert to the previous state.

EDIT: Also be aware that glMatrixMode, glLoadIdentity, glOrthof, glTranslatef, glPushMatrix, glPopMatrix are all fixed pipeline functions that are deprecated/removed in modern OpenGL versions and have been replaced by uploading matrices to shaders. Might be fine for learning (then again it might be best to learn the proper way from the start).

EDIT2:

```
public void Camera::draw(GL10 gl) {
    gl.glMatrixMode(GL10.GL_PROJECTION); // Select the projection matrix
    gl.glLoadIdentity(); // Reset the projection matrix
    gl.glOrthof(0.0f, width, 0.0f, height, 0.0f, 10000.0f); // <- No zoom here anymore, increase view distance
}

public void drawBoard(GL10 gl) {
    gl.glMatrixMode(GL10.GL_MODELVIEW);
    gl.glLoadIdentity();
    gl.glTranslatef(-position.X, -position.Y, zoom); // <- Zoom goes here (possibly it should be negative)
    currentLevel.board.draw(gl);
    gl.glLoadIdentity();
}

public void draw(GL10 gl) {
    camera.draw(gl); // This should actually only need to be done once (and on window resize)
    toolbar.draw(gl);
    drawBoard(gl);
}

```

---
Tags: opengl, 2d, camera
---


# Question
Title: What are the pros and cons of Lua vs. Python as a scripting language for XNA/C# platform?
I am thinking about giving a go to one of my ancient ideas for a game. The core point of this game would be the possible level of functional customization of the game environment and objects (such as modifying the behavior of a space ship weaponry). For this the game would need to be scriptable. Also I don't aim to commercialize it, it is merely an interesting programming challenge for me.

As I am mostly a .NET guy I will use XNA/C# for the game itself. For the scripting I think about going with Python or Lua. I have previous experience with Python and have nothing against it as a language. Lua on the other hand is almost completely new to me, besides some minor World of Warcraft addons modifications I did here and there, and it looks promising. So here is my question:

**What are the pros and cons of Lua vs. Python as a scripting language for XNA/C# platform?**

Is one of them considerably easier to use with XNA/C#? Has one of them some specific advantages or disadvantages when used with XNA/C#? Why would you recommend one over the other for XNA/C#?

# Answer
> 11 votes
I can't compare the two, as I've only had experience embedding IronPython in a C# game so far. Here's what I like about it though:

1) It's easy! Download the IronPython DLLs, add reference in project,

```
 using IronPython.Hosting;

 var engine = Python.CreateEngine();
 var product = engine.Execute<System.Numerics.BigInteger>(@"
 print ' '.join(['hello', 'from', 'ironpython!'])
 a = 123456789
 b = 10
 a**b
 ");
 Console.WriteLine("a**b={0}", product);

```

2) As you can see from the above example, IronPython actually converts to BCL classes where it can. the result of the script is a System.Numerics.BigInteger rather than a PyObject

3) The `dynamic` keyword in C# was made for interop situations where you don't have the static type available:

```
    dynamic example = engine.Execute(@"
class Example(object):
  def __init__(self):
    self.breakfast = ['ham','spam','eggs']
    self.lunch = 'BRAIINNNZ'
Example() # return an example");

    foreach(string item in example.breakfast)
        Console.WriteLine(item);
    Console.WriteLine(example.lunch);

```

# Answer
> 0 votes
IronPython and C# go well together, IronPython can be added to C# to give it boost in performance. So if your writing games then Python calls within C# are an advantage. Python itself can't make use of XNA but can make use of Directx something C# can't do directly.

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


# Question
Title: Designing Collision Detection for 2D Rectangular Adventure/RPG
**TLDR:** I'm looking for an efficient way to detect collisions between irregular/small objects that are not a full tile size (like small cans) and a free-moving character in a 2D game.

---

I'm planning to design a 2D RPG-style game in XNA. It will be similar to the style of Chrono Trigger (pictured below) -- I will explain what that means. The main issue I have is how to properly design the collision detection.

First, a description of two of the main points of my game design:

* Sprites are rectangular. So a character is **two parts**: lower-half (which collides with solid tiles) and upper half (which is "above" the lower half).
* Free movement. Even though I use tiles, you don't move from tile to tile; you can move in **any direction in a small increment** (such as 8px).

Another important aspect of my design is that *I don't (can't?) do any pre-processing on images to detect collision spaces.* It must be either generic (eg. a 4px range outside of each tile), or cheaply calculatable. (This is to make it easier to develop by cutting down on the time needed to make sprites.)

My initial design for this (which I prototyped) was to use the (bottom half of the) character to collide with anything on the "ground" level. This works well with things that are full-tile covering (like walls), but not small objects (like cans). Pixel-level collision detection solved this, but can lead to irregularities, problems with granularity (eg. checking 4 pixels to either side), and of course, performance.

What I really want in this case is for the character to **be able to move close to small or irregular objects.** Is pixel-level collision detection the right answer? What about encapsulating it in a small polygon approximation (say a rectangle, even) and colliding with that area? I'm concerned that, even with spatial partitioning, the performance will be poor and the user perception of collision will be poor-quality.

How do other 2D games deal with this?

# Answer
I'm also working on a retro style RPG but rather than pixel perfect collision I am using circles and ellipses centered on the "feet" of my sprites. My world is made up of square environment tiles with some other shapes on top like tables, trees, and bookcases. These simple shapes are super cheap to collide, scale, and store and they give really nice "sliding" effects when they move against each other since the tangents and normals are trivial to compute and you can project your velocities along them.

In this kind of design the collision shapes are totally independent of the graphics and can move in any direction by any increment. You could take this further if you need more precision -- say you were throwing a hammer: if a bounding circle is not precise enough, use an ellipse or an object aligned bounding box. If that's too sloppy, compose the collision shape out of primitives, like a thin rectangle for the handle and a circle for the head.

Games are often more about smoke and mirrors than actual simulation, so do what's 1) cheap 2) looks reasonable 3) is fun

good luck!
> 4 votes

# Answer
My approach has always been to use rectangles and a simple version of SAT (Separating Axis Theorem) to resolve collisions.

Here's a sample python implementation (as my C# skills are lacking).

```
class Vector:
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Rectangle(Vector):
    def __init__(self, x, y, w, h):
        self.x = x
        self.y = y
        self.w = w
        self.h = h

def intersect_rect(rect r1, rect r2)
    #r1.x1 < r2.x2; etc.
    return (r1.x - r1.w) < (r2.x + r2.w)
    and (r1.y - r1.h) < (r2.y + r2.h)
    and (r1.x + r1.w) > (r2.x - r2.w)
    and (r1.y + r1.h) > (r2.y - r2.h)

def overlap_rect(r1, r2):
    dx = r1.x - r2.x
    dy = r1.y - r2.y

    #Absolute value
    if dx < 0: dx *= -1
    if dy < 0: dy *= -1

    ovlx = (r1.w + r2.w) - dx
    ovly = (r1.h + r2.h) - dy

    if ovlx < ovly:
        ovly = 0
        if r2.x < r1.x: ovlx *= -1
    else:
        ovlx = 0
        if r2.y < r1.y: ovly *= -1

    return Vector(ovlx, ovly)

```

The overlap\_rect function returns a vector that, if subtracted from r1's position will separate it from r2, or added to r2's position, will separate it from r1. If both move, then use half the separation vector. A very simple collision function looks like this:

```
class Body(Rectangle):
    def __init__(self):
    # I hope I did the super() correctly
        super(Body, self).__init__(0, 0, 0, 0)
        self.no_collide = False
        self.is_static = False

        #Function stubs
        self.pre_collide = None
        self.post_collide = None

    #in here goes integration stuff, materials etc

def collide(r1, r2)
    if intersect_rect(r1, r2):
        if r1.pre_collide:
            r1.pre_collide(r2)
        if r2.pre_collide:
            r2.pre_collide(r1)

        if not r1.no_collide and not r2.no_collide:
            if r1.is_static and not r2.is_static:
                v = overlap_rect(r1, r2)
                r2.x += v.x
                r2.y += v.y

            elif not r1.isStatic and r2.isStatic:
                v = overlap_rect(r1, r2)
                v.x *= -1
                v.y *= -1
                r1.x += v.x
                r1.y += v.y

            elif not (r1.isStatic and r2.isStatic):
                v = overlap_rect(r1, r2)
                v.x /= 2
                v.y /= 2

                r2.x += v.x
                r2.y += v.y

                r1.x -= v.x
                r1.y -= v.y
        if r1.post_collide:
            r1.post_collide(r2, v)
        if r2.post_collide:
            r2.post_collide(r1, v)

```

Though the broadphase in that is nearly non-existent, and neither does it take into account any form of momentum or restitution, it should be enough for something very simple.
> 0 votes

---
Tags: 2d, collision-detection, rpg, adventure-games
---


# Question
Title: How to simulate backspin or topspin in a box2d billiard game?
I am designing a simple billiard game with box2d. I think I can easily simulate hitting left or right side of a ball. Since box2d is not 3D, however, I am not sure how to simulate hitting upper or lower part of ball with a cue.

In case you are not familiar with the game. If the ball is hit on its upper part, it's still going forward after hitting another ball. But when cue hit on its lower part, it should backspin as soon as striking another ball.

Is this simulation possible with box2d? If so, a hint or reference will be appreciated.

# Answer
First off; I am not familiar with box2D and may not have the right terminology for physics. But storing the top/backspin *should* be as simple as storing a 2d vector for the potential velocity the ball is "carrying" from when the spin started. Then on collision detection you perform the normal collision and after that you apply the spin. Some tweaking would be required to make it feel right.

Also though, top/backspin affects the balls trajectory depending on how much grip the ball has, correct? So you would probably need to add code for each simulation step to check how much velocity it would transfer depending on the balls current velocity and the friction between the ball and the table.

Hope it helps.
> 6 votes

---
Tags: physics, box2d
---


# Question
Title: How do i calc what side the ball is of the rect?
I have this nice drawing:

http://bildr.no/view/1085283

I know the ball's center and the rectangle's center, but how do I know (programming C#) what side of the rectangle the ball is?

By my drawing, the answer in this case should be the right side.

# Answer
What side of A is B on? Using this info (see Solution 3) you can determine which side of a line A point (or points) B, is on.

For your particular scenario, you need to check which of four sides of the rectangle, the circle is in. In this case, you can treat your circle as just it's centre/origin point. Now you need to look at the rectangle like this:

```
\       /
 \ q1  /<--one of the two lines bordering quadrant 4
  *---*
  |\ /|<---rectangle edge for quadrant 4
q4| x |q2
  |/ \|
  *---*
 / q3  \<--one of the two lines bordering quadrant 4
/       \

```

The `q`'s stand for quadrant or *side* of the rectangle you're on; the numberings are abritrary, but just show you that the centre point can lie in any of these 4 distinct quadrants. You need to determine that the circle centre is:

* to the correct side of each of the two lines bordering that quadrant (the diagonal ones in the drawing above), i.e. it must lie between them;

**AND**

* to the correct side of the rectangle-edge that lies within that quadrant (between the aforementioned diagonal lines.

This will tell you if the point falls in to the bowl-shaped area on each of the four sides of the rectangle shown above.

The "correct" side is determined by you, when you construct the formula in the link given above. It depends on whether you specify a line as PQ or it's reverse, QP. This is known as winding order (see "Winding Order of Vertices").
> 2 votes

# Answer
I do this by giving all of my game entities a position (Vector 2D/3D), and a rotation (Matrix 3x3). Your rotation matrix will have either a column or row for its forward, up, and right vectors. In the case of a 2D game, the 'up' vector is unnecessary.

First you get the vector from your square's center to the ball's center.

```
Vector2 direction = ball.position - square.position;

```

Now you normalize/unitize the vector to make it represent a unit-length direction

```
direction.Unitize();

// Here's a method to unitize a 2D vector
void Vector2::Unitize()
{
    const float inverseLength = 1.0f / Length();
    x *= inverseLength;
    y *= inverseLength;
}

```

Unitizing requires knowing the length of your vector, so we make a helper method for that as well

```
float Length(void) const { return sqrtf( x * x + y * y ); }

```

Ok, now that we have a direction from the square to the ball, defined earlier by the 2D vector we called `direction`, we now do a dot-product between that direction, and the square's right vector (the direction the represents its right-hand side). For this example, in your image, let's say the square is facing toward the top of the image, and that the ball is on the square's right-hand side. Doing this dot product will tell us if the ball is on the right-hand or left-hand side of the square.

```
Vector2 squareRightVect; // You would retrieve this from the square's rotation matrix
float dotResult = direction.Dot(squareRightVect);

```

Now we have the `dotResult`, which will be a value between -1 and 1, anything greater than 0 means the ball is on the right side of the square. Based on the image I'd say the dot product would be about 0.85, putting the ball on the right side of the square. If your dot-product gave a result of anything less than zero than the ball is on the left.

And finally, here's your dot-product method:

```
float Dot(const Vector2& rhs) const { return (x * rhs.x + y * rhs.y); }

```

And here are some helpful links if you want to learn more about the processes involved in the above code:
> 0 votes

---
Tags: 2d, game-mechanics, computational-geometry
---


title: android game using bullet and libgdx

text:
# Question
Title: android game using bullet and libgdx
i'm developing a android project for school and i'm currently using libgdx for rendering. It performs quite well, but it lacks a 3d physics library. So i searched and found that Bullet physics engine was ported to android through NDK (c++). Did anyone try to connect this two libs together?

I've never used a physics engine/library before (i've mainly developed 2d games so i've made one my self) and wanted to ask if any one had any previous experiences with implementing bullet and libgdx? To be more precise i need to simulate a jump and implement physics like: wind/drag, friction, lift, gravity; during the jump.

Does bullet calculate the gravity and other forces by it self (if so can i implement other forces easily?) or can i control which element gets updated (mainly re transformed) and when? How does collision detection work (is there some kind of collision world/collection)? Can i handle collision detection on my own or does bullet take care of this as well?

Thanks for the reply's!

# Answer
> 2 votes
I believe libgdx team is in the middle of including bullet into libgdx. But as they mentioned, I am not sure when it will be done. I think this answers your first question.

For the second part of questions, I am not an expert on bullet engine, but it's called physics engine so like box2d, the main physics operation should be taken care of by itself and user can customize it with callbacks. And Update might occur after stepping. Please check its documentation for sure.

---
Tags: opengl, 3d, android, bullet-physics
---


title: IRC channel about game development?

text:
# Question
Title: IRC channel about game development?
I'm looking for some IRC channel to talk about game development.

Anyone know some?

# Answer
#ludumdare on irc.afternet.org, Other than that I suggest searching for channels about frameworks you are interested in.
> 3 votes

---
Tags: game-mechanics
---


# Question
Title: GUI.Button inside GUI.Window not responding
I am trying to do some GUI work with unity but am having some issues.

I call a window with this code:

```
fortuneRect = GUI.Window(0, fortuneRect, fortuneWindow, "Your future");

```

and inside the window I have a button

```
if(GUI.Button(new Rect(10, 10, 150, 20), "save fortune")){
       Debug.Log("save fortune button press");
       writeToFile("Button pressed!", "fortune.txt");
       Debug.Log("After save fortune button press");
    }

```

but the button doesn't fire any of its events on click. I tried commenting out the writeToFile but even with only Debugs in the body it doesn't fire.

# Answer
> 2 votes
You need to have the button code inside

```
void OnGUI() {...}

```

Provided you ignore the window part, looks fine to me: in other words, the button code on its own, without using a window, should work. Once you have the button code working, go from there. Try doing exactly the same in a brand new project, if all else fails. You should find that alone works, and something else in your current project is preventing proper compilation or runtime operation.

# Answer
> 1 votes
your sample looks like the code in Unity's docs http://unity3d.com/support/documentation/ScriptReference/GUI.Window.html so at first glance should be fine. Can you provide more info?

The first arg in your call to `GUI.Window()` should be the window id. Do you mean for that to be zero? Also, I assume your `GUI.Button(`) call is inside the 'fortuneWindow' callback function. What does the rest of that function look like? You're not inside an `if (windowId != 0)` block or `#ifdef UNITY_EDITOR` or anything? Do you have overlapping windows that might be stealing each other's focus?

What's your runtime environment? Is it a custom editor window or a game UI? Are you seeing this behavior when running in the editor or one of your build targets?

---
Tags: unity, gui
---


# Question
Title: How can I implement a "fast-forward" feature in my game?
How can I implement the fast forward feature for my tower defense game like in http://fieldrunners.com/ and other TD games?

I am using Unity 3D. Would there be something to manage fewer frames per second or some kind of manually set fast movement of enemies and tower firing speed, et cetera?

# Answer
> 7 votes
if your game doesn't have complicated or computationally expensive simulations that require separating them into independent update timelines, you can use a simple approach of basing the code in your `Update()` functions on Unity's Time.time value, and in your code set the value of Time.timeScale to be whatever you want. 0 == paused, 1 = normal, our testers love to set timeScale \> 1 to get things done faster.

http://unity3d.com/support/documentation/ScriptReference/Time-timeScale.html

# Answer
> 19 votes
**Approach: Higher simulation rate**

Your timing for your user interface should be decoupled from your actual game loop, as should your rendering. Say for example your world runs at 4x speed. Lets say that at your basic (1x) speed, your game runs 30 updates per second.

You would then have something like the following, when in fast-forward mode:

* World logic runs 4 updates for every update of UI and renderer. This means it needs to run 120 updates per second. Thus, your world *model* (data) is updated at this rate.
* Renderer and UI logic both continue to poll or do whatever at 30 updates per second.

In other words, the *game* as a whole is not running faster. The *simulation* part is.

You can deduce two things from this:

1. You need to keep your game logic simple enough that you *can* easily run it four times faster on your target platform, OR you need to introduce methods to extrapolate various aspects of gameplay more quickly -- this can result, though, in a model that is different from what it would have been if you had simply used a more rapidly paced simulation. So the tradeoff would be processing cost for accuracy. See approach 2, below.
2. It is the separation of concerns that allows you to easily speed up your world simulation, that separation being model, view and controller (MVC). If your world data(M), render logic(V), and game logic(C) are all mixed up, you really won't be able to do this, at least not without a massive migraine.

**Approach: Extrapolation based on time deltas**

As mentioned above, you'll need to calculate motion based on how far something would have travelled in a given time. This assumes your game physics are inherently more realistic in their simulation, however, which may not be the case. This is a rather larger topic and considerably more complex. You'll need to ask more questions about if you want to know. Essentially, you'll be doing some calculus to get things right. You'll need to deal with interpenetration in collisions and a host of other issues I won't go into here.

**To conclude**

This gives you the general outline. Your language choice is your own, presumably you either know how to do that in Unity or you don't. Timing in any language requires you to understand the ins and outs in detail, I'd suggest starting with Gaffer's articles and checking out the Unity API docs.

# Answer
> 9 votes
As a general principle, the update of game logic should be decoupled from the update of the game's graphics -- that is, simulation of your gameplay, AI, unit movement, et cetera should not be tied to the speed at which the game is rendering. Usually the main game loop computes how much real time had elapsed since the last game update, and sends that delta time step to the update routines of each individual game logic object.

In such a scenario, it becomes simple to implement time scaling (including fast-forwarding) in your game. Simply premultiply the game logic time step by some scalar value that controls how much to "fast-foward" or slow down time. By default this value would be one, and for example once the user hits the "fast forward" key you set it to 1.5, and all simulation would appear to go 50% faster. You would still render at the same rate, however.

I am not extremely familiar with Unity and thus could be wrong in the following suggestion, but Unity does have a time management component which may be useful for implementing this. It in fact already has a timescale property. The description of the component implies that the class was designed for physics objects, but it may be applicable to your scenario as well.

---
Tags: unity, tower-defense, timing
---


# Question
Title: glCreateShader causes segmentation fault
I can't create a shader when trying to use shaders with sfml. The function glCreateShader(GL\_VERTEX\_SHADER); causes a segmentation fault. At first I googled it and found that it does that when the program does not have an opengl context. I tried SDL first but the poor documentation and "look at the header to know what to do" made me go for sfml

the code that causes the seg fault is bellow

```
    sf::Window App(sf::VideoMode(800, 600, 32), "SFML OpenGL");

// Set color and depth clear value
glClearDepth(1.f);
glClearColor(0.f, 0.f, 0.f, 0.f);

// Enable Z-buffer read and write
glEnable(GL_DEPTH_TEST);
glDepthMask(GL_TRUE);

// Setup a perspective projection
glMatrixMode(GL_PROJECTION);
glLoadIdentity();

GLuint vertShader = glCreateShader(GL_VERTEX_SHADER);

    //...

```

I'm including glew, gl.h, sfml-window, sfml-system, using opengl 2.1 on gcc linux.

What is missing?

# Answer
You're not checking OpenGL extensions, version, or etc.

```
GLenum err = glewInit();
if (err != GLEW_OK)
  exit(1); // or handle the error in a nicer way
if (!GLEW_VERSION_2_1)  // check that the machine supports the 2.1 API.
  exit(1); // or handle the error in a nicer way

```

This code needs to happen **after** creating the OpenGL context, but **before** using any potentially-not-existing functions. More details on the GLEW web page
> 19 votes

---
Tags: opengl, sfml
---


# Question
Title: Does ContentManager.Load<T>() re-read an asset if I have loaded it before?
Or is it smart enough to know I have asked for it before and return an in memory copy created from the first call?

For example if I have a projectile's texture:

```
Texture2D projectile;

```

If then I call:

```
projectile = ContentManager.Load<Texture2D>("bullet");

```

every time I want fire a new projectile - am I mallocing this on the heap or am I referencing the same copy in memory? If I am mallocing new memory each time I could keep it in memory myself by making the Texture2D variable static and not calling new each time one is fired! (I was just wondering about the ConentManger). The documentation (as with all the XNA documentation is skint on details: http://msdn.microsoft.com/en-us/library/bb197848.aspx).

# Answer
In the same link you wrote, you'll find the following:

> Return Value
>
> The loaded asset. **Repeated calls to load the same asset will return the same object instance.**

However, normally, you'd keep it somewhere and only load it once, as it is faster to look at a global object than calling the ContentManager.Load method.
> 7 votes

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


# Question
Title: Level Design, Implying a path to the player
I am looking for articles on level design and particularly for techniques to imply a direction the player to go in, instead of another.

Like which game mechanics can be used, how graphics, sound, etc. can influence the player to go where you want.

For example in Donkey Kong Country bananas were used to show other paths or hidden areas, in Alan Wake, there were orange markers to show weapons caches.

If anyone has ideas, I'd be grateful to hear them too!

**Edit:** For anyone that is interested, I found a huge resource with thesis on this question, and others related to Level Design; happy reading!

http://guildhall.smu.edu/Level-Design.226.0.html

# Answer
This isn't an article, but there is a chapter in the book *The Art of Game Design* by Jesse Schell that discusses a concept that Walt Disney referred to as "weenies" in reference to dog handlers holding up a hot dog to control where the dog is looking. The most famous weenie Disney used was the castle in the Magic Kingdom; visitors to that theme park were inexorably drawn toward the center by the castle visible right from the entrance and throughout the park. In the book, Schell talks about using this technique in the Magic Carpet VR ride by painting a stripe on the floor to guide player's to the throne.

More generally, a "weenie" is anything that draws the player's attention. Once their attention is drawn in that direction, they tend to move in that direction. One of the best ways to draw attention is to place a desired item over there. Your example of the bananas falls under this; a lot of games will put gems or ammo or health packs on the path they want the player to take. In fact, the bananas in Donkey Kong Country are discussed at length in a couple articles on http://www.sirlin.net/

Most of the other ways to draw the player's attention are specific examples of using contrast. For example, a bright spot in a mostly dark level will draw the player's attention. Similarly, a sudden change in the audio will draw the player's attention. If you think about those old Hannah Barbera cartoons then you'll recall how a different colored bush (or something in the scenery) told you something was about to happen there.

When done sparingly, it can be fun to play with this trope. For example, when the player is suspicious that the desired item or differently colored door is tricking them into taking a more dangerous path. You don't want to overdo that though, or the player will feel like the level designer is just a sadist.

ADDITION: Oh yeah and enemies can be placed to guide the player. Enemies are an interesting sort of guidance tool because they can be either attractive (the player tends to go towards the enemies) or repellent (the player tends to avoid the enemies) depending on context. How powerful the player is relative to the enemies, what kind of reward the player gets for defeating the enemies, etc. are all factors affecting how enemies affect the player's choices.
> 20 votes

# Answer
not sure if the is relevant to what your doing but I remember some games panning or jumping the camera the first time you enter an area showing you there were secret paths available if you wanted to go find them.

another thing I remember from blue dragon was the enemy placement. a path to a treasure room or the like would have different types of enemies guarding it from the story path.

having to unlock a path also works. finding a locked door but being told the key is here somewhere and I can get in there always drives me to explore.
> 1 votes

# Answer
I think you should specify a bit more about your game. Whats your game about? What genre?

But a common technique is to use game elements to "guide" the player. For example, if your game is bloody, you can use blood splashes in the floor. If your game is dark you can use light spots. Yoy can also trigger some event that gets the camera attention.

If the point is to avoid player to go somewhere, try always to do it with game elements or distracting the player. For instance, if you want to avoid the player to pay too much attention to one scenario that is not the best of your game, you can try to create a frenetic scene there, so the user don't have time to check the defects of the scenario.

You can also place rewarding things to pick-up. You can place a bot calling your attention... etc etc but depends a lot of the game.
> 1 votes

# Answer
try to make things point in the direction you want the player to go, Grass, angles, clouds, like in a painting. put a focus in a circle or arch, use s-curves as they are pleasing to the eye. hide the area slightly to create a sense of mystery. those kinds of things, but dont spend too much time and effort on that or it might not get done.
> 1 votes

# Answer
If you want to **force** the player down a path, just create one path and let them go at it! Any other paths must logically end in dead-ends or else route back to the main path.

It depends a lot on the type of game, too. In a rogue-like, for example, you can generate a single path of rooms leading to the exit, and just branch out dead-end rooms.

In an RPG, you can (as is typically done) block wrong routes with objects/people/etc. so that the user can't take them.
> -2 votes

---
Tags: game-mechanics, level-design
---


# Question
Title: What is the math behind the light effect in krakatoa?
I'd like to know the math behind the light effect in krakatoa (click here for an example).

Light source is traveling with particles, but how is shading done? Is it something simple, like Phong shading? Is it possible to implement such effect in real time on GPU?

# Answer
> 1 votes
It looks like self shadowing particles to me; basically you have 3 point lights that move about the scene with a smoke/particle trail. The hard part with getting that look right is that the particles are translucent so you can't really do hard shadows, Volumetric Particle Shadows might be a good start for implementing a similar effect. Hope it helps.

---
Tags: shaders, lighting, graphic-effects
---


# Question
Title: How do I check collision when firing bullet?
I'm currently creating 2D game from top perspective. I'm having problems with bullets. Yes, I currently simulate their movement so user can see them (about 2x ). Moving them with

```
// this is static
Direction = new Vector2(mouse.X, mouse.Y) - new Vector2(player.x, player.y);
Direction.Normalize();
Speed = 900f;

//this is called in Draw(GameTime gameTime)
Position += Direction * 9f * Speed * (float)gameTime.ElapsedGameTime.TotalSeconds;

```

actually it's working perfectly, however, they're too fast so I can't check their collision each frame and I need to re-play their way each frame. How would I do it? And how would I do this available for both server (which doesn't use XNA as I want to port it to Linux later) and client (using XNA)?

Here's an image which shows the problem (1. bullet is before target 2. bullet is behind target, so it can no longer intersect the target. My goal is to calculate whether it intersected the target before)

I have almost forgot to mention! These objects are moving, these are player, that means that user can get out of the bullet's trace

# Answer
> 3 votes
The simplest way to solve this problem is to use fixed time steps in XNA and tell it you want more fps for your update method, this makes your update code run more often and with smaller time steps which in turn means that your bullet will travel a shorter distance each time you check for collisions. This is essentially what Nick mentioned above, but with less changes needed to your code.

In the constructor for your Game class put the following two lines of code:

```
base.IsFixedTimeStep = true;
base.TargetElapsedTime = new TimeSpan((long)(TimeSpan.TicksPerSecond / 600f));

```

600f Is the number of frames per second you want, most likely your already running with fixed time step (this is the default in XNA) at 60fps, by changing it to 600 your bullets will be checked 10 times more often.

Once you understood how this works in practice however I would recommend that you do this manually by dividing the ElapsedGameTime you receive in your update with the speed of your bullet and then update the bullet multiple times per update, this way you don't force your entire game to run at higher frames per second just to accommodate your bullets moving fast. Hope this helps.

---

PS. Swept objects is an interesting solution to this problem, while probably overkill for your scenario, it involves sweeping the object (the bullet) along its movement vector and then comparing this new shape to the other objects for collision. Sweeping a circle would give you a capsule for instance. You would normally do this with the bounding boxes of the sprites since its easier to calculate, but using algorithms like GJK you can do it with arbitrary shapes as well (in both 2D and 3D).

# Answer
> 8 votes
There are two methods of collision detection.

---

**Discrete stepping**

Use basic calculus to step an object A through space by some (typically fixed) distance per step. At each step, check object A for colocation with other objects B in the same space.

**Pros**: Cheap to process.

**Cons**: Can miss objects through *penetration*, which occurs because your physics timestep (need not necessarily be your gameloop timestep!) is not small enough to catch those cases where a bullet would have hit another object. Either (a) reduce your timestep to a smaller value and iterate your physics more frequently, or (b) reduce and cap maximum velocities, or (c) opt for CCD, below.

---

**Continuous Collision Detection (CCD) AKA raycasting**

This uses linear algebra to determine whether a line (or lines) representing body A's trajectory, is intersected by another line representing the boundary of some other solid body B. .

**Pros**: 100% accurate.

**Cons**: Costly to process, as you have to check the line against everything within your scene, or at least your area of interest (AoI) near to the player.

---

A number of physics engines allow a choice between these, for given types of bodies. For instance, while it may be prudent to use CCD for very fast moving, small objects like bullets, it may be perfectly acceptable to use stepping for other objects, since the timestep is small enough, and they are large and slow-moving enough, that there is no way they could overshoot/penetrate.

# Answer
> 4 votes
If the bullet is moving very fast then I believe that you would use **raycasting** (at least that is what I think it is usually called) in order to determine collision. In this example you would have the *old* position, you would calculate the *new* position. Then you would represent this movement by a line/ray between these two positions. If this line intersects with any geometry in your scene, then the bullet has hit something.

While I am not familiar with XNA, I would be surprised if it doesn't have built-in support for performing raycasting checks.

Some links that may be useful:

http://www.synapsegaming.com/forums/p/825/3684.aspx

http://www.youtube.com/watch?v=o9E1AhpcXWg

---
Tags: xna, c#, bullet-physics
---