# Question
Title: Random monsters move in-sync instead of individually
I am making a game in which monsters spawn randomly and begin to move around randomly. I am fairly new at programming but not at game development. Through using a few tutorials I was able to make 1 creature spawn randomly and move randomly (with animations!) in a way that seemed organic instead of robotic.

So, I moved on to the next step of doing this to several creatures. However, when I executed this, I found that instead of executing their own instructions, the rest of the monsters simply mimic the relative movements of 1 central guy. **Everyone moves in sync like some North Korean military parade!**

I am using foreach loops and random numbers to choose their directions. Since my game is a top down 2d isometric, I am using a dictionary to store 4 directions. I have made some changes based on the suggestions here, and now all the creatures animate! But they still don't change directions or do things on their own.

**How do I make them each have their own unique set of instructions instead of everyone just following the dear leader?**

Below is a walkthrough of my code:

Monster Initialization:

```
public void AddCreatures()
{
     NewMonster = new Monster(Texture);
     NewMonster.AddAnimation("northeast", 0, 96, 48, 48, 8, 0.2f);
     NewMonster.AddAnimation("northwest", 0, 144, 48, 48, 8, 0.2f);
     NewMonster.AddAnimation("southeast", 0, 240, 48, 48, 8, 0.2f);
     NewMonster.AddAnimation("southwest", 0, 288, 48, 48, 8, 0.2f);
     NewMonster.AddAnimation("hoon", 144, 336, 48, 48, 1, 1.0f);
     NewMonster.Position = RandomPos();
     NewMonster.DrawOffset = new Vector2(49, 80);
     NewMonster.CurrentAnimation = "southwest";
     NewMonster.IsAnimating = false;
     creatures.Add(NewMonster);
}

```

Spawn:

```
for (int v = 0; v < 12; v++)
{
    AddCreatures();
}

```

Randomize spawn Position:

```
 private Vector2 RandomPos()
        {
            Vector2 location = Vector2.Zero;
            location.X = rng.Next(300,900);
            location.Y = rng.Next(200, 700);
            return location;
        }

```

Movements:

```
 public void Update(GameTime gameTime)
    {
        timenow += (float)gameTime.ElapsedGameTime.TotalSeconds;
        foreach (Monster mon in creatures)
        {
            if (mon.IsAnimating)
            {

                if (timenow - (float)gameTime.ElapsedGameTime.TotalSeconds > 0.5f)
                {
                    mon.Velocity = directions[rng.Next(1, 5)];
                    ChooseAnim(mon);
                    mon.Velocity.Normalize();
                    speed = (float)(rng.Next(0, 3));
                    diff = new Vector2(mon.Position.X - mon.GetLastPosition.X, mon.Position.Y - mon.GetLastPosition.Y);
                    if (Math.Abs(diff.X) >= 4 && Math.Abs(diff.Y) >= 4)
                    {
                        mon.Velocity = directions[rng.Next(1, 5)];
                        ChooseAnim(mon);
                        mon.Velocity.Normalize();
                    }
                    mon.Velocity.X *= speed;
                    mon.Velocity.Y *= speed;

                    timenow = 0f;
                }
                mon.MoveBy(mon.Velocity);

            }
            DoNotExit();
            mon.Update(gameTime);
        }
    }

```

Animation choosing method:

```
    private void ChooseAnim(Monster mon)
    {
        if (mon.Velocity == directions[1])
            mon.CurrentAnimation = "northeast";
        if (mon.Velocity == directions[2])
            mon.CurrentAnimation = "northwest";
        if (mon.Velocity == directions[3])
            mon.CurrentAnimation = "southeast";
        if (mon.Velocity == directions[4])
            mon.CurrentAnimation = "southwest";

    }

```

# Answer
There is a very quick way to fix your code. Each monster should have its own `timenow`. The rest of the code can be improved, but is not responsible for the bug you are experiencing.

Once it is done, instead of this:

```
    timenow += (float)gameTime.ElapsedGameTime.TotalSeconds;
    foreach (Monster mon in creatures)
    {
        ...

```

You do this:

```
    foreach (Monster mon in creatures)
    {
        mon.timenow += (float)gameTime.ElapsedGameTime.TotalSeconds;
        ...

```

Otherwise when you reset `timenow = 0f` the operation synchronises all monsters.
> 1 votes

# Answer
I don't know if that's everything, but here are some things that look wrong too me:

* Looks like your `oldLoc` variable is common to all your monsters. **It should probably be a member variable of your Monster class**. Otherwise you can't keep a separate record of each monster location.
* You also have a global `thisMonster` and another global `NewMonster`, they seem useless to me, if they're not bringing this bug now, they'll sure bring one later.
* In `ChooseDirection`, you set another global variable `chosen`, and use it afterwards. It's probably not breaking anything for the moment, but simply returning the chosen direction would be a bit cleaner. Otherwise you could be tempted to use this before calling `ChooseDirection` and you'd end up with some more weird issues.
* Less problematic, but still: you're re-initializing your `directions` array at each update, this could be done in an init function, this should event be a static variable.

Moral of the story: global variables are bad. Unless you're a fan of unexpected military parades.
> 3 votes

# Answer
Well, where are you deciding the random movement? This is a symptom of creating multiple `Random`(the class) instances at the same time. They'll all have the same seed time (probably some differing in just a little).
You can usually fix this by instead of creating a `new Random()` for every class that needs random moves, you can just create one `Random` object in your "management class(or something like that) and pass by reference to the classes that will use it. And I think your flaw is in the `RandomPos()` method or in the Monster constructor.

Something like this:

Instead of this:

```
Vector2 RandomPos()
{
    Random rand = new Random();
    return new Vector2(rand.nextInt(x1, x2), rand.nextInt(y1, y2) );
}

```

or this:

```
Monster(Texture2D texture)
{
    this.rand = new Random();
    ///blablabla define movement with rand object.
}

```

you should use:

```
Vector2 RandomPos(Random rand)
{
    return new Vector2(rand.nextInt(x1, x2), rand.nextInt(y1, y2) );
}

```

or this:

```
Monster(Texture2D texture, Random rand)
{
    this.rand = rand;
    ///blablabla define movement with rand object.
}

```

With this example, rand should be created in `AddCreatures()` and shared by all calls of the RandomPos function or Monster constructor.
> 1 votes

---
Tags: xna, c#, algorithm, movement, random
---


# Question
Title: Designing an entity system for a tile-based puzzle game
I'm developing a tile-based game creation library in C# and along with it I'm creating a game to test all of its functions.

This is a screenshot of the game:

You've probably never heard of the original, but my game is a clone of Deadly Rooms of Death (DROD), which you can find at http://caravelgames.com

---

Anyway, as you can see from the screenshot, my game (and my library) is all about 2D puzzle games on a grid, rigorously turn based.

My library has this structure:

* **Entity**: class that gets updated every turn and every game elements inherits from
* **Tile**: class that holds entities (any amount of entities)
* **TileManager**: class that contains a 2D array of all the tiles
* **Field**: class that contains a TileManager and all the methods for querying it and finding entities

For fast queries and flexibility, I'm using interfaces and inheritance to group entities. Let me explain with code for the roach entity:

```
public class TDLMonster : TDEntity, IHasTarget, IDrawn, IHasDirection, ISolid,
IHitByWeapon, IHitByMonster
{
...
}

```

The TDLMonster class inherits from TDEntity (which inherits from Entity). It also uses interfaces as a way to mark certain properties of elements.

```
public interface IHitByWeapon : IEntity
{
    void HitBySword(IWeapon mWeapon);
}

```

This is the IHitByWeapon interface. After every turn, weapons check if there is any instance of IHitByWeapon on their tile. If there is, call HitBySword. Here's the code that does this:

```
 public virtual void CheckHits()
    {
        List<Entity> hitEntities = Field.GetEntities(X, Y, typeof (IHitByWeapon));
        for (int i = 0; i < hitEntities.Count; i++)
        {
            IHitByWeapon hitEntity = (IHitByWeapon) hitEntities[i];
            hitEntity.HitByWeapon(this);
        }
    }

```

Field.GetEntities(x, y, type) returns a list of entities of that type in a specific tile. When an entity is initialized, my library gets all the types and interfaces using the following code snippet, then puts the entity in dictionaries having types and interfaces as keys:

```
public static List<Type> GetAllTypes(Entity mEntity)
    {
        List<Type> types = new List<Type> {mEntity.GetType()};
        Type[] nestedTypes = mEntity.GetType().GetNestedTypes();
        types.AddRange(nestedTypes);
        Type[] interfaces = mEntity.GetType().GetInterfaces();
        types.AddRange(interfaces);

        foreach (Type type in nestedTypes) types.AddRange(type.GetInterfaces());

        return types;
    }
...
foreach (Type type in GetAllTypes(this))
            {
                if (!Tile.TileManager.GroupedEntities.ContainsKey(type))              Tile.TileManager.GroupedEntities.Add(type, new List<Entity>());
                Tile.TileManager.GroupedEntities[type].Add(this);
            }

```

---

My library/game is relies completely on types and interfaces.

This is a good thing because I know what methods and properties entities have, and because different entities can share the same interface. I can have 20 different types of monsters, but as long as they implement IHitByWeapon they will all get killed by the player's sword.

This is a bad thing because it relies on hardcoding elements, and I cannot manipulate interfaces at runtime. Let's say I have a door element. I need it to be solid when the door is closed and to be non-solid when the door is open. If the element implements ISolid I cannot remove it. The same problem applies if I suddenly want a flying roach. I would have to code another element that implements ICanFly, because I cannot add an interface to an entity at runtime.

I've thought about using a List of stuff like "solid", "enemy", "player" - but it's not flexible enough, since I cannot have interface-like methods or properties, and I need to guess if the entity has a method or use the dynamic keyword.

---

How can I solve this problem? Is there something that lets me have the ease of use as interfaces but also the flexibility as List?

Let me know if you need more information or parts of the source code.

# Answer
> 1 votes
It seems like a backwards step to use inheritance for a entity system. Check out the Artemis framework created by Arni Arent and Tiago Costa. It's in Java, but someone has been porting it to C# (I believe they are a user here too). I can't speak for the quality of the conversion to C# since I haven't looked at it. However, the original is very nice. It uses `long`s to keep track of which entities have which components and belong to which systems (that means a maximum of 64, one for each bit). It's a pretty nice system and I learned a lot from reading the code when I was implementing my own entity/component framework. With this system it's easy to add and remove components, but as Jeremiah said, it would be better to have a solid component which can change states. That's a far better option that adding or removing components.

