# Question
Title: How do I set the mouse to control views like zoom in and out?
How would I go about using the mouse to zoom in and out of my current isometric tiled map, where the tiles need to be in the center of the view when the application has started?

This is what I have, so far:

# Answer
I would suggest you start with some tutorials on setting up the model-view and projection matrices in OpenGL. You'll find plenty of these on Google, as I did. Once you have this down, you may find it convenient to create a Camera class to handle this logic.

From there, you'll handle the mouse input (scroll wheel?) and use it to tell your camera to zoom in and out. Zoom probably means moving (translating) your camera "in" and "out" of the scene, but it could also mean scale or even messing with field of view.
> 1 votes

---
Tags: java, isometric
---


title: How do walls affect lighting?

text:
# Question
Title: How do walls affect lighting?
I have been trying to implement a simple form of lighting in my 2D game. In the screenshot, I don't think it looks very good, kind of just plastered over the top of the map. How would the wall effect how the lighting is displayed?

Just looking for tips on how to make my lighting look a bit better. Right now I gave each tile a light value and I change that depending on if there is a light source near by. I don't take in account if there are any objects near by.

Screenshot:

# Answer
Based on your sample image, I would say that you have to imagine the wall stopping the light. So on the tile for the wall, it would be lit, but past it (moving away from the light source) the light would not continue. In your example, the top tile of the emitted light (2 squares up from the source) would be dark but the wall tiles would stay the same.

Now, that said, if you have different layers, you may want light from a higher layer to transfer down a wall to a lower layer. But that depends on what you want and what looks good.

*Edit*
I guess the idea is, imagine yourself in that room, with that light source. What would happen when the light hit the wall? It would stop at the wall, right? Also, if you want to go wider with the emitted light, try and imagine the shadow it would cast as it passed the right and left edges of the wall. It would go off on an angle from there so maybe on the tiles that it crosses, you'd have partially lit tiles there.

Something you may also want to consider, if you haven't already, is that if emitted light overlaps, you may want it to get brighter. In that case, you'd want the light effect to be additive (i.e. the "light value" for a tile from one light source is ADDed to the "light value" on the same tile from the other light sources).
> 4 votes

# Answer
I quite realize that are asking *how* walls effect 2d lighting, and not *what can I use* to do simulate the effect, but I must insert my shameless plug here.

Another developer and I have created a very fast 2d lighting engine in XNA, using similar techniques to Orangy Tang (back in the day from GameDev.net) and Catalina Zima. The Codeplex site has links to these articles, explaining how to do 2D lighting with vector based graphics. You can find the source, binaries, and the links to the articles at krypton.codeplex.com
> 1 votes

---
Tags: xna, 2d, lighting
---


title: Collision filtering techniques

text:
# Question
Title: Collision filtering techniques
**I was wondering what efficient techniques are out there for mapping collision filtering between various bodies, sub-bodies, and so forth.**
I'm working on a physics engine and I need ways for a user to easily specify some complex relationships between bodies (what should/shouldn't collide), and ways to organize that filtering data so that it's easily attainable / memory-efficient. One part of my engine that could also be taken advantage is what my 'bodies' actually are. They're like folders that you can put convex shapes, and other bodies in as to organize the parts of a complex rigid body.

I'm familiar with the simple idea of having different layers of 2D bodies, but this is not sufficient for more complex mapping:

**EXAMPLE:**
*(Think of having sub-bodies of a body, such as limbs, collide with each other by placing them on the same layer, and then wanting to only have the limbs collide with the ground but not the body)*
\- I don't see how a user could accomplish the above example with just a bunch of different layers... The body must collide with the ground and therefore be in the same layer, but the limbs must also be in the same layer as the ground, causing unwanted collision between the body and the limbs.

This can be solved with a multidimensional layer setup, but I would probably end up just creating more and more layers to the point where the simplicity and efficiency of layer filtering would be gone.

**Are there any more complex filtering techniques that would solve complex situations such as the example? And even more possibly complex situations?**

# Answer
First you'll want to do some sort of spatial partitioning like a grid or quad tree. After that you should do like bummzack said and use bitwise operations. Assuming you are already doing spatial partitioning this is how I'd recommend going about filtering.

**Step 1**

Create an enumeration of collision categories. We will call this `Category`. This will be (up to) 32 named constants of type integer. Each of these values needs to be a power of two (e.g., 0, 1, 2, 4, 8 and so on). Assign the name `None` to `0`, you can give the rest whatever names suit your needs. Using your example `Legs` could be `1`, `Arms` `2` and `Ground` `4`. Aside from `None` the names are completely arbitrary.

**Step 2**

Any body that can collide with another body now needs two properties. If you have some sort of base `Entity` class that would be the place to add these.

1. collidesWith
2. collisionCategories

Both of these properties will be populated with values from `Category`. `collidesWith` indicates the categories the current body will collide with. `collisionCategories` is the list of categories the current body belongs to. You can assign multiple categories using bitwise operations. Again, using your example:

```
// Arms collide with other arms and legs
// See [http://en.wikipedia.org/wiki/Bitwise_operation#OR][2]
// for more in-depth discussion
arm.collidesWith = Category.Arms | Category.Legs;
arm.collisionCategories = Category.Arms;

// Legs collide with arms, other legs and the ground
leg.collidesWith = Category.Arms | Category.Legs | Category.Ground;
leg.collisionCategories = Category.Leg;

// The ground collides with nothing since we won't
// be directly testing it
ground.collidesWith = Category.None;
ground.collisionCategories = Category.Ground;

```

**Step 3**

This is where we do the actual filtering. In your collision handling code you will, at some point, be looping over a list of bodies that are colliding or potentially colliding with the current body. This is where you apply the bitwise filter. It works like this:

```
if ((other.collisionCategories & this.collidesWith) != Category.None)
{
    // Bodies are colliding
    // Do collision code
}
else
{
    // Bodies are not colliding
    // Filtered
}

```

The above is asking, "Does this other object belong to any of the categories my body collides with?" The Wikipedia article on bitwise AND will explain this with more detail.

---

The benefits of this approach are that bitwise operations are really, really fast and we can pack a lot of information into a small bit of memory. It's also very flexible.

The downside is that it's not the most straightforward, easy to grasp approach (but it's not really all that hard either). You could also run into problems if you require more than 32 collision categories but that seems unlikely.
> 2 votes

# Answer
You could use Octrees

http://en.wikipedia.org/wiki/Octree

Have each layer as a different depth into the screen in the octree.
> 1 votes

# Answer
Back in the day, I started using Box2D before they had any kind of collision culling. Used to be (on core 2 duo 2.4Ghz), I could have a maximum of 50 colliding boxes before the simulation started lagging severely due to the lack of culling.

I modified the Box2D source to include axis aligned bounding boxes, which allowed me to get round-abouts 500 colliding boxes before it started lagging, and went on to add a Quad Tree (seeing as how this is 2D, and not 3D, octrees are pointless). After the Quad Tree implementation, I was able to get about 1000 colliding boxes before is started lagging. Keep in mind, these boxes were all sitting on top of each other, actively colliding and applying forces upon one another, slowly stabilizing.

I think I also added some logic to prevent sleeping boxes to from colliding with other boxes... therefore only active (moving) boxes could collide with non-moving boxes. This way, sleeping boxes wouldn't get tested against other sleeping boxes (if neither of them are moving, then how can they collide?).

Since then, Box2D has implemented all of those features... Sadly, I never submitted those changes, so I can't claim anything for that.

All in all, it was a pretty educational experience.

TLDR;

* Cull body-body collisions based on range or axis aligned bounding boxes.
* Cull body-body collisions if both are sleeping.
* Cull large counts of bodies by implementing a quad tree.
> 1 votes

---
Tags: 2d, collision-detection, physics, filtering
---


title: Setting up CCMenu for Cocos2d

text:
# Question
Title: Setting up CCMenu for Cocos2d
I am very new to Cocos2d programming and was thinking to build up my first app. I learnt some basics related to CCMenu and CCMenuItems. But I was wondering whether I could provide animations in such a way that every CCMenuItem would animate first and then appear in the CCMenu. Will that be possible in Cocos2d? Can I get some tutorials or samples regarding this?

Thanks.

# Answer
> 1 votes
AFAIK there are two ways to implement that, the first one which is easier is to create an Object, then using CCAnimate and CCSequence classes, first animate an image and then convert it into an image.

the harder way which will result in cleaner code (I suggest this one) is to create a class which inherits normal CCMenuItems class. and change it's constructor to start an Animation instead of immediately being clickable.

---
Tags: game-design, cocos2d-iphone
---


# Question
Title: Handling player/background movements in 2D games
Suppose you have your animated character controlled by the player and a 2D world (like the old 2D side-scrolling games). When the user presses right on the keyboard, the background is moved to the right. If the path is always horizontal, this is simple to do (incrementation/decrementation of the x-coordinate).

But suppose that the path is instead a polygonal chain. My questions are:

1. How do you move the background?
2. How do you move the background if the game objects are managed with a physics engine like box2D?

Note.

What I wanted to ask is, how do you move a 2D character in a side-scroller? For example, consider the following path:

```
A---------B     C'--------D'
           \
            \C__________D

```

You start from A, move horizontally to B, then move diagonally to C, then move horizontally to D OR, from B, jump on C' and continue till D' and so on.

# Answer
> 5 votes
You're thinking about this the wrong way. You're thinking in terms of characters, background, etc. You need to be thinking in terms of a *world*, which can be viewed from *any* location. Or at least, a world that has a bounded area from which it can be viewed.

You should be able to position your camera in any arbitrary location you wish, within restrictions (like world boundaries). Your camera is what determines the offset for the "background".

For example, let's say your world starts at (0, 0). And it advanced to the right by 400 units, and up by 200 units. That's the boundary of your world. Now let's say that your camera can show a 20x15 rectangle of this world.

All entities have a position in the world. For example, maybe the player starts out at location (10, 5) (remember; positive X goes right, and positive Y goes *up* in this example). That's the player's world-space location.

When you *render* the player, you don't render them in world-space. You transform the player's position into screen-relative coordinates. To do that, you must define a *camera*, which represents a particular view of the world.

