# Question
Title: Manage a large number of independent actors in real-time
I am working on a large scale real-time strategy game - ideally with thousands of units active at once - but I am having trouble managing all of the units at once without it becoming astonishingly slow. The problem is that it takes a while to update the positions and states of everything each time step. Do you know any design patterns/methodologies/tips for mitigating this?

# Answer
There are two distinct things to consider when measuring and optimizing the performance of such a large-scale system of entities.

At the low level, you have the physical representation of your entities which tends to boil down to using efficient storage layouts like SoA (structs of arrays) to reduce the cost of iterating and updating all the active entities.

At the higher level, you have decision making logic, general game logic, AI and pathfinding. These are all tasks that have in common that they do not have to run at the same update rate as your rendering does.

As you would get an uneven frame time if you take the naive approach of just doing those tasks every N frames, it tends to be beneficial to amortize the cost over several frames.

If the task is incremental in nature, you could run part of the algorithm every frame and use partial results in your updates.

If the task is largely monolithic but separable per entity, you could perform that task for a subset of your game entities per frame, rotating among them in a round-robin fashion. This has the benefit of reducing the complexity of things like pathfinding and AI, as you don't have everyone trying to act at once.

In the large-scale tactical RTS I worked on, we focused on having robust data structures for querying the low-level representation in the high-level algorithms, for finding the neighbours of game entities. The low level update process acted on intents provided by the slow-updating high-level simulation, and in the end boiled down to a cheap particle simulation, scaling up well into the thousands.
> 4 votes

# Answer
as far as I can remember you'll always have less than 10,000 units a game. there is no game I can remember with more than that number, although empire earth could go up to 14000 trough a hack but no one will ever get to that point. so just having a static array of 10,000 objects seems to be more than needed.

as you know iterating over 10000 objects is no big deal but it may consume a lot of time if your algorithm run slower than O(n). for example if you try checking every two object for collision detection it will take O(n^2) time which means a lot of time. so you have to break your algorithms somehow. let's review a sample algorithm for every thing that I can think of right now:

1. collision detection: for every collision detection algorithm you have to check every two objects but you can eliminate some checking starting the loops. as I suggested in the comments you can use same algorithm given for this question. there is no need to use multiple threads or anything, even with one thread and 4 regions you'll reduce your checkings from n\*(n-1) to 4 * (n/4)*((n-1)/4), and by optimizing the number of regions you can get even better results. I think by using best number regions you can even get to O(n*log(n)).
2. you have to generate path for each moving object. the usual system i've seen so far is a very simple thing: whenever player commands units to move somewhere computer calculates it's path, after that in every cycle if the object can move it moves if it can't it skips that cycle. there is nothing special. although you can also change the algorithms given here to reduce you path finding calls and have real time pathfinding for each group of units but that's really not needed.
3. you have to check if some bullet or bomb or similar thing hits one of the units : you can use same regions you created for collision detection here.
4. for selecting units you can also use same regions.

in general I would suggest using an static array (or a dynamic array with reserved size) of 10,000 or 20,000 at most. then use something around 10 or 15 loops each one iterating over all the units. that is a real big array containing all the units from all players. so each index have both data about unit owner and unit type. you cal also create some other arrays for each player. in each index of these secondary array you'll just have to store pointers to objects in main array.

if you have any other questions put comments to add them to my answer.
> 1 votes

---
Tags: architecture, software-engineering, algorithm, rts
---


# Question
Title: Best practices for UnitTesting heavy Flash game clients and libraries?
We have several quite heavy game clients completely written in AS3 (some also use Flex for UI). Some clients are built with PureMVC, others are a pile of spaghetti code that's grown over the years. We also have several libraries used by our game clients that are written in AS3/Flex.

I'm tasked to evaluate the benefits/risk/cost of applying unit-testing to our clients and libraries and decided to give FlexUnit a closer look. I chose FlexUnit for a first attempt over fluint since FlexUnit is definitively able to test pure AS3 projects while I'm not sure about that for fluint.

Now I'm wondering what some good starting points and best practices are to get unit-testing into previously untested applications.

So my questions for unit-testing game clients and libraries are:

* How to get started? What are "low-hanging" (= easily testable) fruits to test with unit-testing?
* What are commonly tested aspects of game clients?
* Can you apply unit-testing to the BBOY design pattern or do you need to (extensively) refactor the game clients?
* Is it useful (and does it make sense) to test asset loading? If so, how to do it (comparing a binary diff, or comparing hash checksums, or ...)?
* How to test server communication and asynchronous commands?
* How to integrate the whole thing with Hudson/Jenkins CI server and Maven? Are there any reporting tools that can generate overviews of the run tests and report which test failed on which function/class?

I'm thankful for all pointers about the issue (direct answers, blog posts, forum discussions, how-tos, etc. etc. etc.) since I have little previous practical experience with unit-testing.

# Answer
> 5 votes
For me the easiest way to start testing a code base which doesn't have any tests, is to test bugs. When a you discover a bug, the first thing to do is write a test to reproduce it, then fix the bug to make the test pass.

Other low-hangers are classes which contain logic or data. If you're using the MVC pattern, test your domain models first, and then your controllers. Its often easiest to do this while re-factoring, because you will probably need to make changes to the classes to make them testable (using Dependency Injection and Single Responsibility principles).

For code which is not using patterns, see where re-factoring to a pattern might help, then approach it in a test-driven manner. Write tests for the structure you would like to have, then port your code into that structure to make the tests pass. At the very least, create a façade to act as an organised API over the spaghetti code. Write tests to develop the façade, then after it's working, write integration tests to get it working with your current code. You can then re-factor or re-write the spaghetti code without impacting the rest of the system.

Testing client-server-interaction is also a big pay-off, as it is usually the most fragile code because it interacts asynchronously with a foreign data set. Start at very coarse granularity. So first test that the client-server operations happen in the expected order. Then write tests to ensure that the data is sent and received in the correct format, then test how it breaks when used in unexpected ways. Write tests to call operations out of order, pass invalid data, etc. In FlexUnit you can use `[Test(expects="Error")]` when you are testing conditions that are expected to throw exceptions. You can also use `[Test(async)]` in conjunction with the `Async` methods to test asynchronous operations.

Testing third-party code can also pay off for two reasons: firstly it provides documentation by example and use cases for the library, and also indicates compatibility with other versions of the library.

The trick with writing ad-hoc tests (as with all re-factoring) is to do it in small steps, one line at a time until you have covered a method, then a method at a time until you have covered a class, then a class at a time until you have covered the entire library.

Another tip to keep in mind, is to test behaviour, or rather test what the code does, not how it does it. So if you have collision detection code, test that it returns a positive result and depth vector for overlapping objects, and negative results for non-overlapping objects. You don't need to test the actual algorithm which provides these results, just that the correct results are returned. You may test specific optimisations in the algorithm, but keep these separate from the main test code in case you change the algorithm later.

After you have written tests to cover the functionality in the code, then test edge cases (array lower and upper indexes, maximum and minimum numbers of sprites, level locations, inventory items, quest items). If you have combinations of items or quests, simulate testing them in all possible combinations using paramaterized tests in FlexUnit (use the Paramaterized test runner).

Performance is important with a game engine While FlexUnit does provide timings for each test, it comes with quite a large overhead. For this reason it is probably better to write your own framework for testing performance. It doesn't need to be complicated, it can be a simple class which calls a set of methods in order, measuring the time taken to run each function.

A useful tool to have is an automatic game-play script. Either hand-roll or record a game sequence, then play it back and verify the game state at each frame. This can be especially useful when optimising to measure speed increases.

The hardest code to test is visual and audio, as it requires some sort of signal processing to validate, and the resulting tests are usually fragile. Steer away from these initially, and do them last (if at all).

http://www.flexunit.org/?page\_id=6

# Answer
> 2 votes
Unit testing is hard. Since this is probably your first foray into testing, let me share some points with you from my years of experience:

* Not everything is testable, nor easy to test, nor worth testing.
* Tests, like code, need to be maintained and updated as the app changes.
* If nobody is running tests, or keeping them up to date, you might as well not test.

Having said that, the easy, low-hanging fruit are your plain classes -- classes with simple methods and properties. Call methods and verify that the state of your classes are as expected -- that's the easiest unit testing.

Beyond this, it gets hard. Hudson/Maven integrate, but I'm not sure about with FlexUnit.

My experience with testing is that over time, you get things done faster because you have a safety net -- you can risk bigger changes because you know if it broken.

This is probably not the answer you want, but it's good advice-type information that I feel you need to know :)

---
Tags: flash, actionscript-3, unit-testing
---


title: How to properly set up XNA shader?

text:
# Question
Title: How to properly set up XNA shader?
I'm trying to get a basic shader to work in XNA. I pass in a bool value called "TextureEnabled" to indicate whether or not it should expect some UV texture coordinates. But regardless of what I pass, it is always expecting the UV value, and it throws and InvalidOperationException -"TextureCoordinate0 is missing":

```
VertexShaderOutput VertexShaderFunction(VertexShaderInput input)
{
VertexShaderOutput output;

float4 worldPosition = mul(input.Position, World);
float4x4 viewProjection = mul(View, Projection);
output.Position = mul(worldPosition, viewProjection);

if (TextureEnabled == true)
{
    output.UV = input.UV; //**// always executes**
}
else
{
    output.UV = float2(1, 0);
}

return output;

```

}

Here's the declaration at the top of the effect file:

```
float4x4 World;
float4x4 View;
float4x4 Projection;
texture BasicTexture;
bool TextureEnabled = false;

```

I'm even setting the effect parameter in my XNA Draw() method:

```
paramName = "TextureEnabled";
effect.Parameters[paramName].SetValue(false);

```

If I just hard-code output.UV = float2(1, 0) instead of output.UV = input.UV, it does not throw an exception, so I know that has to be the problem. Its almost like the TextureEnabled variable isn't getting set up (or not evaluated), even though I can see SetValue(false) being called in the debugger. What am I doing wrong?

Here's the relevant source files, if needed: http://www.mediafire.com/?g85tc5d9582vs8g

