# Question
Title: How to find and fix the performace problems with my voxel engine?
I am creating a voxel engine in C# and XNA and many posts I have posted on this site have been due to performace issues, many people suggested using a profiler to help me out. I have done so, and strangely enough, the most functions that are costing me the most performance according to the profiler are the simplest. Here is the output of the profiler:

and here is the world code:

```
    public bool InBounds(int x, int y, int z)
    {
        if ((x < 0 || y < 0 || z < 0) ||
            x >= size.X || y >= size.Y || z >= size.Z)
        {
            return false;
        }

        return true;
    }

    public bool Exists(int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            Vector3i regionalPosition = GetRegionalPosition(x, y, z);
            Vector3i region = GetRegionPosition(x, y, z);

            return !(regions[region.X, region.Y, region.Z].Blocks[regionalPosition.X, regionalPosition.Y, regionalPosition.Z].BlockType == BlockType.none);
        }

        return false;
    }

    public void SetLight(int x, int y, int z, int light)
    {
        if (InBounds(x, y, z))
        {
            Vector3i regionalPosition = GetRegionalPosition(x, y, z);
            Vector3i region = GetRegionPosition(x, y, z);

            regions[region.X, region.Y, region.Z].QueueForBuild(BufferType.All);

            regions[region.X, region.Y, region.Z].Blocks[regionalPosition.X, regionalPosition.Y, regionalPosition.Z].Light = (byte)light;
        }
    }

    public int GetLight(int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            // ARRAYS start from ZERO
            // LOGIC starts from ONE

            Vector3i regionalPosition = GetRegionalPosition(x, y, z);
            Vector3i region = GetRegionPosition(x, y, z);

            return regions[region.X, region.Y, region.Z].Blocks[regionalPosition.X, regionalPosition.Y, regionalPosition.Z].Light;
        }

        return -1;
    }

    public Block GetBlock(Vector3 position)
    {
        int x = (int)Math.Floor(position.X);
        int y = (int)Math.Floor(position.Y);
        int z = (int)Math.Ceiling(position.Z);

        Block block = GetBlock(x, y, z);

        return block;
    }

    public Block GetBlock(int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            Vector3i regionalPosition = GetRegionalPosition(x, y, z);
            Vector3i region = GetRegionPosition(x, y, z);

            return regions[region.X, region.Y, region.Z].Blocks[regionalPosition.X, regionalPosition.Y, regionalPosition.Z];
        }

        return new Block(BlockType.none);
    }

    public void RemoveBlock(Vector3 position)
    {
        int x = (int)Math.Floor(position.X);
        int y = (int)Math.Floor(position.Y);
        int z = (int)Math.Ceiling(position.Z);

        Vector3i regionalPosition = GetRegionalPosition(x, y, z);
        Vector3i region = GetRegionPosition(x, y, z);

        Block block = new Block(regions[region.X, region.Y, region.Z].Blocks[regionalPosition.X, regionalPosition.Y, regionalPosition.Z].BlockType);

        regions[region.X, region.Y, region.Z].QueueForBuild(block);
        regions[region.X, region.Y, region.Z].Blocks[regionalPosition.X, regionalPosition.Y, regionalPosition.Z].BlockType = BlockType.none;

        lighting.BlockRemoved(block, x, y, z);
    }

    public void AddBlock(Block block, Vector3 position)
    {
        //position += new Vector3(0.5f, 0.5f, 0.5f);

        int x = (int)Math.Floor(position.X);
        int y = (int)Math.Floor(position.Y);
        int z = (int)Math.Ceiling(position.Z);

        AddBlock(block, x, y, z);
    }

    public void AddBlock(Block block, int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            Vector3i regionalPosition = GetRegionalPosition(x, y, z);
            Vector3i region = GetRegionPosition(x, y, z);

            regions[region.X, region.Y, region.Z].Blocks[regionalPosition.X, regionalPosition.Y, regionalPosition.Z].BlockType = block.BlockType;

            if (lighting != null)
            {
                lighting.BlockAdded(block, x, y, z);

                if (GetBlock(x, y, z).BlockType == BlockType.waterStill)
                {
                    regions[region.X, region.Y, region.Z].QueueForBuild(BufferType.Water);
                    fuilds.WaterQueue.Enqueue(new Flow(x, y, z, 16));
                }
                else
                {
                    regions[region.X, region.Y, region.Z].QueueForBuild(BufferType.Solid);
                }
            }
        }
    }

    public Vector3i GetRegionPosition(int x, int y, int z)
    {
        int regionx = x == 0 ? 0 : x / Variables.REGION_SIZE_X;
        int regiony = y == 0 ? 0 : y / Variables.REGION_SIZE_Y;
        int regionz = z == 0 ? 0 : z / Variables.REGION_SIZE_Z;

        return new Vector3i(regionx, regiony, regionz);
    }

    public Vector3i GetRegionalPosition(int x, int y, int z)
    {
        int regionx = x == 0 ? 0 : x / Variables.REGION_SIZE_X;
        int X = x % Variables.REGION_SIZE_X;

        int regiony = y == 0 ? 0 : y / Variables.REGION_SIZE_Y;
        int Y = y % Variables.REGION_SIZE_Y;

        int regionz = z == 0 ? 0 : z / Variables.REGION_SIZE_Z;
        int Z = z % Variables.REGION_SIZE_Z;

        return new Vector3i(X, Y, Z);
    }

    public void MakeDirty(BufferType buffer, int x, int y, int z)
    {
        Vector3i regionalPosition = GetRegionPosition(x, y, z);

        regions[regionalPosition.X, regionalPosition.Y, regionalPosition.Z].QueueForBuild(buffer);
    }

```

If you need any more of the source I'll post it :D

Any ideas?

**Edit 1:**

```
    public bool InBounds(int x, int y, int z)
    {
        if ((x < 0 || y < 0 || z < 0) ||
            x >= size.X || y >= size.Y || z >= size.Z)
        {
            return false;
        }

        return true;
    }

    public bool Exists(int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            int[] regionalPosition = GetRegionalPosition(x, y, z);
            int[] region = GetRegionPosition(x, y, z);

            return !(regions[region[0], region[1], region[2]].Blocks[regionalPosition[0], regionalPosition[1], regionalPosition[2]].BlockType == BlockType.none);
        }

        return false;
    }

    public void SetLight(int x, int y, int z, int light)
    {
        if (InBounds(x, y, z))
        {
            int[] regionalPosition = GetRegionalPosition(x, y, z);
            int[] region = GetRegionPosition(x, y, z);

            regions[region[0], region[1], region[2]].QueueForBuild(BufferType.All);
            regions[region[0], region[1], region[2]].Blocks[regionalPosition[0], regionalPosition[1], regionalPosition[2]].Light = (byte)light;
        }
    }

    public int GetLight(int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            // ARRAYS start from ZERO
            // LOGIC starts from ONE

            int[] regionalPosition = GetRegionalPosition(x, y, z);
            int[] region = GetRegionPosition(x, y, z);

            return regions[region[0], region[1], region[2]].Blocks[regionalPosition[0], regionalPosition[1], regionalPosition[2]].Light;
        }

        return -1;
    }

    public Block GetBlock(Vector3 position)
    {
        int x = (int)Math.Floor(position.X);
        int y = (int)Math.Floor(position.Y);
        int z = (int)Math.Ceiling(position.Z);

        Block block = GetBlock(x, y, z);

        return block;
    }

    public Block GetBlock(int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            int[] regionalPosition = GetRegionalPosition(x, y, z);
            int[] region = GetRegionPosition(x, y, z);

            return regions[region[0], region[1], region[2]].Blocks[regionalPosition[0], regionalPosition[1], regionalPosition[2]];
        }

        return new Block(BlockType.none);
    }

    public void RemoveBlock(Vector3 position)
    {
        int x = (int)Math.Floor(position.X);
        int y = (int)Math.Floor(position.Y);
        int z = (int)Math.Ceiling(position.Z);

        int[] regionalPosition = GetRegionalPosition(x, y, z);
        int[] region = GetRegionPosition(x, y, z);

        Block block = new Block(regions[region[0], region[1], region[2]].Blocks[regionalPosition[0], regionalPosition[1], regionalPosition[2]].BlockType);

        regions[region[0], region[1], region[2]].QueueForBuild(block);
        regions[region[0], region[1], region[2]].Blocks[regionalPosition[0], regionalPosition[1], regionalPosition[2]].BlockType = BlockType.none;

        lighting.BlockRemoved(block, x, y, z);
    }

    public void AddBlock(Block block, Vector3 position)
    {
        //position += new Vector3(0.5f, 0.5f, 0.5f);

        int x = (int)Math.Floor(position.X);
        int y = (int)Math.Floor(position.Y);
        int z = (int)Math.Ceiling(position.Z);

        AddBlock(block, x, y, z);
    }

    public void AddBlock(Block block, int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            int[] regionalPosition = GetRegionalPosition(x, y, z);
            int[] region = GetRegionPosition(x, y, z);

            regions[region[0], region[1], region[2]].Blocks[regionalPosition[0], regionalPosition[1], regionalPosition[2]].BlockType = block.BlockType;

            if (lighting != null)
            {
                lighting.BlockAdded(block, x, y, z);

                if (GetBlock(x, y, z).BlockType == BlockType.waterStill)
                {
                    regions[region[0], region[1], region[2]].QueueForBuild(BufferType.Water);
                    fuilds.WaterQueue.Enqueue(new Flow(x, y, z, 16));
                }
                else
                {
                    regions[region[0], region[1], region[2]].QueueForBuild(BufferType.Solid);
                }
            }
        }
    }

    public int[] GetRegionPosition(int x, int y, int z)
    {
        int regionx = x == 0 ? 0 : x / Variables.REGION_SIZE_X;
        int regiony = y == 0 ? 0 : y / Variables.REGION_SIZE_Y;
        int regionz = z == 0 ? 0 : z / Variables.REGION_SIZE_Z;

        return new int[] {regionx, regiony, regionz};
    }

    public int[] GetRegionalPosition(int x, int y, int z)
    {
        int regionx = x == 0 ? 0 : x / Variables.REGION_SIZE_X;
        int X = x % Variables.REGION_SIZE_X;

        int regiony = y == 0 ? 0 : y / Variables.REGION_SIZE_Y;
        int Y = y % Variables.REGION_SIZE_Y;

        int regionz = z == 0 ? 0 : z / Variables.REGION_SIZE_Z;
        int Z = z % Variables.REGION_SIZE_Z;

        return new int[] { regionx, regiony, regionz };
    }

    public void MakeDirty(BufferType buffer, int x, int y, int z)
    {
        int[] regionalPosition = GetRegionPosition(x, y, z);

        regions[regionalPosition[0], regionalPosition[1], regionalPosition[2]].QueueForBuild(buffer);
    }

    public void Draw(SpriteBatch spriteBatch)
    {
        blockRenderer.Draw(player, this);
        player.Draw(spriteBatch);
    }
}

```

