title: 2d platform game with zoom in and out

text:
# Question
Title: 2d platform game with zoom in and out
I am using AndEngine, and I wish to create a 2d platform game like worms, where I can zoom out to see the whole world and zoom into single character, so I can select it.

I do not want to use the zoom camera, because *I do not want scaling*. I want the user to see the platform crystal clear.

The only thing I thought about, is making N levels of ZOOM, where each zoom level has it's own set of tiles - very problematic solution, or doing it the other way around - making a huge tiles and sprites, and scaling them down - which still feel a little awkward to me. What is the right way to implement such a thing???

Thanks!!!

# Answer
Well, why does the things you said feel awkward? It's the way to go.

You can create the assets for the closest zoom level for the best quality. When zooming out, you will see scaling (down), but that usually looks ok. In my game I simply create full HD textures and thanks to that, my game looks ok on all mobile devices.

You can also use LOD (level-of-detail) techniques to change the graphics when the zoom level reaches certain threshold. This is not implemented in AndEngine, but you should be able to write the code yourself. The LOD techniques can involve blending between the high detail and low detail graphics, so you won't see a "jump" in the quality.
> 1 votes

# Answer
If you are going to have set zooms then mipmapping is probably the best way to go. By using mipmaps you won't have to worry about needlessly filling in information as you change levels of detail as it is all pre-calculated.

Usually what you do is make a large texture and using a procedure you create yourself you can then halve the size of the texture and from the original source texture you sample the texture data and apply some sort of convolution method to build up a new texture of half the original size. From there you halve the size again and take the new texture you created to make a new texture again. Once this is done and you're happy with how many LOD textures you have you don't need to ever do this again.

Mipmapping is actually used a lot because it has advantages in both visual and performance area's. You won't have to worry about making a algorithm which expensive but gives you a great visual output because it will only need to be done once.
> 0 votes

---
Tags: 2d, andengine, platform
---


title: Should I use tiles in a snake game?

text:
# Question
Title: Should I use tiles in a snake game?
I'm building a simple snake game, which is my first game ever. I'm using LibGDX, which is Java-based.

I've looked at the Tiled Map Editor, but I don't know if it is necessary in a simple game like snake. Is it?

I don't know how to make grid however, and I think that the map editor could make a grid easier than by code? I don't know.

# Answer
I suspect you are overthinking. You could make a simple snake game even without sprites. Why do you need a map editor for a snake game? It won't help you do your code. If it is your first game start without Tiled. I think you have a concrete idea how you want to make it but I would suggest to look after some tutorials to compare if you are on the right track.

I think it also may help if you understand that representation of the data (rendering) and the data itself are mostly two different things.

Your snake game will probably consist of the background, which could be a solid color, a big image or a map of tiles and your snake for which you probably need 2 sprites (head and tail) which you then can rotate. Alternatively you can use a tile map but I would not advice to start with it because then you narrow your solutions to problems you may stumble across to a strict grid and for a beginner I would advise some more "artistic freedom".
> 2 votes

---
Tags: java, libgdx, tiles, tilemap
---


# Question
Title: Outsourcing mobile app development, but royalty-based?
Terribly sorry if this is in the wrong StackExchange site, but it looked closest to my question.

I have an idea or two floating around in my programmer's brain for mobile apps on Android or iOS. Thing is, I can't spend months programming it after my day job just to see someone else go to market first. In the same vein, I don't want to dump tens of thousands of dollars to pay someone to do it outright. I know that in other industries, you can often get paid by offering up the idea as intellectual property, allowing another company to do the work while you collect royalty checks for coming up with the idea in the first place, assuming the developing company went ahead with it and it became successful.

Does such a thing exist in the mobile application development world? If so, any recommendations for trustworthy companies? Let's assume that it actually IS a decent idea, is well vetted out and planned, and does not exist in the marketplace yet.

# Answer
> 8 votes
Since you won't risk your own time, or your own money on it, your idea hasn't totally convinced even you. I doubt you will find anyone else to sell it to.

This is a very common line of reasoning. Paul Graham wrote an essay on the topic.

> People ... overvalue ideas. They think creating a startup is just a matter of implementing some fabulous initial idea. And since a successful startup is worth millions of dollars, a good idea is therefore a million dollar idea.
>
> ...
>
> Actually, startup ideas are not million dollar ideas, and here's an experiment you can try to prove it: just try to sell one. Nothing evolves faster than markets. The fact that there's no market for startup ideas suggests there's no demand. Which means, in the narrow sense of the word, that startup ideas are worthless.

http://www.paulgraham.com/ideas.html

# Answer
> 0 votes
> Does such a thing exist in the mobile application development world?

I guess it's not. I remember reading this post about similar case, it's pretty much sums it all.
Essentially you want developer to take the risks while not taking any yourself (or so I understand.)

# Answer
> 0 votes
Actually, there are two startups that have been created (and, I'm sure, a few more if you look) to meet this exact need. One is called Dandy the other is call AppIdea...Dandy is located in the UK as is, I believe, AppIdea. Both have different biz and operating models, but both essentially offer royalties for ideas that get developed into apps.

---
Tags: mobile
---


# Question
Title: How do you prevent AABBs from passing through each other?
I know what an AABB is, but I don't know how you would check for collision with an object that is going really fast. If an object goes fast enough, it can skip over other bounding boxes without it detecting a collision.

**Example:**

So, for an object with a bounding box to move from (0, 0) to (525, 670) in one update, would I have to somehow iterate over each point from the starting point to the end? Because I need objects to be able to go fast and still be tested for collision on other bounding boxes. I hope that makes sense.

# Answer
The term you are looking for is *"Continuous Collision Detection"* (CCD), something also refered to as *"Anti-Tunneling"* and less commonly *"Broad-phase collision detection"*.

Some CCD implementations rely on ray-casting approaches that cast a ray in the direction of the fast traveling object to check if there is an object in the way and try to estimate whether the next frame update could already bypass this "hit" object (based on current speed). If so the expected time of impact is calculated and the movement restricted accordingly.

Another approach often used by the physics engines (e.g. *"PhysX"* or *"Bullet"*) is to not only check for collisions at the position the object currently is in (which might already be beyond the object it should have collided with), but to also do various checks between the position from the previous frame and the current one. *Bullet* does so by using a "swept sphere" which is used to quickly check for potential collisions along that path (a sphere is used since it is even faster to check than a box).

It is advised to only turn on CCD for fast objects since it rather performance-heavy. Therefore, in some engines you have to defined speed threshold and only once they are hit, CCD comes into play (e.g. see this *Bullet* setup guide).

*PS:* I know that the mentioned physics engines are C++ and you are asking for Java, but the principles still apply.

*BTW:* Also have a look at this answer, as well as this more generic / theoretical SO question on potential algorithms.
> 6 votes

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


title: Actors (Label) not being drawn to stage

text:
# Question
Title: Actors (Label) not being drawn to stage
I have a weird issue that when I try to `draw` a `Stage` with only an `Actor`, a `Label` to be more precise, added to it and nothing seems to be getting drawn.

This is how my setup goes:

I have a `Sprite` (player) being drawn and in another class, which is the HUD, that I draw in a separate `SpriteBatch`, now in the same class I am trying to `draw` the `Stage`, I have ensured that the `Stage` is outside of the HUD's `SpriteBatch.begin()/.end()` calls and that the `Stage` is being drawn after, which should be "above" the HUD. I have also set the position, of the `Actor`, to be in the middle of the `Stage`

I just can't seem to get this to work.

This is my code for the **Player** class:

```
public void update(SpriteBatch spriteBatch, float delta){
    // *** REMOVED FOR CLARITY ***
    spriteBatch.setProjectionMatrix(camera.combined);
    camera.update();
    hud.render(delta);
}

```

And this is my code for the **HUD** class

```
public void render(float delta){
    spriteBatch.begin();
    spriteBatch.draw(hudBackgroundTexture, position.x, position.y, size.x, size.y);
    // *** REMOVED FOR CLARITY ***
    spriteBatch.end();
    labelLives.setPosition(size.x/2, size.y/2);
    hudStage.act();
    hudStage.draw();
}

```

I'm not receiving any errors, and I know I have initialised my `Stage` and `Label`.

Thanks in advance =\]\]

# Answer
> 0 votes
Haha, well, I found out what was up, it was my font file, you see when I was editing it, I used the text **READY**, so when I saved it, I didn't know that the text written is what is saved, so when I looked at the font.png file, I found that it only contained the letters **ADERY**.

Thanks for the help anyway =\]

---
Tags: java, android, libgdx
---


# Question
Title: How do I add a canvas tag to my ocean id in javascript?
I'm trying to create a "wack-a-mole" type of game. I've gotten all of the lines of code except in one area. Here is all of the code:

