title: Mafia kill algorithm

text:
# Question
Title: Mafia kill algorithm
I'm making an Omerta clone/mafia game and trying to work out a kill algorithm. Just a basic formula to decide how many bullets player A needs to kill player B.

The inputs are: players rank (out of 10), and a players kill skill (out of 100). The algorithm needs to return how many bullets are needed for that player to win.

If you're shooting someone a higher rank, or higher kill skill, it should require more bullets.

Anyone ever done anything like this and can offer some tips?

Example chart:

# Answer
> 4 votes
I'll give you a simple method you can use, and you can factor in your stats as needed:

First, you need the player getting shot at's health. Next, you'll need the damage of each bullet. Now we can do simple math to figure out how many bullets you need to fire:

```
bullets = ceil(health / damage)

```

For example, if Player B has 87 health, and each bullet does 12 damage, we would do `87/12`, which is 7.25 and round that up to 8. This means to kill a player with 87 health, you need to fire 8 bullets that do 12 damage.

Now, let's factor in the Kill Skill and the Rank. As you did not provide how these affect the damage dealt/received, I'll do that myself. You can change it as you see fit. We have two players with the information we'll need:

> Player A (Kill Skill 65, Bullet Damage 12)
> Player B (Rank 6, Health 87)

We won't need any other information. Player A is firing at Player B. We'll say that Rank determines the amount of damage you'll receive. For each Rank, you receive 0.4 less damage (`DAMAGE_RECEIVED_PER_RANK`). We'll say that Kill Skill determines the amount of damage you deal. For each level, we'll say you do 0.1 more damage (`DAMAGE_DEALT_PER_KSLVL`). First off, we need to get the amount of damage a bullet will do to Player B factoring in our Rank and Kill Skill:

`damage = (DAMAGE_PER_BULLET - (rank * DAMAGE_RECEIVED_PER_RANK) + (killskill * DAMAGE_DEALT_PER_KSLVL))`

What this does is takes the original damage, and subtracts the amount blocked, which is Rank times `DAMAGE_RECEIVED_PER_RANK`. Next we add the extra damage, which is Kill Skill times `DAMAGE_DEALT_PER_KSLVL`). In this example, we have:

`damage = (12 - (6 * 0.4) + (65 * 0.1)) = 16.1`

The rest is simple, divide health by the damage:

`bullets = 87 / 16.1`, which is 5.4 and we'll round it up to 6. That means a player with a Kill Skill of 65 and Bullet Damage of 12 will need 6 bullets to kill a Rank 6 player with 87 Health. You can adjust the stats to balance it out. You can also fit the entire equation into one statement, but I broke it up for clarity. I hope I was of help, and good luck!

(Since I suck at math I tested this out in Visual Studio and got it to work as expected.)

---
Tags: algorithm
---


# Question
Title: What's the reason behind collision-boxes?
I was surprised that some games use extra models called collision-boxes for collision. What is the benefit of doing so? Can't we calculate collisions between the vertices of any game model? Is this possible? Are there performance reasons?

# Answer
Calculating collisions by using the geometry of the game-model can be really costly in terms of CPU usage (performance). Even more so when you're dealing with detailed polygon models.

To speed calculations up, collision detection is usually done in two phases:

* **Broad-Phase:** Use very simple bounding objects like spheres or axis-aligned bounding boxes. The goal is to have a very fast way to check for a potential collision. In this phase you can also use specialized data-structures like octrees to rule out lots of objects fast. This is very important in games with lots of objects.
* **Narrow-Phase:** If you detected a collision during the broad-phase, you can now check if the objects that had touching bounding-boxes/spheres *actually* intersect. But even in this phase, it's common to use special collider-meshes instead of the actual polygon data of the model. The collider mesh can be much more coarse then the actual model and should also consist of convex bodies to simplify collision-detection (at least that's a common constraint used in physic engines).

So yes, there are definitely performance reasons. It's always a good idea to have a broad- and narrow-phase, unless you only have to deal with very few and simple objects.

The same procedure also applies for 2D. In the broad-phase you can use bounding circles or axis-aligned rectangles. In the narrow phase you can then check the actual outlines of your sprite, for example by using SAT or pixel-perfect collision detection.
> 5 votes

# Answer
Performance reasons are a very important reason, but it's not the only one. If you handled collisions based on the actual models, this is vastly more precise than you actually *want*, for various reasons. Obviously, you don't have the same level of control over a game character as you do over your own body in real life.

In real life, your standing pose is wider than your running animation, but that doesn't mean you clip into the walls of a narrow corridor resulting in weird physics glitches when you stop moving, because you bunch yourself up to fit. Having a game character do that would require not just a lot more time spent on collisions, but an approach to character animation which takes feedback from physics and environmental cues (which would probably discount pure mo-cap).

Even if it's doable, it's not *desirable* to have whether or not your character makes the jump dependent on what point in its animation cycle it is. The control you have is an abstraction: the game underneath should also function as an abstraction. The level of that abstraction is different for different kinds of games:

Many times you want the character collision mesh to be a constant capsule. For a fighting game you may want the collision mesh to use some crude representation of your bone structure (although Street Fighter still uses 2D hitboxes defined with frame data). For a first-person shooter, you may want to use different types of hitbox (for example, capsule for movement, and a collection of bone-related shapes for shot resolution).

But you pretty much always want an abstraction: poly-perfect (or pixel-perfect, in the case of 2D) collisions, whether tractable or not, are very rarely conducive to good gameplay.
> 2 votes

---
Tags: collision-detection, algorithm, bounding-boxes
---


# Question
Title: How does changing weapons and character animation in 2d games work?
I know how I can make my character move by changing animation-frames. What if I want to use a weapon database? I want the character to fight with a bow and sometimes with an axe (different moves). Do I need like many pictures/animations for every different kind of weapon (bows, swords)? Or am I totally wrong?

# Answer
There are multiple ways to do this. The simplest but also the least flexible way would be to render the character with every weapon with every move... As you want to change weapons, you would have to create stand, walk, run and jump animations for every weapon type.

Another way is to split the character into multiple parts, that can be rendered seperately. You would still have to use multiple images for animation, but if you do it right, you can make it quiet modular.

For example, you could have one sprite, that represents a human (2d, side view) without its arm. Instead of just drawing a weapon sprite, the weapon sprite also includes the arm (so the arm can be repositioned per weapon). You could also split it in three sprites, body, arm, weapon. Like that you could define multiple arm types (or arm layouts) and make sure that every weapon has one arm layout, it looks good.

another often used way to animate 2d characters is to make the characters out of multiple parts and then create a skeleton, that is animated.

A page showing a nice example of sprite vs skeleton: http://www.catalinzima.com/2011/06/2d-skeletal-animations/

Skeletal animation is also often used in 2d shoot em ups for bosses, that are large and have multiple parts.

Also take a look at shank. As far as I know, it is done with a mix of skeletal and frame based animation. The parts of the humans are skeletal based, but if needed they also play an animation, or change the sprite of a body part etc.

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

Basically, frame based animation is much simpler, but with skeleton based animation you get much smoother visuals, if done right.
> 5 votes