**Edit 2:**

OK, here is the new code:

```
    public bool InBounds(int x, int y, int z)
    {
        if ((x < 0 || y < 0 || z < 0) ||
            x >= size.X || y >= size.Y || z >= size.Z)
        {
            return false;
        }

        return true;
    }

    public bool Exists(int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            int regionX, regionY, regionZ;
            int regionalX, regionalY, regionalZ;

            regionX = regionalX = x;
            regionY = regionalY = y;
            regionZ = regionalZ = z;

            GetRegionPosition(ref regionX, ref regionY, ref regionZ);
            GetRegionalPosition(ref regionalX, ref regionalY, ref regionalZ);

            return !(regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ].BlockType == BlockType.none);
        }

        return false;
    }

    public void SetLight(int x, int y, int z, int light)
    {
        if (InBounds(x, y, z))
        {
            int regionX, regionY, regionZ;
            int regionalX, regionalY, regionalZ;

            regionX = regionalX = x;
            regionY = regionalY = y;
            regionZ = regionalZ = z;

            GetRegionPosition(ref regionX, ref regionY, ref regionZ);
            GetRegionalPosition(ref regionalX, ref regionalY, ref regionalZ);

            regions[regionX, regionY, regionZ].QueueForBuild(BufferType.All);

            regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ].Light = (byte)light;
        }
    }

    public int GetLight(int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            // ARRAYS start from ZERO
            // LOGIC starts from ONE

            int regionX, regionY, regionZ;
            int regionalX, regionalY, regionalZ;

            regionX = regionalX = x;
            regionY = regionalY = y;
            regionZ = regionalZ = z;

            GetRegionPosition(ref regionX, ref regionY, ref regionZ);
            GetRegionalPosition(ref regionalX, ref regionalY, ref regionalZ);

            return regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ].Light;
        }

        return -1;
    }

    public Block GetBlock(Vector3 position)
    {
        int x = (int)Math.Floor(position.X);
        int y = (int)Math.Floor(position.Y);
        int z = (int)Math.Ceiling(position.Z);

        Block block = GetBlock(x, y, z);

        return block;
    }

    public Block GetBlock(int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            int regionX, regionY, regionZ;
            int regionalX, regionalY, regionalZ;

            regionX = regionalX = x;
            regionY = regionalY = y;
            regionZ = regionalZ = z;

            GetRegionPosition(ref regionX, ref regionY, ref regionZ);
            GetRegionalPosition(ref regionalX, ref regionalY, ref regionalZ);

            return regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ];
        }

        return new Block(BlockType.none);
    }

    public void RemoveBlock(Vector3 position)
    {
        int x = (int)Math.Floor(position.X);
        int y = (int)Math.Floor(position.Y);
        int z = (int)Math.Ceiling(position.Z);

        int regionX, regionY, regionZ;
        int regionalX, regionalY, regionalZ;

        regionX = regionalX = x;
        regionY = regionalY = y;
        regionZ = regionalZ = z;

        GetRegionPosition(ref regionX, ref regionY, ref regionZ);
        GetRegionalPosition(ref regionalX, ref regionalY, ref regionalZ);

        Block block = new Block(regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ].BlockType);

        regions[regionX, regionY, regionZ].QueueForBuild(block);
        regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ].BlockType = BlockType.none;

        lighting.BlockRemoved(block, x, y, z);
    }

    public void AddBlock(Block block, Vector3 position)
    {
        //position += new Vector3(0.5f, 0.5f, 0.5f);

        int x = (int)Math.Floor(position.X);
        int y = (int)Math.Floor(position.Y);
        int z = (int)Math.Ceiling(position.Z);

        AddBlock(block, x, y, z);
    }

    public void AddBlock(Block block, int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            int regionX, regionY, regionZ;
            int regionalX, regionalY, regionalZ;

            regionX = regionalX = x;
            regionY = regionalY = y;
            regionZ = regionalZ = z;

            GetRegionPosition(ref regionX, ref regionY, ref regionZ);
            GetRegionalPosition(ref regionalX, ref regionalY, ref regionalZ);

            regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ].BlockType = block.BlockType;

            if (lighting != null)
            {
                lighting.BlockAdded(block, x, y, z);

                if (GetBlock(x, y, z).BlockType == BlockType.waterStill)
                {
                    regions[regionX, regionY, regionZ].QueueForBuild(BufferType.Water);
                    fuilds.WaterQueue.Enqueue(new Flow(x, y, z, 16));
                }
                else
                {
                    regions[regionX, regionY, regionZ].QueueForBuild(BufferType.Solid);
                }
            }
        }
    }

    public void GetRegionPosition(ref int x, ref int y, ref int z)
    {
        x = x == 0 ? 0 : x / Variables.REGION_SIZE_X;
        y = y == 0 ? 0 : y / Variables.REGION_SIZE_Y;
        z = z == 0 ? 0 : z / Variables.REGION_SIZE_Z;
    }

    public void GetRegionalPosition(ref int x, ref int y, ref int z)
    {
        int regionx = x == 0 ? 0 : x / Variables.REGION_SIZE_X;
        x = x % Variables.REGION_SIZE_X;

        int regiony = y == 0 ? 0 : y / Variables.REGION_SIZE_Y;
        y = y % Variables.REGION_SIZE_Y;

        int regionz = z == 0 ? 0 : z / Variables.REGION_SIZE_Z;
        z = z % Variables.REGION_SIZE_Z;
    }

    public void MakeDirty(BufferType buffer, int x, int y, int z)
    {
        int regionX, regionY, regionZ;
        int regionalX, regionalY, regionalZ;

        regionX = regionalX = x;
        regionY = regionalY = y;
        regionZ = regionalZ = z;

        GetRegionalPosition(ref regionalX, ref regionalY, ref regionalZ);

        regions[regionalX, regionalY, regionalZ].QueueForBuild(buffer);
    }

```

But this still generates a similar report:

**Edit 3:**

```
    public bool InBounds(int x, int y, int z)
    {
        return !((x < 0 || y < 0 || z < 0) || x >= size.X || y >= size.Y || z >= size.Z);
    }

    public bool Exists(int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            int regionX, regionY, regionZ;
            int regionalX, regionalY, regionalZ;

            regionX = regionalX = x;
            regionY = regionalY = y;
            regionZ = regionalZ = z;

            GetRegionPosition(ref regionX, ref regionY, ref regionZ);
            GetRegionalPosition(ref regionalX, ref regionalY, ref regionalZ);

            return !(regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ].BlockType == BlockType.none);
        }

        return false;
    }

    public void SetLight(int x, int y, int z, int light)
    {
        if (InBounds(x, y, z))
        {
            int regionX, regionY, regionZ;
            int regionalX, regionalY, regionalZ;

            regionX = regionalX = x;
            regionY = regionalY = y;
            regionZ = regionalZ = z;

            GetRegionPosition(ref regionX, ref regionY, ref regionZ);
            GetRegionalPosition(ref regionalX, ref regionalY, ref regionalZ);

            regions[regionX, regionY, regionZ].QueueForBuild(BufferType.All);

            regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ].Light = (byte)light;
        }
    }

    public int GetLight(int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            // ARRAYS start from ZERO
            // LOGIC starts from ONE

            int regionX, regionY, regionZ;
            int regionalX, regionalY, regionalZ;

            regionX = regionalX = x;
            regionY = regionalY = y;
            regionZ = regionalZ = z;

            GetRegionPosition(ref regionX, ref regionY, ref regionZ);
            GetRegionalPosition(ref regionalX, ref regionalY, ref regionalZ);

            return regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ].Light;
        }

        return -1;
    }

    public Block GetBlock(Vector3 position)
    {
        int x = (int)Math.Floor(position.X);
        int y = (int)Math.Floor(position.Y);
        int z = (int)Math.Ceiling(position.Z);

        Block block = GetBlock(x, y, z);

        return block;
    }

    public Block GetBlock(int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            int regionX, regionY, regionZ;
            int regionalX, regionalY, regionalZ;

            regionX = regionalX = x;
            regionY = regionalY = y;
            regionZ = regionalZ = z;

            GetRegionPosition(ref regionX, ref regionY, ref regionZ);
            GetRegionalPosition(ref regionalX, ref regionalY, ref regionalZ);

            return regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ];
        }

        return new Block(BlockType.none);
    }

    public void RemoveBlock(Vector3 position)
    {
        int x = (int)Math.Floor(position.X);
        int y = (int)Math.Floor(position.Y);
        int z = (int)Math.Ceiling(position.Z);

        int regionX, regionY, regionZ;
        int regionalX, regionalY, regionalZ;

        regionX = regionalX = x;
        regionY = regionalY = y;
        regionZ = regionalZ = z;

        GetRegionPosition(ref regionX, ref regionY, ref regionZ);
        GetRegionalPosition(ref regionalX, ref regionalY, ref regionalZ);

        BlockType blockType = regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ].BlockType;

        regions[regionX, regionY, regionZ].QueueForBuild(blockType);
        regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ].BlockType = BlockType.none;

        lighting.BlockRemoved(blockType, x, y, z);
    }

    public void AddBlock(BlockType blockType, Vector3 position)
    {
        //position += new Vector3(0.5f, 0.5f, 0.5f);

        int x = (int)Math.Floor(position.X);
        int y = (int)Math.Floor(position.Y);
        int z = (int)Math.Ceiling(position.Z);

        AddBlock(blockType, x, y, z);
    }

    public void AddBlock(BlockType block, int x, int y, int z)
    {
        if (InBounds(x, y, z))
        {
            int regionX, regionY, regionZ;
            int regionalX, regionalY, regionalZ;

            regionX = regionalX = x;
            regionY = regionalY = y;
            regionZ = regionalZ = z;

            GetRegionPosition(ref regionX, ref regionY, ref regionZ);
            GetRegionalPosition(ref regionalX, ref regionalY, ref regionalZ);

            regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ].BlockType = block;

            if (lighting != null)
            {
                lighting.BlockAdded(block, x, y, z);

                if (GetBlock(x, y, z).BlockType == BlockType.waterStill)
                {
                    regions[regionX, regionY, regionZ].QueueForBuild(BufferType.Water);
                    fuilds.WaterQueue.Enqueue(new Flow(x, y, z, 16));
                }
                else
                {
                    regions[regionX, regionY, regionZ].QueueForBuild(BufferType.Solid);
                }
            }
        }
    }

    public void GetRegionPosition(ref int x, ref int y, ref int z)
    {
        x = x / Variables.REGION_SIZE_X;
        y = y / Variables.REGION_SIZE_Y;
        z = z / Variables.REGION_SIZE_Z;
    }

    public void GetRegionalPosition(ref int x, ref int y, ref int z)
    {
        x = x % Variables.REGION_SIZE_X;

        y = y % Variables.REGION_SIZE_Y;

        z = z % Variables.REGION_SIZE_Z;
    }

    public void MakeDirty(BufferType buffer, int x, int y, int z)
    {
        int regionX, regionY, regionZ;
        int regionalX, regionalY, regionalZ;

        regionX = regionalX = x;
        regionY = regionalY = y;
        regionZ = regionalZ = z;

        GetRegionalPosition(ref regionalX, ref regionalY, ref regionalZ);

        regions[regionalX, regionalY, regionalZ].QueueForBuild(buffer);
    }

```