```
<!doctype html>
<title>Squid Smash!</title>
<link rel="stylesheet" href="monsterSmash.css">

<style type="text/css">
body {
background-image: url(squid.png);
background-size:1000px 600px;
background-repeat:no-repeat;
}
.ComicSansBlue {
font-family: Comic Sans MS;
font-size: 24px;
font-style: normal;
color: blue;
font-weight: 700;
text-align: left;
}
}
</style>

<body class="ComicSansBlue">
<img src="=SquidMonstersGame2.png" alt="Squid Smash"><p id="output"></p>
<div id="ocean"></div>

<script>

//--- The squidMonster object
var squidMonster =
{
//tilesheet source, size of each frame, and number of game columns
tileGraphic: "monsterTileSheet4.png",
size: 256,
columns: 3,

//The numbers of the animation frames and the starting frame
numberOfFrames: 5,
currentFrame: 0,

//Properties of the animation frames's x and y positions on the tile sheet.
//They're 0 when this object first loads
sourceX: 0,
sourceY: 0,

//A property to control the loop
forward: true,

//States
hiding: 0,
leaping: 1,
strike: 2,
state: this.hiding,

//Properties needed to help reset the animation
timeToReset: 9,
resetCounter: 0,

//A property to store the random time
waitTime: undefined,

//A method to find a random animation time
findWaitTime: function()
{
this.waitTime = Math.ceil(Math.random() * 60);
},

//The squidMonster's aniMate method
aniMate: function()
{
this.sourceX
= Math.floor(this.currentFrame % this.columns) * this.size;
this.sourceY
= Math.floor(this.currentFrame / this.columns) * this.size;

//Figure out the squidMonster's state
if(this.state !== this.strike)
{
if(this.waitTime > 0 || this.waitTime === undefined)
{
this.state = this.hiding;
}
else
{
this.state = this.leaping;
}
}

//Change the behaviour of the animation based on the state
switch(this.state)
{
case this.hiding:
this.currentFrame = 0;
this.waitTime--;
break;

case this.leaping:
//If the last frame has been reached, set forward to false
if(this.currentFrame === this.numberOfFrames)
{
this.forward = false;
}

//If the first frame has been reached, set forward to true
if(this.currentFrame === 0 && this.forward === false)
{
//Set forward to true, find a new waitTime,
//set the state to hiding and break the switch statement
this.forward = true;
this.findWaitTime();
this.state = this.hiding;
break;
}

//Add 1 to currentFrame if forward is true, subtract 1 if it's false
if(this.forward)
{
this.currentFrame++;
}
else
{
this.currentFrame--;
}
break;

case this.strike:
//Set the current frame to the last one on the tilesheet
//to display the explosion image
this.currentFrame = 6;

//Update the resetCounter by 1
this.resetCounter++;

//Reset the animation if the resetCounter equals the timeToReset
if(this.resetCounter === this.timeToReset)
{
this.state = this.hiding;
this.forward = true;
this.currentFrame = 0;
this.resetCounter = 0;
this.findWaitTime();
}
break;
}
}
};

//======================================================================
//======================== The gameTimer object ========================

var gameTimer =
{
time: 0,
interval: undefined,

begin: function()
{
var self = this;
this.interval = setInterval(function(){self.tick();}, 1000);
},
tick: function()
{
this.time--;
},
stop: function()
{
clearInterval(this.interval);
},
reset: function()
{
this.time = 0;
}
};

//=====================================================================
//--- Main program
//=====================================================================

//Load animation tile sheet
var tileGraphic = new Image();
tileGraphic.addEventListener("load", loadHandler, false);
tileGraphic.src = squidMonster.tileGraphic;

//The number of rows and columns and the size of each cell
var rows = 3;
var columns = 6;
var size = squidMonster.size;
var space = 10;

//Arrays for the squidMonsters, canvases and drawing surfaces
var squidMonsterObjects = [];
var squidMonsterCanvases = [];
var monsterDrawingSurfaces = [];

//Game variables
var squidMonsterSquishes = 0;

//Get a referene to the output
var output = document.querySelector("#output");

function loadHandler()
{
//Plot the grid of monsters
fillOcean();

//begin the game timer
gameTimer.time = 30;
gameTimer.begin();

//begin the animation loop
aniMate();
}

function fillOcean()
{
for(var row = 0; row < rows; row++)
{
playSound('whaleOcean.mp3');
for(var column = 0; column < columns; column++)
{

//Create a new squidMonster object, give it a random time, display its
//first frame and push it into an array
var newMonsterObject = Object.create(squidMonster);
newMonsterObject.findWaitTime();
squidMonsterObjects.push(newMonsterObject);

```

Here is where I'm having the problems (I put a * by the line): I've created a canvas tag, I've created a var so I can use the div, but I don't know how to add the canvas tag to the ocean tag. As you can see I kind of start the line, because I think that's right (which if it isn't, please tell me). I would like to know what line or lines of code I need and why. I did try to look for answers, but couldn't find any so if anyone knows of a good article on the concept, that'd be appreciated as well as the lines of code to put in here.

```
//Create a canvas tag for each squidMonster, add it to the <div id="ocean"> tag,
//position it, then add a mousedown listener and push it into an array

var canvas = document.createElement('canvas');
var div = document.getElementByID('ocean');
*canvas.id =
canvas.style.position = "relative";
canvas.height = 256;
canvas.width = 256;
canvas.AddEventListener("mousedown", mousedownHandler, true);

//Create drawing surface. push it into the drawingSurfaces array
var drawingSurface = canvas.getContext("2d");
monsterDrawingSurfaces.push(drawingSurface);
}
}
}

function aniMate()
{
//Call aniMate every 120 milliseconds while the timer > 0.
if(gameTimer.time > 0)
{
setTimeout(aniMate, 120);
}

//Loop through all the monsters in the array, call aniMate method
for(var i = 0; i < squidMonsterObjects.length; i++)
{
aniMate();
}

//check for the end of the game
if(gameTimer.time === 0)
{
gameOver();
}

//Render the animation
render();
}

function gameOver()
{
//Stop the gameTimer
gameTimer.stop();

//Remove the mousedown event listeners from the
//canvas tags so that they can't be clicked
for(var i = 0; i < squidMonsterCanvases.length; i++)
{
var canvas = squidMonsterCanvases[i];
canvas.removeEventListener("mousedown", mousedownHandler, false);
}
}
function playSound(soundfile_ogg, soundfile_mp, soundfile_ma) {
if ("Audio" in window) {
var a = new Audio();
if (!!(a.canPlayType && a.canPlayType('audio/ogg; codecs="vorbis"')
.replace(/no/, '')))
a.src = soundfile_ogg;
else if (!!(a.canPlayType && a.canPlayType('audio/mpeg;').replace(/no/,
'')))
a.src = soundfile_mp;
else if (!!(a.canPlayType && a.canPlayType(
'audio/mp4; codecs="mp4a.40.2"').replace(/no/, '')))
a.src = soundfile_ma;
else
a.src = soundfile_mp;

a.autoplay = true;
return;
} else {
alert("Time almost up");
}
}
function mousedownHandler(event)
{
//Find out which canvas was clicked
var theCanvasThatWasClicked = event.target;

//Search squidMonsterCanvases array for a canvas that matches the clicked one
for(var i = 0; i < squidMonsterCanvases.length; i++)
{
if(squidMonsterCanvases[i] === theCanvasThatWasClicked)

{
var squidMonster = squidMonsterObjects[i]
if(squidMonster.state === squidMonster.leaping)
{
currentFrame = 6;
squidMonsterSquishes++;
playSound('explosion.mp3');
}
}
}
}

function render()
{
for(var i = 0; i < squidMonsterObjects.length; i++)
{
//Get reference to the current squidMonster and drawing surface
var squidMonster = squidMonsterObjects[i];
var drawingSurface = canvas.getContext("2d");

//Clear the current squidMonster's canvas
drawingSurface.clearRect(0, 0, size, size);

//Draw the squidMonster's current animation frame
drawingSurface.drawImage
(
tileGraphic,
squidMonster.sourceX, squidMonster.sourceY, size, size,
0, 0, size, size
);
}

//Display the output
output.innerHTML
= "<span class='ComicSansGreenLightYellow '> Squid Monsters Squished:</span>" + squidMonsterSquishes
+ "<span class='ComicSansGreenLightYellow '>, Time left:</span>" + gameTimer.time;
}
</script>

```

# Answer
I figured out what was wrong with my 8 lines of code for those of you who may be interested.

```
var canvas = document.createElement('canvas');
var div = document.getElementById("ocean");
canvas.width = 256;
canvas.height = 256;
div.appendChild(canvas);
canvas.style.top = row*(256 + space) + "px";
canvas.style.left = column*(256 + space) + "px";
canvas.addEventListener("mousedown", mousedownHandler, false);
squidMonsterCanvases.push(canvas);

```

I had actually had all 8 of these lines at one point but was struggling and thought my code was wrong. Then I found out it wasn't working because my "addEventListener" had a capital A.
> 0 votes

---
Tags: javascript, html5
---


# Question
Title: How do I implement occluded lighting in a block-based 2D game?
I want to have 2D lighting that can be blocked by in-game objects. My game has a top-down view and all game objects are described by rectangles.

Let's say I have a 10x10 world and I place a light at 1x1 and walls all around that light. I want to be able to see the light source at 1x1, but not anywhere else, because it's blocked by the walls.

I've heard of casting light rays works, but how does that really work?

# Answer
Amit Patel has written a very nice article on 2D ray casting.

This involves casting rays to each of the vertices inside the range of the light source to build a light mesh.

All of the visual examples are interactive in the post and very easy to understand.

You don't have to limit yourself to a box either, the perimeter you trace can be any shape you like.
> 13 votes

# Answer
You should use raycasting algorithm, which means, you should be able to compute the intersection of ray (half-line) with any object in your scene (lines, squares, circles, triangles ....) and choose the closest intersection. You cast the ray in all directions and then "draw the light" only to the closest object.

Here is how it may look like.
> 1 votes

# Answer
If you know what ray casting is, then all you need to do really is hard-code it. It's not overly complex as long as you have coordinates for each vertex.

First, create a light-emanating object. Place your light at x,y coordinates.

```
#include <math.h>
int i = 0;
if ( sqrt( abs( light.x - vertex.x )^2 + abs( light.y - vertex.y )^2 ) <= light.radius)
{
    lightOccludingVertices[i] = vertex;
    i++;
}

//If two or more vertices are both a member of an individual wall,
//illuminate the triangular area between the light, the furthest
//vertex on the x-axis, and the furthest vertex on the y-axis

```

This is not guaranteed to work for a concave polygon, but it should work just fine for any convex polygons.

