title: Move player to mouse click

text:
# Question
Title: Move player to mouse click
Im hopelessly not good at algebra and such. But im trying to learn. I want to learn and understand how to use it in game programming rather than modifying snippets or using classes that do it for me.

So what i want to start with is to click on location and have an object move there. This is what i am thinking (in pseudocode and in a 2D world).

```
        vector2 mousePosition;
        vector2 playerPosition;

        vector2 direction = playerPosition - mousePosition;

        direction.normalize; //ive learned that this should be done, and i understand what it means to normalise a vector, but i am not quite sure of what goes wrong if the vector is not normalised

    //in the players update
    if (player is not facing destinations direction)
    {
player.transform.direction = Lerp towards direction;

}else if(player IS facing the destinations direction)
{
player.rigidbody.AddForce(vector.forward, 100f);
}

```

Am i thinking correctly?

# Answer
> 2 votes
It depends on how you want your character to behave. In general, what you wrote is approximately correct, but be careful of a few things:

1. If the player is already at the `mousePosition`, then direction will have zero length and normalize will be a division by zero! To prevent this, just have an if statement and don't continue unless `direction.length > 0.01` (or some other small constant).
2. Similarly, be careful with the directions. The test `player is not facing destinations direction` is as simple as `direction * player.transform.direction < 0.95`, where * is the dot product, **assuming** both directions are normalized (this is why you want to normalize). Basically, as two unit-length vectors (i.e. directions) get nearer to each other, their dot product gets closer and closer to 1, and if they are the same, then their dot product is exactly 1. On computer of course, the is rounding error, which is why you choose a cut-off close to, but not exactly, 1.
3. Finally, I'm not sure what system you are using, but adding a force is almost certainly the wrong way to get something like a character to move realistically, because players rarely have significant inertia, except in space sims. Also, you probably want to use the target direction rather than vector.forward.
4. See http://www.red3d.com/cwr/steer/Arrival.html, and the other behaviours on that site to get an idea of how to control characters which need to slow down/speed up. If your character is a person/creature, these are not what you are looking for, as you need something designed for a character which can start and stop on a dime.

# Answer
> 0 votes
If you did not normalize the vector, the direction would infact be the same, in a sense, but the scale wrong. Take direction vector \[2.0, 1.0\] and direction vector \[1.0, 0.5\]. Essentially they are pointing the same way, but if you compare them in your code you would get a false in return. Even worse if you want to accelerate something along the direction vector by multiplying it by a constant you would in the case of the first vector get double the acceleration compared to the normalized second one, so it is important to keep directions normalized.

Without knowing the whole context, I would say you think correctly thus far.

# Answer
> 0 votes
Starting with the normalization, it's the process of getting a vector and resizing it to one unit (one meter, one kilometer, whatever you are using). Why this? Because of this equation:

```
s = v.t

```

where `s` is space, `v` is velocity and `t` time. So it tells where your object will be in a given `t` delta time when on `v` speed.

But this is for unidimensional space. When you are in 2D space, you can have movement in two dimensions, `x` and `y`. So your equation is:

```
S = V.t

```

where `S` and `V` are 2D vectors. When your `V` has some speed in `x` but zero in `y`, `S` will result in movement in the `x` axis and not on `y`. Hence, we can say `V` not only tells how fast the object moves, but it also tells which direction it's going, right?

In this case, `V` is not called *speed* anymore, it's called *velocity*, because it contains a direction and it tells how fast the object moves.

But what would be `direction = playerPosition - mousePosition`? It certainly points towards the mouse position, but you can easily see that the farther the mouse position is from player position, the bigger the direction will be. Which means it's more than just the direction, in fact, it's the distance the player should move to get to the mouse position, which is not what you want. You want a direction, and that's why you normalize, to make a vector of magnitude (size) one, so it just represents a direction. And then we have:

```
s = v.D.t

```

where `D` is the direction vector. See? `v.D` is equal to `V`, that is, a scalar `v` multiplied by a direction `D`, vector of size one, will give you velocity.

The same thought can be applied to force equations, which the `AddForce` method uses. `AddForce` takes a direction vector and a scalar for the size of this force. But you don't need to normalize `D` because you don't use it to apply the force, you use `vector.forward` which is a normalized vector.

---
Tags: unity, vector, linear-algebra
---


# Question
Title: Change AI steering behavior's direction to 8 directions
I am making a 2d soccer game, all players move in 8 directions, so I need to convert AI steering behavior(like arrive and pursuit) into 8 directions.
Here are three example situations:
Player(now is at point A) set target To point B, we could not directly move in direction(B - A), player need to first move to point C in horizontal or vertical, then move in 45 degree to reach target point. Consider in my game there is no steering behavior accumulation, which means, at any time , only have one function to affect player movement(arrive or pursuit), so I first make convert code in arrive function, because pursuit actually call arrive either.
Here is pseudo-code:

```
void RSAIController::Init()
{
   ...
    m_vDirectionArray[0] = CCPoint(1.f, 0.f);
    m_vDirectionArray[1] = CCPoint(0.7071f, 0.7071f);
    m_vDirectionArray[2] = CCPoint(0.f, 1.f);
    m_vDirectionArray[3] = CCPoint(-0.7071f, 0.7071f);
    m_vDirectionArray[4] = CCPoint(-1.f, 0.f);
    m_vDirectionArray[5] = CCPoint(-0.7071f, -0.7071f);
    m_vDirectionArray[6] = CCPoint(0.f, -1.f);
    m_vDirectionArray[7] = CCPoint(0.7071f, -0.7071f);
}
//called in arrive method, then use m_vMoveDirection as speed direction
void RSAIController::ConvertTo8Directional()
{
    int idx = -1;
    float maxValue = -MaxFloat;
    CCPoint direction = m_vTarget - m_pPlayer->Pos();
    //do this because in cocos2d normalize zero vector will return (1, 0)
    //which is not the expected result,so I avoid it manually
    if(!VIsZero(direction))
        direction = direction.normalize();

    for(int i = 0; i < 8; ++i)
    {
        float dotValue = m_vDirectionArray[i].dot(direction);
        if(dotValue > maxValue)
        {
            maxValue = dotValue;
            idx = i;
        }
    }
    m_vMoveDirection = m_vDirectionArray[idx];
}

```

Then I am thinking 8-directional AI movement is pretty common in old nes game, like "Nintendo World Cup". Does anyone used to meet this problem or have any articles related to this?

UPDATE: I have update the code in @Json advice, but still got the errors I met before.
1.Actually player will change direction in 22.5 degree not 45 degree. I need player move on the diagonals when the degree is just reach 45.
2.When player move on the diagonals, the player will keep shaking. For example, in situation 1, when player start to move from C to B in first frame, player decide to move in perfect 45 degree, but player can not reach precise point C because "distance from A to C" has small error to "player speed(constant) * move time from A to C" , this will cause next frame player probably run in horizontal direction, again and again..
Do I need to check when the last frame that arrive at C, then just make player at the precise point C manually to avoid this error, or there has any other trick to fix this?

# Answer
> 1 votes
Angles are almost **always** a poor way to handle such situations. You already have vectors, which are *perfect* representations of directions. Just take the eight unit directions (normalized \<1,0\>, \<1,1\>, \<0,1\>, \<-1,1\> etc.), form the dot product with your desired direction, and then take the vector with the largest value. This assumes your characters move the same speed in every direction. If they move faster on the diagonals, just don't normalize the directions.

Basically, this procedure works by making your character move in the direction which most quickly minimizes the distance to the goal.

Be sure to have your character only do things if they aren't already at their destination! This code won't work as intended:

```
 if(!direction.IsZero())
        direction.normalize();
 float radians = direction.getAngleToXAxis();

```

If the direction is zero, then getAngleToXAxis doesn't make any sense, and should throw an exception. If the direction is the zero vector, you are at your destination, and the rest of the logic can be skipped. Don't just blindly avoid normalizing a zero vector. A zero vector going into a normalization usually has some special interpretation, which in this case is "you have arrived at your destination."

**EDIT:** So the original problem is a little more complicated. Basically you are going to need to add a little bit of state to your character. I'm going to describe the simplest way I can think of, but it is a little hack-y because what you want is non-optimal pathfinding behavior.

State: last direction player moved in (E,N,W,NE, etc.), corresponding to one of the eight directions, or NONE if they weren't moving last frame. To decide which way to go:

1. If at destination: stop, set direction to NONE (you might use a boolean flag for this, NONE is conceptual).
2. If last time you moved N,S,E, or W, find the closest *just* out of those four (so use the dot-product trick, but only with \<0,1\>, \<1,0\>, \<-1,0\>, and \<0,-1\>). If it matches what you did last time, then keep doing that. Otherwise, go to 4.
3. Similarly, if last time you did NE, SE, NW, or SW, find the closest from those, and keep doing it if it is still good. Otherwise go to 4.
4. Pick the best direction, as above. Set the last frame direction to this direction, and return it.

Here is a demo of this technique (click to set a new destination):
http://jsfiddle.net/9cLy3/embedded/result/
This is an example of *hysteresis*.

# Answer
> 2 votes
```
        if (degrees < 45 && degrees > -45)          direction = vector(1.0, 0.0);
        else if (degrees == 45.f)                   direction = vector(1.0, 1.0);
        else if (degrees > 45 && degrees < 135)     direction = vector(0.0, 1.0);
        else if (degrees == 135.f)                  direction = vector(-1.0, 1.0);
        else if (degrees > 135 || degrees < -135)   direction = vector(-1.0, 0.0);
        else if (degrees == -135.f )                direction = vector(-1.0, -1.0);
        else if (degrees > -135 && degrees < -45)   direction = vector(0.0, -1.0);
        else if (degrees == -45.f)                  direction = vector(1.0, -1.0);

```

This logic seems to be a little off, for example you are only assigning `vector(1.0,1.0)` if the angle is exactly equal to 45.0f when really it should represent a range of one eighth of a circle.

I would use the following to convert any given angle in radians to 8-way movement:

```
float factor =  (2.0f * pi) / 8.0f;  // or 360.0f/8.0f if using degrees
float newAngle = round(oldAngle / factor) * factor;

```

Once you have `newAngle` perform a mathematically correct conversion to a vector without any need for further manipulation. This example assumes newAngle is in the correct units for the trigonometric functions:

```
direction = vector(sin(newAngle), cos(newAngle));

```

Note: this last line will produce a unit vector (i.e. of length one), you may need to handle thing a bit differently if you want the diagonals to be of length sqrt(2) like the code you posted with your question.