# Answer
If it's in the vertex shader's input structure the shader needs it in the vertex stream, whether you use it or not. XNA is enforcing that.

You're implementing optional texturing improperly. If you do it this way, you'll need to supply texture coordinates always. Also, branching is still to be avoided.

Instead, have two techniques, referencing two different vertex shaders, with two different input structures. One input structure has texture coordinates, the other does not. Then, choose the correct technique for drawing. You don't need to have a 'texture enabled' constant in your shader at all.
> 5 votes

---
Tags: xna, shaders
---


# Question
Title: What is the difference between OpenGL 1.x and 2.x?
Is there a good tutorial that shows the difference between OpenGL 1.\* and 2.\*?

It would be very helpful to know which functions I should **not** be calling (like glBegin(), I assume).

# Answer
In short, OpenGL 2.0 lives between the fixed function (1.x) and fully programmable (2.x+) world; you can still use everything OpenGL 1.x has, while adding shaders. Moving forward (3.x+), all sorts of old fixed function systems start to get deprecated though, so it may be better to have a clean start instead of mixing both worlds.
> 11 votes

# Answer
OpenGL versions, by and large, are *not* like Direct3D versions. Your old code still works with the new versions (with one exception). Therefore, OpenGL v1.4 will function just fine under OpenGL 2.1. OpenGL versions are additions, not subtractions.

OpenGL 2.0 and 2.1 add shaders, in the OpenGL Shading Language. They also add several other features, like floating-point textures, non-power-of-two textures, and so forth. The full list is available in the OpenGL 2.1 specification itself. Just look at the "Version" sections; they will tell you what changed from the previous version.

The only exception to the rule about API changes is OpenGL 3.1 (yes, 3.1, not 3.0). In OpenGL 3.0, a number of APIs were designated as "deprecated". This means that the ARB, the committee in charge of OpenGL, could remove these functions from later versions. This removal happened in OpenGL 3.1. The 3.0 specification has a big list of deprecated stuff in it, and the 3.1 spec is trimmed down accordingly.