# Answer
Yes. You need to model movements of your character for different types of weapons. You can reuse the movements when two weapons are of similar type (who'll notice the slight difference between firing a beretta and a glock?), but it's impossible to have your character move the same way when he's swinging a short sword or a halberd.
> -1 votes

# Answer
If you're using 2D sprites, you will need different pictures of every type of move your character can do. Later, you can draw the weapon from another sprite sheet on top of your character's sprite.
> -1 votes

---
Tags: 2d, movement
---


title: How to store level information on iOS

text:
# Question
Title: How to store level information on iOS
Let's imagine I have a breakout game. I make a level like this:

```
For columns < max columns
    For rows < max rows
        Create sprite from file, put it on some position based on
        current column and row, put it into array of objects.

```

Now, imagine I have 100 levels and I want them to be different. What tools should I use to ease my life? How do I load a level from file? Maybe a `plist`?

# Answer
You can use any format that's convenient to you. `plist` works fine as you can easily parse it into data-structures without the need of external libraries. Also something like `JSON` or plain `CSV` would work. If you write a level-editor yourself, you can use any of these formats.

You don't have to write the level editor yourself though. Since your game is row/column based, a tile editor like Tiled works just fine. Cocos2d directly supports Tiled maps. I guess any other tile-editor will work fine too.

If you don't like Tiled and rather wish to freely position sprites, have a look at CocosBuilder.
> 2 votes

---
Tags: cocos2d-iphone, ios
---


# Question
Title: collision resolve sphere-aabb and aabb-aabb
I am currently working on a basic physics engine which does not consider rotations. At the moment I work on collision resolving between aabbs and spheres. Unfortunately I have no idea what a collision between a dynamic aabb and a dynamic sphere looks like. When a sphere hits a falling aabb from a diagonal direction from above will the aabb be pushed to the sides according to the flight direction of the sphere or only accelerated further downwards? Also, when the sphere has a certain force, it will not bounce off the aabb but push it in front of itself. I don't know how to deal with this either.

At the moment I have the sphere-sphere collision implemented, which is described here: http://www.gamasutra.com/view/feature/131424/pool\_hall\_lessons\_fast\_accurate\_.php?page=3

I guess my solution will be similar, but without caring about the distance between the objects. Also I guess that the collision resolving of aabb-aabb will be the same as sphere-aabb.

Does anybody have an idea or any experience with collision resolving between aabb-sphere and aabb-aabb?

# Answer
> 4 votes
Here is how to resolve a collision between two AABBs (non-continuous). I have commented it carefully so it can be better understood.

```
    private static bool TestStaticAABBAABB(Shape s1, Shape s2, ref Contact contact)
    {
        AABB a = s1 as AABB;
        AABB b = s2 as AABB;

        // [Minimum Translation Vector]
        float mtvDistance = float.MaxValue;             // Set current minimum distance (max float value so next value is always less)
        Vector3 mtvAxis = new Vector3();                // Axis along which to travel with the minimum distance

        // [Axes of potential separation]
        // • Each shape must be projected on these axes to test for intersection:
        //
        // (1, 0, 0)                    A0 (= B0) [X Axis]
        // (0, 1, 0)                    A1 (= B1) [Y Axis]
        // (0, 0, 1)                    A1 (= B2) [Z Axis]

        // [X Axis]
        if (!TestAxisStatic(Vector3.UnitX, a.MinPoint.X, a.MaxPoint.X, b.MinPoint.X, b.MaxPoint.X, ref mtvAxis, ref mtvDistance))
        {
            return false;
        }

        // [Y Axis]
        if (!TestAxisStatic(Vector3.UnitY, a.MinPoint.Y, a.MaxPoint.Y, b.MinPoint.Y, b.MaxPoint.Y, ref mtvAxis, ref mtvDistance))
        {
            return false;
        }

        // [Z Axis]
        if (!TestAxisStatic(Vector3.UnitZ, a.MinPoint.Z, a.MaxPoint.Z, b.MinPoint.Z, b.MaxPoint.Z, ref mtvAxis, ref mtvDistance))
        {
            return false;
        }

        contact.isIntersecting = true;

        // Calculate Minimum Translation Vector (MTV) [normal * penetration]
        contact.nEnter = Vector3.Normalize(mtvAxis);

        // Multiply the penetration depth by itself plus a small increment
        // When the penetration is resolved using the MTV, it will no longer intersect
        contact.penetration = (float)Math.Sqrt(mtvDistance) * 1.001f;

        return true;
    }

    private static bool TestAxisStatic(Vector3 axis, float minA, float maxA, float minB, float maxB, ref Vector3 mtvAxis, ref float mtvDistance)
    {
        // [Separating Axis Theorem]
        // • Two convex shapes only overlap if they overlap on all axes of separation
        // • In order to create accurate responses we need to find the collision vector (Minimum Translation Vector)
        // • Find if the two boxes intersect along a single axis
        // • Compute the intersection interval for that axis
        // • Keep the smallest intersection/penetration value
        float axisLengthSquared = Vector3.Dot(axis, axis);

        // If the axis is degenerate then ignore
        if (axisLengthSquared < 1.0e-8f)
        {
            return true;
        }

        // Calculate the two possible overlap ranges
        // Either we overlap on the left or the right sides
        float d0 = (maxB - minA);   // 'Left' side
        float d1 = (maxA - minB);   // 'Right' side

        // Intervals do not overlap, so no intersection
        if (d0 <= 0.0f || d1 <= 0.0f)
        {
            return false;
        }

        // Find out if we overlap on the 'right' or 'left' of the object.
        float overlap = (d0 < d1) ? d0 : -d1;

        // The mtd vector for that axis
        Vector3 sep = axis * (overlap / axisLengthSquared);

        // The mtd vector length squared
        float sepLengthSquared = Vector3.Dot(sep, sep);

        // If that vector is smaller than our computed Minimum Translation Distance use that vector as our current MTV distance
        if (sepLengthSquared < mtvDistance)
        {
            mtvDistance = sepLengthSquared;
            mtvAxis = sep;
        }

        return true;
    }

```

Resolution is then

`AABB.Position += contact.normal * contact.penetration;`

EDIT:

```
            float ma = a.InverseMass;
            float mb = b.InverseMass;

            // (1/Ma + 1/Mb)
            float m = ma + mb;

            // Position resolution
            a.Position += contact.nEnter * contact.penetration * (ma / m);
            b.Position += -contact.nEnter * contact.penetration * (mb / m);

```

# Answer
> 1 votes
AABB-AABB collision is quite simple : for each axis, you have to check if the smallest bound of an AABB is greater than the highest bound of the other one. If so, no collision is possible (i.e., if aabb1.x1 \> aabb2.x2, the left side of aabb1 is at the right of the right side of aabb2, so there is no collision). You check :

* aabb1.x1 \> aabb2.x2
* aabb2.x1 \> aabb1.x2
* aabb1.y1 \> aabb2.y2
* aabb2.y1 \> aabb1.y2
* aabb1.z1 \> aabb2.z2
* aabb2.z1 \> aabb1.z2

If any of theses returns true, there is no collision. If all were false, there is a collision.

AABB-sphere collision is different. For each axis, you will search the distance between the center of your sphere and your AABB. For the X axis, per exemple, you first check if aabb.x1 \<= center.x \<= aabb.x2. If so, your distance is 0. Else, your distance is Min(Abs(aabb.x1 - center.x), Abs(aabb.x2 - center.x)).

Then, if dx, dy and dz are your distances, you just check if dx² + dy² + dz² \<= sphereRadius². If so, you have a collision.

# Answer
> 0 votes
I guess I finally found the answer: I took the same formula as stated in gamasutra but I don't use centerdiff as the collision normal. Instead I take the corresonding normal of the surfaces which collide. For example: Let's assume an aabb1 with velocity \[1/1/0\] and an aabb2 with velocity \[-1/1/0\]. Also let's say they will hit each other on their sides. This will lead to the collision normal \[1/0/0\] or \[-1/0/0\] respectively for the other aabb.

The corresponding code would be:

```
if (aabb1Max.y > aabb2Max.y && aabb1->velocity().y < 0) {
   // collision top
   contactNormal.set(0, 1, 0);
} else if (aabb1Min.y < aabb2Min.y && aabb1->velocity().y > 0) {
   // collision bottom
   contactNormal.set(0, -1, 0);
} // etc. for the other dimensions

SLVec3f vel1 = aabb1->velocity();
SLVec3f vel2 = aabb2->velocity();
SLfloat m1 = aabb1->mass();
SLfloat m2 = aabb2->mass();
SLfloat optimizedP =
    (2.0 * (vel1.dot(contactNormal) - vel2.dot(contactNormal))) / (m1 + m2);
SLVec3f v1_ = vel1 - optimizedP * m2 * contactNormal;
SLVec3f v2_ = vel2 + optimizedP * m1 * contactNormal;

aabb1->velocity(v1_);
aabb2->velocity(v2_);

```

I haven't found a way to prove that this is correct though.

---
Tags: 3d, collision-detection, physics, aabb
---


# Question
Title: Writing a Massive Multiplayer Onlinegame by Own
I wonder how long it will take a single person to write a complete MMO engine. Is this possible? This question is only about the engine development. There will not be a lot of models or level design or quest design. I want to use C++ and OpenGL but no other framework.

# Answer
> -1 votes
Eh, this question isn't really a good fit for the site but since i spent some time researching a very similar question, I figure I'll post what I determined.

The main problem I have found with developing a large scale game solo is the time it takes. If you wanted this as a hobby and expected it to take a very, very long time, then yes it is possible.

Another problem with doing something solo is that you cannot find all the answers you are looking for online. Working with a team of programmers is invaluable because if you are having a hard time determining how to do something, you can have other people familiar with the code take a look and give their input.

It is really difficult to ask anonymous people online these questions because you can't (or won't) give them all of your code and when people don't fully understand, they probably wont respond.

So now, if you are a highly experienced C++ OpenGL programmer, you might already have some code that you can use or know how to set it up. That is great but it all depends on how much time you can dedicate and how determined you are with completing the game. If you are new to C++ and OpenGL, it makes things a lot more difficult because when you say 'engine', do you really know what that all encompasses? There are a ton of things to take into account and having others be able to have input reduces the odds of you forgetting something or implementing it wrong.

It takes teams of programmers potentially several years to complete a game, so you should expect to spend a multiple of that time working on yours. Its a very difficult task and while i don't discourage you to try, just be aware that it is a pretty much uphill battle the whole way.

I only say this because I have attempted this before and got discouraged and moved on, after much frustration and lost time.

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


# Question
Title: How can I determine the direction of turn?
I want a function that gives me the turn direction for my object (`1` or `-1`)

