# Question
Title: Procedural Generation, Game Updates, & Butterfly Effect
NOTE: I asked this on Stack Overflow a few days ago but had very few views and no response. Figured I should ask on gamdev.stackexchange instead.

This is a general question / request for advice on maintaining a procedural generation system through multiple post-release updates, without breaking previously generated content.

I am trying to find information and techniques for avoiding "Butterfly Effect" issues when creating procedural content for games. When using a seeded random number generator, a repeating sequence of random numbers can be used to create a reproducable world. While some games simply save the generated world to disk once generated, one of the powerful features of procedural generation is the fact that you can rely on the reproducability of the number sequence to recreate a region multiple times in the same way, removing the need for persistence. Because of the constraints of my particular situation, I must minimise persistence, and need to rely on purely seeded concent as much as possible.

The main danger in this approach is that even the slightest change in the procedural generation system can cause a butterfly effect that changes the entire world. This makes it very tricky to update the game without destroying the worlds that players are exploring.

The main technique I've been using to avoid this problem is to design the procedural generation in multiple phases, each of which has its own seeded random number generator. This means that each sub-system is self contained, and if something gets broken it will not affect everything in the world. However this seems like it still has a lot of potential for "breakage",even if in an isolated part of the game.

Another possible way of dealing with this problem could be to maintain complete versions of your generators within the code, and keep using the right generator for a given world instance. This seems like a maintenance nightmare to me though, and I'm curious if anyone actually does this.

So, my question is really a request for general advice, techniques, and design-patterns for dealing with this problem of the butterfly effect, especially in the context of post-release game updates. (Hopefully that's not too broad a question.)

I am currently working in Unity3D / C#, although this is a language agnostic question.

UPDATE:

Thank you for the replies.

It's looking more and more like static data is the best and safest approach, and also that when storing a lot of static data is not an option, having a long campaign in a generated world would require strict versioning of the generators used. The reason for the limitation in my case is the need for a mobile based cloud save / sync. My solution may be to find ways of storing small amounts of compact data about essential things.

I find Stormwind's concept of "Cages" to be a particularly useful way of thinking about things. A cage is basically a reseed point, preventing run-along effects of small changes, ie caging the butterfly.

# Answer
> 8 votes
I think you've covered the bases here:

* Using multiple generators or re-seeding at intervals (eg. using spatial hashes) to limit the spillover from changes. This probably works for cosmetic content, but as you point out it can still cause breakage contained within one section.
* Keeping track of the generator version used in the save file and responding appropriately. What "appropriate" means could be...

+ Keeping a history of all previous versions of the generators in your game executable, and using whichever one matches the save. This makes it harder to patch bugs if players keep using old saves.
    + Warning the player that this save file is from an old version, and providing a link to access that version as a separate executable. Good for games with campaigns lasting a few hours to days, bad for a campaign you expect to be playing for weeks or more.
    + Keep only the last `n` generator versions in your executable. If the save file uses one of those recent versions, (offer to) update the save file to the latest version. This uses the appropriate generator to unpack any outdated state into literals (or into deltas from the new generator's output on the same seed, if they're very similar). Any new state from here on comes from the newest generators. Players who don't play for a long time could be left behind though. And in the worst case you end up storing the whole game state in literal form, in which case you might as well...
* **If you expect to be altering your generation logic frequently and don't want to break compatibility with previous versions, don't rely on generator determinism:** save your whole state in your save file. (ie. "Nuke it from orbit. It's the only way to be sure")

# Answer
> 4 votes
The primary source of such the Butterfly Effect is arguably not number generation - which should be easy enough to keep deterministic from a single number generator - but rather the *use* of those numbers by client code. Code changes are the real challenge in keeping things stable.

**Code: Unit Tests** The best way to ensure that some minor change somewhere doesn't manifest elsewhere unintentionally, is to include thorough unit tests for every generative aspect, in your build. This is true of any piece of compact code where changing one thing can impact on many others - you need tests for all so you can see on a single build what has been impacted.

**Numbers: Periodic Sequences / Slots** Let's say you have one number generator that serves for everything. It doesn't assign meaning, it just spits out numbers in sequence - like any PRNG. Given the same seed over two runs, we get the same sequences, yes? Now you give things some thought and decide that there will be maybe 30 aspects of your game that will regularly need to be supplied with a random value. Here we assign a cycling sequence of 30 slots, e.g. every first number in the sequence is rough terrain layout, every second number is terrain perturbations... etc. ...every 10th number adds some error to AI state for realism. So your *period* is 30.

After 10, you have 20 slots free that you can use for other aspects as game design progresses. The cost here is of course that you must generate numbers for slots 11-30 *even though they're not currently in use*, i.e. complete the period, to get back to the next sequence of 1-10. That has a CPU cost, though it should be minor (depending on the number of free slots). The other downside is you need to be *sure* that your final design can be accommodated in the number of slots you made available at the very start of your development process... and the more you assign at the start, the more "empty" slots you potentially have to go through each, to make things work.

The effects of this are:

* You have one generator producing numbers for everything
* Changing the number of aspects you need to generate numbers for, will not impact on determinism (provided your period is large enough to accommodate all aspects)

Of course, there will be a long period during which your game is not available to the public - in alpha, so to speak - so you could reduce down from say 30 to 20 aspects without impacting any players, only yourself, if you realised that you had assigned *way* too many slots at the start. This would of course save some CPU cycles. But bear in mind that a good hash function (which you can write yourself) should be lightning fast, anyway. So having to run extra slots should not be costly.

# Answer
> 3 votes
If you want persistence with PCG, I suggest you **treat the PCG code itself as data**. Just as you would persist data across revisions with regular content, with generated content, if you wish to persist it across revisions, you'll need to persist the generator.

Of course, the most popular approach is to convert generated data into static data, as you've mentioned.

I don't know examples of games that keep around lots of generator versions around, because persistence is unusual in PCG games - it's why permadeath often goes hand-in-hand with PCG. However there are plenty of examples of multiple PCGs, even of the same type, within the same game. For example, Unangband has many separate generators for dungeon rooms, and as new ones are added, the old ones still work the same. Whether that's maintainable is up to your implementation. One way to keep it maintainable is to use scripts to implement your generators, keeping them isolated with the rest of the game code.

# Answer
> 2 votes
I maintain an area of ca 30000 square kilometers, holding ca 1 million buildings and other objects, in addition to randomized placements of misc things. An outdoor simulation ofc. The stored data is ca 4 GB. I am lucky to have storage space, yet it's not unlimited.

Random is random, uncontrolled. But one can cage it a little:

* Control it's start end end (as mentioned in other posts, the seed number and how many generated numbers).
* Limit its numerical space, eg. generate integers between 0 and 100 only.
* Offset its numerical space, by adding a value (eg. 100 + \[generated numbers between 0 and 100\] produces random numbers between 100 and 200)
* Scale it (eg. multiply by 0.1)
* And apply various cages a around it. This is reducing, scrapping part of the generation. Eg. if generating in 2-dimensional space, one can put a rectangle on top of number pairs and scrap what's outside. Or a circle, or a polygon. If in 3D-space, one can accept for example only triplets that reside inside a sphere, or some other shape (now thinking visually, but this doesn't necessarily have anything to do with actual visualisation or positioning).

That's about it. Cages also consume data, unfortunately.

There is a saying in finnish, Hajota ja hallitse. Translates into **Divide and conquer**.

I quickly abandoned the idea of precise definition of smallest details. Random wants freedom, so it got the freedom. Let the butterfly fly - inside it's cage. Instead i focused on having a rich way to define (and mainain!!) the cages. It doesn't matter what cars they are, as long as they are blue or darkblue (a boring employer said once:-)). "Blue or darkblue" being the (very small) cage here, along color dimension.

What is manageable, for controlling and managing numerical spaces?

* A boolean grid is (bits are small!)
* Corner points are
* As is a tree structure (= to follow into "cages holding cages")

Maintenance-wise, and version intercompatbility-wise... we have
:if version = n then
:elseif version = m then...
Yep, the code base grows larger :-).

Familiar things. Your correct way to go ahead would imho be to define a **rich method to divide and conquer**, and sacrifice some data on that. Then, where possible, give the (local) randomisation freedom, where it is not crucial to control it.

Not totally incompatible with the funny "nuke it fom orbit" proposed by DMGregory, but perhaps use small and accurate nukes? :-)

---
Tags: procedural-generation
---


# Question
Title: Game Modeling good practice regarding quads and ngons
I'm asking myself if using quads is really the better practice instead of using ngons (for flat surfaces!) when it comes to game modeling.

I often read this and saw models that look like this (96 tris!).

But I can't understand why this should be preferred instead of this model using ngons (60 tris!)

Are there reasons why the quad variant with more tris should be preferred also for a final game model (that also does not use displacement mapping for example) or is the n-gon actually preferred in such cases because of the lower triangle count?

**Because it came up in the discussion:** This should be of course only valid for static objects that do not deform, my question came up because I saw that models which are most likely not supposed to deform are modelled using the additional quads and I'm wondering if there's really any benefit of doing it (I just see the disadvantage of additional triangles so far).

# Answer
> -1 votes
There is never an N-gon in any model for a game. All graphics cards use triangles. N-gons are a software construct in 3D apps. When you model for games you should always use triangles or get rid of N-gons. I use Cinema4d and it has some good tools for that. Blender does also. If you do not triangulate your model, the end-user game engine or importer will try and do so on its own and this can be problematic. Worst case is your models look bad.

TL;DR - N-gons are never used by GPUs. Use triangles.

---
Tags: 3d, rendering
---


# Question
Title: Wrong pivot point of parent / wrong scale of children
I'm trying to make two objects, in is an intact glass, the other one is the glass but shattered.

So for the shattered glass, in Maya I make a Plane, cut it with the multi-cut tool, extrude the faces, select the object and then separate. So I have every single piece of the glass as a single object. After that, I select them all, Modify-\>Center Pivot.

Now when I import this into unity, this is where the problems arrive.

* When I rotate the native parent object, which holds all the glass pieces, it looks right:

Native Parent Rotation

* When I rotate all the child glass pieces, the distort some weird way, the scaling is really off on one axis and they appear very thin:

Native Child Rotation

* Now, when I create a new empty GameObject on root level, and simply add all the children glass pieces to this object, they rotate just fine and have the right scaling:

New Parent - Child Rotation