This will work if your occluding objects (walls, character, flying purple people eater) are painted to the screen after applying lighting. Otherwise, half of a wall will appear significantly brighter than the other half. If your point light is equidistant from two pairs of vertices of the same wall (exactly half as high as your wall's height), apply the triangle to the two nearest vertices, rather than the two further away.

I should also mention that this method requires a dynamically-created vertex point where **the edge of the light's radius meets the surface of the occluding object.** This creates a minimum of 3 vertices for any occluding object and will allow for walls that extend past the radius of the light (or off the screen) to also block any light.

More information on concave and convex polygons
> 0 votes

---
Tags: opengl, 2d, lighting, raycasting
---


# Question
Title: Subdividing a polygon into boxes of varying size
I would like to be pointed to information / resources for creating algorithms like the one illustrated on this blog, which is a subdivision of a polygon (in my case a voronoi cell) into several boxes of varying size:

http://procworld.blogspot.nl/2011/07/city-lots.html

In the comments a paper by among others the author of the blog can be found, however the only formula listed is about candidate location suitability:

http://www.groenewegen.de/delft/thesis-final/ProceduralCityLayoutGeneration-Preprint.pdf

Any language will do, but if examples can be given Javascript is preferred (as it is the language i am currently working with)

A similar question is this one: What is an efficient packing algorithm for packing rectangles into a polygon?

# Answer
> 3 votes
Sorry for the long delay since my comment. I'd been trying to reverse-engineer the ProcWorld example and couldn't work out why the algorithm was making some of the choices it did.

In any case though, here's my best idea so far, using the center block from the ProcWorld example as a guide:

Start by finding an oriented bounding rectangle of the polygon. (For this example it happens to be aligned with the grid, which made these diagrams a bit easier) This rectangle defines the axes for the partition inside (you may want to transform all of your vertices into this new coordinate space to make the math simpler)

Next, split the polygon along one of these axes, from one vertex all the way to the far side. (I'm not sure how this vertex is chosen. Most of the time, it looks like it's the one that gives the longest cut, but not always. It might be chosen to roughly equalize the areas on each side of the cut, or to ensure that the max distance on one side does not exceed a maximum building depth constraint)

For each sub-polygon formed, select another vertex from the original polygon boundary and cut across to the previous cut. (This vertex may be chosen as the one furthest from the previous cut - which I assume here - or again in an area-balancing fashion)

Continue until the remaining polygon is a quadrilateral, or the next cut would exceed a maximum-skinniness constraint (eg. the cut shown in green).

Split the remaining polygons into quadrilaterals by cutting parallel to the previous successful cut.

If cutting at a vertex would result in an excessively skinny building, discard it.

Finally, we have a set of quadrilaterals. Several will be bounded by cuts on three sides - cap them off at their obtuse angle to make them rectangular. For quads that are bounded by cuts on only two edges, find the largest rectangle that fits inside.

If ever the next proposed cut would go outside the polygon (shouldn't happen with Voronoi cells since they're always convex), generate a new oriented bounding box for that sub-polygon and start cutting its remaining boundary vertices as though you were starting from scratch. (That's the best way I can think of to explain how the alignment axis changes in places like the one pictured - I think it's because the algorithm wanted to connect the bottom-right vertex to the bold blue cut, and couldn't because of the concavity in-between)

I hope that may be of some use, even if you don't use this algorithm exactly. Thinking about the problem in terms of cutting rather than filling certainly seems to make it easier to get a clean, tightly-packed result.

# Answer
> 1 votes
I have solved my problem in a different way. As i was looking for my problem, it turned out to be a fairly complex one, both measured in difficulty to implement as algorithm, as algorithm complexity.

If anyone is having a similar problem, these problems are classified as 'packing problems' in general, with specific problems like the 'pallet loading problem'.

The problem i was interested in, is illustrated at the bottom of this page:

https://www.ime.usp.br/~egbirgin/packing/

and a paper about this problem, with algorithm descriptions of how to solve the packing problem for convex polygons and curved shapes:

http://www.ime.usp.br/~egbirgin/publications/bmnr.pdf

Some more information on these kinds of problems:

http://lagrange.ime.usp.br/~lobato/utdc/ http://mathworld.wolfram.com/SquarePacking.html

---
Tags: 2d, procedural, tessellation
---


# Question
Title: How to accurately count 1 second within my logic update?
I have the following method:

```
long time = system.nanoTime();

public void count(){

    if (System.nanoTime() > (time+1000000000)){

        //Output something or perform action here
        Log.v("timer","One second passed");

        //Reset for next second-count
        time = system.nanoTime();
    }

}

```

This should output to the console every 1 second. It's close, but it seems not quite perfect.

If I time this with an actual stop watch (or with the same code running on another device), over time, it becomes slightly 'off'. Not by much, but it's off. After a minute, it's about 1/4 of a second off, the longer it is left, the larger the discrepancy.

The above method is called from within my **updateLogic()** method which is called aprox 60 times per second from my main game loop.

Can anyone tell me why this doesn't count **extactly** 1 second or why it's becoming out of snyc over time? How can I get a perfectly accurate timer that will run exactly the same on all devices?

# Answer
> 2 votes
Basically, your Log statement is taking up a few milliseconds, so what your code is actually doing looks sorta like this from a time perspective:

|---------1 sec------|-Log-|---------1 sec------|

As Mr. Beast said, you should use time += 1000000000;, not time = System.nanoTime();

---
Tags: android, timer, realtime
---


title: Pathfinding avoid a list of polygon

text:
# Question
Title: Pathfinding avoid a list of polygon
i'm working on a 2D RTS project, no tile-based map. I have a problem on building map data structure & algorithm for that. I already think of a naive algorithm to solve that. Of course it's very slow. I'm looking for an advice from who experienced :D

At very first, i have a list of obstacle as polygon like that

i decided to build a pathfinding graph, then i travel all pairs of node, connect them if the connection segment doesn't intersect any polygon. this process have O(n^2) time complexity.

after that, on every path query, i try connect every node to A(startnode) and B(goal node), then do dijstra to find path. this process have O(2n) + O(nlogn) time complexity.

That's all, my algorithm works fine(even it's slow) if the environment is static, no insert, remove obstacle. But when the environment turn to dynamic, such as a obstacle removed, i need to rebuild pathfinding graph(O(n^2)), my fps extremely decreased, 120 to 10.

Is there a more professional aproach to solve my problem?

# Answer
i found a solution, it's recastnavigation and detour by memononen.

the main idea are divide the map into many square, called tile. if the polygon doesn't fit the tile, it splitted. then each tile, we can considered it as a map. when a new obstacle placed, only the tile it belong must rebuild.

it's sound simple, but with some cache tricks, performance improved significantly.

thanks for the support!
> 1 votes

---
Tags: algorithm, path-finding
---


title: Using normals in DirectX 10

text:
# Question
Title: Using normals in DirectX 10
I've got a working OBJ loader that loads vertices, indices, texture coordinates, and normals. As of right now it doesn't process texture coordinates or normals but it stores them in arrays and creates a valid mesh with the vertices and indices.

Now I am trying to figure out how can I make the shader use the correct normal in the array for the current vertex if I can't `setnormals()` to my mesh. If I were to just use an index in my array of normals corresponding to the index in the vertices, how would I retrieve the current index the shader is processing? BTW: I am trying to write a blinn-phong shader technique.

Also when I create the input layout and I've added the semantic `NORMAL` to it, how would I list the multiple semantics in that single parameter? Would I just separate it with a space?

PS: If you need to see any code, just let me know.

# Answer
> 1 votes
Your question is slightly ambigious, but if you're actually asking if you can use the triples to sample buffers arbitrarily from your shader, you can (in D3D11) use some `StructuredBuffer<T>` in your shader and index those with each of your index values. If you're stuck on D3D10, you could make a horrible approximation with Vertex-Texture-Fetch from a FP texture holding your geometry values. If this is not what you wanted to know, read below on how to make an multi-indexed mesh single-indexed.

When D3D (and OpenGL) does indexed rendering they sample the streams of attributes at the same index in all vertex attribute streams. This means that if you've got index `i`, you get a vertex made up of `position[i]`, `texcoord[i]`, and `normal[i]`.

OBJ on the other side has faces made up of separate indices for each attribute, where a triple `p/t/n` is intended to gather `position[p]`, `texcoord[t]`, `normal[n]`.

The traditional way to solve this is to while processing your OBJ file, you build a new set of single-indexed vertices. This can be as easy as gathering the attributes corresponding to the `p/t/n` triples, putting the corresponding attributes into a sequence and using the sequence position as the single-index to use.

An optimization is to keep track of which elements of the new buffer corresponds to the attributes for a `p/t/n` triple and reuse those elements if the same triple occurs multiple times, with a `map<Triple,Index>` or so.

---
Tags: c++, shaders, directx, normals
---


title: Deterministic calculation in JavaScript

text:
# Question
Title: Deterministic calculation in JavaScript
I want to create a multiplayer game with HTML/JavaScript and only send user input between players. I read some articles for C++, saying that I could not expect floating point to get the same results on different binaries/machines. I expect the situation to be no better in JavaScript.

Do I need to use fixed point? Assuming fixed point is the way, can I calculate e.g. (estimated reciprocal) square roots using floating point functions exposed thru JavaScript, and then apply something akin to rounding to get determinism?

# Answer
JavaScript as a language does not support any number formats but 64 bit floating point numbers so you can't use true integers (integers in the range of -2^53 to 2^53 can be accurately represented).

Most likely it would be possible to make floating point numbers "act" deterministic through proper rounding and other techniques, however this will require a *lot* of discipline to make and be very hard to debug. Even big game developers like Blizzard struggle with making a game that functions correctly from solely the player inputs.

The problem with floating point differences between computers aren't *that* big, the problem is they accumulate over time and get worse as play progresses, probably the easiest thing to do would be to send player input every network tick and send the variables (position, orientation, etc) of *part* of the game objects along with it. That way you keep bandwidth minimal while keeping the game visually consistent.
> 0 votes

---
Tags: javascript, floating-point
---


# Question
Title: Persist emitted particles in scene after particle system has ended/destroyed?
In Unity, is is possible to persist emitted particles in a scene after the system has ended or even possibly destroyed?

I have a particle system attached to my player prefabs that does a rudimentary blood splatter, and I'd like for the emitted "blood" particles to stay in the scene for as long as the scene is active, even after the player prefab that originally emitted the particles is destroyed.

# Answer
This should do the trick (for the new *Shuriken* particle system):

```
Transform PE = transform.Find("exhaustPE");
PE.particleSystem.Pause();
PE.gameObject.parent = null;

```

The lines below apply to the Unity legacy particle system (version \< 3.5):

```
public ParticleEmitter emit;

// Call this immediately before you destroy your missile
public void DetachParticles()
{
    // This splits the particle off so it doesn't get deleted with the parent
    emit.transform.parent = null;

    // this stops the particle from creating more bits
    emit.emission = 0;

    // This finds the particleAnimator associated with the emitter and tells
    // it not to auto delete the particles.
    emit.GetComponent<ParticleAnimator>().autoDestruct = false;
}

```

Both code samples are taken from the Unity3D forums (sample 1 and sample 2).
> 2 votes

---
Tags: unity, particles, shuriken
---


title: Size of modern games

text:
# Question
Title: Size of modern games
As a non-game developer, I'm always stunned by the sheer size of modern games. For example, last night I downloaded Killzone for my PS4 and it clocked in at over 30GBs, which to me is absolutely insane, I mean that's several times larger than entire OSes!

Why are modern games so big? Are you guys using like RAW images?

# Answer
There's a huge amount of content in a large scale game. Textures can be large, but are less of a contributor than video and audio.

Depending on audio quality, size can vary quite incredibly. A 4 minute flac encoded song can be 100mb alone. When you reach the level of hours of dialog, even a more lossy format will take up a lot of space.
> 1 votes

---
Tags: software-engineering
---


# Question
Title: How can I efficiently implement a bitmask larger than 64-bits for component existence checks?
In my ECS implementation, I use bit-wise operations (as described and illustrated in this thread) to tell an entity what type of components it currently consists of. So my `Entity` class has the following member:

```
unsigned long m_CompMask;

```

The different component types are then defined as an `enum`, whose member values are all power of two:

```
enum ComponentType
{
    COMP_TYPE_UNKNOWN                   = 0,
    COMP_TYPE_PERSON                    = 1,
    COMP_TYPE_RENDERABLE                = 2,
    COMP_TYPE_MOVEABLE                  = 4,
    [...]
};

```

Each time a new component is added to my entity instance, I do the following bit operation to update the mask (where newType is a member of the `enum` mentioned above):

```
m_CompMask |= newType;

```

This approach enables me to efficiently check if a certain entity instance has a certain component (and hence might be relevant for a specific system), like so:

```
return (m_CompMask & type);

```

The limiting factor in this approach however is the `m_CompMask` variable since it won't be able to handle more than 64 component types (if I increase it to `unsigned long long`).

I don't expect to be needing more than that in my current project, but nonetheless I'd like to hear some ideas regarding alternatives that allow more than 64 types (as big games certainly need to) while still maintaining the ease and efficiently of those bit-wise operations as much as possible? Any ideas how this is handled in *"proper big"* projects?

# Answer
> 8 votes
To add to the other answers here, you can use something like in the following code to have a bit set of arbitrary length that grows on demand. This method even lets you do a simple form of compression; if your most common components have the lowest ID values, the majority of your entities will use a small amount of bitset memory to track their components, but ones that use rarer components will still operate properly.

```
/// <summary>
/// A resizable collection of bits.
/// </summary>
public class BitSet {
    const int BitSize = (sizeof(uint) * 8) - 1;
    const int ByteSize = 5;  // log_2(BitSize + 1)

    uint[] bits;

    /// <summary>
    /// Initializes a new instance of the <see cref="BitSet"/> class.
    /// </summary>
    public BitSet () {
        bits = new uint[1];
    }

    /// <summary>
    /// Determines whether the given bit is set.
    /// </summary>
    /// <param name="index">The index of the bit to check.</param>
    /// <returns><c>true</c> if the bit is set; otherwise, <c>false</c>.</returns>
    public bool IsSet (int index) {
        int b = index >> ByteSize;
        if (b >= bits.Length)
            return false;

        return (bits[b] & (1 << (index & BitSize))) != 0;
    }

    /// <summary>
    /// Sets the bit at the given index.
    /// </summary>
    /// <param name="index">The bit to set.</param>
    public void SetBit (int index) {
        int b = index >> ByteSize;
        if (b >= bits.Length)
            Array.Resize(ref bits, b + 1);

        bits[b] |= 1u << (index & BitSize);
    }

    /// <summary>
    /// Clears the bit at the given index.
    /// </summary>
    /// <param name="index">The bit to clear.</param>
    public void ClearBit (int index) {
        int b = index >> ByteSize;
        if (b >= bits.Length)
            return;

        bits[b] &= ~(1u << (index & BitSize));
    }

    /// <summary>
    /// Sets all bits.
    /// </summary>
    public void SetAll () {
        int count = bits.Length;
        for (int i = 0; i < count; i++)
            bits[i] = 0xffffffff;
    }

    /// <summary>
    /// Clears all bits.
    /// </summary>
    public void ClearAll () {
        Array.Clear(bits, 0, bits.Length);
    }

    /// <summary>
    /// Determines whether all of the bits in this instance are also set in the given bitset.
    /// </summary>
    /// <param name="other">The bitset to check.</param>
    /// <returns><c>true</c> if all of the bits in this instance are set in <paramref name="other"/>; otherwise, <c>false</c>.</returns>
    public bool IsSubsetOf (BitSet other) {
        if (other == null)
            throw new ArgumentNullException("other");

        var otherBits = other.bits;
        int count = Math.Min(bits.Length, otherBits.Length);
        for (int i = 0; i < count; i++) {
            uint bit = bits[i];
            if ((bit & otherBits[i]) != bit)
                return false;
        }

        // handle extra bits on our side that might just be all zero
        int extra = bits.Length - count;
        for (int i = count; i < extra; i++) {
            if (bits[i] != 0)
                return false;
        }

        return true;
    }
}

```

Likely to be completely robust you'd want to implement some of the framework interfaces such as IEquatable and IComparable and override a few operators, GetHashCode, etc.

# Answer
> 3 votes
Maybe you could use a C-style bitfield and just add new fields as needed.

```
struct ComponentIds {
    bool person     : 1;
    bool renderable : 1;
    bool movable    : 1;
    bool ai         : 1;
    // and so on...
};

class GameObject {
public:

    ComponentIds componentsUsed;
};

```

Since you only need boolean flags, a bitfield struct would be a lot smaller than simple *bools* and gives the same results and ease of use:

```
GameObject * go = ...
if (go->componentsUsed.ai)
{
    // has AI component
}

```

# Answer
> 1 votes
A simple example of a data structure that fills this purpose:

```
class LongerBitMask {

    //mask1_mask2

    long mask1
    long mask2

    public LongerBitMask() {
        mask1 = 0
        mask2 = 0
    }

    public LongerBitMask(long m1, long m2) {
        mask1 = m1
        mask2 = m2
    }

    public void OR(LongerBitMask other) {
        this.mask1 |= other.mask1
        this.mask2 |= other.mask2
    }

    public bool Match(LongerBitMask other) {
        return (this.mask1 & other.mask1) && (this.mask2 && other.mask2)
    }
}

```

Now, your enums can either index into a dictionary, or array of some sort. It's a bit harder to manage I suppose, but I haven't thought much about this end of things.

Perhaps just have an array of `LongerBitMask` that is generated automatically? Then index into it using the enum? Just make sure to only add to the end of the enums. Otherwise you'll have components that change values.

Some static code:

```
void CreateComponentBitMasks()
{
    LongerBitMasks[] bitMasks
    int index = 0

    bitMasks[index++] = new LongerBitMask(0, 0)

    for(int m2 = 0; m2 < 63; m2++) {
        bitMasks[index++] = new LongerBitMask(0, 1<<m2)
    }

    for(int m1 = 0; m1 < 63; m1++) {
        bitMasks[index++] = new LongerBitMask(1<<m1, 0)
    }
}

```

Set your components to their default enum values, 0 through 127 (don't make them power of two). Then you can retrieve your bit masks with:

```
bitMasks[COMP_TYPE_RENDERABLE]; //would return bit mask with values 0, 2

```

Now your systems will define their own `LongBitMask` values and compare against entities using `Match`.

Like a system would create its own bit mask with:

```
//creates a bit mask to match components that are a renderable person.
LongerBitMask thisSystemMask = new LongerBitMask()
thisSystemMask.OR(bitMasks[COMP_TYPE_RENDERABLE])
thisSystemMask.OR(bitMasks[COMP_TYPE_PERSON])

```

Likely something wrong in my bit shifting or other math...

# Answer
> 0 votes
It is indeed easily possible to use more than 64 components even in a moderate scope game.

Create you own bitset class which can hold a mask of arbitrary length.

# Answer
> 0 votes
I don't know how this is implemented in AAA games, but your problem seems quite simple for me. You just need to fuse together:

* Memory region holding enough bits.
* Way to manipulate given bits by index.

Here is my example code, in C++11. I hope you can translate it into whatever you are using, but if you can't, feel free to ask me. I think I saw something similiar in boost, but can't remember right now.

```
#include <iostream>

struct BitProxy
{
    char &ByteRef;
    char Mask;

    BitProxy& operator=(bool v)
    {
        if(v) {ByteRef |= Mask;}
        else {ByteRef &= ~Mask;}
        return *this;
    }

    operator bool() const {return ByteRef & Mask;}
};

template <unsigned NumBits, typename EnumType, typename UnderlyingType>
struct EnumSet
{
    // how much bytes we need
    static constexpr unsigned Size = (NumBits - 1) / 8 + 1;
    char Bytes[Size];

    BitProxy operator[](EnumType v)
    {
        unsigned byte_ix = unsigned(UnderlyingType(v)) / 8;
        unsigned bit_ix = unsigned(UnderlyingType(v)) & 7;
        return BitProxy {Bytes[byte_ix], char(1 << bit_ix)};
    }
};

namespace Component
{
    enum class Id : unsigned
    {
        One,
        Two,
        Three,
        c4, c5, c6, c7, c8, c9, c10,
        // this special one will tells us how much bits we need
        Last_
    };

    static constexpr Id AllIds[] =
    {
        // well...
        Id::One, Id::Two, Id::Three, Id::c4, Id::c5, Id::c6, Id::c7, Id::c8, Id::c9, Id::c10
    };

    typedef EnumSet<unsigned(Id::Last_), Id, unsigned> Set;
}

int main()
{
    Component::Set cs {};
    cs[Component::Id::Two] = true;
    cs[Component::Id::c7] = true;
    for(Component::Id id : Component::AllIds)
        std::cout << unsigned(id) << " -> " << (cs[id] ? "true":"false") << std::endl;
}

```

http://coliru.stacked-crooked.com/a/63904a428e95df94 Output:

```
0 -> false
1 -> true
2 -> false
3 -> false
4 -> false
5 -> false
6 -> true
7 -> false
8 -> false
9 -> false

```

Used struct insted of class for simplicity, but I advise to properly encapsulate it.

---
Tags: entity-system, component-based
---


title: Terrain & Multi-Texturing

text:
# Question
Title: Terrain & Multi-Texturing
I'm using OpenGL (Version 4.4) (and C++ if that matters).

I've created a terrain renderer, the terrain is stored as a 3D scalar field (isosurface/voxels). It uses a slightly modified version of Marching Cubes, to perform polygonization (converting the scalar field to triangles).

Currently I'm texturing the terrain using a horizontal (grass) texture and a vertical (dirt) texture. Then when applying the texture I simply calculate the amount of the horizontal and vertical texture that is required on the current triangle, depending on the normals of the current triangle. *Thereby the more a normal is pointing upwards (or downward) the more dominant the horizontal (grass) texture will be.*

### Terrain Renderer in Action

Fullscreen Image

Now the question is, what would be the best (or a good) way to perform Multi-Texturing on the terrain? I will give all the values in the *scalar field* a *voxel type* value as well. So the main question is how should the rendering be handled. I have a couple of ideas of how this could be done, but I'm not sure which of my ideas would be the best one to do or if there's even a better way.

### First Idea

* Bind all the needed textures, thereby call `glActiveTexture(...)` for each texture there is.
* Now the mesh can be rendered using a single `glDraw*(...)` call.
* This of course only works if the Shader knows when and where to use each texture, or that the info for using each texture, is stored within the buffer, as some sort of value which the Shader uses, to "detect" which texture should be used. As mentioned previously this could be the *voxel type* value.

***Problem:*** *The maximum amount of textures which can be bound simultaneously is very limited, so that could (and probably would) create some problems.*

### Second Idea

* Bind a single texture and call `glDraw*(...)` with a specific `first` and `count` value, so that only a part of the mesh is rendered. Which of course is the part which uses the bound texture.
* Thereby loop the above until the whole mesh is rendered using all the individual textures.

I don't see any real problem with this idea, the only extra thing we need to take in mind, is that all the triangles need to be sorted according to their `voxel type` value.

Though we wouldn't be able to fade the textures, like in the image above.

### Third Idea

* Split the mesh into individual buffers (VBOs and VAOs), so that each buffer only uses a single (or a couple) texture(s). Basically the same as the *Second Idea* though here the buffer would physically be split according to the textures.

### Fourth Idea?

or is there an even better way?

### Side Note

* Each texture has it's own handle, thereby none of them can be used as a *Texture Atlas*.

# Answer
> 2 votes
Instead of `glActiveTexture` you could bind a texture array and sample as many texture you like... BUT!! That is expensive, if you have 16 layer, you will read 16 samples and then probably only one or two will be predominant.

You can bind a texture array and then specify the index of the two (or three) most predominant textures and the sampling weight.

Sampling weight and index can be other textures or parameters passed by vertex.

# Answer
> 1 votes
If you're creative with what data you pack into your verts, you can build a texture atlas.

Basically, you need 3 sets of UV data, rather than the usual single set. Each represents the mapping for one of the 3 textures used by that triangle. Your color channel will determine how much these will show through.

With a voxel field, you can work out this blend through distance from the vertex.

# Answer
> 0 votes
From the options you suggested, I would stick with splitting the mesh into sub-meshes sorted by material/texture. This might actually be faster to render if your data set is really huge. OpenGL draw calls might fail due to out-of-memory conditions, though you'd have to push it really hard to make it happen.

That said, if you are really serious about optimizing your terrain renderer, you'll probably want to do some research on Virtual Texture Mapping (sometimes referred to as "Megatextures"). This is probably the most efficient way there is to manage large texture data sets.

---
Tags: opengl, c++, textures, rendering, terrain
---


# Question
Title: What are the advantages/disadvantages of using a polar coordinate system in a video game?
Would it ever be a good idea to represent an object's position as a magnitude at some angle relative to a reference point, instead of the typical x, y, z coordinates?

What sort of effect would it have on performance?

Clearly there are many disadvantages to this, such as having to convert into x, y, z coordinates when rendering, and possibly suffering from gimbal lock, but would there ever be a circumstance where it would be a better solution to use polar coordinates?

# Answer
## Short answer:

Polar coordinates are a non Euclidean coordinate system. This means that lines created in this coordinate system are not straight, so it isn't usually used as the primary coordinate system in a game, but rather are used in conjunction with standard Cartesian coordinates when there is a use for Polar coordinates.

One common usage of polar coordinates, is positioning objects around each other. This can be used to make an object orbit around another object.

### Polar coordinates in 3D:

Polar coordinates can also be used in three-dimensional games. Except they are not called polar coordinates in 3D, they are called "Spherical coordinates". Spherical are used for basically the same thing that they are used for in 2D, except they can have an additional usage.

Image from Wikipedia: Original Wiki page.

The difference between Polar and Spherical coordinates, is that Spherical coordinates also have a Φ (Phi) component in addition to the θ (Theta) and r (radius) components.

Spherical coordinates can be used for creating three-dimensional orbits in addition to creating a camera LookAt matrix (you can read more about this on this page).
> 5 votes

---
Tags: coordinates
---


title: 2D collision detection

text:
# Question
Title: 2D collision detection
Let's assume I'm using this character.

<sub>(source: iconbug.com)</sub>

How would you implement collision detection for it? Using a bounding box doesn't seem to be a good approximation, because the bird's shape is nowhere near a square.

I was thinking of having a sort of quad tree data structure inside the object that represents portions of the image. Each leaf could be either `false` (in case it covers the white/transparent space outside the bird) or `true` (in case it represents an area of the bird i.e. beak, eye etc). Then somehow test **the only obstacle in the scene** for collision with the bird.

But my problems in my approach are:

1. I don't know how to initialize the quad tree.
2. Once the quad tree is initialized, I'm not sure how to traverse & use it once the obstacle is within the coordinates of the image.

How would you do collision detection with non-squarish characters?

LE: The other approach I've seen was to use multiple bounding boxes. For example I'd have one or a few bounding boxes for the beak, then a few of them for the hair or the tail. But it can get tedious. If this is a valid approach in my case, how would I generate those bounding boxes? I doubt I'd have to have them hardcoded in my program.

LE2: I care about fairly precise collisions. I can't imagine how a single bounding box or circle can at least approximate decently that shape, so this approach won't work.

# Answer
> 12 votes
Circle collider. Good enough for it I would say unless you're doing something fancy with certain parts being affected by physics or the colliding looking unnatural, and even if you need to split it up into several parts I have one thing to say to you:

Don't overcomplicate it.

You don't need a full quad tree structure for this. Just have several boxes or circles in a straight array, and then intersect with all of them. This can't possibly be performance critical enough and you won't gain that much from using a quad tree.

# Answer
> 14 votes
A two step check process

**On the first step, you check the bounding box**, and if there is no collision there, then the test is over. If there is collision, you move over to the second pass

**On the second pass**, if you want more precision, and you want a true pixel perfect solution, then you can do just that, a **pixel perfect check pass**

Since your image is a PNG (or any other file format that contains an alpha channel) this would be rather easy

> 1. Calculate the intersection area between that one object in the scene and the bird, generating a simple rectangle of intersection on both images
> 2. Within that intersection, check that each pixel has an alpha value \> 0 in BOTH images
> 3. If any such pixels exist, you got your collision. Otherwise no

If you look at your images alpha channel, you can see how it already has all the information you might need for pixel perfect collision

*Pixel perfect collisions are usually expensive, so doing a rough estimate at first with a bounding box or a more detailed collision figure (Like the one Anko suggested) may save you some precious time*

The "finer" detailed collision bounding box Anko suggested:

PS: If your image has a halo, an effect or other non-0 alpha channel around it that you don't want to collide with, the algorithm threshold can easily be adjusted to accommodate that

# Answer
> 3 votes
I would use a circle for the body and a single rectangle for the beak, but that's just my opinion. Overcomplicating your collision geometry can slow down your app though, you're practically doubling (or more) the number of characters on-screen.

# Answer
> 0 votes
Maybe you could use some kind of wonky polygon/edge collider.

Not sure exactly how this would work, but:

two objects: object 1: the bird (o1), object 2: the thing that might hit the bird (o2)

1) Define a bounding shape that is a polygon that fits closely to the first object (o1) in question.

2) Get the edges of o1, o2 that could conceivably collide without could conceivably collide without o2 passing *through* o1 or vice versa.