Let's say we want to center our camera (which is 20x15 in size) on the player's position, as much as possible within the boundaries of world space.

So the bottom-left position of the camera, given a player at (10, 5), would be the camera at (0, -2.5). That is half the camera width/height subtracted from the player's position. But since that is outside of the world, we clamp the Y value to 0. So the bottom-left of the camera is (0, 0).

Now, let's say the player moves to location (30, 20). Well, the bottom-left of the camera should be (20, 12.5). That's still within the world, so there's no need to clamp.

All of those camera positions we computed? Those are used to transform entities from world-relative coordinates to *screen* relative coordinates. This is done by simple subtraction.

If your camera is at (20, 12.5), and there's an entity somewhere that is at (30, 16), then the actual position of that entity on the *screen* is the entity's position minus the camera's position: (10, 3.5). *This* is the location you render him at (again, assuming bottom-left orientation. Most 2D renderers try to use top-left. The math is ultimately the same either way though).

So there needs to be a separation between "where the character actually is" and "where the character gets rendered on the screen".

---
Tags: box2d, movement, side-scroller
---


# Question
Title: Best way to solve tile drawing in 2D side scroller?
What i still can't figure out is which would be the more sane way / easier and faster way to draw the map on the screen.. I mean i will use many tiles for my maps in my side scroller.. But problem is should i make the maps in whole images like one .png file for each map (Example) or should i draw the tiles by code like a for loop in c++.. Which way is most recomended or where can i read about which way is the best.

# Answer
> 5 votes
I would never recommend having one large image. One large image will make changing and creating levels very tedious.

In my tile engine, I draw all the tiles to a separate screensized render target, and reuse that render target as the player moves around in the world, only drawing tiles as they enter the screen. This all happens in the background. I then use the render target as the background, and then draw the entities on top. This is what I believe one of the most efficient ways of drawing a tilebased world.

# Answer
> 2 votes
Tiles have the benefit of being stored in less memory, taking advantage of re-using the same graphics for all the areas in the map that need them. I will describe why it's not a good idea to use large images.

Drawing large images in place of tiles is inefficient also for the workflow. You'll have to recreate an new image from scratch every time a change in the map design is needed, and plus you'll have an arbitrarily large amount of images for any maps, they will barely be reusable.

Another caveat is managing collision detection- I mean, it's going to be more than a pretty backdrop in that you will want to interact with it. Handling collisions is much easier on a tile-based level since tiles can contain collision logic or vice versa, and their collision boxes are "locked in" with the tile area itself. With large static images, there will be a tendency to lose the spatial connection between the visuals and collidable areas, and you'll have to take extra care in not letting collision boxes become misaligned with the visuals. This will just lead to more unpredictable, buggy results.

Even in 2D games where the level design looks very "freeform" (see Aquaria) there is usually still a copy-paste philosophy behind it. The editors may not use tiles that snap to specific areas, but you're still using reusable bits and pieces for making maps and levels that can be scaled, moved and rotated which may take some interactive properties along, collision boxes being among them.

---
Tags: maps, tilemap
---


# Question
Title: Why can I not map a dynamic texture in D3D?
I am trying to map a Texture2D resource in DirectX11 via SharpDX.

The resource is declared as a ShaderResource, with Dynamic usage and the 'Write' CPU flag specified.

My call however fails with a generic exception from SharpDX:

```
_Parent.Context.MapSubresource(
  _Resource,
  0,
  SharpDX.Direct3D11.MapMode.Write,
  SharpDX.Direct3D11.MapFlags.None,
  out stream
);

```

I see from this question that it is supported. The MSDN docs and this other question hint that instead of using `Context.MapSubresource()` I should be using `Texture2D.Map()`, however, the DirectX11 Texture2D class does not define `Map()` (though it does for the D3D 10 equivalent).

If I call the above with `MapMode.WriteDiscard`, the call succeeds but in this case the previous content of the texture is lost, which is no good when I only want to update a section of it.

Has the `Map()` method been removed in Direct3D 11 or am I looking in the wrong place? Is the `MapSubresource()` method unsuitable or am I using it wrong?

**EDIT:** I declared my resource as Dynamic with CPU Write Flags - not Default as I originaly wrote - sorry for the fairly huge 'typo' that changes the entire question!

# Answer
The main reason Direct3D10 Map methods were moved to Direct3D11 DeviceContext is to support multithreading. They were previously attached to each resource (thus implicitly, a single device), but with Direct3D11, It is now possible to update the same resource from different deffered context.

Concerning your issue with MapSubresource, you need to check this documentation on Resource Usage.

You will see that it is not possible to use Map method with Usage.Default, as it is only working with dynamic texture. Usage.Default is suitable if you are only using UpdateSubresource. The correct way to use Map is to declare the texture with Usage.Dynamic and Map with WriteDiscard. It is not possible to keep the content of the dynamic texture (update partially) as a race condition between the GPU and CPU would arise.
> 5 votes

---
Tags: directx11, sharpdx
---


# Question
Title: Why is a fully transparent pixel still rendered?
I am trying to make a pixel shader that achieves an effect similar to this video http://www.youtube.com/watch?v=f1uZvurrhig&feature=related

My basic idea is render the scene to a temp render target then Render the previously rendered image with a slight fade on to another temp render target Draw the current scene on top of that Draw the results on to a render target that persists between draws Draw the results on to the screen

But I am having problems with the fading portion. If I have my pixel shader return a color with its A component set to 0, shouldn't that basically amount to drawing nothing? (Assuming that sprite batch blend mode is set to AlphaBlend)

To test this I have my pixel shader return a transparent red color. Instead of nothing being drawn, it draws a partially transparent red box.

I hope that my question makes sense, but if it doesnt please ask me to clarify

Here is the drawing code

```
    public override void Draw(GameTime gameTime)
    {
        GraphicsDevice.SamplerStates[1] = SamplerState.PointWrap;

        drawImageOnClearedRenderTarget(presentationTarget, tempRenderTarget, fadeEffect);
        drawImageOnRenderTarget(sceneRenderTarget, tempRenderTarget);
        drawImageOnClearedRenderTarget(tempRenderTarget, presentationTarget);

        GraphicsDevice.SetRenderTarget(null);

        drawImage(backgroundTexture);
        drawImage(presentationTarget);

        base.Draw(gameTime);
    }

    private void drawImage(Texture2D image, Effect effect = null)
    {
        spriteBatch.Begin(0, BlendState.AlphaBlend, SamplerState.PointWrap, null, null, effect);
        spriteBatch.Draw(image, new Rectangle(0, 0, width, height), Color.White);
        spriteBatch.End();
    }

    private void drawImageOnRenderTarget(Texture2D image, RenderTarget2D target, Effect effect = null)
    {
        GraphicsDevice.SetRenderTarget(target);
        drawImage(image, effect);
    }

    private void drawImageOnClearedRenderTarget(Texture2D image, RenderTarget2D target, Effect effect = null)
    {
        GraphicsDevice.SetRenderTarget(target);
        GraphicsDevice.Clear(Color.Transparent);
        drawImage(image, effect);
    }

```

Here is the fade pixel shader

```
sampler TextureSampler : register(s0);

float4 PixelShaderFunction(float2 texCoord : TEXCOORD0) : COLOR0
{
    float4 c = 0;
    c = tex2D(TextureSampler, texCoord);
    //c.a = clamp(c.a - 0.05, 0, 1);
    c.r = 1;
    c.g = 0;
    c.b = 0;
    c.a = 0;
    return c;
}

technique Fade
{
    pass Pass1
    {
        PixelShader = compile ps_2_0 PixelShaderFunction();
    }
}

```

# Answer
> 6 votes
BlendState.AlphaBlend uses premultiplied blending so check out this for why you can a value of 0 for alpha and still have the pixel not be transparent (especially the last paragraph).

