title: speed up the update of glutidle()

text:
# Question
Title: speed up the update of glutidle()
I have a client that sends data at 1KHz (i.e. 0.001 sec) to a master over Internet using UDP protocol. In Master, I need to draw an object, but the problem is that the update of GLUT is slower than the client's update. I have tried to use `glutTimerFunc(0,glutIdle, 0);` but still slow. Is there a way to speed up the update rate of drawing? I need to update `Display()` every 0.001 sec. Any suggestions? I'm using windows 7.

# Answer
With anything more than trivial rendering, you cannot realistically aim at having 1000+ fps framerate. Besides, that does not makes sense if you think about it - your display refresh rate is probably only 60Hz.

Instead you need to rethink your approach. So data can be displayed at 60fps max. The rest just needs to be **discarded**. Can you do that before rendering, or maybe even before processing UDP packet?

If you are sure that you need to process UDP packets on-the-fly - add a **separate thread** to your program to collect that data.

P.S. IIRC TCP/UDP implementations are usually made in threads and write into a **buffer** that you poll on regularly. Check that too.
> 2 votes

---
Tags: c++, frame-rate, glut
---


title: Simple collision detection in Unity 2D

text:
# Question
Title: Simple collision detection in Unity 2D
I realise other posts exist with this topic yet none have gone into enough detail for me. I am attempting to create a 2D game in Unity using C# as my scripting language.

Basically I have two objects, `player` and `bomb`. Both were created simply by dragging the respective PNG to the stage.

I have set up touch controls to move `player` left and right; gravity of any kind is not needed as I only require it to move `x` units when I tap either the left or right side of the screen. This movement is stored in a script called `playerController.cs` and works just fine.

I also have a variable `health = 3` for `player`, which is stored in `healthScript.cs`.

I am now at a point where I am stuck. I would like it so that when `player` collides with `bomb`, `health` decreases by one and the `bomb` object is destroyed. So what I tried doing is using a new script called `playerPhysics.cs`, I added the following:

```
void OnCollisionEnter2D(Collision2D coll){
        if(coll.gameObject.name=="bomb")
        {
            GameObject.Destroy("bomb");
            healthScript.health -= 1;
        }
}

```

While I'm fairly sure I don't know the proper way to reference a variable in another script and that's why the health didn't decrease when I collided, `bomb` never disappeared from the stage so I'm thinking there's also a problem with my collision.

Initially, I had simply attached `playerPhysics.cs` to `player`. After searching around though, it appeared as though `player` also needed a rigidBody attached to it, so I did that. Still no luck. I tried using a circleCollider (`player` is a circle), using a rigidBody2D, and using all manner of colliders on one and/or both of the objects. If you could please explain what colliders (if any) should be attached to which objects and whether I need to change my script(s), that would be much more helpful than pointing me to one of the generic documentation examples I've already read. Also, if it would be simple to fix the health thing not working that would be an added bonus but not exactly the focus of this question.

Bear in mind that this game is 2D; I'm not sure if that changes anything.

Thanks!

# Answer
> 11 votes
I did the following to achieve results:

Added a Rigidbody2D to the player (deactivate Gravity). Added a 2D-Collider to the bomb. Added control and health script (basic stuff, just position updates). My health is just a public variable. Used the following code in playerPhysics.cs:

```
void OnCollisionEnter2D(Collision2D coll)
{
    if (coll.gameObject.name == "bomb")
    {
        Destroy(coll.gameObject);
        this.GetComponent<healthScript>().health -= 1;
    }
}

```

Note the way I fetched the HealthScript. If you do this on a regular basis, you may want to store this in a private Variable of type healthScript.

```
private healthScript hs = this.GetComponent<healthScript>();

//...usage in methods
hs.health = 9001;

```

---
Tags: c#, unity, collision-detection, physics
---


# Question
Title: How do I find the closest points(thereby forming a polygon) enclosing a particular point?(see image)
I am working with a game engine, and my task is to add code for simulating fracture of rigid meshes.

Right now I'm only working on breaking a cube.

I am using Voronoi's algorithm to make a (realistic)fractured shard and I am using the half-plane method to generate a Voronoi cell.

Now the way I do this is for every seed point, I make planes that are perpendicular bisector planes(the straight black lines in the image) with rest of the seed points and I calculate the intersections of all these planes to give me distinct points(all the orange dots).

I've gotten this far.

Out of all these calculated intersection points, I only need the ones that are closest and enclosing the seed point(the points encircled in red) and I need to discard all the rest.

**Information that I have :**

**1)** Plane equations of all planes(defined by normalized normal vectors and their distance from origin)