Note that you don't have to care (at least on Windows and Linux. MacOSX is different). You can run just fine in "compatibility" mode, where all of the previously removed features return. Implementations of OpenGL don't have to support compatibility contexts (and Mac OS X Lion doesn't. It supports either 2.1 or 3.2 core, at you request), but all of them still do. Just for backwards compatibility with older applications.
> 3 votes

---
Tags: opengl
---


title: How to fix bad Collada produced by FBX?

text:
# Question
Title: How to fix bad Collada produced by FBX?
I tried to use the FBX SDK (2011.3.1) to load FBX files and save them as Collada files in order to be able to import FBX files in Panda3D. Unfortunately the resulting Collada files are not usable for several reasons, among them:

* There's a Maya specific extra technique

diffuse

```
<diffuse>
    <texture texture="Map__2-image" texcoord="CHANNEL0">
        <extra>
            <technique profile="MAYA">
                <wrapU sid="wrapU0">TRUE</wrapU>
                <wrapV sid="wrapV0">TRUE</wrapV>
                <blend_mode>ADD</blend_mode>
            </technique>
        </extra>
    </texture>
</diffuse>

```
* It assigns a texcoord channel name that isn't referenced anywhere else in the file (in the previous code sample, no geometry uses "CHANNEL0"...)
* Every polygon is exported twice, a first time with a basic material (only diffuse color, specular color, etc.) and a second time with a textured material --\> this doubles the number of polygons of each model without any valuable reason

Anyway, the resulting Collada file cannot be opened correctly either with OpenCOLLADA or Panda3D's "dae2egg".

Anyone has any experience on how to "fix" it and make it understandable by common and well-reputed Collada importers such as OpenCOLLADA?

# Answer
A C# tool is your friend here - you can quickly write something using the .NET System.Xml framework which iterates over the input file, spots parts you don't like, and eliminates (or tweaks) them from the document before writing it back out again. Effectively that's what XSLT does, but in practice I've always found it to be easier to write C# code to describe the transformation than to find the cryptic XSLT syntax to do the same thing.

What you need to do is look at the 'bad' cases and spot what they have in common. For example if all of the diffuse techniques which have a texture which uses texcoord="CHANNEL0", that's easy to find. You just iterate all objects, and for each object, check all of its techniques for the offending attribute. If you don't find it, add the node to an output document and move on. If you don't recognise the node, add it to the output and move on. If you do find it, don't bother to add it to the output document and it will effectively be deleted.

Spotting duplicate polygons is a little trickier however, since you'd have to analyse each pair of polygons for equivalence. Would be much simpler if you could decide on a rule, such as "I don't care about flat colored polygons, only textured polygons", then you can just discard the appropriate polygons.

However it seems very odd to me that you're actually getting duplicates out; duplication of geometry is a big no-no for obvious reasons, so I'm surprised FBX would do that. I've only ever used Collada with Maya/Max, so couldn't vouch for what FBX produces. But I'd ask, are you super doubly sure that there really isn't duplicate geometry in there in the FBX file?
> 2 votes

# Answer
Find or write a different exporter, or perhaps (since Collada files are just XML) use \[XSLT\]\[1\] to transform the undesired data away or in to a more generalized form?
> 0 votes

---
Tags: collada
---


title: Can OpenGL ES help in this game?

text:
# Question
Title: Can OpenGL ES help in this game?
I am learning OpenGL ES and I have setup the environment. I believe the best way to learn things is to grab a dummy project and start working on it. So what I plan to do is...

Flare on a parachute http://goo.gl/8vN4R

Now I want this parachute to be created in OpenGL ES with sparkling effect at its tip. The sparkling effect must be shiny and animating like it's really sparkling. And the whole parachute would be moving down from top of the screen slowly and slightly fluctuating its position.

Please tell me if this is what I can do using OpenGL ES or I should use some other framework for fast development.

# Answer
As you're using OpenGL as the underlying graphics technology it is beneficial to think of the problem in terms of what OpenGL is good at.

As with any other 3D API, the focus is primarily on fast transformation and rasterisation of primitives like triangle, often with texture maps and in some cases programmable shaders.

Your scenario can be modeled in two parts: \- draw a 2D quad (or pair of triangles) which you translate and rotate according to the way you want it to move; \- the sparkling effect can be a set of quads with an animated texture or which rotate in place to give local motion to things.

Another approach for the "sparkling" could be to have a particle system attached which sends off sparks and particles into the air.
> 1 votes

---
Tags: iphone, opengl-es, effects
---


# Question
Title: SDL (or OpenGL), HTML5, Gecko and vector movies
I'm writing a platform game which uses SDL for the main graphics code. There is a chance that I may be using OpenGL for the rendering at a later stage, so answers could relate to either.

I'm needing a good method to include vector animations (such as a starting video) within the game.

Being a platform game, I would prefer to limit the dependents and size of the data. This rules out using Theora as the resulting vector animations would be needlessly lossy and overly large compared to the rest of the content. Flash sounds like an OK option, however it is finicky to embed (or even use) on non-windows platforms, and requires significant amounts of dependencies.

My idea is to use HTML5 animations, rendered by Gecko (the embeddable Firefox rendering engine) or WebKit (the Chrome rendering engine) in SDL, or rendered to an OpenGL surface in SDL. Quite simply - is this feasable? Are there any other examples as to how I should embed it? Is there a better (read: smaller and simpler) solution?

# Answer
One solution (probably the easiest at the moment but not necessary the best) is to include a complete web browser engine into your game.

I'm currently trying some solutions which wrap Chromium/WebKit in C++ (and C# or C) to use some HTML5 as GUI.

* Awesomium seems to be the more popular.
* Berkelium is an alternative solution, that I didn't tried yet.

The both are based on Chromium/WebKit and can be used under Windows / OSX / Linux. As they both render the browser content into off-screen buffers, you can do what you want (save to file, display etc.) with them.

I'm almost certain you can find similar frameworks for other web browser engines, but as I don't know them I can tell for sure.

A best practice is probably to integrate the web browser engine directly instead of using some frameworks but it request more time and work indeed.
> 2 votes

---
Tags: c++, opengl, html5, sdl
---


# Question
Title: Problem while loading an image for a texture
I have built a slideshow in slimDX and is scrolling a text at the bottom of the images. But I am running through a problem that when my new image is loaded in by the help of Texture.FromFile() function and i am giving the new image to the texture it is giving a little pause that is due to the loading of the image and moving text seems to jerky as it waits for some milli seconds when the new image is loaded. I am trying to resolve this problem by the help of a thread and also threadPool but is not getting the right output. Can any body please help me out in this context.

# Answer
Could you open all of the images before you start the slide show? Store them in an array of textures and then just loop through?

If not, then I would suggest using the c# threading classes Josh Petrie suggested, or using the Thread class itself, which can be easier to use than it looks.

If you are new to threading I would suggest avoiding it unless you are prepared to read up on a lot of nuances and problems unique to threading. It is certainly incredibly useful and powerful but you can end up causing a lot of problems if you're inexperienced.
> 3 votes

---
Tags: c#, textures, loading, slimdx
---


# Question
Title: How to make the accelerometer work in different angles
I am working on some Cocos2D tutorials (doodle drop) and have downloaded the program on my device. The program is working but I have to hold the iPhone in a very specific, and not very good, angle to make the little icon move. As it is i must hold the device horizontal with a small tilt forward.

I would like to be able to hold the device horizontal to vertical and tip the device and get the little icon to move.

Could someone please give me some hints how to code this?

Here is my my code:

```
-(void) spiderBelowScreen:(id)sender {

// Make sure sender is actually of the right class
NSAsser([sender isKindOfClass:[CCSprite class]], @"sender is not a CCSprite!");
CCSprite *spider = (CCSprite*)sender;

// Move the spider back up outside the top of the screen
CGPoint pos = spider.position;
CGSize screenSize = [[CCDirector sharedDirector] winSize];
pos.y = screenSize.height + [spider texture].contentSize.height;
spider.position = pos;
}

-(void) runSpiderMoveSequence:(CCSprite*)spider {

// Slowly increase the spider speed over time
numSpidersMoved++;

if (numSpidersMoved % 8 == 0 && spiderMoveDuration > 2.0f) {
    spiderMoveDuration -= 0.1f;
}

// This is the sequence which controls the spiders' movement
CGPoint belowScreenPosition = CGPointMake(spider.position.x, [spider texture].contentSize.height);
CCMoveTo *move = [CCMoveTo actionWithDuration:spiderMoveDuration position:belowScreenPosition];
CCCallFuncN *call = [CCCallFuncN actionWithTarget:self selector:@selector(spiderBelowScreen)];
CCSequence *sequence = [CCSequence actions:move, call, nil];
[spider runAction:sequence];
}

-(void) spidersUpdate:(ccTime)delta {

// Try to find a spioder which isn't currently moving
for (int i = 0; i < 10; i++) {
    int randomSpiderIndex = CCRANDOM_0_1() * [spiders count];
    CCSprite *spider = [spiders objectAtIndex:randomSpiderIndex];

    // If the spider isn't moving it won't have any running actions
    if ([spider numberOfRunningActions] == 0) {
        // This is the squense wich controls the spiders' movement
        [self runSpiderMoveSequence:spider];

        // Only onbe spider should start moving at a time
        break;
    }
}
}

-(void) resetSpiders {

CGSize screenSize = [[CCDirector sharedDirector] winSize];

// Get any spider to get its image width
CCSprite *tempSpider = [spiders lastObject];
CGSize size = [tempSpider texture].contentSize;

int numSpiders = [spiders count];

for (int i = 0; i < numSpiders; i++) {

    // Put each spider at its designated position outside the screen
    CCSprite *spider = [spider objectAtIndex:i];
    spider.position = CGPointMake(size.width * i + size.width * 0.5f, screenSize.height + size.height);
    [spider stopAllActions];
}

// Uschedule the selector just in case. If it isn't scheduled it wont do anything
[self unschedule:@selector(spidersUpdate:)];

// Schedule the spider update logic to run at the given interval
[self schedule:@selector(spidersUpdate:) interval:0.7f];
}

-(void) initSpiders {

CGSize screenSize = [[CCDirector sharedDirector] winSize];

// using a temporary spider sprite is the easiest way to get the image's size
CCSprite *tempSpider = [CCSprite spriteWithFile:@"spider.png"];
float imageWidth = [tempSpider texture].contentSize.width;

// Use as many spiders as can fit next to each other over the whole screen width
int numSpiders = screenSize.width / imageWidth;

// Initialize the spider array using alloc
spiders = [[CCArray alloc] initWithCapacity:numSpiders];

for (int i = 0; i < numSpiders; i++) {
    CCSprite *spider = [CCSprite spriteWithFile:@"spider.png"];
    [self addChild:spider z:0 tag:2];

    // Also add the spider to the spider array
    [spiders addObject:spider];
}
// call the method to reposition all spiders
[self resetSpiders];

}

-(void) update:(ccTime)delta {

// Keep adding up the playerVelocity to the players's position
CGPoint pos = player.position;
pos.x   += playerVelocity.x;

// The player should also be stopped from going outside the screen
CGSize  screenSize  = [[CCDirector sharedDirector] winSize];
float   imageWidthHalved    = [player texture].contentSize.width * 0.5f;
float   leftBorderLimit     = imageWidthHalved;
float   rightBorderLimit    = screenSize.width - imageWidthHalved;

// Preventing the player sprite from moving outside the screen
if (pos.x < leftBorderLimit)
{
    pos.x   = leftBorderLimit;
    playerVelocity  = CGPointZero;
}
else if (pos.x > rightBorderLimit)
{
    pos.x   = rightBorderLimit;
    playerVelocity  = CGPointZero;
}

player.position = pos;

}

-(void) accelerometer:(UIAccelerometer *)accelerometer didAccelerate:(UIAcceleration *)acceleration {

// controls how quickly velocity decelerates (lower = quicker to change direction)
float   deceleration    = 0.2f;

// determines how sensitive the accelerometer reacts (higher = more sensitivity)
float   sensitivity     = 6.0f;

// how fast the velocity can be at most
float   maxVelocity     = 550;

// adjust velocity based on current accelerometer acceleration
playerVelocity.x    = playerVelocity.x * deceleration + acceleration.x * sensitivity;

// we must limit the maximum velocity of the player sprite, in both directions
if (playerVelocity.x > maxVelocity)
{
    playerVelocity.x    = maxVelocity;
}
else if (playerVelocity.x < -maxVelocity)
{
    playerVelocity.x    = -maxVelocity;
}
}

+(id)scene {
CCScene *scene = [CCScene node];
CCLayer *layer = [GameScene node];
[scene addChild:layer];
return scene;
}

-(id)init {
if ((self = [super init])) {
    CCLOG(@"%@: %@", NSStringFromSelector(_cmd), self);

    self.isAccelerometerEnabled = YES;

    player = [CCSprite spriteWithFile:@"alien.png"];
    [self addChild:player z:0 tag:1];

    CGSize screenSize = [[CCDirector sharedDirector] winSize];
    float imageHeight = [player texture].contentSize.height;
    player.position = CGPointMake(screenSize.width / 2, imageHeight / 2);

    // scheduling the update method in order to adjust the player's speed every frame
    [self scheduleUpdate];
    [self initSpiders];

}
return self;
}

-(void) deallaoc {
CCLOG(@"%@: %@", NSStringFromSelector(_cmd), self);

// The spiders array must be released, it was created using [CCArray alloc]
[spiders release];
spiders = nil;

// Never forget to call [super dealloc]
[super dealloc];
}

```

# Answer
> 1 votes
It sounds like you need to transform the values you're getting from the accelerometer so the "neutral" orientation of the device is different. The more correct way of doing this is to construct a rotation matrix to transform the accelerometer input.

But if you don't want to deal with matrix multiplication and you just want a simple rotation about an axis, you can transform the input values you care about with some trig:

```
float holdAngle = 45.0f;
float localAccelX = acceleration.x * cos(holdAngle) - acceleration.y * sin(holdAngle);

// adjust velocity based on current accelerometer acceleration
playerVelocity.x    = playerVelocity.x * deceleration + localAccelX  * sensitivity;

```

You can change the angle value to suit your liking. You also may have to substitute acceleration.z for acceleration.y (I'm not sure what direction those axes point in with your device).

---
Tags: cocos2d-iphone, objective-c
---


title: OpenGL Camera causes spatial distortion

text:
# Question
Title: OpenGL Camera causes spatial distortion
I'm trying to implement a 3D camera of the "Orbit around the origin" variety in a game engine I'm developing in order to learn about 3D graphics and game programming. I have a basic handle on the required math, and have implemented my own crude 3D math library and matrix stack (functionally similar to the one in OpenGL's compatibility profile). My first attempts at a camera failed miserably, until I decided that I should use quaternions to represent rotation. Once I'd done that, I had a camera that moved in the direction I expected it to at about the right speed and fairly smoothly, but there is an odd spatial distortion effect that I can't seem to get rid of. I have posted a brief video on YouTube showing exactly what is happening.

I honestly don't know what could be causing this issue, the magnitude of the distortion appears to reach a maximum at certain angles, but beyond that I'm not sure what I should be looking at. Right now my chief suspect is my quaternion math code, because the matrix stack appears to be behaving itself and if something was wrong with my matrix math code I would be having more serious issues than this.

I'm not sure what information or code I can provide that would be of any use, so I'll start with the code that handles quaternion math.

```
public class Quaternion {
private float w;
private float x;
private float y;
private float z;

public Quaternion(){
    this(1.0f,0.0f,0.0f,0.0f);
}

public Quaternion(float W, float X, float Y, float Z){
    w = W;
    x = X;
    y = Y;
    z = Z;
}

public void loadIdentity(){
    w = 1.0f;
    x = 0.0f;
    y = 0.0f;
    z = 0.0f;
}

public float magnitude(){
    //AKA the "norm"
    return (float) Math.sqrt(w*w + x*x + y*y + z*z);
}

public void qNormalize(){
    float mag = this.magnitude();
    w /= mag;
    x /= mag;
    y /= mag;
    z /= mag;
}

public void qMultiply(Quaternion q){
    this.qMultiply(q.w, q.x, q.y, q.z);
}

private void qMultiply(float w2, float x2, float y2, float z2){
    //Performs A*B, where this Quaternion is A
    this.w = w*w2 - x*x2 - y*y2 - z*z2;
    this.x = w*x2 + x*w2 + y*z2 - z*y2;
    this.y = w*y2 + y*w2 + z*x2 - x*z2;
    this.z = w*z2 + z*w2 + x*y2 - y*x2;
}

public float[] qMatrix(){
    //Return a 4x4 matrix representation of this Quaternion, column-major like OpenGL prefers
    float w2 = w*w;
    float x2 = x*x;
    float y2 = y*y;
    float z2 = z*z;

    if(Math.abs(w2+x2+y2+z2 - 1.0) >= 0.000001){
        this.qNormalize();
        return this.qMatrix();
    }

    return new float[]{
        1.0f - 2.0f*y2 -2.0f*z2, 2.0f*x*y + 2.0f*w*z, 2.0f*x*z - 2.0f*w*y, 0.0f,
        2.0f*x*y - 2.0f*w*z, 1.0f - 2.0f*x2 - 2.0f*z2, 2.0f*y*z + 2.0f*w*x,0.0f,
        2.0f*x*z - 2.0f*w*y, 2.0f*y*z + 2.0f*w*x, 1.0f - 2.0f*x2 - 2.0f*y2,0.0f,
        0.0f,0.0f,0.0f,1.0f
    };
}

public void qFromAA(float angle, float[] axis){
    //create a Quaternion from an axis-angle representation

    if(Vector.magnitude(axis) == 0.0f){
        this.loadIdentity();
        return;
    }

    float theta = angle/2.0f;
    axis = Vector.scale((float)Math.sin(theta), Vector.normalize(axis));

    w = (float)Math.cos(theta);
    x = axis[0];
    y = axis[1];
    z = axis[2];
}

public String toString(){
    return "w: "+w+"\tx: "+x+"\ty: "+y+"\tz: "+z+"\tmag: "+(x*x+y*y+z*z+w*w);
}

}

```

Any ideas about where I should start?

# Answer
> 3 votes
Are you sure your code for quaternion multiplication and your code for quaternion matrix converion is correct?

I had a typo in one of my formulas once that cost me nearly half a day.

btw... http://www.euclideanspace.com/maths/algebra/realNormedAlgebra/quaternions/index.htm is a great reference for quaternion math.

# Answer
> 3 votes
Your math is right, but you're doing an in-place multiply (which means you're writing to values you're using later in the multiplication)

```
private void qMultiply(float w2, float x2, float y2, float z2){
    //Performs A*B, where this Quaternion is A
    this.w = w*w2 - x*x2 - y*y2 - z*z2;
    this.x = w*x2 + x*w2 + y*z2 - z*y2;
    this.y = w*y2 + y*w2 + z*x2 - x*z2;
    this.z = w*z2 + z*w2 + x*y2 - y*x2;
}

```

Should be:

```
private void qMultiply(float w2, float x2, float y2, float z2){
    *this = Quaternion(
    w*w2 - x*x2 - y*y2 - z*z2,
    w*x2 + x*w2 + y*z2 - z*y2,
    w*y2 + y*w2 + z*x2 - x*z2,
    w*z2 + z*w2 + x*y2 - y*x2 );
}

```

Which will store the final values in temporary variables until the calculation is finished.

---
Tags: opengl, java, mathematics, camera, quaternion
---


# Question
Title: Is there any documentation comparing/contrasting C++ standard library implementations?
(This is not game programming per se, but I'm certain if I asked this on SO I'd get told not to prematurely optimize, even though history tells us every large game ends up worrying about these things.)

Is there a document anywhere that summarizes the differences in performance, and particularly memory usage, between different C++ standard library implementations? The details of some implementations are protected by NDA, but a comparison between even STLport vs. libstdc++ vs. libc++ vs. MSVC/Dinkumware (vs. EASTL?) seems like it would be immensely useful.

In particular I'm looking for answers to questions like:

* How much memory overhead is associated with the standard containers?
* What containers, if any, do dynamic allocations merely by being declared?
* Does std::string do copy-on-write? Short string optimization? Ropes?
* Does std::deque use a ring buffer or is it crap?

# Answer
> 6 votes
In case you don't find such a comparison chart, the alternative is to inject an own allocator to the STL classes in question and add some logging.

The implementation I tested (VC 8.0) uses no memory allocation just by declaring a string/vector/deque, but for it does list and map. The string has a short string optimization, since adding 3 chars didn't trigger an allocation. The output is added below the code.

```
// basic allocator implementation used from here
// http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <map>

template <class T> class my_allocator;

// specialize for void:
template <>
class my_allocator<void>
{
public:
    typedef void*       pointer;
    typedef const void* const_pointer;
    // reference to void members are impossible.
    typedef void value_type;
    template <class U>
    struct rebind
    {
        typedef my_allocator<U> other;
    };
};

#define LOG_ALLOC_SIZE(call, size)      std::cout << "  " << call << "  " << std::setw(2) << size << " byte" << std::endl

template <class T>
class my_allocator
{
public:
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;
    typedef T*        pointer;
    typedef const T*  const_pointer;
    typedef T&        reference;
    typedef const T&  const_reference;
    typedef T         value_type;
    template <class U>
    struct rebind
    {
        typedef my_allocator<U> other;
    };

    my_allocator() throw() : alloc() {}
    my_allocator(const my_allocator&b) throw() : alloc(b.alloc) {}

    template <class U> my_allocator(const my_allocator<U>&b) throw() : alloc(b.alloc) {}
    ~my_allocator() throw() {}

    pointer       address(reference x) const                    { return alloc.address(x); }
    const_pointer address(const_reference x) const              { return alloc.address(x); }

    pointer allocate(size_type s,
               my_allocator<void>::const_pointer hint = 0)      { LOG_ALLOC_SIZE("my_allocator::allocate  ", s * sizeof(T)); return alloc.allocate(s, hint); }
    void deallocate(pointer p, size_type n)                     { LOG_ALLOC_SIZE("my_allocator::deallocate", n * sizeof(T)); alloc.deallocate(p, n); }

    size_type max_size() const throw()                          { return alloc.max_size(); }

    void construct(pointer p, const T& val)                     { alloc.construct(p, val); }
    void destroy(pointer p)                                     { alloc.destroy(p); }

    std::allocator<T> alloc;
};

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

    {
        typedef std::basic_string<char, std::char_traits<char>, my_allocator<char> > my_string;

        std::cout << "===============================================" << std::endl;
        std::cout << "my_string ctor start" << std::endl;
        my_string test;
        std::cout << "my_string ctor end" << std::endl;
        std::cout << "my_string add 3 chars" << std::endl;
        test = "abc";
        std::cout << "my_string add a huge number of chars chars" << std::endl;
        test += "d df uodfug ondusgp idugnösndögs ifdögsdoiug ösodifugnösdiuödofu odsugöodiu niu od unoudö n nodsu nosfdi un abc";
        std::cout << "my_string copy" << std::endl;
        my_string copy = test;
        std::cout << "my_string copy on write test" << std::endl;
        copy[3] = 'X';
        std::cout << "my_string dtors start" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "vector ctor start" << std::endl;
        std::vector<int, my_allocator<int> > v;
        std::cout << "vector ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            v.push_back(i);
        }
        std::cout << "vector dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "deque ctor start" << std::endl;
        std::deque<int, my_allocator<int> > d;
        std::cout << "deque ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "deque insert start" << std::endl;
            d.push_back(i);
            std::cout << "deque insert end" << std::endl;
        }
        std::cout << "deque dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "list ctor start" << std::endl;
        std::list<int, my_allocator<int> > l;
        std::cout << "list ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "list insert start" << std::endl;
            l.push_back(i);
            std::cout << "list insert end" << std::endl;
        }
        std::cout << "list dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "map ctor start" << std::endl;
        std::map<int, float, std::less<int>, my_allocator<std::pair<const int, float> > > m;
        std::cout << "map ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "map insert start" << std::endl;
            std::pair<int, float> a(i, (float)i);
            m.insert(a);
            std::cout << "map insert end" << std::endl;
        }
        std::cout << "map dtor starts" << std::endl;
    }

    return 0;
}

```

So far VC8 and STLPort 5.2 tested, here is the comparison (included in test: string, vector, deque, list, map)

```
                    Allocation on declare   Overhead List Node      Overhead Map Node

VC8                 map, list               8 Byte                  16 Byte
STLPort 5.2 (VC8)   deque                   8 Byte                  16 Byte
Paulhodge's EASTL   (none)                  8 Byte                  16 Byte

```

VC8 output string/vector/deque/list/map:

```
===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
my_string add a huge number of chars chars
  my_allocator::allocate    128 byte
my_string copy
  my_allocator::allocate    128 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  128 byte
  my_allocator::deallocate  128 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    12 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate  12 byte
  my_allocator::allocate    24 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  24 byte

===============================================
deque ctor start
deque ctor end
deque insert start
  my_allocator::allocate    32 byte
  my_allocator::allocate    16 byte
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
  my_allocator::allocate    16 byte
deque insert end
deque dtor starts
  my_allocator::deallocate  16 byte
  my_allocator::deallocate  16 byte
  my_allocator::deallocate  32 byte

===============================================
list ctor start
  my_allocator::allocate    12 byte
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
  my_allocator::allocate    24 byte
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

```

STLPort 5.2. output compiled with VC8

```
===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
my_string add a huge number of chars chars
  my_allocator::allocate    115 byte
my_string copy
  my_allocator::allocate    115 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  115 byte
  my_allocator::deallocate  115 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::deallocate   0 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    32 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  32 byte

===============================================
deque ctor start
  my_allocator::allocate    32 byte
  my_allocator::allocate    128 byte
deque ctor end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque dtor starts
  my_allocator::deallocate  128 byte
  my_allocator::deallocate  32 byte

===============================================
list ctor start
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

```

EASTL results, no deque available

```
===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
  my_allocator::allocate     9 byte
my_string add a huge number of chars chars
  my_allocator::allocate    115 byte
  my_allocator::deallocate   9 byte
my_string copy
  my_allocator::allocate    115 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  115 byte
  my_allocator::deallocate  115 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    32 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  32 byte

===============================================
list ctor start
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

```

# Answer
> 8 votes
`std::string` does not do copy on write. CoW used to be an optimization, but as soon as multiple threads enter the picture it's beyond a pessimisation- it can slow the code by massive factors. It's so bad that the C++0x Standard actively bans it as an implementation strategy. Not just that, but the permissiveness of `std::string` with dishing out mutable iterators and character references mean that "write" for `std::string` entails almost every operation.

Short string optimization is about 6 characters, I believe, or something in that region. Ropes are not allowed- `std::string` must store contiguous memory for the `c_str()` function. Technically, you could maintain both a contiguous string and a rope in the same class, but nobody ever did it. Moreover, from what I know of ropes, making them thread-safe to manipulate would be incredibly slow- maybe as bad or worse than CoW.

No containers do memory allocation by being declared in modern STLs. Node-based containers like list and map used to do so but now they have an embedded end optimization and don't need it. It's common to perform an optimization called "swaptimization" where you swap with an empty container. Consider:

```
std::vector<std::string> MahFunction();
int main() {
    std::vector<std::string> MahVariable;
    MahFunction().swap(MahVariable);
}

```

Of course, in C++0x this is redundant, but in C++03 then when this was commonly used, if MahVariable allocates memory on declaration then it reduces the effectiveness. I know for a fact that this was used for faster reallocations of containers like `vector` in the MSVC9 STL which removed the need to copy the elements.

`deque` uses something referred to as an unrolled linked list. It's basically a list of arrays, usually fixed-size in-node. As such, for most uses, it retains the benefits of both data structures- contiguous access and amortized O(1) removal and being able to add to both front and back *and* better iterator invalidation than `vector`. `deque` can never be implemented by vector because of it's algorithmic complexity and iterator invalidation guarantees.

How much memory overhead is associated? Well, honestly, that's a bit of a worthless question to ask. The STL containers are designed to be efficient, and if you were to replicate their functionality, you'd either end up with something that performs worse or in the same spot again. By knowing their underlying data structures, you can know the memory overhead they use, give or take, and it'll only be more than that for a good reason, such as small string optimization.

# Answer
> 2 votes
> The question isn't so much "Please do this comparison" as "where is a resource for this comparison"

If that's really your question (which is most assuredly *not* what you said in your actual question text, which ended in 4 questions, none of which were asking where you might find a resource), then the answer is simply:

There isn't one.

The majority of C++ programmers don't have to care that much about the overhead of standard library structures, cache performance of them (which is *highly* compiler dependent anyway), or that sort of thing. Not to mention, you usually don't get to pick your standard library implementation; you use what comes with your compiler. So even if it does some unpleasant things, the options for alternatives are limited.

There are of course programmers who do care about this sort of thing. But they all swore off using the standard library a long time ago.

So you have one group of programmers who simply don't care. And another group of programmers who would care if they were using it, but since they aren't using it, they don't care. Since nobody cares about it, there is no real information about this sort of thing. There are informal patches of information here and there (Effective C++ has a section on std::string implementations and the vast differences among them), but nothing comprehensive. And certainly nothing kept up-to-date.

---
Tags: c++, performance, memory-efficiency
---


# Question
Title: Need help with collision detection/resolution in a 2D simulation of 'worm-like' creatures
(originally posted this on regular stack overflow, somebody pointed this forum out :-) )

Hi there,

I'm implementing a physics engine for the simulation of worm-like creatures. Problem is, is that they're able to swim over each other and occupy the same point in space. So you have some idea of the environment, I provide a video here: http://www.box.net/shared/mlddkslszbxd59cfdhpc

So what I need to do is incorporate a collision detection and resolution algorithm that would overcome this. For the detection part, I've been utilising bounding circles; each worm is given an outer coarse circle which if crossed then triggers detection around smaller fine grain detection circles as placed around each body segment.

That bit is relatively easy. The more difficult bit is to decide what to do given a collision. My problem is how to derive and correctly set the velocities and forces of the point masses after a collision has taken place.

Just in case its not entirely obvious, each worm is made out of springs and point masses. Each body segment of a worm assumes a rectangular shape at rest with 4 point masses and 6 springs (since there are also two diagonal springs).

Now it was suggested over on regular stack overflow that I implement an elastic collision by summing the momentum of worm A and the momentum of worm B (when they collide). The way I do this is on a body segment by body segment basis: if two body segments from two different worms are close enough (i.e., colliding), then I sum the momentum of each and divide the result by 2. This yields a new velocity value which I then apply to the velocity of each body segment. This is meant to have the effect of 'springing' the colliding body segments away from each other.

However, I don't think I'm implementing it correctly. The issues are: when worm A hits worm B, if they are both swimming strongly enough, they both still swim through each other albeit at a slower pace. An example of this is shown in this video here: http://www.box.net/shared/sankz3i7xeenilhzhqfo

The second issue is that if two worms are within collision range and worm A swims away from worm B, then worm A proceeds to pull worm B along with it although at a slower speed than normal un-hindered swimming.

I'm really not sure how to go about this. I've read about requiring the setting of angular velocity for two colliding bodies but I'm not sure whether this only applies to solid bodies or not..An elastic collision seems the most sensible given that I'm using a spring based model.

If anyone can help, I'd greatly appreciate it

Thanks,

Ben.

# Answer
> 1 votes
Solved using a slightly modified version of the code found here:

Why do objects interpenetrate in this simple collision solver?

Cheers,

Ben.

---
Tags: collision-detection, physics, physics-engine
---


title: Multiple Render Targets not saving data

text:
# Question
Title: Multiple Render Targets not saving data
I originally posted this question on stack overflow, but realised it might be better here. The original question can be found here

I'm using SlimDX, targeting DirectX 11 with shader model 4. I have a pixel shader "preProc" which processes my vertices and saves three textures of data. One for per-pixel normals, one for per-pixel position data and one for color (which I'm currently setting as black).

I then later use these textures in a postprocessing shader in order to implement Screen Space Ambient Occlusion, however it seems none of the data is getting saved in the first shader.

Here's my pixel shader:

```
PS_OUT PS( PS_IN input )
{
    PS_OUT output;
    output.col = float4(0,0,0,0);
    output.norm = float4(input.norm,1);
    output.pos = input.pos;
    return output;
}

```

which outputs the following struct:

```
struct PS_OUT
{
    float4 col : SV_TARGET0;
    float4 norm : SV_TARGET1;
    float4 pos : SV_TARGET2;
};

```

and takes the following struct for input:

```
struct PS_IN
{
    float4 pos : SV_POSITION;
    float2 tex : TEXCOORD0;
    float3 norm : TEXCOORD1;
};

```

My post processing shader simply outputs the colour I set in my preShader, which should be black. However when I run the code I get a light blue, which is the colour I reset my render targets to when I clear them. If I change the pixelshader to instead sample the randomTex texture (which my code previously loaded from a file and is not from a render target) everything is rendered fine, so I am confident it is not my post processing shader.

In case it's my slimDX code that's failing here's what I do:

Creating my textures, shaderresourvecviews and rendertargetviews:

```
Texture2DDescription textureDescription = new Texture2DDescription()
                {
                    Width=texWidth,
                    Height=texHeight,
                    MipLevels=1,
                    ArraySize=3,
                    Format=SlimDX.DXGI.Format.R32G32B32A32_Float,
                    SampleDescription = new SlimDX.DXGI.SampleDescription(1,0),
                    BindFlags = BindFlags.RenderTarget | BindFlags.ShaderResource,
                    CpuAccessFlags= CpuAccessFlags.None,
                    OptionFlags = ResourceOptionFlags.None,
                    Usage= ResourceUsage.Default,
                };
            texture = new Texture2D(device, textureDescription);

            renderTargetView = new RenderTargetView[3];
            shaderResourceView = new ShaderResourceView[3];

            for (int i = 0; i < 3; i++)
            {
                RenderTargetViewDescription renderTargetViewDescription = new RenderTargetViewDescription()
                    {
                        Format = textureDescription.Format,
                        Dimension = RenderTargetViewDimension.Texture2D,
                        MipSlice = 0,
                    };

                renderTargetView[i] = new RenderTargetView(device, texture, renderTargetViewDescription);

                ShaderResourceViewDescription shaderResourceViewDescription = new ShaderResourceViewDescription()
                    {
                        Format = textureDescription.Format,
                        Dimension = ShaderResourceViewDimension.Texture2D,
                        MostDetailedMip = 0,
                        MipLevels = 1
                    };

                shaderResourceView[i] = new ShaderResourceView(device, texture, shaderResourceViewDescription);
            }

```

Rendering to my multiple render targets:

```
private void renderToTexture(Shader shader)
    {
        //set the vertex and pixel shaders
        context.VertexShader.Set(shader.VertexShader);
        context.PixelShader.Set(shader.PixelShader);

        //send texture data and a linear sampler to the shader
        context.PixelShader.SetShaderResource(texture, 0);
        context.PixelShader.SetSampler(samplerState, 0);

        //set the input assembler
        SetInputAssembler(shader);

        //reset the camera's constant buffer
        camera.ResetConstantBuffer();

        //set the render targets to the textures we will render to
        context.OutputMerger.SetTargets(depthStencilView, renderTargetViews);
        //clear the render targets and depth stencil
        foreach (RenderTargetView view in renderTargetViews)
        {
             context.ClearRenderTargetView(view, color);
        }
        context.ClearDepthStencilView(depthStencilView, DepthStencilClearFlags.Depth, 1.0f, 0);
            //draw the scene
            DrawScene();

        }

```

and then the function when I render my postProcessing shader to the screen:

```
private void renderTexture(Shader shader)
        {
            //get a single quad to be the screen we render
            Mesh mesh = CreateScreenFace();
            //set vertex and pixel shaders
            context.VertexShader.Set(shader.VertexShader);
            context.PixelShader.Set(shader.PixelShader);
            //set the input assembler
            SetInputAssembler(shader);
            //point the render target to the screen
            context.OutputMerger.SetTargets(depthStencil, renderTarget);
            //send the rendered textures and a linear sampler to the shader
                context.PixelShader.SetShaderResource(renderTargetViews[0], 1);
            context.PixelShader.SetShaderResource(renderTargetViews[1], 2);
            context.PixelShader.SetShaderResource(renderTargetViews[2], 3);
            context.PixelShader.SetShaderResource(random, 4);
            context.PixelShader.SetSampler(samplerState, 0);
            //clear the render targets and depth stencils
            context.ClearRenderTargetView(renderTarget, new Color4(0.52734375f, 0.8046875f, 0.9765625f));
            context.ClearDepthStencilView(depthStencil, DepthStencilClearFlags.Depth, 1, 0);
            //set the vertex and index buffers from the quad
            context.InputAssembler.SetVertexBuffers(0, new VertexBufferBinding(mesh.VertexBuffer, Marshal.SizeOf(typeof(Vertex)), 0));
            context.InputAssembler.SetIndexBuffer(mesh.IndexBuffer, Format.R16_UInt, 0);
            //draw the quad
            context.DrawIndexed(mesh.indices, 0, 0);
            //dispose of the buffers
            mesh.VertexBuffer.Dispose();
            mesh.IndexBuffer.Dispose();
        }

```

This is the PIX function call output for a single frame of the current run:

```
Frame 40
//setup
<0x06BDA1D8> ID3D11DeviceContext::ClearRenderTargetView(0x06B66190, 0x0028F068)
<0x06BDA1D8> ID3D11DeviceContext::ClearDepthStencilView(0x06B66138, 1, 1.000f, 0)
<0x0059FF78> ID3D11Device::CreateBuffer(0x0028F010, 0x0028EFF8, 0x0028F00C --> 0x06BF8EE0)
CreateObject(D3D11 Buffer, 0x06BF8EE0)
<0x06BDA1D8> ID3D11DeviceContext::PSSetConstantBuffers(0, 1, 0x0028F084 --> { 0x06BF8EE0 })
<0x0059FF78> ID3D11Device::CreateBuffer(0x0F8DEB58, 0x0F8DEB40, 0x0F8DEB54 --> 0x06BF8F68)
CreateObject(D3D11 Buffer, 0x06BF8F68)
<0x0059FF78> ID3D11Device::CreateBuffer(0x0F70EAD8, 0x0F70EAC0, 0x0F70EAD4 --> 0x06BF8FF0)
CreateObject(D3D11 Buffer, 0x06BF8FF0)
<0x0059FF78> ID3D11Device::CreateBuffer(0x0FAAE9A8, 0x0FAAE990, 0x0FAAE9A4 --> 0x06BF9078)
CreateObject(D3D11 Buffer, 0x06BF9078)
<0x0059FF78> ID3D11Device::GetImmediateContext(0x06BDA1D8 --> 0x5BA8A8D8)
<0x0059FF78> ID3D11Device::CreateBuffer(0x0F8DEB58, 0x0F8DEB40, 0x0F8DEB54 --> 0x06BF9100)
CreateObject(D3D11 Buffer, 0x06BF9100)
<0x0059FF78> ID3D11Device::CreateBuffer(0x0F70EAD8, 0x0F70EAC0, 0x0F70EAD4 --> 0x06BF9188)
CreateObject(D3D11 Buffer, 0x06BF9188)
<0x06BDA1D8> ID3D11DeviceContext::Release()
<0x06BDA1D8> ID3D11DeviceContext::UpdateSubresource(0x06B59270, 0, NULL, 0x06287FA0, 0, 0)
<0x0059FF78> ID3D11Device::CreateBuffer(0x0FAAE9A8, 0x0FAAE990, 0x0FAAE9A4 --> 0x06BF9210)
CreateObject(D3D11 Buffer, 0x06BF9210)
<0x06BDA1D8> ID3D11DeviceContext::VSSetShader(0x06B66298, NULL, 0)
<0x0059FF78> ID3D11Device::CreateBuffer(0x0FC0E978, 0x0FC0E960, 0x0FC0E974 --> 0x06BF9298)
CreateObject(D3D11 Buffer, 0x06BF9298)
<0x0059FF78> ID3D11Device::CreateBuffer(0x0FE8EDE8, 0x0FE8EDD0, 0x0FE8EDE4 --> 0x06BF9320)
CreateObject(D3D11 Buffer, 0x06BF9320)
<0x06BDA1D8> ID3D11DeviceContext::PSSetShader(0x06B666F8, NULL, 0)
<0x0059FF78> ID3D11Device::CreateBuffer(0x0FC0E978, 0x0FC0E960, 0x0FC0E974 --> 0x06BF93A8)
CreateObject(D3D11 Buffer, 0x06BF93A8)
<0x0059FF78> ID3D11Device::CreateBuffer(0x0FE8EDE8, 0x0FE8EDD0, 0x0FE8EDE4 --> 0x06BF9430)
CreateObject(D3D11 Buffer, 0x06BF9430)
<0x0059FF78> ID3D11Device::CreateInputLayout(0x0028EBE0, 3, 0x06286CB8, 152, 0x0028EBD8 --> 0x06BF9D68)
CreateObject(D3D11 Input Layout, 0x06BF9D68)
<0x06BDA1D8> ID3D11DeviceContext::IASetInputLayout(0x06BF9D68)
<0x06BDA1D8> ID3D11DeviceContext::IASetPrimitiveTopology(D3D11_PRIMITIVE_TOPOLOGY_TRIANGLELIST)
<0x0059FF78> ID3D11Device::GetImmediateContext(0x06BDA1D8 --> 0x5BA8A8D8)
<0x06BDA1D8> ID3D11DeviceContext::Release()
<0x06BDA1D8> ID3D11DeviceContext::VSSetConstantBuffers(0, 1, 0x0028F024 --> { 0x06B59270 })
<0x06BDA1D8> ID3D11DeviceContext::OMSetRenderTargets(3, 0x0028F004 --> { 0x06B65708, 0x06B657B8, 0x06B582E0 }, 0x06B66138)
<0x06BDA1D8> ID3D11DeviceContext::ClearRenderTargetView(0x06B65708, 0x0028EFEC)
<0x06BDA1D8> ID3D11DeviceContext::ClearRenderTargetView(0x06B657B8, 0x0028EFEC)
<0x06BDA1D8> ID3D11DeviceContext::ClearRenderTargetView(0x06B582E0, 0x0028EFEC)
<0x06BDA1D8> ID3D11DeviceContext::ClearDepthStencilView(0x06B66138, 1, 1.000f, 0)
//draw scene for preproc shader (this should output the three render targets)
//DRAW CALLS HIDDEN
<0x0059FF78> ID3D11Device::CreateBuffer(0x0028EE04, 0x0028EDEC, 0x0028EE00 --> 0x06BF94B8)
CreateObject(D3D11 Buffer, 0x06BF94B8)
<0x0059FF78> ID3D11Device::CreateBuffer(0x0028EE04, 0x0028EDEC, 0x0028EE00 --> 0x06BF9540)
CreateObject(D3D11 Buffer, 0x06BF9540)
<0x06BDA1D8> ID3D11DeviceContext::VSSetShader(0x06B66BB8, NULL, 0)
<0x06BDA1D8> ID3D11DeviceContext::PSSetShader(0x06B66E50, NULL, 0)
<0x0059FF78> ID3D11Device::CreateInputLayout(0x0028EB64, 3, 0x05E988E0, 120, 0x0028EB5C --> 0x06BF9E28)
CreateObject(D3D11 Input Layout, 0x06BF9E28)
<0x06BDA1D8> ID3D11DeviceContext::IASetInputLayout(0x06BF9E28)
<0x06BDA1D8> ID3D11DeviceContext::IASetPrimitiveTopology(D3D11_PRIMITIVE_TOPOLOGY_TRIANGLELIST)
<0x06BDA1D8> ID3D11DeviceContext::OMSetRenderTargets(1, 0x0028EFC0 --> { 0x06B66190 }, 0x06B66138)
<0x06BDA1D8> ID3D11DeviceContext::PSSetShaderResources(1, 3, 0x0028EF3C --> { 0x06B65760, 0x06B58288, 0x06B58338 })
<0x06BDA1D8> ID3D11DeviceContext::PSSetShaderResources(4, 1, 0x0028EFC0 --> { 0x06B66FA0 })
<0x06BDA1D8> ID3D11DeviceContext::ClearRenderTargetView(0x06B66190, 0x0028EFA4)
<0x06BDA1D8> ID3D11DeviceContext::ClearDepthStencilView(0x06B66138, 1, 1.000f, 0)
<0x06BDA1D8> ID3D11DeviceContext::IASetVertexBuffers(0, 1, 0x0028EFAC --> { 0x06BF94B8 }, 0x0028EFB0, 0x0028EFB4)
<0x06BDA1D8> ID3D11DeviceContext::IASetIndexBuffer(0x06BF9540, DXGI_FORMAT_R16_UINT, 0)
//draw quad for post proc shader. This shader takes the three textures in, as well as a random texture, which is added in the second PSSetShaderResources call. The random texture outputs fine.
<0x06BDA1D8> ID3D11DeviceContext::DrawIndexed(6, 0, 0)
<0x06BF94B8> ID3D11Buffer::Release()
<0x06BF9540> ID3D11Buffer::Release()
<0x06B65B00> IDXGISwapChain::Present(0, 0)

```

> EDIT: I've been doing some reading and perhaps I need to deallocate the textures as render targets after the preProc pass before I pass them in as ShaderResourceViews to my postProcess shader. I assumed calling context.OutputMerger.SetTargets() would deallocate all of the currently assigned render targets and then assign only the render targets specified in the function's parameters. If this isn't the case (I can't yet be sure if it is or isn't), then how would I go about unassigning the render targets in SlimDX?
>
> EDIT2: Ah, according to this MSDN page, calling OutputMerger.SetRenderTargets() *"overrides all bounded render targets and the depth stencil target regardless of the number of render targets in ppRenderTargetViews."* so all of my render targets are getting deallocated automatically when I tell the OutputMerger to render to the screen. This leaves me back to square one.

# Answer
> 1 votes
Fixed it by discovering just how silly I am.

When I create my rendertarget I create a Texture2DArray but I'm treating it like an array of Texture2D objects, instead of one object. I have since altered my code to use an array of Texture2D objects and it works very well.

---
Tags: textures, shaders, rendering, directx11, slimdx
---


# Question
Title: 2D Physics Engine for Platform Games - Riding on a Platform
I have a number of questions relating to using a 2D physics engine in a platform game, but one main one that I'm grappling with at the moment. I managed to somewhat integrate the Physics2D.Net engine into a Scrolling Game Development Kit 2 project. I'm very pleased with the performance and the realism of the physics. However, I've lost some things that my original SGDK2 physics engine (oriented more specifically to platform games) made easier:

1. Riding on a platform is very difficult now. This is my main question. It's not difficult to implement, but difficult to play. Assuming I even do manage to get the player onto a platform (which is hard enough in itself), as soon as the platform moves, the player falls off because there's not enough friction between the player and the platform or something. Do I just need to tweak things like friction, inertia, linear velocity dampening and the like to make it easier to ride on a platform, or is there something fundamentally difficult about riding on platform is the "real" world? I've tried reducing the force applied to the platform that makes it move (so it would allow more time for the rider to match the platform's velocity), but then that's not enough force to keep the rider aloft, and the platform sinks to the ground. I'm simply applying forces to move the platform.
2. What is the best way to stop the platform from rotating? I've tried setting the Angular momentum and the angular position to 0 on each frame, but this can result in little twitches that cause anything on the platform to spring into the air a bit, just long enough to fall off.
3. Running along the ground: How do most platform games with realistic 2D physics implement the player? My player is currently a square, but will often tumble and spring into the air due to friction hitting one of the corners. My guess is that the player should be a circle and always drawn upright. Is this standard practice, or is there another way? If I use a circle I expect that riding a platform will be even more difficult! The player will roll right off. I'm thinking of Little Big Planet, which also seemed to keep the player on the ground pretty well. Do I just have to put a lot of velocity damping on the player, or something like that, if I want to keep them grounded too?
4. Since SGDK2 is a tile-based engine/IDE, I have writen code that analyzes all the shapes of the terrain/tiles and turns them into physics bodies with infinite mass (merging them horizontally, but not vertically where appropriate; merging two directions was too difficult for me to figure out because I couldn't figure out how to trace and represent the hole in a torus-like formation). Is that a good way for a platform game to implement something for the sprites to interact with to represent the solid ground? Am I better off turning each tile into a physics body (few simple shapes, many bodies and internal surfaces between tiles), or merging them as I am doing (fewer bodies, but more shapes that are more complex)?
5. I'm having a hard time figuring out the optimal vertex subdivision level and grid spacing to use. I don't really understand these concepts and documentation on Pysics2D.Net is sparse to non-existent as far as I can tell. I am generally subdividing to about 6 and using a grid spacing of about the same. My sprites and tiles are mostly 32x32 units (pixels), all square for the moment.

# Answer
> 2 votes
1) Friction is the correct solution. It's what keeps you on a moving thing in real life. Once the person has accelerated to the same speed as the platform, inertia will keep them on it. If a platform moves down and sideways at the same time, a player might still appear to 'float off' if they don't fall fast enough to keep up with the platform.