Further, the Artemis framework supports groups and tags. This means you can make a "Player" group or tag and treat it specially depending on the situation. There is a sample game that has its source available as well.

# Answer
> 0 votes
I would maybe let your interfaces change the properties they set. In your example, ISolid shouldn't indicate that the object is solid; it should let you set the Solid property. Then you put ISolid on anything whose solidity can change.

# Answer
> 0 votes
You're saying that since everything is defined by its type and not by its attributes then nothing can change dynamically. That's because you're (ab)using interfaces as they were attributes to put together your mix of stuff that an entity can do/be.

I get the reason why you're trying to use interfaces since you said you have some sort of a grid-base creation library.

My suggestion is to take a step back and look the whole picture: you want to cover almost any tile based game. So first off you need an expanded game logic.

In any tile based game you're going to have tiles. Fairly obvious. You may have Pawns, or even implement them as particular states for tile.

Using a set of states/attributes, maybe even 'compressing' them as other users have suggested, thus achieving some sort of finite-state machine could be the right direction since the basic game logic is pretty simple.

---
Tags: c#, tiles, entity-system, puzzle
---


# Question
Title: Elegant way to handle packet loss in a lockstep P2P RTS?
What's an elegant way to handle packet loss in a lockstep simulation peer-to-peer RTS where only player input data is sent over the network?

For example, let's say it's tick 1000 and player 1 sends a message saying that he is going to start attacking player 2 at tick 1002. All the other players receive the message except player 2 who is being attacked. Player 2 receives the message very late, at tick 1020. The other players have been running their simulation according to the fact that at tick 1002 player 1 started attacking player 2. And by tick 1010, player 2 is dead. Not only that, but by 1020 his entire dying animation sequence, according to the accurate game state, is already finished. He is completely dead.

Because the network protocol has a reliability layer which resends unacknowledged packets, player 2 eventually receives the message. He can replay the simulation from tick 1002 and arrive at the same game state: that he is dead at tick 1010 and his animation is already finished at 1020. The simulation must correct itself, moving player 2 back where he should be and setting the appropriate animation frame.

From a gameplay standpoint, what's the elegant solution here? Does player 2 immediately just jerk into a fully dead animation? Or does a little dying animation happen anyway (which would mean the game state might not truly be in sync)?

# Answer
> For example, let's say it's tick 1000 and player 1 sends a message saying that he is going to start attacking player 2 at tick 1002.

That's not how it works. What is sent is what player 1's *controls* do. Click on location, drag to here, pressed key X, whatever. You don't send specific game state like "is attacking".

The idea being that, as long as everything is synched up, everyone will be getting the same data. So if a user clicks on location X at 1002, and there's an enemy unit there, then both sides will issue an attack order.

That's how P2P works.

Also, the message doesn't say how long it should take to complete; that should be implicitly understood on both sides. You pick a latency; if it starts not being fulfilled, both sides will know it and both sides will up the latency using a common algorithm.

> Player 2 receives the message very late, at tick 1020.

If the latency of your game is 2 ticks, then Player 2 should *never* have advanced past tick 1002. It should have halted the game until it could synchronize with the other player. And Player 1 can't advance beyond tick 1002 until Player 2 tells him that he got Player 1's controller data.

P2P requires *lockstep* synchronization: each side only progresses to the next tick when it has gotten controller data for that tick from the other side. If it hasn't, then it can't get it. So each side not only needs to know what the next controller data is, but also how far the other side has advanced.

Unless you're in a LAN situation, or have really good netcode, you'll need to up your latency a bit to make this all work. Say, 75-100ms or so.

In general, the idea is this: controller data is tiny. Mouse positions on the map, clicks, buttons, etc. All very small. So you can afford to shove several "ticks" worth of data into a single packet. So each side's packet consists of:

* How far that player has progressed in terms of "ticks".
* The controller data for future actions.

Each side will *continue* to send the same controller data until the other side tells them that they've reached that "tick".

Let's say Player 1 is on tick 1000, and sends controller data for tick 1004. And this packet is lost. Next frame, on tick 1001, Player 1 will send the controller data for tick 1004 *and* 1005. That packet may gets through. Player 1 gets to 1002, but hasn't gotten an acknowledgement from the other guy about tick 1004. So he sends the controller data for ticks 1004, 1005, and 1006. Player 1 gets to 1003, and he receives acknowledgement that Player 2 got ticks 1004 and 1005. So this frame, Player 1 sends only the controller data for ticks 1006 and 1007. And Player 1 is cleared to advance through 1005.

This uses a 4-tick latency.
> 5 votes

# Answer
I have the same concern, and I have been thinking about it long time... I'm going to expose my thoughs though maybe not a good approach...

1. Fixed Point Math: I think is a must to keep sync the simulation for every player.
2. When there is an input at tick 1000, you should estimate the effective tick for that action... if you consider a ping of 200 ms and your tick duration is 30ms, the tick could be (2 + (200ms x 2) / 30) = 15.
3. You send a message to every player proposing that input for the estimated tick at 1015
4. Every player has to validate that action sending an acknoledgement message back.
5. When the 1015 tick is reached, if any of the players has not been validated... stop the simulation... you have two options: try to validate again or Kick him.

if you don't want to stop simulation at first waiting for every ack, you have to be able to rewind and sync simulation to an older tick.

This can be acomplished in several ways, but I think the easier can be keep a copy of each object state for each tick in the last 2 seconds.

```
struct ObjectState {
    int Life;
    fint Pos;
    ...
}

class GameObject {
    const ObjectStateCount = 2000 / 30;  // 2 seconds / 30 ms tick
    ObjectState[] State = new ObjectState[ ObjectStateCount ];

    void Update(int PrevTick, int NextTick)
    {
       // Generate right states from PrevTick to NextTick,
       // Usually one tick of difference
       int BaseTick = PrevTick;
       int Tick = -1;
       while (Tick!=NextTick) {
          Tick = (BaseTick+1) % ObjectStateCount;
          UpdateOneStep(BaseTick, Tick);
          BaseTick = Tick;
       }
    }

     void UpdateOneStep(int PrevTick, int NextTick) {
         State[NextTick].Pos = State[PrevTick].Pos + Velocity...
         ....
     }
}

```

This way you can easily revert the simulation to an old state where everyplayer were sync.

Every player that is sync with simulation will see the right animations, but player that is lossing packets will realize that is lagging because the inconsistencies in the animation. I think there is no matter with that.
> 0 votes

---
Tags: multiplayer, rts, synchronization, packet
---


title: How do fluid dynamics work?

text:
# Question
Title: How do fluid dynamics work?
How would I go about implementing fluid dynamics in a game, such as can be seen in this video?

# Answer
It looks like the game is just using a fairly simple particle fluid simulation. Basically, the "water" consists of little balls that move according to Newtonian mechanics, fall under gravity and repel each other over short distances. The blobs of water are then drawn around the particles using something like metaballs to smooth the surface.
> 18 votes

# Answer
Looks very similar to the water in PixelJunk shooter. There is a PDF on how the water was done:

http://www.maisonikkoku.com/yonder/SIGGRAPH2011/SlidesForADBAD.pdf ^^link has gone dead... you can get the cached version from google search, but if you're very very lazy, then you may view this copy if you need to: http://dl.dropbox.com/u/203979/SlidesForADBAD.pdf
> 4 votes

# Answer
Try to read great serious of articles from Intel about fluid simulation for video games http://software.intel.com/en-us/articles/fluid-simulation-for-video-games-part-1/

And also try this, fluid simulation in Alice game http://developer.nvidia.com/content/fluid-simulation-alice-madness-returns
> 0 votes

---
Tags: physics
---


# Question
Title: The normal vector to a plane ax+by+cz+d=0?
I am calculating the normal vector to a plane ax+by+cz+d=0

According to the book:

The normal vector N is often normalized to unit length because in that case the equation

```
d = N ⋅Q + D

```

gives the signed distance from the plane to an arbitrary point Q. If d = 0, then the point Q lies in the plane. If d \> 0, we say that the point Q lies on the positive side of the plane since Q would be on the side in which the normal vector points.

How to get the N (Normal vector)? Thank you

# Answer
From MathWorld:

Given the plane

Then the normal vector is

The normal unit vector **n** is given by:

Therefore, for the plane `5x+2y+3z-1=0`,

The normal vector **N** is

> **N** = \[5,2,3\]

The magnitude **|N|** is

> **|N|** = sqrt(5^2 + 2^2 + 3^2)
>
> **|N|** = 6.1644

The normal unit vector **n** is therefore approximately:

> **n** = **N** / **|N|**
>
> **n** = \[0.8111, 0.3244, 0.4866\]

which you can check by measuring the length of **n**.

Code:

```
import math

def mag(V):
  return math.sqrt(sum([x*x for x in V]))
def n(V):
  v_m = mag(V)
  return [ vi/v_m for vi in V]

```

In an interactive python shell:

```
>>> N = [5,2,3]
>>> mag(N)
6.164414002968976
>>> n(N)
[0.8111071056538127, 0.3244428422615251, 0.48666426339228763]
>>> mag(n(N))
1.0

```
> 13 votes

---
Tags: mathematics, vector
---


title: Client Server what do i need?

text:
# Question
Title: Client Server what do i need?
Simple question

if the Client is Android Game App

That send data to the server for Storing/Recalling Data as well as calculating data?

I hear sql is good for simple database stuff.what is good for rts game or street fighter game ? or an fps game?

do i have options ?

# Answer
> 0 votes
It depends on what you want to store.

## Concerning the gamestate

For action games (as opposed to turn by turn games) you will need to run the gamestate at a decent speed (for performance) and more importantly for the player's experience you will have to update the clients regularly (multiple times per second).

Therefore a solution based on a C/C++ server would be preferable. But in the end any language able to provide good performance and proper network socket communication is fine.

The data should be stored in memory during the game session with eventual saves to the server's disks during the session or when players disconnect if you want persistent or semi-persistent game worlds.

You can use SQL to store data if most of it is relational. But if you want to store the gamestate and things that are better stored/retrieved in binary form then you will be better off storing the "save games" in files as you would on the clients.

## Non action games and other data

If you have a lot of relational data, data about players, about game sessions, results, etc, then you can use an SQL database.

When it comes to turn based games, leaderboards and non gamestate related features any scripting language and database will do. But this is a separate subject.

# Answer
> 0 votes
You would need a server architecture, in java world its common to use a web archive on a suitable hosting site. These usually would come with a database and would allow you to store any necessary data using SQL.