I have two angles

**1 - current rotation(A)**

0 \<= A \<= 360

**2 - target rotation(B)**

0 \<= B \<= 360

```
int turnSide = FindTurnSide(A, B);
Myobject.rotation += turnSpeed * turnSide;

public int FindTurnSide(int A, int B){
    //Find the closest side direction for return
    //return 1 for right side
    //return -1 for left side
}

```

The function should find the closest side for turn. And it should return `1` (turn right) or `-1` (turn left).

How can I implement the `FindTurnSide` function?

# Answer
> 2 votes
**EDIT**: The answer is now correct, you had to add 360 in case of `diff` negative

You just have to look at the difference between the two angles. It it is between 0 and 180, you turn left (anticlockwise), otherwise right.

```
int FindTurnSide(int current, int target)
{
     int diff = target - current;
     if(diff < 0)
         diff += 360;
     if(diff > 180)
          return -1; // left turn
     else
          return 1; // right turn
}

```

# Answer
> 0 votes
Here you go.

```
public static class MathF
{
    public const float TwoPi = Math.Pi * 2.0f;
    public const float RadAngle180 = Math.Pi;
    public const float RadAngle360 = TwoPi;

    public static float NormalizeAngle(float var)
    {
        if (var >= 0.0f && var < RadAngle360) return var;

        if (var < 0.0f)
            var = RadAngle360 + (var % RadAngle360);
        else
            var = var % RadAngle360;

        return var;
    }

    public static float TurnDir(float val1, float val2)
    {
        val1 = MathF.NormalizeAngle(val1);
        val2 = MathF.NormalizeAngle(val2);
        if (val1 == val2) return 0.0f;

        if (Math.Abs(val1 - val2) > RadAngle180)
        {
            if (val1 > val2) return 1.0f;
            else return -1.0f;
        }
        else
        {
            if (val1 > val2) return -1.0f;
            else return 1.0f;
        }
    }

    public static float CircularDist(float v1, float v2)
    {
        float vTemp = System.Math.Abs(NormalizeAngle(v1) - NormalizeAngle(v2));
        if (vTemp * 2.0f <= RadAngle360)
            return vTemp;
        else
            return RadAngle360 - vTemp;
    }
}

```

---
Tags: mathematics, rotation, angles
---


# Question
Title: How does Dwarf Fortress keep track of so many entities without losing performance?
In Dwarf Fortress you can have hundreds of Dwarves, animals, goblins, etc in game at any one time, each with their own complex AI and pathfinding routines. My question is how does this not produce noticeable slowdown? Does each Dwarf run in its own thread?

# Answer
Any system which had a thread for each of so many characters would run out of resources very quickly. Threads may give you access to extra processor cores but they don't make anything intrinsically more efficient, and they come with overhead.

The simple answer is just to be efficient about processing each entity in the game.

* Don't process every entity each frame.
* Split processing into stuff that needs doing often and stuff that does not need doing often.
* Spread long-running algorithms across multiple frames so that they don't block processing in other systems.
* Ensure that efficient algorithms and data structures are used.
* Cache the results of expensive calculations if they are likely to be used again.
> 115 votes

# Answer
Dwarf Fortress is not open source, and while there is a lot of conjecture and reverse engineering that can go into how that all works, I will instead focus on some basic techniques for optimizing a 3D (not 3D graphics, 3D world) roguelike of the same type.

As is the case with all video games there are a lot of smoke and mirrors that are creating the illusion of complexity from simple rules and systems. These range from using simple random numbers for aimless movement all the way out to pre-baking a high-level mesh of nodes for pathfinding.

### Movement

Speaking of pathfinding, this can often be a very difficult problem to solve for large spaces like a DF map can be (as much as 768x768x64 IIRC) however the problem can be simplified and sped up in these ways:

* Pre-baked node network: When the map is created the world can be broken into chunks, and each chunk can have its exits and entrances mapped. When a chunk is updated, such as when a wall is built, only that chunk's network needs to be updated.
* Staged Pathfinding: Running a path over the whole map, cell for cell, would take a lot of time, instead you would pathfind over the larger chunk network, which maps all the connection between chunks, and then only run an intra-chunk path when moving from chunk to chunk. This does 2 things for you. It speeds up the pathfinding by breaking it up over many smaller pieces, and it also enables the unit to change direction part way along the path when a chunk updates. It would re-path across the large network if any of the nodes it needs to cross update.
* Random steering: When not moving to a goal, the unit need only walk aimlessly. Many roguelikes just move the unit in a random direction, which feels unnatural. Various steering techniques can be used, simple ones are favoring to move in a straight line and having less and less chance to move in the directions radiating to the back, which would have only about a 1% chance. So the unit would sometimes reverse direction entirely, but only rarely.

I won't cover the basics of pathfinding. Most roguelikes use A\*, but there are other methods to skin the cat. Mmmm Cat leather..

### Personal Tasks