1.5 and 2) The platform should (probably) be a kinematic body. As one, it won't respond to collisions, so it will never rotate, and the player won't be able to push it to the ground. If your physics library doesn't support kinematic bodies, it might have angular inertia, which can be set to an absurdly high value.

3) I've never done this with tiles, but I have with worlds that had little corners the player could get stuck on. My solution was to make the player out of two shapes, a circular 'foot' and a rectangular body. The round foot slid easily over small corners and up slopes.

4) You're probably better off with fewer, larger shapes. Depending on the library, it may perform better with slightly more convex shapes rather than fewer concave ones. A torus is impossible if you use only convex shapes.

5) This sounds like a value you'll have to experiment with. Not knowing specifics of the library, I would guess that a smaller value trades performance for accuracy.

---
Tags: 2d, c#, physics, game-mechanics
---


# Question
Title: Why are my objects becoming permanently stuck to walls using Box2D?
I setup a simple simulation environment something like billiards. There are four circle balls (dynamic) and four box walls (static).

Simulation works... except one thing. Sometimes when a ball rest against a wall, it sticks to the wall eternally. The other balls hits the stuck ball so many times, but the ball never wants to separated with the wall. The only situation where the ball will become unstuck from the wall is another if another ball is rests against the same wall such that it hits the already-stuck ball.