So I believe what you need is in your shader is (I'm bad with shaders so take this with a grain of salt).

```
c.a = clamp(c.a - 0.05, 0, 1);
c.r = c.r * c.a;
c.g = c.g * c.a;
c.b = c.b * c.a;

```

---
Tags: xna-4.0, hlsl, fragment-shader
---


# Question
Title: Scaling and new coordinates based off screen resolution
I'm trying to deal with different resolutions on Android devices.

Say I have a sprite at X,Y and dimensions W,H.

I understand how to properly scale the width and heigh dimensions depending on the screen size, but I am not sure how to properly reposition this sprite so that it exists in the same area that it should.

If I simply resize the width and heigh and keep X,Y at the same coordinates, things don't scale well.

How do I properly reposition? Multiply the coordinates by the scale as well?

# Answer
You are looking for something along the lines of Resolution Independant Rendering. There is a similar question in that link, as well as a great article on the subject.

The article and question is using XNA, but the concept is sound. Essentially, you have a "Real" resolution and a "Virtual" resolution. The Real resolution is the one you are working with to create your game. You pick it once, and don't change it. Your Virtual resolution is your "final" resolution. It's the one you need to scale to achieve the "perfect fit". You can either have your device scale it (by stretching, which may look ugly) or add letterboxing and/or pillarboxing to adjust to the new resolution without stretching.

---

Alternatively, you need to figure out an offset base on your size. Something like "if I increase the scale by 20, I need to move it 10 pixels to the left, and 10 pixels down". That version involves a bit more trial and error, but it may work better, depending on your game.

I'm not sure if there is a concrete equation out there for "if you increase by this, move by this". I've only done something that way once, and it involved me working with the numbers and offsets until I got something that worked.

(For the record, my magic numbers were "if I decrease width by 10, I increase position by 5. The opposite for increasing width. Works with both height and width.)

---

Further, you may want to check out Adaptive Resolution or this question regarding how to develop for different resolution on the Android platform.
> 4 votes

---
Tags: android, coordinates, resolution
---


# Question
Title: How can I factor momentum into my space sim?
I am trying my hand at creating a simple 2d physics engine right now, and I'm running into some problems figuring out how to incorporate momentum into movement of a spaceship.

If I am moving in a given direction at a certain velocity, I am able to currently update the position of my ship easily (Position += Direction * Velocity). However, if the ship rotates at all, and I recalculate the direction (based on the new angle the ship is facing), and accelerate in that direction, how can I take momentum into account to alter the "line" that the ship travels? Currently the ship changes direction instantaneously and continues at its current velocity in that new direction when I press the thrust button. I want it to be a more gradual turning motion so as to give the impression that the ship itself has some mass.

If there is already a nice post on this topic I apologize, but nothing came up in my searches. Let me know if any more information is needed, but I'm hoping someone can easily tell me how I can throw mass * velocity into my game loop update.

# Answer
It looks like you have Position and Direction as vectors and Velocity as a scalar?

If so just change Velocity into a vector as well and then do something like this:

```
Force = Direction * Power
Acceleration = Force / Mass
Velocity += Acceleration * ElapsedTime
Position += Velocity * ElapsedTime

```

Direction being a unit length vector giving the heading of your ship. Power being the amount of thrust you want to add (Zero when no acceleration is needed) ElapsedTime is the time between your game Update calls to keep movement smooth even when your framerate is changing

If you want to know more about it you can look up Euler Integration
> 7 votes

# Answer
Instead of manipulating the *velocity* directly, add another variable: *acceleration*, that gradually, smoothly alters the *velocity*:

**From classical physics (Newton's laws of motion):**

```
a =  F/m  // a Force will result in a smaller acceleration on objects with more mass
v += a    // acceleration is the rate of change in velocity
p += v    // velocity is the rate of change in position

```

where:

```
a = acceleration, v = velocity, p = position
F = force, m = mass

```

*(Note m is the only scalar value; F, a, v, and p are all 2D or 3D vectors)*

**Also, there are actually two directions:**

1. The direction the ship is facing. Force from engines is applied along this vector.
2. The direction the ship is actually moving (due to momentum). This is the velocity vector v.

I answered a related question on StackOverflow: 2D Spaceship movement math. There is some sample code in that answer.
> 8 votes

---
Tags: xna, 2d, physics
---


title: Need help for weapon models for Unity

text:
# Question
Title: Need help for weapon models for Unity
I've been working on this FPS game and I've gotten to the point where I need to start adding the weapons in and have been having trouble creating (unsure of what engine to use) them. Is there an easier way to create models for unity 3D?

# Answer
I created a basic FPS a while ago and got to the point of creating weapon models too. What you will want to do is to create a 'world model' which is the model actually seen on the character in the game, and a 'view model' which is a high detail model that only the player sees.

These Viewmodels should be aligned to the camera during creation, so you know exactly what you want to look at when holding the weapon (this also allows you to omit details from some sections of the model, like the back/hand area).

The Valve dev wiki helped me alot when I was working on my game (See their section on networking too, if you intend to try multiplayer sometime) https://developer.valvesoftware.com/wiki/Viewmodel

As for creating the models themselves, I use Blender, which is really the best 3D modelling (and animating and a whole lot of other things) package out there for us hobbyist/indie game devs. This is one of my favorite sites for blender tutorials: http://cgcookie.com/

When creating the viewmodel in blender, create a camera in blender that is identical to the camera used in Unity - Set the FOV angle on both to be the same (and perspective on both too, I assume), position it somewhere convenient (eg 0,0,0), and keep looking at your viewmodel through the camera (by pressing 0 on the numpad) while keeping track of the exact offset of the viewmodel from the camera. Then when you are ready to import it into Unity, make sure you give it the same offset from the camera.

Sorry if that was a bit elaborate, but its something that I would have loved to have been told back when I was starting out on the FPS. :)

Good Luck!
> 9 votes

---
Tags: unity, models, first-person-shooter
---


# Question
Title: How can we view 3d objects from top down view in TD game
I am making a tower defense game. I am working in x and y axis only. I have made a grid, snapped towers and made a pathfinding algo to run enemy. Initially I have worked with cubes and spheres in place of towers and enemies.

Now I am going to place real towers (3D). Note that I haven't used z axis up till now. The user will analyze the game from top down view.

I want the user to see towers placement with a little bit of 3d view but I have made my all code in 2d thing. Is there any solution to my problem that somewhat tower placement would view a 3D touch or you can say 2.5D ?? (like fieldrunners) or should I have to involve z axis and ignoring y axis ?

# Answer
There shouldn't be anything about your code that needs to change. All you would really need to do is change the representation of your game. I'm guessing from the tag that you're using Unity?

Just throw a camera in there, play around with FOV (or make it ortho), and as you place models in the game they'll just look right. There's no reason for your TD code itself to care about the z axis.
> 1 votes

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


# Question
Title: State Changes in a Component Based Architecture
I'm currently working on a game and using the naive component based architecture thingie (Entities are a bag of components, entity.Update() calls Update on each updateable component), while the addition of new features is really simple, it makes a few things really difficult: a) multithreading / currency b) networking c) unit testing.

* Multithreading / Concurrency is difficult because I basically have to do poor mans concurrency (running the entity updates in separate threads while locking only stuff that crashes (like lists) and ignoring the staleness of read state (some states are already updated, others aren't))
* Networking: There are no explicit state changes that I could efficiently push over the net.
* Unit testing: All updates may or may not conflict, so automated testing is at least awkward.

I was thinking about these issues a bit and would like your input on these changes / idea:

1. Switch from the naive cba to a cba with sub systems that work on lists of components
2. Make all state changes explicit
3. Combine 1 and 2 :p

Example world update:

```
statePostProcessing.Wait() // ensure that post processing has finished
Apply(postProcessedState)

state = new StateBag()

Concurrently(
 () => LifeCycleSubSystem.Update(state), // populates the state bag
 () => MovementSubSystem.Update(state), // populates the state bag
  ....
})

statePostProcessing = Future(() => PostProcess(state))
statePostProcessing.Start()
// Tick is finished, the post processing happens in the background

```

So basically the changes are (consistently) based on the data for the last tick; the post processing can a) generate network packages and b) fix conflicts / remove useless changes (example: entity has been destroyed -\> ignore movement etc.).

EDIT: To clarify the granularity of the state changes: If I save these post processed state bags and apply them to an empty world, I see exactly what has happened in the game these state bags originated from -\> "Free" replay capability.

EDIT2: I guess I should have used the term Event instead of State Change and point out that I kind of want to use the Event Sourcing pattern

# Answer
May this stackoverflow question helps you: https://stackoverflow.com/questions/1901251/component-based-game-engine-design

It contains a lot of interesting literature.

To your question about networking: One approach could be that you introduce a message/event system instead of/in addition to calling the update method.

You can easily transmit the messages/events over the network. The receiving client/server can interpret the message and do what it should do (depending on the type of message). In most cases this is just receiving the message and forwarding it to an actual component which knows what to do when it receives the message.

About sending the state changes: I prefer sending the new position instead of the changes. In a 2D world this means in both cases you are sending an int/double for x and y but with the benefit that loosing one message in the network does not mean that the position isn't correct any more. And you don't have to calculate the new position on each client.
> 3 votes

# Answer
I would suggest using your first option (sub-system) with state change requests from components to the sub-system.

Regarding the order of update, I think this is more of a data structure problem. You should first define the dependencies between objects (or sub-systems) and group independent objects together (that can be easily updated in parallel). This concept is very well explained in this article http://slidesha.re/u6xR10 (long but totally worth it!)

Also have a look at this selection of presentations especially the Data Oriented Design ones.

I hope that helps :)

Cheers
> 3 votes

# Answer
> Multithreading / Concurrency is difficult because I basically have to do poor mans concurrency (running the entity updates in separate threads while locking only stuff that crashes (like lists) and ignoring the staleness of read state (some states are already updated, others aren't))

If that is *'poor man's concurrency'*, what do you consider 'rich man's concurrency' to be?

Thread safety is about more than stopping things from crashing, anyway. I expect you're doing something unsafe here.

> Networking: There are no explicit state changes that I could efficiently push over the net.

What kind of state change are you interested in? I don't see how the components make any difference to what you need to send over the network. If your problem is that you don't have 1 standard place to send updates from, then make a standard place, eg. a Networking component, and push updates into it.

> Unit testing: All updates may or may not conflict, so automated testing is at least awkward.

Again, I don't see what the problem is. Test the components in isolation, and if there are issues with interaction, test those too.
> 0 votes

---
Tags: architecture, component-based, multithreading
---


# Question
Title: What features does D3D have that OpenGL does not (and vice versa)?
Are there any feature comparisons on Direct3D 11 and the newest OpenGL versions?

Well, simply put, Direct3D 11 introduced three main features (taken from Wikipedia):

* Tessellation
* Multithreaded rendering
* Compute shaders
* Increased texture cache

Now I'm wondering, how does the newest versions of OpenGL cope with these features? And since I have this feeling that there are features that Direct3D lacks from OpenGL's side, what are those?

# Answer
> 14 votes
When one talks about OpenGL and D3D "features," one could be referring to either:

1. the feature sets supported by hardware that the graphics API exposes, or
2. the feature sets of the API itself that don't really relate to the hardware.

For example, a programmable tessellation pipeline is something the hardware generally has to support (let's ignore, for the purposes of practicality, that an API could in theory implement missing hardware features in software as that's generally too slow to be of real use). Presupposing it does, you can gain access to that pipeline in both D3D and OpenGL. D3D builds the interfaces for doing so into the core API of D3D11 via the hull/domain shaders and tessellation APIs. OpenGL provided an extension that was eventually promoted to part of the core API. When it comes to hardware features, OpenGL and Direct3D are generally equivalent in terms of what you can make the hardware do via either API. The differences come in how.

There are hundreds of small API features (unrelated to actual hardware capability) that differ in both APIs. It's not practical to list them all in an answer. Aside from the fact that D3D is a "traditionally COM-like" API and OpenGL is a "traditionally C-like" API, one of the biggest differences in the feature set is that OpenGL has its rich extension mechanism (and D3D has no such thing). This tends to mean that OpenGL is in theory more flexible and adaptable to new capabilities, at the cost of being slightly more cumbersome to use (thus the plethora of OpenGL extension assistance APIs like GLEW).

# Answer
> 7 votes
Taken from Wikipedia, too: there aren't many differences. Strictly speaking, OpenGL is usually slightly behind Direct3D in terms of features, because the standardisation takes time. However, many of these features are available as OpenGL vendor-specific extensions first, then in the standard itself after some time.

* Compute shaders are available in GLSL shader model 5.
* Tessellation is available in OpenGL 4.x (see a tutorial here).
* Multithreaded rendering is tricky in OpenGL, but certainly possible, and in all honesty I believe most of what D3D does is manage a big global lock and the interaction with the GPU is still single-threaded.
* I don't know exactly what's implied by "Increased texture cache" but I believe they just raised the lowest common denominator for that feature.

As for your last question, in my opinion, the features that Direct3D lacks the more are a Mac OS X version, a Linux version, an Android version, an iPad/iPhone version, and a PlayStation 3 version :-) (while the last three platforms actually support OpenGL ES rather than OpenGL, it makes porting software a lot easier than porting Direct3D to OpenGL ES)

# Answer
> 4 votes
The other answers (Sam and Josh) cover most of what you need to know, but just adding a few extra points.

Before that however, Josh's point about the API not offering features is worth repeating. It's quite incorrect to say things like "OpenGL has vertex buffers" or "D3D has shaders", and was just as incorrect back in the day when you used to read things like "D3D doesn't have a stencil buffer" or "OpenGL has polygon offset". Your gfx hardware has features and the API exposes them; if your gfx card doesn't have a feature no amount of exposition in the API will give you it (unless you use some form of software emulation, which you really don't want to do) and if your gfx card has a feature but the API doesn't support it then you can't use it either.

Moving on with the extra stuff.

D3D has more sensible management of multiple monitors/multiple gfx cards, which can't be underestimated with some end-users.

Explicit memory pools in D3D9 or below were nice (aside from the dreaded D3DERR\_DEVICELOST) and it's vertex buffer API is much cleaner and clearer and easier to use. Separation of layout specification from data specification was the right decision IMO. GL has improved with attrib arrays and VAOs but it's still not all the way there.

D3D also guarantees a single consistent shader compiler for all users and on all hardware, whereas each GL implementation has a different shader compiler. The Effects framework is also very nice.

D3D generally has better quality drivers than OpenGL. That's pretty critical.

OpenGL has extensions. That's something of a double-edged sword, as while you can get access to newer vendor-specific features earlier, you may end up with a mess of multiple codepaths all doing broadly the same thing. You make your own choice about which side of that tradeoff you're happier to accept.

OpenGL still has some nice things that D3D is missing. The accumulation buffer (on hardware that accelerates it) can do some neat things; D3D11.1 is apparrently finally going to get logic ops on the framebuffer.

glCopyTexSubImage is very nice in cases where it's implemented properly (which should be everywhere as Doom 3 used it) and D3D has no direct equivalent, to pull another specific example out.

OpenGL is capable of providing software fallback for things required by the spec but unsupported in hardware (not all things however) whereas D3D will normally give you a big ugly crash or error. Another tradeoff where you decide (although I still have nasty memories of a Geforce FX - which supported NP2 textures as required by the GL 2.0 spec - going back to full software emulation without warning if you actually tried to *use* one...)

OpenGL tends to maintain backwards compatibility through revisions of the API (I'm ignoring core contexts here) whereas D3D does not. There are arguments for and against each philosophy that it's probably not appropriate to retread here; just something to be aware of.

OpenGL still has bind-to-modify whereas D3D does not; you operate directly on the object (or pass it as a param) instead. The OpenGL way tends to mess up any state filtering you might be doing, IMO.

They're the main big ones I can think of right now; nothing too earth-shattering but enough to tip a decision.

Finally, it's also incorrect to state that Android, mobile devices, the PS3, etc use OpenGL, because they actually don't. They use GL ES which is in some ways a subset of full OpenGL and in other ways quite different (and on the PS3 anyone concerned about performance uses libgcm anyway).

---
Tags: opengl, graphics, directx11
---


# Question
Title: Need some help implementing VBO's with Frustum Culling
i'm currently developing my first 3D game for a school project, the game world is completely inspired by minecraft (world completely made out of cubes). I'm currently seeking to improve the performance trying to implement vertex buffer objects but i'm stuck, i already have this methods implemented: Frustum culling, only drawing exposed faces and distance culling but i have the following doubts:

1. I currently have about 2^24 cubes in my world, divided in 1024 chunks of 16\*16\*64 cubes, right now i'm doing immediate mode rendering, which works well with frustum culling, if i implement one VBO per chunk, do i have to update that VBO each time i move the camera (to update the frustum)? is there a performance hit with this?
2. Can i dynamically change the size of each VBO? of do i have to make each one the biggest possible size (the chunk completely filled with objects)?.
3. Would i have to keep each visited chunk in memory or could i efficiently remove that VBO and recreated it when needed?.

# Answer
1. Do you currently modify your cubes on the CPU in order to do frustum culling? When you move the camera? If not (and I'm guessing not), then there's no need to do it for the GPU as well. If so... then you should probably stop doing that.

Unless the positions within a given mesh are actually moving relative to one another, they should not be *changing*. They should be static. You should be transforming those cube chunks into different positions using matrices through OpenGL. The vertex positions you pass, whether in immediate mode or with buffer objects, should not be changing.

Frustum culling should not be done against the actual cubes, but against the bounding volume of each chunk. That's what you should transform to do frustum culling.
2. Yes you can, but I would *strongly* advise against it. See below.
3. You can do whatever you want. But you *shouldn't* be deleting the actual buffer objects. Instead, you should be swapping data into and out of them. Allocate however much active buffer space you need initially, then upload different data into them as needed. More information on streaming to buffer objects exists.
> 0 votes

---
Tags: opengl, java, minecraft-modding, lwjgl, vbo
---


# Question
Title: How to achieve hologram projection effect with head tracking
I want to recreate this: http://www.youtube.com/watch?v=9xMSGmjOZIg&feature=related

I can take care of tracking the user's head, and in one of the comments I believe the author says that he used a vertex shader to do the work, but what logic do you use to move the vertices to get this effect?

# Answer
To implement this effect, there are a few things you need to know:

1. The exact physical measurements of the display surface.
2. The viewer's eye location, relative to the centre of the screen.

Once you have this information, it's relatively simple to get the effect. Instead of calculating a normal projection matrix (typically by taking the camera position, vertical field of view, aspect ratio, and near and far clip distances), you instead construct your own skewed projection matrix using explicit frustum planes.

To generate these explicit frustum planes, you use the centre of the screen as your "zero" position, and define each frustum plane by the viewer's eye location (relative to the zero position) and two of the corners of the screen (also relative to the zero position). Near and far clip planes may either be parallel to the screen (which is a little easier mathematically) or perpendicular to the eye-\>zero vector.

I seem to recall reading that D3D has an explicit API for creating skewed projection matrices, while you need to do the math yourself in OpenGL. Either way, there's plenty of sample code for constructing skewed projection matrices from arbitrary frustum planes in Google.

Once you have your skewed projection matrix, all the rest of your rendering happens normally, exactly as it does with a non-skewed projection matrix. Note: do *not* attempt to rotate or translate a "camera" object to mimic the viewer's motion; that's all handled explicitly by the skewed projection matrix. (If you wish the viewer to be able to navigate through the world to a greater extent than they can by moving physically, say by using a joystick, then you'll need to use a camera. Remember that any such camera motion/rotation would be relative to the physical screen, not relative to the viewer's perspective, so you'd need to do some extra maths if you wanted to make the camera move relative to the viewer's facing)

Anyhow, the net effect is that the game renders a carefully distorted view of the scene, precisely calculated to **not** appear distorted when viewed specifically from the viewer's eye position (and nowhere else).

A few notes on the video linked in the question. First, it looks like the effect being shown in the video has the helicopter placed slightly forward of the screen. Objects forward of the screen are always tricky to do well in this sort of system, as the view frustum is so narrow that it's so easy for them to wind up falling outside of the frustum when viewed from a sharp angle. For this reason, it's much more standard to place objects behind the screen, treating the screen as if it was a limited "window" into another 3D scene. If you're going to put objects in front of the screen (or intersecting the screen), then it's important to make these objects small relative to the size of the screen, and not to place them very far forward of the screen, or you risk users walking past them, or otherwise having difficulty finding them.

Also note that in this sort of rendering approach, the object will not appear to 'pop out'; it distinctly remains a 2D image on a flat screen. It's kind of disconcerting the first time you see something doing this in real life, rather than in a YouTube video; it's not at all what most people seem to have been expecting, despite intellectually knowing that the image is still just an image on a flat screen.

Finally, note that display lag is a serious issue with this sort of effect. Your whole architecture (viewer eye detection-\>rendering-\>display) needs to be as responsive as possible in an effort to minimise motion sickness among people using the system. This is a problem suffered by every VR-like system which tries to feed people images based upon their movements; many (but not all!) people simply can't cope with more than a few milliseconds of lag, and soon begin to feel nauseous. The longer the lag, the more people seem to be affected. So keep this in mind, too.
> 5 votes

# Answer
It looks to me like you just set the camera position to the user's head position, then run the vertex shader normally.

You'd probably need to feed it through a matrix to convert whatever coordinates Kinect uses into the world space of your scene, but that's about it.
> 1 votes

---
Tags: mathematics, animation, hlsl
---


title: A* navigational mesh path finding

text:
# Question
Title: A* navigational mesh path finding
So I've been making this top down 2D java game in this framework called Greenfoot and I've been working on the AI for the guys you are gonna fight. I want them to be able to move around the world realistically so I soon realized, amongst a couple of other things, I would need some kind of pathfinding.

I have made two A\* prototypes. One is grid based and then I made one that works with waypoints so now I need to work out a way to get from a 2d "map" of the obstacles/buildings to a graph of nodes that I can make a path from. The actual pathfinding seems fine, just my open and closed lists could use a more efficient data structure, but I'll get to that if and when I need to.

I intend to use a navigational mesh for all the reasons out lined in this post on ai-blog.net. However, the problem I have faced is that what A\* thinks is the shortest path from the polygon centres/edges is not necessarily the shortest path if you travel through any part of the node. To get a better idea you can see the question I asked on stackoverflow.

I got a good answer concerning a visibility graph. I have since purchased the book (Computational Geometry: Algorithms and Applications) and read further into the topic, however I am still in favour of a navigational mesh (See "Managing Complexity" from Amit’s Notes about Path-Finding). (As a side note, maybe I could possibly use Theta\* to convert multiple waypoints into one straight line if the first and last are not obscured. Or each time I move back check to the waypoint before last to see if I can go straight from that to this)

So basically what I want is a navigational mesh where once I have put it through a funnel algorithm (e.g. this one from Digesting Duck) I will get the true shortest path, rather than get one that is the shortest path following node to node only, but not the actual shortest given that you can go through some polygons and skip nodes/edges.

Oh and I also want to know how you suggest storing the information concerning the polygons. For the waypoint prototype example I made I just had each node as an object and stored a list of all the other nodes you could travel to from that node, I'm guessing that won't work with polygons? and how to I tell if a polygon is open/traversable or if it is a solid object? How do I store which nodes make up the polygon?

Finally, for the record: I do want to programme this by myself from scratch even though there are already other solutions available and I don't intend to be (re) using this code in anything other than this game so it does not matter that it will inevitably be poor quality.

# Answer
I would advise that even if you are going to write all your own code, that you download Recast and build the sample application as it has visualisations that show the generated navmesh and it allows you to test the path-finding with a simple point and click interface. You can learn a lot just by playing with that.

As you have already realised, there are two steps to producing a good looking path - the A\* path-finder and then the subsequent post-processing which includes path straightening (the elimination of any turns not necessary to avoid obstacles) and possibly also the adding of curves at the turning points.

## Path finding

You've got the A\* part mastered which is great. You have also made the observation that A\* will not always find the straightest path. It's crucial to understand that this is because A\* is an algorithm to find the shortest path through a graph (being a mathematical concept where nodes are dimensionless) when you apply it to a mesh, you have to map nodes to mesh elements somehow.

The most obvious thing to do is to navigate from polygon centre point to centre point and base the cost on this distance, but this has some problems. One is that it won't always find the geometrically shortest path and the second is that if you try and follow the path you've calculated there you'll notice that a straight line from one centre to the next can cross a polygon that isn't part of the path (and might not be navigable at all). It's not an awful way to cost the graph traversal while perform A\* but it's clearly not adequate for any traversal purpose.

The next simplest solution is to perform A\* from edge to edge through the mesh. You'll find this simpler to think about if you imagine that instead of one node per polygon, you have one per-edge per-polygon. So your path goes from your start point to just inside the nearest edge, crosses to just inside the edge of the adjacent polygon and then to just inside the next edge in that same polygon and so on. This produces the shortest path more often and also has the benefit of being traversable if you don't want to perform a path straightening step.

## Path straightening

The algorithm used in Detour (the navigation library that accompanies Recast) is pretty simple. You should observe that it will only straighten the path within the bounds of the polygons found during the A\* search. As such, if that doesn't not find the tightest path around an obstacle, you will not get a tight path after running that algorithm either. In practice the navmeshes produced by recast tend to have a single polygon that you can pass through when navigating a choke point (the closest point between two obstacles) and so A\* will always produce a list of nodes that are as close to the obstacle as possible. If you are using tiles as the navmesh, this won't be the case and this very simple algorithm will insert spurious turns.

Detour's path straightening algorithm isn't quite O(n) in complexity because when it determines that it needs to insert a turn, it inserts it at the point where it last tightened the funnel to the left (when turning left and vice versa) and then starts tracing through the nodes from that point again.

If you want to straighten the path outside of the polygons that form part of the A\* route, things get a lot more complex. You'll need to implement a ray-cast routine that can test if two points in your navmesh can see each other (you should have this anyway so you can see if you need to use A\* at all). You do this by intersecting the line segment formed by origin-\>target with the connecting edges of the polygon containing the origin, then testing the connecting edges of the polygon that moves you into and so on. If you intersect a non-connecting edge (I call them border edges), then you've hit an obstacle.

You can then perform this ray-cast test whenever the funneling algorithm determines it needs to insert a turn to see if it really does, but I think you'll have to keep performing that test at every node until you do insert a turn (at which point you can revert to the simple funnel algorithm). That's going to get expensive, rendering the path straightening approximately O(n^2).

## Representing the navmesh

You can represent your mesh as an array of polygon classes. The polygon class could be as simple as an array of vertices and an array of references to the adjacent polygon for each edge if there is one. Of course you can probably think of ways to store that more compactly. Since a vertex is usually shared by several polygons, it's normal to have one big array of vertices and then have each polygon store indices into that array. Depending on the characteristics of your navmesh you might have an average number of connecting edges that's only 50% or less of the number of edges. In that case you might want to store a link to another polygon and the index of the edge rather than store a link for every edge. Also I recommend you store the index of the polygon in the navmesh's polygon array rather than using a class reference.
> 15 votes

---
Tags: java, path-finding, navmesh
---


# Question
Title: How should a team share/store game content during development?
Other than Dropbox, what out there has been especially useful for storing and sharing game content like images during development (similar feature set to Dropbox like working offline, automatic syncing and support for windows/osx)?

We are looking into hosting our own SharePoint server but it seems to be really focused on documents... Maybe Box.net would work?

**EDIT**

For code, we are using Git.

To be more precise, I was looking for an easy, automatic way for content produced by artists/audio engineers to be available to everyone. Features like approvals of assets don't hurt either. Following the answer linked by Tetrad, Alienbrain looked pretty interesting but..is way out of our budget (may be something to invest in in the future).

What ended up doing...

We were going to go with Box.net but downloading the sync apps for desktop use required us to wait to be contacted by them for some reason. We did not have much time to wait so we ended up going with Dropbox Teams. Box.net has a nice feature set but we never really felt held back without them.

Thanks for the help :).

# Answer
> 19 votes
It depends on the nature of the content:

* Is it an asset that is loaded by the game, like a model or a texture? **You want a version control system.**
* Is it some form of data not loaded directly by the game, but used to build data directly loaded by the game, such as a localisation spreadsheet? **You want a version control system.**
* Is it a document outlining the game design, some feature detail, or a technical process or procedure? **You want a version control system.**
* Is it a file that can be rebuilt from something that's already in version control, such as executables and linker objects? **You *probably* don't want a version control system (\*).**
* Is it a file that you want to share with a coworker temporarily, such as a code change or an updated asset, that you *don't* want permanently in the game, but they need in order to continue their work? **You don't want a version control system. (^)**

**(^)** There are a few options in this case:

* You mentioned Dropbox, which is great when you're collaborating with teams over any distance, but limits you to 2GB. This should be fine for temporary use, given that all your other data should be in version control; however, if you need more space there's now a (paid) Dropbox for Teams option.
* If you don't want to pay for the cost of a bigger Dropbox plan, but only need to occasionally share large files, then using one of the dozens of file sharing sites (like RapidShare) might be an option.
* Hosting an FTP server may also be viable for you.
* If you're working on the same LAN (or you can set up a VPN), then both Windows and Mac can create network shares that are writeable by one another, without size restrictions. It's common to create a read/write share named Dropbox, and use that for exchanging files. It's also common to name machines after their users; i.e. to send a file to John Doe, I can open the share `\\JOHNDOE\Dropbox` and place the file there.
* Special mention for Git if you're sharing code: you can create a separate branch with your code changes, and push to your main repository. Other people can then grab your changes, without disrupting your `master` branch. (In these cases, it's common to place your branch in a directory with your name, i.e. `johndoe/bugfix`.)

**(\*)** Occasionally, you'll want to commit/store executables and symbol files somewhere in order to debug issues with older builds, without needing to rebuild the game. This is commonly the case when dealing with crash dumps.

---
Tags: server, storage
---


# Question
Title: How to create projection/view matrix for hole in the monitor effect
Lets say I have my XNA app window that is sized at 640 x 480 pixels. Now lets say I have a cube model with its poly's facing in to make a room. This cube is sized 640 units wide by 480 units high by 480 units deep. Lets say the camera is somewhere in front of the box looking at it.

How can I set up the view and projection matrices such that the front edge of the box lines up exactly with the edges of the application window?

It seems like this should probably involve the Matrix.CreatePerspectiveOffCenter method, but I don't fully understand how the parameters translate on to the screen.

For reference, the end result will be something like Johhny Lee's wii head tracking demo: http://www.youtube.com/watch?v=Jd3-eiid-Uw&feature=player\_embedded

P.S. I realize that his source code is available, but I am afraid I haven't been able to make heads or tails out of it.

# Answer
(None of this advice is specific to the XNA function you named; it applies equally well to e.g. `glFrustum`. I don't know XNA.)

You need to think about the **view frustum**. The rectangle in 3D space which is "at the location of" the viewport is precisely the "near plane" face of the frustum, and the left, right, bottom, and top values are the positions of the edges of that face.

First, compute the coordinates of the box, in the coordinate system where the camera is at (0,0,0), the box is axis-aligned, and the box's "hole" face is parallel to the XY plane and on the negative-Z side of it. Then set the left, right, bottom, and top values to the corresponding coordinates of the edges of that face of the box. Set the near plane distance to the negated (i.e. positive) Z coordinate of the box face, and set the far plane distance to whatever you see fit.

This will cause everything in the volume in front of the box/monitor to be clipped. If you don't want that, then change the near plane value — but you must scale the left, right, bottom, and top values by the same amount. (Visualize the view frustum — as the near face gets closer to the camera, the coordinates defining its edges get *proportionally* smaller to preserve the same angles.)

In the following diagram, *l*, *t*, *b*, *r*, and *n* are the coordinates I've been discussing. The near face of the frustum, which is also your box face, is the smaller rectangle; the rest of the box does not correspond to anything.

(image from Wikimedia Commons, by Martin Kraus, CC-BY-SA licensed)
> 3 votes

---
Tags: mathematics, xna-4.0, matrix, projection
---


title: 2d, Top-down map with different levels

text:
# Question
Title: 2d, Top-down map with different levels
So, I'm creating a 2d, top down, sprite based (tiled) game, and right now I'm working on maps (well, a map editor at the moment, but it will be creating my maps, so basically the same thing).

### The scenario

So, I'm thinking about efficiency and creating a map in pieces. In each piece, I plan on having 'layers'. Basically, I plan on rendering it down to a 'below hero' level, and an 'above hero' level, with the hero rendered in between obviously. There will likely also be a 'on level with hero' layer, but I'm not quite there yet. Not even worrying about events or interaction yet. Just looking to get a hero on the screen.

Now for movement, I obviously need to know what tiles can be moved and in what direction. My plan at the moment is each tile getting 8 bits (4 'can enter in direction' bits, 4 'can leave in direction'). This will allow me to limit movement and even allow one way directional movement.

### The dilemma

This works great for a lot of scenarios. It will allow me to store a map in essentially 3 layers, a string, and gives me flexibility going forward. However, I can't create maps that themselves have layers. A good example is a bridge where the user can go under or over the bridge without invalid moves being allowed. I can't create a platform and allow movement underneath. These are things I would like to be able to include in my game.

### My idea

In theory, I could allow multiple hero layers and then allow multiple sets of 'below' and 'above' layers (or sandwich layers). But this complicates my system, and makes movement between maps potentially tricky (If the hero is on the third layer at the edge of a map, but that corresponds to the second layer on the other map, how can I allow or disallow movement).

### My question

Is there a better way to manage multiple maps with multiple levels like this where a users level may be 'connected' on different levels on different maps?

Or even...

Am I doing this the hard way? Is there a more standard way to handle top-down 2d tiled maps that I am just not aware of?

### Things to note or that might be helpful

* This will be done in Javascript (transferred around in JSON)
* State will need to be transferred quickly, so a map-id and x/y/direction should be enough to get me a boolean 'can move' value
* Maps will not be standard sized (though they will be in a certain number of tiles)
* Making an editor tool so that I can have others help, so something that I can create in a tool would be helpful
* 'Teleportation' locations will likely need to exist to get into building maps and to and from different map sets (which will not necessarily be connected), but have not been created yet (lumping in with events at the moment).

# Answer
> 2 votes
> 'below hero' level, and an 'above hero'

Why do they layers have to be relevant to the Hero? Shouldn't it be the opposite as in the hero has a current level they are on? If the hero is on level 1 then all levels above level 1 are drawn after or on top of the hero. This works for any number of level so you are not restricted to 2 levels. You can have the player keep track of what level they are on and alter it with basic collision detection. A wall to wall series of tiles on the top of a stair case can set the player to layer 1 where as a similar thing could set the player to level 0 at the bottom of the stairs.

You would only do collision checking for the current layer so in the case of going under the bridge you could walk right under it if there was no obstruction on layer 0 while all above layers would be rendered only.

---
Tags: 2d, architecture, sprites, javascript, tiles
---


# Question
Title: How can I respond to mouse events in AS3?
**Background:**

Trying to make a simple "drop the ball" game.

The code is located inside the first frame of the timeline. Nothing more is on the stage.

**Issue:**

Using QuickBox2D I made a simple If statement that drops and object acording the Mouse-x position:

```
if (MouseEvent.CLICK) {
sim.addCircle({x:mouseX, y:1, radius:0.25, density:5});

```

I imported the MouseEvent library:

```
import flash.events.MouseEvent;

```

Nothing happens if I click, no output errors either.

**See it in action:** http://gabrielmeono.com/download/Lucky\_Hit\_Alpha.swf http://gabrielmeono.com/download/Lucky\_Hit\_Alpha.fla

**Full Code:**

```
    [SWF(width = 350, height = 600, frameRate = 60)]
import com.actionsnippet.qbox.*;
import flash.events.MouseEvent;

var sim:QuickBox2D = new QuickBox2D(this);
sim.createStageWalls();
//var ball:sim.addCircle({x:mouseX, y:1, radius:0.25, density:5}); //

// make a heavy circle

sim.addCircle({x:3, y:1, radius:0.25, density:5});
sim.addCircle({x:2, y:1, radius:0.25, density:5});
sim.addCircle({x:4, y:1, radius:0.25, density:5});
sim.addCircle({x:5, y:1, radius:0.25, density:5});
sim.addCircle({x:6, y:1, radius:0.25, density:5});
// create a few platforms

sim.addBox({x:3, y:2, width:4, height:0.2, density:0, angle:0.1});
// make 26 dominoes
for (var i:int = 0; i<7; i++){
//End
     sim.addCircle({x:1 + i * 1.5, y:16, radius:0.1, density:0});
     sim.addCircle({x:2 + i * 1.5, y:15, radius:0.1, density:0});

//Mid end

      sim.addCircle({x:0 + i * 2, y:14, radius:0.1, density:0});
      sim.addCircle({x:0 + i * 2, y:13, radius:0.1, density:0});
      sim.addCircle({x:0 + i * 2, y:12, radius:0.1, density:0});
      sim.addCircle({x:0 + i * 2, y:11, radius:0.1, density:0});
      sim.addCircle({x:0 + i * 2, y:10, radius:0.1, density:0});

      //Middle Start
     sim.addCircle({x:0 + i * 1.5, y:09, radius:0.1, density:0});
     sim.addCircle({x:1 + i * 1.5, y:08, radius:0.1, density:0});
     sim.addCircle({x:0 + i * 1.5, y:07, radius:0.1, density:0});
     sim.addCircle({x:1 + i * 1.5, y:06, radius:0.1, density:0});
}

if (MouseEvent.CLICK) {
    sim.addCircle({x:mouseX, y:1, radius:0.25, density:5});

sim.start();
/*sim.mouseDrag();*/

    }

```

# Answer
You can't catch mouse-events like that. You have to add an event listener, like this:

```
function handleClick(evt:MouseEvent):void
{
    sim.addCircle({x:mouseX, y:1, radius:0.25, density:5});
}

addEventListener(MouseEvent.CLICK, handleClick);

```
> 2 votes

---
Tags: actionscript-3, box2d, mouse, flash-cs5
---


# Question
Title: How can I create an orthographic display that handles different screen dimensions?
I'm trying to create an iPad/iPhone game using GLES2.0 that contains a 3D scene with a heads-up-display/GUI overlaid on the top. However, this problem would also apply if I were to port my game to a computer and run the game in a resizable window, or allow the user to change screen resolutions...

When trying to make the 2D GUI/HUD work I've made the assumption that all I'm really doing is drawing a load of 2D textured 'quads' on the screen and am trying to treat the orthographic projection as an old-style 2D display with 0,0 in the upper left and screenWidth,ScreenHeight in the lower right.

This causes me all sorts of confusion when I rotate my ipad into Landscape mode since I can't work out what to put into my projection and modelview matrices to turn everything around the right way. It also gets messy if I want to support the iPad's large screen, an iPhone or a Retina display since I have to then draw three sets of textures for everything and work out which ones to use.

Should I be trying to map the 2D OpenGL co-ords 1:1 with the screen? While typing out this question it occurs to me that I could keep my origin in the centre, still running -1/+1 along the axes. This would let me scale my 2D content appropriately on the different screen sizes, but wouldn't I end up with the textures being scaled and possibly losing quality?

I'm using OpenGLES 2.0 and have a matrix library that has equivalents to the GLES1.1 glOrthof() and glFrustrum() calls.

# Answer
> 1 votes
You look to be on the right track to me with your last set of questions.

I would suggest first and foremost that you scale the position but not nessecarily the size of the HUD elements. That way when you rotate your device or simply change the resolution the elements look the same but are positioned properly.

Next up I would take a look at how many rendering iPhone/iPad games actually support horizontal and vertical rotation modes. I would say hands down they almost all support only one or the other and additionally, rarely rotate to even the alternate (180 degrees) positioning that would keep the same resolution.

Lastly, to address the quality issue, this should kind of go away if you only scale positional information. What may come up however is visual clarity. And while this can lead back to quality I am just attempting to focus on the fact that if they scale the resolution very high, the HUD elements may appear so small as to be unreadable. Alternately if they scale the resolution down alot and then you can see nothing but the HUD. My suggestion for solutions to this is to develop a more advanced set of HUD elements since it sounds like you are doing one quad per element. If you could make a button up out of 9 background pieces and a text rendering on top of it it may take care of most of your issues as then you could scale the size of the hud or offer hud sizing options to the end user. You break apart the button's background into the top left corner the top bar the top right corner the left border the central background the right border the bottom left corner the central bottom border and finally the bottom right corner. In this manner you scale the size of the object (and likely the text) but not the texture, you let the corners remain the same size and the borders be the same height for horizontal ones and width for vertical ones so the texture can repeat along the edges. Same for the background section which I would suggest even just making a solid color.

Anywho, like I said you look to be in the right direction.

Hope this helps.

---
Tags: opengl, architecture, graphics-programming, opengl-es2
---


# Question
Title: Steady zoom on center in LWJGL (Modelview)
I am having a problem in LWJGL with zooming in and out. I am using glScaled(zoom, zoom, 1) before glTranslated. There are 2 problems: 1. The rate of zoom speeds up a lot when zooming out (lower zoom value). 2. It zooms in on the bottom left corner of the screen rather than the center. Eventually, I would like to have the zoom focused on the mouse position.

I have tried to fix these problems by make it glScaled(zoom^12, zoom^12, 1) so that the greater the zoom value, the faster it will zoom in order to balance out the faster zoom at lower zoom values. To compensate for the zoom focused on the bottom left, I have tried to subtract (zoom+1)^10 + 2^10 from the X and Y of each sprite. This results in a curved zoom path, first to the left and then to the right. It is a 2D game.

# Answer
> 0 votes
These should be considered as two separate problems:

**The center-point problem**

`glScale` always acts on the center of your coordinate system. You can do scaling at a different point by translating that point to the center temporarily. Just do this sequence:

```
glTranslated(centerX, centerY, centerZ);
glScaled(zoom, zoom, 1);
glTranslated(-centerX, -centerY, -centerZ);

```

(I might have the order reversed.)

**The speed problem**

Suppose you are adjusting your zoom variable at a rate of 1.0 per second. Suppose your zoom level is 2.0, and the user is zooming out. Then it takes 1 second to go from 2.0 to 1.0, and 1 second to go from 1.0 to 0.0 — at which point things are infinitely small.

What you probably want is for the visible zoom speed to be *proportional to the current zoom value*. There are two ways to do this:

* When you modify your `zoom` variable, use the current value as a multiplier: zoom in with `zoom *= 1 + SPEED` and zoom out with `zoom /= 1 + SPEED`.
* Compute the scale factor as an *exponential* function of the zoom variable.

```
double scale = Math.exp(SPEED*zoom);
glScaled(scale, scale, 1);

```

These two methods are completely equivalent except for needing slightly different values for `SPEED`. (If you want to learn the math behind this, looking up *compound interest* and *continuous compounding* would be a place to start.)

---
Tags: 2d, java, camera
---


title: Make a basic running sprite effect

text:
# Question
Title: Make a basic running sprite effect
I'm building my very first game with *XNA* and i'm trying to get my sprite to run. Everything is working fine for the first sprite. E.g : if I go right(D) my sprite is looking right , if I go left(A) my sprite is looking left and if I don't touch anything my sprite is the default one. Now what I want to do is if the sprite goes Right, i want to alternatively change sprites (left leg, right leg, left leg etc..) *xCurrent* is the current sprite drawn *xRunRight* is the first running Sprite and *xRunRight1* is the one that have to exchange with *xRunRight* while running right. This is what I have now :

```
    protected override void Update(GameTime gameTime)
    {
        float timer = 0f;
        float interval = 50f;
        bool frame1 = false ;
        bool frame2 = false;
        bool running = false;

        KeyboardState FaKeyboard = Keyboard.GetState();
        // Allows the game to exit
        if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed)
            this.Exit();

            if ((FaKeyboard.IsKeyUp(Keys.A)) || (FaKeyboard.IsKeyUp(Keys.D)))
            {
                xCurrent = xDefault;
            }

            if (FaKeyboard.IsKeyDown(Keys.D))
            {

                timer += (float)gameTime.ElapsedGameTime.TotalMilliseconds;
                if (timer > interval)
                {
                    if (frame1)
                    {
                        xCurrent = xRunRight;
                        frame1 = false;
                    }
                    else
                    {
                        xCurrent = xRunRight1;
                        frame1 = true;

                    }
                }

                xPosition += xDeplacement;

            }

```

Any ideas...? I've been stuck on this for a while.. Thanks in advance and let me know if you need any other part from the code.

# Answer
You want to use a spritesheet. The SpriteSheetPacker tool can assist you in making one.

First of all, we need to define some objects:

```
Texture2D SpriteSheet;
Point FrameSize = new Point(64, 64);//this is the size of your frame.  This is an example.
//It should be the Width, Height of each of your frames.
//It's important that each frame is the same size.

Point SheetSize = new Point(12, 1);//this is how many frames of animation
//you have.  The first number is the number of frames in a row.  The second is the
//number of rows you have.  E.g, for 8 frames that are in one row, it would be (8,1).

Point CurrentFrame = new Point(0, 0); //You'll use this later to keep track
//of what frame you're on.

int AnimationDelay = 0;//You'll use this later to slow down the animation
//if it plays too quickly.

```

Next, you need to assign a texture to your Texture2D:

```
SpriteSheet= Content.Load<Texture2D>("Sprites\\SpriteSheet");//Loads Texture

```

Then, you need to update your animation:

```
if (AnimationDelay == 5)// delay frame update if it's too fast
   {
     if (CurrentFrame.X < SheetSize.X)
        {
           ++CurrentFrame.X;// Move to a new frame
        }
        else
        {
           CurrentFrame.Y++;//Move down a row, since we've
           //hit the end of the current one
           CurrentFrame.X = 1;//set the X to 1, so we start fresh
        }
        if (CurrentFrame.Y >= SheetSize.Y)
           {
             CurrentFrame.X = 0;
             CurrentFrame.Y = 0;//Start the animation over again
           }

           AnimationDelay = 0;//Set this to 0, so we delay it again
    }
    else
    {
      AnimationDelay += 1;// add one, so we can continue when we are ready
    }

```

Now, we have to draw your sprite, using your new spritesheet:

```
spriteBatch.Draw(SpriteSheet, Position,
                                new Rectangle(CurrentFrame.X * FrameSize.X,
                                CurrentFrame.Y * FrameSize.Y, FrameSize.X, FrameSize.Y),
                                Color.White, Rotation, Center, Size, SpriteEffects.None, 0);

```

---

Alright, time to explain. Everything is pretty straightforward, except for the update, so I'll explain that.

Essentially, what you're doing is moving a Rectangle across your giant spritesheet. In doing so, you will only draw what is inside the rectangle, giving the illusion of changing frames. In reality, you're just drawing a portion of the larger sprite.

You continue this way until you hit the last frame of your row. Then, if applicable, you move down to the next row. You continue this way until you reach the last frame of the last row, at which point you start over. You delay the update with AnimationDelay, as it will normally "play" the animation too quickly.

---

As for your questions, yes, it is possible to only do a portion of that sheet. However, since the sheet is laid out in a rather arbitrary manner, it's not as easy as specifying a row to start on.

Personally, I would cut out the row that you need (in an image editing program like GIMP or Photoshop. GIMP is free, Photoshop is not). Otherwise, you'll have a hard time lining up your frames.

---

It is possible to skip frames and rows, if you know which ones you don't want to use. For example, this will skip frame 5 of row 2:

```
if(CurrentFrame.X == 4 && CurrentFrame.Y == 2)
  {
     CurrentFrame.X += 2;//This will skip frame 5.  Just be sure to not use the
     //normal CurrentFrame.X++, or you're skip 2 frames!
  }

```

Similarly, you can apply this to skip whole rows as well:

```
if(CurrentFrame.X >= SheetSize.X && CurrentFrame.Y == 2)
  {
     CurrentFrame.Y += 2;//This will skip row 3.  Just be sure to not use the
     //normal CurrentFrame.Y++, or you're skip 2 rows!
     CurrentFrame.X = 1;
  }

```
> 2 votes

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


# Question
Title: How to Effectively Create Bullet Patterns
I'm currently creating a top-down shooter like Touhou. The most important factor of the game is that there are many diverse patterns and ways at which bullets are generated and shot at the player, see this video: http://www.youtube.com/watch?v=4Nb5Ohbt1Sg#start=0:60;end=9:53;

At the moment, I'm using a class "Pattern" which has a series of steps on moving and shooting. However, I feel this method is quite laborous as I have to create a new Pattern for each attack and perhaps new Bullet classes that will implement a certain behavior.

This question received a comment suggesting I should look into BulletML for easy creation and storage of bullets with a specific pattern. It looks decent, but it led me to wonder, what other solutions do you have that I should take into consideration?

**Update**

My current design is as follows:

An example of an implemented pattern:

My GigasPattern first executes a teleport which moves Alice to a certain point (X, Y) on the screen. After this is completed, the pattern starts using the Mover to move the sprite around (whereas teleporting has separate effects and animation). These are of no concern, really, as they are quite simple.

The Shooter also creates various Attacks, which are classes again that the Shooter can use to create various patterns of bullets, much like the one in the question I posted. Once the Mover has reached it's destination, both it and the shooter stop and return to an inactive state. The pattern completes, is removed by the AI and a new one gets chosen.

# Answer
It is going to be laborious no matter what, creating such a level seems like an easy task, and it may not all that difficult, but it will always take a lot of time. (A very rough estimate: 1000 times the playtime for something as cool as that video.)

If you use a scripting language you still have to write exactly the same code, just in a different language, the advantage is that you can make scripted levels without messing with the compiled code. If you work in a big team you'd definitely want that, but as a sole developer it usually doesn't make a big difference.

BulletML is not an answer in itself, you need a working implementation in your language, which must interface with the rest of your game. And still there is a huge job of writing all those XML files.

I'm inclined to say that you should stick to programming the desired patterns in classes as you do, but perhaps you could reveal some samples of your current structure, there might be improvements to make.

Edit:
There may be one realization which could simplify things a bit, and give you a slightly better toolbox. You could describe an AI as being a pattern, ideally there should be just one type of entity, but any such entity may choose to invoke another entity of the same type to do the job. This will rid you of any limits to how deep you can nest responsibility propagation and give you one less type of class to think about.

At least that is what I gather from the diagram. While you rightly should limit the amount of code you include in a question, there is never a complete substitute for seeing some actual code.
> 4 votes

# Answer
Maybe you could implement an own, small script language for your game. Then you would be able to script bullet behaviours by just add new scripts. The advantage of an own script language is that you could use that at other parts of you game. Or you could try to use Lua (I don't know what language/framework you are using). But in my opinion Lua would be an overkill if you just want to have movin patterns.

Between: I did this already for a space shooter, but for the enemy behaviour. It worked well, so you really could just try that.
> 2 votes

# Answer
I was in the exact same situation a while ago and started implementing my own architecture for bullet patterns. I gave up, though, because I came across an implementation of BulletML for C#/XNA: BulletML C#

I had to make a few changes, but now creating patterns that look spectacular are really really easy. There is a great demo here that shows you how, a few lines of XML, can create awesome patterns.

If you are working on C#, I highly recommend avoiding re-inventing the wheel. Especially if you want to have very complex patterns. It may take some time to wrap your head around BulletML, but, in my opinion, it is well worth your time.

However, if you decide not to use BulletML, then, at the very least, have a look at the C# code and get an idea of its architecture. It might give you some ideas.
> 2 votes

---
Tags: architecture, shooter
---


title: Jumping Vs. Gravity

text:
# Question
Title: Jumping Vs. Gravity
Hi i'm working on my first XNA 2D game and I have a little problem. If I jump, my sprite jumps but does not fall down. And I also have another problem, the user can hold *spacebar* to jump as high as he wants and I don't know how to keep him from doing that. Here's my code: The Jump :

```
    if (FaKeyboard.IsKeyDown(Keys.Space))
        {
            Jumping = true;
            xPosition -= new Vector2(0, 5);
        }

        if (xPosition.Y >= 10)
        {
            Jumping = false;
            Grounded = false;
        }

```

The really simple basic Gravity:

```
    if (!Grounded && !Jumping)
        {
            xPosition += new Vector2(1, 3) * speed;
        }

```

Here's where's the grounded is set to True or False with a Collision

```
    Rectangle MegamanRectangle = new Rectangle((int)xPosition.X, (int)xPosition.Y, FrameSizeDraw.X, FrameSizeDraw.Y);
        Rectangle Block1Rectangle = new Rectangle((int)0, (int)73, Block1.Width, Block1.Height);
        Rectangle Block2Rectangle = new Rectangle((int)500, (int)73, Block2.Width, Block2.Height);

        if ((MegamanRectangle.Intersects(Block1Rectangle) || (MegamanRectangle.Intersects(Block2Rectangle))))
        {
            Grounded = true;
        }
        else
        {
            Grounded = false;
        }

```

The grounded bool and The gravity have been tested and are working. Any ideas why? Thanks in advance and don't hesitate to ask if you need another Part of the Code.

# Answer
So, I'm not very good at XNA, but if I had to guess, the following would be your issue (unless I'm misunderstanding your code):

```
if (FaKeyboard.IsKeyDown(Keys.Space))
{
    Jumping = true;
    xPosition -= new Vector2(0, 5); // This Line
}

```

You are changing the position, even if `Jumping` should be false again. You'll want to check if `Jumping` is false after you've checked if they should still be jumping, and then apply the vector. You'll probably also want another variable to see if they have already jumped as high as you allow. Let's call it `Falling`. You could also do it a single if statement. Something like:

```
if (FaKeyboard.IsKeyDown(Keys.Space) &&
        (Grounded || (!Falling && xPosition.Y < 10)))
{
    Jumping = true;
}
if (xPosition.Y >= 10) {
    Jumping = false;
    Falling = true;
}

```

And then, when you are `Grounded`, you'll want to set `Falling = false` again.

At least, that's my hunch.
> 3 votes

# Answer
You need to change this:

```
if (FaKeyboard.IsKeyDown(Keys.Space))
    {
        Jumping = true;
         xPosition -= new Vector2(0, 5);
    }

```

To this:

```
if (FaKeyboard.IsKeyDown(Keys.Space) && Jumping == false)
    {
         Jumping = true;
         xPosition -= new Vector2(0, 5);
    }

```

Woops, nevermind. Got ninja'd.
> 1 votes

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


title: Game Programming in java

text:
# Question
Title: Game Programming in java
I'm new to this site as well as new in game development, so I need to get a great start for it. Can anybody tell me from where I should start and some books or link are appreciable.
What are the prerequisites to start game programming in java?
I already knows the concepts of `java`.

# Answer
> 4 votes
Have a look around at javagaming.

# Answer
> 6 votes
Among all java game engines out there, jMonkeyEngine is a very good one.

Its just not a library, its comes with a full featured sdk. There is abundance of tutorial and the community is very active. You can check this out too, jMonkeyEngine Beginner’s Guide

# Answer
> 1 votes
Have a look at some samples in this repository:

https://github.com/adamgit

https://github.com/adamgit/Entity-System-RDBMS-Beta--Java-

https://github.com/adamgit/Game--Escape-from-the-Pit

It is good introduction into basics of modern game engine architecture in Java (component-based entity systems).

Basic idea is that component-based approach is more suited for games than traditional entity-centric object-oriented. This is because the latter leads to bloated super-classes with lots of responsibilities and rigid inheritance hierarchies.

---
Tags: java
---


# Question
Title: Continuous Physics Engine's Collision Detection Techniques
I'm working on a *purely continuous* physics engine, and I need to choose algorithms for broad and narrow phase collision detection. "Purely continuous" means I never do intersection tests, but instead want to find ways to catch every collision before it happens, and put each into "planned collisions" stack that is ordered by TOI.

**Broad Phase** The only continuous broad-phase method I can think of is encasing each body in a circle and testing if each circle will ever overlap another. This seems horribly inefficient however, and lacks any culling.

I have no idea what continuous analogs might exist for today's discrete collision culling methods such as quad-trees either. *How might I go about preventing inappropriate and pointless broad test's such as a discrete engine does?* I also would like to be able to see collisions more than 1 frame ahead to.

**Narrow Phase**
I've managed to adapt the narrow SAT to a continuous check rather than discrete, but I'm sure there's other better algorithms out there in papers or sites you guys might have come across.
*What various fast or accurate algorithm's do you suggest I use and what are the advantages / disatvantages of each?*

**Final Note:**
I say *techniques* and not *algorithms* because I have not yet decided on how I will store different polygons which might be concave, convex, round, or even have holes. I plan to make a decision on this based on what the algorithm requires (for instance if I choose an algorithm that breaks down a polygon into triangles or convex shapes I will simply store the polygon data in this form).

# Answer
*I am really just throwing ideas around here. Assuming you have (at the very least) the `current` position and `next` position; for each frame.*

You would need two separate broad phases, followed by your narrow phase:

* One that figures out that a collision will occur.
* One that figures out roughly where the collision actually occurs (e.g. a broad phase/inaccurate SAT)
* Finally your narrow phase would improve the result of the second broad phase.

# Initial Broad Phase

You could look into spatial hashing (using the `next` position, not `current`) for the initial broad phase. This would partition your problem space nicely into groups of collision candidates.

# Second Broad Phase

Do a binary multi-sample using the circle intersection method you described. In other words:

```
left = current
right = next
midpoint = (left + right) / 2
loop a desired amount of times tweaked to the accuracy you want:
  is a collision occuring at midpoint?
    right = midpoint
  else?
    left = midpoint
  midpoint = (left + right) / 2
pointOfCollision = midpoint

```

That accuracy tweak could also take distance into consideration - I **think** using the 'length squared' of `next - current` would get a pixel-perfect result.

# Narrow Phase

Do a binary multi-sample using something like PMask \- the logic will be exactly the same as above; just using a different collision routine.

# Finally

You will be able to work out the time-of-intersection from `pointOfCollision`, `current` and your current `speed` and `acceleration` (assuming you have a reasonable integrator).
> 2 votes

# Answer
Alright, I've seen you've updated your question so as to be more specific. I'll try and help you out some more.

For your first broad-phase check, I would strongly recommend spatial hashing.

Essentially, you divide your screen into equal-sized grids. Then, if an object lies within a grid, you add it to a "bucket" in a 1D hash table.

That's your first check done. If objects aren't in the same bucket, it would be impossible for them to intersect.

Continuing with that, you now have a list of buckets with objects (potentially) in them. You can do another broad-phase check here by either:

A.) Dividing this bucket into 4 other buckets, and checking the resulting 1D hash table. If they aren't in the same bucket, no collision.

Or:

B.) Doing a simple distance check and keeping the width and/or height of the object in mind to ensure accuracy.