# Answer
Ok, it's pretty simple. The good bit is, once you fix this stuff it'll perform a couple of orders of magnitude better ;)

The first rule is that for functions that are frequently used and perform read operations, you can't afford to allocate memory if you want your game to actually function or perform at an interactive level. You can't afford to allocate a vector every time you want to find out which part of the array is storing the block you want.

**GetRegionalPosition/GetRegionPosition/GetBlock**

None of these should ever allocate memory on the heap.

If you have a block of voxels, just use a 1 dimensional array, and you can use something simple for the location within that block:

width * height * z + height * x + y

That will be an integer location, and you won't have to pass around objects for the location. Since integers are primitives, they're allocated on the stack, so they're safe, temporary objects are the enemy.

An improvement of this is to use shift operators if the size of your chunks are powers of two. I'm happy to walk you through that later, but first we need to get rid of those allocations.

It's ok to allocate objects in response to use input, or for non-frequent events, but it'll come back to bite you if it's occurring in any frequently running code.

If you're writing a game on a garbage collected VM (like C#/Java), you should feel physical pain at any point that you allocate an object.

**GetBlock**

At any point you want a class that represents the block, you really cant afford to allocate it everytime. In order to avoid allocations, the only sane way to approach it is to have a single class instance for each block type, and all methods that use it and depend on it's location pass in the (x,y,z) that the block is at. To go with this you should also have an array in static space that allows you to lookup blocks based on their ids.

Happy to clarify anything I've skipped over or written confusingly.

**In Response to Edit #3**

In "public void AddBlock(BlockType block, int x, int y, int z)"

```
regions[regionX, regionY, regionZ].Blocks[regionalX, regionalY, regionalZ].BlockType = block;

```

I'm guessing this block object has a whole bunch of methods for block type, lighting and extra data etc. This means you're storing thousands of individual block objects. Your garbage collector hates you for this, and it causes an extra level of indirection (chasing pointers) which is a bad thing for memory locatlity.

At some point you're going to want to switch to just using a handful of primitive arrays:

Different language, but same deal:

```
var blockIds = new Array[Byte](Chunk.blockSize)
var data = new Array[Byte](Chunk.blockSize)

var sunLight = new Array[Byte](Chunk.blockSize)
var torchLight =new Array[Byte](Chunk.blockSize)

```

The results from the fluid flow profile aren't surprising. Any local water modal is a can of worms in terms of run time complexity. There isn't a guarantee that you can have a water model like that and have decent performance at the same time.

world.addBlock taking 10% (which also involves your lighting system) doesn't look too bad.

I'd move to primitive arrays away from objects and see how much of an improvement that gives you. I'd also move to having a placeholder empty Region that returns only empty blocks so you can remove inBounds checking from your common methods. As part of this, you'd increase your region array to be always have padding on the sides, and slot the placeholder empty region in to all of the non-loaded slots.

This means that all of your actual world would be surrounded by the placeholder empty region, and you would never need to check bounds, removing the last bit of branching from your read operations.
> 6 votes

---
Tags: c#, xna, performance, voxels
---


# Question
Title: How are dynamic blending shadows like this created?
I would like to know, how dynamic shadows, that 'blend' onto other objects, are created.

# Answer
> 7 votes
These can be done using shadow mapping. Basically, place the camera at the light source and render the scene into a depth buffer; the resulting buffer identifies all the lit surfaces since they are just the surfaces the light can "see". This texture is then used in the pixel shaders in the main render to mask away light on surfaces behind the shadow map. There are plenty of shadow mapping tutorials on the Web, so consult those for details.

# Answer
> 0 votes
Assuming you know how to generate a shadow for an object, generate all the shadows separately, and then blit them onto the scene. Any overlaps will have the sum of their... darkness (as it were), and therefore look like the shadows overlap.

---
Tags: opengl, lighting, lwjgl, shadows
---


# Question
Title: what is the absolute simplest way to add physics to a simple 3D game
This physics does not have to be very complex at all.

There are a number of rectangles and one ball, all of which have the appropriate bounding volumes constrained to them, it would be great if the ball could knock them over and they in turn could knock into each other.

What is the most basic way of doing this?

# Answer
> 3 votes
The scenario you describe is already complex enough that I would *strongly* recommend using an external physics engine. I can't think of any other way of implementing this that I would personally consider as being simple.

The good news is that integrating a physics engine into your game - if done early on - is usually a very straightforward process.

Details will obviously vary from engine to engine but in most of them it consists of:

1. Instatiating a `World` object which will manage the simulation
2. Associating a `Body` object with each of your game objects, and adding them to the world.
3. Updating the `World` and drawing each game object using the information from their `Body`s.

**Example**

So if for instance, you had a class like this:

```
class GameObject
{
    Vector3 position;
    Quaternion rotation;
    Model model;

    void Draw()
    {
        model.RenderAt(position, rotation);
    }
}

```

You could replace the transforms information in your object with that of a physics body instead:

```
class GameObject
{
    Body body;
    Model model;

    void Draw()
    {
        model.RenderAt(body.Position, body.Rotation);
    }
}

```

Of course when creating the `Body` you'd need more information about its shape and behavior, e.g. you could specify the shape of the body using the model's bounding box.

Then it's just a matter of registering the bodies in the world and updating it.

```
// Register bodies in world
foreach(var gameObject in gameObjects)
    world.AddBody(gameObject.Body);

// Update world
world.Update(elapsed);

```

---
Tags: c++, physics, directx, directx10, physics-engine
---


# Question
Title: How do I integrate bullet physics into my game?
I downloaded the release file found here, but I'm just not sure where to start. In my game I have a number of oblongs and a sphere, I want all of these to collide with one another. (They all have meshes and associated bounding volumes)

edit - I just realised the cuboids actually have AABB's associated with them. I guess I'll have to change that at least.

What are the steps I need to follow?

# Answer
> 25 votes
Here's the basic steps you'll need to folow:

1. First **create a world** object (i.e. `btDiscreteDynamicsWorld`) to drive your physics simulation.
2. You should already have a class such as `GameObject` that perhaps stores a model along with its bounding box and position/orientation in the world. **Replace** the **position/orientation** information **with** an instance of a physics **body** object (i.e. `btRigidBody`) and when rendering the model, use the information provided by the body instead. When creating the body you'll need to provide its mass and collision shape which should match the bounding volumes you already have. I've talked about this in your other question too.
3. **Add** each of your game object's **bodies to the world** object.
4. **Update the simulation** by stepping the world (i.e. calling `stepSimulation` on your world).

And take some time to read the manual as it has a lot of information too.

---

**Edit to address comment**

> I cringe before I ask but... how do I do the very very basic stuff like simply including the right files in my game? If you need specifics I'm looking for the files that will deal with rigid body collisions. Also thank you very much for the help so far!

Well, it would appear from your comment that you've never worked with external C++ libraries before. It's been a while since I did this, but this is how I remember the process to be (in Visual Studio).

For starters I quote the manual which already explains what you need:

```
- #include “btBulletDynamicsCommon.h” in your source file
- Required include path: Bullet/src folder
- Required libraries: BulletDynamics, BulletCollision, LinearMath

```

And here's the basic steps you will have to follow to fulfill the conditions above...

**1. Preparation Step**

First of all, extract the file you downloaded into a known directory, e.g. `C:\Bullet`. You'll need to know the path to this folder later.

Inside there are two folders that you will need to reference in your project. The first is the `src` folder which holds the `.h` header files that you will *include* in your source code. The second is the `lib` folder which will hold the `.lib` library files that you will *link* to your project. Notice that including and linking are two different things.

But the `lib` folder should be empty for now, because you haven't *built* the engine yet. So refer to the manual on how to build the project using CMake and Visual Studio for instance. It's on page 7.

After you succeed, you should have at least three files in the `lib`folder: `BulletDynamics.lib`, `BulletCollision.lib` and `LinearMath.lib` (I am guessing from the manual). Now to make the connection between Bullet and your project...

**2. Include Headers**

First of all, you'll need to add the `C:\Bullet\src` folder to your project's include path options. You can do so in Visual Studio by right-clicking on your project, navigating to `Configuration Properties -> C/C++ -> General -> Additional Include Directories` and writing the directory path in there.

After setting that up, you can simply do `#include “btBulletDynamicsCommon.h”` on your code. That header seems to serve as an hub to all features you require.

**3. Link Libraries**

Finally you'll need to link the libraries mentioned above. Frist, under `Configuration Properties -> Linker -> General -> Additional Library Directories` add the path to the `lib` folder, or in other words, `C:\Bullet\lib`.

Then, under `Configuration Properties -> Linker -> Input-> Additional Dependencies`, add the name of the libraries to the list of dependencies. Separate each library with a `;` and don't forget the file extension. So for instance, you might *add* this to the end of the list: `BulletDynamics.lib;BulletCollision.lib;LinearMath.lib`.

After this you should be able to build and run your project.

---
Tags: c++, directx, physics-engine, bullet-physics
---


# Question
Title: where have the shape drawing functions gone in DirectX10?
such as the CreateTeapot function - http://msdn.microsoft.com/en-us/library/windows/desktop/bb172798(v=vs.85).aspx

Is there an equivalent in DX10? If so, how do I use it?

In DX9 you..

Declared:

```
LPD3DXMESH meshTeapot;

```

Initialised:

```
D3DXCreateTeapot(device, &meshTeapot, NULL);

```

Drew:

```
meshTeapot->DrawSubset(0);

```

Released:

```
meshTeapot->Release();

```

Is there an equivalent set of methods for drawing primitives? (to be honest the sphere is of more interest to me than the teapot!)

# Answer
> 2 votes
**Short Story**

Check the *DXUT Library* under `DXSDK_DIR\Samples\C++\DXUT`.

**Long Story**

I'm not entirely sure, but from looking over the documentation it appears that the D3DX utility library has been significantly trimmed between DX9 and DX10. See the following links for a side by side comparison of both libraries:

It seems to me that the shape drawing functions have not been relocated to another portion of the library, but removed entirely instead. You still have mesh support though, using the `ID3DX10Mesh` interface and the `D3DX10CreateMesh` function.

With further investigation I managed to find the methods you wanted in the *DXUT Library*. This is the library used in most of the official DX samples that come with the SDK. I think you should be able to find the library under `DXSDK_DIR\Samples\C++\DXUT`. In particular check the `DXUTShapes.h` file which has the following method:

```
HRESULT WINAPI DXUTCreateSphere(ID3D10Device* pDevice,
                                float fRadius,
                                UINT uSlices,
                                UINT uStacks,
                                ID3DX10Mesh** ppMesh );

```

In case you don't want to use that library because it implies having to include and link to yet another library, here's some other alternatives I could think of:

1. The easiest method and also the one I'd probably use would be to **generate a sphere in a 3D modelling application** such as Blender and import it. Make the sphere have a diameter of 1 unit and be centered around the origin, so that with a simple scaling and translation of the vertices you can adjust it to any size and location.
2. Alternatively you could also think about **generating the vertex information for the sphere procedurally** with your own code (this answer has a lot of information on how to do this) and populating a mesh object with that data.
3. Finally I can think of yet another solution but I'm not sure I would recommend it as it seems very much like a hack. That alternative would be to **initialize a minimal Direct3D 9 device** object just so so you can run the `D3DXCreateSphere` method once, store the data in memory, and then use it later to initialize the Direct3D 10 objects.

---
Tags: directx, directx10, directx9
---


title: Should I use Java or C#?

text:
# Question
Title: Should I use Java or C#?
i know a similar question has been asked before but, my question is somewhat different. I have been learning C# for a few years but nothing in game making, more like applications and web like programs. I have seen many say java is a program that is not used as much now, but my favorite games like Minecraft and Runescape are both java games. My idea for the game would be something that opens like minecraft with a splash screen then a interactive screen that lets you do things and enter a saved game or make a new one. I see a lot of java games and have never heard of any large game being in C# yet people have told me don't use/learn java. Any help would be appreciated, thanks guys!

# Answer
You're trying to choose a language just based on the popularity of some titles that have been made with them? Sure, Minecraft was made in Java. Well, Terraria (over one million copies sold), Bastion (a gazillion awards last year), and Magicka among others, were made in C#. Does it matter? I really don't think so.

Furthermore if you already have a few years of experience with C#, I don't see any advantages in changing over to Java. And by the way, if you decide to use C# and want to take advantage of modern hardware features, you could look into using something like SharpDX for instance. Otherwise, use XNA or keep a close eye on the ANX framework which is currently under development.
> 4 votes

---
Tags: c#, java
---


title: Leaf movement simulation in a 3d world

text:
# Question
Title: Leaf movement simulation in a 3d world
I am using opengl, and a simple texture or mesh to draw a leaf.

Can somebody show me a nice movement method to simulating leafs in a 3d world?

thanks, Leslie

# Answer
> 1 votes
I guess it really depend on what type of leafs you want to simulate. for each type go out and check how it's moving in the air. there is no need for an actual physical simulation just find a function that has an output similar to what the leaf moves.

here are some sample function:

```
Vec3 LeafAPosition(Vec3 lastPosition, time now, time lastTime)
{
    Vec3 result;
    result.z = lastPosition.z - constant_value1 * (now - lastTime);
    result.x = lastPosition.x - constant_value2 * cos(lasttime) + constant_value2 * cos(now);
    result.y = lastPosition.y - constant_value2 * sin(lasttime) + constant_value2 * sin(now);

    return result;
}

Vec3 LeafBPosition(Vec3 lastPosition, time now, time lastTime)
{
    Vec3 result;
    result.z = lastPosition.z - constant_value1 * (now - lastTime);
    result.x = lastPosition.x - constant_value2 * (now - lastTime);
    result.y = lastPosition.y - constant_value3 * (now - lastTime);

    return result;
}

```

I'll post more functions as soon as they came to my head.

---
Tags: opengl, simulations
---


# Question
Title: How to draw efficiently large number of objects with alpha blending?
In a 3D game i have large no. of trees with alpha value. What is the efficient way to draw all? What i tried is Taking every tree as a object and draw according to its z value and using billboarding. But large draw calls, hiting performance.

# Answer
You can use geometry instancing to draw a large number of trees in one draw call. (That article is written about Direct3D 9, but the same feature should be available in any 3D graphics API.) That should improve CPU performance, if that's indeed the bottleneck.

If the trees are alpha-blended you still have to sort them back-to-front yourself, though, which can itself be a significant performance cost. There's no good way around the necessity of sorting to get correct rendering with alpha blending (although see this answer for some alternative approaches).
> 4 votes

# Answer
You can set a maximum draw distance and use it as a limit instead drawing every tree. With Z buffer you can start by drawing the trees closer to your point of view and then move to the farthest trees. Also be sure of not drawing trees or objects if they are outside of your current view. (Culling)

Finally another way to deal with this is not drawing trees that are already hidden by other trees. For that you need to make a vector from the point of view to the target tree and see if there is a tree intersection in the middle. If its true then you don't draw the tree.

I hope I helped.
> 0 votes

---
Tags: 3d, blending
---


# Question
Title: Avoiding lag when playing sound for first time using Cue.Play
In my code I'm using `SoundBank.GetCue("cuename")` and `Cue.Play()` to play my sounds.

On the xbox whenever I first play a cue I get lag of about about one second.
**How can I avoid this?**

I'm thinking I probably have to do something like call `GetCue` (without playing it) for every `Cue` I'm going to use, however I don't have a central place where I list all cues I'll want to play, so is there an easy way to do that?

---

Update: It seems calling `GetCue` for all sounds i want to play doesn't work. I'm still getting stuttering in various places in my game when i call `GetCue....Play`.

# Answer
I've tried introspecting the `SoundBank` class hoping to find some way to know which cues are stored in it, but found no way to enumerate over all cues other than by name. The class is pretty much just a wrapper that delegates all method calls to the lower level XACT3 engine.

So I'll have to suggest that you go with your current train of thought, by creating your own list of cues, for example in a txt file, and doing a preload step in your game where you enumerate over all names in the list and call `GetCue` for each of them.
> 2 votes

---
Tags: xna, c#, sound-effects
---


# Question
Title: WriteObject<T> in XNA with existing ContentWriters
I have quite a lot of custom content pipeline components, and I was just wondering if under the hood XNA knows about these things when doing its magic...

Here is my scenario.

I have animation objects which basically contain 2d animation frames and timings etc, which can be loaded as self contained objects or can be embedded within other object. Now I was expecting that my CustomObjectAWriter could contain an instance to AnimationObjectAWriter and internally just call through to that to write out each animation object, i.e:

```
<SomeCustomObjectA>
    <SomeCustomElementA>
        ...
    </SomeCustomElementA>
    <SomeCustomElementB>
        ...
        <AnimationObjectA>
            ...
        </AnimationObjectA>
    </SomeCustomElementB>
</SomeCustomObjectA>

```

However as AnimationObjectAWriter has its Write method protected I am unable to access it, however I was wondering if WriteObject will know of the AnimationObjectAWriter so if I did `WriteObject<AnimationObjectA>(animationObjectAInstance)` would this work?

# Answer
Yes that will work, although if it's just simple XML-\>objects you probably don't need custom writers/readers at all.

See: Automatic XNB serialization in XNA Game Studio 3.1

See also: Shawn Hargreaves Blog Index: Content Pipeline
> 1 votes

---
Tags: xna, xna-content-pipeline
---


# Question
Title: Resources of realistic water simulation?
I want to study water simulation, with a a demo with source code which using physically-based methods(Eulerian approaches or Lagrangian approaches).

How can I get some examples?

# Answer
> 10 votes
Here is one, with source

Fluid simulation for video games series : Part 1 - 9

# Answer
> 4 votes
Q-Games presented their system for Pixeljunk Shooter at SIGGRAPH:

Disclaimer: I got this information from another StackOverflow post.

I've also seen those slides in PDF/Powerpoint form, but don't know where they are at the moment. All of the information is available in the Youtube videos, however.

---
Tags: 3d, physics, simulations
---


# Question
Title: How does a game's frame rate change for each missed vsync?
I seem to remember reading somewhere that a game's frame rate is halved each time it misses a vsync. In other words, the number of frames per second decreases to 1/2, 1/4, and 1/8 the normal rate for the first, second, and third missed vysnc cycles (respectively) rather than to 1/2, 1/3, and 1/4 the normal rate.

Is this correct? If so, why?

# Answer
> 2 votes
It does not get halved for each missed vsync. Framerates go as the refresh rate of the screen divided by the number of vsync periods you need to get a new frame out, so if the refresh rate is 60 Hz (typical for TVs), then your framerate can be 60, 30, 20, 15, 12, 10, 8.6, 7.5, etc.

# Answer
> 1 votes
Framerate is calculated by taking the duration of one or more past frames, averaging them, and dividing one second by the result to get the number of frames that would be drawn in a second assuming each would take as long as the average.

```
avgTimeMS = (totalTimeMS / numFrames)
fps = 1000 / avgTimeMS

```

This would yield the average number of frames per second over the last *$numFrames* frames. If *$numFrames* is 1, you get the effective frame rate of the last frame. If *$numFrames* is 60, you'll get the averaged frame rate over the last 60 frames (about 1 second at 60fps).

Assume we happen to have a steady framerate of 16.666ms per frame, and that we're averaging the last 10 frames, the last of which has now doubled (2 * 16.666) since we missed a vsync. We would have:

```
totalTimeMS = (9 * 16.666) + (1 * 33.333)
numFrames = 10
fps = 54.54

```

Now assume our numFrames is 1, and we skip a frame:

```
totalTimeMS = 1 * 33.33;
numFrames = 1
fps = 30

```