One of the major things that makes DF units pop and feel alive is their personal goal list. In truth many roguelike games have this on a basic level. Essentially each unit has a list of desires (and for your dorfs, tasks they might pick up that you're asking to be done) and they will pick from them based on their personality (stats.)

Some tasks have requirements. Making a leather skirt requires the dorf be in such-and-such a shop that has X items. So those all are checked and added as tasks to their list. Simple as that.

Since most of the time a unit will be in transit, the checks for what units are doing can be very fast, only a few units will be making a choice at any given moment, and so overall there is no slow down even for hundreds or thousands of units. And remember, in DF everything from bees to troglodytes to trees are units.

---

In doing some additional research it is clear that, hilariously, DF is doing a terrible job of pathfinding in general. It isn't breaking the map into chunks, it is breaking the map into segments or areas that are connected, (which is better than nothing for sure) so my above assessment is even less an example of how DF works than I thought. :) Which is not to say that DF is anything less than amazing for a million other reasons.

It goes to show that what is important in a game is the game play. Not graphics, not great programing, not great writing, not great music, not even the interface; nothing else is even 1% as important as the game itself.
> 65 votes

# Answer
From this page:

> Well \[the pathfinding\] looks amazing from my end, since there's a metric ton of characters all doing it at once.
>
> TA: The dwarves themselves mostly move around with A\*, with the regular old street-distance heuristic. The tricky part is that it can't really call A\* if they don't know they can get there in advance, or it'll end up flooding the map and killing the processor.

I don't know if this is definitely how he prevents *"flooding the map"*, but the usual way to do this in games is using an alteration to A\* called Hierarchical Path-Finding A\*, or HPA\*. The idea is to break the grid into many fewer but larger chunks, then use A\* to find the best path from each chunk to its neighboring chunks. You can use this to build a much smaller graph over which to run A\* for each unit over.

You can also group those chunks into even larger chunks, which is where the "hierarchical" comes from.

This algorithm only finds near-optimal paths, but for games like Dwarf-Fortress that is usually ok. It is still guaranteed to find a path if one exists; and when there is no path, it will only flood-fill the smaller graph, saving an enormous amount of time.

There is also an abstraction of HPA\* that deals with units which can go over some terrain but not others *(such as cliffs, which air-units can traverse over but ground-units can't)*. It's called HAA\*, and there is a very accessible article explaining it here.

You can read more about various pathfinding algorithms here.
> 52 votes

# Answer
If anything, it's the opposite - the whole thing runs on one thread and it's now hitting the point where that is becoming the blocking factor (last time I checked!)

The reason it's fast is that there's no fancy graphics. It's deceptive, but the main thing that slows stuff down is drawing things (think upwards of two thirds of a frame in AAA titles). Since dwarf fortress is quite basic, it devotes the rest of that time to doing interesting things.
> 18 votes

# Answer
I don't know how DF is coded but the amount of AIs doesn't really impress me because what people often oversee it that **AI doesn't need precision**. It's perfectly viable to do most stuff only every few seconds. It's also viable to use imprecise calculations. *Imperfection saves a lot performance*. You can run the decision making routine of 100 units every 100 ms, or you can run it for 1000 units every second, it will take the same amount of CPU time but well... you have 10 times the units.

Here is a simple example how one could handle a lot units:

```
int curUnit;
Array<Unit> units;
[...]
while([...]) // Game Loop
{
  [...game logic...]
  // process 10 AIs per Frame
  for(int i=0; i++; i<10)
  {
    curUnit++
    if(curUnit == units.length()) curUnit=0;
    if(curUnit < units.length())
      units[curUnit].processAI();
  }

  // Update the position of all units, this should be as optimized as possible
  foreach(Unit& unit in units){ unit.move(); };

  [...graphics...]
}

```

The AI will become less and less responsive the more there are, but the player probably will only notice it in extreme cases.
> 11 votes

---
Tags: ai, path-finding, multithreading, npc
---


# Question
Title: In a 2d tile based game, what is a good method for scrolling?
I am using Direct3D with the D3DXSPRITE wrapper to draw the tiles to the screen. I have a tile class which contains members such as collision and tile type, then i have an array of tiles e.g.

Tile grid\[256\]\[256\];

Which would be a better method?

-Draw the player in the center of the screen and offset where the map draws.

-Move the player with the camera following.

I was using the first method, but its getting really complicated when you get to the top left edge of the map, and when other players/enemies are on the map and moving at the same time

if i make the camera follow the player, would i have to call spriteBatch-\>Draw(...) for every single grid tile even though only a few can fit on the screen?

# Answer
> 4 votes
It's probably best to do all updates and calculations in "real", world units and move the camera. Your spriteBatch may perform culling itself but if it's too slow you can try to determine what tiles need to be displayed on screen and only draw those.

# Answer
> 2 votes
Moving the camera in world coordinates and have your character move around the world is the easiest way to approach this problem, working in world coordinates means you dont need to do any extra calculations when it boils down to all the other systems which must work on a relative coordinates system and also understand where they are in world coordinates.

Since you are working in 2D another good tip is to do some spatial partitioning the easiest way would be to create a virtual world grid system, this will allow you to manage each tile individually by associating sprites and other resources on a per tile basis, so in essence the process would be:

* create some tile class which can hold the boundary coordinates for the tile and whatever resources that specific tile may need ( sprites, enemies, etc.. ).
* decide on the size of your world and create a 2D array ( you could use one dimension and access it as 2D ) of tiles each one representing a bit of your world with all of its associated resources.
* only draw resources from the tile the player is in and its neighbours.

With a grid you can easily find out which tile the player is in based on it's position relative to the start of the grid.

To work around the problem you mentioned about the camera you need to make the player and the camera two independent systems where the camera wont travel any further than the centre of the edge tiles so when the player travels to that tile he can still travel throughout the entire tile as he is bound by world coordinates ( i.e. no longer centered on the screen ) but the camera is locked.

# Answer
> 0 votes
I use a surface. I create the entire world on an off screen surface and keep an x and y coordinate. I alter these as the player moves and each frame draw a 1028 x 768 rectangle from the surface to the backbuffer using x and y.

as for other people I give them an x and y and let them move around the world as they please, when drawing I check if there x and y is in the 1028 x 768 rectangle and if so draw them (I use textures for people).

I have the player in the centre of the screen and check if the edge of the world has reached the edge of the screen. In this circumstance the player moves about the screen to the edge of the world and back to the centre then the world starts moving again. it seems hard and took me a while but is not to bad to do.

I use 64 x 64 tiles and the biggest world I have used so far is 50 x 60 tiles.

This is all done in direct x with c++

# Answer
> 0 votes
It's quite normal for the code to get a bit of a pain in the corners of a tiled world, when working out which tiels to draw, and simultaneously ensuring the camera doesn't go 'off-world'. Those edge cases are basically the most compelx thing about implementing a 2D tile-based world thats larger than the screen res. It gets much more complex if you support zooming in, and zoom-to-cursor :D

---
Tags: c++, directx, directx9
---


# Question
Title: About Alpha blending sprites in Direct3D9
I have a Direct3D9 application that is rendering ID3DXSprites. The problem I am experiencing is best described in this situation:

I have a texture that is totally opaque. On top of it I draw a rectangle filled with solid color and alpha of 128. On top of the rectangle I have a text that is totally opaque. I draw all of this and get the resulting image through GetRenderTarget call. The problem is that on the resulting image, on the area where the transparent rectangle is, I have semi transparent pixels. It is not a problem that the rectangle is transparent, the problem is that the resulting image is.

The question is how to setup the blending so in this situation I don't get the transparent pixels in the resulting image?

I use the sprite with D3DXSPRITE\_ALPHABLEND which sets the device state to D3DBLEND\_SRCALPHA and D3DBLEND\_INVSRCALPHA. I tried couple of combinations of SetRenderState, like D3DBLEND\_SRCALPHA, D3DBLEND\_DESTALPHA etc., but couldn't make it work.

Thanks.

# Answer
You can use D3DRS\_SEPARATEALPHABLENDENABLE render state to control the blend outcome in the alpha channel of the destination.

```
SetRenderState (D3DRS_SEPARATEALPHABLENDENABLE, TRUE);
SetRenderState (D3DRS_SRCBLENDALPHA, D3DBLEND_ZERO);
SetRenderState (D3DRS_DESTBLENDALPHA, D3DBLEND_ONE);

```

Provided that your texture was filled with a fully opaque color to begin with; this should leave the alpha channel alone.
> 2 votes

# Answer
for future reference, you should check out Pix in the directx SDK, it's a great tool for seeing exactly what is being rendered at each point, and working out how the final color fo a specific pixel was arrived at.
> 1 votes

---
Tags: c++, directx9
---


title: Trouble with the State of things in XNA

text:
# Question
Title: Trouble with the State of things in XNA
I'd decided to break the mold and make my first game based on RPG mechanics *(note sarcasm)*. An RPG style action bar would be a reasonable and fun way to get started as it's limited in scope but still challenging.

I have my spell bar and three targets. I click a target, cast a spell, start the cast, put the spell on recovery cooldown, set the global cooldown, the spell goes through a casting phase then casts, the effect is applied to the target, mana is spent, the spell goes on cooldown or is removed depending. Casting is animated, cooldowns are typical gray shading. Then the other rules start to come into play.

* When a spell is being the cast the target cannot be changed.
* When a spell is on cool down we want a standard global cool down effect.
* When a target has an effect we put a smaller version of the icon near it which also has the same cooldown effect based on remaining duration.
* When the effect expires we need to remove it.
* When something is on cooldown and another cooldown is triggered the cooldown must become the longer of the two.
* Each spell on a target has an effect such as damage or shield
* Some effects, like shield, mitigate other effects, like damage

I've ended up with too many UI concerns checking the same pieces of data. So my buttons have states, I tried the State Pattern, but ended up with the same type of crappy code in determining what state to set my objects to.

Take the example that a spell can't be cast if it's on cooldown. Pretty straight forward as that's information the spell has about itself. You can't cast if you have insufficient mana, getting more complicated because now I need to know about the state of the player to properly render the spell as shaded cause it's not available, can't cast on player if effect already exists, getting ugly now I need knowledge about the target and their effects as well. Every one of these new situations resulted in my code bloating or getting stringy.

I'm event driven enough to detect clicks but should I go farther and be creating events for everything such as OnSpellCastBegin, OnSpellCastInProgress, OnSpellCastComplete, OnManaChanged, OnTargetChanged?

I would think it's the spell classes responsibility to answer if it can be cast but this requires it have a reference to the Player, and the PlayersTarget, and whatever else in the game in the future can effect a spell cast. What kind of design approach would support future adjustments to if a spell could be cast that followed the open/closed principal where I didn't have to modify the spell class every time?

thanks!

# Answer
> 1 votes
There is no trick: you need good OOP design to avoid State-Hell.

Decouple, decouple, decouple.

The "classic" advice to get out of State-Hell is to go with the Strategy Pattern

---
Tags: xna, design-patterns, state
---


# Question
Title: How to draw reflection of shaded objects in OpenGL?
I am trying to draw a scene with objects floating around and a mirror among them to reflect the objects in front of it.

I managed to draw the reflection properly when the floating objects aren't drawn using a glsl shader program: https://i.stack.imgur.com/434Ug.png

But when I use a simple toon shader program to draw the objects, the reflection isn't there: https://i.stack.imgur.com/s2AlB.png

So, I need some advice on how to do in properly so that it would work for both cases.

FYI, I am using negative scaling to draw the reflection, using stencil buffer to draw it only on the right areas on mirror, using a clipping plane so that objects behind the mirror wouldn't have reflections.

Here is the code I used to draw the scene in the images (I apologize for all those includes and defines, most of which aren't used anyway):

```
#include <GL/glew.h>
#include <GL/freeglut.h>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <fstream>
using namespace std;

typedef double dbl;
typedef float flt;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

#define abs(x) ((x)<0?-(x):(x))
#define sqr(x) ((x)*(x))
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define intclz(x) __builtin_clz(x)
#define intctz(x) __builtin_ctz(x)
#define intln(x) (32-intclz(x))
#define intbc(x) __builtin_popcount(x)
#define atbit(x,i) (((x)>>(i))&1)
#define tof(x) __typeof(x)
#define FORab(i,a,b) for (int i=(a); i<=(b); ++i)
#define FOR1(i,n) FORab(i,1,n)
#define FOR(i,n) FORab(i,0,n-1)
#define allstl(i,x) for (tof((x).begin()) i = (x).begin(); i!=(x).end(); ++i)
#define begend(x) (x).begin(),(x).end()
#define ms(a,v) memset(a,v,sizeof(a))
#define msn(a,v,n) memset(a,v,n*sizeof(a[0]))
#define mcp(d,s,n) memcpy(d,s,n*sizeof(s[0]))
#define clamp(x,a,b) min(max(a,x),b)

// Camera works

flt camrotx = 0, camroty = 0;
flt camposx = 0, camposy = 0, camposz = -15;
int screenWidth = 640, screenHeight = 480;
int movx = 0, movy = 0;

const GLfloat light_ambient[]  = { 0.0f, 0.0f, 0.0f, 1.0f };
const GLfloat light_diffuse[]  = { 1.0f, 1.0f, 1.0f, 1.0f };
const GLfloat light_specular[] = { 1.0f, 1.0f, 1.0f, 1.0f };
const GLfloat light_position[] = { 0.0f, 4.0f, 4.0f, 0.0f };

const GLfloat mat_ambient[]    = { 0.7f, 0.7f, 0.7f, 1.0f };
const GLfloat mat_diffuse[]    = { 0.8f, 0.8f, 0.8f, 1.0f };
const GLfloat mat_specular[]   = { 1.0f, 1.0f, 1.0f, 1.0f };
const GLfloat high_shininess[] = { 100.0f };

// Shader works

static int readfile(const char* filename, char* buffer, int buflen, char** strs)
{
    FILE* fx = fopen(filename, "rt");
    char* buf = buffer;
    int ret = 0;
    while ((buf=fgets(buf,buflen-(buf-buffer)-1,fx))!=NULL) strs[ret++] = buf, buf += strlen(buf)+1;
    fclose(fx);
    return ret;
}

GLuint vtxshaderId=0, frgshaderId=0, myshaderprogId=0;

static GLuint loadshader(const char* filename, GLenum shadertype)
{
    GLuint ret = 0;
    char buffer[10000];
    char* lines[100];
    int linec = readfile(filename, buffer, sizeof(buffer), lines);
    ret = glCreateShader(shadertype);
    glShaderSource(ret, linec, (const GLchar**)lines, NULL);
    glCompileShader(ret);
    glGetShaderInfoLog(ret,sizeof(buffer),&linec,buffer);
    cout<<buffer<<endl;
    return ret;
}

static void des_shaders()
{
    if (vtxshaderId) glDeleteShader(vtxshaderId);
    if (frgshaderId) glDeleteShader(frgshaderId);
    if (myshaderprogId) glDeleteProgram(myshaderprogId);
}

static void gen_shaders()
{
    des_shaders();
    myshaderprogId = glCreateProgram();

    vtxshaderId = loadshader("/home/prat/Desktop/tatka/upalGL/water/assets/crow1.vert", GL_VERTEX_SHADER);
    glAttachShader(myshaderprogId,vtxshaderId);
    frgshaderId = loadshader("/home/prat/Desktop/tatka/upalGL/water/assets/crow1.frag", GL_FRAGMENT_SHADER);
    glAttachShader(myshaderprogId,frgshaderId);

    glLinkProgram(myshaderprogId);
}

// Scene works

const int slices = 32, stacks = 32, circlecount = 10;
struct circle
{
    flt x, y, z, r, red, green, blue;
};
circle sceneCircles[circlecount];

static void gen_sceneCircles()
{
    sceneCircles[0] = {0, 0, 0, 3, 1, 1, 1};
    FOR1(i,circlecount-1) sceneCircles[i] = { (rand()%1000)/100.0-5.0, (rand()%1000)/100.0-5.0, (rand()%1000)/100.0-5.0, (rand()%100)/100.0+0.4, (rand()%100)/100.0, (rand()%100)/100.0, (rand()%100)/100.0 };
}

static void draw_sceneCircles()
{
    FOR(i, circlecount)
    {
        const circle& c = sceneCircles[i];
        glColor3f(c.red,c.green,c.blue);
        glPushMatrix();
        glTranslated(c.x,c.y,c.z);
        glutSolidSphere(c.r,slices,stacks);
        glPopMatrix();
    }
}

// GLUT callback Handlers

static void resize(int width, int height)
{
    screenWidth = width, screenHeight = height;
    glViewport(0, 0, screenWidth, screenHeight);
}

static void display_init_cam(void)
{
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluPerspective(45.0, (float)(screenWidth)/screenHeight, 0.5, 100.0);
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
    glTranslated(camposx, camposy, camposz);
    glRotatef(camroty, 1, 0, 0);
    glRotatef(camrotx, 0, 1, 0);
}

bool flg = false;
const int mirrorpos = -0, mirrorsize = 10;
GLdouble mirrorplane[] = {0, 1, 0, -mirrorpos};

static void display(void)
{
    #define outtahere glutSwapBuffers();return
    #define glStencilFuncDefault() glStencilFunc(GL_ALWAYS,0,0xFFFFFFFF)
    #define glStencilOpDefault() glStencilOp(GL_KEEP,GL_KEEP,GL_KEEP);
    #define glColorMaskDefault() glColorMask(GL_TRUE,GL_TRUE,GL_TRUE,GL_TRUE)
    #define glDepthMaskDefault() glDepthMask(GL_TRUE)
    #define glCullFaceDefault() glCullFace(GL_BACK)
    #define glDepthFuncDefault() glDepthFunc(GL_LEQUAL)
    glClearColor(0, 0, 0, 0);
    glClearStencil(0);
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT | GL_STENCIL_BUFFER_BIT);
    display_init_cam();
    glLightfv(GL_LIGHT0, GL_POSITION, light_position);

    // mask

    glStencilFunc(GL_ALWAYS, 1, 0x1);
    glStencilOp(GL_REPLACE, GL_REPLACE, GL_REPLACE);
    glBegin(GL_QUADS);
    glNormal3f(0, 1, 0);
    glColor4f(1,1,1,1);
    glVertex3f(mirrorsize, mirrorpos, mirrorsize);
    glColor4f(.5,.5,.5,1);
    glVertex3f(mirrorsize, mirrorpos, -mirrorsize);
    glColor4f(0,0,0,1);
    glVertex3f(-mirrorsize, mirrorpos, -mirrorsize);
    glColor4f(.5,.5,.5,1);
    glVertex3f(-mirrorsize, mirrorpos, mirrorsize);
    glEnd();
    glStencilFunc(GL_ALWAYS, 0, 0x1);
    glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
    if (flg) glUseProgram(myshaderprogId);
    draw_sceneCircles();
    glUseProgram(0);
    glStencilFuncDefault();
    glStencilOpDefault();

    // reflection

    glStencilFunc(GL_EQUAL, 1, 0x1);
    glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
    glCullFace(GL_FRONT);
    glClear(GL_DEPTH_BUFFER_BIT);
    glPushMatrix();
    glScalef(1, -1, 1);
    glLightfv(GL_LIGHT0, GL_POSITION, light_position);
    glTranslatef(0, -2*mirrorpos, 0);
    if (flg) glUseProgram(myshaderprogId);
    glEnable(GL_CLIP_PLANE0);
    glClipPlane(GL_CLIP_PLANE0, mirrorplane);
    draw_sceneCircles();
    glDisable(GL_CLIP_PLANE0);
    glUseProgram(0);
    glPopMatrix();
    glStencilFuncDefault();
    glStencilOpDefault();
    glCullFaceDefault();

    outtahere;
}

static void key(unsigned char key, int x, int y)
{
    #define GLUT_KEY_ESC 27
    #define GLUT_KEY_BKSP 8
    if (key==GLUT_KEY_ESC) exit(EXIT_SUCCESS);
    else if (key==GLUT_KEY_BKSP) glutFullScreenToggle();
    else if (key=='=') gen_shaders();
    else if (tolower(key)=='a') camrotx += 5;
    else if (tolower(key)=='d') camrotx -= 5;
    else if (tolower(key)=='w') camposz += 1;
    else if (tolower(key)=='s') camposz -= 1;
    else if (key==' ') flg = !flg;
    glutPostRedisplay();
}

static void idle(void)
{
    glutPostRedisplay();
}

int mx=-1, my=-1;
int mx2=-1, my2=-1;

static void click(int button, int state, int x, int y)
{
    if (button==GLUT_LEFT_BUTTON)
    {
        if (state==GLUT_DOWN) mx = x, my = y;
        else mx = my = -1;
    }
    else if (button==GLUT_RIGHT_BUTTON)
    {
        if (state==GLUT_DOWN) mx2 = x, my2 = y;
        else mx2 = my2 = -1;
    }
    else if (button==3) camposz += 0.2;
    else if (button==4) camposz -= 0.2;
}

static void mousemove(int x, int y)
{
    if (mx>=0 and my>=0)
    {
        int dx = x-mx, dy = y-my;
        camrotx += dx/10.0;
        camroty += dy/10.0;
        const flt clamp_range = 90;
        camroty = clamp(camroty,-clamp_range,clamp_range);
        mx = x, my = y;
        glutPostRedisplay();
    }
    if (mx2>=0 and my2>=0)
    {
        int dx = x-mx2, dy = y-my2;
        camposx += dx/100.0;
        camposy -= dy/100.0;
        mx2 = x, my2 = y;
        glutPostRedisplay();
    }
}

// Program entry point

int main(int argc, char *argv[])
{
    glutInit(&argc, argv);
    glutInitWindowSize(screenWidth,screenHeight);
    glutInitWindowPosition(10,10);
    glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE | GLUT_DEPTH | GLUT_ALPHA | GLUT_STENCIL);
    glutCreateWindow("Sample Scene");

    glewInit();

    glutReshapeFunc(resize);
    glutDisplayFunc(display);
    glutKeyboardFunc(key);
    glutIdleFunc(idle);
    glutMouseFunc(click);
    glutMotionFunc(mousemove);

    glEnable(GL_CULL_FACE);
    glEnable(GL_DEPTH_TEST);
    glEnable(GL_ALPHA_TEST);
    glEnable(GL_STENCIL_TEST);
    glEnable(GL_LIGHT0);
    glEnable(GL_NORMALIZE);
    glEnable(GL_RESCALE_NORMAL);
    glEnable(GL_COLOR_MATERIAL);
    glEnable(GL_LIGHTING);
    glEnable(GL_TEXTURE_2D);
    glEnable(GL_NORMALIZE);
    glCullFace(GL_BACK);
    glDepthFunc(GL_LEQUAL);
    glShadeModel(GL_SMOOTH);
    glHint(GL_PERSPECTIVE_CORRECTION_HINT, GL_NICEST);
    glHint(GL_LINE_SMOOTH_HINT, GL_NICEST);
    glHint(GL_POLYGON_SMOOTH_HINT, GL_NICEST);
    glClearStencil(0);
    glClearDepth(1);

    glLightfv(GL_LIGHT0, GL_AMBIENT, light_ambient);
    glLightfv(GL_LIGHT0, GL_DIFFUSE, light_diffuse);
    glLightfv(GL_LIGHT0, GL_SPECULAR, light_specular);
    glLightfv(GL_LIGHT0, GL_POSITION, light_position);
    glMaterialfv(GL_FRONT, GL_AMBIENT, mat_ambient);
    glMaterialfv(GL_FRONT, GL_DIFFUSE, mat_diffuse);
    glMaterialfv(GL_FRONT, GL_SPECULAR, mat_specular);
    glMaterialfv(GL_FRONT, GL_SHININESS, high_shininess);

    if (GLEW_ARB_vertex_shader && GLEW_ARB_fragment_shader) printf("Ready for GLSL\n");
    if (glewIsSupported("GL_VERSION_2_0")) printf("Ready for OpenGL 2.0\n");

    gen_sceneCircles();
    gen_shaders();

    glutMainLoop();

    des_shaders();

    return EXIT_SUCCESS;
}

```

Vertex Shader:

```
varying vec3 normal, lightDir;

void main()
{
    lightDir = normalize(vec3(gl_LightSource[0].position));
    normal = normalize(gl_NormalMatrix * gl_Normal);

    gl_Position = gl_ModelViewProjectionMatrix * gl_Vertex;
}

```

Fragment Shader:

```
varying vec3 normal, lightDir;

void main()
{
    float intensity;
    vec3 n;
    vec4 color;

    n = normalize(normal);
    intensity = max(dot(lightDir,n),0.0);

    if (intensity > 0.98)
        color = vec4(0.8,0.8,0.8,1.0);
    else if (intensity > 0.5)
        color = vec4(0.4,0.4,0.8,1.0);
    else if (intensity > 0.25)
        color = vec4(0.2,0.2,0.4,1.0);
    else
        color = vec4(0.1,0.1,0.1,1.0);

    gl_FragColor = color;
}

```

# Answer
I think when using shaders you have to calculate the clip planes yourself in the vertex shader and output the clip value (plane dotted with position) to the `gl_ClipDistance[0]` built-in output variable. See the opengl.org man page for some more details.

The plane equation set in `glClipPlane` in C++ may also be available in GLSL as a built-in variable; I'm not sure. If not, you'd have to send it down to the shader as a uniform.
> 2 votes

---
Tags: opengl, shaders, reflection-rendering
---


# Question
Title: What elements of D3DPRESENT_PARAMETERS MUST be set?
DIRECTX9... For ages, I've shipped games that only half-fill out the D3DPRESENT\_PARAMETERS structure, and now I'm wondering if this is buggy. The items I'm worried about, and never set are:

* hDeviceWindow
* Windowed
* EnableAutoDepthStencil
* FullScreen\_RefreshRateInHz

I zero out the whole structure initially, so they should all be zero, even if my game is running (happily) in a window. As ever, there are a tiny %tage of users who have issues, and I am looking for possible causes. Could not setting one of these cause problems? The documentation doesn't say either way, and 99% of users certainly are fine with these settings. Does anyone have a definitive answer as to what *should* be set?

# Answer
> 2 votes
I normally set all of them, and if you have a look at the enum and other values in the D3D SDK and your header files you'll find that there are very few cases where you can safely use 0.

Windowed is OK if fullscreen is your desired behaviour - it's a BOOL so FALSE will be 0. That'll clash with BackBufferFormat though where D3DFMT\_UNKNOWN (value 0) is only documented as safe for windowed modes.

FullScreen\_RefreshRateInHz should definitely be given a value for fullscreen modes, and it should be a value from a properly enumerated mode; 0 is only safe for windowed modes (which again clashes with Windowed 0).

Without EnableAutoDepthStencil set to TRUE (1) you won't (or at least shouldn't) have a depth buffer, but yet you may be setting AutoDepthStencilFormat. And so on...

This will be internal driver and/or D3D runtime behaviour so we're into "best guess" country now, but it doesn't seem unreasonable to suppose that there are drivers (or versions of the runtime) out there that can figure something meaningful out from conflicting parameters like this. It's not guaranteed though and shouldn't be relied on.

---
Tags: directx9
---


# Question
Title: Applicability of Business Architectures in XNA 4
I've done a lot of C# programming and the architecture we use of late is a MVC =\> PresentationService =\> Domain Service And/OR DataService =\> Repository with a UnitOfWork and a messaging bus. In web applications this gives a pretty clean and flexible design that's extensible but is also stateless.

I've been working on a 2D starter project in XNA and I find these layers are still useful until I get to the interface and start trying to deal with knowing the states of everything, keeping the sprites and bounding rectangles and detecting clicks and drags.

What patterns should I be looking at that maybe I just wasn't exposed to doing enterprise architecture but are clearly needed in a game.

Which concepts might I need to let go of when doing a game because they are not applicable.

# Answer
> 7 votes
I'm not a big fan of these on-site link posting answers, but in this case I feel there are several questions that address this.

You may also want to browse some other questions in the design-patterns tag on this site.

With respect to porting skills and patterns learned while developing business apps on the Microsoft Stack to game development, I think you're in a big boat with a lot of other developers. My guess is that you are very new to game development, so my advise would be to skip any and all patterns and best practices to **get your first game working.**

Some additional thoughts

1. Keep the scope of your first game small
2. Get something on the screen as fast as possible
3. Make that thing on the screen react to user input
4. Start implementing the rules of your game
5. Finish testing, and **ship your game**
6. Refactor the best bits of code into a common library
    1. Implement patterns you think fit, based on your experience with shipping your first game
7. Start your next game and continue working on your library

---
Tags: xna, architecture, design-patterns
---


title: Java: Standing Animation

text:
# Question
Title: Java: Standing Animation
I've been working on a top-down, and the player already has animations for moving left and right. However, if I move a certain distance and stop, it will stop on the walking animation, which isn't logical as opposed to a standing animation while the player is idle.

I've been using this input handler class:

```
public class InputHandler implements KeyListener
{
public boolean up = false;
public boolean down = false;
public boolean left = false;
public boolean right = false;

public InputHandler(Game game)
{
    game.addKeyListener(this);
}

public void toggle(KeyEvent ke, boolean Pressed)
{
    int KeyCode = ke.getKeyCode();

    if(KeyCode == ke.VK_UP) up = Pressed;
    if(KeyCode == ke.VK_DOWN) down = Pressed;
    if(KeyCode == ke.VK_LEFT) left = Pressed;
    if(KeyCode == ke.VK_RIGHT) right = Pressed;
}

public void keyPressed(KeyEvent e)
{
    toggle(e, true);
}

public void keyReleased(KeyEvent e)
{
    toggle(e, false);
}

public void keyTyped(KeyEvent e)
{

}
}

```

and it is coupled with the tick() method from my main class:

```
private void tick()
{
    if(input.right)
    {
        xScroll++;

        if(xScroll / 16 % 2 == 0)
        {
            dirFacing = 2;
        }
        if(xScroll / 16 % 2 != 0)
        {
            dirFacing = 4;
        }
    }

    if(input.left)
    {
        xScroll--;

        if(xScroll / 16 % 2 == 0)
        {
            dirFacing = 1;
        }
        if(xScroll / 16 % 2 != 0)
        {
            dirFacing = 3;
        }
    }

    if(input.down)
    {
        yScroll++;
    }

    if(input.up)
    {
        yScroll--;
    }
}

```

Again, the above yScroll will be added later, I really just need to solve the standing animation first.

# Answer
> 3 votes
One way to solve this is to add a check to see if none of direction flags are set. Then use that case to start the idle animation in the `tick()`.

For instance:

`if(!input.up && !input.down && !input.right && !input.left)
{
 //play idle animation this frame
}`

Another thing to consider is the direction of the idle animation. If your character is walking left, and the idle animation shows them looking down, when the player stops moving the character will suddenly change directions. This can be solved with having 4 different idle animations. Then you use the `dirFacing` from your last tick to determine which one to play.

One last point is you aren't checking the time between ticks anywhere. If you store the delta time between ticks you can make the animation play at the same rate no matter how fast or slow the `tick()` method gets called

---
Tags: java, rpg, tilemap, logic
---


# Question
Title: What is the technical definition of "sprite batching?"
Platform and language agnostically, how is sprite batching defined? It seems as though there are many different techniques for lessening the amount of work when drawing, and that they are often lumped with "batching". It occurs to me that there may not be a real answer, but perhaps someone here has found something I have not.

# Answer
Technically, "batching" is putting multiple actions and their data into one data structure so it all can be executed at once rather than individually.

The biggest bottleneck of modern GPUs is not their working power, but the communication between your game running on the CPU and the GPU. Each package of data sent to the GPU has an overhead, but the overhead of a small package is just as big as that of a big package, so it's a big gain when you send one big package rather then a hundred smaller ones. And that's what batching is; making one big package out of all those smaller ones.

Batching is particularly useful for sprites because of the ridiculously small amount of data per sprite; four vertices and four tex coords. So the overhead of the small package is proportionally big.
> 18 votes

# Answer
Sprite batching is the method of submitting multiple sprites to the GPU with a single draw call.

Neither of the other answers point out the real point of doing this: minimizing state changes and GPU command submissions. If you have 100 sprites I draw, each with their own texture, the hardware can only process one sprite at a time. The dozens or even thousands of shader cores end up barely being utilized, and the GPU spends far too much time configuring its render state for texture switches.

If you put all your sprite images into an atlas, you can minimize the state changes needed to draw. The driver may even be able to automatically combine sprite draw requests into a single batch so that the hardware can be fully utilized, but this is not guaranteed or likely.

If you use a sprite atlas and then create a single VBO with all your sprites quads filled into it, an make a single draw request with that data, you are guaranteed that the hardware is fully utilized and all of your sprites are rendered in parallel.

Sprite batching then is doing that very thing: putting as many of your sprites as possible into a single VBO using a single atlas that is submitted to the GPU with a single draw call, maximizing GPU usage.

There are other ways to do sprite batching (like hardware instancing, using geometry shaders, etc), and other benefits to doing so, but the gist of it is that batching means drawing multiple objects per draw call.
> 12 votes

# Answer
It's not a tightly-defined technical term. Batching is basically any system where you perform multiple operations as a set rather than individually, and often this is done because it's more efficient to do so. The efficiency gains usually come from being able to re-use some or all of the context that the operation requires.

So, sprite batching is just any system that lets you draw multiple sprites at once and hopefully gain some efficiency from it. Usually the benefit is that your sprite batch is all using the same texture, so you can draw all the sprites in the batch without changing texture, which is a relatively slow operation.
> 6 votes

---
Tags: spritebatch, terminology
---


# Question
Title: What uses are there for multiple UV maps on a model?
I'm trying to think of some reasons why there might be more than one UV map on a mesh. Usually I just unwrap the model, and the same UV map works for both the diffuse color texture, the bump map texture, and any other textures I chose to add. Are there any examples of when a model might need more than one UV map?

# Answer
One example is for light maps. Usually texture space is maximized by overlapping faces which have the same diffuse texture, like the six sides of a crate. With light mapping this would mean that all six sides get the same light and shadow, not to mention it would almost assuredly confuse the light mapper because it can't tell which point in space it should be sampling light from. Obviously this is not what you want so a second set of UV coordinates is used for the light map which do not overlap.
> 6 votes

---
Tags: models, 3d-meshes, uv-mapping
---


title: Using Copyrighted Images

text:
# Question
Title: Using Copyrighted Images
I was thinking about developing a sidescrolling platformer very similar to an old Mario and Luigi game for NES. To start out I was thinking about taking the images from a site like this:

http://www.mariouniverse.com/sprites/nes/smb3

Which clearly states a copyright. I was wondering how far I am allowed to take these images. I figure I'm probably allowed to use it for personal development, but what if I publish the game as an exe file and send it to some friends? I figured a definite no-no would be selling the game with the copyrighted images included.

A secondary question would be whether or not I would be allowed to modify them slightly and then call them my own.

# Answer
> 1 votes
Disclaimer: not a lawyer (yet). Nothing here is legal advice.

Nintendo doesn't have to argue that you harmed them; violation of a copyright is a strict-liability offense, regardless of whether you sell the game, send it for free, or even keep it for yourself. Fair use could work in certain cases, particularly if it's noncommercial and won't supplant Nintendo's place in the market, but it's a weak argument at best.

As for modifying them slightly, the test is whether there is substantial similarity between the two works. If you make major modifications such that no one would really think they came from a copyrighted Nintendo source, you should be fine.

If you can get your hand on public domain images or create your own, do that. Chrono Trigger HD and Chrono Resurrection are good examples of why you shouldn't try to use copyrighted works.

# Answer
> 2 votes
The issue with doing this is a civil one, not a criminal one. As such, the real question becomes "can Nintendo argue that you've harmed them"? If the answer is yes, their civil suit will likely result in you paying damages.

The only safe play is not to use copyrighted material.

Of course, fair use exists, but distribution for anything other than artistic or educational purposes invalidates that defense. Even so, fair use is not trivial to argue.

---
Tags: game-design, sprites, legal
---


# Question
Title: What advantages does multisampling have over supersampling?
I never really fully understood this, or found an article which explained all the steps in a friendly way.

I'll start with what I do know already (which I hope do not contain misconceptions). I'm pretty sure allocating a multi-sampled frame buffer requires as many times the memory (of a regular buffer) as the number of samples (N). This makes sense because each pixel may be sampled up to N times.

During rasterization, the GPU generates a fragment for the MS frame buffer by testing if each sample is inside of the geometry being drawn. This is what provides edge anti-aliasing. Each sample produces a fragment.

I'm unsure about what occurs when all samples of a pixel are inside the geometry. How many fragments are generated? Is this configurable? What if I want to sample the "inside" pixels 4 times, and the edge pixels 16 times? This would require a 16x MS frame buffer.

Are there other differences? It seems like if the fragment shader is run once on each sample then we are left with something not much different from basic supersampling with the exception of jittered sample locations.

Actually, I'm also a bit unsure about what a frogment really is. It seems like a fragment shader gets (can get) executed more than once per pixel in a multi sampled scene, however this doesn't seem to necessarily mean that a fragment is more related to the sample than the pixel. Is a fragment best thought of as a sample, a pixel, or something else?

# Answer
Multisampling runs the pixel shader once per *pixel*, while visibility (geometry coverage, depth/stencil tests, etc.) are done per *sample*. The same color output from the pixel shader is replicated to all the samples that pass the visibility tests. The fact that the pixel shader is only run once per pixel is what makes MSAA faster than supersampling.

In fact, in D3D10-11 you *can* cause the pixel shader to run per-sample if you really want to, by using the `SV_SampleIndex` parameter, or by marking an interpolated parameter with the `sample` keyword; see the MSDN for more. The OpenGL equivalent is the ARB\_sample\_shading extension (also part of core OpenGL since 4.0). If you do this, then it would turn into just plain supersampling. This is not the normal use case, though.

There is currently not a way to do something like run the PS 4x per pixel while having MSAA at 16x. Your only choices are to run the PS per-pixel or per-sample. But you could achieve what you described by having a 4x larger buffer that is 4x multisampled, then resolving the MSAA and downsampling the extra 4x yourself before displaying.

You're right that a multi-sampled frame buffer takes as much memory as a super-sampled one - although GPUs often internally use some sort of compression to reduce the memory bandwidth required, they still have to allocate the full amount of memory as a fallback, in case of "bad" pixels that aren't amenable to compression.

A "fragment" means a sample-sized chunk of a triangle (or other primitive, technically). As Nicol Bolas says, "A fragment is the state generated by the rasterization process for a particular sample, which will be used in various processing", e.g. depth/stencil testing. So yes, when using multisampling multiple fragments may be generated for the same primitive in the same pixel. However, the fragment shader still normally runs once per pixel.
> 6 votes

---
Tags: opengl, 3d, directx, rendering, antialiasing
---


# Question
Title: Help retrieving/sending data to/from a server on iOS (C#, Mono, .Net)
I'm sorry in advance if this is a silly question.

I'm currently working on getting something running where I can grab information from a server. My goal is to make the data I'm retrieving (or sending, for that matter) as small as possible -- both for speed and bandwidth.

To make matters more complicated, I'll be needing two sets of data:

**Global:** Something that doesn't house a lot of data, but needs to be synced every time. (News, status, etc.)

**Personal:** The user's data. (Points, scores, etc.) This isn't a lot of data either, but I thought that a database would be ideal for this. Doesn't this then mean that I'd have to retrieve the whole database, and then filter it? (i.e. transmitting too much data)

The server would be as small as possible (for cost), so it should only house data, and not do any (or almost any) of the work itself, so it would essentially just be storing the files.

Is a database the best way to go about this? Should I use two databases (global, personal)?

Would SQL be best for this? Or could I use REST and just grab the data I need (not the whole file)?

---

I'm sorry if this seems like a lot. I've been googling for a few days now, and I'm unsure of what I should do. If this is unclear, please say so and I'll try to clear things up. If it's too broad, I will narrow it down more.

---

EDIT: Thanks for the answers thus far, but they aren't quite what I'm looking for. So, I'll go into more detail.

I'm thinking of using Amazon for the server, mainly because it's pay-as-you-need and scalable. Furthermore, I've found this article which is specific to MonoTouch, but I'm still not sure what's easiest. I will not have a ton of data, so if I can grab either a small file, or query a database, that would be great. I'm all for using third-party libraries, if it's possible, but mainly I'm not sure how I should do what I want to do.

Sorry for being so thick. Obviously I can understand it better with example code, but it's not a requirement for an answer. (And I want to make it explicitly clear that I'm not asking for hand-outs.)

# Answer
> 1 votes
Higher-level protocol - design around your functional requirements. Think about what data the client will need to have, to show the user what he's expecting to. If your tababase is small, and your user is able to set up different filters to query the data - then "retrieve the whole database, and then filter it" will work OK. If however your DB is large and/or user only \[typically\] need a small subset of your DB - then client is better to ask your server for the filtered dataset.

Lower-level transport protocol - based on your requirements, I'd choose between Microsoft's NET.TCP binary XML (if you're ready to run your server on Windows which is not free) and Google's protocol buffer (GPB) atop of either TCP (if you need callbacks from server) or HTTP (of you don't need callbacks). IMO, GPB is a bit easier to code on client, harder on server.

SQL vs NoSQL vs plain file storage - the answer mostly depends on your data access patterns. Client needs complex queries, especially with joins? Use an RDBMS for sure. Only need to download/upload blobs? Use NoSQL or just file system. Expect complex concurrency problems with multiple users competing to update a single record? Only consider RDBMS or carefully chosen NoSQL that is OK with that (e.g. ESENT if your server is on Windows).

# Answer
> 1 votes
**Short answer:** You can setup a cheap Linux box, setup MySQL, setup the database schema, populate your tables, and write the code to connect and query the data however you see fit.

**Long answer:** Depending on how you want to expose that data, you could set up web services (SOAP/REST) with various endpoints on a web server (which would in turn connect to the database). You could also simply connect directly to the database from your client and bypass the whole web services setup. It's really dependent on what your use case is.

Both the "global" and "personal" data can be stored in a database like MySQL on a Linux box for little cost. I wouldn't split them into separate databases unless that's a customer requirement. Even then, I would question it. The reason is because you never know when you might want to tie in the "global" data with the "personal" data. For example, what if you want to let the user customize a news feed so that the global "news" can be tied to a specific "user"?

---
Tags: c#, networking, ios, mono
---


# Question
Title: How do I create this underwater effect with Cocos2D?
http://vimeo.com/2461697

Hi everyone, I'm trying to create an effect like this, the underwater effect (water distortion). I've looked around and I've seen references to "water caustics" but I'm not sure how to create this in Cocos2d or if it's done with obj-c only.

Thanks.

# Answer
While I don't think they'll give you what you're asking for out of the box, you should definitely check out these two classes because they might be able to get you something very close.

CCShaky3D & CCRipple3D

Play around with those effects and see if you can get close. If you can't, you can always dive deeper into the engine to see how those effects are made and create your own effect.

Here's an old Youtube video showcasing these effects and others (you may want to mute the sound, though).

I hope this helps.
> 3 votes

# Answer
Even though `CCShaky` or `CCRipple` or `CCLiquid` are good effects for this kind of stuff, they consume quite a lot of processing. I do recommend you to use Cocos2d 2.x and give shaders a go. I have been doing it for a while and it seems to work better.
> 0 votes

# Answer
If you use Cocos2d 1.x version, take a look at Joe D answer. For fixed graphics pipeline this effect is only possible via grid distortion.

Maybe you use Cocos2d 2.x, with shaders? Then things are much better :) It's easy to do this effect in fragment shader (offset texture coordinates by some function of x, y and time). And you would have much more flexibility with shader (for example - add shading somewhere).
> -1 votes

---
Tags: iphone, cocos2d-iphone, water, effect
---


# Question
Title: Maintain performance and precision with a large vertex buffer?
I have a world with 100s of simple objects on screen at once. Most objects don't have more than 40-50 vertices. The vertex coordinates for these objects are very large (planetary scale), so I use the 'floating origin' method to draw my data (actual coordinates are close to the origin and then you apply a translation out to where you want the object).

Based on the user's position, these objects are dynamically created and destroyed. Other than that, the objects are static. With my previous implementation, I was drawing these objects separately, and the result was significant slow down (I'm targeting mobile devices)... since the total number of triangles on screen is sort of trivial (even though there are many objects), I assume that the slow down is because of the multiple draw calls.

So I tried packing my objects into a single buffer to draw them all with a single call. This works, but I also use a 'floating origin' transform to position the geometry. The final transform matrix is calculated with the CPU to maintain precision and then sent to my vertex shader. The problem is applying the floating origin fix is CPU intensive:

* If I use a single floating origin for the vertex buffer:

+ (good) only need to calculate one transform matrix
    + (bad) I need to perform an offset subtraction on every vertex in the buffer. The upper limits of scene complexity reaches 50k+ vertices, so this is expensive.
* If I use multiple objects:

+ (sorta good) only need to compute as many matrices as there are objects (this is still really expensive though, since there are a ton of objects)
    + (bad) I need to pass the shader a large array of matrix uniforms

I feel like I'm stuck. Are there any other ways to maintain precision I could use? Or maybe a better way to use the floating origin method? The problem is basically "how do I draw a ton of simple geometry with really large numerical coordinates with OpenGL ES 2?"... I'd appreciate any advice.

EDIT

Just some clarification on the offset. The vertex should always be a valid float. The maximum distance a vertex can be from the origin is the maximum radius of the earth +/- few thousand meters. Assume 1 unit = 1 meter. The distances are never so large that they can't be represented by floats at all.

The objects themselves are things you find in a map on the surface of the earth: buildings/roads/etc. So relative to the coordinates being used, the objects are very small.

I'm not confident on the floating origin stuff, but here's my take...

When you calculate the MVP on the CPU where your vertex is offset, you're getting something you calculate with double precision that goes from an offset vertex position (say its 10.1,10.2,10.3) to the normalized opengl coordinates (I think thats +/- 1 in xy and 0-1 in z... I don't remember right now). You then pass the shader a vertex thats close to the origin, so no huge loss in precision, and a transform matrix that was calculated with double precision.

That's way better than sending the shader a vertex with much larger values since you lose a bunch of precision right away.

# Answer
It sounds like your world is not entirely visible on screen at once (you mention creating/destroying objects based on the camera's position, and why else would you need such huge precision?). I would try to divide your world up into grid cells, where each object is entirely contained in a cell, and each cell is backed by its own vertex buffer. Because a cell has finite extent, you can use use normalized integral coordinates for the positions of your vertices, which will be more efficient (from a bits-per-precision standpoint) than floating-point vertices. You can compute a transformation matrix for each individual cell on the CPU (there shouldn't be that many cells, so it should be fairly fast), and the shader can apply it to every vertex.

This will work better if your game is 2D (or, at least, if your three dimensions aren't completely interchangeable), as you'll need significantly fewer cells to cover your world. You should be able to render all visible parts of your world with only four draw calls in the worst case (which should be negligible overhead compared to one draw call).

In order to not constrain the positions of your objects, you may have to treat the borders of your cell as loose (i.e. expand them by half the radius of the largest object; see the picture below).

* (good) only need to calculate a handful of matrices on the CPU
* (good) the matrices will maintain precision and be applied by the GPU (fast)
* (good) only a handful of draw calls
* (possibly bad) the size of the grid cells may need to be tuned, and if the grid is significantly bigger than the screen, the vertex cost can fluctuate by a factor of 4 or so
* (bad) much less useful if you need a fully 3D grid
* (bad) everything in a grid needs to use the same rendering state (standard batching caveat)
> 0 votes

---
Tags: opengl-es2
---