But what about when you potentially have a collision?

Then I would recommend something along the lines of this. It's essentially a kind of mix between polygonal collision (for complex shapes) or rectangle/circle for less complex shapes.

Also, if you really want to "catch collisions before they happen and store them" then you can always do something like this:

If two objects are in the same bucket, then they might collide.

Furthermore, are the objects close enough that they may collide soon? (Taking into account velocity, object size and distance)

If the answer to both is yes, then go ahead and store it to do an intersection test later.

---

"**Old answer**

Well, unfortunately I have lost track of my "All Collision Types and What They Are Used For" Handbook. :)

However, even though this is an *extremely* broad queston, I'll get you started.

There's a good (answered) question pertaining to something like this here.

As well as an article by the people who made N and N+ over here.

Not to mention, you've got the good ol' fallback Per-pixel Collision.

I sincerely doubt that anyone will have a list handy of each and every type of collision, but this should help get you started.

However, I should mention that the type of collision you need (and will end up using) largely depends on the type of game you are creating. That's why you find tutorials - most people assume you have an idea of what you want, so they help you in that specific area. I realize that most of my links are tutorials on a specific subject, but I think a tutorial will honestly help you more. A list is one thing, but if you read about each bulletpoint yourself, you can come to a more educated decision that will likely suit your needs more specifically.
> 1 votes

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