Your figures, then, are correct only when *$numFrames* is 1, since 30 is half of 60 (which I'm assuming matches vsync.)

So the perceived drop in frame rate due to one long frame is directly related to the number of frames you take in your average. When you skip a frame, you're increasing *$totalTimeMS* and not increasing *$numFrames*.

# Answer
> 1 votes
To supplement the other answers...

What vsync does is synchronize the buffer swap with your monitors vertical refresh rate. So what happens to frame rate if you miss this is that the synchronization must wait until the next refresh. So - if you're refreshing at 16ms intervals (just to keep things simple for the purposes of this explanation) but a frame needs 17ms to draw, it will miss the sync interval. Because the buffer swap is locked to the refresh rate it can't take place on the 17ms mark - it needs to wait until the next interval, which will be at 32ms. Likewise if a frame needs 33ms it will miss the intervals at 16ms and 32ms, and will need to wait until the 48ms interval.

---
Tags: frame-rate, vsync
---


# Question
Title: GO Game, placing stones on grid intersections
I'm currently making a GO game and I am stuck on the most basic functionality. That functionality is being able to click on the intersections of the grid and ONLY the intersections to place a stone, either can be black or white. I have made a 2D array to represent the board but what I don't really understand is:

* How do I draw the stones on the grid?
* How do I reference the GUI grid to the 2D array?

# Answer
> 1 votes
i added some more stuff:

```
import java.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import java.util.*;
import java.util.List;
import javax.swing.*;
enum Stone {
    vacant, black, white; // maybe add edge?
    Stone otherColor() {
        if (this == black) return white;
        else if (this == white) return black;
        else
            return vacant;
    }
}
interface Board {
    int size();
    Stone at(int x, int y);
}
interface MutableBoard extends Board {
    int size();
    Stone at(int x, int y);
    void setAt(int x, int y, Stone color);
}
class BoardImpl implements MutableBoard {
    BoardImpl(int n) {
        this.n = n;
        stones = new Stone[n][n];
        clear(n);
    }
    private void clear(int n) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                stones[i][j] = Stone.vacant;
    }
    @Override public int size() {
        return n;
    }
    @Override public Stone at(int x, int y) {
        return stones[x][y];
    }
    @Override public void setAt(int x, int y, Stone color) {
        stones[x][y] = color;
    }
    final int n;
    private final Stone[][] stones;
}
class Block {
    Block(Board b, int i, int j, boolean[][] processed) {
        this.b = b;
        this.processed = processed;
        n = b.size();
        this.who = b.at(i, j);
        points = new LinkedList<Point>();
        grow(i, j);
        countLiberties();
    }
    int liberties() {
        return l;
    }
    Stone color() {
        return who;
    }
    public String toString() {
        return who + " " + points.size() + " stone(s), " + l + " liberties" + points;
    }
    static List<List<Block>> findBlocks(Board b) {
        int n = b.size();
        boolean[][] processed = new boolean[n][n];
        List<Block> blackBlocks = new LinkedList<Block>();
        List<Block> whiteBlocks = new LinkedList<Block>();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                Stone who = b.at(i, j);
                if (!who.equals(Stone.vacant) && processed[i][j] == false) {
                    Block g = new Block(b, i, j, processed);
                    switch (who) {
                        case black:
                            blackBlocks.add(g);
                            break;
                        case white:
                            whiteBlocks.add(g);
                            break;
                        default:
                            System.out.println("findGroups " + b + g + who);
                    }
                }
            }
        List<List<Block>> blocks = new LinkedList<List<Block>>();
        blocks.add(blackBlocks);
        blocks.add(whiteBlocks);
        return blocks;
    }
    private void grow(int i, int j) {
        if (!(0 <= i && i < n && 0 <= j && j < n)) return;
        if (!processed[i][j]) {
            Stone who = b.at(i, j);
            if (who.equals(this.who) || who.equals(Stone.vacant)) processed[i][j] = true;
            if (who == this.who) {
                points.add(new Point(i, j));
                grow(i - 1, j);
                grow(i, j - 1);
                grow(i, j + 1);
                grow(i + 1, j);
            }
        }
    }
    private void countLiberties() {
        l = 0;
        processed = new boolean[n][n];
        for (int k = 0; k < points.size(); k++) {
            Point p = (Point) points.get(k);
            count(p.x - 1, p.y);
            count(p.x, p.y - 1);
            count(p.x, p.y + 1);
            count(p.x + 1, p.y);
        }
    }
    private void count(int i, int j) {
        if (0 <= i && i < n && 0 <= j && j < n && !processed[i][j]) {
            if (b.at(i, j) == Stone.vacant) l++;
            processed[i][j] = true;
        }
    }
    static List<Block> capturedStones(List<List<Block>> blockLists) {
        List<Block> dead = new LinkedList<Block>();
        List<Block> blocks = blockLists.get(0);
        if (blocks != null) for (int i = 0; i < blocks.size(); i++) {
            Block g = (Block) blocks.get(i);
            // System.out.println(g);
            if (g.liberties() == 0) dead.add(g);
        }
        blocks = blockLists.get(1);
        if (blocks != null) for (int i = 0; i < blocks.size(); i++) {
            Block g = (Block) blocks.get(i);
            // System.out.println(g);
            if (g.liberties() == 0) dead.add(g);
        }
        return dead;
    }
    private Stone who;
    List<Point> points;
    private int n;
    private int l;
    transient private Board b;
    transient private boolean[][] processed;
}
class Move {
    Move(Stone stone, Point point) {
        if (stone.equals(Stone.vacant)) throw new RuntimeException("bad move");
        this.stone = stone;
        this.point = point;
    }
    Move(Stone stone, int x, int y) {
        this(stone, new Point(x, y));
    }
    void make(MutableBoard board) {
        board.setAt(point.x, point.y, stone);
        List<List<Block>> blockLists = Block.findBlocks(board);
        List<Block> capturedBlocks = Block.capturedStones(blockLists);
        if (capturedBlocks != null && capturedBlocks.size() > 0) {
            Block fromThisMove = null;
            for (Block block : capturedBlocks)
                if (block.points.contains(point) && block.points.size() == 1) {
                    fromThisMove = block;
                    break;
                }
            if (fromThisMove != null) capturedBlocks.remove(fromThisMove);
            for (Block block : capturedBlocks) {
                captured = capturedBlocks;
                for (Point point2 : block.points)
                    board.setAt(point2.x, point2.y, Stone.vacant);
            }
        }
    }
    void unmake(MutableBoard board) {
        if (captured != null) for (Block block : captured) {
            Stone who = block.color();
            for (Point point : block.points)
                board.setAt(point.x, point.y, who);
        }
        board.setAt(point.x, point.y, Stone.vacant);
    }
    final Point point;
    final Stone stone;
    List<Block> captured;
}
class Line {
    Line(Point p1, Point p2) {
        this.p1 = p1;
        this.p2 = p2;
    }
    public void paint(Graphics g) {
        g.drawLine(p1.x, p1.y, p2.x, p2.y);
    }
    final Point p1, p2;
}
class Gui extends JPanel {
    Gui(TopPanel game, MutableBoard board, int width, int height) {
        this.game = game;
        this.board = board;
        x0 = 10;
        y0 = 10;
        this.n = board.size();
        rectangle = new Rectangle(1, 1, n, n);
        dx = width / n;
        dy = height / n;
        for (int i = 0; i < n; i++)
            addLine(x0, y0 + i * dy, x0 + (n - 1) * dx, y0 + i * dy);
        for (int j = 0; j < n; j++)
            addLine(x0 + j * dx, y0, x0 + j * dx, y0 + (n - 1) * dy);
        addMouseListener(new MouseListener() {
            @Override public void mouseReleased(MouseEvent e) {}
            @Override public void mousePressed(MouseEvent e) {}
            @Override public void mouseExited(MouseEvent e) {}
            @Override public void mouseEntered(MouseEvent e) {}
            @Override public void mouseClicked(MouseEvent e) {
                Point2D.Float point = toBoardCoordinates(e.getPoint());
                Point closest = new Point(Math.round(point.x), Math.round(point.y));
                if (ispointOnBoard(closest)) {
                    double distance = point.distance(closest);
                    if (distance < .35) if (Gui.this.board.at(closest.x, closest.y) == Stone.vacant) Gui.this.game.makeMove(closest);
                    else
                        System.out.println(closest + " is occupied!");
                } else
                    System.out.println(closest + " is off the board!");
            }
        });
    }
    private Point2D.Float toBoardCoordinates(Point screen) {
        return new Point2D.Float((screen.x - x0) / (float) dx + 1, (screen.y - y0) / (float) dy + 1);
    }
    private Point toScreenCoordinates(Point board) {
        return new Point(x0 + (board.x - 1) * dx, y0 + (board.y - 1) * dy);
    }
    private boolean ispointOnBoard(Point point) {
        return rectangle.contains(point);
    }
    Move createMove(Stone stone, Point point) {
        if (ispointOnBoard(point)) return new Move(stone, point);
        else
            throw new RuntimeException(point + " is off the board!");
    }
    void makeMove(Move move) { // currently we do not allow vacant moves
        repaint(); // use the long form!
    }
    void unmove(Move move) {
        repaint();
    }
    private void addLine(int x1, int y1, int x2, int y2) {
        this.lines.add(new Line(new Point(x1, y1), new Point(x2, y2)));
    }
    private void addLine(Point p1, Point p2) {
        this.lines.add(new Line(p1, p2));
    }
    private Image blackStone(int width, int height, Color color) {
        Image img = createImage(width, height);
        Graphics g = img.getGraphics();
        g.setColor(color);
        g.fillRect(0, 0, width, height);
        g.setColor(Color.black);
        g.fillOval(0, 0, width - 1, height - 1);
        g.drawOval(0, 0, width - 1, height - 1);
        // these two are different from
        // either g.fillOval(-1, -1, width+1, height+1);
        // or g.fillOval(0, 0, width-1, height-1);
        g.setColor(Color.white);
        g.drawArc(width / 5, height / 5, width * 3 / 5, height * 3 / 5, -20, -60);
        return img;
    }
    private Image whiteStone(int width, int height, Color color) {
        Image img = createImage(width, height);
        Graphics g = img.getGraphics();
        g.setColor(color);
        g.fillRect(0, 0, width, height);
        g.setColor(Color.white);
        g.fillOval(0, 0, width - 1, height - 1);
        g.setColor(Color.black);
        g.drawOval(0, 0, width - 1, height - 1);
        g.drawArc(width / 5, height / 5, width * 3 / 5, height * 3 / 5, -20, -60);
        return img;
    }
    private void paintStone(Graphics g, int i, int j) {
        if (board.at(i, j) != Stone.vacant) {
            if (board.at(i, j) == Stone.black) g.setColor(Color.black);
            else if (board.at(i, j) == Stone.white) g.setColor(Color.white);
            else
                throw new RuntimeException("oops");
            Point screen = toScreenCoordinates(new Point(i, j));
            if (black == null || white == null) g.fillOval(screen.x - dx / 2, screen.y - dy / 2, dx, dx);
            else {
                if (board.at(i, j) == Stone.black) g.drawImage(black, screen.x - dx / 2, screen.y - dy / 2, dx, dy, null);
                else
                    g.drawImage(white, screen.x - dx / 2, screen.y - dy / 2, dx, dy, null);
            }
        }
    }
    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        if (game != null) {
            black = blackStone(dx, dy, getBackground());
            white = whiteStone(dx, dy, getBackground());
            Color color = g.getColor();
            for (Line line : lines) {
                line.paint(g);
            }
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    paintStone(g, i, j);
            g.setColor(color);
        }
    }
    private final TopPanel game;
    private final int n;
    final MutableBoard board;
    private final int x0, y0;
    private final int dx, dy;
    private final Rectangle rectangle;
    private final Set<Line> lines = new LinkedHashSet<Line>();
    private Image black, white;
    private static final long serialVersionUID = 1L;
}
class Game {
    Game(int n) {
        board = new BoardImpl(n);
    }
    Move makeMove(Point point) {
        Move move = new Move(turn, point);
        move.make(board);
        moves.add(move);
        turn = turn.otherColor();
        return move;
    }
    Move unmove() {
        if (moves.size() > 0) {
            Move move = moves.remove(moves.size() - 1);
            move.unmake(board);
            turn = turn.otherColor();
            return move;
        } else {
            System.out.println("no moves to undo!");
            return null;
        }
    }
    final MutableBoard board;
    Stone turn = Stone.black;
    final java.util.List<Move> moves = new LinkedList<Move>();
}
class TopPanel extends JPanel {
    static final String unmove = "Unmove";
    static final String newgame = "New Game";
    TopPanel(Game game) {
        init();
        this.game = game;
        gui = new Gui(this, game.board, 500, 520);
        Dimension d = new Dimension(510, 530);
        gui.setSize(d);
        gui.setPreferredSize(d);
        gui.setMaximumSize(d);
        gui.setMinimumSize(d);
        gui.setOpaque(true);
        gui.setBackground(Color.orange);
        add(gui);
    }
    void makeMove(Point point) {
        Move move = game.makeMove(point);
        if (move != null) gui.makeMove(move);
    }
    void unmove() {
        Move move = game.unmove();
        if (move != null) gui.unmove(move);
        else
            System.out.println("no moves to undo!");
    }
    private void init() {
        setLayout(new BoxLayout(this, BoxLayout.Y_AXIS));
        JButton jButton = new JButton(newgame);
        jButton.setName(newgame);
        add(jButton);
        jButton = new JButton(unmove);
        jButton.setName(unmove);
        add(jButton);
        jButton.addActionListener(new ActionListener() {
            @Override public void actionPerformed(ActionEvent e) {
                Object object = e.getSource();
                if (object instanceof JButton) if (((JButton) object).getName().equals(unmove)) unmove();
                else if (((JButton) object).getName().equals(newgame)) {
                    //
                }
            }
        });
    }
    final Gui gui;
    Game game;
    private static final long serialVersionUID = 1L;
}
class Main {
    private static void build(Container c) {
        c.add(new TopPanel(new Game(19)));
    }
    private static void createAndShowGUI() {
        JFrame frame = new JFrame("Board");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        build(frame.getContentPane());
        frame.setPreferredSize(new Dimension(520, 600));
        frame.pack();
        frame.setVisible(true);
    }
    public static void main(String[] args) {
        javax.swing.SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                createAndShowGUI();
            }
        });
    }
}

```

# Answer
> 1 votes
> I have made a 2D array to represent the board

For GO, think of the 2D array as **array of placement/intersection points**, instead of array of grid (rectangle) on the board. Then to draw the board, just draw normal grids based on that array length, but **offset it**.

> How do I draw the stones on the grid?

Pick a number, say "size", as the size of a grid. Define the top left position of the board in the window, say "boardX" and "boardY". the 2d array you defined earlier should be an array of byte or char or int or whatever that able to represent stones on the grid. You will look up the array to find out whether a given position has stone or not. for example, `array[2][2] == 1` checks whether player 1's stone is on position 2,2.

```
size = 10;
stoneSize = 10;
boardX = 20; boardY = 20

void drawStone(col, row, color) {
 x = col * size + boardX;
 y = row * size + boardY;
 drawCircle(x, y, color);
}

void drawStones(array) {
 for(int i = 0; i < array.length; ++i) {
  rowArr = array[i];
  for(int j = 0; j < rowArr.length; ++j) {
   if(array[i][j] == 0) { /* nothing here */ }
   else if(array[i][j] == 1) { drawStone(i, j, Color.WHITE); }
   else { drawStone(i, j, Color.BLACK); }
  }
 }
}

```

> How do I reference the GUI grid to the 2D array?

You should have the information of the click's position.

```
gridX = (clickPositionX - boardX) / (size * gridColumnCount);
gridY = (clickPositionY - boardY) / (size * gridRowCount);
array[gridX][gridY] // <- this is the clicked grid in 2d array

```

The code is pretty sloppy, but I hope you get the idea.

# Answer
> 0 votes
You can override the JFrame's paint() method. Use the Graphics that it gives you to call methods like drawLine and fillRect to do your drawing. Then when you get a mouse or touch events, you'll calculate which grid point it's nearest and whether it's close enough to count.

---
Tags: java
---


# Question
Title: Designing Efficient 2D Collision for Topdown Shooter
This makes it the first time I'm posting here, so apologies if I stumble over beloved conventions.

Currently, I'm trying to figure out how I want to handle collisions for a large number of entities on screen (a bullet hell, top-down shooter). I've done a prototype of the game with some friends in the past before and we reached about 300 circular entities (a point with a radius "hitbox") checked against 3 every 1/60 seconds before considerable performance drops. The implementation was cringe worthy; due to lack of experience and a very stringent deadline, we didn't have time to do anything but a brute force distance check with each entity, making 900 pythagorean calculations per game loop.

This time I'd like to approach it with some intelligence. Since I'm simply checking for collision and not retaining any kind of directional information, I've managed to come up with two strategies. Unfortunately, they have their benefits and drawbacks:

1. **Localized Checking** \- Essentially, creating a 2D array and checking only cells that the 3 entities exist in. The problem with this is that edge cases become an issue - say, if an allied entity is on the edge of a cell and an enemy entity is on the adjacent edge of an adjacent cell, I should have to check both, meaning there would be additional adjacent cell checks. While I can overcome this with a mandated "all cells that share a vertex" check and reduce the size of the cells to \[standard entity radius * 2\], it restricts the size of entities or forces me to use a separate system of checking for larger-than-standard entities. Obviously, avoiding this would be ideal.

* More importantly, while this drastically lowers calculations made during collision detection, the reassignment of an entity to another cell due to movement would create a computational step on all moving entities (most of them) during each iteration of the game loop. Furthermore, an additional call must be made to move an object from one cell to another when it has to migrate into another cell, which will be much more common as the cell size drops. *This is not ideal*.
2. **Mathematical Checking** \- The theory goes that if we think of bullet patterns not as separate entities but as *mathematical formulas expressed as the intersection of equations (linear, quadratic, etc.) and a sinusoidal function (determining position of an entity based on the y position on that function)*, checking would be simplified to 3 entities against the sum of all formulas present. Unfortunately, I lack the mathematical background to do this. Furthermore, designing bullet patterns becomes a giant headache, so the cost of designing levels rises (and I am of the opinion that the most expensive work is that performed by humans).

* What's more, if we take a basic curved formula such as a hyperbola, it is incredibly difficult to keep entities perfectly circular along the curves. Without a really good grasp of math, entities would appear oblong or pinched as the entity moves across the curve. This is extremely difficult to graphically represent without doing it dynamically, which would limit the visual vocabulary I am able to utilize. *Also not ideal*.

I'm not exactly sure how I'd like to proceed with this. Any thoughts out there? Standards that I've managed to miss?

# Answer
I can't leave comments yet but have you looked into Box2D for collision detection? I'm not sure what environment you're working in but it's been ported for different platforms. I takes a little time to learn but I personally think it's worth the time.
> 2 votes

# Answer
If your rate of fire is high, bullet speed fast and the target movement speed is relatively slow. A simple optimisation would be to use your original method with a larger collision circle that represents the maximum movement of the target in the time of flight of the bullet and exclude every bullet that fails the test from further physics checking. If a large portion of shots miss by a considerable distance this could speed things up a bit without a great deal more code.
> 1 votes

---
Tags: collision-detection
---


# Question
Title: COLLADA, loading, the modelling/animation process?
So, we're making a game in C++ using SDL - a TDS. It was originally intended to be 2D, but our lead programmer wanted to redo the engine and make it 3D. And, now, we really don't know how to go about it.

What model and animation formats should we be using? We're considering COLLADA, and if I understand correctly, we export models as .dae, then the animators import them, make the animation, then export as .dae. We then load them into the game using AssImp, then render, am I right? Or does the animator build a rig, save it as .dae, then the modeller builds on that, saves as .dae, then the animator makes the animations?

Thanks a lot for any help, really appreciate it.

# Answer
I don't think COLLADA makes for a good format to work with. The standard is too open and seems to be implemented differently across different software. So some features might not be readable by other software and vice-versa.

Ideally you would have your working-assets in a proprietary format, eg. the one of the 3D modelling/animation package you're using. That way you can leverage the full potential of the 3D package and not care about compatibility and format-specifications.

Exporting your final assets to COLLADA is ok though. As long as it covers your needs and you got a decent parser for it, then go for it. I suggest you create one asset for testing and import it with the parser at hand. Then you'll see if everything gets imported correctly. Otherwise you should probably use another format... but that won't be too much of an issue, because you'll only generate the "production asset" at the end of your workflow.
> 2 votes

---
Tags: c++, 3d, animation, models, collada
---


# Question
Title: How to convert screen space into 3D world space?
I am trying to make a 3D model to look at the mouse position. Currently I have this code:

```
MouseState mouseState = Mouse.GetState();

Matrix world = Matrix.CreateTranslation(0, 0, 0);

Vector3 source = new Vector3((float) mouseState.X, 1f, (float) mouseState.Y);
Vector3 mousePoint = GraphicsDevice.Viewport.Unproject(source, this.game.Camera.Projection, this.game.Camera.View, world);

System.Console.Out.WriteLine("x: " + mousePoint.X + ", Y: " + mousePoint.Y + ", Z: " + mousePoint.Z);

```

I get output such as this in the console:

```
x: 0.1787011, Y: 999.7204, Z: 299.7723
x: 0.08917224, Y: 999.8602, Z: 299.8862
x: 0.05908892, Y: 999.9069, Z: 299.9241
x: 0.04422692, Y: 999.9302, Z: 299.9431
x: 0.03303542, Y: 999.9477, Z: 299.9573
x: 0.03109217, Y: 999.9508, Z: 299.9598
x: 0.02930491, Y: 999.9535, Z: 299.9621
x: 0.02770578, Y: 999.9559, Z: 299.9641
x: 0.0263205, Y: 999.9581, Z: 299.9659

```

The player is positioned at `Vector3.Zero`. The camera is positioned at `new Vector3(0.0f, 1000.0f, 300.0f)`.

I would like to get output such as `X: -300, Y: 0, Z: -300` when moving the mouse to screen top left and when moving the mouse to screen center where the model is located I want to have `X: 0, Y: 0, Z: 0`. So I want the world coordinates of the mouse so that I can make the player rotate towards the mouse.

Basically I want to map mouse X into world X, mouse Y to world Z and the world Y coordinate can be 0 at all times.

# Answer
I solved it after days of googling. I had to create a plane to ray cast to, then calculate denominator and numerator.

```
        /// <summary>
        /// Returns the mouse X, Y and Z coordinates on the world so that the Y is always on ground zero (0).
        /// </summary>
        /// <param name="game"></param>
        /// <returns></returns>
        public static Vector3 GetMouseWorldPosition(Game game)
        {
            GraphicsDevice graphicsDevice = game.GraphicsDevice;
            MouseState mouseState = Mouse.GetState();

            Vector3 nearSource = new Vector3((float) mouseState.X, (float) mouseState.Y, 0f);
            Vector3 farSource = new Vector3((float) mouseState.X, (float) mouseState.Y, 1f);
            Vector3 nearPoint = graphicsDevice.Viewport.Unproject(nearSource, game.Camera.Projection, game.Camera.View, Matrix.Identity);
            Vector3 farPoint = graphicsDevice.Viewport.Unproject(farSource, game.Camera.Projection, game.Camera.View, Matrix.Identity);

            // Create a ray from the near clip plane to the far clip plane.
            Vector3 direction = farPoint - nearPoint;
            direction.Normalize();

            // Create a ray.
            Ray ray = new Ray(nearPoint, direction);

            // Calculate the ray-plane intersection point.
            Vector3 n = new Vector3(0f, 1f, 0f);
            Plane p = new Plane(n, 0f);

            // Calculate distance of intersection point from r.origin.
            float denominator = Vector3.Dot(p.Normal, ray.Direction);
            float numerator = Vector3.Dot(p.Normal, ray.Position) + p.D;
            float t = -(numerator / denominator);

            // Calculate the picked position on the y = 0 plane.
            Vector3 pickedPosition = nearPoint + direction * t;

            return pickedPosition;
        }

```
> 2 votes

# Answer
You need the inverse of the camera\_to\_screen matrix.

The 3D pipeline overall looks like this:

```
model -> world -> camera -> viewport -> screen

```

The world\_to\_camera matrix is the usual rotation/translation matrix you construct for a 3D camera system. Inverting it is trivial: https://stackoverflow.com/questions/695043/how-does-one-convert-world-coordinates-to-camera-coordinates

The camera-\>viewport matrix is your projection matrix; inverting that is trivial if you know how to construct it in the first place: http://www.gamedev.net/topic/478055-perspective-projection-matrix/

The viewport\_to\_screen matrix is generally a simple transformation that maps the coordinate space \[-1,-1\]:\[1,1\] into \[0,0\];\[ScreenWidth,ScreenHeight\]. You don't usually need to generate this matrix yourself as it's taken care of by the graphics hardware automatically. The order of operations of the matrix is to scale by half the screen size, then to translate by half the screen size. Inverting those operations is basic algebra.

Multiply those inverted matrices together in the opposite order to get your screen-\>world matrix. You can now multiply by the vector (ScreenX,ScreenY,Near,1) to get the world position of the mouse cursor on the near clipping plane in world space.

If you need to do object picking at some point, you can take that point and the camera's position to generate a ray to do ray-collision test to find the object the cursor is pointing at.
> 10 votes

# Answer
Xna has a built im method for doing this. GraphicsDevice.Viewport.Unproject

Checkout the code sample from here to see how to implement it:

http://create.msdn.com/en-US/education/catalog/sample/picking\_triangle
> 2 votes

---
Tags: xna, c#, 3d
---


# Question
Title: How to implement different weapons in player's hands?
What's the general approach to support variety of weapons in player's hands?

I currently have a 3d model that has empty hands. Should I have separate weapon models that I will just create and render into players hands in the game, or should I implement them in the actual model instead?

If they are not in the model, then how do I make the weapon appear in the right position, especially when considering that I want the player to have a walking animation and perhaps running too.

# Answer
In general, the way this works is very simple. Your characters have a list of bones, which are animated by the animation system. You renderer takes these animated bones and uses them to draw the mesh via skinning or some similar technique.

So you simply add an extra bone to the animation system. This bone is not weighted to any vertices; it's there solely to position objects your character carries. Typically, this bone is either a child of the animation root or a child of the hand.

When you execute your animation system and get the bone-to-object space matrices for each bone, you get one for the "extra" bone as well. Just use that as the transform for the object you want the character to "carry". If the animators and modelers did their jobs (animation must position and orient the bone correctly, modelers must build the mesh to fit the hands and center the object on the place where the character will hold it), then the object will appear in the character's hand.
> 2 votes

# Answer
You want to get the position and general orientation of the hand, then put the weapon in it. This saves you from having to have duplicate character models for each weapon.

You then might want to consider setting the other hand after this has happened to be positioned on a forward grip, or on the barrel of a shotgun, or just by your side for a pistol etc.
> 1 votes

---
Tags: xna, 3d
---


# Question
Title: How often to SendData() in my peer-ro-peer XNA game?
Currently I call

```
myLocalNetworkGamer.SendData(myPacketWriter, ...)

```

every Update(). 60 times a second sounds too much. Is there an inbuilt way to only send less often? How often should network players update their position?

**UPDATE** It is a real time shooter. Also does XNA backlog the updates if the other peer is not receiving them fast enough or are packets dropped in this case?

# Answer
There are lots of factors to take into account, type of game, speed of connection, number of peers, how much data you want to send, if people have limited bandwidth allowances you don't want to over use, is this over a LAN or internet, etc.

Lets say for example, you have a 64kbs (64 kilobits per second or 8 kilobytes per second) connection (which is slow by modern standards for average home internet but not necessarily slow for phones), with 8 players and you want to update as often as possible for a real-time game, you'll need to send to 7 people at most 9kbs each (64/7). Assuming your update packet size was 1kb (1024 bits or 128 bytes) for each update, you'd only want to send an update roughly 8 times per second, or put another way for a game running at 60fps, every 7 or so frames.

You'll need to do your own calculations based on what your target bandwidth is, packet size, etc. There's nothing standard that will scale this for you, however it's fairly easy to keep track of when the last update was done and not send another for X frames or X milliseconds, etc. When calculating the size of your packets, you'll also need to take into account packet header sizes which will potentially vary by the platform you use and apply and a specific overhead to sending anything (which for UDP over IPv4 seems to be 20 bytes).

UPDATED due to extra info (and switching TCP reference above for what it should have been, UDP): You'll want to be using UDP instead of TCP as the overall overhead of TCP is more than you want in a real-time game. You don't need/want the guaranteed delivery of packets as it'll require each packet to return a successfully delivered reply (plus by the time it's then re-sent the data is out of date anyway). For the internet you'll need to assume at least a certain level of packet loss and how you cope with this (you can even simulate this in your code by randomly not sending or not sending every Xth packet). You'd also using UDP need to take into account that packets can arrive in a different order to that being sent, so you'd also probably want to send some sort of number (be it time, or some incrementing value) to indicate that if you receive packet 200 first, then that's the current good state and then receiving packet 199 it should be ignored.