Why does this situation occur? How can I avoid it?

# Answer
Try changing b2\_velocityThreshold variable in b2Settings.h - this setting keeps the simulation stable by ignoring tiny bounces but that's probably not what you want in a billiards game.
> 3 votes

# Answer
Most likely, you have collision resolution code that reverses (reflects) the direction that the ball is going when it hits the wall. If the ball's position penetrates the wall slightly and stays there until the next frame, it may sense a collision again be reversing direction again (and each frame thereafter) and stay stuck.

Typically, if you sense a collision with the wall, in addition to reflecting the ball's direction, you should also make sure you position it on the side where it won't sense a collision next frame.
> 5 votes

---
Tags: physics, box2d
---


# Question
Title: Problem in blitting a clean, crisp sprite
I am having a bit of a tooling problem...and I am unsure of how to solve it.

I am currently using PyGame to try and write a simple Minesweeper clone, except my sprites that I made are hexagon based and therefore have diagonal lines.

I drew up a nice, clean, crisp vector sprite set which looks very nice in Inkscape, however once I export it everything goes to hell. I'm going to outline what I've done below and hopefully somebody here can set me straight :D

**Disclaimer**: Unfortunately I'm behind a proxy and cannot provide screenshots at the moment..I'll do my best to describe.

If I attempt to use a color key (`0xFF00FF`), then when I set the color key in PyGame I get a bunch of jagged pink edges along my sprite. I believe this could be an anti-aliasing issue with Inkscape, but unfortunately my Googling didn't turn up a way to disable it.