# Question
Title: How can a single script attached to multiple enemies provide separate behavior for each enemy?
I am making a TD game and now stucked at multiple enemies using same script. All is well with scripts attached with one enemy only. Problem is in running multiple enemies.

Here is the overview. I have a Enemy object with which I have attached a 'RunEnemy' script. Flow of this script is:

RunEnemy.cs:

```
PathF p;
p = gameObject.GetComponent<PathF>();     //PathF is a pathfinding algo which has     'search; function which returns a array of path from starting position
PathList = p.search(starting position);
//-------------------------------

if(PathList != null) {                               //if a way found!
if(moving forward)
     transform.Translate(someXvalue,0,0);  //translates on every frame until next grid point

else if(moving back)
   transform.Translate(0,someXvalue,0);

    ...and so on..

      if(reached on next point)
         PathList = p.search(from this point)   //call again from next grid point so that if user placed a tower enemy will run again on the returned path
}

```

Now I have attached this script and "PathF.cs" to a single enemy which works perfect. I have then made one more enemy object and attached both of these script to it as well, which is not working they both are overlapping movements. I can't understand why, I have attached these scripts on two different gameobjects but still their values change when either enemy changes its value. I don't want to go with a separate script for each enemy because there would be 30 enemies in a scene. How can I fix this problem?