You also have the option to use mobile game frameworks that come with server hosting like Moai or any of the other similar services.

This is a fairly advanced starting point, if you don't understand my answer you may want to start out making some simpler one player games first, while reading up on databases and server architecture.

# Answer
> 0 votes
I won't talk about architecture since that has been discussed by the previous two posters, I would check out Kryonet for your Client/Server needs.

It's pretty lightweight and speedy, and is perfectly suitable for action games. It uses it's own serialization system called Kryo.

Its definitely compatible with android and better yet: It's open source! Check em out.

Kryonet: http://code.google.com/p/kryonet/ Kryo: http://code.google.com/p/kryo/

---
Tags: java, android, game-design, server
---


title: Camera Coordinate To Screen Coordinate

text:
# Question
Title: Camera Coordinate To Screen Coordinate
I want to convert the camera coordinate to screen coordinate. I have asked this question because my camera is 48m wide and 32m high but my screen is 480x320 pixels. So whatever collision point I get those are based on camera. Also I like to mention that my camera set at center of the screen. So I get (0,0) coordinate at middle of the screen. At collision time I put some particle effect but now that particle effect not at correct place in the screen. So someone from community please help.

# Answer
How about using the project-method in the camera class.

```
camera.project(Vector3 worldPoint)

```

That projects the vector cameraPoint from world/camera coordinates into screen/window coordinates. The reverse method is camera.unproject(Vector3 screenPoint). Have a look at the libgdx camera class.
> 7 votes

# Answer
Taken from http://www.badlogicgames.com/wordpress/?p=2032

I'm only assuming that this will help based on your question...

```
Ray pickRay = cam.getPickRay(Gdx.input.getX(), Gdx.input.getY());
Intersector.intersectRayPlane(pickRay, xzPlane, intersection);

```
> 2 votes

# Answer
What you need to do is to translate the camera coordinates into viewspace.

In this particular case your Camera coordinates go from \[-24,-16\] to \[24,16\] and you want that to translate to \[0,0\] to \[480,320\].

Pseudo code:

```
view.X = camera.X * 10 + view.width / 2
view.Y = camera.Y * 10 + view.height / 2

```
> 1 votes

---
Tags: libgdx
---


# Question
Title: Making a Point Light follow a cube (Unity)
I'm trying to have a point light positioned directly above a cube follow wherever the cube goes. However, it doesn't move at all. This is my code for the light:

```
using UnityEngine;
using System.Collections;

public class SpotlightController : MonoBehaviour {

// Use this for initialization
void Start() {

}

void OnGUI(){
    GUI.Label(new Rect(20,50,500,20), "(" + transform.position.x.ToString() + ", " + transform.position.y.ToString() + ", " + transform.position.z + ")");
}

// Update is called once per frame
void Update() {
    GameObject cube = GameObject.Find("Cube");
    float xlocation = cube.transform.position.x;
    float zlocation = cube.transform.position.z;

    transform.TransformPoint(new Vector3(xlocation,transform.position.y, zlocation) * Time.smoothDeltaTime);
    //transform.Translate(new Vector3(xlocation, 0, zlocation));
}
}

```

# Answer
> 1 votes
This is untested code, but I think it should be as simple as this:

```
void Update() {
    GameObject cube = GameObject.Find("Cube");
    transform.position = cube.transform.position;
}

```

# Answer
> 7 votes
You can also do it without code. Attach the point light to your Cube object and set its relative position.

---
Tags: unity, lighting
---


title: SAT and then what?

text:
# Question
Title: SAT and then what?
I am on my way to make another Arkanoid game but this time I decided that I want it a little bit more realistic than just checking intersections between AABB and inverting one vector's component on collision.

So I found SAT but I don't know how can I change direction of the ball in realistic matter. Maybe I'm wrong but it seems like knowing MTV doesn't give me much.

So my question is what algorithms should I use to make it realistic? I also care about possibility of spinning ball with a pallet. I don't know how to do it exactly but I guess I will need to consider acceleration of the pallet.

# Answer
> 1 votes
Using SAT for AABBs is an overkill, though it doesn't hurt to learn it, i guess.

I don't know what you're looking for. From SAT you'll have a vector that's a normal to the surface you're bouncing of off, all you have to do is calculate your new speed vector based on it, it's not complicated. I can tell you how i calculate it, but where's the fun in that?

After that if you want to calculate, i guess, "bounciness" of the surface or the ball, you add a vector that's perpendicular to the surface. If you want to add some friction then you can add annother vector, but this time one that's pararell to the surface. For a "spin", again you're adding a vector that's pararel to the pad, for a breakout game, depending on what part of the pad the ball landed on. So you check collision with the pad, you check what part it is, it can be regions, it can be % based, whatever you like, and you just add a vector, increse or decrese the speed probably, just put a limit on this so the player can't screw himself over. Giving you numbers won't help, you have to experiment alot with "simple" models like these.

For more complicated calculations you'll need a physics book and a realistic model probably.

---
Tags: collision-detection, collision-resolution, separating-axis-theorem
---


title: Directional and orientation problem

text:
# Question
Title: Directional and orientation problem
I have drawn 5 tentacles which are shown in red. I have drew those tentacles on a 2D Circle, and positioned them on 5 vertices of the that circle. BTW, The circle is never be drawn, I have used it to simplify the problem. Now I wanted to attached that circle with tentacles underneath the jellyfish. There is a problem with the current code but I don't know what is it.

You can see that the circle is parallel to the base of the jelly fish. I want it to be shifted so that it be inside the jelly fish. but I don't know how. I tried to multiply the direction vector to extend it but that didn't work.

```
// One tentacle is constructed from nodes
// Get the direction of the first tentacle's node 0 to node 39 of that tentacle;
   Vec3f dir = m_tentacle[0]->geNodesPos()[0] -  m_tentacle[0]->geNodesPos()[39];

    // Draw the circle with tentacles on it

    Vec3f pos = m_SpherePos;

    drawCircle(pos,dir,30,m_tentacle.size());

    for (int i=0; i<m_tentacle.size(); i++)
    {
        m_tentacle[i]->Draw();

    }

 // Draw the jelly fish, and orient it on the 2D Circle
    gl::pushMatrices();
    Quatf q;
    // assign quaternion to rotate the jelly fish around the tentacles
    q.set(Vec3f(0,-1,0),Vec3f(dir.x,dir.y,dir.z));
    // tanslate it to the position of the whole creature per every frame
    gl::translate(m_SpherePos.x,m_SpherePos.y,m_SpherePos.z);
    gl::rotate(q);

    // draw the jelly fish at center 0,0,0
    drawHemiSphere(Vec3f(0,0,0),m_iRadius,90);

    gl::popMatrices();

```

# Answer
I think you want to move the "circle" position along the line defined by dir.

```
Vec3f pos = m_SpherePos + dir.Normalise() * -10;

```
> 1 votes

---
Tags: opengl, 3d, mathematics
---


# Question
Title: How common are Rete algorithms in game development?
I was looking through some game AI and general AI texts and a couple of them touched on using the Rete algorithm for rule systems. Is this commonly used? I'm having trouble justifying the extra effort to create a complex Rete decision tree versions a simpler straightforward one.

Is this a worthwhile thing to implement for when my application (or future applications) grow in scale?

# Answer
> 7 votes
The answer is completely dependent on your actual game. The correct answer is going to be, "if you need them, you have to implement them, and if you don't, then don't bother."

A vast majority of AAA games don't have any kind of decision tree at all, so by all means, implement whatever you need for your specific game design, and no more.

Just remember that with games, good AI has *nothing* to do with making the AI actually intelligent. It's all about making the AI seem human and believable and interesting. 90% of that is done with animations and voice acting, not AI. Your AI can be dumb as mud, but if the AI actors choreograph their "reactions" and are given personality with voice and characteristic movements then the players will be deeply engaged with them.

# Answer
> 2 votes
Rete itself can be heavy, because it's determining all partial matches for all rules, regardless of whether those eventually execute or not. Depending on the type of rules you have, LEAPS may be a better algorithm to implement.

For bonus points, if you have the time it is possible to develop an algorithm that merges the benefits of thte LEAPS algorithm with the Rete implementation.

---
Tags: ai
---


title: Dealing with string memory pollution

text:
# Question
Title: Dealing with string memory pollution
Consider following example. I have a title screen for a game which displays top scores list, and some other text. The Update method looks like (simplified):

```
// remove all text
textList.Clear();

// add scores
foreach(var sc in scores)
{
    textList.Add(new GameText(string.Format("{0}: {1}", sc.Name, sc.Score));
}

```

If I understand all correctly, then each frame 10 new strings are created, polluting memory at high rate. Currently I fight it with creating a cache:

```
// this is a class level variable, outside of Update method of course
List<GameText> scoreCache = new List<GameText>();

// remove all text
textList.Clear();

// add scores to cache if needed
if(scoreCache.Count == 0)
{
    foreach(var sc in scores)
    {
        scoreCache.Add(new GameText(string.Format("{0}: {1}", sc.Name, sc.Score));
    }
}

// get fast copy from cache
// no new strings created until score cache is invalidated
textList.AddRange(scoreCache);

```

I wonder, if there are some other reliable solutions and patterns to this common, as I see it, problem?

**Update**. As @JasonH correctly mentioned, there is no need to update list each time at all, so now `scoreCache` is initialized once in a `LoadContent`-like method which is called once before main Game loop starts.

**Update 2**. Another similar problem was with a debug text layer output which displays FPS, Total game time, etc. on top of all screens. Despite using StringBuilder, intermediate strings were required for creation of final debug text for each frame. I've decided to solve it this way, since I don't actually need per frame response, I update this only each second:

```
private void PrepareDebugText(GameTime gameTime)
{
    this.refreshAccumulator += gameTime.ElapsedGameTime.TotalMilliseconds;

    // if required time is not elapsed yet
    if (this.refreshAccumulator < RefreshIntervalMs)
    {
        // do nothing
        return;
    }

    // reset accumulator
    this.refreshAccumulator = 0;

    // create debug text below
    // ...
}

```

Applying this two approaches gives following:

* reduced garbage collection frequency by 2 (from 60-70 seconds to 130-140 seconds)
* reduced peak heap allocation from 3,4 Mb to 1,5 Mb
* reduced short life objects to less than 1% from more than 50%.

Now I'm satisfied.

**Update 3**. @GeorgeDuckett found an interesting approach example how we can further reduce string pollution then output is integer number.

I also would like to clarify why strings are so specific in XNA (.NET). Despite being a reference type, on each assign (i.e. `=`) operation new string is created instead of assigning reference. This can produce not very obvious amounts of garbage strings.