If I import my PNG into Photoshop or the Gimp and delete the background, then I run into an issue where the background appears to be black when running the game. I have tried to follow the instructions I saw on SO, but to no avail.

I am open to suggestions, but at this point I'm debating importing another library which can handle SVG graphics, in order to keep my clean, crisp diagonal lines.

# Answer
> 5 votes
Try this in Photoshop:

1. Make a new document.
2. Make a new layer. It will be transparent.
3. Delete the background layer.
4. Your document should be all transparent now. It will look like a checkerboard.
5. Draw the hexagon onto that transparent layer.
6. Save this as a 24-bit PNG with transparency.

Now bring that into PyGame. You may need to do some `convert_alpha()` thing to enable the alpha channel. That should give you correct anti-aliased transparency.

# Answer
> 1 votes
For your pink halo-ing, the issue is exactly what you described: anti-aliasing. If you have Photoshop, just create the hexagon with two layers, one with all pink (0xFF00FF) and another with the hexagon. Make sure when you create the hexagon all feathering and anti-aliasing settings are set to zero for all the tools you use, and all brushes are set to 100% hardness. Save as a PNG.

For best results, stick to the pencil and paint bucket tools.

# Answer
> 1 votes
While I would personally resort to munificents solution, here's a way to get a crisp sprite using ImageMagick.