# Answer
> 1 votes
I'd say you are executing one instance of the script, but retrieving only one path. Thus, each time the script runs, it executes the same path for every object it is in. Either store enemy-path pairs in a dictionary (or something like that) or use a script per enemy, with the corresponding encapsulation and local references.

A good option is linking the AI script to a global object and have all enemies needing it register for the service and poll it. Each frame the AI could update all the enemies registered. Or enemies could ask whenever interested for the next point in the path. This lets enemies do stuff while on their way and resume without requesting a new path, if the destination did not change.

# Answer
> 1 votes
Did you try putting RunEnemy in a RunEnemy class then writing another script "EnemyPath.cs" that create a new instance of RunEnemy and assign that script to the enemy prefabs?

Hope this helps

# Answer
> 1 votes
How are you putting the enemies in the scene? If they both exist from the start and have the same code the. Of course they're going to do the same thing (barring RNG).

Just instantiate the second enemy later. You have some kind of class responsible for spawning your enemies over time right?

# Answer
> 1 votes
I would guess that the error isn't in the code you've shown us, but in the code you've not shown us, for the PathF script. There's no reason why components on 2 separate objects would share any data unless you've made it so, by storing the data as static, by choosing to reference the same game object, or some other similar method.

---
Tags: c#, unity, tower-defense
---