# Answer
> 1 votes
So here is general tips:

1. Don't create static (i.e. which doesn't change) strings in Update, create then in Initialize or LoadContent.
2. If string is changed occasionally then cache it, and invalidate cache on text change.
3. Finally, try to reduce string update rate if applicable. For example if you displaying game time with seconds precision, there is no need to update it more frequently then once in a second (this reduces string creation rate by your FPS value).
4. Suggested by @GeorgeDuckett use StringBuilder optimized routines for displaying integer numbers. My implementation can be seen here.

# Answer
> 0 votes
Generally, what you want to do is create an object pool. It is like your buffer, but managed.

In practice, you would create the pool with a set number of objects; instead of throwing the object out when you are done, you set it to "inactive" and give it back to the pool. When you need to create a new object, just ask the pool for one. It will give you an inactive one and set it's state to active for you.

Keep in mind that you want to carefully tune your pool to contain *just enough* objects. Pretend you give it 10,000 strings. The GC is going to have to iterate over all 10,000 to see if any are not referenced.\* Being that they all will be, it will have been wasted GC time. The best thing is to tune it to just what you need.

See a good implementation of a generic pool here, and you can look at his implementation of an interpolator on how to use it. Let me know if you have any questions.

<sup>* There are exceptions. I **think** if you use an array to hold them then it is a bit different. Don't quote me on that though</sup>

---
Tags: xna, optimization
---


# Question
Title: Changing background texture by drawing on it?
Actually I'm sorry for the title, I'm not sure which short phrase will describe situation best. I'm porting (or remastering, I don't know which word suits better, maybe both) a Win32, pure C, DirectX 8 game to XNA. Here is the problem I'm facing now.

The game background represents dirt through which player can dig, leaving the tunnels in it. The background is erased *literally* from a background bitmap array (which is static) by applying a "dig step" mask forming a new background picture:

From that little knowledge I have currently on XNA, I assume that it's hard to mimic this approach and modify a background texture in `Update` method. So I was thinking about storing an array of "tunnels" data and draw tunnels above background. This however seems not so elegant as the original approach. You see, tunnel form depends on direction, so I would need to store following information for a cell: 1) directions of tunnel (from 1 to 4), 2) dig amount (for each direction) ranges from 0 to 5.

So question is, what is a good way to implement that? Am I on a right way?

P.S. BTW anyone can try and see it in action!

# Answer
> 3 votes
Don't think this is the best way to go about what you are trying to do but is actually very easy in XNA. Check out how RenderTargets work. Below is a simple Example.

Assuming `background` is the image in your example that is being drawn each frame.

```
var _renderTarget = new RenderTarget2D(GraphicsDevice, background.width, background.height);
var _spriteBatch = new SpriteBatch(GraphicsDevice);

// While the render target is not null all draw calls will only
// affect the rendertarget only not the backbuffer (which is what you see next frame).
GraphicsDevice.SetRenderTarget(_renderTarget);

// Actually doesn't matter in this example but this will default every pixel
// to this color
GraphicsDevice.Clear(Color.Transparent);

_spriteBatch.Begin();

// Draw the current background
_spriteBatch.Draw(background, Vector2.Zero, Color.White);

// Draw on top of it to modify is however you wish.
// You can actually draw a mask but you can just draw a black texture
// with transparent edges over it.

_spriteBatch.End()

//Return to drawing to the backbuffer
GraphicsDevice.SetRenderTarget(null);

//Set the background to the render target that holds its modification
background = _renderTarget;

```

# Answer
> 1 votes
Here's my way of adding transparent holes in your background. It uses a simple pixel shader that subtracts the values. I'm not sure this is the best way, there may be some tricks possible simply by using a custom BlendState and the Subtract function.

What I did was create two rendertargets. One holding your dirt. This could just be a large texture, however, to get it tiling dynamically, rendertargets was a good choice.

First I prepare them in the LoadContent override.

```
...
    // Prepare the dirt layer.
    this.earthRenderTarget = new RenderTarget2D(this.GraphicsDevice, 1280, 720);
    this.GraphicsDevice.SetRenderTarget(this.earthRenderTarget);
    this.GraphicsDevice.Clear(Color.Black);
    this.spriteBatch.Begin();
    for (var x = 0; x < (1280 / this.earth.Width) + 1; x += 1)
        for (var y = 0; y < (720 / this.earth.Height) + 1; y += 1)
            this.spriteBatch.Draw(this.earth, new Vector2(x * this.earth.Width, y * this.earth.Height), Color.White);
    this.spriteBatch.End();

    // Prepare the "hole" layer, with 100 random holes.
    this.maskRenderTarget = new RenderTarget2D(this.GraphicsDevice, 1280, 720);
    this.GraphicsDevice.SetRenderTarget(this.maskRenderTarget);
    this.GraphicsDevice.Clear(Color.Transparent);
    this.spriteBatch.Begin();
    var random = new Random();
    for (var i = 0; i < 100; i += 1)
        this.spriteBatch.Draw(this.chunkMask, new Vector2(random.Next(1280), random.Next(720)), Color.White);
    this.spriteBatch.End();
...

```

Here's the pixelshader code I used. It just subtracts the individual color components.

```
texture Mask;

sampler textureSampler  : register(s0);

sampler maskSampler = sampler_state
{
    Texture = <Mask>;
};

float4 MaskFunction(float2 texCoord : TEXCOORD0) : COLOR0
{
    float4 color = tex2D(textureSampler, texCoord);
    float4 mask = tex2D(maskSampler, texCoord);

    return color - mask;
}

technique MaskTechnique
{
    pass MaskPass
    {
        PixelShader = compile ps_2_0 MaskFunction();
    }
}

```

And finally, I combine the two rendertargets in the Draw override like this:

```
...
    this.GraphicsDevice.SetRenderTarget(null);
    this.GraphicsDevice.Clear(Color.CornflowerBlue);

    this.maskEffect.Parameters["Mask"].SetValue(this.maskRenderTarget);
    this.spriteBatch.Begin(SpriteSortMode.Deferred, null, null, null, null, this.maskEffect);
    this.spriteBatch.Draw(this.earthRenderTarget, Vector2.Zero, Color.White);
    this.spriteBatch.End();
...

```

You can see it in action here.

Now, you'll need to implement a rendertarget swapper to further edit the "hole" rendertarget, but I'll leave that as a challenge for you.

---
Tags: xna, architecture
---


# Question
Title: Connect-three game: Increasing level-of-difficulty as play progresses
I'm writing a connect-three type game (think Chuzzle, but without all those nasty locks, and with no big chuzzles) and I'm trying to figure out how to increase the level of difficulty as play progresses.