With the position and size of the shape (o2) you could probably isolate edges (of o1) which can't conceivably be hit, whether it's becauses they are "behind" another edge (of o1) which is closer to o2. If you had a right triangle whose hypotenuse faced up and right and a rectangle approaching it straight on (with the long side along the x-axis) then you can tell which edges to omit because they're beginning and end y values are both either above or below the rectangle.

3) Determine if one of the points on an edge of o2 is the same as a point on any of the edges of o1 that you selected in step 2.

this concept probably works best for colliding polygons (i.e. things with clear edges), but maybe you can treat a circle as one long edge (e.g. if o2 was a circle).

---
Tags: android, opengl-es2
---


# Question
Title: Java 2D World: Convert from mouse screen co-ords to screen co-ordinates?
I have a 2D world background made up of a Grid of graphics, which I display on screen with a viewport (800x600) and it all works.

My question is I have the following code to

convert the mouse co-ordinates to world co-ordinates

then

World co-ordinates to grid co-ordinates

then

grid co-ordinates to screen co-ordinates.

```
//Add camerax to mouse screen co-ords to convert to world co-ords.
int cursorx_world=(int)camerax+(int)GameInput.mousex;
int cursorx_grid=(int)cursorx_world/blocksize;  // World Co-ords / gridsize give grid co-ords
int cursorx_screen=-(int)camerax+(cursorx_grid*blocksize);

```