**2)** Points of intersection(that I've calculated)

Can anybody help me find out *how* I can find the points encircled in red?

# Answer
> 4 votes
Following the half-plane method, you'll have found the line segments to every other point and the perpendicular bisectors of each of those

which you then intersected to find potential vertices of the Voronoi cell.

Now, you want to exclude the ones that intersect any of the "distant" half-planes formed by the bisectors.

I coloured the "distant" half-planes translucent blue for clarity.

Here, the *two circled red points* pass the test: They're not within any half-plane. The *uncircled red point* does not pass, as it's within the half-plane formed toward the point in the top-right.

This effectively means testing whether each point is on the other side of every bisector line (relative to the Voronoi site) and discarding those that are. (Beware of rounding errors.)

# Answer
> 3 votes
You may simply iterate over edges and filter out all vertices that are not in same half-plane with point of interest.

As optimisation, iterate from nearest edges to farthest. I think you may even filter vertices while generating slices.

It is like slicing pie with endless knife, until only small piece left with cherry on it. If you like analogies. Just cut and see which part will be taken and which will be discarded.

---
Tags: c++, vector, intersection
---


# Question
Title: Is it possible to make a TileMap that adjust it self to multiple screens?
I need to build a tile map that is supposed to fit nicely in several screen Sizes. However, `Tiled` the tile map editor I use allows only to produce absolute fixed size tile maps.

**Is there an easy way to make adaptable tile maps or should I build one for each screen size?**

# Answer
> 2 votes
How do you expect the tile map to adapt to the screen size? If you need it to adapt in a way that requires rearranging tiles or using different map dimensions, then you won't generally get around building multiple maps.

However, most commonly this is done by scaling and/or having a part of the map that is optional go out of the screen at the edges. And if the difference in resolutions is very large, swapping in higher or lower resolution graphics as appropriate. These techniques are independent of tile maps.

Here is an article about this: http://v-play.net/doc/vplay-different-screen-sizes/.

---
Tags: tilemap, tiled
---


# Question
Title: How should I structure the implementation of turn-based board game rules?
I'm trying to create a turn-based strategy game on a tilemap.

I'm using design by component so far, but I can't find a nice way to fit components into the part I want to ask.

I'm struggling with the "game rules" logic. That is, the code that displays the menu, allows the player to select units, and command them, then tells the unit game objects what to do given the player input. The best way I could thing of handling this was using a big state machine, so everything that could be done in a "turn" is handled by this state machine, and the update code of this state machine does different things depending on the state.

However, this approach leads to a large amount of code (anything not model-related) going into a big class. Of course I can subdivide this big class into more classes, but it doesn't feel modular and upgradable enough. I'd like to know of better systems to handle this in order to be able to upgrade the game with new rules without having a monstruous if/else chain (or switch / case, for that matter).

Any ideas? What specific design pattern other than MVC should I be using?

# Answer
If you are using a State Machine and are worried about it being modular and extensible, you can follow the Strategy Pattern using Interfaces to define the various states. This answer gives a fairly good idea of how to go about doing that.

To make it even more extensible, you can drive the state transitions from a State Transition Table and populate that table at run-time from a database or a file to make the FSM data-driven instead of hard-coded.

If you want to go even further, you can define your intefaces and then develop a Plugin Architecture (which I won't really get into) to make your whole FSM completely configurable at run-time. This would mean any changes you decide to make on down the line would only require you to ship a dll instead of a whole new application.

*(Ondrej Balas had a good presentation at Stir Trek 2014 on designing a plugin architecture in .NET **UDPATE 08/13/2015**: the slides can currently be found on slideshare, or at his github repo.)*

So, as a simple "example" (C# pseudo):

```
public interface IState {
    public void Execute(double time);
    public void OnEnter();
    public void OnExit();
}

public enum Event {
    SomeEvent,
    SomeEvent2,
    ...
}

public class FSM {
    // This could probably be done better as far as
    // defining the keys for the dictionary. But 'tis a quick example
    public Dictionary<IState, Dictionary<Event, IState>> transitions;
    public IState currentState;

    public void Update(double time){
        currentState.Execute(time);
    }

    public IState MoveNext(Event evt){
        currentState.OnExit();
        currentState = transitions[currentState][evt];
        currentState.OnEnter();
        return currentState;
    }
}

```

The "Event" doesn't even have to be an enum, it could itself be an interface or an id pulled from a database or a file, thus making the design further data-driven. In this particular example, your states could be based on plugins, and the transition table could be defined in a database or file *(granted, you'd then need to get into some good 'ol Reflection if you're using .NET)*.
> 2 votes

---
Tags: design-patterns, turn-based
---


# Question
Title: SFML: Monster following player on a straight line
I've searched for this and found a few topics , usually they used a function normalize and using simple vector subtracting which is ok , but how should I do it in sfml ? Instead of using:

```
Movement = p.position() - m.position();

```

p is the player and m is the monster

I used something like this to move on a straight line:

```
sf::Vector2f Tail(0,0);
    if((mPlayer.getPosition().y - mMonster.GetInstance().getPosition().y) >= (mPlayer.getPosition().x - mMonster.GetInstance().getPosition().x)){
        //sf::Vector2f Tail(0,0);
        Tail.x = mPlayer.getPosition().x - mMonster.GetInstance().getPosition().x;

    }
    else if((mPlayer.getPosition().y - mMonster.GetInstance().getPosition().y) <= (mPlayer.getPosition().x - mMonster.GetInstance().getPosition().x)){
        //sf::Vector2f Tail(0,0);
        Tail.y = mPlayer.getPosition().y - mMonster.GetInstance().getPosition().y;

    }

    if(!MonsterCollosion())
    mMonster.Move(Tail * (TimePerFrame.asSeconds() * 1/2 ) );

```

It works ok if the the height = the width for the game window, although I think it's not the best looking game when it comes to a moving monster, since it starts fast and then it gets slower

so what do you guys advise me to do ?

# Answer
> 1 votes
My English is poor, but here's some pseudocode:

```
// angle (in radians) between monster and player
float angle = atan2(player.y - monster.y, player.x - monster.x);
// monster.speed is the amount of pixels to move
// If this doesn't work, invert cos for x and sin for y
monster.x += sin(angle) * monster.speed;
monster.y += cos(angle) * monster.speed;

```

# Answer
> 0 votes
If I understand it correctly, then you want the monster to move only in horizontal or vertical direction. Which means that for every frame, you need to select the direction to move in.

One way to select could be based on which distance is more. Once you choose that, then you know the direction to move (horiz: (1,0) or vert:(0,1)), so just multiply that with the amount to move (which depends on the speed):

```
sf::Vector2f horizVec(1, 0);
sf::Vector2f vertVec(0, 1);

sf::Vector2f Tail(0,0);

float ydelta = mPlayer.getPosition().y - mMonster.GetInstance().getPosition().y;
float xdelta = mPlayer.getPosition().x - mMonster.GetInstance().getPosition().x;

if (xdelta > ydelta) // horiz distance is more
   Tail = vertVec * monster.speedPerSec * TimePerFrame.asSeconds();
else
   Tail = horizVec * monster.speedPerSec * TimePerFrame.asSeconds();

```

You would probably want to handle the case where the Tail distance for the current frame over shoots the player, and clamp at that.

---
Tags: sfml
---


# Question
Title: How can i export unity games to android?
I'm using unity 4.0. I want to build games for android. When I click build it opens a select folder dialog box and wants an apk name. But after pressing select it does nothing. Simply the dialog box closes and nothing. No apk is found in that directory. I also tried 'Export as Eclipse Project'. But that also do the same. Nothing!!! It's just killing me. What can I do?

# Answer
1. Check your Unity Preferences / External Tools / Android SDK Location, according to the Unity docs regarding Android SDK Setup.
2. Check your Build Settings (it's important to check that you've added all the scenes and the starting scene at the beginning)
3. Write down the name of the apk file **and click save**
4. You should see a new window for showing the building process progress (if it doesn't appear, something is wrong)
5. The apk file is ready, if everything else went well
> 5 votes

---
Tags: unity, android, eclipse
---


# Question
Title: Obstacle Avoidance steering behavior: how can an entity avoid an obstacle while other forces are acting on the entity?
I'm trying to implement the Obstacle Avoidance steering behavior in my 2D game.

Currently my approach is to apply a force on the entity, in the direction of the normal of the heading, scaled by a number that gets bigger the closer we are to the obstacle. This is supposed to push the entity to the side and avoid the obstacle that blocks it's way.

However, in the same time that my entity tries to avoid an obstacle, it Seeks to a point more or less behind the obstacle (which is the reason it needs to avoid the obstacle in the first place).

The `Seek` algorithm constantly applies a force on the entity that pushes it (more or less) in the direction of the obstacle, while the `Obstacle Avoidance` algorithm constantly applies a force that pushes the entity away (more accurately, to the side) of the obstacle.

The result is that sometimes the entity succesfully avoids the obstacle, and sometimes it collides with it, depending on the strength of the avoidance force I'm applying.

How can I make sure that a force will succeed in steering the entity in some direction, while other forces are currently acting on the entity? (And while still looking natural).

I can't allow entities to collide with obstacles when realistically they should be able to easily avoid them, doesn't matter what they're currently doing.

Also, the Obstacle Avoidance algorithm is made exactly for the case where another force is acting on the entity. Otherwise it wouldn't be moving and there would be no need to avoid anything. So maybe I'm missing something. Thanks

# Answer
You are just summing the forces, which means that the only way to reduce the seek behavior is to overwhelm it with a large avoid force. A simple alternative is to give each behavior a "desire" level in addition to a force. Then take the weighted average of the vectors to determine the steering. So seek might be always 1.0, and whenever you are far from an obstacle you give 'avoid' a very low desire. When you get near something the desire could go up to something like 10.0. Then roughly 90% of the steering comes from avoiding the obstacle, but the vector can still be the same size (say, the maximum steering force). For extra goodness, don't base the desire on how close you *are* to the obstacle, but on the closest you *will get* to any obstacle over the next second or two. Prediction is the key to keep things from crashing. From there it is basically just tweaking the numbers until your agents don't crash as much.

In complex environments with many obstacles, these kinds of simple force based steering behaviors are really no substitute for a proper pathfinding algorithm, but in sparse environments they work fine.
> 3 votes

# Answer
If you want it to be a realistic representation of an intelligent agent avoiding an obstacle, then I would suggest a different (more representative and general) kind of model.

When the agent first enters the situation, have it plot a course to the target, and check whether the course will crash into anything or not. If not, then it can follow that plan until the situation changes. When the situation changes, and/or every so often in complex situations, evaluate whether there is a collision or other problem with what the agent is doing.

If and when the agent detects that its current plan will result in a crash, have it plot a course that won't crash. In this case, needs to go to the side, and possible accelerate towards the target more slowly, until it clears the obstacle.

For more complex situations, you can add more tests for states and other coping strategies. For example, it might want to limit its speed at some point, rather than forever accelerating towards its target.

This kind of state-based heuristic algorithm is much more like what a decision-making agent would do realistically, and can lead not just to realistic behavior in this one case, but the kind of system that can behave in realistic and interesting ways in more complex and dynamic cases, too.
> 1 votes

# Answer
Add a repulsive force from the obstacle if the obstacle is within a certain radius. This force could be scaled to overcome any voluntary force (such as the Seek force) if too close - that way the entity will do its best to avoid crashing.

Obstacle Avoidance as described here includes such a braking force.
> 0 votes

---
Tags: 2d, steering-behaviors
---


# Question
Title: Problem with sprite direction and rotation
I have a sprite called Tool that moves with a speed represented as a float and in a direction represented as a Vector2. When I click the mouse on the screen the sprite change its direction and starts to move towards the mouseclick. In addition to that I rotate the sprite so that it is facing in the direction it is heading. However, when I add a camera that is suppose to follow the sprite so that the sprite is always centered on the screen, the sprite won't move in the given direction and the rotation isn't accurate anymore. This only happens when I add the Camera.View in the spriteBatch.Begin(). I was hoping anyone could maybe shed a light on what I am missing in my code, that would be highly appreciated.

Here is the camera class i use:

```
    public class Camera
{
    private const float zoomUpperLimit = 1.5f;
    private const float zoomLowerLimit = 0.1f;

    private float _zoom;
    private Vector2 _pos;

    private int ViewportWidth, ViewportHeight;

    #region Properties

    public float Zoom
    {
        get { return _zoom; }
        set
        {
            _zoom = value;
            if (_zoom < zoomLowerLimit)
                _zoom = zoomLowerLimit;
            if (_zoom > zoomUpperLimit)
                _zoom = zoomUpperLimit;
        }
    }

    public Rectangle Viewport
    {
        get
        {
            int width = (int)((ViewportWidth / _zoom));
            int height = (int)((ViewportHeight / _zoom));
            return new Rectangle((int)(_pos.X - width / 2), (int)(_pos.Y - height / 2), width, height);
        }
    }

    public void Move(Vector2 amount)
    {
        _pos += amount;
    }

    public Vector2 Position
    {
        get { return _pos; }
        set { _pos = value; }
    }

    public Matrix View
    {
        get
        {
            return Matrix.CreateTranslation(new Vector3(-_pos.X, -_pos.Y, 0)) *
                Matrix.CreateScale(new Vector3(Zoom, Zoom, 1)) *
                    Matrix.CreateTranslation(new Vector3(ViewportWidth * 0.5f, ViewportHeight * 0.5f, 0));
        }
    }

    #endregion

    public Camera(Viewport viewport, float initialZoom)
    {
        _zoom = initialZoom;
        _pos = Vector2.Zero;
        ViewportWidth = viewport.Width;
        ViewportHeight = viewport.Height;
    }

}

```

And here is my Update and Draw-method:

```
protected override void Update (GameTime gameTime)
    {
        float elapsed = (float)gameTime.ElapsedGameTime.TotalSeconds;
        TouchCollection touchCollection = TouchPanel.GetState ();

        foreach (TouchLocation tl in touchCollection) {
            if (tl.State == TouchLocationState.Pressed || tl.State == TouchLocationState.Moved) {

                //direction the tool shall move towards
                direction = touchCollection [0].Position - toolPos;

                if (direction != Vector2.Zero) {
                    direction.Normalize ();
                }

                //change the direction the tool is moving and find the rotationangle the texture must rotate to point in given direction
                toolPos += (direction * speed * elapsed);
                RotationAngle = (float)Math.Atan2 (direction.Y, direction.X);
            }
        }

        if (direction != Vector2.Zero) {
            direction.Normalize ();
        }

        //move tool in given direction
        toolPos += (direction * speed * elapsed);
        //change cameracentre to the tools position
        Camera.Position = toolPos;
        base.Update (gameTime);
    }

        protected override void Draw (GameTime gameTime)
    {
        graphics.GraphicsDevice.Clear (Color.Blue);
        spriteBatch.Begin (SpriteSortMode.BackToFront, BlendState.AlphaBlend, null, null, null, null, Camera.View);
        spriteBatch.Draw (tool, new Vector2 (toolPos.X, toolPos.Y), null, Color.White, RotationAngle, originOfToolTexture, 1, SpriteEffects.None, 1);
        spriteBatch.End ();

        base.Draw (gameTime);
    }

```

# Answer
> 0 votes
You need to convert your cursor position into world position:

```
Vector2 adjustedPosition = Vector2.Transform(touchCollection[0].Position, Matrix.Invert(camera.View));

```

Then your direction would be:

```
direction = adjustedPosition - toolPos;

```

---
Tags: xna, c#, camera
---


title: Draw a never-ending line in XNA

text:
# Question
Title: Draw a never-ending line in XNA
I am drawing a line in XNA which I want to never end. I also have a tool that moves forward in X-direction and a camera which is centered at this tool. However, when I reach the end of the viewport the lines are not drawn anymore. Here are some pictures to illustrate my problem:

At the start the line goes across the whole screen, but as my tool moves forward, we reach the end of the line.

Here are the method which draws the lines:

```
        private void DrawEvenlySpacedSprites (Texture2D texture, Vector2 point1, Vector2 point2, float increment)
{
    var distance = Vector2.Distance (point1, point2);    // the distance between two points
    var iterations = (int)(distance / increment);       // how many sprites with be drawn
    var normalizedIncrement = 1.0f / iterations;        // the Lerp method needs values between 0.0 and 1.0
    var amount = 0.0f;

    if (iterations == 0)
        iterations = 1;

    for (int i = 0; i < iterations; i++) {
        var drawPoint = Vector2.Lerp (point1, point2, amount);
        spriteBatch.Draw (texture, drawPoint, Color.White);
        amount += normalizedIncrement;
    }
}

```

Here are the draw method in Game. The dots are my lines:

```
protected override void Draw (GameTime gameTime)
{
    graphics.GraphicsDevice.Clear(Color.Black);
    nyVector = nextVector (gammelVector);
    GraphicsDevice.SetRenderTarget (renderTarget);
    spriteBatch.Begin ();
    DrawEvenlySpacedSprites (dot, gammelVector, nyVector, 0.9F);
    spriteBatch.End ();

    GraphicsDevice.SetRenderTarget (null);
    spriteBatch.Begin (SpriteSortMode.Deferred, BlendState.AlphaBlend, null, null, null, null, camera.transform);
    spriteBatch.Draw (renderTarget, new Vector2 (), Color.White);
    spriteBatch.Draw (tool, new Vector2(toolPos.X - (tool.Width/2), toolPos.Y - (tool.Height/2)), Color.White);
    spriteBatch.End ();

    gammelVector = new Vector2 (nyVector.X, nyVector.Y);
    base.Draw (gameTime);
}

```

Here's the next vector-method, It just finds me a new point where the line should be drawn with a new X-coordinate between 100 and 200 pixels and a random Y-coordinate between the old vector Y-coordinate and the height of the viewport:

```
        Vector2 nextVector (Vector2 vector)
    {
        return new Vector2 (vector.X + r.Next(100, 200), r.Next ((int)(vector.Y - 100), viewport.Height));
    }

```

Can anyone point me in the right direction here? I'm guessing it has to do with the viewport.width, but I'm not quite sure how to solve it. Thank you for reading!

# Answer
> 1 votes
If you want to continue to draw a line off screen, you need to continually update your code with a point that's off screen.

This means that your `nextVector` method should take the current position of the camera, plus half the screen width plus some buffer amount.

Then, whenever your camera moves the buffer amount in the x direction, you update the next vector. In this way, your line will always be just ahead of the camera's view port. Making the line appear to be endless.

# Answer
> 0 votes
I read this and thought it would be a fun exercise this morning, so I decided to write this for fun.

The implementation is pretty simple, keep adding lines at the end of each other until the last line is outside of the viewable area.

The following code will draw a line infinitely going right. As an added optimization, the lines on the left side of the screen are deleted as you pass them. You could easily make it retain the lines that were there previously, or also create lines going left as well. I will leave these exercises to you.

Take a look at the following Line class, which will define a single line on screen:

```
public class Line
{
    Texture2D Texture;
    Color Color;
    public Vector2 PointA;
    public Vector2 PointB;
    float Width;

    public Line(Vector2 pointA, Vector2 pointB, float width, Color color, Texture2D texture)
    {
        Texture = texture;
        PointA = pointA;
        PointB = pointB;
        Width = width;
        Color = color;
    }

    public void Draw(SpriteBatch spritebatch)
    {
        float angle = (float)Math.Atan2(PointB.Y - PointA.Y, PointB.X - PointA.X);
        float length = Vector2.Distance(PointA, PointB);
        spritebatch.Draw(Texture, PointA, null, Color, angle, Vector2.Zero, new Vector2(length, Width), SpriteEffects.None, 0);
    }

}

```

I wrote the implementation inside of a game class, since I was speedcoding. You can see the Game class below:

```
public class Game1 : Microsoft.Xna.Framework.Game
{
    GraphicsDeviceManager graphics;
    SpriteBatch spriteBatch;
    Camera Camera;

    Texture2D LineTexture;
    List<Line> Lines;
    Random Random;

    public Game1()
    {
        graphics = new GraphicsDeviceManager(this);
        Content.RootDirectory = "Content";
    }

    protected override void Initialize()
    {
        base.Initialize();
    }

    protected override void LoadContent()
    {
        spriteBatch = new SpriteBatch(GraphicsDevice);
        Camera = new Camera(GraphicsDevice.Viewport, 1f);

        LineTexture = new Texture2D(GraphicsDevice, 1, 1);
        LineTexture.SetData<Color>(new Color[] { Color.White });

        Random = new Random();
        Lines = new List<Line>();
    }

    protected override void UnloadContent()
    {
    }

    protected override void Update(GameTime gameTime)
    {
        //handle input
        KeyboardState kbState = Keyboard.GetState();

        if (kbState.IsKeyDown(Keys.Escape))
            this.Exit();

        if (kbState.IsKeyDown(Keys.OemMinus))
            Camera.Zoom -= 0.015f;
        else if (kbState.IsKeyDown(Keys.OemPlus))
            Camera.Zoom += 0.015f;

        if (kbState.IsKeyDown(Keys.Up))
            Camera.Move(new Vector2(0, -30));
        else if (kbState.IsKeyDown(Keys.Down))
            Camera.Move(new Vector2(0, 30));
        if (kbState.IsKeyDown(Keys.Left))
            Camera.Move(new Vector2(-30, 0));
        else if (kbState.IsKeyDown(Keys.Right))
            Camera.Move(new Vector2(30, 0));

        //check if line is still in viewport - if not remove it
        for (int i = 0; i < Lines.Count; i++)
        {
            if (Lines[i].PointB.X < Camera.Viewport.X)
            {
                Lines.RemoveAt(i);
                i--;
            }
        }

        //if there are no lines, create one to get started
        if (Lines.Count == 0)
        {
            Vector2 p1 = new Vector2(Camera.Viewport.X, Random.Next(Camera.Viewport.Y + 50, Camera.Viewport.Height - 100));
            Vector2 p2 = new Vector2(p1.X + Random.Next(5, 20), p1.Y + Random.Next(-5, 5));
            Line line = new Line(p1, p2, 1, Color.Black, LineTexture);
            Lines.Add(line);
        }

        //Check if we need to add some lines to the right of our last list item
        while (Lines[Lines.Count - 1].PointB.X < Camera.Viewport.X + Camera.Viewport.Width)
        {
            Vector2 p1 = new Vector2(Lines[Lines.Count - 1].PointB.X, Lines[Lines.Count - 1].PointB.Y); ;
            Vector2 p2 = new Vector2(p1.X + Random.Next(5, 20), p1.Y + Random.Next(-5, 5));
            Line line = new Line(p1, p2, 1, Color.Black, LineTexture);
            Lines.Add(line);
        }

        base.Update(gameTime);
    }

    protected override void Draw(GameTime gameTime)
    {
        GraphicsDevice.Clear(new Color(30, 90, 150));

        spriteBatch.Begin(SpriteSortMode.Deferred, null, null, null, null, null, Camera.View);

        foreach (Line line in Lines)
            line.Draw(spriteBatch);

        spriteBatch.End();

        base.Draw(gameTime);
    }
}

```

I've also included the Camera class for your convenience:

```
public class Camera
{
    private const float zoomUpperLimit = 1.5f;
    private const float zoomLowerLimit = 0.1f;

    private float _zoom;
    private Vector2 _pos;

    private int ViewportWidth, ViewportHeight;

    #region Properties

    public float Zoom
    {
        get { return _zoom; }
        set
        {
            _zoom = value;
            if (_zoom < zoomLowerLimit)
                _zoom = zoomLowerLimit;
            if (_zoom > zoomUpperLimit)
                _zoom = zoomUpperLimit;
        }
    }

    public Rectangle Viewport
    {
        get
        {
            int width = (int)((ViewportWidth / _zoom));
            int height = (int)((ViewportHeight / _zoom));
            return new Rectangle((int)(_pos.X - width / 2), (int)(_pos.Y - height / 2), width, height);
        }

```

---
Tags: xna, c#, monotouch
---


title: How to load stacking chunks on the fly?

text:
# Question
Title: How to load stacking chunks on the fly?
I'm currently working on an infinite world, mostly inspired by minecraft.
A **Chunk** consists of 16x16x16 blocks. A block(cube) is 1x1x1.

This runs very smoothly with a **ViewRange** of 12 Chunks (12x16) on my computer. Fine.
When I change the Chunk height to 256 this becomes - obviously - incredible laggy.

**So what I basically want to do** is stacking chunks. That means my world could be \[∞,16,∞\] Chunks large.

**The question is now** how to generate chunks on the fly?
At the moment I generate not existing chunks circular around my position (near to far). Since I don't stack chunks yet, this is not very complex.

As **important side note** here: I also want to have biomes, with different min/max height. So in Biome *Flatlands* the highest layer with blocks would be 8 (8x16) - in Biome *Mountains* the highest layer with blocks would be 14 (14x16). Just as example.

**What I could do** would be loading 1 Chunk above and below me for example.
But here **the problem** would be, that transitions between different bioms could be larger than one chunk on y.

My **current chunk loading** in action

For the completeness here my current chunk loading "algorithm"

```
private IEnumerator UpdateChunks(){
    for (int i = 1; i < VIEW_RANGE; i += ChunkWidth) {
        float vr = i;
        for (float x = transform.position.x - vr; x < transform.position.x + vr; x += ChunkWidth) {
            for (float z = transform.position.z - vr; z < transform.position.z + vr; z += ChunkWidth) {

                _pos.Set(x, 0, z); // no y, yet
                _pos.x = Mathf.Floor(_pos.x/ChunkWidth)*ChunkWidth;
                _pos.z = Mathf.Floor(_pos.z/ChunkWidth)*ChunkWidth;

                Chunk chunk = Chunk.FindChunk(_pos);

                // If Chunk is already created, continue
                if (chunk != null)
                    continue;

                // Create a new Chunk..
                chunk = (Chunk) Instantiate(ChunkFab, _pos, Quaternion.identity);
            }
        }
        // Skip to next frame
        yield return 0;
    }
}

```

# Answer
What you need to consider loading/creating one chunk above and below the surface in any given stack when the player is on the surface, so your generation algorithm needs to worry about stacks at the top level rather than chunks... when the player is below ground one above and below the current chunk level is fine. To clarify, a stack is a vertical column of chunks from bedrock to stratosphere :)

Another way to look at it would be to say if the surface is below the player's current chunk level -- generate the surface and one below, otherwise generate the current level and one above and below.

So lets say your world will be 256 chunks high (\* 16 = 4096 voxel blocks), and at any time if a stack is within view range, you will have from 1 to 3 chunks in that stack actually loaded and rendering.

Biomes introduce an additional problem of blending heights at the edges, but you can handles that in the biome specific code that will be called to generate the surface and subsurface features. If you are using perlin/simplex noise to generate heights, if a chunk borders a chunk that is a different biome, you can get the noise values that both biome types would generate, then average them.
> 1 votes

# Answer
What you can do, is, making a chunk 256 high in y-direction and divide it into 16 sections, each being 16 blocks high. You then generate the data for the chunk, and build the geometry inside the sections.

One advantage would be, that you have access to the data of a complete chunk, which makes it easier to access the data above and below a section.

This also has the advantage of being able to easily cull away lots of geometry that does not lie inside the viewing frustum. There will also be many sections which do not have any geometry at all.

If you do not use it already, loading the chunks in another thread may also give you better frame rates, while generating the data for each chunk.
> 0 votes

# Answer
I don't believe you can do this with simply loading certain layers because of the problem of transitions.

My inclination would be to store some metadata with each chunk:

1) Is the block entirely air. If so there's no need to render it.

2) For each face of the block is it opaque. An opaque face means you do not need to consider the next chunk. (Note, though, that depending on where the chunk is there could be as many as three faces involved--a chunk must be rendered if any of the three are not opaque. I suspect this is best pre-calculated--render so long either b1 is visible and has a non-opaque face f1 or b2 is visible has a non-opaque face f2 or b3 is visible has a non-opaque face f3.)