As it stands, I've been adding an additional block colour/shape/type when the player advances to another multiple of num\_blocks\*1000, and it seems to work moderately well, aside from the fact that I keep running out of new colours/shapes/types that look distinct enough on the screen.
(currently, blocks only differ by colour, but I'm planning on adding a shaped highlight to help differentiate)

I'd like to know if manipulating the probabilities of each block type based on the blocks surrounding the new block in an attempt to minimize the chances of cascades and other types of easy matches would be a good idea.

# Answer
> 1 votes
Manipulating the probabilities seems the right thing to do and also adding some sort of prediction to the algorithm you're using to increase the types/colors would help.

Just as most board games do, predicting what's going to happen in a set number of time slices (turns, moves, etc) should provide a better 'opponent' for the player. Finding actually harder patterns should help if you're running out of colors too.

Avoiding repetitive patterns then becomes the next problem to solve, since a bad pattern generation could lead to a repetitive game.

Anyway, as stated above, having a bunch of people testing it is surely a good idea.

Edit:

The order, amount and timing of appearance would define a filling pattern in this instance.

I.E: If you have 2 blue tokens next to each other, to clear them you need another blue token. If your algorithm is preventing the third blue token from appearing too soon or too close, then the player is forced to search for another move.

If the game is time based, than postponing the appearance of any third token will make it harder to get a higher score, if it's moves based than increasing the distance of the third token will have the same result.

The needed algorithm should check the neighbors of the existing tokens and keep modifying such a pattern.

---
Tags: game-design, levels, difficulty
---


title: Excluding Background from Color Picking

text:
# Question
Title: Excluding Background from Color Picking
I've implemented picking based on color coding, but I don't want the background color to be pickable. Is there any way in openGL (2.x) to exclude the background color? For some reason, doing glClear(GL\_COLOR\_BUFFER\_BIT) just before rendering in "color picking" mode, excludes the background in windows but not in Linux.

I'm using glut btw.

# Answer
If you are rendering with one different single color for each pickable item, then just compare the color under the mouse against the background color.
> 2 votes

---
Tags: opengl, color, glut, picking
---


title: Scene Graph Theory

text:
# Question
Title: Scene Graph Theory
I have a scenegraph that represents the whole world. However, at the moment if there are multiple copies of the same scene graph (aka the same model) it will just create a new scenegraph linking. This works, however, the loading time is insane. Which is to be expected. I have tried to load the model's scene graphs and simply just have the world link to these. However, when I need to travel up the scenegraph the model doesn't know anything about the world unless you count the last one that was using it. Making it impossible to render the models in the right place as everytime you travel up the scenegraph you get into the problem of not knowing where to go from the models node to get to the world node.

For example I have a scene graph for each model in the world, like a boat has a scene graph. If I want multiple copies of the boat in the world at the moment I will have to load the boat x amount of times. Which I don't want. I want to be able to specify the boat, load it, then have a world scenegraph which specifies down at the leaf nodes (Load boat). What is a design that would solve this problem?

# Answer
> 7 votes
You seem to be treating your scene graph as a tree - each scene contains N boats, each of which contains its own copy of the "boat" scene graph, etc. This is not fundamentally wrong, but can certainly be improved upon. The following diagram illustrates my understanding of your current approach, for a scene with two boats1:

Rather than storing N copies of the "boat" scene graph if you have N boats, instead create N copies of a "SceneGraphReference" node that all reference a single copy of the "boat" scene graph. Each such node should maintain its own position/rotation/scaling etc information, so that the bulk of the information (the "boat" scene graph) is only stored once, but the information necessary to draw multiple copies in different places (position etc) is stored as often as necessary. This would look something like the following, for the same example with two boats:

To put this in more technical terms, your current approach is an N-ary tree: consider using a unidirectional acyclic graph instead2.

---

1. *Please excuse my (minor) abuse of UML diagrams.*
2. *Interesting things can be achieved by relaxing the unidirectional and acyclic restraints (i.e. using a plain old unrestricted graph), but that's a discussion for another time.*

# Answer
> 0 votes
I assume you're doing a top-down traversal of the scene graph, e.g. for frustum culling or similar. You just need to remember where you came from when descending into the instanced scene graph (the boat in your example). You can do this by maintaining a stack of the nodes from the root to the current node, pushing when you descend a level and popping when you ascend. That way the stack at any point contains a complete record of how you got to the current node. (This is assuming a depth-first traversal order, which is the most common, I think.)

---
Tags: scene-graph
---


# Question
Title: Physics motor on servers, How a billiard server works?
i'm trying to figure how a phisics game like billiard works in server side . I'm asking this cause i know how to achieve this in a client , but if i use a phisics motor i think it could be very heavy for a server when i want to have many people in the server.

When i see this type of games, it use to be really fast , thinking that server is controlling the movements of course . Cause any other way maybe from client you could have been doing cheats.

Then my questions are:

The server sends in this case, all ball movements? Are the server trusting in clients? In this case : How to be sure a phisics motor doesn't have little error. (float decimals differences)

And globaly : How this type of server works?

# Answer
As with most things in game development, there are a number of ways to tackle this issue. The most common way I have seen is to have the client-side physics be completely "dumb."

The simulation on the client side is merely reacting to data delivered by the server and inputs from the client side are sent to the server, interpreted and distributed to all connected clients as data. You can easily do very basic cheat detection during this "interpretation" step by ensuring that the move the client is attempting to make fits within the rules of your game. For instance, in the context of your billiards game, if the server currently has `ball1`'s position as (x:26, y:50) in the game world and suddenly fields a request to move `ball1` from (x:35, y:50), you know something strange is going on. Now "something strange" could be either network latency, dropped packets or player tampering and it's up to you to decide how to determine the cause and handle it.

This article by Gaffer on Games (really great source), can explain in much more detail than I ever could, but these are the essential steps:

* **Player** presses a key or invokes an action.
* Action is sent to the **server**.
* **Server** interprets the action for the **player**.
    + **Server** checks if the action is valid.
    + If valid, **server** applies action to all relevant game objects.
* **Server** sends updated data on all affected objects to all connected **players**.

With this implementation, the drawback is that because *real* game data is only flowing one way (server to player), and network transmission is never perfect, the client has to do some guesstimating. This is called **client-side prediction** and is covered in the section of the same title in the article linked above.

Even though you're not working with the UnrealEngine, their Networking Overview article does an excellent job of explaining how their server-client system works and how they tackled certain challenges that exist in managing multiple objects and states over network.

Hope this helps!
> 3 votes

---
Tags: server
---


title: Grouping units in world space

text:
# Question
Title: Grouping units in world space
I figure that I intend to generate, for group orders, one optimal path, and then use a flocking algorithm to "glue" the units together as they all follow this one optimal path. However, a naive implementation would fail if, for example, the units were ordered from two distinct locations- two optimal paths would have to be computed. So for a group of units, I need to group them into subgroups which can all share the same optimal path.

At the moment, what I'm thinking is to pick an arbitrary unit in the group, and then pick all units in a certain, relatively small radius. Then for every unit in that radius, I increase the radius.

Are there any existing algorithms for grouping units into subgroups?

# Answer
If you are looking for an academic solution have a look at cluster analysis, possibly combined with this other Wikipedia page: Determining the number of clusters in a data set.

Keep in mind these algorithms are typically designed for processing highly-dimensional data, not unit positions in 2D/3D, so be sure not over-engineer your solution based on this.
> 1 votes

# Answer
Not entirely sure if this is what you're describing, but there is an article in Game Programming Gems 7 entitled "A Sketch-Based Interface to Real-Time Strategy Games" (Chapter 1.6) that describes a method for moving RTS units using potential fields. Essentially, it says that if you have a multi-segmented path that can be represented by a vector, or series of vectors, where the magnitude of these vectors determines the relative speed of the affected units, you can project that vector onto the terrain, divide it into an arbitrary grid of 2D cells, and have the units infer their movement speed and direction from the vector in the cell they are standing on. I drew a quick little diagram to illustrate what I'm describing:

The algorithm can be easily adjusted to make all units within the affected area stick together by ensuring that the flanking vectors are angled slightly towards the original vector path when they are generated. This method produces a more organic and fluid method of unit control which may be what you're looking for.
> 1 votes

---
Tags: c++, path-finding
---


# Question
Title: Different types of memories which a graphics card has
I've been googling this around and yet nothing showed up but some articles from middle ages which were talking about Gforce mx and ... . My question is just this: what are the different memories in a high-end graphics card and what is their size and usage?

# Answer
Generally in the old days you'd read things like how a Voodoo 2 might have 2 mb of texture memory per TMU and 4 mb of framebuffer memory, and everything would have been segmented in a similar manner on other models. I suspect that this is what you might be asking about.

That kind of setup doesn't exist any more.

Since the late 90s a GPU has had unified memory. To take another Jurassic piece of kit as an example, a TNT might have been specced at 16 mb, but there was no segmentation. If textures needed (say) 10 mb, they could take 10 mb. If the framebuffer needed 12 mb it could likewise take all 12. All modern GPUs are like this.

There was a certain art to programming for the old way. Looking through the old Quake 2 source code, for example, I can see that it always bound it's lightmaps to GL\_TEXTURE1, even when building them at load time - quite clearly to ensure that the texture always stayed in the memory space which was segmented off for that TMU.

But by and large it's a good thing that we don't have to deal with this kind of thing nowadays.
> 1 votes

# Answer
There are memories where you have read/write access to it
like Global memory / DRAM and others which are controlled by the GPU itself
like Texture and Instruction Cache, etc.

I use the Fermi architecture for this example.

## Read-/Writeable:

Global Memory (DRAM)
\- Only memory on its own chip
\- Very big (many gigabytes)
\- but slow to read/write and higher latency

Register file
\- smaller compared to DRAM (Fermi: 32768 x 32-bit = 128KB per SM)
\- fastest memory available \- can only be read/wrote to through ptx code

Shared Memory
\- shares space with L1 Cache
\- can decide between bigger Shared Memory (48 KB shared memory and 16KB L1) or bigger L1 Cache (48KB L1 and 16KB shared memory) (not with DX11 usage which needs 32KB shared memory)

## Controlled by GPU:

Instruction Cache
L1 Cache L2 Cache
Constant/Uniform Cache
Texture Cache
> 0 votes

---
Tags: gpu
---


# Question
Title: How to calculate the direction a ball must bounce
I have a tile engine I have made. I can detect collision between the ball(the player) and the tiles. When a collision is detected all the colliding tiles are stored inside a list. My question now is, how do I figure how should I change the velocity of the ball using the collided tiles? I tried to figure out a way to calculate the direction the ball is hitting but I am lost.

# Answer
The ball's new velocity will be it's incoming velocity reflected about the collision normal. Assuming you already have the normal, `n`, you can reflect the vector `v` about `n` using the formula:

```
reflect = -v + 2*(v*n)*n

```

Where `v*n` is the dot product.

To further get into the pseudo-physics, you might want to add in some damping to the collision response in order to simulate energy lost to heat and sound:

```
reflect *= 0.8

```

This value, `0.8`, is often referred to as the coefficient of restitution, in case you want to do more research. It can really be anything you want, and is more representative of how bouncy the ball in question is.

A final heads up: things will get more complicated if your ball has angular velocity.
> 4 votes

# Answer
If you already have some basic physics knowledge, you just need the normal of the surface collided by the ball and the original speed.

If S is the original speed, N is the normal and Aplha is the angle of those 2 vectors, then if Cos(Alpha) =\> 0 the ball vector is moving away from the surface and you should let it go.

Otherwise, adding a speed of S\*-Cos(Alpha) to the ball in a direction parallel with the surface's Normal will get you a simple rigid bounceback effect.

If it's parallel (Cos == zero) it's your choice to apply any resistance, same goes for any coefficient due to the tiles being elastic or whatever effect you want to add.

Edit: If the ball is colliding with more than 1 surface, just calculate the resulting collision force for each surface, combine them together and you'll get the resulting force.
> 1 votes

---
Tags: xna, c#, collision-detection, tiles, tilemap
---


# Question
Title: Is screenplay for a low budget to no budget indie game necessary?
i'd love any advice about knowing if screenplay for indie games are necessary or not.

i've seen loads of successful and unsuccessful games that dont require them,

the only issue is, im a 3d artist not a writer, and in triple A title movies there are a max of 100 pages of screen play, though in games its around 600 pages.

thank you for any help!

# Answer
> 7 votes
### No, it isn't necessary.

You're an indie developer. Do what you like. You don't need to write that much script if you don't want to, and who's going to make you? Not your customers, that's for sure. You said it yourself: You've seen loads of successful games that don't require them (so clearly you don't need a screenplay to succeed), and unsuccessful games (so clearly having a screenplay isn't critical to success).

Do you need *dialog?* Up to you! Not necessarily. Heard of **Minecraft**? **Tetris**? Do you think **Team Fortress 2** \- a game whose only dialog consists of occasional outbursts by the classes - would have a screenplay? (of course its comics would; forget those)

Do you need *a script*? If you have dialog it would be handy to keep it written down so you don't forget it, yes.

Does your script need to be written *in screenplay format*? Write it in whatever format works for you - it doesn't necessarily need to be formal screenplay format. Triple-A movies have a stigma around being written like movies, with gameplay only there to shepherd you between cut scenes which tell the actual story. **Half-Life**, on the other hand, has no cut scenes, with its story told purely during the gameplay. A screenplay format might not have worked for them. A lot of independent games don't do it the way triple-A games do either: this is just my opinion, but I think that's because the independent developers *understand how to tell a story in a game* and the triple-A studios, on the other hand, do not.

Does it need to be *100 pages*? ... No, of course not. **Super Meat Boy** and **Braid** have almost no dialog at all. **Magicka** and **Eufloria** have moderate amounts of dialog. **Bastion** and **Cave Story** have a lot. Take your pick! Do what suits you and your game.

# Answer
> 1 votes
Only if your game has a strong advancing narrative. A screenplay is a way to prepare the narrative ahead of time, so that it's examinable only on it's own merits and flaws. If your game has a central narrative that you care about and want it to be well-written - yes, do a screenplay. If not, there's nothing to actually write.

---
Tags: 3d, game-design
---


# Question
Title: How do I dynamically reload content files?
Is there a relatively simple way to dynamically reload content files, such as effect files?

I know I can do the following:

1. Detect change of file
2. Run content pipeline to rebuild that specific file
3. Unload ALL content that was loaded
4. Load all content

And use double references to reference content files.

The problem is with step 3 (and step 2 isn't that nice either). I need to unload everything because if I have model `Hero.x` which references `Model.fx` effect, and I change the `Model.fx` file, I need to reload the `Hero.x` file which will then call `LoadExternalReference` on `Model.fx`.

Has someone managed to make this work without rewriting the whole `ContentManager` (and every `ContentReader`) and tracking calls to `LoadExternalReference`?

# Answer
> 0 votes
So current solution that i use is following:

I have two projects:

**Continuous Pipeline**

1. Checks for changes in content pipeline project
2. Rebuilds changed item
3. Moves produced .xnb files to game content directory

*(this approach won't work for things like .fxh and other stuff that links file in non standard way)*

**Game**

1. Checks for changes in game content directory
2. Unloads all loaded assets *(this is nescessary because I have my model reference effect files)*
3. Reloads all previously loaded

(Building game is set to not build content project)

*What asset reference what can be found by storing ContentManager.Load calls, because thats what is called when content reader finds external reference*

# Answer
> 1 votes
I don't think this is a very common approach since the content build system is not redistributable (although some projects appear to be working around this limitation: Effect generator and XNA content compiler).

Also, here's another project that you might find interesting/useful: Content tracker. I'm not 100%, but believe it may help address some of your concerns regarding limitation 3.

---
Tags: xna, xna-content-pipeline, hot-reload
---


# Question
Title: Dealing with 2D pixel shaders and SpriteBatches in XNA 4.0 component-object game engine?
I've got a bit of experience with shaders in general, having implemented a couple, very simple, 3D fragment and vertex shaders in OpenGL/WebGL in the past. Currently, I'm working on a 2D game engine in XNA 4.0 and I'm struggling with the process of integrating per-object and full-scene shaders in my current architecture.

I'm using a component-entity design, wherein my "Entities" are merely collections of components that are acted upon by discreet system managers (SpatialProvider, SceneProvider, etc). In the context of this question, my draw call looks something like this:

* SceneProvider::Draw(GameTime) calls...
* ComponentManager::Draw(GameTime, SpriteBatch) which calls (on each drawable component)
* DrawnComponent::Draw(GameTime, SpriteBatch)

The SpriteBatch is set up, with the default SpriteBatch shader, in the SceneProvider class just before it tells the ComponentManager to start rendering the scene. From my understanding, if a component needs to use a special shader to draw itself, it must do the following when it's Draw(GameTime, SpriteBatch) method is invoked:

```
public void Draw(GameTime gameTime, SpriteBatch spriteBatch)
{
    spriteBatch.End();
    spriteBatch.Begin(SpriteSortMode.Immediate, BlendState.AlphaBlend, null, null, null, EffectShader, ViewMatrix);

    // Draw things here that are shaded by the "EffectShader."

    spriteBatch.End();
    spriteBatch.Begin(/* same settings that were set by SceneProvider to ensure the rest of the scene is rendered normally */);
}

```

My question is, having been told that numerous calls to SpriteBatch.Begin() and SpriteBatch.End() within a single frame is terrible for performance and creates a number of special cases for my drawing logic, is there a better way to do this? Is there a way to instruct the currently running SpriteBatch to simply change the Effect shader it is using for this particular draw call and then switch it back before the function ends?

# Answer
> 1 votes
i had the same problem in my engine.

the solution i choose was to draw every sprite that should be affected to a rendertarget and draw it with the effect to the backbuffer.

# Answer
> 1 votes
Instead of Drawing in Draw() you could generate list of commands (one of them being Begin, with shader as parameter) and other would be Draw calls)

And then you can sort those commands to call Begin as little as possible

---
Tags: xna, c#, xna-4.0, shaders, component-based
---


title: Change of direction after Collision

text:
# Question
Title: Change of direction after Collision
I am having a pickup image which is moving at random direction and have to change the direction after collision with some tiles, which are a rectangle. I've my own algorithm for detecting the collision, but I couldn't accurately calculate new direction. Please have a look at my code for collision detection.

```
void PickUpManager::CheckPickUpToTileCollision(){
CIwArray<_TILE*> tiles=m_GAME.m_Datamine->m_Tile;
uint16 tileTop,tileLeft, tileBottom, tileRight, pickTop,pickLeft, pickBottom, pickRight;
for(uint32 i=0;i<tiles.size();i++){
    tileTop=tiles[i]->m_TilePos.y;
    tileLeft=tiles[i]->m_TilePos.x;
    tileBottom=tiles[i]->m_TilePos.y+tiles[i]->m_TileSize;
    tileRight=tiles[i]->m_TilePos.x+tiles[i]->m_TileSize;

    pickTop=m_Pos.y;
    pickLeft=m_Pos.x;
    pickBottom=m_Pos.y+pickHeight;
    pickRight=m_Pos.x+pickWidth;
    //Collision from Top of Tile
    if(pickBottom>=tileTop && pickBottom<=tileBottom && pickRight>=tileLeft && pickLeft<=tileRight &&!yFlag){
        yDir=-PICK_SPEED;
        yFlag=true;
    }
    //Collision from Bottom of Tile
    if(pickTop<=tileBottom && pickTop>=tileTop && pickRight>=tileLeft && pickLeft<=tileRight &&!yFlag){
        yDir=PICK_SPEED;
        yFlag=true;
    }
    //Collision from Left of Tile
    if(pickBottom>=tileTop && pickTop<=tileBottom && pickRight>=tileLeft && pickRight<=tileRight &&!xFlag){
        xDir=-PICK_SPEED;
        xFlag=true;
    }
    //Collision from Right of Tile
    if(pickBottom>=tileTop && pickTop<=tileBottom && pickLeft<=tileRight && pickLeft>=tileLeft &&!xFlag){
        xDir=PICK_SPEED;
        xFlag=true;
    }
    if(xFlag && yFlag)
        return;
}
}

void PickUpManager::Move(){
xFlag=false;
yFlag=false;
CheckPickUpToTileCollision();
    m_Pos.x+=xDir;
    m_Pos.y+=yDir;
}

```

The problem is the tiles are like bricks making a wall. So if the pickup hit the tile from top left, it changes it's x and y both direction, while the change of direction should be only in the x direction, as there's another tile which ended before this tile. I know it's some stupid problem, but still couldn't make it out.

# Answer
> 2 votes
What you need to do is reflect the velocity vector in the normal of the collision. If it's a wall, then the normal is the normal of the wall (which direction it is facing). So if you know which side of the tile was hit, then you can work out the normal for that side.

To reflect the vector you need to use the dot product to calculate the resultant vector to use as the new velocity. Vector Reflection.

If you don't know the normal of the surface there are also ways to calculate it from the two points which define the tile edge. Calculating Normals.

---
Tags: c++, 2d, collision-detection
---


title: game data structures

text:
# Question
Title: game data structures
I am working on a game that will be a 3D-shooter (camera trailing player), and want to impose some architecture on the game being that a `level` is composed of `rooms` where each room can hold `entities`(the player, enemies, pickups, projectiles), `AInodes`, walls/floor, and `doors`(more on these in a little)

my first concern/iteration is to get a single room functional, and then link rooms together in a later iteration(this is so that rooms to render are dynamically chosen to accelerate render times on larger level). my direct question for this iteration is what would be an optimal data structure for holding my `entities` for the room? keeping in mind that whatever structure I use needs to be searchable, removable(single/group of items), sortable(this can be given up if needed), growable, and possibly be able to take pointers to the `gameObjects`. this structure would probably also be used for my doors. my initial thought was to use linked list though removing items from linked lists can be a chore, and if not done right can just create a memory black-hole.

I keep bouncing back, and forth on putting walls/floor into the same structure as the `entities` as it would be mostly efficient for collision detection (i think), but I know it can cause a graphics nightmare (more things being rendered means longer it takes), so maybe keeping walls separate, and create a separate list of walls to be rendered vs collisions.

the next part would be linking the rooms together by doors(see picture bellow where the joint between each room is a `door`) where my first though was adjacency list. I understand that the `std::graph` has an adjacency list that it uses though I don't feel that it would work in my situation as just rooms `05`, and `11`/`15` don't work within a `std::graph` so would it be worth while to build a custom adjacency list (might need to see an implementation as I keep getting lost on connecting adjacent things that should be connected)

* S: start
* F: finish
* ## : room number

# map example

# Answer
Usually I separate the rendering from the game structure. I have mechanisms where game entities can attach graphics to the graphic engines. This way the graphics can be optimized independently.

## Relationships

Then when it comes to relationships between entities, there are many ways to implement them. You can have a general purpose relationship mechanism with an ends list, a communications system dedicated to related entities, or very specific hardcoded relationships.

How you implement your relationships will depend on the architecture of your engine. But you need to establish the relationship between the rooms and if using the doors is simpler you can for each room add a list of doors/gates...

Each gate can hold 2 pointers to the rooms they link to. When it comes to pointers and lists it's up to you to organize the construction and destruction of your objects. It's not a big problem if you think about and implement the destruction while you write the construction process.

## Rooms composition

You don't have to put each floor tile as a different entity. You can load your level as one entity with graphics managed separately by the graphics engine. Your levels can create additional entities like traps, mechanisms, gates, objects with collision, etc... This way you don't have to bloat your main engine with floors tiles and other passive elements. You can have only one physics component per room for example (composed of floors and walls).

## Composition is the solution

Your current system seems to store everything in the entities. A component based system can bring more work when you start but you will benefit from the composition as you progress. Additionally a component based system will allow you to implement quickly and simply the relational structure you want to have.
> 2 votes

---
Tags: c++, data-structure
---


# Question
Title: elongate or scale limbs of a model in XNA
I'd like to create one model that I import into an XNA game.

I'd like to be able to copy this model and make programmatic modifications to it during execution (with the intent of using the same model to represent multiple characters in the game). For example, I'd like to make the legs slightly longer or shorter, or the waist slightly fatter or thinner, or the head slightly smaller or larger.

I know how to use transforms to modify a mesh, but it seems that what I need here is to apply a transform to only a subset of vertices in that mesh. I have no idea how to do this in XNA, or if it's even supported.

Two questions: 1) is functionality like this supported in XNA? 2) if so, what kind of methods are used to obtain the desired result?