So is there anyway I can convert straight from mouse screen co-ords to screen co-ordinates?

# Answer
Something I use fairly often is a `viewbounds` variable, which is a list of three game coordinates. The first is the upper-left corner of the screen, the second is the center, and the third is the bottom right. I also use `zoom` (which looks like your `blocksize`).

When you register a mouse event, you can find its game coordinate by offsetting from the first viewbound by the coordinates of the mouse multiplied\** by the zoom level.

```
// Create a new Coordinate using a copy constructor
game_coor = new Coordinate(viewbounds[0]).add(mouse_coor.multiply(zoom));

```

---

\** Depending on your implementation zoom could be px/unit or unit/px, multiply or divide accordingly.
> 1 votes

---
Tags: java, 2d
---


# Question
Title: Pixel Perfect collision detection on rotated bitmaps
I have two bitmaps which are being drawn onto a canvas using a matrix

```
canvas.drawBitmap(bitmap, matrix, paint);

```

first to work out if I need to check for a collision i am using eucilidean vectors as such

```
//vector between the bitmaps
float vx = bitmap2.x - bitmap1.x;
float vy = bitmap2.x - bitmap1.x;

//magnitude of the vector between the two bitmaps
float m = Math.sqrt( (vx*vx)+(vy*vy) );

if( m < bitmap1.getDiagonalWidth() + bitmap1.getDiagonalWidth())
{
    //pixel perfect collision detection required
}

```

Firstly, is this the best way to approach this part of the collision detection?

Secondly once I have found that a collision is possible, do I need to do anything before throwing the bitmaps into a method that runs pixel perfect collision detection? basically, is the issue complicated because of the rotation of the images?

edit\* it is possible that the bitmaps will also be scaled by the matrix. i would imagine that this will complicate things further.

# Answer
> 1 votes
If you can generate proper matrices for the objects for translation & rotation, you can solve this pretty much straight-forwardly

Let's assume object A has the translation & rotation matrix **mat\_A** and object B has translation & rotation matrix **mat\_B**

You need to loop over pixels in A and if it has an alpha value \> 0 (or a custom threshold you want) check which pixel of B is at this very position and check if this pixel also has a non-0 alpha channel

Using matrix mathematics, you can move the 2nd object into the first objects world space, to get the mapping between the pixels

You need to transform the global location to a local location in the space of object B. This is the **inverse of mat\_B**. So, we have to transform the local position in A with the following matrix:

```
matrix fromAToB = mat_A * Inverse_Matrix(mat_B);
//now iterate over each pixel of A
for(int x = 0; x < width_A; ++x) {
    for(int y = 0; y < height_A; ++y)
    {
        // check alpha channel
        if (alpha_value != 0) {
        //calculate the position in B
            Vector pos_in_A = new Vector2(x, y);
            Vector pos_in_B = Vector2.Transform(posInA, fromAToB);
            //use width_B & height_B to make sure the point is within the object
            if (point_inside_B) {
                //round posInB.X and posInB.Y to integer values
                //check if the pixel is transparent
                //if pixel is not transparent, you got collision
            }
        }
    }
}

```

This is not really proper Java code, mostly pseduo-code, but I think it conveys the idea well

---
Tags: java, android, collision-detection
---


# Question
Title: Box2d stopping the movement of an object
I am in the process of making a game and I need an object to move only when the buttons are pressed. I have a method that begins the movement, and so far I am ending the movement of an object by having destroying the body of the object. The problem that I have is that every subsequent time that I try and move the ship the program crashes.

Here is my code.

Initializer method that contains the shipBody and its definition.

```
-(id) init
{
    if( (self=[super init])) {

        CGSize s = [CCDirector sharedDirector].winSize;

        //create spaceShip sprite and add it to the layer
        _ship = [CCSprite spriteWithFile:@"theShip.gif" ];
        _ship.position = ccp(s.width/2, 1.25*_ship.contentSize.height);
        [self addChild:_ship];

        //create the world
        b2Vec2 gravity = b2Vec2_zero;
        _world = new b2World(gravity);

        //create ship body
        b2BodyDef shipBodyDef;
        shipBodyDef.type = b2_dynamicBody;
        shipBodyDef.position.Set((s.width/2)/PTM_RATIO, (1.25*_ship.contentSize.height)/PTM_RATIO);
        shipBodyDef.userData = _ship;

        if(_shipBody == NULL){
        _shipBody =_world->CreateBody(&shipBodyDef);
        }

        //create ship shape
        b2PolygonShape shipShape;
        shipShape.SetAsBox(_ship.contentSize.width/PTM_RATIO/2, _ship.contentSize.height/PTM_RATIO/2);

        //create Ship definition and add to body
        b2FixtureDef ShipShapeDef;
        ShipShapeDef.shape = &shipShape;
        ShipShapeDef.density = 3;
        ShipShapeDef.friction =0;
        ShipShapeDef.restitution =0;
        _shipFixture = _shipBody->CreateFixture(&ShipShapeDef);

        ......
}

```