You could also potentially do other network optimisations, such as sending a less frequent "big" update (say position, orientation, velocity, etc) with more information, then send more "smaller" partial updates (such as controller input, or delta's). Smaller packets allow more to be sent for the same bandwidth (again you need to take into account packet header overhead, you want to have a good ratio of actual data sent to header size).

This mostly applies to peer-2-peer over the internet. If this is just for a local area network (unclear from the question), then it probably isn't a concern on how often you send the data unless the actual sending or receiving the data is somehow computationally expensive (not usually). You'd most likely want to send it as fast as you can in a LAN environment for responsiveness.
> 2 votes

# Answer
There's no built-in mechanism to run code at a different rate because it's trivial to implement that yourself. Here's an example of how to do it:

```
public class YourGame : Game
{
    float timer = 0f;
    float delay = 1f / 10f;

    public void Update(GameTime gameTime)
    {
        timer += (float) gameTime.ElapsedGameTime.TotalSeconds;
        if(timer >= delay)
        {
            // Send data here
            timer -= delay;
        }
    }
}

```

In this example your data would be sent 10 times per second instead of 60 times. You could easily update the `delay` variable dynamically in order to implement the ideas Roger Perkins discussed on his answer.
> 2 votes

---
Tags: xna, xna-4.0, multiplayer
---


title: Get points on a line between two points

text:
# Question
Title: Get points on a line between two points
I'm making a simple space game in JavaScript, but now I've hit a wall regarding vectors.

The game view is top-down on a 2d grid. When the user clicks on the grid, the space ship will fly to that spot.

So, if I have two sets of points:

```
{ x : 100.2, y : 100.6 }; // the ship
{ x : 20.5,  y : 55.95 }; // the clicked coordinates

```

If the game loop ticks at 60 iterations per second, and the desired ship velocity is 0.05 points per tick (3 points per second), how do I calculate the new set of coordinates for the ship for each tick of the game loop?

p.s. I do not want to account for inertia, or multiple vectors affecting the ship, I just want the ship to stop whatever it is doing (i.e. flying one way) and move to the clicked coordinates at a static speed.

# Answer
> 11 votes
In Pseudocode:

```
speed_per_tick = 0.05
delta_x = x_goal - x_current
delta_y = y_goal - y_current
goal_dist = sqrt( (delta_x * delta_x) + (delta_y * delta_y) )
if (goal_dist > speed_per_tick)
{
    ratio = speed_per_tick / goal_dist
    x_move = ratio * delta_x
    y_move = ratio * delta_y
    new_x_pos = x_move + x_current
    new_y_pos = y_move + y_current
}
else
{
    new_x_pos = x_goal
    new_y_pos = y_goal
}

```

# Answer
> 24 votes
## LERP - Linear Interpolation

I gave this answer for a similar problem some days ago, but here we go:

Linear Interpolation is a function that gives you a number between two numbers, based on the progress. You could actually, get a point between two points.

---

## The Great Formula - How to calculate it

The general LERP Formula is given by `pu = p0 + (p1 - p0) * u`. Where:

* pu: The result number
* p0: The initial number
* p1: The final number
* u: The progress. It is given in percentage, between 0 and 1.

---

## How to get percentage

You may be wondering, "How can I get this percentage!?". Don't worry. It's like this: How much time the point will take to travel from the start point to the end point? Ok, now divide it by the time that has already passed. This will give you the percentage.

Something like this: `percentage = currentTime / finalTime;`

---

## Calculating Vectors

To get a resultant vector, all you need to do is apply the formula two times, one for X component and one for Y component. Like so:

```
point.x = start.x + (final.x - start.x) * progress;
point.y = start.y + (final.y - start.y) * progress;

```

Some frameworks/engines allow you to do the above in a single operation on the vector:

```
point = start + (final - start) * progress;
// or even
point = start.lerp(final, progress);

```

---

## Calculating variate time

You may want to have your points to travel at a 0.5 points speed, yea? So let's say, a longer distance should be traveled in a longer time.

You can do it as follow:

* Get the distance length For it, you'll need two things. Get the `distance` vector, then find its length value.

`distancevec = final - start;`
`distance = distancevec.length();`

If you don't know vectors math, you can calculate a vector length with this formula: `d = sqrt(pow(v.x, 2) + pow(v.y, 2));`.

* Get the time it will take and update `finaltime`. This one is easy. As you want to have each tick travel a 0.5 length, we just have to do a simple division and see how many ticks we got.

`finalTime = distance / 0.5f;`

Done.

**NOTICE:** Maybe, this may not be the intended speed for you, but this is the right one. So you have a linear movement, even on diagonal moves. If you apply `x += 0.5f` and `y += 0.5f`, the resultant speed would be different at diagonals (given by the length formula above)

# Answer
> 4 votes
This can be done by computing the normal of the direction and then computing the current position via the parametric equation

```
newPoint = startPoint + directionVector * velocity * t

```

Where t is the time elapsed since the ship started traveling in the desired direction. You can also perform this per update via

```
newPoint = currentPoint + directionVector * velocity * timeDelta

```

And you just calculate this at every frame/physics/etc. update until the ship reaches its destination.

---
Tags: javascript, vector, coordinates
---


# Question
Title: How can I get rid of the diagonal wires in wireframe boxes?
I create a box with a material and set that material to be wire framed.

```
Box b1 = new Box(new Vector3f(1.0f, -2.0f, 1.0f), 1.0f, 1.0f, 1.0f);
Geometry geom1 = new Geometry("Box", b1);
Material mat1 = new Material(assetManager, "Common/MatDefs/Misc/Unshaded.j3md");
mat1.getAdditionalRenderState().setWireframe(true);
mat1.setColor("Color", ColorRGBA.Blue);
geom1.setMaterial(mat1);

```

However, because the box is drawn using triangles there are diagonal wires visible:

How can I get rid of these diagonal wires (not draw them)?

# Answer
> 9 votes
As said in the comments. Wireframe rendering is used to show what polygons are being drawn, and is generally only used when debugging.

To solve you problem...

What you want is to only draw lines around the edge of the cube. And there are many ways you can acheive this...

1. Render a texture on to the cube, which has alpha everywhere but the edges.
2. Use a pixel shader to turn all pixels that are not at the edge of the cube to alpha. \<- This is recommended by me, as you will be able to set the line length around the cube.

# Answer
> 1 votes
I don't know how you are drawing, what libraries you are using...

In DirectX and OpenGL, you usually use vertex and index buffers to hold your geometry data. If the triangles in whatever format you are storing them in are still in the order of the quads they appear in, as is the case with at least some OBJ exporters, it can be relatively easy to figure out which vertices form a quad.

For example, in an obj file, a quad with the vertices 1,2,3 and 4 that was translated to triangles upon export might look like this (pseudo code):

f 1 2 3 f 3 4 1

which would look pretty much the same in your index buffer. A very simple solution would be to keep a second index buffer for your quads, where you could store the indices 1,2,2,3,3,4,4,1 or even 1,2,3,4,1. In directx there are the linelist and linestrip topology types which would render these indices as lines treated with your regular shading.

If you create your own file format for storing models in, it becomes easier as you could store quads where possible and tris when necessary in the file, and only translate them to triangles upon import.

I've done this, and since I usually create my 3D models with quads and only use tris where necessary I find a quad wireframe much more intelligible. It is relatively easy to implement provided you are lucky and your storage format accomodates you, but it does have a number of drawbacks. For one thing it does not produce thick and soft wireframes. It also does not produce a shaded wireframe, but a completely transparent one, so to have your wireframe ontop of your regularly shaded geometry you would have to first draw your object and then draw your wireframe, so there is a performance hit. Still, even drawing the objects twice, once shaded once as wire, this still performs better than just directx' wireframe RasterizerState setting alone. This method is also likely to create z-fighting, which might make it necessary to increase the scale momentarily to avoid that.

Here you can see how it looks in my test implementation, you can see both the z-fighting and the moire patterns created by the aliasing of the lines (there are ways to draw antialised lines though): https://i.stack.imgur.com/N6X3Y.png (sorry I can't embedd images here yet)

All in all nvidia's solution David posted looks very interesting, I've seen it in the samples and I've been meaning to take a closer look at that.

# Answer
> 0 votes
I found the following resource that might be helpful in implementing the technique described by Twitchy, although it's written for Direct3D. It's taken from the NVIDIA Direct3D SDK 10 Code Samples page. Quoting the page:

> Render the wireframe of a mesh using filled triangles, coloring only the fragments near the edges of the triangle. This technique produce high quality thick antialised lines on the mesh edges, without any z fighting issues. This technique is a DirectX10 implementation of the SIGGRAPH 2006 sketch "Single-Pass Wireframe Rendering". This technique can be easily added in an existing graphics engine as it only requires one pass and all algorithm is based on the position of the vertices.

And you can find a whitepaper describing the technique in detail here. The downside is that it requires a geometry shader.

---
Tags: java, jmonkeyengine
---


# Question
Title: Using tilemaps for an isometric football game with cocos2dx
I am writing a simple soccer game in cocos2d-x and recently found out that older iOS versions do not support cocos2d sprites larger than 1024x1024px.

I was thinking about using isometric tilemaps to create a larger football field.

Is this the way to go ? If so, how can i convert a convert my 2048x2048px football field image into several isometric tiles ?

# Answer
If you want to cut your image into tiles and then use individual images depending on what your screen is showing to the user then you should use Tile Cutter provided by "JEFF LAMARCHE" by following this link,

http://iphonedevelopment.blogspot.in/2010/10/tile-cutter-updated\_30.html

Also if you want to use one of your images that contains all the sprite used by the game then use Tiled Map Editor,

http://www.mapeditor.org/
> 0 votes

---
Tags: iphone, cocos2d-iphone, isometric, tilemap
---


# Question
Title: Game Server Framework / Engine that supports AMF?
I am looking for a server technology that supports AMF (because I plan on using an as3/flash front end).

I would like to develop game logic / simulations that run on the server. Small number of users and logic at first, but that will grow.

I might use this for some simple turn based / simple tests, but I am hoping this will also support some tougher real time (RTS) or even MMO style games and simulations.

So far I have been looking at (in order of what I think is most promising so far):

WebORB - Looks the most promising so far, appears to be well supported and developed, lots of features, yet sells itself as easy. Looks like they have a community open source/free version

Cubeia Firebase - Looks really good, only thing that worries me is their statement that it does not work well for real time style games, but is ideal for turn-based. It might be ok for now, but what if I need to scale the game up? Open Source/Free

BlazeDS - Looks promising, supported by adobe, I should be able to develop game logic in the BlazeDS server and has amf support. Open Source/Free

Red5 - No release since 2010, some activity though. (has amf) Open Source/Free - however have not been able to locate any good 'game' examples / tutorials.

FlashMOG - looks interesting, but I am not sure if it is robust enough to act as an actual game server with continuously running logic. No release since 2010, Uses PHP as a socket server. Open Source/Free

RedDwarf (used to be SGS/Project Darkstar) -- no release since 2010, is this active? Has AS3 library, but it is out of date too? Open Source/Free

Cirrus, Wowza, FMS - these are more of a media server?

SmartFox, Electroserver - these are nice, but are not open source/free. I believe they have limited connection versions available and while I am hoping to scale my project above those limitations I do not expect to be drawing an income to pay for the licenses at that point

LCDS (live cycle data services) - similar to blazeDS, not free

Any other options or clarifications??

# Answer
For business applications I used Spring with BlazeDS in combination. This is a very nice combination. You have all support for NoSQL, JDBC, JMX, full transaction control, authentication, integration frameworks like Apache Camel and much much more. I don't know all technologies you listed above. But here are my (fast) thoughts. You need to think about data synchronization, transactions and protocols.

With Red5 you are able to build your communication up on RTMP which is the bi-directional protocol which is very fast but this is more like a Web Server technology and not a framework. For RTMP you need opened ports but I think there are solutions to bring RTMP through HTTP.

With LCDS from Adobe which is in my opinion a wonderful technology is much too expensive (arround 30k per CPU). This would save you a lot of time thinking about data synchronization, messaging, data conflicts, lazy loading etc. and it also provides the very fast RTMP protocol. Clustering is also possible. With money this would be your first option.

BlazeDS gives you only the base to build on your own framework. A wonderful start from is ClearData Toolkit from Yakov Fain or one of it's nice books like this. He will explain the basics about data sync and how you can write your own sync mechanism for optimistic locking. BlazeDS gives you the ability to send messages out to clients. Clustering can be done by JGroups between the single nodes. Problem here is only the sharing of FlexSessions between the nodes (session replications). As protocol you only can use AMF over HTTP.

Don't use Cirrus aka FMS aka LCCS. This maybe will be stopped by Adobe and would be much too expensive too.
> 1 votes

---
Tags: flash, actionscript-3, flex
---