(note, this was crossposted from stackoverflow, this forum was recommended as a better place for my question)

# Answer
it can be done modifying the bone transform of your model.

You don't need submeshes, each vertex in a model should have a bone weight property that quantify how that vertex is affected by the bone transform.

In this image each color defines the bone that is applied to each vertex.

You will have a bone hierarchy tree that seems to this skeleton, that way if you change athe forearm bone, scaling it, it will affect to the hand bone.

Xna offers you a Model class that let you access to the Bones, but you have to recalcultate the bone transform by yourself. And of course the model have to be created with the skeleton that you need.

http://msdn.microsoft.com/en-us/library/microsoft.xna.framework.graphics.model\_members(v=xnagamestudio.40).aspx

You should have to do something similiar to:

```
// Save the original bone transforms that are relative to its parents.
Model.CopyBoneTransformsTo ( Backup );

// I have not done this ever, but I would test this:
    Model.Bones.Item["Hand"].Transform = Matrix.CreateScale(1,1,1.5f) * Model.Bones.Item["Hand"].Transform;
or
    Model.Bones.Item["Hand"].Transform = Model.Bones.Item["Hand"].Transform * Matrix.CreateScale(1,1,1.5f);

```

Remember that order in matrix multiplication is very important.
> 5 votes

# Answer
It depends somewhat on the format of the model you are attempting to perform these transformations on. Some models are implemented as a single monolithic mesh, and it in this case it may be difficult to isolate the vertices which make up the arms, or legs for example. Although other commenters may know a way to work with such a model.