* But now, when I rotate the parent, the pivot point seems to be completely off:

New Parent - Parent Rotation

The rotation I make is a simple `gameObject.transform.Rotate (Vector3.left);`

How can I achieve the correct pivot point for the parent, and avoid the weird scaling issues on the children? I need to be precise of course, because the shattered parent object is supposed to replace the intact glass object 1:1 after a collision.

# Answer
> 1 votes
Okay, I finally fixed it after several hours.

Problem was, my parent plane in Maya was set to something like 6,3 / 2,1 / 3,1. So this was the scaling the object always got imported into Unity, which messed up its space / pivot points.

In Maya I now just used `Modify->Freeze Transformations` on the Plane, to normalize it to 1 / 1 / 1. After that I had to re-reset my pivot points on my glass pieces (select all, `Modify->Center Pivot`.

Now all rotates around the correct pivot points and scales the way it's supposed to.

---
Tags: unity, rotation, maya, scale
---


title: Create a crosshair openGL

text:
# Question
Title: Create a crosshair openGL
How do I draw a white crosshair in the middle of screen in openGL, it's all well and good knowing how to render objects in 3d space, but I have literally no idea on how to draw something that sticks on the screen no matter what

Would this require a shader? one that does not take into account model view projection matrix? at what point would i draw the cross? after everything to coincide with the painters algorithm? Or do I give it a z value?

# Answer
> 2 votes
To render a cross-hair, all you would need to do is render a piece of geometry using just a screen-space transformation, followed by the projection matrix. Mapping the identity matrix as your view will do this for you. A view matrix allows us to transform vertices into view space; removing this step allows us to go directly from model-space to screen-space. This will make it so that no matter how you turn, the reticle will stay in the same position.

---
Tags: opengl, c++, graphics
---


# Question
Title: cocos2d-x Label Load Image like Sticker-Smile..(by html or …)
hi and sorry for my english...

i am using cocos2d-x (c++)... can i load sticker (smile) in my Label(a text mixed by image)? i know that we can load bitmap fonts by:

```
Label::createWithBMFont

```

also i know many frameworks like flash can load html texts by textbox which can contains img tags... but what is the best way for adding smile image in the text of label in cocos2d-x?? can cocos2d Label load html text like :

```
"hello<br>How Are You<img src="..." width=".." height=".." alt="..">"???

```

thanks...

# Answer
> 0 votes
i've found my way... we can load images and show different text formats by UIRichText... also you can push unicode texts... example code is:

```
auto text = cocos2d::ui::RichText::create();
const auto font = std::string("fonts/FinalFonts/Berlin.ttf");
text->pushBackElement(ui::RichElementCustomNode::create(1995, Color3B(255, 255, 255), 255, Label::createWithSystemFont(persianText01, font, 20, Size::ZERO, TextHAlignment::RIGHT, TextVAlignment::TOP)));
text->pushBackElement(ui::RichElementImage::create(1993, Color3B(255, 255, 255), 255, "icons/sticker.png"));
text->pushBackElement(ui::RichElementCustomNode::create(1994, Color3B(255, 255, 255), 255, Label::createWithSystemFont(persianText02, font, 20, Size::ZERO, TextHAlignment::RIGHT, TextVAlignment::TOP)));
text->pushBackElement(ui::RichElementImage::create(1990, Color3B(255, 255, 255), 255, "icons3/sticker.png"));
text->pushBackElement(ui::RichElementCustomNode::create(1998, Color3B(255, 255, 255), 255, Label::createWithSystemFont(persianText03, font, 20, Size::ZERO, TextHAlignment::RIGHT, TextVAlignment::TOP)));
sprite->addChild(text);

```

---
Tags: cocos2d-x, image, rendertexture
---


title: Store Player Stats

text:
# Question
Title: Store Player Stats
My character creation order is: Select Race, Select Class, Assign Bonus Stat Points, Customize and Name the character.

Because I am using Unity's UI components I am using scripts attached to empty objects (eg. \_RaceManager, \_ClassManager) that handle which button is pressed and select the actual race or class.

However a look on the inspector shows stat values as 0. So I must be doing something wrong!

**MY QUESTION:** How would my Playing Character (Player) get the selected values depending on race and class?

Here is an example of my code (actual code is too big to post):

```
using UnityEngine;
using System.Collections;
using UnityEngine.UI;
using UnityEngine.EventSystems;

public class Class_GOnClick : MonoBehaviour {
    public GameObject Barbarian, Knight, Paladin, Assassin, Scout, Shadow, Elementalist, Druid, Summoner, Priest, Hunter, Next, Previous, descRect, ClassPanel, RacePanel, RaceManager;
    StageIDs sID = new StageIDs(); //0 - ERROR, 1 - RACE, 2 - CLASS, 3 - STATS, 4 - CUSTOMIZATION
    public static BaseClass classSelection;
    public void Start()
    {
        sID.id = 2;
        Barbarian.GetComponent<Button>().onClick.AddListener(() => { isBarbarian(); });
        Next.GetComponent<Button>().onClick.AddListener(() => { _Next(); });
        Previous.GetComponent<Button>().onClick.AddListener(() => { _Previous(); });
        descRect = GameObject.Find("DescriptionText");
        descRect.GetComponent<Text>().text = "";
    }

    public void isBarbarian()
    {
        SaveInformation _Info = new SaveInformation();
        classSelection = new BarbarianClass();
        descRect.GetComponent<Text>().text = classSelection.CharacterClassDesc;
        _Info.Constitution += classSelection.Constitution;
        _Info.Strength += classSelection.Strength;
        _Info.Intelligence += classSelection.Intelligence;
        _Info.Dexterity += classSelection.Dexterity;
        _Info.Charisma += classSelection.Charisma;
        _Info.Wisdom += classSelection.Wisdom;
        _Info.Willpower += classSelection.Willpower;
        _Info.Luck += classSelection.Luck;
        _Info.Perception += classSelection.Perception;
        _Info.MaxPhResist += classSelection.MaxpResist;
        _Info.MaxMaResist += classSelection.MaxmResist;
        _Info.MaxSpeed += classSelection.MaxSpeed;
        }

public void _Next()
    {
        //ClassPanel.SetActive(false);
    }
    public void _Previous()
    {
        ClassPanel.SetActive(false);
        RacePanel.SetActive(true);
        Previous.SetActive(false);
        RaceManager.SetActive(true);
    }
}

```

As requested, the Barbarian Class:

```
using UnityEngine;
using System.Collections;

public class BarbarianClass : BaseClass {

    public BarbarianClass(){
        //Description
        CharacterClassName = "Barbarian";
        CharacterClassDesc = "The Barbarian is a breed of Fighter focused more on damage than defense. Often characterized by wearing less armor, being less civilized, and being able to fly into a berserker rage that increases damage output or allow them to do more damage based on how hurt they are.";
        CharacterClassOrigin = "Fighter";

        //Base Stats

        Constitution = 5;
        Strength = 10;
        Intelligence = 5;
        Dexterity = 5;
        Charisma = 3;
        Wisdom = 3;
        Willpower = 3;
        Luck = 3;
        Perception = 5;
        //CurHp = ;
        //MaxHp = ;
        //CurpResist = MaxpResist;
        MaxpResist = 5;
        //CurmResist = MaxmResist;
        MaxmResist = 1;
        //CurSpeed = MaxSpeed;
        MaxSpeed = 5;

    }

}

```

# Answer
Move `_info` into class-scope. In your code it is a local variable which is destroyed when isBarbarian returns

```
public SaveInformation _Info;
public void Start()
...
public void isBarbarian()
{
   _Info = new SaveInformation();
   ...
}

```

When you make changes to your .NET assemblies, Unity copies the existing data to the un-managed side, reloads the new assemblies, then copies the data back. Classes you create are not serializable, by default, so Unity will not be able to "see" them. This is also required since this SaveInformation is probably going to be.... saved (serialized to disk). This is done through the `[System.Serializable]` class-level attribute and the `[NonSerialized]`/`[SerializeField]` field-level attributes.

```
[System.Serializable] //This allows Unity to "see"
class SaveInformation
{
   public float PublicFloat1; //Serialized

   [NonSerialized]
   public float PublicFloat2; //Not serialized

   private float PrivateFloat1; //Not serialized

   [SerializeField]
   private float PrivateFloat2; //Serialized
   ...
}

```
> 1 votes

---
Tags: unity, c#
---


title: When do I need to call `glUseProgram`?

text:
# Question
Title: When do I need to call `glUseProgram`?
Looking at examples at http://learnopengl.com/#!Getting-started/Hello-Triangle and many different places, I've found that the draw sequence usually goes like this:

```
// setup VBO, VAO, load shaders

while (true) { // game loop
  glUseProgram(shader);
  glBindVertexArray(someVAO);
  drawStuff(...);

  // ...
}

```

Now my question is, is there any reason why I'd want to repeatedly do `glUseProgram(...)` on each frame, unless I'm using multiple shaders (such as OpenGL clearing currently used shader after rendering?)?

Also, if I am using multiple shaders, do I need to `glUseProgram` before switching to a different VAO? I'm unclear on whether the VAO just gets set as active, or if it actually modifies the state of a currently used shader. I've tried looking this up in the OpenGL spec, but couldn't quite find it.

**edit:** Yes I did mean `glUseProgram`, sorry.

# Answer
> 3 votes
Maybe you mean glUseProgram()? I can't find something related to glUseShader, so if i'm wrong then sorry. But if this is the case then basically you use it when you want to use the shader itself.

This is an example from my current opengl project (EDIT: Oh, by the way, this example code is on the main rendering loop):

```
GL30.glBindVertexArray(vao); // Binding vao.
majorShader.glUseProgram(); // Don't mind the "majorShader" it's an util class i made.
GL11.glBindTexture(GL11.GL_TEXTURE_2D, 0); //Don't mind these, some framebuffer stuffs.
GL30.glBindFramebuffer(GL30.GL_FRAMEBUFFER, fb);
display.renderTriangle(); // Render the scene.

GL30.glBindVertexArray(screenVao); // Bind a different vao.
screenShader.glUseProgram(); // Switching shader because it does a different thing
GL11.glBindTexture(GL11.GL_TEXTURE_2D, fbTex);
GL30.glBindFramebuffer(GL30.GL_FRAMEBUFFER, 0);
display.renderScreen(); // Render the frame buffer, which used different vao, vbo and shader.

```

But, if you're planning on using only one shader, then you can just call `glUseProgram()` once on initialization function or something like that before drawing.

EDIT2 (Summary): So, 1. I don't see why you need to call `glUseProgram()` repeatedly if you're only using one shader (Unless maybe you call `glUseProgram(0)` for some reason and want to use shader again..) 2. You can see in my case, i use `glUseProgram()` after calling `glBindVertexArray()` when i want to do a something with a different shader

---
Tags: opengl, shaders
---


# Question
Title: How to create guides to off-screen objects?
I've played Metroid Blast on Wii U, and would like to build one of its features in a three.js game.

The feature is: if an opponent is out of view, a guide is displayed showing the direction of the opponent.

An example of it is here:

(Image source)

Notice the small circles with arrows in the left side.

How could I have a similar feature in my game?

# Answer
> 3 votes
For each opponent/object/destination to display:

* Project it's worldspace location to view-space (MV)
* Flatten the Z to 0
* Normalize the direction to unit-length
* Multiply by "HUD" radius (world/view-space units)
(the linked image looks like they might have used aspect ratio, instead, to stretch circle into an ellipse)
(i.e. scale by `(widthFactor, heightFactor, 0)` instead of `1.0f`)

I may not be able to provide the code to "find opponents within the proper range" (using three) (I'm betting you can)

---
Tags: gui, three.js
---


title: OpenGL is box blur this slow?

text:
# Question
Title: OpenGL is box blur this slow?
I've never tried blur until recently, and by that i've noticed fps drop when doing box blur. My fps will go down from 4000-5000 fps to 1000-1500 fps. Currently rendering at 853x480 frame buffer and window size.

Is this normal? Oh, and i'm only rendering a basic triangle. Here's the fragment shader code (pretty much the same from open.gl):

```
#version 150

in vec2 fTexCoord;

out vec4 finalColor;

uniform sampler2D tex;

const float blurSizeX = 1.0f / 853.0f;
const float blurSizeY = 1.0f / 480.0f;

void main() {
    vec4 col = vec4(0.0f);
    for (int y = -3; y < 4; y++) {
        for (int x = -3; x < 4; x++) {
            col += texture(tex, vec2(fTexCoord.x + x * blurSizeX, fTexCoord.y + y * blurSizeY)) / 49.0f;
        }
    }
    finalColor = col;
}

```

Thank you in advance.

# Answer
> 3 votes
Yes and no.
**Yes**, generally: the convolution operation is usually very computationally heavy and if you are sampling 7x7 area, that is 49 times more samples than you would usually do.

**No**, in your case: One important thing about FPS is that it is *inverse of* a function. Because with 5000 FPS the time to render a frame is 0.20 ms and with 1500 FPS it is 0.66 ms the assumption the blur will always take away 3500fps (flat) is wrong. The blur just took 0.46 ms extra, with 60fps(=16.66 ms) target it is less than 3% of frame time.

---

I am not sure if it is worth it for post-processing effect with small radius, because you would have to re-create the image every frame, but there is an optimization using integral images reducing it from O(n^2) to constant complexity(per pixel) but it is a two-pass partially serial algorithm and it could prove difficult to implement in shaders.

---
Tags: opengl, glsl, lwjgl
---


title: Handling animations in a Platformer

text:
# Question
Title: Handling animations in a Platformer
I'm developing a 2D platformer game using the Cocos2d-x Engine, i can load correctly the animations according in which action the player is(running, jumping, standing, etc).

Now i'm trying to add the attack action to the player, and i need some advice about the best way to handle the corresponding animation for this new action.

The first thing that comes to my mind is to create new states for the player and his corresponding animation. For example, JumpRightAttack, JumpLeftAttack, and so on. But handling this that way seems to be a mess, and if i have more than one weapon it will become even more messy.

On the other hand, i can have only one attack animation and attach the current weapon, but i'm a little lost of how to attach the weapon in the correct spot(i.e. player's hand)

Which method would you recommend??

# Answer
> 1 votes
Rather than using entire sprite sheet animation, I would recommend a 2D skeletal approach. Tools like **Spine** can help you here and are supported by cocos2d-x framework. The class in question is the ***SkeletonAnimation*** object.

Here is a sample code on how to initialize the same

*source- cpp tests from cocos2d-x*

```
//initilize the object with animation atlas
...
skeletonNode = SkeletonAnimation::createWithFile("spine/spineboy.json", "spine/spineboy.atlas", 0.6f);
    skeletonNode->setScale(0.5);
//Setting the animation to play
skeletonNode->setAnimation(0, "walk", true);
...

```

This is just the bare bones code, for more detail look up the SpineTest.h/.cpp files in the cocos2d-x cpp-test folder.

This also helps you to "attach" the weapon to the Sprite's hands by adding an anchor point at the arms and then animating it from the Spine application. This also makes the code a bit more clean and reduces you sprite sheet size considerably.

---
Tags: c++, cocos2d-x, spritesheet
---


# Question
Title: The steps in implementing Bézier triangle patches
What are the steps in creating a Bézier triangle patches. What steps would you do in order to create this in directx 11?

Say I just input 3 vertices and create a simple triangle. Is this enough? Or should I create a triangle with 9 vertices, all of them in different heights so it would make a bumpy triangle, then I apply berstein's formulas and make them smooth. so I get like a smooth triangle, not all bumpy.

A triangle like

My book says Research and implement Bézier triangle patches.

Luna, Frank D. (2012-05-21). Introduction to 3D Game Programming with DirectX 11 (Kindle Location 11901). Mercury Learning and Information. Kindle Edition.

So what are the steps you would do in order to accomplish it? Please no "coulds"

# Answer
Edit: The triangle's Bezier-curved edges are of the same order as the Bernstein you use; the edges of a third-order Bezier triangle are third-order Bezier curves. The order also determines the number of control points you need (or vice-versa). (Yes, a triangle with 3 vertices can be tessellated)

* Set topology to D3D11\_PRIMITIVE\_TOPOLOGY\_10\_CONTROL\_POINT\_PATCHLIST
(there are 10)
* Set vertex buffer
* Set shaders
* Draw(10);

10 vertices go into the vertex shader and (probably) come right out the other end:

```
void VS(inout float3 inputVertex) { }

```

These are fed into the hull shader which tells the GPU exactly how you intend to subdivide the patch. The hull shader sends the points it creates (and the input control points) to the domain shader. (a tessellated triangle)

The domain shader applies the Berstein polynomial to "Bezier" each input point. At this point, we are in "patch-space" using UV's to represent coordinates on the unit-\[DOMAIN\] (quad,tri,isoline). The pixel shader expects the inputs to be in clip-space, so the domain shader applies transformation instead of the vertex shader.

```
float4 DS(..., ..., ...) : SV_POSITION
{
   //Bernstein
   //Project
}

```

---

An example hull shader snippet:

```
[domain("tri")]
[partitioning("integer")]
(patch constant function) TessFactors[] == 2 //split each control edge into two

```

Looks like this:

---

If you have trouble getting past tessellation to the Bernstein, try this first: (You can ignore "4"; the geometry shader just makes it solid)
> 1 votes

---
Tags: directx11
---


# Question
Title: Why does lightmapping take so long compared to real time shadows?
I am using Unity 5. As a test, I set the realtime shadow resolution to max and the distance to cover my entire scene with no cascades. As expected, it lagged severely, but I could still move the camera and the shadows updated in real time.

As a second test, I lightmapped the scene using the absolute lowest settings. This took about a minute to complete.

Basically, I can use lightmapping, and it takes much longer to work than real time shadows even though it looks worse. Why does lightmapping take so long to bake in comparison to real time shadows?

# Answer
> 5 votes
Realtime shadow maps allocate texels for *everything the light can see*.

Lightmaps allocate texels for *everything*.

This makes a big difference in several cases:

* **faces occluded from the light** don't contribute any information to a shadow map - they occupy the same texels as the object occluding them. A lightmap will allocate separate texels to shadowed faces.
* **faces nearly parallel to the light rays** occupy only a narrow sliver of a shadow map, leading to stretchy/zig-zag artifacts when partially shadowed because there's not enough resolution to capture the shadow shape in the near-parallel axis. A lightmap will allocate a more even (or possibly adaptive) distribution of light samples across these faces.

This also demands substantially different methods for computing them. Shadow maps are designed to be re-rendered every frame, tolerating some errors like aliasing, light bleeding, and peter panning, while lightmaps are designed to be baked in advance, taking the time needed to minimize these errors as much as possible at the available resolution.

Lightmaps can also encode indirect lighting information (bounce light), which is a whole extra layer of computation.

---
Tags: shadows, shadow-mapping, lightmap
---


# Question
Title: Crowd funded DLC. Is this a viable option for covering the development costs of DLC?
I have had this idea floating around in my head for a while now but I am not sure if it will work.

I was looking at the idea of DLC and thought what about if we made some DLC crowdfunded in order to incentivise the players to provide money to cover for the development of it.

Basically the modal I am pondering is this: DLC is announced and a trailer is shown. Next the announcement states that a crowdfunding campaign for the development of it has start and people are free to donate money as a backer. Backers get special rewards such as early access, their name included in the credits, etc. Once the campaign is fully funded development starts immediately and a release date is announced. Once the DLC is finished and ready for release, it is available for free because all costs have been covered.

The other version is to start development on the DLC right away and run the campaign at the same time. If enough people back the project, in addition to the backer rewards, the DLC is released for free.

I am not so sure that this a good idea or not so this is why I am asking.

# Answer
Your question may get closed as opinion based, but I like it, so I am going to give my two cents.

I like your idea. But not for the reasons you mentioned.

Crowdfunding the DLC shows whether or not it is worth the development cost. Players have already played the game, and it is less of a gamble for them to purchase the DLC, because they know what to expect. This means the funding you get will have a direct correlation to the DLC sales. If it gets funded, it is worth making. If it doesn't et funded, you had free research to tell you it's no longer a viable product.

I would not make the DLC free to everyone. I would only make it free to those who backed you. In terms of marketing, you get this free focus group with your campaign. You'd be wasting it by saying it's free, because from a money point of view, who cares how many copies it sells if it is free.

So I like your idea of crowd funding it first. If it goes thru, make it (and charge for it). If it doesn't go thru, you've found out is is not worth the development cost any longer.
> 2 votes

---
Tags: marketing, fund-raising
---


title: Image Interpolaton for Rotation

text:
# Question
Title: Image Interpolaton for Rotation
I am building a 2D game in Java in which I use trig operations for rotation. I know Java offers an excellent graphics library but I intend to make my own code just for learning purposes. Now the problem is, I do not understand image interpolation. I do know it tracks the unmapped pixels on rotation and there are various techniques to do it etc. But one thing that Im still confused about even after referring to several tutorials, is - how to find the pixels that are not mapped ?? Once I know it, I can easily implement it in code. Im using PixelGrabber to get pixels and then perform rotation. So could someone just explain how to find unmapped pixels in the array during the rotation operation please?

# Answer
> 2 votes
What you call unmapped pixels are what appear as "holes" in the rotated image. In image computing (such as analysis, rendering, etc.) a rotation is a manipulation of an image *A* in order to obtain an image *A'* so that it is a rotated version of *θ* degrees (or radians). The simplest way to achieve this, and I guess this is the method you applied, is to consider a transform function *f(P,θ)* which takes point *P* and rotates it of an additional angle *θ*. From polar to cartesian coordinates, we get the system:

This way we can find out the final position of every pixel *P(x,y)* our image has. Here comes the problem you encountered. When we use this naive method we get the following results:

The presence of holes in the final image (I used a gray scaled one to keep it simple for my MatLab renderer) are due to the fact your image has a finite number of pixels, and when tranforming their position they are not likely to fit the final shape you're expecting, you must round the floating values you get using *sin()* and *cos()* to get integer coordinates (code not optimized):

```
function newimg= rotazione(img, an)
    anrad= (an/180)*pi;
    x= size (img, 1);
    y= size (img, 2);
    b= round (x*cos(anrad)+ y*sin(anrad));
    h= round (x*sin(anrad)+ y*cos(anrad));
    for i=1:x
        for j=1:y
            cx(i,j)= round (i*cos(anrad) - j*sin(anrad));
            cy(i,j)= round (i*sin(anrad) + j*cos(anrad));
        end
    end
    px= min (cx(:));        // Bounding box: get the minimum x coordinate among all
    py= min (cy(:));        // Bounding box: get the minimum x coordinate among all
    for i=1:x
        for j=1:y
            cx= round (i*cos(anrad) - j*sin(anrad));
            cy= round (i*sin(anrad) + j*cos(anrad));
            if (px < 0)
                cx= cx + abs (px) + 1;
            end
            if (py < 0)
                cy= cy + abs (py) + 1;
            end
            newimg (cx, cy)= img (i, j);
        end
    end
end

```

To answer your question, I tell you you don't need to find a way to get the unmapped pixels in the rotated image. First, you *can't*, because you mapped forward all available pixels the starting image has.

There's a simple way to find a solution to this problem. Instead of rotating forward the original image, you can just consider the area your rotated image is going to be drawn into (you have to calculate the final bounding box) and apply the inverse rotation. This way you are going to map back all the pixels you're supposed to see on the screen. This is achieved by considering any pixel *P'(x',y')* in the final rectangle and apply the inverse function for rotation:

When using *sin()* and *cos()* here, you are not forced to round these values, but you can even interpolate the value with nearby pixels to get different effects: no interpolation (nearest), linear interpolation, bi-linear, and so on:

```
function [ out ] = ruota_nearest_semplice( img , gradi)
    // Rotates the image applying a nearest-neighbour interpolation
    // but computing for every pixel inside the bounding box
    [x, y]=size(img);
    gradi=(gradi/180)*pi;
    kernel=[cos(-gradi) sin(-gradi);-sin(-gradi) cos(-gradi)];
    c1=[x y]./2;
    d=ceil([ abs(x*cos(gradi)) + y*abs(sin(gradi)) abs(x*sin(gradi)) + abs(y*cos(gradi))]);
    out=ones(d);
    c2= round(d./2);
    for i=1:d(1) %x
        for j=1:d(2) %y
            p=([i j]-c2);
            p1=round(p*kernel)+c1;
            if(p1(1)>0 && p1(2)>0 && p1(1)<=x && p1(2)<=y)
                out(i,j)=img(p1(1),p1(2));
            end
        end
    end
end

```

This is just some pseudo-code from MatLab, but I hope it can be useful for you to make your own script.

---
Tags: image, interpolation
---


# Question
Title: How would I create a billboard that is fixed to my camera's farplane?
I'm trying to set a GameObject(plane) to be positioned at my camera's farplane. I plan on using this billboard as a sort of dynamic skybox. How would I create a billboard that is fixed to my camera's farplane?

# Answer
I'd do this in the shader:

```
Shader "Unlit/SkyplaneShader"
{
    Properties
    {
        _MainTex ("Texture", 2D) = "white" {}
    }
    SubShader
    {
        Tags { "RenderType"="Opaque" "Queue"="Geometry+1"}
        LOD 100

        Pass
        {
            CGPROGRAM
            #pragma vertex vert
            #pragma fragment frag

            #include "UnityCG.cginc"

            struct appdata
            {
                float4 vertex : POSITION;
                float2 uv : TEXCOORD0;
            };

            struct v2f
            {
                float2 uv : TEXCOORD0;
                float4 vertex : SV_POSITION;
            };

            sampler2D _MainTex;
            float4 _MainTex_ST;

            v2f vert (appdata v)
            {
                v2f o;
                o.vertex = float4(v.uv * 2.0f - 1.0f, 0.9999f, 1.0f);
                o.uv = TRANSFORM_TEX(v.uv, _MainTex);
                return o;
            }

            fixed4 frag (v2f i) : SV_Target
            {
                // sample the texture
                fixed4 col = tex2D(_MainTex, i.uv);
                return col;
            }
            ENDCG
        }
    }
}

```

What this does is take a quad or and stretch it to fill the camera's viewport, at the furthest depth.

Note that this breaks Unity's expected bounds on the object - it's always in view, no matter whether Unity thinks the mesh is outside the camera frustum. I'd recommend either parenting it to the camera so they move together, or using a script to disable frustum culling on this object.
> 2 votes

# Answer
First of all Skybox is not that sort of thing you are trying to create. It is a set of 6 images representing **up, down, left, right, top, bottom**. To understand it, make it simple, consider your camera is in a cube and your cube has definitely all 6 faces. For more details see this link.

Second *Plane* is quite expensive as compare to *Quad*, so if you want to use it in this way (anyway) then use Quad instead.

Third is I'd would suggest to use *Quad* on different layer rendering with a different camera, camera having depth less than your Main Camera and only rendering that *Quad*. From this easy step you will get your desired effect as your question is pretending.
> 0 votes

---
Tags: unity, c#, billboarding
---


# Question
Title: Why is my canvas being rendered underneath everything?
I'm currently trying to implement a UI that will overlay a scene and follow a scene's main camera, but I'm running into some issues. When I set canvas's mode to `Screen Space - Camera`, the `Z` position of the canvas is always set to `89.5`, which is behind all of the objects that are generated into my scene, making the canvas and the UI elements on it completely invisible to the player.

This is the game preview before running the game, with the UI elements clearly visible:

This is the game while it's running in the editor, with the UI elements not visible at all:

This is what my hierarchy looks like:

This is what the properties for the canvas look like:

Why is my UI not visible when I run my game? How can I fix this?

# Answer
> 5 votes
Set the render mode of your camera to "Screen Space - Overlay". That way it will always be on-top of the actual game scene.

When you set the mode to "Screen Space - Camera", the "Plane Distance" determines what's drawn in front and what's drawn behind the canvas. Everything which is closer to the camera than the plane distance will be drawn in front. The objects in your game likely have a z-value of less than 100, so everything is drawn in front of the canvas.

For more information on the canvas render mode settings, see the documentation.

# Answer
> -1 votes
Set the Z in the parent object to what you want it to be and try it again.

---
Tags: unity, gui
---


title: Canvas/Paint Mechanic

text:
# Question
Title: Canvas/Paint Mechanic
I'm currently working on an idea for a Unity game app with a canvas mechanic. I understand I may have to use particles for the brush/paint f/x however I can not think of a way to add collision detection let alone the paint itself...onto a canvas... Any suggestions are much appreciated!

# Answer
You can use both particles (for the animation) and another system to really "paint" the surface. What I would do is use one or multiple invisible spheres that I would "trow" in direction of the canvas (with a Rigidbody, so it's affected by gravity), and then, detect collisions.

You could also use Raycasting.
> 0 votes

---
Tags: collision-detection, game-mechanics, collision-resolution
---


# Question
Title: How to make the snake to pass from one side of the screen and come out the opposite side?
How do I code the left and right collision, and also tell me how I can set the collision of snake according to the form size.

If i want to change or maximize the form, snake should collide with the ending boundaries of the form ..

# Answer
> 1 votes
I can answer one of your problems enough to allow you to fill in the rest. I'm a C++ developer, so I'm not gonna be your best source of information. (For the heads up)

To collision detect the border of the window, you'd say something like:

```
int xMin = 0, xMax = this.width;
int yMin = 0, yMax = this.height;

if (player.x <= xMin) {
    // Arguments go here for if object player has passed the left of the window border.
} else if (player.y >= yMax) {
    // Arguments here for if object player is passing the bottom of the screen.
}

```

So that's all I've got, but I hope it helps. Good luck! I only know that information bc I had to make a pong game in C++ using Windows Forms, it's extremely hard, and it had TONS of bugs.

# Answer
> 0 votes
I had to do this whilst learning basics of c++, its one of the first things we had to do for collision detection so hopefully I can be of some use

Youll want to store the width and height of your screen in variables, and then perform a collision check to determine whether or not you have touched the screen and set the snakes position to, for example, the same on the x axis but at the other side of the screen.

This is a basic example from my work

```
if (object.position.X > window.width)
{
    object.position.X = 0;
}
else if (object.position.X + object.sourceRect.Width < 0)
{
    object.position.X = this.Width - object.sourceRect.Width;
}

```

By using this.Width, even if the form changes in size, the check should still work

Alls this is doing is the X axis checks, but you also need to take into account the width of the object that is going to be colliding, not just its x and y positions

From what youve got, you seem to already have the collision checks implemented. All's you should need to do now is set the snakes position to the other side of the screen, and from whatt I've shown you, and a bit of trial and error, it shouldn't be too hard:)

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


title: Understanding Scriptable Objects

text:
# Question
Title: Understanding Scriptable Objects
I am trying to understand the logic and functionality behind Scriptable Objects. I 've watched the provided video 2 times and I keep getting lost. I tried to follow the code as well but with no luck.

Can someone please explain to me what the Scriptable Objects are and how they work in a few lines?

\[EDIT:\] *This* **Video** as well as the following answers helped me understand Scriptable Objects and even better incorporate them in my own game.

# Answer
> 13 votes
`ScriptableObjects` are **just data**... except that they *look like* assets (drag-and-droppable on objects, contained in "Assets", etc).

Consider this code:

```
class ItemShop
{
   ItemList MyAvailableItems;
}

```

Now, for every `ItemShop` instance you create, `MyAvailableItems` contains a unique `ItemList`. Even if every `ItemShop` sells the same set of items, they will each contain their own unique copies. If one instance of the "shared" list is changed, it will NOT propagate back to the original `ItemList` source.

If `ItemList` was a `ScriptableObject`, you could create 100 `ItemShops` and drag the same `ItemList` (from Assets) onto them all. Every instance **REFERENCES** the original (one and only) `ItemList` that you assigned. There is never more than one copy of the `ItemList` in memory.

Additionally, by accessing an entire `ItemList` through a single reference, you can change the items available at the `ItemShop` by swapping in a different reference (one line of code (or a drag and drop, if in editor)).

**Be aware:**

While you are designing your game, you have access to the `Editor` namespace. That allows you to create and/or modify `ScriptableObjects` (at run-time) and then persist those changes back into the actual assets. This lets you run the game, actually visit "tier 3", actually visit the actual item shop, actually change the actual list (at run-time) and then "save" the changes, permanently.

Once built, the `Editor` namespace is lost as well as the ability to persist changes. For that reason, `ScriptableObjects` are **NOT** for saving/loading of run-time-generated data in **built** games; this is a common misunderstanding.

**Edit:**

```
//Data
//(De)serialization is probably your next stop
[System.Serializable] //This will become clear then
class AIBehaviorData //or struct
{
   public float AttackPriority = 0.5f;
   public float DefensePriority = 0.5f;
}

//Implementation
abstract class AIBehavior : ScriptableObject
{
   public bool SomeFlag = false;
   public void Update(AIBehaviorData instanceData) = 0;
}
class TurtleAI : AIBehavior
{
   public override void Update(AIBehaviorData instanceData)
   {
      //Obviously, no need to assign these over and over...
      //Just example data
      instanceData.AttackPriority = 0.3f;
      instanceData.DefensePriority = 0.7f;
      ... //turtle stuff
   }
}
class AggressiveAI : AIBehavior
{
   public override void Update(AIBehaviorData instanceData)
   {
      //Obviously, no need to assign these over and over...
      //Just example data
      instanceData.AttackPriority = 0.8f;
      instanceData.DefensePriority = 0.2f;
      ... //aggressive stuff
   }
}

//Dummy wrapper
class AI_NPC : MonoBehavior
{
   public AIBehaviorData MyInstanceData;

   public AIBehavior MyPersonality; //Public access, visible in inspector, drag-and-drop

   //[HideInInspector]
   //public AIBehavior MyPersonality; //Public access, but not visible in inspector
   //Probably assigned by "AIManager" while creating AI instances

   //private AIBehavior MyPersonality; //Must initialize locally with Awake/Start/OnEnable

   public void Update()
   {
      //Modify my data based on my personality
      if (MyPersonality.SomeFlag)
        MyInstanceData.AttackPriority++;

      //or

      //My personality modifies my data
      if (MyPersonality != null)
        MyPersonality.Update(MyInstanceData);
   }
}

--------------------------------------------------
**Editor namespace**
//Will not build if in same file
using UnityEditor;
//These make your objects really come to life (in the editor at least)
[CustomEditor(typeof(AI_NPC))]
class AI_NPC_Editor : Editor
{
   void OnInspectorGUI()
   {
      serializedObject.Update();
      //This is where the inspector panels are assembled
      AI_NPC inspectedAI = (AI_NPC)target;
      if (inspectedAI.MyPersonality is TurtleAI) //polymorphism
      {
         //Display "turtle" properties (data is in same struct either way)
         ...
         inspectedAI.MyInstanceData.SomeFlag =
            EditorGuiLayout.Toggle(inspectedAI.MyInstanceData.SomeFlag); //checkbox
      }
      else if (inspectedAI.MyPersonality is AggressiveAI)
      {
         //Display "aggressive" properties (data is in same struct either way)
         ...
      }
      serializedObject.ApplyModifiedProperties();
   }
}

```

Now you can drag-and-drop personalities onto AI's. One copy of each is resident in memory at any time, regardless of how many times it is referenced.

---

**Edit:**

The `ScriptableObject` **asset** will be "reset to factory", every time the game loads. If you go to the definition of `ScriptableObject`, you will find that it inherits from `Object` which means you can `Instantiate<>()` (clone) them. Those clones can be overwritten with run-time data, loaded from disk. The class/struct that holds the item-counts for a particular shop can **be** a `ScriptableObject`, that references a specific `ItemList` (a `ScriptableObject`). In that case, a quantity means "there are ten `ItemList[0]`'s available at this shop, right now" (the item list can be swapped out).

If the majority of this answer and `ScriptableObject` makes sense to you, move on to serialization. When you have the save/load framework in place, "where things belong" should become more obvious; you'll probably find that the quantities belong within the `ItemShop` instance, not the `ItemList` (an `ItemShop` "has" an `ItemList` and item-counts, an `ItemList` "has" only items). An `InventoryList` (class/struct or `ScriptableObject`) could reference an `ItemList` (`ScriptableObject`) and contain quantities. Both can be dynamically modified at run-time during save/load.

Based on where they intuitively belong, "should I use a `ScriptableObject` here?" will also be more obvious. If each `ItemShop` has its' own item-count list, there's really nothing to reference; since you HAVE to have multiple instances of the class/struct, the clear benefit of using a `ScriptableObject` instead is diminished. If multiple `ItemShops` can "share inventory", then `ScriptableObject` may be the way to go. You have to consider the size of one class/struct instance, as well as how many identical copies you will be making.

From the tutorial, the "list of 1000 int's" (`Int32`) would occupy approximately 32 KB of memory, so ten copies of that list would occupy approximately 320 KB. Depending on the platform you are developing for, the "excessive memory usage" may not be worth fixing. My PC has about 6,291,456 KB (6 GB) of memory, so 320 KB is 0.005% of my total memory that I don't mind you using. But, if your game can't run on my preferred device (an older Android), I can't buy it.

Some `ItemShops` sharing, and some not, is probably your "worst case", in terms of complexity:

```
[Serializable]
class QuantityData
{
   public ItemList Items;
   ... //Probably a few List<int> representing min/max/current
}
class ScriptableQuantityData : ScriptableObject
{
   public QuantityData MyQuantityData;
}
class ItemShop : MonoBehavior
{
   public QuantityData MyQuantityData = null;
   public ScriptableQuantityData MyScriptableQuantityData = null;

   void DoSomething(int itemID)
   {
      if (MyScriptableQuantityData != null) //Shared inventory
      {
         //MyScriptableQuantityData.MyQuantityData.Items[itemID]
         ...
      }
      else if (MyQuantityData != null) //Private inventory
      {
         //MyQuantityData.Items[itemID]
         ...
      }
      else
      {
         Debug.Log("Error: no QuantityData assigned");
         //throw new exception("Error: no QuantityData assigned");
      }
   }
}

```

Regardless of how you end up layering the data structures, you'll have to provide the (de)serialization mechanism for anything you want to include in save/load. Classes derived from `ScriptableObject` are not `[Serializable]` so you'll need to add enough information for saving so you can reconstruct the objects during load.

It is easy to drag-and-drop `ScriptableObjects` in the Editor. How does an `ItemShop`, loaded from disk, know which of the `QuantityDatas`, also loaded from disk, belongs to **this** shop? Do they have names or unique ID's? You can count on `ItemList[0]` being the same list, time after time, as long as you load/save the same way every time.

Serialization is going to drive most, if not all, of your decision-making from now on.

(I also agree that the tutorial falls short in some critical way, although I can't say precisely how)

# Answer
> 3 votes
Scriptable objects are data containers to be used in the editor. It is basically a standard data class, except you can make a custom window in the editor to edit that data. It is for making tools to extend Unity.

*Disclaimer: I just started with scriptable objects myself, so take my answer with a grain of salt, and please correct me if I am wrong.*

# Answer
> 3 votes
Adding to the great answers, ScriptableObjects can also contain methods. You could create something like an EventService asset for messaging, passing an instance to your scripts for them to subscribe and use.

You could say that whenever you find yourself considering Singleton patterns, ScriptableObjects as assets usually work just as well (or even better).

---
Tags: unity, c#
---


# Question
Title: Running subsystems at difference update intervals
I want to update the rendering at 60fps, but the logic at some lower rate, say 15Hz. But if an object only moves when the game logic updates, then it would appear to stutter badly especially for lower frequencies. I guess the rendering system could interpolate an entity's vector and draw the model moving at a lower dt, but if the game logic causes the entity to change direction it will appear to teleport back, and so on. I can imagine many more problems.

How is this usually solved in games? Surely most engines want to decouple rendering from game logic, so there must have been some though put into this. Or does everyone just update all systems that have graphical effects at the same rate?

# Answer
> 1 votes
What you've described is backwards. If nothing has updated, then there's no reason to redraw anything. You've suggested showing the same image 4 times before updating it, limiting your *effective* graphical frame-rate to only 15Hz.

What you want to do is `Update()` using the smallest deltaTime possible. This allows animations to take more, smaller steps, increasing visual fidelity.

You don't have to `Update()` every object's velocity vector, every frame, but you should `Update()` every object with a velocity, every frame.

# Answer
> 1 votes
I would decouple the different concepts, and having 3 systems with separate goals:

1. Position/Render system: updates/applies the visual position of your object every time this is rendered (60Hz)
2. Logic system: takes decisions like "now I want to go towards point B" (15 Hz)
3. Motion (or similar) system: "translates" the decisions taken by the Logic into whatever action are needed, for instance creating an interpolation from the current point towards point B (60Hz)

This way you keep the lower level system atomic and independent from each other (Position and Logic) and create a higher level system as a glue between them.

---
Tags: animation, rendering, game-loop, timestep, fixed-timestep
---


# Question
Title: LibGDX Textfield - Text Overflow - Not Wrapping
In my app's registration screen, the textfield is not wrapping text as I expected. Notice in the above image, the email field is not containing the text. I have set the size of the textfield using `setSize()` method but I couldn't find any way to wrap text. Is there any solution to this?

I'm using LibGDX v1.9.0.

**EDIT:** I don't have problem with overflowing but I think it should be hidden beyond the textfield borders.

**UPDATE:** It was indeed carelessness from my part. I actually included a padding to the textfield position which I didn't correct when defining its size. Issue got solved now. I don't know whether I should keep the question or delete it.

# Answer
The **libGDX** `TextField` is, according tho the API specification, a "*A single-line text input field.*".

That's why it's not wrapping the text.
> 1 votes

---
Tags: android, libgdx, gui
---


# Question
Title: How is time/duration handled in strategic games?
I'm considering developing a space opera game, having already done some game design. Technically, though, I'm coming from a business applications background. Hence I don't really know how I should handle time and duration.

Let's state the matter clearly: what if something is bound to happen in 5 hours and on which other events depend.

For example the arrival of some space ship in some system where some defense systems are present, hence a fight would start.

The aim is to do some web application, so with multiple nodes for better scalability and the like. Hence a single loop on one node wouldn't do it. Should there be a master node or are they some better known solution?

Furthermore, the loop in itself doesn't resolve this duration issue: between firing of the event on its ends, many loops happen. Does it mean every loop should check such "waiting" actions?

Should I use some kind of scheduler (like Quartz in my java land) to trigger the corresponding event when due (I plan to use events for communication)? Something else?

# Answer
Most games centre around a 'game step' loop. Things happen in discrete pacels of time.

It is straightforward to have a queue of future events and to consume those events for each game step.

More about game time-steps on the gafferongames blog.
> 6 votes

# Answer
Just record your game time, add it to a variable, once the variable gets to a certain amount, fire your event.
> 5 votes

# Answer
What you need is a priority queue with the *time of event* as priority. If you create an event that will happen in 5 hours, you add it to the priority queue; it will probably be inserted somewhere in the back as *in 5 hours* has a low priority. Your main event-loop will constantly work on your priority queue and will check if the priority of first even is *now*. If so, it will trigger the event. After 5 hours, your event will become the event with the highest priority in the queue and will be the first element. This will make the event-loop trigger the event. If the ship has exploded in the mean-time, you need to make sure that the event is removed from the queue... ;)
> 3 votes

# Answer
What kind of web application is it?

Is it one that runs all the time, as a continuous process? If so, simply do this with a standard game loop:

```
while app_still_running:
    check queue of pending events
    while the next pending event is due now:
        execute event
    sleep(some reasonable duration)

```

You may need to run this in a background thread if the rest of your app is event-driven: if so, be sure to put a lock around the whole event so that everything stays consistent.

Or, is the web app one that only runs when you visit a page? (eg. like a PHP app?) If so, you can have an entry at the top of each page which checks if events are due, and if so, process them at that point before rendering the rest of the page. It's basically the same thing, except done just-in-time instead of periodically.

Either way, the idea is to push events onto a queue and read them off in order. If you just have one process, this can be a queue data structure. If you have multiple processes, it's probably best to have them in a database and use a sorted query to collect them. (Though be careful to ensure multiple processes can't both read the same events.)

There is probably no reason why a single loop on one node isn't good enough for your purposes. You can designate one node as the master for performing all this. Or you can store pending events in the database and just have the various nodes grabbing a handful of events via a transaction. On the whole though your scalability problems will not be at the business logic end.

As far as consistency across nodes is concerned, where one node is processing an event but another is displaying or editing data relevant to that event, that's an issue for database transactions and the like. If you cache anything, you are pretty much throwing away consistency, so you have to make decisions over what can be cached, and what cannot. That starts to get outside the scope of this particular problem however.
> 1 votes

# Answer
You usually have some kind of "main loop" in your game that runs continuosly.

Depending on wether your game is multithreaded or not, this "main loop" looks different.

In a single threaded environment, your main loop usually looks like this

```
time = current time
while game is running
    deltaTime = (current time) - time
    // custom logic
    // e.g. updating the AI etc.
    // or polling input
    // or polling sockets when networking is involved
    render current state to screen
    sleep some reasonable amount
end

```

You would typically advance your simulation using the time delta. This allows your user to speed up or slow down the game as well (just multiply the delta with a time factor, e.g. 2, and the game runs twice as fast \[but especially when physics are involved, might lose precision\]).

You can simply add a priority-queue sorted by the (game) time an event should be done, and then check the top elements of the queue. If the time for the event is reached, execute it, otherwise sop iterating over the queue (if it is sorted by time, no other event can come).

In a multi-threaded system this gets a bit harder, but you typically enqueue things in the main thread then.
> 0 votes

---
Tags: architecture, web
---


# Question
Title: Fastest way to render isometric world with moving entities?
I've got an isometric diamond-shaped world. The world consists of isometric planes like rooms. The walls and floors of the rooms and all obstacles and items in the rooms are isometric entities. So I have a list with each existing object in the world. Each object has its own coordinates. x, y, and z. x is from top to right bottom, y is from top to left bottom, z is straight up into the air. Each object has also an isometric width and height as property.

Now I have to render the world correctly. I'm quite sure the only hard step is to sort each object by its depth, and this isn't that hard when nothing changes in the world. But of course everything changes... I want to figure out a sorting system which is very fast, so it doesn't do too much unnecessary work. I ended up with multiple articles, saying a pigeonhole sort is the way to go. But is this really the right solution? And doesn't this cause rendering glitches? I also read that I should use topological sorting. (https://en.wikipedia.org/wiki/Topological\_sorting).

# Answer
> 2 votes
From my own experience, I've found that using the sum of components (x + y + z) is a very good measure for sorting entities in an isometric scene. It doesn't perfectly represent the distance your image is away from the camera, but it does give an indication which image is further or closer to the camera, and that's what ultimately matters. Moreover, sums are incredibly cheap to compute.

You should re-sort your entity list every frame though.

In terms of implementation, it may be worth investigating whether you could use WebGL here. The library has built-in depth sorting that runs on the GPU and is therefore faster than anything you could write in JavaScript. Although it's a lot more complicated to get it working, of course.

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


# Question
Title: How can a game handle all characters at once?
This question is just to gain knowledge about how a game can handle so many characters at once. I am new to gaming so I beg your pardon in advance.

## Example

I am creating a tower defense game in which there are **15 tower slots** where towers are built and each tower ejects projectile at a certain rate; lets say that **every second, 2 projectiles** are created by each of the towers and there are **enemies marching on the battlefield, lets say 70** (each with 10 types of attributes like HP, mana, etc., which will change as they move around the battlefield).

## Summary

**Tower Count** = 15
**Projectiles Created By Each Tower Per Second** = 2
**Total Number of Projectiles Created Per Second** = 30
**Units in Battlefield Count** = 70

Now, does the game handle those **30 projectiles and 70 units** by handling them on **100 different threads** (which is too much for a PC) or **1 thread that moves all of them, reduces their value, etc.** (which will be kind of slow, I think)?

I do not have a clue about this so can anyone guide me on how this will work out?

# Answer
> Now how does the game handle those 30 Projectile and 70 units by handling them on 100 different threads

No, never do that. Never create a new thread per resource, this doesn't scale in networking, neither does it in updating entities. (Anyone remember the times when you had one thread for reading per socket in java?)

> 1 thread that moves all of them reduces their value etc?

Yes, for starters, this is the way to go. The "big engines" split some work between threads, but this is not needed to start a simple game like a tower-defense game. There's probably even more work to do every tick which you'll also do in this one thread. Oh yeah, and the rendering of course.

> (which will be kind of slow i think)

Well... What is your definition of *slow*? For 100 entities, it shouldn't take more than half a millisecond, probably even less, depending on your code-quality and the language you're working with. And even if it takes two full milliseconds, it's still good enough to hit the 60 tps (ticks per seconds, not talking about frames in this case).
> 78 votes

# Answer
Rule number one of multithreading is: Don't use it unless you *need* to parallelize on multiple CPU cores for performance or responsiveness. A requirement "x and y should happen simultaneously from the users point of view" is not yet sufficient reason to use multithreading.

Why?

Multithreading is hard. You have no control over when each thread gets executed which can result in all kinds of impossible to reproduce problems ("race conditions"). There are methods to avoid this (synchronization locks, critical sections), but these come with their own set of problems ("deadlocks").

Usually games which deal with such a *low* number of objects as just a few hundred (yes, this isn't that much in game development) usually process them in a serial manner each logic-tick using a common `for` loop.

Even the relatively weaker smartphone CPUs can perform *billions* of instructions per second. That means even when the updating logic of your objects is complex and takes about 1000 instructions per object and tick, and you are aiming for a generous 100 ticks per second, you have enough CPU capacity for tens of thousands of objects. Yes, this is a grossly oversimplified back-of-the-envelope calculation, but it gives you an idea.

Also, common wisdom in game development is that the game logics are very rarely the bottleneck of a game. The performance-critical part is almost always the graphics. Yes, even for 2d games.
> 39 votes

# Answer
The other answers have handled the threading and power of modern computers. To address the bigger question though, what you are trying to do here is avoid "n squared" situations.

For example if you have 1000 projectiles and 1000 enemies the naive solution is to just check them all against each other.

This means you end up with p\*e = 1,000\*1,000 = 1,000,000 different checks! This is O(n^2).

On the other hand if you organize your data better you can avoid a lot of that.

For example if you list on each square of the grid what enemies are in that square then you can loop through your 1000 projectiles and just check the square on the grid. Now you just need to check each projectile against the square, this is O(n). Instead of a million checks each frame you only need a thousand.

Thinking about organizing your data and processing it efficiently due to that organisation is the biggest single optimization you can ever make.
> 26 votes

# Answer
Do not create threads per resource/object but per section of your program logic. For example:

1. Thread to update units and projectiles - **logic thread**
2. Thread for rendering the screen - **GUI thread**
3. Thread for network (eg. multiplayer) - **IO thread**

The advantage of this is that your GUI (eg. buttons) does not necessarily get stuck if your logic is slow. User can still pause and save the game. It's also good for preparing your game for multiplayer, now that you separate the graphic from the logic.
> 17 votes

# Answer
Even Space Invaders managed dozens of interacting objects. Whereas decoding one frame of HD H264 video involves hundreds of millions of arithmetic operations. You have a *lot* of processing power available.

That said, you can still make it slow if you waste it. The problem is not so much the number of objects as the number of collision tests performed; the simple approach of checking each object against each other object **squares** the number of calculations required. Testing 1001 objects for collisions this way would require a million comparisons. Often this is addressed by e.g. not checking projectiles for collision with each other.
> 4 votes

# Answer
I am going to disagree with some of the other answers here. Separate logic threads are not only a good idea, but hugely beneficial to processing speed - **if your logic is easily separable**.

Your question is a good example of logic that is probably separable if you can add some additional logic on top of it. For example, you could run several hit detection threads either by locking the threads to specific regions of space, or mutexing the objects involved.

You probably do NOT want one thread for every possible collision, just because that is likely to bog down the scheduler; there is also a cost associated with creating and destroying threads. Better to make some number of threads around the system's cores (or utilize a metric like the old `#cores * 2 + 4`), then reuse them when their process finishes.

Not all logic is easily separable, though. Sometimes your operations can reach across all game data at once, which would make threading useless (in fact, harmful, because you would need to add checks to avoid threading issues). Further, if multiple stages of logic are highly dependent on each other occurring in specific orders, you will have to control the execution of threads in such a way as to ensure that does not give order-dependent results. However, that issue isn't eliminated by not using threads, threads just exacerbate it.

Most games don't do this simply because it is more complex than the average game developer is willing/able to handle for what is usually not the bottleneck in the first place. The vast majority of games are GPU-limited, not CPU-limited. While improving the CPU speed can help overall, it's usually not the focus.

That said, physics engines often employ multiple threads, and I can name several games I think that would have benefited from multiple logic threads (the Paradox RTS games like HOI3 and such, for example).

I do agree with other posts that you probably would have no need to employ threads in this specific example, *even if* it could be beneficial. Threading should be reserved to cases where you have excessive CPU load that cannot be optimized down via other methods. It is a huge undertaking and will affect the fundamental structure of an engine; it isn't something you can tack on after the fact.
> 3 votes

# Answer
I think the other answers miss an important part of the question by focusing too much on the threading part of the question.

**A computer doesn't handle all objects in a game at once at all. It handles them in sequence.**

A computer game progresses in discrete time-steps. Depending on the game and the speed of the PC, these steps are usually either 30 or 60 steps per second, or as many/few steps as the PC can calculate.

In one such step, a computer calculates what each of the game objects will do during that step and updates them accordingly, one after another. It could even do so in parallel, using threads to be faster, but as we'll soon see speed is not a concern at all.

An average CPU should be 2 GHz or faster, that means 109 clock cycles per second. If we calculate 60 timesteps per second, that leaves 109 / 60 clock cycles = 16,666,666 clock cycles per time step. With 70 units, we still have about 2,400,000 clock cycles per unit left. If we had to optimize, we might be able to update each unit in as little as 240 cycles, depending on the complexity of the game logic. As you can see, our computer is about 10,000 times faster than it needs to be for this task.
> 2 votes

# Answer
## Disclaimer: My all time favourite type of game is text-based and I write this as a long time programmer of an old MUD.

I think an important question you need to ask yourself is this: Do you even need threads? I understand that a graphical game probably has more use of MTs but I think it also depends on the mechanics of the game. (It might also be worth considering that with GPUs, CPUs and all the other resources we have today are far more powerful which makes your concerns of resources as problematic as it might seem to you; indeed 100 objects is virtually zero). It also depends on how you define 'all characters at once'. Do you mean at the exact same time? You won't have that as Peter rightfully points out so all at once is irrelevant in the literal sense; it only appears this way.

Assuming you will go with threads: You definitely should not consider 100 threads (and I am not even going to get into whether it is too much for your CPU or not; I refer only to the complications and the practicality of it).

But remember this: multiple-threading is not easy (as Philipp points out) and has many problems. Others have much more experience (by a lot) than I do with MT but I would say they too would suggest the same thing (even though they would be more capable than I would be - especially without practise on my part).

Some argue that they disagree that threads aren't beneficial and some argue that each object should have a thread. But (and again this is all text but even if you consider more than one thread you need not - and should not - consider it for each object) as Philipp points out games tend to iterate through the lists. But yet it isn't only (as he suggests although I realise he is only responding to your parameters of so few objects) for so few objects. In the MUD I am a programmer for we have the following (and this isn't all the activity that happens in real-time so keep that in mind too):

(The number of instances do vary of course - higher and lower)

Mobiles (NPC i.e. non player character): 2614; prototypes: 1360 Objects: 4457; prototypes: 2281 Rooms: 7983; prototypes: 7983. Each room has its own instance usually but we also have dynamic rooms which is to say rooms within a room; or rooms inside a mobile e.g. the stomach of a dragon; or rooms in objects e.g. you enter a magical object). Keep in mind that these dynamic rooms exist per object/room/mobile that actually has them defined. Yes this is very much like World of Warcraft's (I don't play it but a friend had me play it when I had a Windows machine, for a while) idea of instances except we had it long before World of Warcraft even existed.

Scripts: 868 (currently) (oddly enough our statistics command doesn't show how many prototypes we have so I will be adding that). All of these are held in areas/zones and we have 103 of those. We also have special procedures that proc at different times. We also have other events. Then we also have connected sockets. Mobiles move around, do different activities (besides combat), have interactions with players, and so on. (So do other types of entities).

How do we handle all this without any delay?

* sockets: select(), queues (input, output, events, other things), buffers (input, output, other things), etc. These are polled 10 times a second.
* characters, objects, rooms, combat, everything: all in a central loop on different pulses.

We also (my implementation based on discussion between the founder/other programmer and myself) have extensive linked list tracking and pointer validity testing and we have more than enough free resources should we actually have a need for it. All of this (except we have expanded the world) existed years ago when there was less RAM, CPU power, hard disk space, etc. And indeed even then we had no problems. In the loops described (scripts cause this as do area resets/repopulations as do other things) monsters, objects (items), and other things are being created, freed, and so on. Connections are also accepted, polled, and everything else you would expect.
> 0 votes

---
Tags: game-mechanics, multithreading, strategy, tower-defense
---


title: Game industry layoffs?

text:
# Question
Title: Game industry layoffs?
I want to be a game programmer and it's come to my attention that people who work in this industry are laid off/fired every few years. Can someone please tell me how to deal with this? Thanks

# Answer
> 1 votes
Sebastian, you are in for a reality check. You make it sound like layoffs happen only in the game industry.

You may want to have a look at what happens in other industries. Many jobs disappear, Many companies go bankrupt or downsize. Intel just announced major layoffs. Microsoft had them in the last years.

You cope by finding another job. This is not Japan in 1920 where jobs were assumed to be for life. This is the year 2016 and you are explicitly NOT guaranteed a job for life. Many jobs will disappear in the next years.

Want guarantees? Be much better than your peers (and in programming I have seen standards go down to incompetence in the last 15 years, sadly) and you will not be fired first.

# Answer
> 0 votes
As game developer you might be hired for a project, or you might be hired by a company that files for bankruptcy after disappointing sales of a single title. That's like working for a start-up in any other industry. You also might be hired by a humongous soul-crushing entity which provides job security but low wages and very little artistic freedom, so you might decide to quit on your own.

Personally, I don't think I'll ever commit myself to any industry for several decades. Don't tie yourself to an industry. You get skills. These skills may be especially valuable in one place, but they are still valuable in lots of other places.

---
Tags: jobs
---


# Question
Title: How do I take 2D ballistic trajectory planning and apply it to 3D?
I am currently using this formula

```
speed = sqrt((gravity.y*target.x^2)/(2*cos^2(angle)*(target.y - target.x*tan(angle)))

```

provided by DMGregory as an answer for my question here to determine the speed of a trajectory given an angle and start/end points. So now I need to be able to apply this to a 3D scenario. How would I go about doing that?

# Answer
> 1 votes
First, we pick out a unit vector describing our vertical axis (or, more generally, the axis on which the constant acceleration is being applied):

```
Vector3 vertical = Vector3.up;  // If wind introduces diagonal acceleration,
                                // include it here too and normalize.

```

Then we isolate the perpendicular/horizontal component of the offset from the start to the end of the trajectory:

```
Vector3 toTarget3D = end - start;
Vector3 horizontal = (toTarget3D - Dot(toTarget3D, vertical) * vertical).normalized;

```

Now we can project our problem into 2D using this basis:

```
Vector2 toTarget2D = new Vector2(
               Dot(toTarget3D, horizontal),
               Dot(toTarget3D, vertical));

```

You can now solve this the same as the 2D version of the problem.

`... // Solution logic goes here`

Then, once you have your velocity in 2D, you can unproject back to 3D:

```
 Vector3 velocity3D = velocity2D.x * horizontal
                    + velocity2D.y * vertical;

```

In practice, you might embed these translations into your formulae, so you don't explicitly switch dimensionality anywhere, but here I've shown it completely separate so you can drop whatever solution method you prefer into that `...`

---
Tags: 3d, projection, trajectory
---


# Question
Title: Java RPG class implementation (design pattern ?)
For my school project I'm making a little NFC based game on Android. The concept is simple, on each phone you create a character and you can fight with other people through NFC.

The character will have have a set of attributes, like strength, agility, etc which are represented as short (only 2 bytes =\> for NFC communication). A character must have a race (human, dwarf, ...) and a class (warrior, wizard, ...). Each race has attribute advantages (ex : + 2 strength for dwarf) and a passive bonus ex : +5% gold after a fight. Each class can wear different weapon and will have a different attack() methods.

My problem is that I don't know how I should create my character class and allow it to have a race and a class.

Does anyone have an idea of how I can accomplish this ?

# Answer
As hinted at in the comments, you'll want to use a combination of Inheritance and Composition. (Inheritance being ***is a*** and Composition being ***has a***).

In your case, each Character **isn't** a race or a class, but instead **has** a race and **has** a class.

Each race would then inherit from a base Race class, and each Class would inherit from a base Class class.

An example Character class setup:

```
public interface CharacterClass {
    int doSomething(Character me);
    int applyBonusOrSomesuch(Character me);
}

public interface Race {
    int doSomethingRacial(Character me);
    int applyRacialBonuses(Character me);
}

// Example Race
public class Elf implements Race {
   // Implement the Race methods
}

// Example "Class"
public class Cleric implements CharacterClass {
    // Implement the CharacterClass methods
}

// The Compositional Character class
public class Character {
    Race _race;
    CharacterClass _class;

    ...

    public void ApplyBonuses(){
        _race.applyRacialBounuses(this);
        _class.applyBonusOrSomesuch(this);
    }
    ...
}

```

You then set the Race and CharacterClass on creation, or whenever is suitable. The Character class would then call the Race and CharacterClass methods as appropriate, and the methods for the classes passed in (e.g. Elf for Race and Cleric for CharacterClass) would then be called.
> 2 votes

# Answer
I would do this rather than have a dozen classes and races;

```
public class GameCharacter
{
    public enum CharacterClass
    {
        WARRIOR
        {
            @Override
            public void attack(GameCharacter from, GameCharacter target)
            {
                //Do something here
            }
        },

        MAGE
        {
            @Override
            public void attack(GameCharacter from, GameCharacter target)
            {
                //Do something here
            }
        };

        public void attack(GameCharacter from, GameCharacter target)
        {
            //Default attack implementation
        }
    }

    public enum CharacterRace
    {
        HUMAN, ELF, DWARF, ORC;
    }

    private CharacterClass cClass;
    private CharacterRace race;

    public GameCharacter(CharacterClass cClass, CharacterRace race)
    {
        this.cClass = cClass;
        this.race = race;
    }

    public void attack(GameCharacter target)
    {
        cClass.attack(this, target);
    }
   //Some more methods
}

```

This allows you as much flexibility as the other method, and IMHO is more extendable (ie just add a new member to either race or class to extend them).
> 0 votes

---
Tags: android, rpg, design-patterns
---


# Question
Title: Which data structure should be used to represent voxel terrain?
According to the Wikipedia page about voxels, "\[...\] the position of a voxel is inferred based upon its position relative to other voxels (i.e., its position in the data structure that makes up a single volumetric image)."

How should one implement such a data structure? I was thinking about an octree but I'm wondering if there's something else that I never heard about.

# Answer
> 14 votes
First. Lets write what do we know about each voxel :

```
voxel = (x, y, z, color) // or some other information

```

## General storage

General way is simply this:

```
set of voxels = set of (x,y,z, color)

```

Note, that triplet (x,y,z) identify each voxel uniquely, since voxel is point in space and there is no way two points occupy one place (I believe we are talking about static voxel data).

It should be fine for simple data. But it is by no means a fast data structure.

Rendering is AFAIK done by scanline algorithm. Tom's Hardware article on voxels has image of scanline algorithm.

## Fast lookup

If fast lookup is needed, then the fastest data structure for lookup is hash (aka array, map ...). So You have to make hash out of it. So, naively we want just fastest way to get arbitrary element:

```
array [x][y][z] of (color)

```
* This has O(1) for looking up voxel by x,y,z coordinates.
* Problem is, that it's space requirements are O(D^3), where D is range of each x,y and z numbers (forget Real number, since if they were Chars, which have range of 256 values, there would be 256^3 = 2^24 == 16 777 216 elements in array).

But it depends on what You want to do with voxels. If rendering is what You want, then it is probably this array what You want. But problem of storage still remains ...

## If storage is the problem

One method is to use RLE compression in the array. Imagine a slice of voxels (set of voxels, where voxels have one coordinate constant value .... like plane where z = 13 for example). Such slice of voxels would be looking like some simple drawing in MSPaint. Voxel model, I'd say, usually occupy fraction of all the possible places (D^3 space of all possible voxels). I believe, that "take a pair from triplet of coordinates and compress the remaining axis" would do the trick (for example take \[x\]\[y\] and for each element compress the all voxels at z axis at given x,y ... there should be 0 to few elements, RLE would do fine here):

```
array [x][y] of RLE compressed z "lines" of voxel; each uncompressed voxel has color

```

Other method to solve storage problem would be instead of array using tree data structure:

```
tree data structure  = recursively classified voxels
for octrees: recursively classified by which octant does voxel at (x,y,z) belong to

```
* Octree, as mentioned by Nick. It should compress voxels. Octree has even a decent speed for lookup, I guess it is some O(log N), where N is number of voxels.
* Octree should be able to store decently arbitrary voxel data.

If voxels are some simplistic heightmap You might store just that. Or You might store parameters to function which generates the heightmap, aka procedurally generate it ...

And of course You can combine all possible approaches. But don't overdo it, unless You test that Your code works and measure that it is REALLY faster (so it is worth the optimization).

## TL;DR

Other than Octrees is RLE compression with voxels, google "voxlap", "ken silverman" ...

## Resources

There is list of resources and discussion on how to make fast voxel renderer, includes papers and source code.

# Answer
> 4 votes
There are two different data structure aspects they may be talking about.

**Array structures**

When you reference an element of an array of any number of dimensions, consider that the array itself, once you pass the indices (eg. `myArray[4][6][15]`) knows what is at that location. If what is at that location is a voxel, that voxel doesn't need to additionally record it's own x, y, and z coordinates -- the array holding the voxel specifies it's world location implicitly based on it's array-indexed location.

The reason this is good is that the pointer arithmetic used for this sort of array access is inherently *fast* and generally speaking, provides the foundation for most of the quick (often called "native") arrays found across languages. The downside to these arrays is that they must have elements of equal size in bytes, in order for said pointer arithmetic to be applicable.

**Octrees**

(I note this second, because this is less likely to be what wikipedia refers to, and voxel implementations do not require the use of octrees although nearly all modern ones do use octrees.)

An octree's root node is a single, undivided cube. Let's set up an example. Say your octree's root, the very centre of the cube, is at `{0, 0, 0}` in 3D space. Once you begin to place objects within that space (read: more than one object), it is time to subdivide the octree further. This is where you divide into 8 (*oct-*), by slicing it up using 3 planes, these planes being the xy, xz and yz planes. Your original cube now exactly contains 8 smaller cubes. Each of these sub-nodes is positioned as *an offset from the central, parent cube*. That is, that for example, the cube lying in the positive xyz octant would have an offset from the parent / containing cube's centre of exactly `{root.width / 4, root.height / 4, root.depth / 4}`. Rather than specifying an absolute position for each subnode, it makes more logical sense to consider the parent node as the origin of its childrens space. This is the same way scene graphs work.

It is simple enough to see this in a 2D drawing, where you draw a square, and subdivide it into 4 equal regions. If, like our octree root node, the centre of the parent square were considered to be `{0, 0}`, then the 4 centres of the child squares would be

`{root.width / 4, root.height / 4}`, `{-root.width / 4, root.height / 4}`, `{root.width / 4, -root.height / 4}`, `{-root.width / 4, -root.height / 4}`

...As relative to their parent -- the same principle as in 3D.

# Answer
> 1 votes
You can use RLE. But you can use SVO (Sparse Voxel Octree), id Tech 6 uses SVO. A SVO is a 3D computer graphics rendering technique using a raycasting or sometimes a ray tracing approach into an octree data representation.

The technique varies somewhat, but generally relies on generating and processing the hull of points (sparse voxels) which are visible or may be visible, given the resolution and size of the screen.

Use raycasting, because it's more fast.

# Answer
> 0 votes
Generally you can avoid a 3D data-structure for terrain. You can use a heightmap instead. This can be very cheaply and efficiently voxelised at runtime. It usually pays (in my experience) to track the minimum height you need to render in each column and also sometimes start-stop-top angles so you can cull backface columns too.

Here's one I made a long time back: http://sites.google.com/site/williamedwardscoder/spinning-voxels-in-flash

If you terrain has a small number of overhangs or caves or other features that cannot be represented by a heightmap, then you can have holes in your heightmap and have an alternative representation e.g. true 3D voxel objects that fill just those localised places where the runtime expense is warranted.

Sparse voxel representations are worth it when you have large true voxel worlds. John Carmack has been talking them up for the past few years now...

---
Tags: data-structure, terrain, voxels
---


title: Collision Detection Unresponsiveness

text:
# Question
Title: Collision Detection Unresponsiveness
I'm creating a simple jumper game in Libgdx that makes the player jump over obstacles in order to stay alive.

The only problem is that the collision detection for when the player just touches the ground, it:

1) Looks a little bit like there's a hitch in the repainting (because it tends to go a y axis little too far before being brought back to above 0).

2) Can't jump right away again (a very small, but annoying delay).

Here is the code that checks for collisions:

```
public void update(float dt) {
    if (location.y < screenBounds.y) {
        location.add(MOVEMENT * dt, 0, 0);
        velocity.y = 0;
        location.y = 0 + dt;
    } else {
        velocity.add(0, GRAVITY, 0);
        velocity.scl(dt);
        location.add(MOVEMENT * dt, velocity.y, 0);
        velocity.scl(1 / dt);
    }

}

```

I know why, it does this though:

```
LOCATION BEFORE RESETTING -0.45871875
LOCATION AFTER RESETTING 0.017244088

```

It takes too long to realize that the location on the y axis is below 0. This creates a hitch as well as a small delay between the times where it lets the player jump again.

I don't know how to fix this problem. I've looked at many posts that discuss collision detection, but none address the same problem I'm having.

For example, these tell me to do what I'm currently doing:

Collision detection Collision detection in libgdx

But they both don't solve my issue.

Any help would be greatly appreciated.

# Answer
I assume that you are calling `update()` once every frame, before you draw the frame.

Your problem is that you are doing either the collision correction or the movement every frame. You need to do both. What's happening is:

1. Your character checks if it is below the screen bounds, it isn't
2. So it moves below the screen bounds, draws for one frame below the screen bounds
3. Then, on the next frame checks again if it is below the screen bounds, it is, so it corrects itself

Try this

```
public void update(float dt) {
    //Let the player intially move wherever they want
    velocity.add(0, GRAVITY, 0);
    velocity.scl(dt);
    location.add(MOVEMENT * dt, velocity.y, 0);
    velocity.scl(1 / dt);

    //If they ended up below the screen, move them up and cancel out gravity
    if (location.y < screenBounds.y) {
        velocity.y = 0;
        location.y = screenBounds.y;
    }
}

```

Also, you probably don't need the `scl()` calls. Instead, just multiply the y velocity by `dt`

```
location.add(MOVEMENT * dt, velocity.y * dt, 0);

```
> 1 votes

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