Use the tool of your choice to draw your sprite. Export it as PNG with alpha channel. Your exported image might look like this:

Then you can use ImageMagick to convert this image to a sprite with magenta background using the following command:

```
convert sourceFile.png -channel alpha -threshold 50% -background "#ff00ff" -flatten destFile.png

```

The resulting file should look like this:

You can tweak the resulting "alpha" by changing the threshold parameter. And since this is ImageMagick, you can also easily batch convert lots of sprites.

---
Tags: python, pygame, antialiasing
---


# Question
Title: How do I get beautiful small text in XNA without using external libraries?
In XNA, the spritefont technology is horrible. Nuclex does the job so much better, but I don't want to have any external references, and I'm nearly done with my game.

When using fonts like Sansation or Quicksand, it looks terrible in smaller sizes of the fonts. It's so bad!

Is there a known workaround for this? I tried setting the fontsizes to extremely high, and then scaling them down in the spritebatch with no luck.

# Answer
> 12 votes
XNA lets you import a texture as a spritefont. You can probably get better hinting and anti-aliasing in your font if you lay each character out manually in a good image editing program, rather than relying on the sprite sheet that XNA generates.

# Answer
> 14 votes
The XNA sprite font processor uses DXT3 compression that does not work well with the new premultiplied alpha in XNA 4.0. Hence the blocky look of the text.

The Nuclex sprite font processor outputs exactly the same data, except that the internal `Texture2D` that holds the font bitmap data is not compressed - so it has no quality issues.

Because the data from the Nuclex processor is in the same format, the XNA `SpriteFont` reader can read it, and **you do not need to include any Nuclex libraries for distribution with your game.**