When the paddle is pressed and movement happens logic. THis is related to the problem since this is how movement of a sprite is achieved in the first place.

```
-(void)ccTouchesBegan:(NSSet *)touches withEvent:(UIEvent *)event
{
    //Set up a way for touches to be turned into locations onscreen
    NSSet *allTouches = [event allTouches];
    UITouch *touch = [allTouches anyObject];
    CGPoint location = [touch locationInView:[touch view]];
    location = [[CCDirector sharedDirector] convertToGL:location ];

    //check to see if Left Paddle is being pressed
    if (CGRectContainsPoint([_paddle1 boundingBox], location)){
        b2Vec2 force = b2Vec2(-5,0);
        _shipBody->ApplyLinearImpulse(force, _shipBody ->GetPosition());
        }
    if (CGRectContainsPoint([_paddle2 boundingBox], location)){
        b2Vec2 force = b2Vec2(5,0);
        _shipBody->ApplyLinearImpulse(force, _shipBody->GetPosition());
    }
}

```

Logic for when touches stop. This is the problem area since destroying the shipBody stops all future movement as well.

```
-(void)ccTouchesEnded:(NSSet *)touches withEvent:(UIEvent *)event
{
    _world->DestroyBody(_shipBody);
 }
 @end

```

# Answer
I modified the ccTouchesBegan method to the following:

```
-(void)ccTouchesBegan:(NSSet *)touches withEvent:(UIEvent *)event
{
    //Set up a way for touches to be turned into locations onscreen
    NSSet *allTouches = [event allTouches];
    UITouch *touch = [allTouches anyObject];
    CGPoint location = [touch locationInView:[touch view]];
    location = [[CCDirector sharedDirector] convertToGL:location ];

    //check to see if Left Paddle is being pressed
    if (CGRectContainsPoint([_paddle1 boundingBox], location)){
        b2Vec2 force = b2Vec2(-5,0);
        _shipBody->SetLinearVelocity(force);
        }
    if (CGRectContainsPoint([_paddle2 boundingBox], location)){
        b2Vec2 force = b2Vec2(5,0);
        _shipBody->SetLinearVelocity(force);

    }
}

```

and the CCTouchesEnded to:

```
-(void)ccTouchesEnded:(NSSet *)touches withEvent:(UIEvent *)event
{
    _shipBody->SetLinearVelocity(b2Vec2(0,0));

}

```

Using setLinear Velocity over applying linear impulse allows for the velocity to be changed if the buttons are no longer being pressed. Applying linear impulse can't be stopped, but only dampened which would require me to write additional code to create a dampening method in the ccTouchesEnded.
> 0 votes

---
Tags: ios, box2d, objective-c
---


# Question
Title: How to generate caves that resemble those of Minecraft?
I've been working on a 3D procedural world for a while now and am wanting to start adding cave systems. I'm currently using 2D/3D Perlin Noise for the terrain generation in combination with Marching Cubes for smoother terrain. I'm just getting stumped when it comes to long interconnecting caves.

I'm hoping to get something more like Minecraft's cave systems. They seem to be very connected, branch off randomly in nearly any direction, and nearly any point in the cave would have a fairly circular look with a fairly equal radius throughout (not the best wording, but not quite sure how else to put it).

The biggest challenge for generating caves like I'm wanting is that I want to generate the world on the fly. The world is generated chunk by chunk currently, starting where the player is and it generates outwards from there. **I would NOT want to generate any of the world and then dig the caves out using a wandering pattern, cellular automata, etc.**

Are there any well known algorithms that can be used for this? If so, does anyone want to share how they do something similar? I'd greatly appreciate any help.

A good example:

# Answer
> 31 votes
Minecraft's caves are generated by "perlin worms" method. The generator snakes through terrain and caves out a tunnel. Minecraft **does not** use 3d perlin noise for cave generation, because it tends to leave unconnected pockets in the terrain. Minecraft caves have not been generated through 3d Perlin noise since very early Alpha versions.

Here are caves in Gnomescroll generated from the "perlin worm" method.

These are the libnoise "Perlin Worms" from the libnoise tutorial. The technique closely reproduces the caves generated in Minecraft.

The snaking parameters affects the quality of the cave system and determine how vertical the caves are and how fast they change direction. Caves in minecraft branch and the radius of the cave tunnel is varied over the length of the caves.

Minecraft generates the caves on a chunk by chunk basis. The approach required is complicated and no one has perfectly reverse engineered Minecraft's cave generator yet, despite interest by server modders.

The most likely approach generates the snaking caves chunk by chunk as the infinite map is generated and expands outward. The caves on the current chunk are functions of the cave seeds on the closest N chunks for some N. Using a random number generator which is a function of chunk coordinates to seed the caves it is possible to compute the caves on the current chunk for an infinite map while only evaluating the chunks within a finite chunk radius.

# Answer
> 7 votes
I would generate a cloud of points inside areas where the terrain is solid - you can experiment with different densities. Then I would use an algorithm like a minimum spanning tree to connect all of the points - this will ensure that every area is reachable. Then simply draw big hollow (composed of air) areas from node to node (i.e. a thick line of voxels).

# Answer
> 3 votes
Game Developer Magazine's April 2011 issue goes into detail on this with iterative Perlin noise functions - see the Creator of Worlds article starting on page 21.

# Answer
> 1 votes
Use a noise function to assign values for every chunk to determine if it has tunnels or not and then use them to decide where to place caves. If you want tunnels, simply use more noise functions (with different seeds) and use their values to determine if there are tunnels. After that, use ordinary "drawing" functions to create the tunnels. To make everything more realistic, use more noise to do random displacement for origin points of said caves/tunnels.

If you don't want to use multiple noise functions, you can probe at bigger distances - for example, rather than do noise3d(2,2,2) for chunk at (2,2,2) do noise3d(2,2,16) and use (2,2,16) for one value, (2,2,17) for second value, etc.... then just tune your frequency accordingly to either make all the values independent or correlated at short scales.

To vary cave density thorough the world, use another, lower frequency function that will influence said values.

In case this results in messy caves, simply increase distance of said interconnected points or otherwise tune the algorithm.

I'm not sure if Minecraft does caves like this(although I think it does), but this solution should yield satisfactory results.

# Answer
> -6 votes
Although most caves such as the ones above use **Perlin worm**, some people would rather do it manually. This way they can make it the way they want it exactly block for block. A cave made by using **Perlin worm** can be inaccurate and may only make the cave 5 foot high and 6 foot wide, this can be inaccurate as you might want it 10 foot high and 15 foot wide.

---
Tags: 3d, algorithm, procedural-generation, terrain
---


title: Top-down player collision with walls

text:
# Question
Title: Top-down player collision with walls
I am having trouble trying to think of how I am going to approach collisions in my game. My idea which sucked in the beginning because it would reduce performance dramatically has failed which was when I was updating the list of walls it would check collision with players but the player would just stop and wouldn't be able to move anymore. Collision not only has to work with player but with at least 15-20 other entities in the game as well. Does anyone have a good idea to check collision with a top down shooter?

Here is my update method with everything being updated:

```
public void update(float dt){

    inputHandler();

    //Update the player
    player.update(joystick1, joystick2, projectiles, dt);
    updateCamera();

    //Update them zombies
    for(int i = 0; i < enemies.size(); i++){
        Enemy e = enemies.get(i);
        e.update(player, dt);
        if(e.getDistanceFromPlayer() < 60){
            //check collision
            if(e.collided(player)){
                player.hit(e, particles);
            }
        }
    }

    //Update Projectiles
    for(int i = 0; i < projectiles.size(); i++){
        Projectile p = projectiles.get(i);
        p.update(dt);
        //Check if projectile has hit any enemies
        for(int j = 0; j < enemies.size(); j++){
            Enemy e = enemies.get(j);
            if(p.collided(e)){
                p.remove();
                e.hit(p);
                ParticleEmitter.createBloodParticle(particles, e.getX(), e.getY(), 5, 500, 10);
            }
        }
    }

    //Update Items
    for(int i = 0; i < items.size(); i++){
        Item item = items.get(i);
        if(item.collide(player)){
            if(item instanceof Ammo){
                player.getCurrentGun().addAmmo(item.getAmount());
            }
            if(item instanceof Health){
                player.addHealth(item.getAmount());
                if(player.getHealth() >= 100){
                    player.setHealth(100);
                }
            }
            item.remove();
        }
    }

    //Update them particles
    for(int i = 0; i < particles.size(); i++){
        Particle p = particles.get(i);
        p.update(dt);

    }

    int numberOfObjectInGame = 1 + walls.size() + enemies.size() + items.size() + particles.size() + projectiles.size();
    System.out.println(numberOfObjectInGame);

    logger.log();

}

```

I don't know when to check for collisions. Should it be done in the update method or in the player update method, or at some other point? Really confused at this point.

**EDIT:**

Ok so added 4 rectangle bounds to my player and had each one checked to see if they have collided with a wall. So right now it is working but i'm pretty sure this is horribly inefficient. Any way to make this more efficient...

Here is the code:

```
for(int i = 0; i < walls.size(); i++){
        Wall w = walls.get(i);
        if(Intersector.overlaps(w.getBounds(), up)){
            if(velocity.y < 0){
                velocity.y = 0;
            }
        }
        if(Intersector.overlaps(w.getBounds(), down)){
            if(velocity.y > 0){
                velocity.y = 0;
            }
        }
        if(Intersector.overlaps(w.getBounds(), left)){
            if(velocity.x < 0){
                velocity.x = 0;
            }
        }
        if(Intersector.overlaps(w.getBounds(), right)){
            if(velocity.x > 0){
                velocity.x = 0;
            }
        }
    }

```

It is checked to see if the player is colliding with every wall and the problem is this is only the player. This has to check with every moving entity in the game. Is this a good way to implement this into a game or should I look into something else?

# Answer
> 1 votes
First thing is that your player is sticking to the wall because whenever it collides, you set the velocity in that direction to be zero ( `velocity.x=0;`). zero means it stops moving in that direction, which is exactly whats happening. What you want to do is `velocity.x=-velocity.x;` or `velocity.x*=-1;`. This makes the player move in the opposite direction with the same velocity.

Second is that you have your collision checking code is inside the player object, so it only checks the player's collision. If each object reacts differently to collisions then you have to add the appropriate code in each object.

If they are all gonna bounce around, then keep a common code in your update method and loop through all the entities on stage, accessing their fields (`up`, `down`, ...) to check for each collision.