**Edit:** I can see two approaches to address the issue of switching directions on each frame and approximating 16-direction movement.

*BlackList:* If each time a player changes direction we disable or blacklist the direction they were taking before that turn, this would rule out that issue, and instead result an a high degree of over steering. This might be acceptable if the target was stationary but is unlikely to look natural if the target moves into the direction we have blocked, and players would learn to take advantage of this.

```
//
int currentDirection = -999;     // the direction taken last frame
int previousDirection = -999;    // the direction taken before the last turn
//

float factor =  (2.0f * pi) / 8.0f;  // or 360.0f/8.0f if using degrees
float idealDirection = oldAngle / factor;
int newDirection = round(idealDirection);
if (newDirection != currentDirection) {
    if (newDirection == previousDirection) {
        if (idealDirection > newDirection) {
            newDirection++;
        }
        else {
            newDirection--;
        }
    if (newDirection != currentDirection) {
        previousDirection = currentDirection;
        currentDirection = newDirection;
    }
}
float newAngle = newDirection * factor;

```

*Bias:* If we set a bias towards heading in the current direction and only switch direction when a new direction is *much* more desirable we should have a more natural result. This will have an about of back and forth between headings abut the bias can be tuned to reach the desired result.

```
//
int currentDirection = -999;     // the direction taken last frame
float bias =  2.0;               // how much better should the new direction be
//

float factor =  (2.0f * pi) / 8.0f;  // or 360.0f/8.0f if using degrees
float idealDirection = oldAngle / factor;
int newDirection = round(idealDirection);
if (newDirection != currentDirection) {
    float distanceFromCurrent = abs(currentDirection - idealDirection);
    float distanceFromNew = abs(newDirection - idealDirection);
    if (distanceFromCurrent > (distanceFromNew * bias)) {
        currentDirection = newDirection;   // switch to new direction
    }
    else {
      newDirection = currentDirection;     // stick to the established heading
   }
}
float newAngle = newDirection * factor;

```

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


title: Starting with shaders and particles

text:
# Question
Title: Starting with shaders and particles
I'm working on a flow field with particle systems and starting to learn about shaders in three.js.

Current state of my work is available here.