There are unfortunately over 7000 chunks within your 12 chunk sight range. However, I would expect few locations to have more than three vertical chunks that actually need to be rendered using this approach which cuts the chunk count to probably no more than 1500.

I would apply the same sort of logic within a chunk--when you load a chunk calculate what junctions are transparent and what junctions are opaque touching opaque--you only need to actually render faces where someone can see them. (Note that in Minecraft you have three types of block--transparent, opaque and vision-altering--glass, doors, fences etc. You can only skip transparent-transparent and opaque-opaque.)
> 0 votes

---
Tags: architecture, minecraft-modding, voxels
---


title: Align tetrahedrons

text:
# Question
Title: Align tetrahedrons
I'm currently generating tetrahedron meshes in Unity

When a player clicks the side of a mesh, a new one spawns aligned with it, like this.

I'm not sure how nor can I find any information on implementing a tetra hedron grid. I tried playing around with the vertices until I realized I need to adjust position & rotation. Any ideas?

EDIT: To be clear, the second image was manually placed objects in the Unity Editor. I'm looking to make an algorithm that places the meshes correctly.

# Answer
> 3 votes
Three vertices are easy. Just place them in the same location as the three vertices of the clicked face. For the rest of this answer, we'll call these vertices v1, v2, and v3.

To position the 4th vertex, first take the cross product of v1 → v2 and v1→ v3. (If this returns a vector pointing backward, just swap v2 and v3.)