Something like this in your main update method:

```
Entity[] entities={...};
for(int j=0; i<entities.length; j++){
for(int i = 0; i < walls.size(); i++){
    Wall w = walls.get(i);
    if(Intersector.overlaps(w.getBounds(), entities[j].up)){
        if(entities[j].velocity.y < 0){
            entities[j].velocity.y = 0;
        }
    }
    .
    .
    .
}

```

}

---
Tags: java, collision-detection, libgdx
---


# Question
Title: Converting between Spiral Honeycomb Mosaic and axial hex coordinates
There seems to be quite a lot of logic in dealing with hexagonal grids using a system of axial coordinates like the one described here.

In doing some reading about hex grids, though, I ran across the notion of the Spiral Honeycomb Mosaic (the links on that mirror are broken; the content is copied from here, about halfway down the page). It seems to be used mostly in image processing, but it's interesting from the standpoint that it assigns each hex a unique, sequential base-7 number as its identifier.

I'm not sure that it's actually *useful* for anything, but I'm wondering: **is it possible to convert back and forth between the SHM numbering system and axial coordinates?**

Both systems have methods to convert from a hex to the Cartesian coordinates of its center, so presumably one could calculate that out of one system, and then into the other. But that's messy and inefficient, and I'm convinced it's possible to do better.

Because of the fractal nature of the SHM, the conversion routine in the sample code provided relies on a loop; it seems like the general solution might involve a series?

# Answer
Thanks for a fascinating puzzle! Yes, it looks like we can do better than a conversion through cartesian coordinates of hexagon centers. It can be done entirely with integer math, though I've included a rational in a matrix below to keep the notation concise.

You're right that both the encoding and decoding processes require loops. Fortunately, because SHM works by orders of magnitude, the loops will never need more than Log\_7(n + 1) iterations, where n is the number of tiles in the grid, which is very reasonable.

To keep my notation symmetric, I've opted to use a 3-coordinate grid like the one below (what your example from Red Blob Games calls "Cube Coordinates"). If you prefer, you can omit the z coordinate and replace all instances of .z with -(x + y) to get "Axial Coordinates" instead.

For speed and cleanliness of code, I recommend using lookup tables for encoding and decoding. First, for decoding SHM into cube coordinates, you can build the table with these recurrences:

```
Rotate(v) = (-v.z, -v.x, -v.y)

Decode[,] = 2D array of ordered triples, [7 x (max_order_of_magnitude + 1)]

Decode[0, k] = (0, 0, 0) for all k = 0...max_order_of_magnitude
Decode[1, 0] = (0, -1, 1)

Decode[d + 1, k] = Rotate(Decode(d, k)) for d = 2...6, all k
Decode[d, k + 1] = Decode(d, k) + 2 * Rotate(Decode(d, k)) for all d, k

```

Then decoding becomes extremely simple:

```
SHMToPoint(code)
{
    point = (0, 0, 0)
    order = 0

    while(code > 0)
    {
        digit = code % 7
        point += Decode(digit, order)
        code = floor(code/7)
        order++
    }
    return point
}

```

This works because the first row of the table stores the offsets of the cells encoded by the digits 0, 1, 2, 3, 4, 5, 6. The next row stores the offsets for 0, 10, 20, 30, 40, 50, 60, and so on. By summing the offsets contributed by each order of magnitude, you can decode any point within the range of the table.

For encoding, I think the following method will work, but I'll confess I haven't tested it. It uses a much simpler lookup table:

```
Encode = [0, 5, 1, 6, 3, 4, 2]

```

and a rotation & scaling matrix:

```
Untwist = | 5  -4   2 |
          | 2   5  -4 |
          |-4   2   5 | * 1/21

```

To encode a cube coordinate into SHM, then...

```
PointToSHM(point)
{
    code = 0
    magnitude = 1
    while(point != (0, 0, 0))
    {
        digitIndex = (((point.x - 2 * point.y) % 7) + 7) % 7
        code += magnitude *Encode[digitIndex]
        point = Untwist * (point - Decode[digit, 0])
        // treating "point" as a column vector, and rounding if necessary
        magnitude *= 7
    }
    return code
}

```

Note that the code generated here (and decoded above) is in standard numeric format (ie. the cell marked "10" in the SHM diagram will be assigned a code of 7 in base 10, or 111 in binary). If you want to display it in base 7, you'll need to use the appropriate radix when converting it to a string.

This works by figuring out the least significant digit of the SHM code at each iteration, (using the fact that these digits repeat in a way that tiles the plane regularly - the LUT is the sequence of digits read from (0, 0, 0) to (6, 0, -6), which repeats at an offset every row). Next it effectively zeroes that digit by subtracting the corresponding offset from our Decode table earlier, and scales the fractal down one level using the Untwist matrix. This acts like a right shift in base-7, in geometric form - it brings the next digit into the least significant position, bringing cell "10" to "1" and so on, where we can use the same trick again to read that digit on the next loop.

I hope that works for you!
> 6 votes

---
Tags: mathematics, geometry, hexagonal-grid
---


# Question
Title: Passing a list of existing entities to a new client when using a component system?
My game server uses entities containing components to represent everything in the game world. This has worked great so far but I've run into a problem now that I'm allowing clients to connect to the server.

Basically the server needs to tell the connecting client about all the existing entities in the game, Since the player, the monsters, the trees etc. are all instantiated from the same Entity class I currently have no way of telling the client what each entity actually is.

What would be the best way of sending the entities to the client so that the client knows what components to add to each? The only thing I can think of is having a string "name" on the entity and then sending packets like this to the client...

```
{

     'action': 'create-entity',
     'data': {
         'entity-type': 'dragon',
         'x': 300,
         'y': 40,
     }
}

```

So now the client would know to call the "createDragonEntity" function to create the correct entity.

Any better suggestions?

# Answer
The problem you encountered is that you seem to have no clear way of serialising/unserialising your entities.

You can keep your `create<EntityType>()` functions to create initial versions of your entities, but you should be able to serialise the entities. And unserialising them should result in the same result as what was there before the serialisation process.

When you write an entity (to file or network stream) the resulting data should allow you to reverse the process and unserialise just as easily:

Serialized entity:

```
{
    'id':38,
    'transform':{'x': 300, 'y': 40, 'angle':0, scale:1},
    'movement':{'id':'walk', 'maxspeed': 30, 'turnrate': 180},
    'movement':{'id':'flight', 'maxspeed': 180, 'turnrate': 20},
    'weapon':{'id':'claws', 'dmg':[{'slash':300}], 'rate':0.25},
    'weapon':{'id':'firebreath', 'dmg':[{'fire':30}], 'rate':5, 'remaining':58, 'rr':2},
    'visual':{'model':'dragon_02', 'mainColor':'FF4921'},
    'dragonScript'{'anger':12.333333,},
    'health':{'hp':2004, 'hr':3},
    'intent':{script:[
        {'id':'move', 'movement':'walk', 'data':[1,0]},
        {'id':'fire', 'weapon':'firebreath'}]}
}

```

Here we can clearly rebuild the entity with an id, and all the components needed for the game to resume/start.

There are certain components you will want to avoid serialising (i.e. all components related to local behaviours like input or data which should be recomputed from the existing data).

But in the end a simple function to reload all components should do the trick:

Ex:

```
unserializeEntity(pojo) {
    var entity = null;
    var cmps = [];
    //Each key could be used to code the type of component...
    for(var componentType in pojo) {
        var cmp = createComponent(componentType, pojo[componentType]);
        if(cmp) {
            cmps.push(cmp);
        }
    }
    if (0 < cmps.length) {
        entity = new Entity(pogo.id);
        entity.addComponents(cmps);
    }
    return entity;
 }

//Once all entities are unserialised simply add them to your engine
for(...) { engine.add(entities[i]); }

// once all entities have been unserialised and added you can wake them up
//so they can recompute all the missing data and fetch dependencies
for(...) { entities[i].awake(); }

```

If this approach doesn't allow you to retrieve all the behaviours and data needed for your entities then you might have to rethink your design if you want to be able to pass arbitrary entities across the network.

---

**Edit**: To avoid sending too much data try to compress it. For example using http compression if you send the data to a browser.

Otherwise you can use any other compression library available to you. lz4 is a good one, it has a browser implementation as well as a native one for node.

Using the above dragon entity I get the following result after using lz4:

```
data.length:1200 compressed.length:444

```

Quite good and it also saves space when writing to files or database.
> 1 votes

---
Tags: javascript, networking, component-based
---


title: Cubic bezier for easing?