As such amount of calculations is quite heavy for a big amount of particles I am wondering is it possible to move it to the vertex shader? (Im just a beginner, no experience with shaders, only what i've read, so please be patient)

The calculations requires previous position to add further displacement and to move the particle further according to the noise value on given position, but i don't think it is possible to output anything from the shader?

# Answer
> 5 votes
You are right, a GPU can do upwards of millions of points at interactive framerates, but no, unfortunately there isn't a way to do this *directly* in WebGL (which is what three.js is based on). In full OpenGL/DirectX, there is something called transform feedback which does exactly what you want, but it isn't available in WebGL.

However, all hope is not lost. Before transform feedback, people made particle systems on the graphics card using render-to-texture. The idea is that you do the normal render step, but instead of given the positions of the particles in vertex arrays, you store it in textures. For example, you could store the X position in the red channel, the Y position in green, the hue in blue, and the size in alpha.

Each frame, you render to another texture with a fragment (pixel) shader which computes the new position, size/etc. Then you switch back to drawing to the screen and use the positions from this texture to draw the particles themselves. Finally, you make the "new positions texture" the positions texture, and the old positions texture becomes the new positions texture for the next frame. Basically, there **is** a way to output something from a shader -- a pixel shader, that is.

This is a complicated system though. I would recommend learning about shaders in general (and particularly about the ways to do texture access and render to texture) before attempting this.

---
Tags: shaders, particles, perlin-noise, three.js
---


# Question
Title: Canvas setTransform function clarification
I'm currently building some kind of fake-3D dungeon, and I'm facing some difficulties understanding the behavior of the setTransform() function.

Here's my simplified code:

```
var can = document.getElementById('c'),
    ctx = can.getContext('2d'),
    angle = Math.PI / 4;

ctx.fillStyle = "grey";

ctx.setTransform(1, Math.tan(angle), 0, 1, 0, 0);
ctx.fillRect(100, 0, 50, 50);

```

Here's also s JsBin with the same code for you to see the result: http://jsbin.com/oxaSIpe/7/edit

Changing the x coordinate in the `fillRect` seems to also affect the y coordinate. It makes no sense. Skewing an element changes its position? No documentation mentions anything like that.

If anyone could please try to explain this function and its weird behavior, I would be very grateful.

# Answer
`setTrasnform(a, b, c, d, e, f)` has six parameters:

* a Scales the drawings horizontally
* b Skew the the drawings horizontally
* c Skew the the drawings vertically
* d Scales the drawings vertically
* e Moves the the drawings horizontally
* f Moves the the drawings vertically

It scales and skews the whole canvas. Imagine you are drawing on the canvas that is not skewed. It is skewed (transformed) only just before it is printed to the screen. See the following diagram:

The whole canvas is skewed. I added four squares to the red rectangle. The skew causes the Y shift.

Here's the code:

```
var game = function() {
    var can = document.getElementById('c'),
        ctx = can.getContext('2d');

    ctx.fillStyle = "red";
    ctx.setTransform(1, 0.2, 0, 1, 0, 0);
    ctx.fillRect(20, 20, 250, 150);

    ctx.fillStyle = "blue";
    ctx.fillRect(30, 30, 20, 20);
    ctx.fillRect(60, 30, 20, 20);
    ctx.fillRect(90, 30, 20, 20);
    ctx.fillRect(120, 30, 20, 20);
};

game();

```

---

Philipp's answer is correct and it does answer your question. But maybe it's hard for you to digest. Use my example and add more small squares with different transforms to get a better idea of the setTransform.
> 5 votes

# Answer
The `context.setTransform` function (as well as all the convenience projection-functions like `scale` or `rotate`) works by changing the coordinate-system of the canvas. So yes, changing the transformation to a skewed projection changes the position of everything you draw. It doesn't just affect *how* you draw, it also affects *where* you draw.
> 1 votes

# Answer
Set transform sets the whole transform at once, which means if you want to specify where the rectangle ends up in screen coordinates, then you need to modify the translation component to compensate for the scale and skewing. In some sense, these are applied "first," which is just the convention used by most drawing APIs. Or you could just do:

```
ctx.translate(23,40);
ctx.transform(1, 1/2, 0, 1, 0, 0);

ctx.fillRect(0, 0, 50, 50);
ctx.rect(-10,-10,20,20);
ctx.stroke();

```

http://jsbin.com/oxaSIpe/11/edit

Now the translate part controls where the top left corner of the square goes, with an extra box to show where the origin is of this new space. You can modify the translate line to put it anywhere in screen space.

Note that most isometric games use 2-1 slope for the lines, or about 26.5 degrees, which I have done here. "True" isometric is 30 degrees, not 45.
> 0 votes

---
Tags: javascript, html5, html-canvas
---


# Question
Title: How does pixel shading work for ambient occlusion volumes?
I'm trying to understand the ambient occlusion technique described here, but I've trouble comprehending what exactly is the pixel shader doing.

Is the pixel shader invoked on points that belong to the surfaces of occlusion volumes? Can anyone explain on a simple scene (like a cube corner seen from inside) how pixels get their AO values?

# Answer
> 1 votes
Here's how the algorithm works:

We want to calculate the "occlusion" at each visible point in the scene, which represents the portion of the hemisphere aligned with the normal at that point that doesn't have geometry to close in that direction, as this is an approximation of the amount of light we would get from the "sky", or more generally the rest of the scene. The real answer is to take an integral over this hemisphere, but this is *way* too slow for realtime.

Instead, we accumulate the "occlusion" generated by all of the nearby polygons. First, we initialize a buffer to 1, representing no occlusion. We subtract off of this every time we find an occluder. To find what can occlude each pixel, we take every polygon in the scene, extrude it into a volume on one side, and then send that to the rasterizer. What this does is generate a fragment for every scene point (pixel in our buffer) which could possibly be affected by the polygon we are processing. So now our fragment shader knows the position in the scene and normal (from reading the depth buffer/normal buffer) for the point we are calculating AO for, and the details of the polygon (triangle, if you like). So the fragment shader knows all three points of the triangle, not just it's own position.

Now it is just a simple matter to calculate the weighted area of the hemisphere around the pixel that the triangle blocks. We weight it because light coming in from near the normal illuminates the point more than light coming it at an extreme angle, due to the cosine term. We then take this off of the total occlusion using subtractive blending.

In your example, first we would draw the three planes that made up the cube corner, to get a depth/normal buffer. Then we extrude each of these polygons inward. What happens is the points that are far from the other two planes only get touched by their own plane, which gets rejected. The points along the edges have two polygons affect them. Again their own polygon doesn't have any affect, but this time some of the other plane intersects their hemisphere. The closer it is to the edge, the more of the hemisphere is blocked, and the darker the occlusion is. In the corner, each pixel has two non-degenerate polygons, and so they get even darker as more occlusion is subtracted.

Of course, one limitation is that two polygons which both block the same part of the hemisphere will both be counted separately, as the only thing that is tracked between polygons is the total occlusion removed. Without storing something like a mini-cubemap, there would not really be any way to prevent this -- this is a fundamental limitation of this technique. In particular, if you just rendered the same model twice during the "extrude and accumulate" phase, models that were nearby would get twice the occlusion, and be two times darker! Of course, a more realistic scenario is small, thin, repeated geometry, which is probably rare enough to make this a good technique.

---
Tags: lighting, occlusion
---


title: Add vertices to "middle" of VBO

text:
# Question
Title: Add vertices to "middle" of VBO
I've been playing around with VBOs as of late (mostly because my game necessitates it), and I've found the need to add new vertices to a VBO, but not necessarily at the end. The game in question is a Terraria port, and when a player updates the world, the VBO needs to be updated. Up until now, I've been using glBufferData() to update the array, but it's time I switch to glBufferSubdata() or glMapBuffer() I'd like to be able to update a certain "chunk" of the world when a block in it is modified, but this could potentially result in adding more or less vertices than are already in the appropriate memory section. If a player places a "block," more memory would need to be allocated, resulting in any proceeding vertices being shifted over x indices. My only thought would be to allocate enough memory for each chunk to be completely filled with blocks, but I haven't yet found a way to do that. Would anyone be able to point me in the right direction?

EDIT: To clarify, pushing new VBO data to the graphics card (which is what causes the lag spike) takes 11-12ms the first couple of times, and 1-4 every time after. This also raises the question: why does the graphics card seemingly need to be "broken in?" In other words, why is there such a huge delay at first?

# Answer
> 2 votes
You can gain efficiency by doing two things:

1. Localizing updates. Only update a small part of the buffer to add or remove objects. Let's assume each object takes up a constant amount of space, say 96 bytes. To delete a object (tile), we issue a 96 byte upload via `glBufferSubData` to replace the deleted object with the data for the *last* object in the buffer. Then we make sure we render one less object of geometry. The effect is that the last object is still rendered once, but now in the dead space at the end of the buffer we have a second copy. To add and object, we update the buffer with another 96 bytes at the end, and render one more object's worth of geometry. If we run out of room, we allocate a new VBO and stick it in there. Thus each "chunk" can have multiple VBO's, if it is really full. Nothing has to be sorted in your VBO's, even if it is in client memory. You just need to keep track of which index each tile went into in order to know where to put each thing. In any case, uploading a Terraria's game worth of changes should not be a problem at all. This technique required 96\*n bytes to be transferred per addition/deletion.
2. Delaying updates. Issuing something and having it happen the next frame is a good way to get lots of performance. Rather than deleting the object from the VBO, rendering, and then swapping buffers, consider rendering, deleting, and then swapping. This way the graphics card gets to use the old data to render the frame, and can transfer the data over the bus while you are waiting to vsync. You'll lag by one frame this way, but it is the most efficient way to transfer data to the graphics card. If you want to get *really* clever, then you can issue two draw calls which render everything before and after the removed block, which doesn't touch the buffer, then remove it for the next frame. On adds, keep around a small VBO which you can push one object to and render without doing an allocation. The key is to not try to modify a buffer which the graphics card may be still using. There are many ways to accomplish this, and many ways to fail to do so in subtle ways.

---
Tags: java, lwjgl, vbo
---


# Question
Title: Dynamic "Light Level" System based on alpha levels
My team and I have been working on a game in Java using the Slick2D engine and there are a few things I have questions on. As of right now, the code that I've written basically takes a cosine function and gets a value based on the current game time (which is normalized by some multiple of Pi, like 4\*Pi, to give us a period (or day length) of 4\*Pi). The value that comes out of the function is used directly as the alpha level of the overlaying light layer so that as the night comes on, the screen darkens until it's completely opaque, then eventually comes back to completely transparent. I've also created a mask around the player, which disallows the alpha level from drawing near the player.

Now, this looks cool and all, but if I want to draw different alpha levels around *that*, some that may even be non-existent until it begins to get dark like an average alpha transition that goes from the 100% transparent alpha near the player to the 100% opaque alpha outside that mask during the pitch black of night, I run into issues. Screenshot

Basically, Slick provides some tools, like static values in the Graphics class that change the draw mode. Examples are: MODE\_ADD, MODE\_ADD\_ALPHA, etc. I'm wondering if there's a particularly good rundown on using these to get results where I have alpha levels that will vary between the current overall alpha level and the 100% transparency so I can create clean transitions so it doesn't have that clean cutoff seen in the screenshot.

Or should I scratch this and go with a grid/cell based system since the game's tile based when it comes to drawing the background layers, save for the entities. Might make a bit more sense and look a little more natural with the backgrounds, although still look a tad unnatural.

EDIT: I'd also be open to other paradigms.

# Answer
> 2 votes
Use MODE\_COLOR\_MULTIPLY, but without alpha. You are going to end by drawing an image (RGB, but no alpha) over the screen using multiply.

Construct this image (NOT using multiply mode, but normal blending) by drawing pure white during the day, pure black during the night, and a gray color during twilight, as you have done. Then, around the player's location, draw a smooth falloff image using additive blending mode. This falloff image does not have an alpha channel, and is black around the edges and white in the middle. Here is the important part: the image you are drawing to does not have an alpha channel. This is because you are encoding the light level into the actual image, not the alpha channel. As a bonus, you can support colored lights. By using additive blending, you could add lights for other characters, or the environment (but be careful of making any of them too bright).

Once this image is prepared, draw it over the screen using MULTIPLY. This works because light is fundamentally object\_color * incoming\_light. Basically, what is already on the screen is object\_color, and you are calculating an image which represents the incoming\_light based on the time of day and where the character is. Even though your game is pixel-art based and 2D, does not mean it can't have cool lighting!

(Hint: you can make it colored, redish-orange at sunset, blue-purple at dusk/night, yellow at sunrise, pale-white during a full moon, and light blue in the morning for a really cool effect. Play with the colors to fit your art style. Just vary the color of the rectangle you draw over the scene; there is no reason it must be white, gray, or black.)

(Hint #2: When drawing the player's light, disable it completely during the day, then have it fade in quickly sometime during the evening, and tint it orange to simulate a lantern (it would make sense to have the character hold one during this time).)

---
Tags: java, lighting, slick
---


title: Generating mipmaps for volume texture

text:
# Question
Title: Generating mipmaps for volume texture
Does texconv from DirectxTex support generating mipmaps for volume textures? If not what are the other alternatives?

I am asking because I have tried to create the mipmaps by using textconv.exe -m 3 my.dds, but it looks like this (I am viewing it in the DDS plugin for photoshop):

And now I wonder whether the DDS plugin is bugged that it displays only mipmap for first texture or the texconv doesn't support it?

EDIT: Acutally by taking a deeper look on this image, the mipmap is somehow blended from these 2 main textures. Why? (high resolution texture here)

# Answer
> 4 votes
Simple answer: the tool is right, this is proper behavior for a volume texture.

Long answer: A volume texture is a 3D-texture in which mipmaps shrink in all three dimensions. So if you have a 16\*16\*16 texture, the next miplevel is 8\*8\*8, and then 4\*4\*4, etc, down to 1\*1\*1. If the dimensions aren't the same, then you still have each one (this is the same rule as for 2D textures). So 16\*4\*8 would have mips 8\*2\*4, 4\*1\*2, 2\*1\*1, and 1\*1\*1. You have something like 128\*128\*2, so the next miplevel is 64\*64\*1. Basically, there is only one 2D slice left to put the data, so it is a blend of the two.

This is like storing a pair of 1D lookup tables in a 64\*2 2D texture. The next mipmap is 32\*1, and so it can no longer distinguish between the two tables, and it is an average of the two.

What you want is a **2D texture array**, for which the mipmaps for different layers are totally separate. If you have 6 layers in a 2D texture array, then you will have 6 1x1 images at the smallest miplevel, all guaranteed not to filter across layers. It looks like support for texture arrays in .dds files is spotty at best. You might have to upload the data manually from a bunch of separate .dds files.

---
Tags: textures
---


# Question
Title: Does client side prediction sync with the server in the past?
I've spent some time now messing around and just trying to learn dead reckoning and client side prediction for the fun of it. Most of what I do doesn't need it, so i've never had a need to go down the path.

I get how to predict the client and i've got a completely deterministic setup with a lockstep of 60fps for the physics on client and server. Both client and server use the same movement code, and i'm using constant velocity to reduce complexity. I also understand how to interpolate for corrections. I also have the server and client ticking at nearly the same time (as close as one can really get it).

The problem i'm having, that doesn't seem clear to me in anything I've read (i'll put links at the end to a few things), is what does the client message sync against on the server? So, for example, the client is at 0, 0, 0, with a heading of 0, 0, 1 at tick 0. At tick 5 the client presses the button to start moving forward at 40u/s and sends the message to the server. We'll say that the trip to the server takes 50ms and 50ms back. So the server gets the message at tick 8 (roughly), and here is where I am slightly lost.

The client sent the tick they pressed the button along with the position and new velocity. Does the server do:

* A. Look back at tick 5 and say "you're good b/c you were where you should be at that tick"
* B. Check against tick 8 and say "well you where at 0, 0, 0 at tick 8, so you didn't start moving until then".

It would seem with B, which is what i'm currently doing, that the server is always sending back a correction. B also has a bad side affect that when I stop, I'm almost never where the server is and the interpolation of this feels impossible to get right.

While with A, it would seem I have to redo all collisions for that object from tick 5 thru 8 on the server, but this sends less corrections and would give a smoother feel. I understand that A is used for lag compensation when firing a weapon or taking some action that would affect other entities, but is that also used for motion?

Things I've read: http://gafferongames.com/ http://www.gabrielgambetta.com/fpm1.html Various articles out of books and other websites that seem to skip past this detail

Thanks in advance for any help.

# Answer
> 5 votes
That's "server reconciliation", I've written specifically about it here: http://www.gabrielgambetta.com/fpm2.html Since you link to one of these articles in your question, I assume you've read it already. Believe me, the answer is there :)

It's more like your option "A". Typically what happens is that you get a server update for a "true" state of the world sometime in the past. It will generally match what you had predicted for that instant in time, unless you ran into another player or something.

The key here is to predict the current state again by interpolating from whatever the server was the true state *and the inputs the server hasn't seen yet*. If both the client and the server agree on what happened at `T - dT` (and they *must* since the server is authoritative), and then apply the same inputs again (the server is already processing them, and the client keeps them until a future server update has a timestamp in the future respect to when the input ended), they *must* end up with identical states.

In my article, this is explained with pretty diagrams; the problem is stated in **Synchronization issues**, and the solution (which I outlined above) in **Server reconciliation**. Let me know if you still have doubts :)

---
Tags: physics, networking, client-server, simulations, fixed-timestep
---


title: Mesh with quads to triangle mesh

text:
# Question
Title: Mesh with quads to triangle mesh
I want to use Blender for making models yet realize some of the polygons are not triangles but contain quads or more (example: cylinder top and bottom).

I could export the the mesh as a basic mesh file and import it in to an openGL application and workout rendering the quads as tris, but anything with more than 4 vert indices is beyond me.

Is it typical to convert the mesh to a triangle-based mesh inside blender before exporting it? I actually tried this through the `quads_convert_to_tris` method within a blender py script and the top of the cylinder does not look symmetrical. What is typically done to render a loaded mesh as a tri?

# Answer
> 8 votes
Yes, it's typical to convert into triangles. When reading the mesh in, it's simple to convert a quad into a triangle. It will depend on the format you're exporting to. For example, the format I use, Blender will export all the vertices, then it will export index information for triangles and quads. So it's a simple matter of arranging the indices to take a quad and create two triangles.

```
if (indexCount == 3) { //triangle face
    int one = readNextIndex();
    int two = readNextIndex();
    int three = readNextIndex();
    indicies.add(one);
    indicies.add(two);
    indicies.add(three);

} else if (indexCount == 4) { //quad face
    int one = readNextIndex();
    int two = readNextIndex();
    int three = readNextIndex();
    int four = readNextIndex();

    indicies.add(one);
    indicies.add(two);
    indicies.add(three);

    indicies.add(three);
    indicies.add(four);
    indicies.add(one);
}

```