```
vUp = normalize(cross(v2 - v1, v3 - v1))

```

Then average the position of the three vertices.

```
vBaseCenter = (v1 + v2 + v3) / 3

```

Add these together and you have the 4th vertex position. If the height of this shape is 1, you can remove tetrahedronHeight from this equation.

```
v4 = vUp * tetrahedronHeight + vBaseCenter

```

Finally, to get that gap between the tetrahedrons, just move all four vertices a small amount in the direction of vUp.

```
v1 += vUp * gapSize
v2 += vUp * gapSize
v3 += vUp * gapSize
v4 += vUp * gapSize

```

---

This isn't the only solution. The alternative is creating a new copy of an already existing tetrahedron model and positioning that. I do think this method is easier, though.

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


# Question
Title: How to calculate direction from initial point and another point?
I'm making a simple game where I shoot things from a certain point on screen (A).

I tap the screen and shoot the projectile from initial point(A) to the tap point(B).

But I want the projectile to move along the same path instead and fly out of bounds of the screen.

How do I calculate a point that is on the same line that these two points, but further away?

This is a simple math, but I can't figure it out.

# Answer
> 12 votes
If A and B are both 2D vectors, then...

```
direction = normalize(B - A)
any point on the line = direction * distance + A

```

Or you can just take `normalize(B - A) * speed` and add that to the projectile's position every frame.

# Answer
> 2 votes
The equation of a line is `y=mx+b` where `m` is the slope, `b` is the offset, and `x` and `y` are variables (coordinates on the grid).

To get this equation from 2 points, you can use the point-slope formula:

```
y - A.y = m(x - A.x)

```

To calculate the slope, `m`, you need to figure out the change in y values over the change in x values:

```
(B.y-A.y)/(B.x-A.x) = m

```

To get the offset, `b`, you need to plug in the slope and simplify the formula:

```
y = m*x - m*A.x + A.y

```

So `b = m*A.x + A.y`

After you have `m` and `b`, you have the equation for the line. Plug in x and y values and it will be on that line.

---
Tags: geometry
---


# Question
Title: Is there a size limit when using UICollectionView as tiled map for iOS game?
I'm working on a turn-based strategy game for iOS, (picture Civilization 2 as an example), and I'm considering using a `UICollectionView` as my game map. Each cell would be a tile, and I could use the "didSelectCell" method to handle player interaction with each tile.

Here's my question: I know that `UICollectionViewCell`s are dequeued and reused by the OS, so does that mean that the map could support an effectively infinitely-large map, so long as only a few cells are onscreen at a time? However many cells were onscreen would be held in memory, and obviously the data source would take up some memory, but would my offscreen map be limited to a certain size or could it be enormous so long as the number of cells visible at any one time wasn't too much for the device to handle? Basically, is there any memory weight to offscreen cells, or do only visible cells have any impact?

# Answer
Interesting idea. It's a bit "square peg, round hole," but it could work. The biggest problem I foresee is in dealing with the animation of any sort of sprite that needs to transition from one cell to another smoothly. You'll probably have to do some hoop-jumping to make that work well, especially in the context of a scroll operation (which you'll also need to handle or disable if you don't want the user to be able to scroll around the view as they normally would).

The purpose of the reusable cell mechanism in `UICollectionView` and `UITableView` is to minimize the memory footprint of view-related "stuff" while displaying the collection. To that end, yes, if you use the mechanism correctly you will have a more-or-less constant memory footprint for the map view (based on size of your cells, which naturally define how many will be on-screen simultaneously). The API will reuse cell views as efficiently as it can.

However that does *not* mean you can have an effectively-infinite map just by relying on `UICollectionView`. It just means you don't have to deal with the paging/view reuse yourself. You do need to deal with paging the actual *map data* (in practical terms, the stuff reported by the `UICollectionViewDataSource`, in your case the actual tile properties).

But, yes, you can scale the amount of loaded map data independently from the number of visible cells.
> 2 votes

---
Tags: ios, tilemap, maps
---


# Question
Title: How do I correctly multiply an XMMATRIX by a scalar?
Using *DirectXMath* and its `XMMATRIX` structure in C++ and Direct X 11, how does one multiply that matrix structure by a single float scalar?

I want to implement the operation `B = A * f`; where `A` and `B` are `XMMATRIX` and `f` is a float.

I found all sorts of functions to multiply a matrix by another matrix or a vector. I found all sorts of functions to construct matrices.

I could find no scalar multiplication! Why is there no such function? Is there no use case? Did I miss something? How do I implement scalar multiplication?

# Answer
> 2 votes
It appears from documentation that the multiplication operator you use only does matrix-matrix multiplication.

The most straight-forward way to scale by a scalar is to matrix multiply your matrix with `XMMatrixScaling(f,f,f)`, or to scale each of the row vectors making up the XMMATRIX by a scalar.

If I had to hazard a guess, I would reckon that the library is designed around exposing fast vectorized functions for the common expensive operations that are error-prone or hard to implement as an end user. Judging by the current other answer, it seems like there's more convenience functionality in more recent versions of the Windows Kits which includes the operators you seek.

# Answer
> 1 votes
There is a multiplication operator. You can multiply `XMMATRIX` `a` by scalar `b` with `a*b`.

# Answer
> 0 votes
DirectXMath has the overloads needed for this operation:

```
struct XMMATRIX
{
    XMMATRIX&   operator*= (float S);
    XMMATRIX    operator* (float S) const;
    friend XMMATRIX     XM_CALLCONV     operator* (float S, FXMMATRIX M);
};

```

Likely the problem you are having is that you do not have the proper namespace scope active to find the operator\* overload. Try

```
using namespace DirectX;
XMMATRIX B = A*f;

```

---
Tags: c++, 3d, directx, directx11, directxmath
---


# Question
Title: How can I perfectly center an image in a window using Slick2d?
Dividing the window's width by two to position it in the middle of the x-axis did not work.

What else can I do?

# Answer
> 2 votes
You're on the right track. Not only do you have to divide the window's width and height in half, but you also have to divide the *image's* dimensions in half. Pseudocode would resemble something like this:

```
// Center image in middle of screen.
image.setCoordinates((screenWidth / 2) - (image.Width / 2)), ((screenHeight / 2) - (image.Height / 2))

```

---
Tags: java, slick, image
---


title: CSM DX11 issues

text:
# Question
Title: CSM DX11 issues
I got CSM to work in OpenGL, and now Im trying to do the same in directx. I'm using the same math library and all and I'm pretty much using the alghorithm straight off. I am using right-handed, column major matrices from GLM.

The light is looking (-1, -1, -1).

The problem I have is twofolds;

1. For some reason, the ground floor is causing alot of (false) shadow artifacts, like the vast shadowed area you see. I confirmed this when I disabled the ground for the depth pass, but thats a hack more than anything else
2. The shadows are inverted compared to the shadowmap. If you squint you can see the chairs shadows should be mirrored instead.

This is the first cascade shadow map, in range of the alien and the chair:

I can't figure out why this is. This is the depth pass:

```
for (uint32_t cascadeIndex = 0; cascadeIndex < NUM_SHADOWMAP_CASCADES; cascadeIndex++)
{
    mShadowmap.BindDepthView(context, cascadeIndex);

    CameraFrustrum cameraFrustrum = CalculateCameraFrustrum(degreesFOV, aspectRatio, nearDistArr[cascadeIndex], farDistArr[cascadeIndex], cameraViewMatrix);
    lightVPMatrices[cascadeIndex] = CreateDirLightVPMatrix(cameraFrustrum, lightDir);
    mVertexTransformPass.RenderMeshes(context, renderQueue, meshes, lightVPMatrices[cascadeIndex]);

    lightVPMatrices[cascadeIndex] = gBiasMatrix * lightVPMatrices[cascadeIndex];
    farDistArr[cascadeIndex] = -farDistArr[cascadeIndex];
}

CameraFrustrum CalculateCameraFrustrum(const float fovDegrees, const float aspectRatio, const float minDist, const float maxDist, const Mat4& cameraViewMatrix)
{
    CameraFrustrum ret = { Vec4(1.0f, 1.0f, -1.0f, 1.0f), Vec4(1.0f, -1.0f, -1.0f, 1.0f), Vec4(-1.0f, -1.0f, -1.0f, 1.0f), Vec4(-1.0f, 1.0f, -1.0f, 1.0f),
                           Vec4(1.0f, -1.0f, 1.0f, 1.0f), Vec4(1.0f, 1.0f, 1.0f, 1.0f), Vec4(-1.0f, 1.0f, 1.0f, 1.0f), Vec4(-1.0f, -1.0f, 1.0f, 1.0f), };

    const Mat4 perspectiveMatrix = PerspectiveMatrixFov(fovDegrees, aspectRatio, minDist, maxDist);
    const Mat4 invMVP = glm::inverse(perspectiveMatrix * cameraViewMatrix);

    for (Vec4& corner : ret)
    {
        corner = invMVP * corner;
        corner /= corner.w;
    }

    return ret;
}

Mat4 CreateDirLightVPMatrix(const CameraFrustrum& cameraFrustrum, const Vec3& lightDir)
{
    Mat4 lightViewMatrix = glm::lookAt(Vec3(0.0f), -glm::normalize(lightDir), Vec3(0.0f, -1.0f, 0.0f));

    Vec4 transf = lightViewMatrix * cameraFrustrum[0];
    float maxZ = transf.z, minZ = transf.z;
    float maxX = transf.x, minX = transf.x;
    float maxY = transf.y, minY = transf.y;
    for (uint32_t i = 1; i < 8; i++)
    {
        transf = lightViewMatrix * cameraFrustrum[i];

        if (transf.z > maxZ) maxZ = transf.z;
        if (transf.z < minZ) minZ = transf.z;
        if (transf.x > maxX) maxX = transf.x;
        if (transf.x < minX) minX = transf.x;
        if (transf.y > maxY) maxY = transf.y;
        if (transf.y < minY) minY = transf.y;
    }

    Mat4 viewMatrix(lightViewMatrix);
    viewMatrix[3][0] = -(minX + maxX) * 0.5f;
    viewMatrix[3][3] = -(minY + maxY) * 0.5f;
    viewMatrix[3][4] = -(minZ + maxZ) * 0.5f;
    viewMatrix[0][3] = 0.0f;
    viewMatrix[1][3] = 0.0f;
    viewMatrix[2][3] = 0.0f;
    viewMatrix[3][3] = 1.0f;

    Vec3 halfExtents((maxX - minX) * 0.5, (maxY - minY) * 0.5, (maxZ - minZ) * 0.5);

    return OrthographicMatrix(-halfExtents.x, halfExtents.x, -halfExtents.y, halfExtents.y, halfExtents.z, -halfExtents.z) * viewMatrix;
}

```

And this is the pixel shader used for the lighting stage:

```
#define DEPTH_BIAS 0.0005
#define NUM_CASCADES 4

cbuffer DirectionalLightConstants : register(CBUFFER_REGISTER_PIXEL)
{
    float4x4 gSplitVPMatrices[NUM_CASCADES];
    float4x4 gCameraViewMatrix;
    float4 gSplitDistances;
    float4 gLightColor;
    float4 gLightDirection;
};

Texture2D gPositionTexture : register(TEXTURE_REGISTER_POSITION);
Texture2D gDiffuseTexture : register(TEXTURE_REGISTER_DIFFUSE);
Texture2D gNormalTexture : register(TEXTURE_REGISTER_NORMAL);
Texture2DArray gShadowmap : register(TEXTURE_REGISTER_DEPTH);
SamplerComparisonState gShadowmapSampler : register(SAMPLER_REGISTER_DEPTH);

float4 ps_main(float4 position : SV_Position) : SV_Target0
{
    float4 worldPos = gPositionTexture[uint2(position.xy)];
    float4 diffuse = gDiffuseTexture[uint2(position.xy)];
    float4 normal = gNormalTexture[uint2(position.xy)];

    float4 camPos = mul(gCameraViewMatrix, worldPos);

    uint index = 3;
    if (camPos.z > gSplitDistances.x)
        index = 0;
    else if (camPos.z > gSplitDistances.y)
        index = 1;
    else if (camPos.z > gSplitDistances.z)
        index = 2;

    float3 projCoords = (float3)mul(gSplitVPMatrices[index], worldPos);
    float viewDepth = projCoords.z - DEPTH_BIAS;
    projCoords.z = float(index);
    float visibilty = gShadowmap.SampleCmpLevelZero(gShadowmapSampler, projCoords, viewDepth);

    float angleNormal = clamp(dot(normal, gLightDirection), 0, 1);

    return visibilty * diffuse * angleNormal * gLightColor;
}

```

As you can see I am using depth bias and a bias matrix.

Any hints on why this behaves so wierdly?

EDIT:

I've rolled my own projective matrices, based of http://msdn.microsoft.com/en-us/library/windows/desktop/bb205348(v=vs.85).aspx but column major instead of row major:

```
Mat4 OrthographicMatrix(const float left, const float right, const float top, const float bottom, const float zNear, const float zFar)
{
    Mat4 ret(1.0f);

    ret[0][0] = 2.0f / (right - left);
    ret[1][5] = 2.0f / (top - bottom);
    ret[2][6] = 1.0f / (zNear - zFar);
    ret[3][0] = (left + right) / (left - right);
    ret[3][7] = (top + bottom) / (bottom - top);
    ret[3][8] = (zNear) / (zNear - zFar);

    return ret;
}

```

EDIT #2: The new bias matrix:

```
const Mat4 gBiasMatrix(0.5f, 0.0f, 0.0f, 0.0f,
                       0.0f, -0.5f, 0.0f, 0.0f,
                       0.0f, 0.0f, 1.0f, 0.0f,
                       0.5f, -0.5f, 1.0f, 1.0f);

```

Dosn't fix the shadow artifacts though - but the mirror issue yes

# Answer
1. This might be due to the fact that NDC space (post-projective space) in D3D extends from 0 to 1 along the z axis, while in OpenGL it extends from -1 to 1. This requires a change to your projection matrices to generate Z values in the correct range, else half of your depth range will be gone.
2. Window space is top-down in DirectX, rather than bottom-up as in OpenGL. You'll need to take this into account, i.e. by either flipping the Y axis when you render, or flipping the V axis when you sample the shadow map.
> 3 votes

---
Tags: directx11, shadows
---


title: Find normal based on rotation?

text:
# Question
Title: Find normal based on rotation?
Given the XYZ rotation of an object, e.g. `(90,0,0)`, how can I find the object's normal assuming the object is pointing along it's local Z axis?

In the above example the desired result is `(0,1,0)`.

---

I'm using blender, but this seemed like more of a general math question so I decided to ask here..

# Answer
> 1 votes
1. Get the object's Normal as vector (X,Y,Z). I guess that will be (0,0,1) in your case.
2. Construct rotation matrix from your angles (e.g. euler-to-matrix or any other "Euler to Matrix" instructions that suit you). Order of rotations is important.
3. Multiply your Normal with Rotation matrix

---
Tags: mathematics, blender
---


# Question
Title: How can I prevent seams from showing up on objects using lower mipmap levels?
Disclaimer: kindly right click on the images and open them separately so that they're at full size, as there are fine details which don't show up otherwise. Thank you.

I made a simple Blender model, it's a cylinder with the top cap removed:

I've exported the UVs:

Then imported them into Photoshop, and painted the inner area in yellow and the outer area in red. I made sure I cover well the UV lines:

I then save the image and load it as texture on the model in Blender. Actually, I just reload it as the image where the UVs are exported, and change the viewport view mode to textured. When I look at the mesh up-close, there's yellow everywhere, everything seems fine:

However, if I start zooming out, I start seeing red (literally and metaphorically) where the texture edges are:

And the more I zoom, the more I see it:

Same thing happends in Unity, though the effect seems less pronounced. Up close is fine and yellow:

Zoom out and you see red at the seams:

Now, obviously, for this simple example a workaround is to spread the yellow well outside the UV margins, and its fine from all distances. However this is an issue when you try making a complex texture that should tile seamlessly at the edges. In this situation I either make a few lines of pixels overlap (in which case it looks bad from upclose and ok from far away), or I leave them seamless and then I have those seams when seeing it from far away.

So my question is, is there something I'm missing, or some extra thing I must do to have my texture look seamless from all distances?

# Answer
> 15 votes
You can't.

All right, that was a bit harsh. Let me illustrate this with two examples.

1. Let's get outside of the computer graphics world. Suppose you are given a piece of paper with the texture you gave us printed on it. There's a faintly printed millimeter grid in the paper as well.

Now you get some scissors and some paste, and your task is to make a cylinder out of the piece of paper, but you can only cut exactly through the millimeter grid. No problem! the printed paper was originally created in such a way the yellow and red parts fall exactly on the millimeter grid, so you make your cylinder with no problem.

Now your task is to make a cylinder half the size. To do this, you get a piece of paper half the size with everything printed half the size. This is where your problems start. Some of the yellow-red borders will fall on the millimeter grid, but others won't. And for those that don't, you can either cut on the yellow or the red parts. Which one is more correct? It depends. Sometimes it's the yellow one, sometimes it's the red one, sometimes it's neither...
2. So let's get back into the computer graphics world. Let's try to do what you're asking the GPU to do when you're asking it to create mipmaps. Take your large texture and resize it into a texture exactly half the size of the original one. What happens at the yellow-red borders? Well, it depends. It depends on the filtering algorithm you use when scaling your texture down.

If you use "Nearest neighbor", you will preserve your abrupt yellow-red changes, but some borders (to be precise, those that fall in an odd coordinate in the original texture) will be forced to either side of the pixel grid, and the texture coordinates you originally carefully chose will no longer match the yellow-red border.

If you use "Bilinear filtering", things are not really better. When the yellow-red border doesn't fall in the pixel grid as before (once again, when the border lies on an odd coordinate in the original texture), the resulting pixel will neither be red or yellow. It will be more like orange! Is this acceptable? I don't know.

You will notice that the problem is limited to the yellow-red borders that fall in odd coordinates. You can say "no problem!" and make sure all the yellow-red borders fall in even coordinates, and problem solved! Or is it?

Actually not. The problem will be solved when creating the first mip level. But when you create the next mip level, which is a texture one quarter of the size of the original, you will experience the same problem with the yellow-red borders that don't fall in an even coordinate in the half-size texture, which happen to be those that don't fall in a multiple of 4 coordinate in the original texture.

So even if you fix it for the second mip level, you will never solve the entire problem. You will just be taking it to a lower mip level.

As you can see this is not a problem with the game engine you're using. It's a problem with mipmapping in general. So does this mean that mipmapping is useless and should be disabled? Actually no. Mipmapping is very useful. You're just using it wrong. Actually, you said the answer yourself:

> spread the yellow well outside the UV margins, and its fine from all distances

It seems like an ugly hack, but it's actually not. However, I have a more general solution I hereby call the "First Panda Pajama Rule of 3D skinning".

> Don't map abrupt UV coordinate changes to abrupt texture changes.