(It also conveniently allows you to use the same XML format as XNA's native sprite font definitions.)

That being said: there's nothing wrong with bundling external libraries with your game. It's not like they get installed on your system or anything. (You could even go so far as to merge the two assemblies).

And the same thing goes for the code (if you're worried about version control, for example). You can just put `Nuclex.Fonts.Content.TrueTypeImporter.dll` in with your source code. It's actually not a big deal.

# Answer
> 9 votes
You could use pixel fonts:

When you use a pixel font at the font size it was designed for (or a whole multiple of it, e.g. 2x, 3x, 4x) you are guaranteed pixel-perfect text that requires no anti-aliasing. This means you never have to deal with the terrible anti-aliasing which makes XNA's sprite fonts so bad and Nuclex so much better. (This article examines that problem and compares them)

---
Tags: xna, fonts
---


title: SFXR-Like Tool for Speech

text:
# Question
Title: SFXR-Like Tool for Speech
Sfxr (and also Bfxr) is a great tool for generating sound-effects for games. Is there something like this for speech synthesis?

Not every game development tool and platform has a speech synthesis engine, and it would be great to at least get some decent-sounding placeholders in place to see how the usability/experience plays out. Even better if the results are tweakable, like sfxr.

I'm looking for something I can at least **run on windows,** though preferably (like Bfxr) I would like a **web application** that I can just run out of my browser.

# Answer
> 3 votes
Festival has a free software license and one set of voice samples for American English that is also free. It has C++ and Java APIs as well as a Lisp-like command interface.

Flite is based on the same principles and is mostly compatible; it has only a C interface and is considerably lighter.

---
Tags: tools, sound
---


title: How granular should entity states be?

text:
# Question
Title: How granular should entity states be?
I'm writing a component-based entity system and one of the components is the entity's state, which dictates how it reacts to game events. In case anyone has experience with implementing states, how granular should they be?

To give you an idea about how granular they are in my case, I have a `WalkingLeft` state and a `WalkingRight` state (as opposed to simply a `Walking` state) and I fear that they might be too granular. What do you think?

# Answer
It should be as granular as you **need** the entities to be.

That means that if you don't ever have a case where an entity can walk to the left, but not to the right, you shouldn't split it up and just keep the "walking" component since anything else will just add unnecessary overhead.

And don't worry about how to find out what you're going to need in the future: The advantage of an component based model is that you can very easily exchange and split up small parts.

Always keep in mind: These kinds of architectures are not there to make your code look prettier, but to help you achieve what you want faster and more easily, plus less bug-prone. Splitting up walking to walking left and walking right if you don't ever need it has neither of the qualities above.
> 2 votes

# Answer
> I'm writing a component-based entity system and one of the components is the entity's state

You have missed the point. In a component based system, the entity's state is parceled and distributed among different components, each of which has a well-defined and limited data storage and processing task. There is not one component that is "the state component".

As to how many you need, the only correct answer is exactly as many as you need to implement your game logic.
> 4 votes

---
Tags: state, entity-system
---


# Question
Title: Algorithm for spreading labels in a visually appealing and intuitive way
## Short version

> Is there a design pattern for distributing vehicle labels in a non-overlapping fashion, placing them as close as possible to the vehicle they refer to? If not, is any of the method I suggest viable? How would you implement this yourself?

## Extended version

In the game I'm writing I have a bird-eye vision of my airborne vehicles. I also have next to each of the vehicles a small label with key-data about the vehicle. This is an actual screenshot:

Now, since the vehicles could be flying at different altitudes, their icons could overlap. However I would like to never have their labels overlapping (or a label from vehicle 'A' overlap the icon of vehicle 'B').

Currently, I can detect collisions between sprites and **I simply push away the offending label in a direction opposite to the otherwise-overlapped sprite**. This works in most situations, but when the airspace get crowded, **the label can get pushed very far away** from its vehicle, even if there was an alternate "smarter" alternative. For example I get:

```
  B - label
A -----------label
  C - label

```

where it would be better (= label closer to the vehicle) to get:

```
          B - label
label - A
          C - label

```

**EDIT:** It also has to be considered that beside the overlapping vehicles case, there might be other configurations in which vehicles'labels could overlap (the ASCII-art examples show for example three very close vehicles in which the label of `A` would overlap the icon of `B` and `C`).

**I have two ideas on how to improve the present situation, but before spending time implementing them, I thought to turn to the community for advice (after all it seems like a "common enough problem" that a design pattern for it could exist).**

For what it's worth, here's the two ideas I was thinking to:

**Slot-isation of label space**

In this scenario I would divide all the screen into "slots" for the labels. Then, each vehicle would always have its label placed in the closest empty one (empty = no other sprites at that location.

**Spiralling search**

From the location of the vehicle on the screen, I would try to place the label at increasing angles and then at increasing radiuses, until a non-overlapping location is found. Something down the line of:

```
try 0°, 10px
try 10°, 10px
try 20°, 10px
...
try 350°, 10px
try 0°, 20px
try 10°, 20px
...

```

# Answer
> 10 votes
After some thought, I finally decided to implement the ***spiralling search*** method I briefly described in the original question.

The rationale is that the Byte56's method needs special treatment for certain conditions, while the *spiralling search* doesn't, and **it codes in a really compact way**. Also, the *spriralling search* emphasise **finding the closer spot to the vehicle** to place the label, which IMO is the main factor in making the map readable.

However please continue to upvote his answer, as it's not only useful, it's also very well written!

Here's a screenshot of the result achieved with the spiralling code:

And here's the code which - although not self-contained - it gives an idea on how simple is the implementation:

```
def place_tags(self):
    for tag in self.tags:
        start_angle = tag.angle
        while not tag.place() or is_colliding(tag):  #See note n.1
            tag.angle = (tag.angle + angle_step) % 360
            if tag.angle == start_angle:
                tag.radius += radius_step
        tag.connector.update()                       #See note n.2

```

**Note 1** \- `tag.place()` returns True if the tag is entirely on the visible area of the screen/radar. So that line reads like "keep on looping if the tag is outside the radar or it overlaps something else..."

**Note 2** \- `tag.connector.update` is the method that draw the line connecting the aeroplane icon to the label/tag with the text information.

# Answer
> 15 votes
Essentially this issue is similar to a collision avoidance problem. Yes, the planes can fly at different altitudes, but their labels are all at the same "altitude".

There are algorithms like Unaligned Collision Avoidance, that would be a step in the right direction for you. Of course for your situation, the labels are "tethered" to their planes, so they have a limited range of movement.

If you look at Flocking Behavior, you want to implement the first "rule" of flocking: short range repulsion. However, instead of "steering" in the direction that is away from the nearest neighbors, you'll use the "away" vector as the placement location for your label.

For example:

The large black circle represents your area of influence, the green circle represents the valid placements for the label, the center green dot is the plane your currently considering, small green dot is the point on the circle chosen for label placement.

Now the black dots could represent either other labels, or other planes. I'm not sure which one would work best, you may get better avoidance if they were other labels, but I'm not sure. Obviously the "force" arrows are the direction vectors between your current plane and the "objects of influence". Finally, the box is the label.

So using your example above, I think this would produce something like:

```
            - label
           /
          B
label - A
          C
           \
            - label

```

Using this method there are some situations you'll have to make special cases for, like three planes vertically aligned:

```
          - label       label -
          |                   |
          B                   B
  label - A                   A - label
          C                   C
          |                   |
          - label       label -

```

All three labels could flip flop from right to left, depending on how your have your label corners defined. Basically, you'll just have to watch out for the angles around the circle where your labels can switch which corner they're drawn from: 0, 90, 180, 270.

I think in the end, this would look kind of neat, watching the labels avoid each other. If it gets too distracting, perhaps you can round to the nearest 10 degrees for less frequent movement.

Sorry for the weird details, most of this stuff I thought about when I was making a radial menu for my game, but I think in this "dynamic" form it would work pretty well.

---
Tags: algorithm, sprites, collision-avoidance
---


title: What comes with Nintendo's DS SDK?

text:
# Question
Title: What comes with Nintendo's DS SDK?
Presumably a development machine for sure, but would it contain any sort of editor (of any kind)? Or are there any editors in existence that work with the SDK that are commercially available?

# Answer
> 4 votes
The details of the content of the SDK are probably covered by NDA.

That said, since SDKs generally contain compilers and other related tools and libraries. Access to the development hardware is often a separate issue, although to most developers they will appear to be part of the same package.

You can use any text editor to write code, and just about any IDE that can work with external compilers (which is any decent one) can be made to incorporate the tools from a console SDK.

# Answer
> 4 votes
It comes with compilers (Metroworks Codewarrior, and GCC via cygwin), lots of documentation, lots of sample code for different techniques, a Nintendo designed emulator, and optionally development hardware. From a code perspective, it's all really low level, basically directly talking to hardware registers with macros. Lower level than even something like OpenGL or Direct3D.

---
Tags: nintendo
---


# Question
Title: Game engine: a decent way, architecture-wise, to implement scripting support?
I am developing a simple game engine (in C#, if it matters), and I can't think of a decent enough way to implement scripting in terms of architecture.

It's a simple turn-based strategy with custom, logic-independent animations for battles. It has a global architecture layer for system/low-level stuff and, most importantly, two main modules - logic and game-view thingy - that communicate using an event manager.

And the thing is, I would really like to have the scripts influence both stuff related to the game logic (changing unit parameters, etc) and stuff related to the game-view, such as special animations/dialogues for battles that might depend on a certain scripted trigger.

*(To be honest, ideally I want the script to control the game flow, leaving only the core mechanics/graphics to the logic/view, but I'm new to this, so I'm not sure I can do it right now)*

I've been thinking of three options:

* Just let the scripting live in the logic, but let it know about the graphical side of the game. But this would make the logic/view division very vague, won't it...
* Make the scripting a separate module that will exchange events with the others using the same event manager. But this would require to be very careful about event synchronization, I guess... and also add a whopping lot of event types to the manager. *(Still, personal favorite)*
* Make the scripting a module above all, so it can directly influence/call functions of the logic/view. This allows for an inherently wider functionality at the cost of sort of screwing the entire event exchange scheme and being afraid that the script can break stuff even when it really shouldn't.

So, I can neither decide on one of these nor think of a better way to insert the scripting module... Any suggestions or useful links?

Thank you!

*P.s. thanks for migrating the question, didn't know there was a specialized section for gamedev*

# Answer
> 3 votes
I believe you want the third option but you will find that you are right in your thinking that having logical events happening in potentially two locations a bad thing. You will find that you want the logic module of the engine to end up being an update tick that asks two questions 'What do I do now?' and 'How do I do that?' which you can then bind scripts to for handling answering those questions.

Couple this with exposing the objects that contain the data and an API to access required Logic components (I mean you could script a the AI Path finding, but since that is a generic piece of code that is likely to be used and reused, why not embed it in the module and then add it to the API exposed to the scripting language?). This should give you the accessibility as well as the clearly defined locations where things are happening.

Again, I caveat this with the same statement I always do. A finished working product is always more valuable than a good theory in programming :)

Hope this helps!

# Answer
> 2 votes
Many tends to underestimate the powerful of dynamic languages thinking that such flexibility comes at cost of speed; This is true but often the cost is simply negligible.

Personally I tend to develop as much as possible using dynamic languages exploiting the expressiveness and then I profile the prototype to understand *where* and *if* optimization are needed.

In your case this means that you should try to move toward the third option, developing the "higher" part using a suitable dynamic language that you can use as scripting language too.

A lot of patterns can be used after you place the dynamism at the right depth. Your custom scripts can be integrated in an event based system as a callback system, when the core calls back it can provide a suitable environment so the script can alter the global status or just the state of a subset of the whole system.

You can encapsulate the interface you script can interact by using the Façade pattern. In the façade methods you can put the logic that defines *how*, *when*, *if* the script can use a functionality and abstracting the script interaction from the core implementation.

Your script interface should provide the relevant factory methods so the script can generate elements without instantiate them directly; these instances can be wrappers over the real objects so further control access logic can be implemented.

# Answer
> 1 votes
The scripting object needs to have access to the other objects it will provide data for. Be careful not to pass those other objects directly into the scripting object. Do so creates a brittle interface. You might want to have something like a mediator class that manages those object references and provides data access to the scripting object.

# Answer
> 1 votes
Lua is a popular choice for a general purpose scripting language. You can create your own scripting language using Lex and Yacc (check out the article in Game Programming Gems 3) but I would say most of your needs could be taken care of with Lua no matter how big or small.

---
Tags: c#, architecture, scripting
---


# Question
Title: Is there any notification when my data uploaded to VRAM is erased?
When my data (vertices, textures, et cetera) is purged from VRAM, how I can know that?

# Answer
> 3 votes
You can't. When you destroy your OpenGL resources (textures, VBO, etc) you are telling the graphics card that you don't need that resource anymore and it can do whatever it wants with the space they used; now, the driver can instantly delete them, mark them for purging or just mark the space as available for use. This implementation is transparent to the user and you can't know when or what happens.

# Answer
> 1 votes
Data in your VRAM won't get erased unless you explicitly call the glDelete\* function. Therefore, OpenGL does not contain such notifications.

If you for some reason need such notifications, you'll need to wrap all glDelete\* functions in your code into functions that call a notification routine.

---
Tags: c++, opengl
---