Many models are implemented as a hierarchy of sub-meshes, and this can be defined by the modeller when the asset is created. If you have created the model yourself or an artist has created it for you, you the arms could be made a separate sub-mesh. You could then identify these in code and perform your transformation on only this sub-mesh.

Personally, I am a programmer and not a modeller myself, so I am unsure as to the specifics of this process in the modelling software, but it is certainly possible.

Also, you may want to bear in mind that transforming vertices might have an effect on any skinned animations provided with the model, although I'm unsure about the specifics of this.

Another approach that might give more plausible results would be to a have an animation with keyframes that range between really thin and really fat, and then 'tweening' between these frames via interpolation before copying the vertices to give your new base model. Simple programmatic manipulation of the vertex data via something like linear interpolation might result in some strange and artificial looking results.

EDIT: Taking into account other suggestions and approaches I had not considered such as other reply on bone weighting
> 0 votes

---
Tags: xna
---


# Question
Title: GLSL Shader Solution for Ambient Occlusion?
For the iOS app I am writing I want to incorporate some aspects of ambient occlusion for photo manipulation. Can someone suggest a GLSL approach that will work. Realtime performance is not super critical. Under a second compute time is fine.

# Answer
Generally, ambient occlusion requires 3D data to be calculated. If you are planning to add some depth information then I would suggest the use of screen space ambient occlusion; SSAO.

Using screen space ambient occlusion should fit better into your pipeline. Since you want to manipulate photos, I presume you already have a method for adding post process filters.

What you will need to do is render the 3D data to a depth buffer. There are many sources which detail how to do this. If you can't find any, try looking up deferred shading techniques. These rely on filling a depth buffer for post processing so there should be a good example out there for you.
> 2 votes

---
Tags: ios, glsl
---


# Question
Title: How many update and draw calls can a windows phone suppport
I'm making a Windows Phone game (XNA 4.0) which requires a lot of activity on the screen. It's working well for now. But what I am concerned about is that it uses a lot of sprites and many of them as *'lists'* so that I can make multiple copies of the sprite, and this causes a lot of Update() calls which have *'for'* loops and collision testing method calls also. This also increases the number of Draw() calls. As the game progresses, I am going to need to add more sprites and update calls.

Can that cause problems in Windows Phone? (Currently I have no device to test it on).

My game has 18 sprites for now and most of them requires multiple copies to be drawn on screen.

Is there a more efficient way to achieve this?

# Answer
There is practically no limit. As most things though, that is not 100% sure. What you are going to be limited by is hardware.

The default FPS is set to 30, but you can change it to 60 if you like. If you are not able to do all the work in your main Update Loop *in **one** frame* then you will start to see frames getting dropped. This is bad.

Also, there is a limit to how much memory you can use on the phone. For smaller devices running the yet-to-be released "Tango" update, this limit is 90MB. The Certification Guide details out how much memory you are allowed to use. If your game is using more than the limit it will not get passed certification. Use too much memory and your app will crash.

A few tips:

* To reduce memory usage and allow your game to scale, look into sprite sheets.
* Being "wasteful" with your objects will cause the GC to kick off, and that will cause skipping as well. Make sure you only allocate what you need.
* If you need to create/destroy sprites a lot (think bullets, enemies, etc...) look into object pools
* Use Doubles instead of Floats when appropriate. Internally the phone version of the framework used Doubles; any Float has to be casted over anyway.
* Run the Windows Phone Performance Analysis tool on your game. It will show you "hotspots" as well as tell you what is using the most memory.

All that being said, If you game runs fine (no noticeable "skipping" or dropped frames), doesn't take too long to load, and passes certification; it is probably fine. Don't really worry about performance right now. Just work on making your game fun.
> 3 votes

---
Tags: xna, windows-phone-7, memory-efficiency
---


# Question
Title: Optimizing updating thousands of enemies? (Or break up the enemies that need updated?)
Thanks in advance for wanting to help.

I have an array of (right now) ~1000 enemies that I need to update every frame. The issue, I believe, is mainly brute-force checks. I've profiled my application with dotTrace, and there are no lines of code that are inherently slow (the method itself is slow, though). This leads me to believe that it's simply the number of operations performed that's my bottleneck.

---

I can already picture the comments of "why do you need to update that many objects!", so I'll answer that first.

I'm using GLEED2D (amazing level editor, by the way) to create my "maze" of enemies. This is a top-down shooter level, so these enemies are then loaded into my game, and I move them downward each frame. Picture a giant sheet that I move downward every frame, and you have the basic idea.

Now, I have to (currently) update every enemy with it's velocity, to keep it in sync with all of the other enemies.

This takes a long time, even on the PC, eventually starting to lag.

I'm asking for some help in thinking this problem through, or in designing a solution if you're generous. I thought I could possibly do a chunk-based solution, where I throw enemies into arrays that contain bite-sized chunks, but then I'm back to trying to update them correctly. This would mean I'd have to move the chunk, or keep track of the chunk's offset (if it were moving) and apply them later.

I can't see that as the best solution. Not to mention that this is a seamless level, so the chunk calculations would have to match perfectly. However, if it sounds good, I would still require some help in figuring out how to split up and update chunks.

---

I've thought about this problem for days now, and nothing I've tried has worked. Ideally, this will be a solution that can handle more than my current amount of enemies (which was why I thought the chunk-based solution might work).

Any suggestions or ideas?

Thanks!

---

## (Additional information)

The enemies are mainly just having a velocity applied to them. Strictly Vector2 += Vector2.

# Answer
> 0 votes
## (My final chunk-based approach)

---

I used a combination of things. Much like the Scene-Graph suggested by OriginalDaemon, I divide my enemy array into "Chunks". I created rectangles in the editor, and imported them as a pre-defined array of "Chunk Boundaries".

From this, I take my giant array of enemies, and run through it at build time to place the enemies into the "Chunks" in which they fit (Checking if their position is a point in the "Chunk Boundary" rectangle).

Then, at runtime, I only update each "Chunk Boundary"'s position. Then, when the last "active" chunk that's having it's enemies updated passes a certain point, I activate the next chunk "behind" it, thus letting the enemies in that chunk be drawn and updated.

Then, when an active chunk passes off-screen, I deactivate it, stopping the drawing and updating of all enemies within the chunk.

I would like to thank all the people who responded, answered or inquired about the problem, as you were all instrumental in pushing me in the correct direction. (Massive props to OriginalDaemon!)

# Answer
> 3 votes
You mention this is a "top-down shooter" and that the enemies are all moving downward simultaneously. If you mean the kind of game where the player flies past/shoots down lots of enemies as they scroll by, then...

**Don't move the enemies!** Instead, move the *player* and the *camera*. (You mention in comments you don't have a camera — so fix that problem. It will be far more efficient than updating many enemies, and simpler than a scene graph.) Then, there is no need to update every enemy every frame, unless it's on-screen and therefore having visible behavior.

An even more refined method which you can use if this is a strictly fixed-scrolling game is to not actually have all the enemy objects instantiated at once — create them at the top of the visible screen at designated *time* points. Keep a data structure that's basically a script for creating enemies at designated times. Given fixed scrolling, this works out to be exactly the same thing as having the enemies at designated not-yet-on-screen positions (kind of like how a waveform can be seen in either space or time). The advantage of this method is that you do not need to keep around all the information about idle offscreen enemies — just when they go onscreen.

# Answer
> 2 votes
If you can organize the enemies into chunks then what you may be looking for is a scene graph.

You would make each enemy in your chunk a child of that chunk which would also have a position, orientation and scale. Each enemy would then, in turn, inherit the values of the parent, but can still be moved separately when necessary.

I would tend to make a SceneNode interface. Then anything can be a SceneNode, even the enemies themselves.

I might use an interface for scene nodes like the following;

```
public interface SceneNode
{
    Vector3 Position, Orientation, Scale;
    Vector3 finalPosition, finalOrientation, finalScale;
    void Update(float ElapsedTimeInMilliseconds);
    SceneNode Parent;
    List<SceneNode> Children;
}

```

The final... values are the values after adding on the values for the parent final... So these values would propagate down the tree, although you'd make them read only. So the get for finalPosition might be; return Parent.finalPosition + Position;

Then you simply have to change the parent object and all of it's children will be changed as well.

---
Tags: xna, 2d, algorithm, optimization
---


# Question
Title: Partial recalculation of visibility on a 2D uniform grid
**Problem**
Imagine that we have a 2D uniform grid of dimensions *N* x *N*. For this grid we have also pre-computed a visibility look-up table, e.g. with DDA, which answers the boolean query *is cell X visible from cell Y?*

The look-up table is a complete graph *KN* of the cells *V* in the grid, with each edge *E* being a binary value denoting the visibility between its vertices.

**Question**
If any given cell has its visibility modified, is it possible to extract the subset *Edelta* of edges which must have their visibility recomputed due to the change, so as to avoid a full-on recomputation for the entire grid? (Which is N(N-1) / 2 or N2 depending on the implementation)

# Answer
> 1 votes
Perhaps you should look at "The Visibility Skeleton: A Powerful And Efficient Multi-Purpose Global Visibility Tool," Durand et al., a 1997 paper that Google Scholar shows has been cited 148 times since. The question you pose has been heavily studied! One of the key search phrases is *walkthrough*.