You're experiencing this problem because you're matching an abrupt texture change (yellow to red) to an abrupt texture coordinate change (the change between the cylinder and the void (or the cap, when you close the cylinder). You want to avoid this when skinning, precisely to avoid the problem you're describing.

Corollary:

> If you must make an abrupt UV coordinate change, don't put an abrupt texture change (like your proposed solution of spreading the yellow). If you must make an abrupt texture change, make it so it doesn't require an abrupt UV coordinate change (you should usually prefer doing this)

You can take advantage of the fact that, unlike when you're making models out of paper and paste, the shape of your texture does not have to match the shape of your model. When making the texture for the cap of your cylinder, you don't have to make it round. In fact, I'd make it rectangular so I can match it to the texture of the sides of the cylinder precisely to avoid abrupt UV coordinate changes between the sides and the caps (look for "Filters-\>Distort-\>Polar Coordinates" in Photoshop).

I'd also align the left and right borders of the cylinder texture to the left and right borders of the texture, and set the texture mapping to wrap, so the texture wraps nicely around the cylinder.

# Answer
> 0 votes
It is a problem of baking in 3D software. Just increase the number of texture seams and second it is all about in Unity selecting texture and Mip on and off. You will see seams will go, but better to see you texture in game with your main camera.

---
Tags: unity, textures, blender, uv-mapping, mipmaps
---


title: UV Atlas Generation and Seam Removal

text:
# Question
Title: UV Atlas Generation and Seam Removal
I'm generating light maps for scene mesh objects using DirectX's UV Atlas Tool( D3DXUVAtlasCreate() ). I've succeeded in generating an atlas, however, when I try to render the mesh object using the atlas the seams are visible on the mesh. Below are images of a lightmap generated for a cube. Here is the code I use to generate a uv atlas for a cube:

```
struct sVertexPosNormTex
{
    D3DXVECTOR3 vPos, vNorm;
    D3DXVECTOR2 vUV;
    sVertexPosNormTex(){}
    sVertexPosNormTex( D3DXVECTOR3 v, D3DXVECTOR3 n, D3DXVECTOR2 uv )
    {
        vPos = v;
        vNorm = n;
        vUV = uv;
    }
    ~sVertexPosNormTex()
    {

    }
};
// create a light map texture to fill programatically
    hr = D3DXCreateTexture( pd3dDevice, 128, 128, 1, 0, D3DFMT_A8R8G8B8,
        D3DPOOL_MANAGED, &pLightmap );
    if( FAILED( hr ) )
    {
        DebugStringDX( "Main", "Failed to D3DXCreateTexture( lightmap )", __LINE__, hr );
        return hr;
    }

    // get the zero level surface from the texture
    IDirect3DSurface9 *pS = NULL;
    pLightmap->GetSurfaceLevel( 0, &pS );

    // clear surface
    pd3dDevice->ColorFill( pS, NULL, D3DCOLOR_XRGB( 0, 0, 0 ) );

    // load a sample mesh
    DWORD dwcMaterials = 0;
    LPD3DXBUFFER pMaterialBuffer = NULL;
    V_RETURN( D3DXLoadMeshFromX( L"cube3.x", D3DXMESH_MANAGED, pd3dDevice, &pAdjacency, &pMaterialBuffer, NULL, &dwcMaterials, &g_pMesh ) );

    // generate adjacency
    DWORD *pdwAdjacency = new DWORD[ 3 * g_pMesh->GetNumFaces() ];
    g_pMesh->GenerateAdjacency( 1e-6f, pdwAdjacency );

    // create light map coordinates
    LPD3DXMESH pMesh = NULL;
    LPD3DXBUFFER pFacePartitioning = NULL, pVertexRemapArray = NULL;
    FLOAT resultStretch = 0;
    UINT numCharts = 0;

    hr = D3DXUVAtlasCreate( g_pMesh, 0, 0, 128, 128, 3.5f, 0, pdwAdjacency, NULL, NULL, NULL, NULL, NULL, 0, &pMesh,
        &pFacePartitioning, &pVertexRemapArray, &resultStretch, &numCharts );
    if( SUCCEEDED( hr ) )
    {
        // release and set mesh
        SAFE_RELEASE( g_pMesh );
        g_pMesh = pMesh;

        // write mesh to file
        hr = D3DXSaveMeshToX( L"cube4.x",
            g_pMesh,
            0,
            ( const D3DXMATERIAL* )pMaterialBuffer->GetBufferPointer(),
            NULL,
            dwcMaterials,
            D3DXF_FILEFORMAT_TEXT );
        if( FAILED( hr ) )
        {
            DebugStringDX( "Main", "Failed to D3DXSaveMeshToX() at OnD3D9CreateDevice()", __LINE__, hr );
        }

        // fill the the light map
        hr = BuildLightmap( pS, g_pMesh );
        if( FAILED( hr ) )
        {
            DebugStringDX( "Main", "Failed to BuildLightmap()", __LINE__, hr );
        }
    }
    else
    {
        DebugStringDX( "Main", "Failed to D3DXUVAtlasCreate() at OnD3D9CreateDevice()", __LINE__, hr );
    }

    SAFE_RELEASE( pS );
    SAFE_DELETE_ARRAY( pdwAdjacency );
    SAFE_RELEASE( pFacePartitioning );
    SAFE_RELEASE( pVertexRemapArray );
    SAFE_RELEASE( pMaterialBuffer );

```

Here is code to fill lightmap texture:

```
HRESULT BuildLightmap( IDirect3DSurface9 *pS, LPD3DXMESH pMesh )
{
    HRESULT hr = S_OK;

    // validate lightmap texture surface and mesh
    if( !pS
        || !pMesh )
        return E_POINTER;

    // lock the mesh vertex buffer
    sVertexPosNormTex *pV = NULL;
    pMesh->LockVertexBuffer( D3DLOCK_READONLY, ( void** )&pV );

    // lock the mesh index buffer
    WORD *pI = NULL;
    pMesh->LockIndexBuffer( D3DLOCK_READONLY, ( void** )&pI );

    // get the lightmap texture surface description
    D3DSURFACE_DESC desc;
    pS->GetDesc( &desc );

    // lock the surface rect to fill with color data
    D3DLOCKED_RECT rct;
    hr = pS->LockRect( &rct, NULL, 0 );
    if( FAILED( hr ) )
    {
        DebugStringDX( "main.cpp:", "Failed to IDirect3DTexture9::LockRect()", __LINE__, hr );
        return hr;
    }

    // iterate the pixels of the lightmap texture
    //      check each pixel to see if it lies between the uv coordinates of a cube face
    BYTE *pBuffer = ( BYTE* )rct.pBits;
    for( UINT y = 0; y < desc.Height; ++y )
    {
        BYTE* pBufferRow = ( BYTE* )pBuffer;
        for( UINT x = 0; x < desc.Width * 4; x+=4 )
        {
            // determine the pixel's uv coordinate
            D3DXVECTOR2 p( ( ( float )x / 4.0f ) / ( float )desc.Width + 0.5f / 128.0f, y / ( float )desc.Height + 0.5f / 128.0f );

            // for each face of the mesh
            //      check to see if the pixel lies within the face's uv coordinates
            for( UINT i = 0; i < 3 * pMesh->GetNumFaces(); i +=3 )
            {
                sVertexPosNormTex v[ 3 ];
                v[ 0 ] = pV[ pI[ i + 0 ] ];
                v[ 1 ] = pV[ pI[ i + 1 ] ];
                v[ 2 ] = pV[ pI[ i + 2 ] ];

                if( TexcoordIsWithinBounds( v[ 0 ].vUV, v[ 1 ].vUV, v[ 2 ].vUV, p ) )
                {
                    // the pixel lies b/t the uv coordinates of a cube face
                    // light contribution functions aren't needed yet
                    //D3DXVECTOR3 vPos = TexcoordToPos( v[ 0 ].vPos, v[ 1 ].vPos, v[ 2 ].vPos, v[ 0 ].vUV, v[ 1 ].vUV, v[ 2 ].vUV, p );
                    //D3DXVECTOR3 vNormal = v[ 0 ].vNorm;

                    // set the color of this pixel red( for demo )
                    BYTE ba[] = { 0, 0, 255, 255, };

                    //ComputeContribution( vPos, vNormal, g_sLight, ba );

                    // copy the byte array into the light map texture
                    memcpy( ( void* )&pBufferRow[ x ], ( void* )ba, 4 * sizeof( BYTE ) );
                }
            }
        }

        // go to next line of the texture
        pBuffer += rct.Pitch;
    }

    // unlock the surface rect
    pS->UnlockRect();

    // unlock mesh vertex and index buffers
    pMesh->UnlockIndexBuffer();
    pMesh->UnlockVertexBuffer();

    // write the surface to file
    hr = D3DXSaveSurfaceToFile( L"LightMap.jpg", D3DXIFF_JPG, pS, NULL, NULL );
    if( FAILED( hr ) )
        DebugStringDX( "Main.cpp", "Failed to D3DXSaveSurfaceToFile()", __LINE__, hr );

    return hr;
}
bool TexcoordIsWithinBounds( const D3DXVECTOR2 &t0, const D3DXVECTOR2 &t1, const D3DXVECTOR2 &t2,
                     const D3DXVECTOR2 &p )
{
    // compute vectors
    D3DXVECTOR2 v0 = t1 - t0,
        v1 = t2 - t0,
        v2 = p - t0;

    float f00 = D3DXVec2Dot( &v0, &v0 );
    float f01 = D3DXVec2Dot( &v0, &v1 );
    float f02 = D3DXVec2Dot( &v0, &v2 );
    float f11 = D3DXVec2Dot( &v1, &v1 );
    float f12 = D3DXVec2Dot( &v1, &v2 );

    // Compute barycentric coordinates
    float invDenom = 1 / ( f00 * f11 - f01 * f01 );
    float fU = ( f11 * f02 - f01 * f12 ) * invDenom;
    float fV = ( f00 * f12 - f01 * f02 ) * invDenom;

    // Check if point is in triangle
    if( ( fU >= 0 ) && ( fV >= 0 ) && ( fU + fV < 1 ) )
        return true;

    return false;
}

```

Screenshot

Lightmap

I believe the problem comes from the difference between the lightmap uv coordinates and the pixel center coordinates...for example, here are the lightmap uv coordinates( generated by D3DXUVAtlasCreate() ) for a specific face( tri ) within the mesh, keep in mind that I'm using the mesh uv coordinates to write the pixels for the texture:

v\[ 0 \].uv = D3DXVECTOR2( 0.003581, 0.295631 );

v\[ 1 \].uv = D3DXVECTOR2( 0.003581, 0.003581 );

v\[ 2 \].uv = D3DXVECTOR2( 0.295631, 0.003581 );

the lightmap texture size is 128 x 128 pixels. The upper-left pixel center coordinates are: float halfPixel = 0.5 / 128 = 0.00390625; D3DXVECTOR2 pixelCenter = D3DXVECTOR2( halfPixel, halfPixel );

will the mapping and sampling of the lightmap texture will require that an offset be taken into account or that the uv coordinates are snapped to the pixel centers..?

...Any ideas on the best way to approach this situation would be appreciated...What are the common practices?

# Answer
> 3 votes
In the past I've fixed this sort of problem using a dilation filter. Basically, the idea is to go over the lightmap after it's rendered and expand the borders of all the pieces by a few pixels, by copying the values of filled pixels into adjacent empty pixels. This can be done with a pixel shader in a full-screen pass or two over the lightmap.

# Answer
> 1 votes
The dilatation will seem to work, but it is an imperfect solution because it is undersampled, it re-uses information (entropy coming from light irradiance samples) and spread it over, effectively creating extrapolation.
The correct thing to do here is to use **conservative rasterization** which is not trivial at all to do. Your rasterization is based on the very classic barycentric coordinates `is-pt-in-triangle` test. This is not conservative and thus some texels which HAVE partial surface intersected in the triangle don't get chosen because the test point (center?) is over the mathematical edge (infinitely thin).
There are some papers about conservative rasterization, but they all implement fairly complex methods. You're free to do your own hack here. e.g. like multisampling the `point in the texel (lumel)` test, that you test for inclusion so that you have greater chance of picking texels on the edge. that would be the fastest way to *somehow*-conservativeness :)

Or you can just be happy with dilatation and call it a day. Anyway, the conservative rasterization is not enough in itself because of filtering issues later. And obviously as well, never try to generate mipmaps for lightmaps, directx will do it automatically in numerous cases therefore dont forget to force it off (only 1 mip). Otherwise you are going to see the black re-appear for afar objects.

---
Tags: c++, directx9, uv-mapping, lightmap
---


# Question
Title: Procedual level generation for a platformer game (tilebased) using player physics
I have been searching for information about how to build a 2d world generator (tilebased) for a platformer game I am developing. The levels should look like dungeons with a ceiling and a floor and they will have a high probability of being just made of horizontal rooms but sometimes they can have exits to a top/down room.

Here is an example of what I would like to achieve. I'm referring only to the caves part. I know level design won't be that great when generated but I think it is possible to have something good enough for people to enjoy the procedural maps (Note: Super Metroid Spoiler!):

http://www.snesmaps.com/maps/SuperMetroid/SuperMetroidMapNorfair.html

An idea I had to accomplish this was to let the computer play a level and carve the dungeon as the "computer player" plays. But don't know how to handle branches in the way, etc... Using this way of carving I could be confident that at least an exit exists in the map and that it is reachable.

Another idea I had was using a cellular automata with some heuristics to do the carving. A problem arises here: how could I make sure that all zones carved are reachable by the player (that is limited by gravity, etc...) ?. I guess I could use some kind of graph that could follow the different dungeon floors the automata is carving and then somehow I could measure if some part would be reachable or not by the player and add platforms or new terrain to make it reachable.

# Answer
> 2 votes
In order to create a randomly procedurally generated level, you need a random moving unit AI that behaves like the player.

The computer controlled unit needs all the moves (actions) the player would have at this point in the game and it will need to refrain from heading back (I'll explain why and how next).

You need to mark each platform and each empty `tile` or empty `space` the carving character moves through to ensure they are not modified after they are generated. If they are modified it could break the desired flow and movement in the level.

Lets take a "basic" example where the player unit can only walk, jump and fall. The computer controlling AI begins sending the player a random stream of input and state (similar to keyboard input from a real live player + `onGround` state Boolean).

Lets say the AI player starts in an entrance. Now the computer begins to pick moves randomly with a specified expectancy. Each time the unit moves left or right `onGround`, a platform is generated underneath it's new position. The unit is disallowed from moving backwards to platfroms it already visited (we specified how before).

The player can also jump. When the player jumps, she will begin to fall down once she reaches her jump `maxHeight`. When she begins to fall, the computer will decide when to turn the `onGround` back on. This needs to be done before the player reaches a point lower than the point from which the character cannot jumped back unless you want the reverse route to be inaccessible (you need to write a method that test for jump-back-ability, there are instructions on the site).

Sometimes you may wish to randomly turn off the `onGround` and let the character fall through a hole in the ground. Again the character is disallowed from falling longer than her jump `maxHeight` when the route needs to be bidirectional.

In order to add forks in the route, simply create a new random player moving player at the point where you want the path to fork, this player will have to jump because it is disallowed from moving on existing ground and after jumping it will need to land on a newly created platform because like we said, empty `tiles` or empty `space` are not modifiable after a character moved through them.

Last notes:

* Test for jump-back-ability and create empty space tiles as needed.
* give the player a general direction to head towards.
* Allow it multiple goals in one room so the path could twist and turn.

---
Tags: 2d, tiles, procedural-generation, tilemap, procedural
---


# Question
Title: Dealing with numerous, simultaneous sounds in unity
I've written a custom class that creates a fixed number of audio sources. When a new sound is played, it goes through the class, which creates a queue of sounds that will be played during that frame. The sounds that are closer to the camera are given preference.

If new sounds arrive in the next frame, I have a complex set of rules that determines how to replace the old ones. Ideally, "big" or "important" sounds should not be replaced by small ones. Sound replacement is necessary since the game can be fast-paced at times, and should try to play new sounds by replacing old ones. Otherwise, there can be "silent" moments when an old sound is about to stop playing and isn't replaced right away by a new sound. The drawback of replacing old sounds right away is that there is a harsh transition from the old sound clip to the new one.

But I wonder if I could just remove that management logic altogether, and create audio sources on the fly for new sounds. I could give "important" sounds more priority (closer to 0 in the corresponding property) as opposed to less important ones, and let Unity take care of culling out sound effects that exceed the channel limit. The only drawback is that it requires many heap allocations.

I wonder what strategy people use here?

# Answer
> But I wonder if I could just remove that management logic altogether, and create audio sources on the fly for new sounds.

Don't create and destroy "numerous" audio sources on each frame, you'll just slow the game down eventually. Allocation is not your only issue there, but also the garbage collector kicking in to clean things.

Keep on using a constant number of audio sources and switch old sounds with new ones. To avoid what you mention to be a harsh transition, add a smooth transitioning effect. You can do more than `audioSource.sound = newSound;` to change a sound.

For example, when it's time to switch to a new sound, quickly lower the volume of the old sound, replace the old sound, then raise the volume again. Set this interval to whatever value you find to work best for your case.

Another example would be to use two audio sources for a single transition, and crossfade (audio source 1's volume is lowered, audio source 2's volume is increased) between the two different sound effects.
> 6 votes

---
Tags: unity, audio
---


# Question
Title: techniques for an AI for a highly cramped turn-based tactics game
I'm trying to write an AI for a tactics game in the vein of Final Fantasy Tactics or Vandal Hearts. I can't change the game rules in any way, only upgrade the AI. I have experience programming AI for classic board games (basically minimax and its variants), but I think the branching factor is too great for the approach to be reasonable here. I'll describe the game and some current AI flaws that I'd like to fix. I'd like to hear ideas for applicable techniques. I'm a decent enough programmer, so I only need the ideas, not an implementation (though that's always appreciated). I'd rather not expend effort chasing (too many) dead ends, so although speculation and brainstorming are good and probably helpful, I'd prefer to hear from somebody with actual experience solving this kind of problem.

For those who know it, the game is the land battle mini-game in Sid Meier's Pirates! (2004) and you can skim/skip the next two paragraphs. For those who don't, here's briefly how it works. The battle is turn-based and takes place on a 16x16 grid. There are three terrain types: clear (no hindrance), forest (hinders movement, ranged attacks, and sight), and rock (impassible, but does not hinder attacks or sight). The map is randomly generated with roughly equal amounts of each type of terrain. Because there are many rock and forest tiles, movement is typically very cramped. This is tactically important. The terrain is not flat; higher terrain gives minor bonuses. The terrain is known to both sides. The player is always the attacker and the AI is always the defender, so it's perfectly valid for the AI to set up a defensive position and just wait. The player wins by killing all defenders or by getting a unit to the city gates (a tile on the other side of the map).

There are very few units on each side, usually 4-8. Because of this, it's crucial not to take damage without gaining some advantage from it. Units can take multiple actions per turn. All units on one side move before any units on the other side. Order of execution is important, and interleaving of actions between units is often useful. Units have melee and ranged attacks. Melee attacks vary widely in strength; ranged attacks have the same strength but vary in range.

The main challenges I face are these:

* Lots of useful move combinations start with a "useless" move that gains no immediate advantage, or even loses advantage, in order to set up a powerful flank attack in the future. And, since the player units are stronger and have longer range, the AI pretty much always has to take some losses before they can start to gain kills. The AI must be able to look ahead to distinguish between sacrificial actions that provide a future benefit and those that don't.
* Because the terrain is so cramped, most of the tactics come down to achieving good positioning with multiple units that work together to defend an area. For instance, two defenders can often dominate a narrow pass by positioning themselves so an enemy unit attempting to pass must expose itself to a flank attack. But one defender in the same pass would be useless, and three units can defend a slightly larger pass. Etc. The AI should be able to figure out where the player must go to reach the city gates and how to best position its few units to cover the approaches, shifting, splitting, or combining them appropriately as the player moves.
* Because flank attacks are extremely deadly (and engineering flank attacks is key to the player strategy), the AI should be competent at moving its units so that they cover each other's flanks unless the sacrifice of a unit would give a substantial benefit. They should also be able to force flank attacks on players, for instance by threatening a unit from two different directions such that responding to one threat exposes the flank to the other.
* The AI should attack if possible, but sometimes there are no good ways to approach the player's position. In that case, the AI should be able to recognize this and set up a defensive position of its own. But the AI shouldn't be vulnerable to a trivial exploit where the player repeatedly opens and closes a hole in his defense and shoots at the AI as it approaches and retreats. That is, the AI should ideally be able to recognize that the player is *capable* of establishing a solid defense of an area, even if the defense is not currently in place. (I suppose if a good unit allocation algorithm existed, as needed for the second bullet point, the AI could run it on the player units to see where they could defend.)
* Because it's important to choose a good order of action and interleave actions between units, it's not as simple as just finding the best move for each unit in turn.

All of these can be accomplished with a minimax search in theory, but the search space is too large, so specialized techniques are needed. I thought about techniques such as influence mapping, but I don't see how to use the technique to great effect. I thought about assigning goals to the units. This can help them work together in some limited way, and the problem of "how do I accomplish this goal?" is easier to solve than "how do I win this battle?", but assigning good goals is a hard problem in itself, because it requires knowing whether the goal is achievable and whether it's a good use of resources.

So, does anyone have specific ideas for techniques that can help cleverize this AI?

Update: I found a related question on Stackoverflow: https://stackoverflow.com/questions/3133273/ai-for-a-final-fantasy-tactics-like-game The selected answer gives a decent approach to choosing between alternative actions, but it doesn't seem to have much ability to look into the future and discern beneficial sacrifices from wasteful ones. It also focuses on a single unit at a time and it's not clear how it could be extended to support cooperation between units in defending or attacking.

# Answer
Here is how I would approach this:

I would start by performing terrain analysis (pdf) and creating a set of influence maps based on various attributes (conflict maps, resource maps, etc). You might want to combine the influence maps together with associated weights. You'll probably update some of them at the start of each turn.

But assuming you have the above, and since the game does not control that many agents, I think a simple two level system is sufficient: the high-level, where strategic decisions are made, and the low-level, where tactical decisions are made.

In the high-level, you could have an Utility-Based system that would feed the state of the game (including the analysis) and get a decision. Or have a trained neural network that takes the same information and outputs a decision.

In both cases, you would end up with a strategic decision. You would then break that down into multiple steps that each agent would have to perform. I.e. if the strategic decision is to attack a certain location, the first step for each agent would be to path find to a specific tile and attack a specific enemy unit. Depending on the system, you can use a planner to break that decision down (might be too complicated) or have those steps embedded in the decision itself (depends on your architecture).
> 4 votes

# Answer
I have no experience programming AI. However, I can offer you my naive strategy that might help you brainstorm a little. I know you said you'd prefer experienced individuals for this question, but this is an intimidating question to say the least.

Right then. What I would do is implement a per-turn checklist/surveillance. Each AI unit, every turn, would:

1. Scan the map for advantageous positions (high ground, bottlenecks, etc) either within a range or globally, depending on how smart/fast you want them to be.
2. Compute the number of minimum turns required to reach that spot, and compare that number to the number of turns the player would have to use to get there.
3. If the AI should decide to move, scan the immediate surroundings. If the terrain's obstacles are purely static(mountains, forest, etc), then find the quickest route around. If the obstacles are dynamic (other AI, or (I guess) player units), check if the AI is in the way, and if so, determine if it is about to move. If it is moving soon, wait it out, otherwise, go around.
4. In order to move as a team, I would implement a 'squad' sort of class/array. Assign one squad to the front; if another is available, assign it to the rear; if another is available, assign it to the side closest to the nearest hostile.
5. If a single unit is dispatched to reach the gates, dispatch a single unit (or two, if you want to smite the player) from the largest squad.

I realize this may be of little to no use to you, but some help is better than none.
> 1 votes

# Answer
Curious to hear what ideas you ended up going with. I've worked on this type of problem myself, so I'm interested to hear what you found that works, and what not.

In my own projects, I currently use a very simple approach to determine AI:

First, I determine which units should go first. This is done by assigning an initiative to each unit; fast unit, units closer to the enemy, and units on the flanks are usually prioritized.

I then iterate over each unit. For each unit, I map its possible moves (including staying in place). Each move is assigned a utility, depending on a number of factors (terrain benefits, can I attack from here, cost to move there, closeness to enemy, etc). A location's utility can also be set by factoring in which "good" locations are within range from it (e.g., or #2 from igrad above). I then sort by utility and pick the best move (or randomly from among the best, depending on difficulty level).

The trick of the effective AI is getting the utility constants right. It's very dependent on that, but when it clicks, it gives a fairly effective AI - albeit not very creative.

It does not look too far ahead, because generally I do not find that this leads to all that useful behavior, unless you can also predict what the player will do.

Two simple added refinements that I am considering:

* Do two passes over the unit planning, in order to avoid the situation where a unit enters the intended path of another unit, thereby blocking it from engaging.
* Implement a basic strategic layer, that "forces" specific movement based on a strategic plan (e.g., outflank left/right, double envelopment, etc). Choice of strategy would of course be limited by terrain. Essentially what the strategy would do is affect the utility functions when dealing with the relevant sector of the battlefield (e.g., outflank right would make all units on the right flank prioritize a rapid advance in the beginning).
> 0 votes

# Answer
A very complicated question, but here are my 2 cents.

Judging from your explanation, this game has some broad sets of movements which are generally desirable, such as 'take a high position' or 'defend the flanks'. I think these kind of game calls more for the `Artificial` part in the term Artificial Intelligence.

Maybe you could implement a movement library, so that the player makes these kind of movements in a more automatic way (probably using some kind of rule system), and then let the minmax act when there is no obvious optimal strategy.

You can also go completely out of your way and actually implement the AI using some kind of machine learning. By using traces from previous games (against the AI itself, or ideally against people) you can train a ML of your choice. Maybe its a long shot, but worth exploring.
> 0 votes

---
Tags: ai, turn-based, turn-based-strategy
---


title: Pokemon Yellow wrap transitions

text:
# Question
Title: Pokemon Yellow wrap transitions
So I've been trying to make a pretty accurate clone of the good old Pokemon Yellow for quite some time now and one puzzling but nonetheless subtle mechanic has puzzled me. As you can see in the uploaded image there is a certain colour manipulation done in two stages after entering a wrap to another game location (such as stairs or entering a building).

One easy (and sloppy) way of achieving this and the one I have been using so far is to make three copies of each image rendered on the screen all of them with their colours adjusted accordingly to match each stage of the transition. Of course after a while this becomes tremendously time consuming.

So my question is does anyone know any better way of achieving this colour manipulation effect using java?

Thanks in advance,

Alex

# Answer
In java you can use an RGBImageFilter and a FilteredImageSource to change the individual pixels of an image before you draw it.

```
Image screen = //render screen to image
if(timeSinseStartWarp>0){
    ImageFilter effectFilter = new Warpfilter(timeSinseStart);
    screen  = createImage(new FilteredImageSource(screen.getSource, effectFilter));
}

```
> 1 votes

---
Tags: java, graphics, graphic-effects
---


# Question
Title: TileEntitySpecialRenderer only renders from certain angle
I'm developing a Minecraft mod with Forge. I've added a tileentity and a custom renderer for it. The problem is: The block is only visible from sertain angles. I've compaed my code to other peoples code and it looks pretty much like them.

The block is opaque and not to be rendered and the renderer is registered normally so the fault must be in the renderer.

Here's the renderer code:

```
public class TERender extends TileEntitySpecialRenderer
{
    public void renderTileEntityAt(TileEntity tileEntity, double d, double d1, double d2, float f)
    {
        GL11.glPushMatrix();
        GL11.glTranslatef((float)d, (float)d1, (float)d2);
        HeatConductTileEntity TE = (HeatConductTileEntity)tileEntity;
        renderBlock(TE, tileEntity.getWorldObj(), tileEntity.xCoord, tileEntity.yCoord, tileEntity.zCoord, mod.EMHeatConductor);
        GL11.glPopMatrix();
    }

    public void renderBlock(HeatConductTileEntity tl, World world, int i, int j, int k, Block block)
    {
        Tessellator tessellator = Tessellator.instance;
        GL11.glColor3f(1, 1, 1);
        tessellator.startDrawingQuads();
        tessellator.addVertex(0, 0, 0);
        tessellator.addVertex(1, 0, 0);
        tessellator.addVertex(1, 1, 0);
        tessellator.addVertex(0, 1, 0);
        tessellator.draw();
    }
}

```

# Answer
> 1 votes
Turns out if you want to render only colour, but not texture you have to disable GL\_TEXTURE\_2D

---
Tags: java, rendering, minecraft-modding
---


# Question
Title: Why does my code dividing a 2D array into chunks fail?
I have a 2D-Array representing my world. I want to divide this huge thing into smaller chunks to make collision detection easier.

I have a `Chunk` class that consists only of another 2D `Array` with a specific width and height and I want to iterate through the world, create new `Chunk`s and add them to a list (or maybe a `Map` with `Coordinates` as the key; we'll see about that).

```
world = new World(8192, 1024);

Integer[][] chunkArray;

for(int a = 0; a < map.getHeight() / Chunk.chunkHeight; a++)
{
    for(int b = 0; b < map.getWidth() / Chunk.chunkWidth; b++)
    {
        Chunk chunk = new Chunk();
        chunkArray = new Integer[Chunk.chunkWidth][Chunk.chunkHeight];

        for(int x = Chunk.chunkHeight*a; x < Chunk.chunkHeight*(a+1); x++)
        {
            for(int y = Chunk.chunkWidth*b; y < Chunk.chunkWidth*(b+1); y++)
            {
                // Yes, the tileMap actually is [height][width] I'll have
                // to fix that somewhere down the line -.-
                chunkArray[y][x] = map.getTileMap()[x*a][y*b];
                // TODO:Attach to chunk
            }
        }

        chunkList.add(chunk);
    }
}

System.out.println(chunkList.size());

```

The two outer loops get a new chunk in a specific row and column. I do that by dividing the overall size of the map by the `chunkSize`.

The inner loops then fill a new `chunkArray` and attach it to the chunk. But somehow my maths is broken here.

Let's assume the `chunkHeight = chunkWidth = 64`.

For the first Array I want to start at `[0][0]` and go until `[63][63]`. For the next I want to start at `[64][64]` and go until `[127][127]` and so on. But I get an out of bounds exception and can't figure out why.

Any help appreciated!

**Actually I think I know where the problem lies:**

`chunkArray[y][x]` can't work, because `y` goes from 0-63 just in the first iteration. Afterwards it goes from 64-127, so sure it is out of bounds.

Still no nice solution though :/

**EDIT:**

```
if(y < Chunk.chunkWidth && x < Chunk.chunkHeight)
    chunkArray[y][x] = map.getTileMap()[y][x];

```

This works for the first iteration... now I need to get the commonly accepted formula.

# Answer
Note that even though your `chunkArray` instances are all supposed to cover different areas of your world, their indices still all range from `0` to `Chunk.chunkWidth` and `0` to `Chunk.chunkHeight` respectively.

Therefore, you should make sure that whenever you access `chunkArray` the `x-` and `y-` indices do not go out of these ranges. The easiest way to make sure they won't is to actually change the two inner-most for-loops like so:

```
int offsetX = b * Chunk.chunkWidth;
int offsetY = a * Chunk.chunkHeight;
Integer[][] tileMap = map.getTileMap();

for(int y = 0; y < Chunk.chunkHeight; y++)
{
    for(int x = 0; x < Chunk.chunkWidth; x++)
    {
        chunkArray[x][y] = tileMap[offsetX + x][offsetY + y];
    }
}

```

A faster way to achieve the same thing would be to use the built-in `System.arraycopy`:

```
int offsetX = b * Chunk.chunkWidth;
int offsetY = a * Chunk.chunkHeight;
Integer[][] tileMap = map.getTileMap();

for(int x = 0; x < Chunk.chunkWidth; x++)
{
   System.arraycopy(tileMap[offsetX + x], offsetY, chunkArray[x], 0, Chunk.chunkHeight);
}

```
> 2 votes

# Answer
Here is my two cents:

All the work can be found on here too so you can run it and see how it works http://ideone.com/xKWAip

Separate it into pieces and you can see how it'll work with a wee access expression after flattening the initial map array.

Here is what I used to generate your map (at the moment it's square only but as long as your width and length are divisible by your chunk size you're fine):

```
public static int[][] GenMap(int mapSize)
{
    int[][] arrayStuff = new int[mapSize][mapSize];
    for (int x = 0; x < mapSize; x++)
    {
        for (int y = 0; y < mapSize; y++)
        {
            arrayStuff[x][y] = y + (mapSize * x);
        }
    }
    return arrayStuff;
}

```

Here we Generate the chunks by flattening the map array and then using a chunk map coordinate of `(i, j)` and a chunk coordinate of `(x, y)` to then look through x and y within `i` and `j`.

Once that is looped through you can use the expression: `y + (x * mapLength) + (chunkSize * i) + (chunkSize * mapLength * j)` to find the index of the flattened array, providing the values you need in a `[0, 1, 2, 3], [16, 17, 18, 19], [32, 33, 34, 35], [48, 49, 50, 51]` format for your chunk info.

```
public static List<int[][]> GenChunks(int[][] map, int mapLength, int chunkSize)
{
    int[] inputArray = new int[map.length * map[0].length];
    for(int a = 0; a < map.length; a++)
    {
        for(int b = 0; b < map[0].length; b++)
        {
            inputArray[(a * map.length) + b] = map[a][b];
        }
    }

    List<int[][]> chunksList = new ArrayList<int[][]>();

    for (int i = 0; i < mapLength / chunkSize; i++)
    {
        for (int j = 0; j < mapLength / chunkSize; j++)
        {
            int[][] newChunk = new int[chunkSize][];

            for (int x = 0; x < chunkSize; x++)
            {
                newChunk[x] = new int[chunkSize];

                for (int y = 0; y < chunkSize; y++)
                {
                    int offset = j * chunkSize * mapLength;
                    newChunk[y][x] = inputArray[y + (x * mapLength) + (chunkSize * i) + (chunkSize * mapLength * j)];
                }
            }

            chunksList.add(newChunk);
        }
    }

    return chunksList;
}

```

Example usage:

```
public static void main (String[] args) throws java.lang.Exception
{
    int mapSize = 8;
    int chunkSize = 2;

    int[][] mapArray = GenMap(mapSize);

    System.out.println("Start chunks");

    List<int[][]> chunks;
    chunks = GenChunks(mapArray, mapSize , chunkSize);
 }

```
> 2 votes

---
Tags: java
---


title: Dynamic object creation with HashMap

text:
# Question
Title: Dynamic object creation with HashMap
I want to use a HashMap to dynamically create objects based on the key.

I have a Random Map Generator that stores the maps in 3D Arrays of Type `Integer[][][]`. Upon creation of the actual map I iterate through this array and based on the Integer I want to create the right block.

Example: `Integer[][][] map ... map[6][6][6] = 3;` 3 is a Earth-Block and now I want to initialize a new Block of this type and give it the right coordinates.

Currently I store my Bindings from Integer to Class in a `HashMap(Integer, String)` and create my objects like that:

```
int id = array[x][y][z];
String block_name = Blocks.map.get(id);

Block block = (Block) Class.forName(block_name).newInstance();
block.setPosition(x,y,z);

```

But I want to avoid `newInstance()` if possible.

I've never worked that dynamically with Java before and I couldn't find a solution like changing the HashMap to (Integer, Class) or something. I just need to create a new Object based upon the Integer.

Any ideas/solutions? Thanks in advance and have a wonderful day!

# Answer
> 1 votes
Invalidated by asker

> If you don't mind to use the same Block over and over again, simply do a mapping `Integer→Block`.

---

## Answer starts here

Otherwise, you could use some kind of factory-pattern.

You store a mapping `Integer→BlockFactory`, where BlockFactory is an instance of the Factpry corresponding Block. You then have a `newInstance(/*params*/)` method which would create a Block on runtime.

```
public DirtFactory extends BlockFactory
{
    @Override
    public Block newInstance(int x, int y /*...*/)
    {
        Dirt d = new Dirt();
        d.x = x; d.y = y; /*...*/
        /* do other stuff if necessary*/
        return d;
}

```

.

```
/*only the code from id to block */
HashMap<Integer,BlockFactory> mapping = new HashMap<>();

/*fill your HashMap with Instances of your BlockFactorys at the start of your game*/

int id = array [13][3][7];
Block b = mapping.get(id).newInstance(/*params*/);

```

Now you have your Block saved in `b`.
You will not come around a newInstance () in some way (a copy() is also some kind of newInstance() ). But I consider my solution better than using the Class-class.
If you want to save class-Definitions, you can embed the functionality of the Factory in the corresponding Block, however this gets messy very, *very* fast and is not recommended.

Note to programmers: I know this is not the nicest representation for the Factory-Pattern, but should do the trick here quite well.

---
Tags: java
---