text:
# Question
Title: Cubic bezier for easing?
I would like to find out what Y is if X is a certain number from a cubic bezier curve to make a custom easing function, like it's done on this site: http://cubic-bezier.com/
Does anyone know a formula or a function to find Y if X is something of a cubic-bezier? (Coding in C#/XNA)

# Answer
Lets look at two approaches:

1. Binary search - assuming the Bezier is set with values where there is one `Y` for each `X`, meaning that there is an injective function that receives an `X` and returns a `Y` then you can search for the correct `t` value that will return the `x,y` pair you are looking for.
2. Precomputation: Computing 1000 values for `t` between in the range `[0 1]` should only take an instant and you can place the results in 200 buckets. Afterwards, you could easily get a tiny set of relevant `x,y` pairs by simply picking the relevant bucket from the array.

Lets explore this in more depth (this is the formula):

To do a binary search, we'll assume that you create a specialized function `h(t)` that commputes the `x` value for a given `t` and returns it.

We are looking for the `y` value where `x=a` for some `a` so we need to find the correct `t` such that `h(t)` (nearly) equals `x`.

```
h(t) : return (1 - t)^3 * x0 + 3(1 - t)^2t * x1 + 3(1 - t)t^2 * x2 + t^3 * x3;

//Util
sign(z) : (z >= 0)? 1 : -1;
abs(z) : z * sign(z);

//binary search :
lookup(a) :
  t = 0.5;
  step = 0.5;
  precision = 0.0001;
  While(abs(h(t) - a) > precision) :
    step /= 2.0;
    t += sign(a - h(t)) * step;

```

I did not check the code for faults so you"re welcome to look for errors.

Other method:

Calculate the `Y` and `X` values for a 1000 values of `t` (in advance). Put the results into buckets in an array of length `N`. `x` is between `[0 1]` so place all results between `M/N` and `(M + 1)/N` in the list in index M in the bucket array. You can later use a (fast) lookup to find the `x,y` pair you want (by radix/range). Binary search (and Newton Raphson) are you friends when you want to quickly answer complex mathematical questions with the use of a computer. You can still use the binary search to increase precision after the look up by searching between the two closest values.

A quick recap: you store the `x,y` pairs in **linked-lists** within an **array of buckets** by creating lists of `x,y` pairs where the values of `x`(s) that are between `[m/n (m+1)/n]` are all stored in the `m`th index (i.e. in `listarray[m]`).
> 4 votes

---
Tags: xna, c#, beziers, easing
---


# Question
Title: How do some mobile games scale graphics so beautifully?
I'm working on my first Android game and have been struggling a bit with scaling.

I've got 3 test devices 800x480, 1920x1080 and a 2560x1600 tablet. Some games look near perfect on all of them - many other games don't, including mine.

I'm really struggling with images looking blocky when scaling. I'm using the libdgx library, and have turned on linear filtering for everything. Almost always scaling down. Fonts are something I'm really struggling with.

I've been dissecting the apk's of various games for tips but can't see anything in particular that they're doing. In one game I examined (Candy Crush Saga) there's only 1 set of images, they only use 1 font. They also have a ttf in there, but I can't work out where that's used. The main font in a pre-created bitmap font.

Does anyone else have any tips or tricks. Ho do others manage it, especially the font scaling?

# Answer
> 4 votes
There is no magic filter that will make your game look good on high resolution devices, you simply need to increase the resolution of your assets.

Down-scaling high resolution sprites looks considerable better than up-scaling of low resolution sprites.

**Edit**:
Fonts and pixel art are a special case because they are so small and shape that important that each single pixel is important. As a basic rule of thumb, don't ever scale bitmap fonts down and only scale up to multiples to integers using nearest neighbor filtering (e.g. only 2x, 3x, 4x, not 2.25x).

You might want to create a few fixed font sizes and chose the most appropriate one for each resolution.

If you really need arbitrary font sizes you'll need to use either vector fonts (.ttf extension) or use distance field rendering (probably more suited for games since faster).

---

A few resources on distance field based rendering:

# Answer
> 2 votes
Down-scaling assets can still look bad. This is especially the case for weird ratios (e.g. 1600 width to 800 works well, but to 900 gives uneven sampling patterns).

People also pay very close attention to fonts. Even things like texture compression are usually avoided, because it can screw up anti-aliasing of edges. Also, a font might simply not be designed for small sizes (intuitively it's clear that you cannot scale Comic Sans to 6px height very well), so you will need an entirely different font for extreme cases.

If you want to scale well, what you will need to do is either

1. provide assets optimized for prominent display sizes (and for outliers, use the closest one), or
2. Use vector graphics, raster them at the client's resolution, cache the result. For example you can use libfreetype to raster ComicSans.ttf to a texture (which you can store to disk to not have this loading time again). Then you use that texture for rendering (texture atlas with single characters, or whole UI elements if you don't have much text). The big advantage is that you can even rotate the text properly, then rasterize it and you will get perfect anti-aliasing (instead of anti-aliasing, then rotating, which will break it).

---
Tags: android, libgdx, scale
---


# Question
Title: How do I determine color resolution of an output in DXGI/D3D?
i'm was revising some code i wrote some time ago when working on the window wrapper for my rendering framework. The framework is based off DirectX, but it wasn't really using any D3D-related facility. Instead it was wrapping the EnumDisplaySettings call :

```
DEVMODE dm;
dm.dmSize = sizeof(dm);
int_32 count{ 0 };
while (EnumDisplaySettings(NULL, count, &dm))
{
    if (dm.dmPelsWidth == _width && dm.dmPelsHeight == _height)
    {
        m_width = dm.dmPelsWidth;
        m_height = dm.dmPelsHeight;
        m_color_resolution = dm.dmBitsPerPel;
        m_display_frequency = dm.dmDisplayFrequency;
        return true;
    }
    ++count;
}

```

Simple as that, this doesn't take into account the format. It does take the refresh rate in count (`DisplayFrequency`) that I've supposed being the same thing. I'm using this Win32 call because later whenever someone needs to set the window to fullscreen I apply the `DEVMODE` through `ChangeDisplaySettings()`.

I could have used the `IDXGIAdapter::EnumOutputs` call, but this doesn't give me the bits per pixel (or color resolution). I've done some tests and its value is 32 most of the times but I don't want to take it for granted. My question(s) is(are):

* Is there any way to get the color resolution through Direct3D ? is it strictly related to the format ?
* Is my approach correct at all ? because i'm having some doubts, should i keep using the Win32 calls or use the D3D ones ?

I apologize if this question has already been answered or if it has an obvious answer that I can't get, I bet I'm missing something.

# Answer
> Is there any way to get the color resolution through Direct3D ? is it strictly related to the format?

The color resolution (bits per pixel) of a surface is strictly bound to the format of that surface, yes. You can use CheckFormatSupport to determine what formats are available for what uses at runtime.

> Is my approach correct at all ? because I'm having some doubts, should I keep using the Win32 calls or use the D3D ones?

Due to the nature of the Windows platform and the way it's evolved over the years *and* focused on retaining backwards compatibility, there are a lot of ways to do things. Each will have various pros and cons but often any option will work fine. You may be able to accomplish what you want in slightly fewer lines with DXGI, or slightly more (without knowing in detail what you are doing, it's hard to say). The DXGI approach is "more modern," if that matters to you.

However, if your code is functional and (appears) bug-free, I wouldn't *rush* to change it.
> 2 votes

---
Tags: c++, directx, resolution, win32
---


title: XNA Move List of Rectangles

text:
# Question
Title: XNA Move List of Rectangles
I have a game in which sprites will be removed and added under different circumstances, and so I created `Rects` of type `List<Rectangle>` to hold the bounding rectangle for each sprite.

```
List<Rectangle> Rects = new List<Rectangle>();

```

Within `Initialize()`:

```
playerTexture = Content.Load<Texture2D>("player");
cowTexture = Content.Load<Texture2D>("cow");
player = new Player(playerTexture, new Vector2(100, 100));
Rects.Add(player.Bounds);
for (int i = 0; i < 5; i++)
{
    Cow cow = new Cow(cowTexture, graphics);
    cows.Add(cow);
    Rects.Add(cows[i].Bounds);
}

```

What I want to do is iterate through every rectangle in the list and move it when the player approaches the edge of the screen. This is the code with which I have tried to do this:

```
for (int i = 0; i < Rects.Count; i++)
{
    if (player.Bounds.Left < 60)
    {
        Rects[i].Offset(2, 0);
    }
    if (player.Bounds.Right > GraphicsDevice.Viewport.Width - 30)
    {
        Rects[i].Offset(-2, 0);
    }
    if (player.Bounds.Top < 60)
    {
        Rects[i].Offset(0, 2);
    }
    if (player.Bounds.Bottom > GraphicsDevice.Viewport.Height - 30)
    {
        Rects[i].Offset(0, -2);
    }
}

```

But when my player gets to the edge of the screen, he very happily leaves and none of the sprites move. What am I doing wrong?

# Answer
It looks like you're **copying** the `cows[i].Bounds` rectangles to your `Rects` list. Your loop is just updating the copy, not the original - your original `Cow` will not be modified in this way. `Rectangle` is a struct, not a class, so it's copied by value to the list, not as a reference.

Also, your loop design is *very* inefficient, in that you're checking the GraphicsDevice settings multiple times per per loop. Try this instead:

```
Point offset;

if (player.Bounds.Left < 60)
   offset.X = 2;
else if (player.Bounds.Right > GraphicsDevice.Viewport.Width - 30)
  offset.X = -2;

if (player.Bounds.Top < 60)
   offset.Y = 2;
else if (player.Bounds.Bottom > GraphicsDevice.Viewport.Height - 30)
    offsetY = -2;

if (offsetX != 0 || offsetY != 0)
   for(int i = 0; i < cows.Count; i++)
   {
    cows[i].Bounds.Offset(offset);
   }

```

Another potential issue:

Why are you offsetting by only 2? It may make more sense to offset the position based on the distance the sprite has moved outside of the view:

```
if (player.Bounds.Left < 60)
    offsetX = 60 - player.Bounds.Left;

```

... and so forth.

**Update**

Also, you're moving either `cows[]` or `rects[]`, based on whether `player` is near the edge of the viewport. Shouldn't you be moving `player` instead?

The logic above seems to do the following:

If the **player** is less than 60 units from the left or top of the viewport, or less than 30 units from the bottom or right of the viewport, move all of the **cows**.

If the player is moving, it willl happily keep moving, and not be adjusted relative to anything else. If you fix the `Rect` reference issue, I'd expect them to start moving when `player` hits your 60x30 margin, and for `player` to keep going in the direction it was before (right off of the screen).

If your units are pixels, and this is being called per frame, you'll also see some pretty dramatic velocity when the motion starts, which may or may not appear as a flicker followed by everything disappearing.

**Update the second**

In response to your comment,

> Are you saying that the only way to do this is to move cows\[i\].Bounds, player.Bounds, and any others separately?

In C++, you'd use a template for this. In C#, you'll need either an interface or a common base class. For example:

```
public abstract class Entity
{
    public Rectangle Bounds;
}

public class Player : Entity
{
}

public class Cow : Entity
{
}

public class MyGame
{
   public List<Entity> Entities { get; private set; }

   public MyGame()
   {
       Entities = new List<Entity>();
   }
}

```

And, create some players and cows at some point in your application

```
void Initialize()
{
    /// add 4 players
    for(var i = 0; i < 4; i++)
    {
        var player = new Player();

        player.Bounds = new Rectangle(.....)

        Entities.Add(player);
    }

    /// add some cows
    for(var i =0; i < 10; i++)
    {
        var cow = new Cow();
        cow.Bounds = new Rectangle(..........(;
        Entities.Add(cow);
    }
}

```

In your update loop:

```
/// later on, move everything
for(var i = 0; i < Entities.Count; i++)
{
    var item = Entities[i];
    item.Bounds.Offset(.....);
}

```
> 1 votes

---
Tags: xna-4.0
---


title: Artillery Simulation

text:
# Question
Title: Artillery Simulation
I need some help on a simulation of an Artillery like this one

https://www.youtube.com/watch?v=YktWSKo\_UbA.

I cant figure out how to make the "tomato" to get to the selected spot.

Where can I get solutions for this kind of questions in the future? Physics programming books? I am using LibGDX (Java).

# Answer
> 0 votes
I bought 'Physics for Game Developers' and I liked it. It even has an 'Artillery'-example in it. One with canons.

As far as I remember it was in C but you can easily rewrite it into Java.

If you do not want to buy books. You can ask questions here on Stack Exchange or you can look into GameDev.net.

# Answer
> 0 votes
I cannot see your link at work, but an artillery trajectory is mostly subject to gravity.

Horizontal speed `vh` is assumed to be constant while in air and the initial location is `x0`:

```
x(t) = vh . t + x0

```

Vertical coordinate accelerate with gravity `g`, so the second derivative is `-g`:

```
y"(t) = -g

```

You know the initial vertical speed `vv`, so you can set the constant after integrating:

```
y'(t) = -g . t + vv

```

You add the initial location (`y0`) after integrating again:

```
y(t) = -0.5 . g^2 t + vv . t + y0

```

Now you have `x` and `y`, the horizontal and vertical coordinates in function of the time `t`. `g` is roughly 9.81, it is the constant for the gravitation formula

---
Tags: java, physics, libgdx
---