Where the index information looks like:

```
//NumberOfElements;Element1;...;ElementN;,
4;40;41;42;43;,
3;44;45;46;,

```

Alternatively, using Blender:

1. Go into Edit Mode
2. Press A to select all
3. Press Ctrl+T to convert Quads to Triangles
4. Re-export mesh with triangles

# Answer
> 5 votes
If you want to permanently change quads to tris in Blender use Ctrl+T in Edit-Mode

# Answer
> 2 votes
In your export script, you can ask for tessellated data so that you only have to deal with triangles and quads. Turning a quad into two triangles is trivial (as Byte56 has already answered).

```
ob = bpy.context.active_object
me = ob.data
me.calc_tessface()
for v in me.vertices:
    print("v", v.co.x, v.co.y, v.co.z)
for f in me.tessfaces:
    if len(f.vertices) == 3:
        print("f", f.vertices[0], f.vertices[1], f.vertices[2])
    else:
        print("f", f.vertices[0], f.vertices[1], f.vertices[2])
        print("f", f.vertices[0], f.vertices[2], f.vertices[3])

```

Another option (if you're not writing your own exporter) is to add a "Triangulate" modifier (new in Blender 2.6) to your mesh; with the "Beauty Subdivide" option it will always pick the shorter of the two choices for where to split quads.

---
Tags: opengl-es2, blender
---


title: Angular velocity from 2D Collision

text:
# Question
Title: Angular velocity from 2D Collision
I have been working on a 2D physics engine for my A Level computing project and I am having trouble calculating the angular velocity from a collision. I have managed to workout each objects linear velocity and create a collision manifold containing the collision points relative to each of the 2 objects involved in to collisions centre of mass (0, 0) along with the overlap etc. I also know each objects mass, speed etc. I have been looking for a couple weeks now at every equation I can find and non of them seem to work returning incredibly high numbers for normal collisions. My current algorithm pulled from an article in the game development section on tuts+ (linked here) is like so:

```
objectArray[i].angularVelocity += objectArray[i].inverseMass * CrossProduct(collisionInfo.collisionPointB, impulse);
objectArray[ii].angularVelocity += objectArray[ii].inverseMass * CrossProduct(collisionInfo.collisionPointA, impulse);

```

Could someone please explain how I can calculate the change in angular velocity and give me some example values for the equations as mine are probably in the wrong scale or something.

Thank you for any help, Andy A

Other things to note, this engine is written in C# for XNA so if there are any language specific optimisations they have to work with C#, thank you.

# Answer
I was struggling on the same question so I looked after some clue on physics.stackexchange

this post about the collision theory was very helpful. Code snippets inside.

If you are looking for something more complete, then take a look at this wikipedia page about the impulse based reaction model which contains some interesting infromation about angular velocity that may sound a littlebit complicated. But if in your model you make use of inertia and impulse concepts this may be resolutive.

For my personal purpose I took advantage of calculations expressed in the first link to get impulse value and then used a formula like

```
Va = (V * sin(angle))/r

```

given

* `V` = your particle velocity
* `angle` = angle between `V` and `r`
* `r` = distance from rotation axis
> 1 votes

---
Tags: xna-4.0, algorithm
---


# Question
Title: How can I convert a Tiled level array to a 2D array?
For the code in my game, I want a 2D array which represents the map.

I created an actual map with Tiled but it produces a 1D array. Is there any way to convert it into my desired format wothout manually adding brackets and commas after each line?

# Answer
> 3 votes
You can always index a 1D array with 2D semantics. Given the `x` and `y` you'd like to look up, if you know the `width` of the "2D" interpretation of the array, use the following indexing math:

```
var tile = array[y * width + x]

```

This will save you the hassle of converting.

If you must convert, and Tiled does not offer an option to export in the format you want, your best bet is to write a function to do it. This would look roughly like (in pseudo-code):

```
var result = new array[width][height];
for (var row = 0; row < height; ++row) {
  for (var column = 0; column < width; ++column) {
    result[column][row] = tiledLevelArray[row * width + column]
  }
}

```

Run your level through a function like this at initialization time; this way you do not have to manually fix up the Tiled-generated array every time you'd like to change it.

---
Tags: javascript, tilemap
---


# Question
Title: How can I support many point light sources in a dynamically-generated level in Unity?
I'm currently working with a dungeon game which is similar to Dungeon Keeper by Mythic Entertainment. I'm using Unity and developing this game for Ipad 2 and above. Player can modify his dungeon, and I'd written a dungeon generator which creates it. In this case, I can't use lightmaps, because the dungeon has been created dynamically and player can tweak it. I also devised a way to combine separate game objects in a single mesh, so imagine that the entire dungeon (except special objects such as pillars, statues and mobs) is the single mesh. There's many point light sources (10-15 and above) on the stage, but Unity don't allow to use more than 8 light sources per object.

So, if all dungeon cells are separated objects, I can use the diffuse or even vertex-lit lighting, but if the entire dungeon is a single mesh, there's the hardware limit appears.

Ways to solve this problem I'd divised:

* Use separated geometry **(tried)** \- bad, because it harms berformance because there's many-many-many drawcalls (16-17 fps on Ipad 4).
* Use deffered shading **(tried)** \- bad, because it harms performance even more than separated geometry.
* Use a custom shader **(haven't tried)** \- I don't know how.
* Don't unite all cells in the single mesh but unite groups of cells to reduce the number of separated objects **(haven't tried)**
* Use the light manager **(haven't tried)** \- I don't know how.
* ???

How can I deal with it?

# Answer
This would probably best be solved with a Scene Manager. Specifically a quad-tree. Which will probably require a little bit of scripting, but it'll help a lot.

A scene manager solves the problem of dividing the mesh, the problem being that there are too many draw calls. So what you do, is you divide the scene into small parts, and then only render the parts that are on screen. So since the rest of the scene isn't rendered, you have less draw-calls. You should be able to change what is rendered and not rendered by disabling the mesh renderer.

That's how I would do it anyway. Though I'm not very experienced with Unity3D, so the above answer is just generic game-dev theory.
> 1 votes

# Answer
Deferred lighting should be the ideal option here, along with perhaps better partitioning in your scene handling code (culling out objects that are far enough outside the view frame that they cannot impact the scene; this can be done with quad- or oct- trees for example

Deferring shading is a multi-pass technique that involves first "rendering" data for use in eventual shading computation into render targets, and then sampling from those render targets in a later pass to produce a final scene.

One of the particular advantages deferred shading offers is the ability to have an extremely high number of light sources, because the light source information is rendered into the early-pass targets exactly as you would render geometry; the cost per light is roughly akin to the cost of rendering a screen-space quad. The disadvantage is that it does not naturally support transparent objects, and if you need those, you need to apply additional techniques or render them in a non-deferred way.

Unity has a deferred rendering path you can look into.

I am suspicious of your claims that you tried and discarded the deferred approach because it was too performance intensive. iPad 2's aren't the best hardware these days, so you might have problems there, but the 4th generation iPad's should handle a well-constructed deferred renderer fairly well. I suspect that somewhere there is a bug or potential optimization in your implementation, and it may be worth posting a new question to explore that.
> 1 votes

---
Tags: unity, shaders, lighting
---


# Question
Title: How can I read texel data on a separate thread in D3D11?
In D3D10, I load a staging texture onto my GPU memory, then map it in order to access its texel data on the CPU. This is done on a separate thread, not the thread I render with. I just call the device methods, and it works.

In D3D11 I load the staging texture onto my GPU, but to access it (i.e. Map it) I need to use the Context, not the device. Can't use the immediate context, since the immediate context can only be used by a single thread at a time. But I also can't use a deferred context to Read from the texture to the CPU:

"If you call Map on a deferred context, you can only pass D3D11\_MAP\_WRITE\_DISCARD, D3D11\_MAP\_WRITE\_NO\_OVERWRITE, or both to the MapType parameter. Other D3D11\_MAP-typed values are not supported for a deferred context."

http://msdn.microsoft.com/en-us/library/ff476457.aspx

Ok, so what am I supposed to do now? It is common to use textures to store certain data (heightmaps for instance) and you obviously have to be able to access that data for it to be useful. Is there no way for me to do this in a separate thread with D3D11?

# Answer
Once a texture is mapped to the CPU, its texel data is in CPU-accessible memory, which can be read by all threads, including your worker thread.

Thus, you should map the resource in your main thread using your immediate context, and then perform all your reads and assorted dependent work (which is generally where the real need for a worker thread would be) on a worker thread, setting some state or signal to notify the main thread when the worker is complete and the main thread can unmap the resource.

If map stall time (on the main thread) is an issue as well, consider the `D3D11_MAP_FLAG_DO_NOT_WAIT` flag (make sure to check if `DXGI_ERROR_WAS_STILL_DRAWING` is returned and then do something else if so).

To make the best use of this scenario, you're likely going to want to move as many post-read operations to the worker thread as you can (to load it), and also make sure you have other things the main thread can do if the resource is not mappable at the time (perhaps move on to another resource, for example) to make sure it stays loaded, otherwise there wasn't much point in multithreading the work.
> 3 votes

---
Tags: directx11, multithreading
---


# Question
Title: Should I use object references or integral values to store pieces in a chess board?
just a general question regarding a checkers project. I built a class hierarchy for the game pieces (that could be extended for chess etc). The hierarchy looks something like

```
interface GamePiece() {...}
class EmptySquare implements GamePiece {...}
class Pawn implements GamePiece extends EmptySquare {...}
class Queen implements GamePiece extends EmptySquare {...}

```

I store an object reference in the `board[][]` array. In the tree search that array is cloned for each recursion (not with `doMove()` ... call recursion ... `undoMove()`). I store object refs for the game pieces so I can do something like this for generating the list of moves:

```
for(sq:Squares)
    sq.getPossibleMoves()
    possibleMoves.addAll(sq.possibleMoves)

```

I'm not sure how much space this array of references takes up and if that is any good way to it from a performance point of view. It works nicely logically though. Would you do it like that or sacrifice the nicer code for a more compact game board array and the use `switch()` to call subroutines for each piece to make the move list?

# Answer
Most modern chess engines use redundant methods of storing the board. For example, my own engine uses bitboards (64-bit integer for each possible piece type - see http://chessprogramming.wikispaces.com/Bitboards) as the primary board representation, but also makes use of a one-dimensional array of integers. In this array, empty squares are represented by 0, while the white pieces are represented by integers 1 through 6 for pawn, knight, bishop, rook, queen and king. Black pieces are the white pieces multiplied by -1, so the white pawn is 1, black bishop is -3 and so on.

This redundant representation comes at a cost when making moves, as there is more to update, but it pays off elsewhere in the program. For example, we can easily answer questions such as "what piece is on f4?" (array) or "which black pawns are attacking white pieces?" (bitboards).

To more directly answer the question - go with the array and switch statement if you're looking for pure performance, which is the case for most chess engine authors. At an early stage of developing my engine, I used a similar inheritance scheme, with a Piece interface implemented by classes like WhitePawn and Bishop. This worked fine, but was awfully slow, and I eventually went through the effort of replacing the scheme with the integer array, and eventually adding the bitboards. There is a lot of messy code involved behind the scenes, but it's all abstracted away neatly enough and the benefits are many.

I highly recommend reading articles that take your interest on the chess programming wiki (http://chessprogramming.wikispaces.com/), as I found it to be an invaluable resource in every phase of development. Many concepts are also directly applicable to other board games, especially checkers!
> 1 votes

# Answer
Here's how I would move pieces around:

```
private void playChess() {

    Board board = new Board();
    board.makeSquares();
    System.out.println(board);
    Square startingSquare = board.getSquare(3, 1);  //   0<=x<=7, 0<=y<=7  (file, rank)
    Square endingSquare = board.getSquare(3, 4);  //illegal move
    ChessPiece pawn = startingSquare.getPiece();  //assumes a pawn is at that square...
    System.out.println(pawn.toString());
    try {
        board.movePiece(startingSquare, endingSquare);
    } catch (IllegalMove ex) {
        System.out.println(ex);  //pawns can only move two spaces, so it's an illegal move
    }
    System.out.println(board);
}

```

The important thing is to only allow the board to move pieces, I think, but have the logic for movement into the pieces. The knight would be the most difficult, followed by the pawn (because the pawn can move twice at first, and en passant). I would have the pawn throw an error to the square, and then to the board, to catch the illegal move in the driver.

Some code:

https://github.com/THUFIR/StackOverflow/tree/0001chess\_boar
> 0 votes

# Answer
It depends on what you want to do.

Do you have an AI or not? If not, then it hardly matters. About all modern devices have more than enough memory to handle 32 pieces on 64 fields, no matter how you represent them. Here you should make the code the way it looks/feels best for you.

If you do have an AI that you want to do quite good then you will need the most effective data structure behind the whole thing. It doesn't matter so much whether you use referenced objects or an int as ID but it matters much more what kind of data structure you are using.

I would probably use multiple data structures in combination. On the one hand you need to be able to do a quick look-up if a field is occupied and what unit occupies it. For this it is best to use a 2D-array. On the other hand you need a data structure where you only have the units of each player in it, so you don't have to iterate over all 64 fields just to find the two remaining pieces. Here something like a linked list would do just fine.

I'd probably use reference types, just because they make programming so much easier.
> 0 votes

---
Tags: java, performance
---


title: How to move an object along a vector

text:
# Question
Title: How to move an object along a vector
Let's say I got an object `A` and object `B` in a 2D game. I create a vector leading from `A` to `B`. It's name is `AB`.

How can I make `A` move along the vector `AB` and reach `B`?

One way I was thinking of doing this, is calculate the angle between `AB` and the x axis, and then move the object every game-loop cycle in that angle, using trigonometry.

I would calculate that angle by making a new normalized vector (1,0) (the x axis), normalize `AB`, and then get the angle between them by getting their dot product and using `arccos` on it.

But is there an easier way to make an object follow the path of a vector?

**EDIT:**

In this question: Make objects follow a strict path (Xna), the way someone suggested to move an object along a vector, is like so:

```
position += direction * speed * elapsed;

```

Where:

* `position` = current position of the object.
* `direction` = a normalized vector pointing in the direction of the destination.
* `speed` = a scalar to decide how much to advance the object every cycle of the game-loop. *(Is this a 'scalar'? Am I using this word correctly?)*
* `elapsed` = what is this?

I get everything but `elapsed`. What is this? Is this necessary?

**Anyhow, is this method a good method? Would you recommend it?**

Thanks

# Answer
Yes, as the answer to the other question suggests, the best method of doing this is to move the object each frame along the directional vector according to the speed of the object. It's the fastest in terms of mathematical operations, and also is the least prone to numerical or floating point drift.

You can use either implicit (commonly used for curves or splines) or explicit integration:

```
Implicit:
    // t starts at 0
    // PA' is the current position of A
    // PA is the original position of A
    // PB is the position of B
    t += deltaTime
    PA' = PA * (1 - t) + PB * t

Explicit:
    // PA' is the current position of A
    // D is the direction vector
    // S is the speed
    PA' = PA' + (D * (S * deltaTime))

```

Caveats: Over longer periods of time, explicit Euler integration (as shown above) becomes rather inaccurate. Also, the direction vector must be normalized before use.
> 2 votes

# Answer
elapsed is time change. look at it

```
position += direction * speed * elapsed;

```

if you move at speed, say, 5m/s you don't know how to change your position, unless you know, say, 2 second elapsed. then you know change is 10 meters
> 0 votes

# Answer
Another option, which is more useful if you need to know the rotation of your object as well, is this:

```
rotation = atan2(dy, dx);
px += speed * elapsed * cos(rotation);
py += speed * elapsed * sin(rotation);

```

Where elapsed is the time since your last game loop, dy and dx are the y and x coordinates of the vector from your current position to the target destination, and px and py are your current x and y coordinates.

You should also check if the distance you need to go is less than the total amount you can move so that you don't pass your target. A method to do this is:

```
if( dx*dx + dy*dy < speed * elapsed * speed * elapsed){
    px += dx;
    py += dy;
}
else {
    calculate position with the first formula
}

```

This method saves you from having to normalize your vectors and gives you your rotation relative to the x axis in the range of -180 to +180 degrees, while using arccos will not tell you whether your angle is positive or negative.
> 0 votes

---
Tags: 2d, movement, vector, geometry
---


title: Shadow mapping with directional light?

text:
# Question
Title: Shadow mapping with directional light?
I'm doing shadow mapping in my OpenGL 4.3 deferred renderer, and I'm starting with directional lights believing it to be the easiest.

What I do not understand is how the view projection matrix is to be constructed for the shadow mapping depth pass. I mean, all I have is the lights direction, and it affects the entire scene - so how do I construct the view matrix from only the direction, and what of the projection matrix?

Thanks

# Answer
> 3 votes
Spotlight shadow maps are created by projecting the scene with a perspective frustum. This allows the light to radiate out from a single point. This perspective frustum is built using:

1. A view matrix originating from the light's position and pointing in the direction of the spotlight
2. A perspective projection matrix that encompasses the light volume

In a similar way, directional light shadow maps use an orthographic projection, so the direction of the light is uniform across the map so as to approximate a very far away light source (the sun). The frustum in this case is built unsing:

1. A view matrix where the direction is parallel to the light's direction; it usually follows the camera around
2. An orthographic projection matrix that defines the volume to be shadowed

The only tricky part of using a directional light is that it usually cannot shadow the whole scene at once. Instead, you have to use techniques such as **cascaded shadow maps** (CSM).

With CSM, you have a number of shadow volumes of different sizes that overlap so as to cover the entire viewing frustum. Ideally, they would be sized and placed so that each screen pixel maps to at least one shadow texel while minimizing overdraw.

The colored areas in this image each represent a different shadow volume. The red volume is the smallest and thus has the highest texel resolution, then green, and so on.

This page is more in-depth and should provide you with a pretty thorough understanding of the concept.

# Answer
> 0 votes
you can rotate/shear the scene so the light is vertical and build a height map and use that as the shadow map

for the shear matrix it's something like

```
[1 0 -x/z 0]
[0 1 -y/z 0]
[0 0 1    0]
[0 0 0    1]

```

---
Tags: opengl, lighting, shadow-mapping
---


# Question
Title: Is the source code of the Source Engine available?
Is the full C++ source code of the Source Engine available?

I know the SDK is available with the purchase of a Source-based game, but my goal is to find a open-sourced game engine that includes its full implementation details for learning purposes.

# Answer
No, it is not. You may obtain a source license from Valve, but Source itself is not open-source.

---

Further, it is generally a very dangerous approach to use entire existing engines as *learning material* without guidance from somebody who was heavily involved in the development of that engine.

Source code alone only tells you the *how* of particular design decisions, not the *why* behind most of those decisions which is often extremely important given that so many choices in software engineering are from among generally equally-valid options. You need context to understand why a choice is good, and if you just look at the source of some engine and parrot their techniques and idioms, you are hardly learning anything useful.

Further, just because code shipped a game doesn't make that code good (Source in particular is prone to lot of now *very* outmoded design decisions with respect to C++ and OO, for example). There are plenty of horror stories dwelling in the engine codebases of even the most successful AAA titles. And as an impressionable neophyte, how are you going to be able to tell the good code from the bad?

Be very careful using source code as a learning resource, and make sure to pair it with as much supplementary information as you can.
> 35 votes

# Answer
tl;dr: Learning how to make an engine is often as useful to game making as learning to build your own computer and operating system from scratch. If you not an expert in the field, you probably do not want to make an engine. Make a game instead, the engine part already exists. Later on if none of the engines you have access to meet the criteria for your game design, you could focus on building that specific aspect and hell it might be useful to others as well since you are creating something new and not rehashing a less robust version of something that people already invested thousands of hours in.

Long version: If you really want to learn how to write an engine, don't look at an existing engine yet. Learn instead of the parts (algorithms) that make an engine, be it rendering, physics or path finding etc. Once you gain a deep understanding of a specific aspect, you may want to check out source.

You normally do not wish to learn directly from source unless there is no superior alternative. Even experienced programmers normally would not look at the source of an entire engine to learn from it (if they can help it), they would most likely inspect a specific part of it or tweak a certain part of it. Trying to look at the source for pure learning purpose would not expose the procedure and thought process behind the engine code; That would be like tearing a building apart ti pieces in an attempt to see its insides in order to learn how to build one. While I agree with Josh's answer, I will take it another step further, you do not even learn the "How" in many senses (unless you are familiar with the field); for instance, what methodology was used by the programming team? What principles did they rely on to implement working code? What tools and techniques did they use for debugging? All these questions are sometimes more important than the code itself (for learning purposes).

If you do wish to learn from source, look for source that is well documented and has a strong community built around it. Reading (engine) code, even if you've written it yourself, is often confusing.
> 5 votes

---
Tags: open-source
---


# Question
Title: How do I make an object face the mouse position, but only on one plane?
I want a game object to turn and look towards where the mouse was clicked (in world space). It works well when considering all 3 dimensions, but I really only care for the plane formed by the `x` and `z` axis, not the `y`.

I've tried to fix this by setting the `y` of the `directionTarget` to the `y` of the object's position, but that gives weird results.

My code looks like this:

```
Quaternion rotationTarget;
    float rotationLerpProgress;
    float rotationLerpDuration = 1f;

    // Use this for initialization
    void Start ()
    {

    }

    // Update is called once per frame
    void Update ()
    {
            if (Input.GetMouseButtonDown (0)) {
                    var ray = Camera.main.ScreenPointToRay (Input.mousePosition);
                    RaycastHit rayHit;
                    if (Physics.Raycast (ray, out rayHit)) {
                            var rayHitPoint = rayHit.point;
                            var rotationDirection = transform.position - rayHitPoint;
                            rotationDirection.Normalize ();
                            //rotationDirection.y = transform.position.y;
                            rotationTarget = Quaternion.LookRotation (rotationDirection);
                            rotationLerpProgress = Time.deltaTime;
                    }
                    //targetPosition = Camera.main.ScreenToWorldPoint (Input.mousePosition);
            }

            if (rotationTarget != transform.rotation) {

                    transform.rotation = Quaternion.Lerp (transform.rotation, rotationTarget, rotationLerpProgress / rotationLerpDuration);
                    rotationLerpProgress += Time.deltaTime;

                    if (rotationLerpProgress >= rotationLerpDuration) {

                            transform.rotation = rotationTarget;
                    }

            }

    }

```

I must be missing something. How do I do this right?

# Answer
> 3 votes
I'd project the rotationDirection into the horizontal plane before you normalize it, something like...

```
var rotationDirection = transform.position - rayHitPoint;

```

**rotationDirection.y = 0;**

```
rotationDirection.Normalize ();
rotationTarget = Quaternion.LookRotation (rotationDirection);

```

Note that the order of the subtraction used to define your rotationDirection there results in a vector *from* the rayHitPoint *to* transform.position, not the other way - is that as intended?

---
Tags: 2d, 3d, unity, rotation, lerp
---


# Question
Title: Verify which bubble is connected to top using DFS
I am working on a bubble shooter game in this game i have implemented searching using `DFS` as suggested in this link, and this is working fine.

**Update**

Here is my code for DFS

```
-(void)callDfs:(int)startR:(int)startC:(int)color{

notVisitedBubblesArr = [[NSMutableArray alloc]init];

//reset visited matrix to false.
for(int i = 0; i < R; i++)
    for(int j = 0; j < C; j++)
        visited[i][j] = FALSE;

//reset count
count = 0;
isFound = NO;
bubbleBlastCount = 0;
[self dfs:startR :startC :color :false];

[self bubbleFalling];

}
-(void)dfs:(int)ro:(int)co:(int)colori:(BOOL)set{
    coundown++;
    for(int dr = -1; dr <= 1; dr++)
        for(int dc = -1; dc <= 1; dc++)
            if([self ok:ro+dr :co+dc]) // 4 neighbors
            {
                int nr = ro+dr;
                int nc = co+dc;

                if ((([[[bubbles_Arr objectAtIndex:nr] objectAtIndex:nc]   integerValue]==colori) && !visited[nr][nc])) {
visited[nr][nc] = true;
count++;
[self dfs:nr :nc :colori :set];
if(count>2)
{
// pass row and colom will start dfs
//  if (nr >= touchClum && nc >= touchROW) {
isFound = YES;
bubbleBlastCount++;
[[bubbles_Arr objectAtIndex:nr] replaceObjectAtIndex:nc withObject:NOCOLOR];
[bubbles[nc+1][nr+1] setTexture:[[CCTextureCache sharedTextureCache] addImage:@"blank.png"]];
}
}
}
}

```

Now i am trying to implement bubble falling using DFS, i studied this link. i got all unvisited nodes after DFS but i am not able to verify with node is connected to top.

Here is my code for bubble falling

```
-(void)bubbleFalling{

for(int i = 0; i < R; i++){
    for(int j = 0; j < C; j++){
if (!visited[i][j]) {
    //NSLog(@"Array :  %d %d", i,j);

    NSLog(@"Value : %d",[[[bubbles_Arr objectAtIndex:i] objectAtIndex:j] integerValue]);

    BOOL canReach = [self canreachTop:i :j];
    if(canReach){
        NSLog(@"Yes");

    }
    else{
        NSLog(@"NO");
        [[bubbles_Arr objectAtIndex:i] replaceObjectAtIndex:j withObject:NOCOLOR];
        [bubbles[j+1][i+1] setTexture:[[CCTextureCache sharedTextureCache] addImage:@"blank.png"]];
    }

}

    }
}
}

-(BOOL)canreachTop:(int)ro:(int)co{
   int topNode = [[[bubbles_Arr objectAtIndex:R-1]objectAtIndex:C-1] integerValue];

BOOL success = FALSE;
for(int dr = -1; dr <= 1; dr++)
    for(int dc = -1; dc <= 1; dc++)

        if([self ok:ro+dr :co+dc]) // 4 neighbors
        {
            int nr = ro+dr;
            int nc = co+dc;

            if ((([[[bubbles_Arr objectAtIndex:nr] objectAtIndex:nc] integerValue]== topNode) && !visited[nr][nc])) {
            success = TRUE;
            }
        }

return success;
}

-(BOOL)ok:(int)r:(int)c{
    return r >= 0 && r < R && c >= 0 && c < C;
}

```

Below is the screenshot of my iPhone simulator in that green bubble should fall because it is not connected with any bubble, i think we have to check whether it is connected with the top bubble or not or i have to follow some other approach?

This is my first game and i am not getting what is wrong with my bubble falling code.

Thanks in advance.

# Answer
If you are using DFS starting from the top, all unvisited nodes should drop. The top should be an invisible node connected to all top bubbles (in the top row). One thing worth noting, is that unlike the current DFS which is checking for color equality, the functionality you should use for deciding which bubbles to drop because they are hanging in the air should ignore color and simply be content with bubbles being accessible from the top.

1. Run DFS from the newly added bubble with same color condition to see which bubbles to drop.
2. Run DFS from the top with no color condition and drop all bubbles that are hanging in the air.

I will try to clear it up. You are checking if a bubble can reach the top.. Don't. Run your DFS starting from the top and simply remove (drop) unvisited nodes.
> 1 votes

---
Tags: algorithm, game-mechanics, cocos2d-iphone, path-finding, search
---


title: Paint with soft brush (logic)

text:
# Question
Title: Paint with soft brush (logic)
During the last few days I was coding a painting behavior for a game am working on, and am currently in a very advanced phase, I can say that I have 90% of the work done and working perfectly, now what I need to do is being able to draw with a "soft brush" cause for now it's like am painting with "pixel style" and that was totally expected because that's what I wrote.

My current goal consist of using this solution :

1. Import a brush texture
2. Create an array that contain all The alpha values of that texture
3. When drawing use the array elements in order to define the new pixels alpha

And this is my code to do that (it's not very long, there is too much comments)

```
//The main painting method
//theObject     = the object to be painted
//tmpTexture    = the object current texture
//targetTexture = the new texture
void paint (GameObject theObject, Texture2D tmpTexture, Texture2D targetTexture)
{
    //x and y are 2 floats from another class
    //they store the coordinates of the pixel
    //that get hit by the RayCast
    int x = (int)(coordinates.pixelPos.x);
    int y = (int)(coordinates.pixelPos.y);

    //iterate through a block of pixels that goes fro
    //Y and X and go #brushHeight Pixels up
    // and #brushWeight Pixels right
    for (int tmpY = y; tmpY<y+brushHeight; tmpY++) {
        for (int tmpX = x; tmpX<x+brushWidth; tmpX++) {
           //check if the current pixel is different from the target pixel
           if (tmpTexture.GetPixel (tmpX, tmpY) != targetTexture.GetPixel (tmpX, tmpY)) {
               //create a temporary color from the target pixel at the given coordinates
                Color tmpCol = targetTexture.GetPixel (tmpX, tmpY);
                //change the alpha of that pixel based on the brush alpha
                //myBrushAlpha is a 2 Dimensional array that contain
                //the different Alpha values of the brush
                //the substractions are to keep the index in range
                if (myBrushAlpha [tmpY - y, tmpX - x].a > 0) {
                    tmpCol.a = myBrushAlpha [tmpY - y, tmpX - x].a;
                }
                //set the new pixel to the current texture
                tmpTexture.SetPixel (tmpX, tmpY, tmpCol);
            }
        }
    }
    //Apply
    tmpTexture.Apply ();
    //change the object main texture
    theObject.renderer.material.mainTexture = tmpTexture;
}

```

Now the fun (and bad) part is the code did exactly what I asked for, but by asking to draw anytime with the brush alpha I found myself create a very weird effect which is decreasing the alpha value of an "old" pixel, so I tried to fix that by adding an `if` statement that check if the current alpha of the pixel is less than the equivalent brush alpha pixel, if it is, then augment the alpha to be equal to the brush, and if the pixel alpha is bigger, then keep adding the brush alpha value to it in order to have that "soft brushing" effect, and in code it become this :

```
if (myBrushAlpha [tmpY - y, tmpX - x].a > tmpCol.a) {
  tmpCol.a = myBrushAlpha [tmpY - y, tmpX - x].a;
} else {
  tmpCol.a += myBrushAlpha [tmpY - y, tmpX - x].a;
}

```

But after I've done that, I got the "pixelized brush" effect back, am not sure but I think maybe it's because I'm making these conditions inside a `for` loop so everything is executed before the end of the current frame so I don't see the effect, could it be that?

Am really lost here and hope that you can put me in the right direction.

# Answer
New answer:

After giving it much thought I think you may not be blending the new clor with the existing one. I took the liberty to modify the code to what might work here:

```
for (int tmpY = y; tmpY<y+brushHeight; tmpY++) {
    for (int tmpX = x; tmpX<x+brushWidth; tmpX++) {
           //No need to check if the current pixel is different from the target pixel
            Color oldCol = tmpTexture.GetPixel (tmpX, tmpY);
            Color tmpCol = targetTexture.GetPixel (tmpX, tmpY);
            //change the alpha of that pixel based on the brush alpha
            if (myBrushAlpha [tmpY - y, tmpX - x].a > 0) {
                tmpCol.a *= myBrushAlpha [tmpY - y, tmpX - x].a;
            }
            //set the new pixel to the current texture
            double total_alpha = tmpCol.a + oldCol.a;
            tmpCol.a = oldCol.a + (1 - oldCol.a) * tmpCol.a;
            tmpCol.r = (tmpCol.r * tmpCol.a + oldCol.r * oldCol.a) / total_alpha;
            tmpCol.g = (tmpCol.g * tmpCol.a + oldCol.g * oldCol.a) / total_alpha;
            tmpCol.b = (tmpCol.b * tmpCol.a + oldCol.b * oldCol.a) / total_alpha;
            tmpTexture.SetPixel (tmpX, tmpY, tmpCol);
    }
}

```

Old answer:

This piece of code appears to be incorrect.

```
if (myBrushAlpha [tmpY - y, tmpX - x].a > tmpCol.a) {
  tmpCol.a = myBrushAlpha [tmpY - y, tmpX - x].a;
} else {
  tmpCol.a += myBrushAlpha [tmpY - y, tmpX - x].a;
}

```

I believe what you wish to do is mix the color of the brush with the current color of that pixel. It should be something like this:

```
// mba == myBrushAlpha[tmpY - y, tmpX - x];

double total_alpha = tmpCol.a + mba.a;
double alpha_result = tmpCol.a + (1 - tmpCol.a) * mba.a;
double red_result = (tmpCol.r * tmpCol.a + mba.r * mba.a) / total_alpha;
double green_result = (tmpCol.g * tmpCol.a + mba.g * mba.a) / total_alpha;
double blue_result = (tmpCol.b * tmpCol.a + mba.b * mba.a) / total_alpha;

tmpCol.a = alpha_result; // Assuming you will set the color to tmpCol.
tmpCol.r = red_result;
tmpCol.g = green_result;
tmpCol.b = blue_result;

```

I also notice this:

```
if (myBrushAlpha [tmpY - y, tmpX - x].a > 0) {
    tmpCol.a = myBrushAlpha [tmpY - y, tmpX - x].a;
}

```

It looks like it might have been supposed to be something along the lines:

```
if (myBrushAlpha [tmpY - y, tmpX - x].a > 0) {
    tmpCol.a *= myBrushAlpha [tmpY - y, tmpX - x].a;
}

```
> 2 votes

---
Tags: unity, textures
---


title: 2D Line drawing with Pixel Shaders

text:
# Question
Title: 2D Line drawing with Pixel Shaders
Recently I asked a question, what is the fastest way to render 2D lines using DirectX, and one of the answers mentioned this paper on Fast Prefiltered Lines which uses Pixel Shaders to accomplish wireframe drawing. This paper draws quads per line segment then uses a pixel shader to draw a line by computing distance from the pixel to the line down the centre of the quad before filling with line-color or transparent.

So, I'm wondering how can this be done? I wasn't aware the pixel shader can get knowledge of the input geometry (e.g. the quad) that creates it. Is the following possible? Ideally in DirectX9 but DX10 or OpenGL solutions also appreciated!

**EDIT**

Turns out I don't draw the quad like that, but like this. So the question is: How can I get information about x1y1 x2y2 into the pixel shader so I can compute distance to line edge & get a nice antialiased line segment?

# Answer
> 2 votes
See pseudo code First check if the current pixel is in range:

```
if(current.x >= - max_distance + min(x0, x1) && current.x =< max_distance + max(x0, x1))
{
    if(current.y >= -max_distance + min(y0, y1) && current.y =< max_distance + max(y0, y1))
    {
        result.color = some_color;
        float distance = simple_function_that_computes_distance_from_segment(x0, x1, y0, y1);
        if(distance < max_distance)
            result.alpha = (max_distance - distance) / max_distance;
        else
            result.alpha = 0.0;
    }
}

```

Get a tutorial for some generic pixel shader and re-write the code. To compute the distance of a point from a segment, you could google.

---
Tags: 2d, directx, directx9, fragment-shader
---


# Question
Title: How can texture packing improve performance?
Let's say I let a user give my library (a GUI system) multiple textures for rendering elements. What would be the performance impact of rendering with each of those textures separately versus, say, packing them all into a single texture and sampling from that as-needed?

# Answer
Using many separate textures involve many separate state changes; state changes are costly, and can add up. Depending on the scope (the number of separate textures used by a game, in this case), this can either be a non-issue or eventually have a noticeable impact on performance. It isn't possible to say in general though.

I would recommend a hybrid approach. Choose (based on the detected hardware specs, or allow the user to specify) a texture atlas size. Pack textures into a single texture as you are given them, and when you cannot fit one into the current atlas, allocate a new one and start filling that.

This gives you the advantage of reducing state changes, but also avoids the disadvantage of one giant texture (you may not be able to allocate that much space, it may be costly to map or unmap, it may waste a ton of space depending on the inefficiency of your bin packer, et cetera).

Consider also these related questions:
> 3 votes

---
Tags: opengl
---


title: Cell Lighting Propagation Problem

text:
# Question
Title: Cell Lighting Propagation Problem
I have in place a cell-based lighting system that works basically like this: (Not my actual code)

```
    //Light moves up
    for (int x = 0; x < width; x += 1)
    {
        for (int y = 0; y < height; y += 1)
        {
            light[x,y] = light[x,y+1] - amount;
        }
    }

    //Light moves down
    for (int x = width; x < 0; x -= 1)
    {
        for (int y = height; y < 0; y -= 1)
        {
            light[x,y] = light[x,y-1] - amount;
        }
    }

    //Light moves left
    for (int x = 0; x < width; x += 1)
    {
        for (int y = 0; y < height; y += 1)
        {
            light[x,y] = light[x+1,y] - amount;
        }
    }

    //Light moves right
    for (int x = width; x < 0; x -= 1)
    {
        for (int y = height; y < 0; y -= 1)
        {
            light[x,y] = light[x-1,y] - amount;
        }
    }

```

The variable `amount` is determined in each for() loop by if there is a block at x,y.

This should make it so that light darkens faster if there is a block at the position, but the light shows up looking like this:

Light shine out sides oddly

Light is in a tunnel, as you can see the top and bottom blocks are solid but they are not being lit up

Verical tunnel, but it seems to work correctly

Up and down dont seem to work quite right

I should also mention that changing the order of the passes changes in which direction the light propagates incorrectly. For example, if I change the order from `up,down,left,right` as shown above to `left,right,up,down`, the light is spread correctly in a horizontal tunnel and incorrectly in a vertical tunnel.

**SO MY QUESTION IS: What is wrong with my code that creates this obvious miscalculation?**

If you need to see more code or explanation or screenshots, I'll be happy to provide.

# Answer
(I removed this answer because it ended up not working)

I took this a completely different way, using recursion instead of for() loops.
> 0 votes

# Answer
You should put the calculated values into a copy of the light double-array, to avoid having the order in which you read the lightvalue of the tiles influence the each other. So read all values from the first doublearray over into a new one, then use the new one for the actual lighting.
> 2 votes

# Answer
As written, your down and right loops don't run (I'm assuming that's a mistake in your example code). Beyond that you have overlap in the updates, so the order you run the loops gets amplifications in different directions. I suggest making a single pass over the lit area, and calculating the light value based on the distance from the source.

```
for (int x = 1 - width; x < width; x += 1)
{
    for (int y = 1 - height; y < height; y += 1)
    {
        light[x,y] = light[x,y] + LightValueAt(x,y, sourceX, sourceY);
    }
}

```

This does mean doing a line of sight check to get shadows. Check out Amit Patel's excellent article on 2D visibility.
> 1 votes

# Answer
Basically, what Xnafan told is one of the possible ways to do it right. What (I assume) he wanted to say is:

```
int* light_src;
int* light_dst;

// then in your code (i showed only one block but oyu need to do it for all :-) )
for (int x = 0; x < width; x += 1) {
    for (int y = 0; y < height; y += 1) {
        light_dst[x,y] = light_src[x,y+1] - amount;
    }
}
swap(light_src, light_dst);

```

Also, I am not sure how do you iterate through your 2d array and it is hard to see what is solid on your images and what is not.

I thought this was a nice effect so I did this :-) One possible way: we need to go opposite to light. there are 4 possible directions 1) right, down 2) left, down 3) right, up 4) left, up Here I show only one for right down, others are similar (just switch + for - where appropriate). I use texture of unsigned chars \[0..255\]

```
float fadeK = 253.0f/255.0f;
float fadeSolidK = 200.0f/255.0f;

// assume lx, ly - is indices of cell where the light is
// first fill right part of horizontal line where the light is
for(int x=lx+1; x< width; ++x) {
    unsigned char prev_v = light[ly*width + x-1];
    float fade = is_solid(x-1, ly) ? fadeSolidK : fadeK;
    float propagation = 1.0f*fade*prev_v;
    light[ly*width + x] = (unsigned char)propagation;
            if(propagation<=0.0) break;
}
// do same for vertical line under the light
for(int y=ly+1; y< height; ++y) {
    unsigned char prev_v = light[(y-1)*width + lx];
    float fade = is_solid(lx, y-1) ? fadeSolidK : fadeK;
    float propagation = 1.0f*fade*prev_v;
    light[y*width + lx] = (unsigned char)propagation;
            if(propagation<=0.0) break;
}
// now fill right down part
for(int y=ly+1; y< height; ++y) {
    for(int x=lx+1; x< width; ++x) {
        unsigned char left_v = light[y*width + x-1];
        unsigned char up_v = light[(y-1)*width + x];

        // determine how strong each previous (left or right) pillar influences us
        float dx = x - lx;
        float dy = y - ly;
        float sum = dx + dy;
        dx = dx/sum;
        dy = dy/sum;

        float fadeh = is_solid(x-1, y) ? fadeSolidK : fadeK;
        float fadev = is_solid(x, y-1) ? fadeSolidK : fadeK;
        float proparation = dy*fadev*up_v + dx*fadeh*left_v;
        light[y*width + x] = (unsigned char)clamp(proparation, 0.0f, 255.0f);
    }
}
// make all solid cells look white (just to mark them, you do not need to do it)
for(int y=ly; y< height; ++y) {
    for(int x=lx; x< width; ++x) {
        if(is_solid(x-1, y))
        {
            light[y*width + x] = 255;
        }
    }
}

```

It may look like a lot of code, but this is all very simple operations and you are not dependent on light move direction (actually your light can be at any cell at any single moment). Also (as optimization) you do not need to scan all array - only in some radius around light (radius depends on how fast the light fades out).

You can check out my resulting image (only case for one quadrant, other are done similar)
> 1 votes

---
Tags: xna, c#, tiles, lighting
---


title: Managing Voxel Data

text:
# Question
Title: Managing Voxel Data
I've been programming in C++ as a hobby for about 4 months now, and I've really loved creating stuff using voxels. I wrote a "game" (More of just a personal challenge, as I really only did the terrain, no gameplay) that rendered a Minecraft-like world, but recently I've been thinking about trying to write a game/challenge/etc that uses an algorithm such as Marching Cubes or Dual Contouring and reducing the voxel size. When I wrote my Minecraft-like project, I stored each chunk's data in a multidimensional array of unsigned shorts (thus giving me up to 65536 different block types). Additionally, for rendering, I only stored one point (as a GLubyte) and another GLubyte to indicate which of the 6 faces the point represented. I then rendered the face using a geometry shader. All of this was done to save the amount of RAM usage my project required, as I wanted to have the render distance out as far as possible.

With the new project I've been thinking about, the thing I can't wrap my head around is how I can possibly store enough voxel data to have voxels around ~5cm or 10cm compared to the old 1m sized voxels I had. When I rendered a 704x704x704 area of blocks, my old project used around 670MB of RAM. If I shrunk the voxel size to 10cm and kept the same render distance, that would be around 649GB of Voxel data (assuming 2 bytes per voxel and an area of 7040^3 voxels). Is there any way I can store the voxel data in a more efficient manner that still allows me a wide range of different voxel types?

# Answer
Do you need to have every single chunk (presuming you're using chunks) in memory at once? Some will be occluded - particularly underground - or behind mountains etc. Lots will probably be just air/empty and so could be marked with a flag.

Also you could use a LOD octree or similar structure to try keep the detail currently visible inversely related to the distance from the observer. As stated by Jason, this is much more likely to buy you performance, but it's a major structural change from a flat chunk map.

See this article about clipmaps from my favourite blog (he has a voxel engine similar to what you describe with a voxel size of ~a decimetre).
> 5 votes

# Answer
The standard approach for engines like Ken Silverman's VoxLap and it's successor Ace of Spades, is to use RLE compression and several other bit-level tricks to both store and access the data. This sort of 1D compression tends to be highly efficient and considerably easier to use than octrees. I believe Silverman's engine achieved a voxel resolution of something like 10cm cubed. Something you don't commonly see today, and which was achieved on much weaker hardware.

I believe it is also true that his approach did not store colours for unexposed voxels, that it instead calculated colour for surface voxels as a function of height, or by remembering which areas of the terrain had been blasted open and colouring these as "fresh soil". You could use some sort of continuous function like perlin noise to do this, but it could rapidly get costly for large surface areas (unless, perhaps, performed on the GPU).

Octrees are not bad, but they are difficult to use in practice, and cache-efficient allocation is considerably more challenging than RLE, which is easy to linearise by chunk. Tero Karras and Samuli Laine's seminal paper on SVOs indicates just how much effort goes into truly performant octree implementation -- and that is considering *only* rendering, not gameplay or network communications.
> 4 votes

# Answer
I don't know how far you've gone in your project but I and a friend of mine are using the Dual Marching Cubes algorithm, based on Octree chunck structure and using a dual grid to render the data. It has many advantages, like really low memory required and a really fast rendering. It may be a little tricky to implement Level Of Detail (LOD) in chunk borders with other chunks, but if you have some spare time you may find out how Ogre3D developers did.
> 0 votes

---
Tags: c++, voxels, data
---


# Question
Title: recommended shader pipeline infrastructure in core opengl 3.3
I am writing a game project in Go and I am using an OpenGl 3.3 core context to do my rendering stuff. At the moment I have different types of renderers. Each renderer has it's own pair of vertex- and fragment-shader, a struct of uniform- and attribute locations. A struct with glBuffers, vertex-array-object, and numverts (int) which contains all data required to render one object (mesh). Last but not least a constructor to create and initialize the attribute/uniform locations a method to load a mesh into mesh data and the render method itself.

I am absolutely not happy with this design. Every time I want to create a new simple shader, I have to write all this code, and I haven't found a way to make the overhead of a new shader smaller. All I was able to make with the help of go reflections is to automatically get the attribute/uniform location based on the variable name in attribute/uniform location struct and to automatically set the attribute pointers based on the layout of the vertex struct.

another thing that I don't like, is that when I want to implement for example the functionality of the function glClipPlane of the fixed function pipeline, I need to add the uniform to each shader separately and I need to set this uniform in each shader and I need to implement the discard of fragments in each fragment shader

Are there some common practices that significantly reduce the code overhead of a new shader? Are there good shader pipelines that you can recommend me to take a look at? Are there some good practices to add functionality to several shaders at once?

# Answer
> 1 votes
What I understand from your question, you are trying to minimize the amount of code you are writing for new shaders.

One thing I use, even though not without its problem is, conditional shader compilation, using preprocessor directive. What I do is pass conditional directive when compiling the shader program, and build the functions accordingly. For example you have specular function, diffuse, texture sampling etc.. And build the shader based on that.

```
void glShaderSource(GLuint shader,
                    GLsizei count,
                    const GLchar **string,
                    const GLint *length);

```

Notice that `glShaderSource` takes an array of strings (Not sure how Go handles this) but that's the OpenGL standard; it takes an array so you can concatenate shader strings. Also horde3D use a similar technique.

If that's not entirely satisfying you can investigate using uniform constants, but as far as I know GLSL doesn't support that, so if uniforms are not optimized by the GLSL compiler you don't really want branching in your shaders. Direct3D on the other hand supports this.

As for managing uniforms and attributes:

For attributes I bind constant attributes locations, and save that in a dictionary. This is simple yet effective and easy to use.

Uniforms on the other hand are a bit more complex. I wrote an article on this topic, the summery is; I used the observar pattern for updating the uniforms, while for the actual uniform types, I used some kind of static polymorphism to handle different uniform types correctly. This is only a suggestion and might not be the best solution.

---
Tags: opengl, shaders, pipeline
---


title: libgdx get the value of a key

text:
# Question
Title: libgdx get the value of a key
I'm trying to do collision detection (which I have working well) but now I want to use it for a little more. I want to check special circumstances for the collision. Right now I'm checking for containsKey like so:

```
someCell. ... .getTile().getProperties().containsKey("collision");

```

This works fine. But now I want to use the VALUE of that key to determine what the character hit and continue accordingly. If the value is null, just a normal hit. But if the value is a sign, and the user chooses, it can be read. Or if the value is a chest, if the user chooses to do so they can open it (but check that locked is indeed false first, or the user can unlock it).

The thing is, I've looked everywhere and can't find a way to check the value of the key. And yes, I can just create a lot of keys but it would be easier to have one key that can carry many values and check and alter them based on user input or game circumstances. I tried

```
theKey = someCell. ... .getTile().getProperties().containsKey("collision")[.value("someValue");];
theKey.value("someValue");

```

but neither worked.

So, my question to you is this: how can I access and later edit the value of a custom key created in tiled map editor (should have mentioned that earlier, huh)?

Any help would be appreciated.

# Answer
> 4 votes
In fact it's really easy.

`getProperties()` returns a MapProperties object.

So if you look at the documentation it contains a `get` method just like a regular map in Java.

```
getProperties().get("key")

```

Sometimes you just want to retrieve a simple type like a number, in this case, libGDX allows you to pass a type, it prevents you from having to transform the value manually into a number.

```
getProperties().get("key", Integer.class)

```

There is even an overload allowing you to pass a default value in case there is no such key, which is really convenient right?

---
Tags: libgdx, tiles
---


# Question
Title: How do I hide the console window for my released MonoGame game?
I am just finishing up my first game for the One Game A Month challenge which I wrote with the current MonoGame framework in Xamarin for Windows. I built the program in release mode, but running the executable produces **a console window besides the game window**. The console stays empty unless I deliberately cause an error to be logged, say by removing a required resource.

How can I get rid of this extraneous console window?

I looked through the project settings, but saw nothing alluding to removing the console window...

# Answer
> 2 votes
Found that changing the build settings to Executable with GUI solved this problem.

# Answer
> 1 votes
Basically, change the configuration of Build "Console Application" to "Windows Application".

---
Tags: xna, monogame
---


# Question
Title: Game Design: Faction/Player circular relationship
For a Java game, say I have two classes:

**Player**, representing a player in the game. **Faction**, representing a faction of players in the game.

When the game starts up, all factions are loaded into some collection and all players are loaded into some collection.

```
Collection<Player> players;
Collection<Faction> factions;

```

Say there are two variables:

```
Player player1;
Faction the_destroyers;

```

`player1` is in the faction `the_destroyers`.

the\_destroyers needs to reference `player1`, since `player1` is in `the_destroyers`. At the same time, `player1` needs to reference `the_destroyers`, for quick lookup (otherwise I would have to iterate through the collection of factions, which may be a very large collection).

Obviously, whichever variable is loaded first cannot reference the other, since the other has not yet been loaded.

Generally speaking, how do I get around this issue? Is there a simpler solution?

# Answer
What I would do is make the factions be simple symbols which represent their information regardless of members (name, description etc), and keep some sort of dictionary for each match, which keeps track of which players are in which faction.

```
Dictionary<Faction, List<Player>>

```

This also allows you to do more exotic stuff like players betraying their faction and switching more easily.

For accessing the faction from the player's point of view, you can just use a field in the player's class.

```
void addToDictionary(Faction faction, Player player) {
    dict[faction].add(player);
    player.setFaction(faction);
}

```
> 9 votes

# Answer
Create one type of object first without adding any references to the other.

Then you create the other type of object, and during its construction you create the bidirectional links between itself and the other object type.

The calling code would look like this:

```
// create players
Player player1 = new Player("1");
Player player2 = new Player("2");
Player player3 = new Player("3");

// create factions
Faction jpf = new Faction("Judean People's Front");
jpf.addPlayer(player1);
jpf.addPlayer(player3);

Faction pfj = new Faction("People's Front of Judea");
pfj.addPlayer(player1);
pfj.addPlayer(player2);

```

The implementation of `addPlayer` would then both add the player to the faction and tell the player that it is now a member of this faction:

```
public void addPlayer(Player player) {
    this.players.add(player);
    player.addFaction(this);
}

```

(omitted for clarity: Checking that the player isn't already a member of that faction, and when that's the case, throw an exception)

This example loads the players first and then the factions, but you can of course also do it the other way around. You can also choose to add factions to players instead of adding players to factions. Choose whatever option makes more sense in the context of your game.
> 3 votes

---
Tags: java, game-design
---