# Answer
> 0 votes
If it is not possible to solve this in closed form, then maintaining a separate mapping of each cell and every cell pair which's line intersects said cell might also be an option. This obviously consumes more memory, but the data is static.

The increased memory requirement could be reduced by introducing a hierarchy, subdividing the grid into smaller parts, and by doing so the above mapping can be reused for each sub-grid. This would come at a cost in terms of increased computation relative to the number of subdivisions; also requiring a resumable ray-casting algorithm.

---
Tags: 2d, algorithm, geometry, graph, occlusion
---


title: Unsure how to move a unit to a point

text:
# Question
Title: Unsure how to move a unit to a point
I've got a unit and a series of points in 3D space which approximate the path it's been given. However, I'm not sure where to go from there. The unit has certain physical constraints, like, it can only turn so fast, it can only accelerate so fast/decelerate so quickly, etc. I thought that this would be the simple part and finding the path would be the hard part, but apparently it's not. Here's the code I've written:

```
void Sim::Context::tick() {
    auto t = 1.0f / Sim::ticks_per_sec;
    std::for_each(players.begin(), players.end(), [&](std::unique_ptr<Sim::Player>& p) {
        auto units = p->GetOwnedUnits();
        std::for_each(units.begin(), units.end(), [&](Sim::Unit* unit) {
            auto t = 1.0f / Sim::ticks_per_sec;
            auto u = unit->GetVelocity();
            auto a = unit->GetAcceleration();
            if (u == 0 && a == 0)
                return;
            auto rotated_heading = Math::Vector(0, 0, 1) * unit->GetRotation();
            auto bp = unit->GetBlueprint();
            auto v = t * a + u;
            if (v > bp->MaxVelocity) { // Do a more accurate lerp since we went over max velocity
                // leerrrppppp
                auto frac = (bp->MaxVelocity - u) * (t / (v - u));
                auto total_increase = (u * t) + (0.5f * a * frac * frac) + (bp->MaxVelocity * (t - frac));
                unit->SetPosition((rotated_heading * total_increase) + unit->GetPosition());
                unit->GetOwningPlayer()->OnUnitPositionChange(unit, unit->GetPosition());
                unit->SetVelocity(bp->MaxVelocity);
                return;
            }
            auto increase_due_to_velocity = u * t;
            auto increase_due_to_acceleration = 0.5f * a * t * t;
            auto rotated_increase = rotated_heading * increase_due_to_acceleration;
            unit->SetPosition(rotated_increase + unit->GetPosition());
            unit->SetVelocity(v);
            unit->GetOwningPlayer()->OnUnitPositionChange(unit, unit->GetPosition());
        });
    });
    for(auto orderit = UnitOrders.begin();orderit != UnitOrders.end();) {
        if (auto move = dynamic_cast<Move*>(orderit->second.get())) {
            auto unit = orderit->first;
            if (Math::Length(unit->GetPosition() - move->target) < 2) { // Close enough to target
                orderit = UnitOrders.erase(orderit);
                unit->SetAcceleration((-4 * unit->GetVelocity()) / (t * t)); // Let the setter implement the cap
                continue;
            }
            auto path = GetPath(unit->GetPosition(), move->target, unit);
            if (path.size() == 1) {
                orderit++;
                continue;
            }
            auto target_heading = Math::Normalize(path[1] - unit->GetPosition());
            auto current_heading = Math::Normalize(Math::Vector(0, 0, 1) * unit->GetRotation());
            auto axis = Math::Normalize(Math::Cross(current_heading, target_heading)); // Every path has at least two positions- a beginning and an end.
            auto dot_value = Math::Dot(target_heading, current_heading);
            if (dot_value > 1)
                dot_value = 1;
            if (dot_value < -1)
                dot_value = -1;
            auto degrees_angle = std::acos(dot_value);
            auto angle = glm::degrees(degrees_angle);
            if (target_heading == current_heading) {
                unit->SetAcceleration(unit->GetBlueprint()->MaxAcceleration);
                orderit++;
                continue;
            }
            if (std::abs(angle) > (unit->GetBlueprint()->MaxTurnRate * t)) {
                angle = unit->GetBlueprint()->MaxTurnRate * t;
                // Not done turning, slow down as much as possible.
                unit->SetAcceleration((-4 * unit->GetVelocity()) / (t * t)); // Let the setter implement the cap
            } else {
                // Done turning- let's rock on.
                unit->SetAcceleration(unit->GetBlueprint()->MaxAcceleration);
            }
            auto added_rotation = Math::RotateAxis(angle, axis);
            auto total_rotation = unit->GetRotation() * added_rotation;
            if (total_rotation.x != total_rotation.x)
                __debugbreak();
            unit->SetRotation(total_rotation);
            orderit++;
        }
    }
}

```

Sometimes the units rotate to move backwards towards the target, instead of forwards.

Sometimes the units rotate to face a few degrees away from the target, backwards or forwards. The exact value of a "few" is quite variant.

The units turn to face the target, and then move towards it. This is by design, but what's not is the several-second gap in the middle- but only the first time the unit is ordered to move. After that it's perfectly responsive.

I don't really understand how this can go wrong- the logic is simple. As you can see, I split most of my processes up into many intermediate variables so that I can debug their values, but the truth is that when I look, they seem fine. For example, the `target_heading` and `current_heading` variables are equal (or close to) when the unit is facing the wrong direction, but moving in the right direction. This definitely puzzles me.

Any suggestions as to where I can look for the source of the errors?

# Answer
Solved at least two of my problems- turns out that quaternions have a handedness. I'm still not sure which is which, but Direct3D uses one and my mathematical support lib uses the other. Once I wrote a conversion into the conversion function, now the rotations match up.
> 1 votes

# Answer
The 'handedness' of the quaternions should be the same one as the way angles are measured in the specific API you're using, since quaternions requires an angle between two vector to work. It's more or less the same difference about matrix notations (rows VS columns).

If you avoid any other type of manual transformation (maybe you have some matrix transformation code you wrote) and let the system do it (by calling API-related methods to get angles and such) you'll be sure to never have 2 different notations.

Another possibility is that you passed some vector backward (tail-to-head instead of head-to-tail).
> 0 votes

---
Tags: c++, physics
---


# Question
Title: How do I determine the position of one vector relative to another?
I'm making a game for Kinect in Unity which tracks hand movements. I have the player's root position and the position of their fist stored as 3-dimensional vectors (`Vector3` in Unity), but they're both in world space.

**How can I determine the location of the player's fist relative to their root position?**

# Answer
> 6 votes
Use `Vector3 relativeFistPosition = globalFistPosition - globalRootPosition;` to get the fist position relative to the root. Use this new Vector3 for comparing different moves.

---
Tags: unity, vector, kinect
---


# Question
Title: Pathfollowing with acceleration - centripetal force
I'm implementing A\* waypoint pathfinding with some twists. One of the problems I'm encountering is because I do not change velocities of the agents directly but rather I do so through forces.

Which gives me the following problem: let's suppose the path consists of three nodes,

P0 = the starting position P1 = node 1 P2 = node 2

When the agent starts moving, it's first target position is P1. The agents moves in that direction because I let a force F act on it's velocity: F=normalized(targetPos-agentPos)\*agentAccel\*agentMass;

The agent reaches P1.

Now the agent's target position is P2, and upon it will act a force in the direction of (targetPos-agentPos).

However, this is a centripetal force, meaning that the agent will most likely orbit around P2 instead of popping the next node off the path (unless the angle between \[P0,P1\] and \[P1,P2\] is small) Stopping the agent at each node is not an option (would look unnatural) What should really happen is the velocity of the agent gradually shifting towards 100% the direction of \[targetPos-agentPos\], and the velocity should be completely 'shifted' before a certain distance(dX) is laid off, starting from the previous node position

**In order to solve this problem, only one parameter is adjustable:**

* F\_dir: the direction of the force acting upon the agent, that's supposed to lead the agent to the next node.

**The values of the following parameters are known:**

* agentAcceleration (=the magnitude of the force vector)
* agentVelocity
* agentPosition
* node positions
* targetPosition (= the next node on the path)

I've been trying some different strategies with trial and error to prevent this, but it seemed rather messy, so my question is, what is a decent approach to this problem?

# Answer
As much as I can tell you can use beizer curves to smooth the path. I know it's not physical at all, but just create a beizer curve with order of 2, from each three points in the path. this way character will not path exactly over all the waypoints but it'll move over a path which can be an actual physical shape's path. you can also check for the collision along the way to solve issues about the object moving through the walls, since beizer curves will go through the wall.
> 1 votes

# Answer
Note: know that with constant acceleration your speeds will soon become ludicrous if the path is even moderately straight.

Mode 1: Cheat. Use the path points to define a hermite spline then use velocity and acceleration to define how fast, it will look reasonable to audiences brought up on Star Wars and Battlestar Galactica physics. (this is basically faking sideways friction)

Mode 2: Cheat less. Realize that passing directly through the path points is not necessary, allowing a radius to trigger arrival will stop the orbiting behavior you are talking about.

Mode 2.5: (I think this will work) You left out current direction of movement, in physics terms "velocity" is simply a speed. Take the direction your agent is currently moving and that's vector V1, now take the direction directly to the new point and call that vector V2. Get the angle between V1 and V2 and create a vector V3 that is -angle from V1 and this will be your F\_dir vector. Note that it does not point directly at the next point, but appears to over-compensate by pushing too far - but that's self correcting because over time V1 will approach a heading directly at the next point.

Mode 2.5a: Since your acceleration is constant and the agent's velocity is constantly changing the real angle to move your force's direction vector won't be as I described in 2.5 above but instead will have to over and under compensate based on relative velocity versus force, but that's beyond my math to describe beyond that. (ie. a very slow agent doesn't require as much angle to get headed the right way, while a very fast one would require extreme measures to bring into line).
> 1 votes

---
Tags: physics, path-finding
---


# Question
Title: What technique should I use to create models and animation sequences in OpenGL code?
I'm getting into game development using OpenGL (and the LWJGL library) and I want to create models for characters, NPC's etc. in the code, as well as animation sequences (for example the way the models are done in Minecraft).

What is the process to go about doing something like this? Is there a particular feature set that is used or common methods of doing this? I'm basically looking for pointers as to what to search for when trying to find examples of how this is done.

# Answer
You can start 3d modelling in http://www.blender.org/ ( Opensource. Or try 3dsmax if you have access. ) You can export as md2 / obj / etc. format, to import models and animations, in game.
> 2 votes

---
Tags: opengl, animation
---