# Question
Title: Is it normal for a game to use 100% CPU?
I just implemented multi-threaded input handling in my game engine where the code that polls the OS to gather input from it and time stamps them is in a separate thread and each frame in the main thread I just eat up the gathered input up to a logical game time. It all works, but this set up is using 100% of my CPU. I have two cores, and its going up to 100% while running my game.

I have checked with other games to see if they do that too. For example Skyrim and Doom 3 seem to be fine with just over 60% CPU.

Is it acceptable for a game that uses multi-threaded input to use up 100% CPU? If not, what are some tricks such games use to lower cpu usage by the input thread?

# Answer
> 42 votes
Yes, this is normal for a real-time game **to try** to use 100% CPU to perform as fast and good as it can. So that player sees as much frames per second or as good physics simulation or anything else as his PC can provide.

In your case - No, this looks like an inefficient design, to take a thread and make it poll for events in a loop (`while true do CheckForEvents;`). Correct me if I'm wrong, but OS already polls the events. You should just check them from your main thread once every tick.

The main game loop should be fast enough to run at 30+ ticks per second, which is quite enough for polling commands for many games. Player wont see a difference if his commands get processed e.g. 0-33ms later. On the other hand you could have used that extra CPU core for more beneficial tasks, like MUCH better AI or physics or whatever.

P.S. As requested to clarify in comments, do not take above numbers blindly for all kinds of games. While TBS game could need just 1 tick per turn and RTS game could be fine with 10 ticks a turn, other genres, like RaceSims need much more. And of course do not tie logic ticks with framerate, these are two separate things.

# Answer
> 9 votes
A game with a constant active window refresh will mostly be ran in full-screen mode and be the only (big) program of the machine managed by the OS. So it is totally acceptable to use 100% of CPU, because nothing else should need it.

**However**, that doesn't means of course you have to always use 100% whatever your game state. Most game loops use a *sleep* method as a framerate delimiter if they finished to render a frame before the frame-rate limit, in order to not make the CPU used for nothing.
This is probably what happen in your examples: your machine is faster than Skyrim or Doom 3 need to run, so they only use what they need - but all of what they need.

As @KromSterm said, OS usually already poll events for you, so there is no need to make a loop faster than the OS one. If you have only two cores, to use 100% of the second one only for events detection is not a good idea, because if you only transfer events to the main update loop, it is very fast to execute. You should try to use this core for a part of the main thread job with another thread instead.

# Answer
> 9 votes
There are a few drawbacks of aiming to use all available CPU time in a PC or mobile game.

**System requirements:** Even if a game is playable on the PC where you develop your game, it might not be playable on a weaker PC owned by someone who bought your game. Limiting CPU use will keep a game usable on machines that more people are likely to already have. If you really want to see whether you're limiting your market, test your PC games and those of your competitors on a low-end laptop with a Pentium Silver CPU, or test your mobile games on an inexpensive prepaid Android phone.

**Power use:** A laptop computer drains its battery faster when four cores are used at 100 percent of full frequency than when, say, two cores are used at 60 percent of half frequency. So make sure your controller polling thread, AI thread, physics thread, and graphics thread are blocked until it's time for them to run again. Except in a few very twitchy genres, such as fighting and rhythm, you won't need to poll the controllers faster than about 60 Hz, so set your polling thread to run on a 60 Hz timer.

**Physics variability:** If physics that affect gameplay are more detailed on stronger machines, the same player action will have different outcomes on different machines. This means the player may be able to cheat by using a stronger or weaker machine. Id's *Quake III Arena* is notorious for having frame rate affect jump height (as described in "UpsetChaps Quake3 Guide - Why Your Framerate Affects Jumping"). To avoid this, a lot of games use a fixed time step for physics. But this doesn't affect physics that are disconnected from gameplay, such as particle effects or cloth effects or interpolation of coordinates between physics frames to render video at a higher frame rate than physics. So design your physics using some variant of model-view-controller architecture, where essential things (acceleration, hit detection, and the like) go in the model and adjustable eye candy goes in the view.

**AI variability:** If the AI is more detailed on stronger machines, enemies will behave differently on different machines. For example, in a Go or Chess implementation, the opponent will be weaker on a weaker PC, and players can cheat by playing the game on a weaker PC or by running background processes such as antivirus or video transcoding or operating system updates.

---
Tags: c++, performance, input, multithreading, cpu
---


# Question
Title: load all files out of folder as resources in lua and love2d
If i use this code

```
-- some lua file
-- some code
local IMAGE_FILES = {"file1";"file2";"file3";"file4}
-- some code
function loadRes()
    -- some code
    -- load all images:
    for i,v in ipairs(IMAGE_FILES) do
        img[v] = love.graphics.newImage("data/img/"..v..".png")
    end
    -- some code
end

```

i have 2 problems!

1. If i have/want to rename a file, i have to rename it in the IMAGE\_FILES table,too. (If i forget to rename it in one place, either in the .lua-file or in the folder, i run into problems)
2. If i need/want to add another file into the folder, i have to add its name to the variable,too.

For this reasons i want to load data(for example images, music, etc) out of a folder without having to let lua/love2d know the file names beforehand. In other words, is there a way to say to lua/love2d: load all files contained in this "data/img/" folder.

Secondly: Can you get the file type(file ending, like .png) with the solution for my first question?

I'm relatively new to lua and love2d, so i'd really appreciate any help. =)

# Answer
> 1 votes
Just in case someone has a similar problem as i had:

First locate the directory in which you want to go (using windows, don't forget to escape the backslash signs). e.g.(windows) `dir = ".\\data\\img\\"`

Then read and save the filenames in a table (for this you can look at the link from Alexandre Vaillancourt in the question comment section or here:)

```
local i = 1
love.graphics.setBackgroundColor(255,255,255)
p = io.popen('dir "'..dir..'" /b')  --Open directory look for files, save data in p. (with option "/b" everything contained in the given directory is listed with simple format)
for file in p:lines() do                    --Loop through all files
    data[i] = tostring(file)
    i = i + 1
end

```

Last but not least, load whatever you want with the strings that are now contained in the data table. Attention: if you want to load images make sure that either the directory only contains images or don't forget to sort out strings that don't contain image data names (folder names, music data names etc). After you have eliminated possible mistakes you can use the string at position x to create an image out of it. For example like this:

```
img[x] = love.graphics.newImage(data[x])

```

---
Tags: lua, love2d
---


title: Game Slowed by Particles in XNA

text:
# Question
Title: Game Slowed by Particles in XNA
I am developing an XNA game and am trying to improve the performance of the game by hiding objects that are not visible to the user.

My first thought was to use a `BoundingFrustum` based on the camera's view and projection matrices, and then only draw objects whose `BoundingBox` collides or is inside the frustum. However, trying to do this gave me very unpredictable results, with objects disappearing before going out of view and sometimes not showing at all at certain camera angles.

Has anyone else implemented a successful solution to improve their game's performance?

# Answer
> 0 votes
I have developed a multi-faceted solution to my performance problem.

1. I have reduced the lifetimes of particles so they disappear more quickly.
2. I have reduced the number of emitters by almost 25%.
3. I have implemented some code to decide whether to draw the particle:

```
if (distance > 600) { continue; }
if (distance > 300 && distance < 600) {
  if (Math.Round(distance) == Math.Truncate(distance)) { continue; }
}

```
4. Not particle related, but I prevented smaller objects, like fighters, from being drawn since they are obscured by HUD icons. These models usually have ~20k polys with a 2048x2048 texture.

This prevents all particles further than 600 units from the camera being drawn (since they are too small to be seen), and randomly reduces the number of particles between 300 and 600 being drawn (since additional particles at that distance adds no detail).

This has greatly increased the frame rate and makes the game very smooth even in large battles. Number two was by far the biggest improvement.

# Answer
> 0 votes
You can use billboarding technique for particles.

~~Also you can check my old ugly test project. It somehow works and contains particle shader.~~

**UPDATE**

This system was real ugly and slow so I rewrite it:

1. Particle is simple object that has positions, velocity scale and lifetime.
2. Particle emitter is object that has link to particle manager, bounds and emit function.
3. Particle manager is object that keep list of particles and dictionary of emitters.

All particles drawing in one draw call and using special shader.

1. I create special vertex with fields Position, TexCoord and Index.
2. I create mesh with 50 rectangles from (-0.5,-0.5,0) to (-0.5,-0.5,0) using this special vertex class and each 6 vertices (each rectangle) have same index. This mesh never recreated and used for rendering of all particles.
3. To shader I pass rotation transform based on camera rotation and array of 50 transforms. Rotation transform turn all rectangles to face to the camera.
4. Each vertex has index. In vertex shader position should be multiplied on rotation transform and it own transform from passed transforms array.

So, to draw all particles I use same mesh but in cicle pass each next 50 transforms until all particles was drawn. Each frame recalculates only rotation matrix once for all particles and transform matrix for eache perticle.

Also composing all particle textures in one will texture increase performance.

So, I tested it with simple one pixel texture and have 60 FPS with 10K and about 20 FPS with 30K particles in my voxel game on my Lenovo G555 (2.2 GHz; Radeon HD 4550).

---
Tags: c#, xna, monogame
---


# Question
Title: Keep track of VoxelData/NPC in parallel Level
## Background

I'm tring to make a First-Person-Shooter Game in a Voxel-World (Finit Size) with Unity3d.

The Player has some kind of a Base that he has to protect against Enemy units. There are also one or more enemy Bases that the Player has to destroy, but in a different Level/Map.

The Game has multiple Levels that are connected through predefined Ports. So the Player and other Units can travel from Level to Level. There are a couple of Levels to explore. (Maybe there could be infinit Levels in the future.)

At game start I create a LevelManager and all Levels as Children of them. They can spawn an manage the Units and Voxel-Blocks independently. One ChunkManager renders always the current Level where the Player is in. He creates multiple Chunks which itself generate the Mesh from the current Voxel-Data of the Level. This works all very well and I'm also able to travel between the Levels. (This runs all in one Scene.)

At the moment I try to implement some kind of a Worm unit. They spawn from time to time anywhere in each level and can move randomly around and modify the Voxel-World by eating the Blocks away... type of random enviroment event.

## Problem

The problem I can't solve is how to simulate all the Worms in parallel Levels? And the Blocks they have eaten? Same problem would occur for the enemy bases if they grow and build new defences and so on. Because when the Player enter a Level there should be some differences since his last visit.

## My attempt

All my Units and Buildings have already separated logic and rendering components. So they can work properly even when not rendered by the ChunkManager. Its working for maybe 3 Levels and a handfull of worms but if I increase the amount of Levels it gets starting to go laggy (4-10FPS). So this would not be the right way to go or is it and my code is crap?

Has someone any suggestions for me how I can solve this?

## Edit

I disable now all none active Levels and reactivate always the current Level where the Player is in. So I can better manage the objects that realy need computation time.

The problem I get now is how can I simulate the progress in a Level since start? Example for the worm unit. He would have moved across the Level and left a path of removed voxels. Should I made a seperate method to calculate the path that would be made or the last X minutes or should I just call the Update method multipletimes to match the missed calls since last X minutes? This should then be made by all Objects that can modify the Level or produce something.

# Answer
> 1 votes
**Option 1** Decrease the size / number / complexity of the levels

**Option 2** Use WorkerThreads.

**Option 3** Process more distant levels less frequently. Maybe this frequency relies on how close the player currently is to that level... so the current level might be affected every update, a neighbouring level might only be affected once in 2 updates, more distant ones every 4-8 updates (just example numbers). And beyond a certain distance or where there are no enemy bases, don't do anything.

For things like enemy base building, maybe this also means you don't only add 1 voxel every n updates, but maybe you add n voxels every nth update: you're still likely to speed things up this way because at that point in time you're doing all your ops on that level, getting it done with, and moving on with other things (resulting in better cache coherence, for one). Or maybe you build one whole wall at once. Whatever seems efficient to do in one go, every nth update. What you can manage in this regard depends on what your bottleneck is, e.g. if it still takes 8 times longer to add 8 voxels rather than 1, then you'd better stick with adding fewer voxels per update, regardless.

**Option 4** Look for obvious bottlenecks in existing code; specifically look at costs surrounding modification of voxels. Don't do so for very long as it isn't worth doing heavy optimisation early on.

**As regards worms** If their bodies stream between levels, you'll have to make a special case for them. Work only on voxels that may be affected by the worm e.g. using a bounding box, or divide your levels into smaller parts and only operate on parts around the worm, each update.

---
Tags: unity, performance, procedural-generation, voxels, npc
---


# Question
Title: Horizontal lines between vertices do not render
Good day,

I am using LibGDX to try to render a mesh for a hexagon board. I can render the triangles, which is great, but I am having an issue rendering all of the line segments for the mesh and I can't figure out why.

---

## Pictures

Here is an image of what it renders with the primitive type set to GL\_TRIANGLES. The colours are just to help me troubleshoot/identify which triangles are where. .

Here is an image of what it renders with the primitive type set to GL\_LINES. Whether there is 1 triangle being rendered or 1 million, the horizontal lines do not get rendered. .

---

## Code

How I create the mesh:

```
mesh = new Mesh(true, MAX_VERTS, 0,
                new VertexAttribute(Usage.Position, POSITION_COMPONENTS, "a_position"),
                new VertexAttribute(Usage.ColorUnpacked, COLOR_COMPONENTS, "a_color"));

mesh.setVertices(verts);

renderable = new Renderable();
renderable.mesh = mesh;
renderable.primitiveType = GL20.GL_TRIANGLES;
renderable.meshPartSize = mesh.getNumVertices();
renderable.meshPartOffset = 0;

```

When I switch the renderable.primitiveType to GL20.GL\_LINES I get the 2nd picture from above.

I've tried to set the renderable.meshPartSize a couple of different ways:

```
renderable.primitiveType = GL20.GL_LINES;

renderable.meshPartSize = mesh.getNumVertices(); // Doesn't work
renderable.meshPartSize = MAX_VERTS * 2;         // Doesn't work

```

Here is how I make a triangle:

```
void drawTriangle(float x, float y, float z, float width, float height, Color color) {
    // Counter-clockwise winding

    // Vertex 1: Top Left
    verts[idx++] = x;
    verts[idx++] = y;
    verts[idx++] = z;
    verts[idx++] = color.r;
    verts[idx++] = color.g;
    verts[idx++] = color.b;
    verts[idx++] = color.a;

    // Vertex 2: Bottom Left
    verts[idx++] = x;
    verts[idx++] = y;
    verts[idx++] = z + height;
    verts[idx++] = color.r;
    verts[idx++] = color.g;
    verts[idx++] = color.b;
    verts[idx++] = color.a;

    // Vertex 3: Top Right
    verts[idx++] = x + width;
    verts[idx++] = y;
    verts[idx++] = z;
    verts[idx++] = color.r;
    verts[idx++] = color.g;
    verts[idx++] = color.b;
    verts[idx++] = color.a;
}

```

Any help would be appreciated.

Thanks.

# Answer
Using GL\_LINE\_STRIP worked for me, you could give that a try if you have not solved this yet.
> 1 votes

---
Tags: java, libgdx, 3d-meshes
---


# Question
Title: Unity GridLayoutGroup children ignoring resizing
Can anyone explain why, in the editor I get:

while, on my Galaxy S6, I get:

My `Panel` UI element (which is the parent) has the `GridLayoutGroup` component, as well as the `ContentSizeFitter`. The child elements have a `LayoutElement` component with a FlexibleWidth/Height of 120 and all anchors are set to stretch in all directions.

The `Canvas` is set to Scale with Screen size, with a reference res of 320x480 and screen mode is to match height.

Regardless of the amount of squares (which is dynamic) the editor perfectly resizes child elements within the parent, but my device makes them tiny. I'm really confused.

There is no setting of sizes or anchors within the script, purely an instantiate and an assignment of parent, like so:

```
    for(int i=0; i < amount; i++)
    {
        GameObject emptyCell = (GameObject)Instantiate(emptyCellObject);
        emptyCell.transform.SetParent(cellHolder);
        emptyCell.GetComponent<RectTransform>().localPosition = new Vector3(0f, 0f, 0f);
        emptyCells.Add(emptyCell);
    }

```

I've also checked all docs related to: http://docs.unity3d.com/Manual/comp-UIAutoLayout.html \- And even UI tutorial movies, as well as some blog posts about the 'new' UI tools, but nothing changes the dimensions on the physical device, and seems to change nothing in the editor as that remains the same.

I'm sure I'm doing something silly, but I've exhausted all avenues and was hoping someone had come across this oddity previously.

# Answer
Figured this out in the end. Was due to the parent object scaling the child elements (based upon screen space I'm assuming), which was counter-productive in this instance. My work around:

```
emptyCell.GetComponent<RectTransform>().localScale = new Vector3(1f, 1f, 1f);

```

...was to manually override the scaling myself and it works lovely on all devices now. Hope this helps someone out in the future :)
> 0 votes

---
Tags: unity, unityscript
---


# Question
Title: Camera follow rotating ball - ortogonal direction
I have a ball, that has been moved via addForce. It colides in the scene with objects, leading to rotation in all axes.

I want a camera to follow this ball but from the side (direction ortogonal to the move vector and UP vector). No matter what I do, I cannot get this working. The closest I get is almost correct, but camera "bumps" during frames.

I have used this in camera script to attach camera to the ball and move it with it:

```
this.transform.LookAt(this.cannonBall.transform.position, Vector3.up);

this.transform.position = ball.transform.position;

```

No I need to rotate camera 90 degree aroun up axis and move it a little backward to track ball from the side.

How can I achive this? If I use

```
this.transform.Rotate(Vector3.up, 90, Space.World);

```

It mess up lookAt

# Answer
Try something like:

```
public GameObject ball;
public float distanceBack = 6;

private void LateUpdate() {
    //Manually change to the starting angle you want here:
    transform.rotation = Quaternion.identity;

    transform.position = ball.transform.position - transform.TransformDirection(Vector3.back * distanceBack);
    transform.LookAt(ball.transform);
}

```
> 1 votes

# Answer
You can add this script to the camera, and plug in the ball as the target to be followed. Then just set your offsets.

FYI, I wrote this script in Unity 4.x, so it will ask you if it's all good, so just say yes and it will auto-update.

```
using UnityEngine;
using System.Collections;

public class TargetFollower : MonoBehaviour
{

    [Tooltip("Target to be followed")]
    public Transform Target;
    [Tooltip("Mimic the Target's changes in x coordinate")]
    public bool FollowTargetX = true;
    [Tooltip("Mimic the Target's changes in y coordinate")]
    public bool FollowTargetY = true;
    [Tooltip("Mimic the Target's changes in z coordinate")]
    public bool FollowTargetZ = true;

    // Update is called once per frame
    void FixedUpdate()
    {
        if (Target)
        {
            Vector3 targetMovement = GetTargetMovement();
            UpdatePosition(targetMovement);
        }
    }

    private Vector3 oldTargetPosition;
    private Vector3 GetTargetMovement()
    {
        if (oldTargetPosition == Vector3.zero)
        {
            oldTargetPosition = Target.transform.position;
        }
        Vector3 newTargetPosition = Target.transform.position;
        Vector3 targetMovement = newTargetPosition - oldTargetPosition;
        oldTargetPosition = new Vector3(newTargetPosition.x, newTargetPosition.y, newTargetPosition.z);
        return targetMovement;
    }

    private void UpdatePosition(Vector3 targetMovement)
    {
        float xPosition = transform.position.x;
        float yPosition = transform.position.y;
        float zPosition = transform.position.z;
        if (FollowTargetX)
        {
            xPosition += targetMovement.x;
        }
        if (FollowTargetY)
        {
            yPosition += targetMovement.y;
        }
        if (FollowTargetZ)
        {
            zPosition += targetMovement.z;
        }
        Vector3 updatedPosition = new Vector3(xPosition, yPosition, zPosition);
        transform.position = updatedPosition;
    }
}

```
> 2 votes

---
Tags: unity, camera
---


# Question
Title: How to work out given two coordinates should I use a vertical/horizontal/diagonal line to connect them
I'm developing an android game and have essentially a grid. The user can drag a line between two points however the line will only ever be vertical, horizontal or diagonal (y=x). So I need to work out given two points which type of line is the best match.

# Answer
Using vector calculations, you can calculate the angle between the two points, relative to an axis and then based on that angle, choose on how to draw the line.

If you have 2 vectors A and B, you subtract A from B, to get the vector that lies inbetween. You then normalize the result and compare it with a given axis, e.g. y-axis = (0,1). To get the angle between those two, you can use the acos of the dot product of both vectors.

The resulting formula would then be, for an input vector A and B, and the axis C:

```
angle = acos(dot(normalize(B - A), C))

```

If you are not familiar with vectors, these are the step-by-step calculations:

```
AB = B - A = (B.x - A.x | B.y - A.y)

#divide AB by its length, to get a vector of length 1
ABn = normalize(AB) = AB / square root of(AB.x² + AB.y²)
d = dot(ABn, C) = ABn.x * C.x + ABn.y * C.y
angle = acos(d)

```

The angle will always be between 0° and 180°, no matter on which side of the compared axis it lies. If you compared your vector with the y-axis, you can simply check if

* angle \< 30°? -\> vertical
* angle \< 60°? -\> diagonal
* angle \< 120°? -\> horizontal
* angle \< 150°? -\> diagonal
* otherwise (between 150-180°) -\> vertical
> 2 votes

# Answer
I'm not sure I understood your question, but from what I got, you want the best representation for such line. A simple line containing both points would be the best.

If you want to test if something is inside the line, you want something similar:

Think of it in terms of a line that passes between the two.

It will have a initial point (your first point) and a direction. This direction, once multiplied by a given scalar t, will give you your p1.

Any other point you want to test will be given by that t. If you can't find a valid t, it's not in the line.

If t is negative, then you got something that lies on the infinite line, but not on the p0-p1 segment. If you got a t value bigger than the t that gives you your p1, than such point also lies out of the p0-p1 segment.

Hope it helps
> 0 votes

---
Tags: mathematics
---


title: Unity set ui image as active onclick

text:
# Question
Title: Unity set ui image as active onclick
I want my button to activate an inactive ui image in the hierarchy through c# called "Responded\_A" when the "Response\_A" button is clicked. I assume this will use setActive in someway, but I'm just starting out and a little lost. I think some guidance here could really set me in motion. Thanks!

# Answer
You can achieve this without any code using the UI

Add a additional slot to your button click event and drag the Image to the slot.

Make sure editor and runtime is set.

Then simply scroll to GameObject.SetActive

Checking the box will enable it when you click. and no check in the box will disable it when clicked
> 4 votes

# Answer
This should do the trick. Add a new script to the button and put this in it. Next you'll want to drag the image into the GameObject field in the inspector. Then assign the Button component of the same object into the appropriate field.

```
using UnityEngine;
using UnityEngine.UI;

public class PushButton : MonoBehaviour {

    // Assign both of these in the editor.
    public GameObject image;
    public Button button;

    void Start() {
        button.onClick.AddListener(() => {
            image.SetActive(true);
        });
    }
}

```
> 2 votes

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


# Question
Title: How far back should I move my camera to fit a given GameObject in frame?
In Unity with C#, I want to calculate the minimum distance that my perspective camera has to be from a given GameObject (a procedurally generated mesh), so that the object is fully framed by the camera and leaving the least space possible around it in the screen. In other words, *fully framed* means that there is no part of the object outside the view area.

To make things easier, my camera does not need to rotate or move - it's fully static, with the exception of one axis to zoom in or out in order to frame the target object. So, in fact, we could summarize my problem as a zoom problem (not using FOV to zoom) where I need to frame a procedurally generated mesh whose size varies considerably.

Would anyone be kind enough to point me in the right direction with code snippets, suggestions, etc?

# Answer
(Side note: In camera talk, "zoom" means to adjust the zoom lens which is the field of view. "Dolly" means to glide forward and back. Or just say "move along some axis".)

Here's a general approach, without the math:

When you know the field of view angle, which may be different for horizontal and vertical of your screen, you can solve the view distance for each vertex of your mesh: "what camera position puts it at exactly an edge of the screen". Solve for each of the mesh vertexes, and choose the furthest-back camera position. Did!
> 1 votes

# Answer
You could calculate the camera's position using the signed distances between the camera's frustum planes and the mesh's bounding volume. That's the approach I'm using.
> 0 votes

---
Tags: camera, procedural-generation, screen, mesh, viewport
---


# Question
Title: need a pathfinding algorithm from 1 column to another
grid contains weights and I need a max path sum from one column to another possible movement directions are (right, up & down only).

Can Djikstra or A\* help ??

# Answer
# What is a graph?

> A graph consists of 3 things.
>
> 1. **objects** called *"vertices"* (singular *"vertex"*),
> 2. **connections between the objects** called *"edges"*, which are ordered pairs of the form `(a,b)` this means that "a is connected to b", it does not mean that b is connected to a.\*
> 3. **weights** or **worths** assigned to the edges. This is done by a function, `w: connections -> numbers` with `w(x,y)` being the weight of the edge from `x` to `y`

---

# Dijikstra and A\*

These algorithms take a graph **and the assumption that `w(x,y)>=0` for all `x` and `y`** and return a shortest path (between some or all vertices of the graph)`+`

They will work provided you can satisfy the definitions above.

---

# Footnotes:

`*` \- so called "undirected" graphs are graphs where if the edge `(a,b)` exists then so does `(b,a)` and they require that `w(a,b)=w(b,a)`

`+` \- suppose that your weight is "time taken" and you have a portal that'll take you back in time to a location `p`, the "weight" of going to `p` might be the weight to the portal `-` the time difference. Suppose you can go from `p` back to the portal before you even leave through the portal. This is called a `negtive weight cycle` and totally buggers up the algorithm (see `Floyd's algorithm`) - even if it isn't a negative weight cycle it causes severe problems.
> 1 votes

# Answer
Of course.

Dijkstra's (of which A\* is just a refinement) adds nodes to an open list. The usual grid implementation is to consider all adjacent nodes. You can simply change this to only consider nodes on the same column or the column to the right.

For termination, the usual algorithm is looking for a specific node or position. You can also change the algorithm to terminate on a specific set of nodes ie. a specific column.

Ultimately, this is no different than games that filter out nodes for different types of units (e.g. airborne vs terrestrial vs aquatic units pathing over a map in an RTS) or games that search for points near a target location (e.g. to get within 10 meters of a point a user clicked, rather than the exact node the user clicked).
> 0 votes

---
Tags: path-finding, grid
---


# Question
Title: Accessing a C++-based optimization library in FlashPunk
Some time ago I launched my FlashPunk primer, an adaption of *Asteroids*, which mainly served as a basis for trying out a simple optimization algorithm.

Now I'm planning to take this concept a level further and program a version of *Lunar Lander*. This would require to incorporate a sophisticated external C++-based numerical optimization library into my Flash Punk code.

When looking for a solution I came across the Crossbridge compiler. If I got it correctly, it would allow for writing native C++, accessing flash functions via the AS3 header and have it compiled to a \*.swf-file.

Would that mean I have to give up FlashPunk and write the whole piece in C++/AS3?

# Answer
I call this the "Hello-world gulf" - the HUGE gap between "hello world" and what are basically samples and actual code.

In Python creating an auxiliary library in C++ that does the computationally intensive things is absolutely brilliant. The ability to link languages like this is also something you should consider when choosing what language to do stuff in, so great work there.

**However this doesn't apply to flash** \- you should basically drop Flash.

The best technologies here are "open" and I don't mean this in the hippy-ish sense (although I really do fall under that banner....). Look at PDFs, these are great, look at Adobe's ability to do PDFs - it's crap. But they have specific extensions (things you can only do in Adobe's reader) that "locks you in". Flash is a bit like that in the sense it is a closed aboimination (there are open source *implementations* but whether or not they'd work with your library, or your mentioned compiler is another issue)

I know of no "serious" game (that is made by someone who's aware of what MinGW is) that is compiled using Microsoft's C++ compiler for example. This is often because open stuff either plays nice with other things, or can be made to play nice with other things. Before someone dismisses this as off topic, please read the next paragraph.

I hate Javascript, I think it's gotten way too much attention, but it's an example of "things playing nice". There's a project called "asm.js" which is a collection of all the parts of javascript that are easy to optimise. There's a back end for LLVM (a compiler, that's open) that emits "asm.js", there are many front ends for LLVM (like CLang) that allow it to compile say C++.

So now you get to write stuff in C++, have it compiled by the second best compiler on the planet (GCC is in first place. RTL is a lot more advanced, story for another time though) to this "asm.js" then have the browser (Firefox, Chrome will also) compile this really easy to compile chunk of javascript to native code. The result is NEAR native speeds of stuff you wrote in FORTRAN, C, C++.... any front end you like for LLVM (you could even make your own)

If it's the browser based bit you like, this is the way to go.

---

## The Hello-World gulf

Many years ago I started with this thing called "DarkBasic" - it held me back years by:

1. Not working like any engine should (so I had this warped idea of APIs engines should present to users)
2. Selling dreams and false-hope (buy this ad-on for AI! Because implementing such stuff in it was not feasible, this was simple money-making from "dreams" as I said)
3. Letting you make "samples" quickly but being the most awful thing ever for "actual software" (this is the "hello-world gulf")

You're at the point now where you're looking to cross it (from the sounds of it) and this is the toughest part of "growing up" programmer wise. I see this post as a nudge in the right direction because with game design especially there are HUGE markets for false hope.

---

## How to cross the gulf

With systems programming I say "do actual projects" like things that let you put in data and analyse it with graphs and such, this shows you user input validation and the importance of planning ahead and over time you'll learn.

I've always said: "one cannot be taught how to model object orientated things" unlike the Matrix (which you can explain without showing) you actually do need to see it to understand it. After a while everything will just "click" and finally those diagrams will be something you actually want.

The same largely goes for games, only they're more complicated. Once you can plan ahead you'll see the huge **massive** gaping chasms that crap like DarkBasic doesn't show you and be like "I shouldn't use that for the job, because of this"

I think you should go for Python/C++ and OpenGL, or even wxPython/wxWidgets and drawing your lander on a DeviceContext as an image or whatever. IF you get stuck with things like "understanding shaders" - that is the kind of question I am here to answer. Understanding why/how things work make them easy to use OR go Javascript of browser-based is important to you.

I know this seems like a rant but I am totally serious, from the sounds of it you're teetering at the edge you now need to cross into the "real" world.
> -1 votes

---
Tags: c++, flash, flascc
---


# Question
Title: In a tile-based MMO, how do I decide which players need to receive what updates?
I am planning a tile based MMO, like *Tibia* or top down *Minecraft*. I'm using a client-server model. I've got almost everything figured out, with a notable exception of *state updates*.

When information about a tile changes (e.g. new item is added) all clients that see this tile need to be informed about it. How do I efficiently decide which clients needs to receive this update? I'd like to support on the order of 100 000s of tiles and 100s of players.

# Answer
> 5 votes
Divide your game world into rectangular chunks which are about half the size of the players screen. Keep track of which players are in which chunk. You can easily do that in the code which handles player movement.

When a tile changes, inform only those players which are in this or in an adjacent chunk.

When a player moves to a new chunk, give them an update of the complete state of the newly adjacent chunks.

---
Tags: 2d, networking, tiles, mmo
---


title: Overlay Image on Mesh Unity

text:
# Question
Title: Overlay Image on Mesh Unity
I have a whiteboard object that I would like to put images/pdfs/powerpoints on. I am not sure how to overlay an image on a white shader. I looked at this post:

Loading .PNG file and using it for UnityEngine.UI.Image

But I am not sure where to put the UI.Image. If I create a mesh from the image won't it cover up my entire whiteboard?

# Answer
> 1 votes
To reply to your comment:

First of all you are going to have to make your image into a prefab. This can be easily done by dragging the image file from the assets folder onto the scene view, then drag the newly made object back into the assets folder. (Delete the object in the scene if you want)

Now in order for the prefab to be able to accessed, you will have to create a new folder in your assets folder called "Resources". Put the GameObject prefab into this folder.

After that is done this code should do the trick:

```
private GameObject image;

public void Start() {
    image = (GameObject)Resources.Load("Image1");
    AddImage();
}

public void AddImage() {
    Vector3 spawnPosition = new Vector3(0, 2, 0);
    Quaternion spawnAngle = Quaternion.Euler(0, 0, 0);
    Instantiate(image, spawnPosition, spawnAngle);
}

```

---
Tags: image, unity, overlay
---


# Question
Title: Cocos framework gives large Android builds than cocos2d-x
This question is regarding Project Architecture and workflow. I have an installation of cocos2d-x and Cocos Studio with Cocos Framework ( version 3.6). I carried out different build tests with hello world ( only 1 sprite in a scene) as follows:

* Cocos Framework Android Build \[ release \] : 9.2 mb
* Cocos2d-x Android Build \[ release \] : 2.06 mb
* cocos Framework Game Source Directory : 379 MB
* Cocosd2d-x Game Source Directory : 600+ Mb

After a debug version of windows build

* Cocosd2d-x Game Source Directory : 4+ GB

I want to work with the cocos2d-x native workflow but its huge source is actually a problem for Github / bitbucket hostings and/or project migrations. So the questions are:

1. **Why is there a huge difference in the android builds by using pre-compiled header?**
2. **How can I have Lowest Android builds with precompiled headers (cocos Studio / Framework )?**

# Answer
okay, its been a while since anyone answered the question and finally i figured it out myself.

1. The pre-compiled headers does not require the user to build all the engine source code from scratch ( and this is the reason you see only one project in visual studio whereas when using source version, you see atleast projects in the solution explorer because they should be built too). Hence, they are already packed as dlls and does not occupy memory for db files and other build files. Hence the huge difference between their sizes.

2. It turns out, the user should not be dependent on pre-compiled headers for production ready APKs. the workflow is actually quite simple : Make the whole game with pre-compiled headers ( this saves hell lot of time in development + builds). Once you are fully satisfied with the game and it is ready to be shipped / published, just create an new project with the source, copy the source files, update the make list, build. That's how the overall workflow should be maintained.
> 0 votes

---
Tags: android, cocos2d, cocos2d-x
---


# Question
Title: Has google increased apk limit from 50mb to 149?
I recently seen Angry Birds GO has apk size of 149 on google play, https://play.google.com/store/apps/details?id=com.rovio.angrybirdsgo&hl=en

Yet google says apk size limit is 50 mb.So my question is,has google increased apk size limit from 50 mb?

# Answer
> 2 votes
No, it hasn't.

According to the development docs:

> Google Play currently requires that your APK file be no more than 50MB

However, the same page mentions that you can have up to 4GB if you use expansion packs:

> You can provide up to 4GB of additional data for each APK

This is probably what Angry Birds GO uses.

---
Tags: google-play
---


# Question
Title: How can I adjust steer angle based on speed in Unity?
I'm following this (https://www.youtube.com/watch?v=kAEpLX3rfms) video on how to make a car in Unity. But my car doesn't lower the steering angle based on the speed of the video. The idea was that you can steer the car at a max of 50 degrees at the slowest and then 10 degrees at the fastest. But it's having no effect on the car. Could someone show me how to fix this?

Code:

```
public WheelCollider wheelFL;
public WheelCollider wheelFR;
public WheelCollider wheelRL;
public WheelCollider wheelRR;

public Transform wheelFL_Trans;
public Transform wheelFR_Trans;
public Transform wheelRL_Trans;
public Transform wheelRR_Trans;

public float maxSpeed;
public float lowSpeedSteerAngle;
public float highSpeedSteerAngle;
public float Torque;
public float centerOfMassHeight;

private float currentSteerAngle;
private Vector3 com;
private Rigidbody rigidBody;

void Start () {
    rigidBody = GetComponent<Rigidbody>();
    com = rigidBody.centerOfMass;
    com.y = centerOfMassHeight;
    rigidBody.centerOfMass = com;
}

void FixedUpdate () {
    wheelRL.motorTorque = Torque * Input.GetAxis("Vertical");
    wheelRR.motorTorque = Torque * Input.GetAxis("Vertical");

    //Here is the part with the issues

    float speedFactor = GetComponent<Rigidbody>().velocity.magnitude / maxSpeed;
    currentSteerAngle = Mathf.Lerp(highSpeedSteerAngle, lowSpeedSteerAngle, speedFactor) * Input.GetAxis("Horizontal");
    wheelFL.steerAngle = currentSteerAngle;
    wheelFR.steerAngle = currentSteerAngle;
}

void Update () {
    wheelFL_Trans.Rotate(0, 0, wheelFL.rpm / 60 * 360 * Time.deltaTime);
    wheelFR_Trans.Rotate(0, 0, wheelFR.rpm / 60 * 360 * Time.deltaTime);
    wheelRL_Trans.Rotate(0, 0, wheelRL.rpm / 60 * 360 * Time.deltaTime);
    wheelRR_Trans.Rotate(0, 0, wheelRR.rpm / 60 * 360 * Time.deltaTime);

    Vector3 wheelSteerAngle = wheelFL_Trans.localEulerAngles;
    wheelSteerAngle.y = currentSteerAngle + 90;
    wheelFL_Trans.localEulerAngles = wheelSteerAngle;
    wheelFR_Trans.localEulerAngles = wheelSteerAngle;

    if(Input.GetKeyDown(KeyCode.P)){
        Vector3 resetPosition = new Vector3(transform.position.x, 1.5f, transform.position.z);
        Quaternion resetRotation = Quaternion.Euler(0f, 0f, 0f);

        //Reseting Velocity
        GetComponent<Rigidbody>().velocity = new Vector3(0f, 0f, 0f);

        //Reseting Rotation
        transform.rotation = resetRotation;

        //Reseting Position
        transform.position = resetPosition;

        //Reseting Motor Torque and Steering Angle
        wheelFL.motorTorque = 0f;
        wheelFR.motorTorque = 0f;
        wheelRL.motorTorque = 0f;
        wheelRR.motorTorque = 0f;

        wheelFL.steerAngle = 0f;
        wheelFR.steerAngle = 0f;
        wheelRL.steerAngle = 0f;
        wheelRR.steerAngle = 0f;
    }

}

```

# Answer
Try adapting this code to the area that you marked with the issues. This algorithm should give the amount that you should be able to turn given the speed. You will just have to apply the turnAmount to the car.

```
float maxTurn = 50, minTurn = 10;

float speedFactor = 1 - (GetComponent<Rigidbody>().velocity.magnitude / maxSpeed);
float currentMaxTurnAngle = minTurn + ((maxTurn - minTurn) * speedFactor);
float turnAmount = currentMaxTurnAngle * Input.GetAxis("Horizontal");

```

This should yield 10 at max speed and 50 when not moving.

I suggest increasing the turn values, and then multiplying the turnAmount by Time.deltaTime so that the turning will work more consistently whatever the framerate.
> -1 votes

---
Tags: unity, c#, rotation, car
---


# Question
Title: How to implement visibility graph pathfinding in Unity/C# to detect paths (i.e. visibility connections) efficiently?
I am struggling with implementing continuous path-finding trough visibility graphs. Notice, I know that grids can be used even when movement is not trough grids (e.g. Theta\*). But for my current needs, I really have to implement a real visibility graph path-finding.

First, I understand the logic of such an approach: 1) finding the points that go at each corner around obstacles, 2) calculating which of these points have direct connections to each other, 3) then applying A\*. I am able to do steps 1 and 3 by my own, but I can't find out how to do number 2. It means, how can I find out which points are visible to each other and then transform it into an array to use with A\*, in an efficient manner in terms of computer processing (i.e. avoinding raycast)?

I use Unity and C#, but also favor pseudo-code format. Please, suggestions, tutorials, sources, are all welcome.

# Answer
For the first step, I'd use the bounding box of the obstacle to compute the points as it'll be much easier and computationally less expensive. If you want, here's how I'd do it:

```
//PlayerExtents includes margin for avoidance
Vector2[] GetPointsAroundObstacle(Bounds b) {
    Vector2[] points = new Vector2[4];
    points[0] = new Vector2(b.min.x, b.min.z) - PlayerExtents;
    points[1] = new Vector2(b.min.x - PlayerExtents.x, b.max.z + PlayerExtents.z);
    points[2] = new Vector2(b.max.x, b.max.z) + PlayerExtents;
    points[3] = new Vector2(b.max.x + PlayerExtents.x, b.min.z - PlayerExtents.z);
}

```

But for my method, you can use a convex/concave hull too so long as the points on the grid form a polygon.

If you are getting the points using the bounding box, the function will return 4 points on the grid. From there it is just a simple matter of seeing which vertices are connected directly to which on a square for the second step.

So if the square/polygon formed is as follows:

```
   1        2
    - - - -
    -     -
    -     -
    - - - -
   0        3

```

Where 0, 1, 2, 3, ..., n - 1 are its vertices, then (if I've understood you correctly) simply

```
0 -> 1, 3;
1 -> 0, 2;
2 -> 3, 1;
3 -> 2, 0;

```

This holds true for any n-gon, so you can even use a more complex shape.

Or a simple function for this (I like Python for pseudocode :P) :

```
def connections(i, n):
    c = []
    c.append(i + 1 % n)
    c.append(wrap(i - 1, n))
    return c

```

where `wrap()` is

```
return i - 1 <= -1 ? n : i - 1

```

Now you can build the graph of the points around obstacle and use A\*.
> 0 votes

---
Tags: unity, c#, path-finding, graph, visibility-determination
---


# Question
Title: change position/orientation of a bone using assimp
I have been using assimp to import rigged models and animations. I followed this tutorial for skeletal animation and I have got it done properly. The part that I am trying to do now is to orient a certain mesh by using transformation matrix, which represents change from the initial orientation of bone For example, rotating left hand of the model by a 90 deg angle shall make the hand vertical if it's initially horizontal. To achieve this I have taken the following steps:

1. map each bone with its bone offset matrix, given by pBoneData\[BoneIndex\].BoneOffset below. This BoneOffset matrix transforms from mesh space to bone space.
2. find the parent bone in a mesh i.e. body part,
3. get the matrix for orienting the mesh, and save this matrix for parent bone of that mesh, given by pBoneData\[BoneIndex\].rotTransform. For all the other bones in a mesh, the orientation matrix is identity matrix;
4. traverse the node heirarchy and assign final transformation for each bone as:

```
void rag::BoneTransform(const aiScene* mScene)
{
aiNode* pNode = mScene->mRootNode;
readNode(pNode, IdentityMatrix);
}

//recursive process
void rag::readNode(aiNode* pNode, Matrix4f& ParentTransform)
{
 Matrix4f rot, GlobalTransformation;
 std::string NodeName(pNode->mName.data);
 Matrix4f NodeTransformation(pNode->mTransformation);

 if (boneMapping.find(NodeName) != boneMapping.end())
 {
 //if node represents a bone, then take it`s unique index
 unsigned int BoneIndex = boneMapping[NodeName];
 //rot is the matrix that represents change in orientation of bone
 rot = pBoneData[BoneIndex].rotTransform;
 GlobalTransformation = ParentTransform * NodeTransformation;
 pBoneData[BoneIndex].FinalTransformation = GlobalInverseTransform * GlobalTransformation * pBoneData[BoneIndex].BoneOffset;
 }

 GlobalTransformation = ParentTransform * NodeTransformation;

for (unsigned int i = 0 ; i < pNode->mNumChildren ; i++)
readNode(pNode->mChildren[i], GlobalTransformation);

}

```

If the function above is run as it is, it will display the model in the state it was while posing it in Blender, in T pose in my case. I am having problems on using 'rot' Matrix. One of the books that I read suggested multiplying the initialBoneOrientation with the changeMatrix. My initial thoughts was to sum 'rot' with NodeTransformation as both of these represent relative change from their parent Matrices. However, I got a totally disfigured model on doing so. Any thoughts on these is highly welcomed.

# Answer
> 1 votes
The animation data provided by the assimp library is expressed as absolute values, relative to the node/bone's parent; you just set the translation/rotation/scale specified by the animation directly on the node or bone being animated -- don't try to "combine" it with the initial orientation or any other value.

More detail in the assimp library documentation

> To apply such an animation you need to identify the animation tracks that refer to actual bones in your mesh. Then for every track:
>
> 1. Find the keys that lay right before the current anim time.
> 2. Optional: interpolate between these and the following keys.
> 3. Combine the calculated position, rotation and scaling to a tranformation matrix
> 4. Set the affected node's transformation to the calculated matrix.

---
Tags: c++, glsl, matrix, assimp, rigging
---


title: Server/Client architecture

text:
# Question
Title: Server/Client architecture
I have high experience In Java and Networking. Our team have built a effective server that can create thread-pools managing many players. But we have hit a brick-wall. The way our server works is that our clients directly all just connect to the server. The client sends information to the server. For example, Client 004 pressed W. And the server calculates and responds. But here's the problem. What exactly do we send over the data stream? Do we send strings and decode them on the client/server side, or serialize objects? Sadly that question is very opinion based. So let me re-phrase it. What data do we send over the stream? For example, you can use W,A,S,D To move around. Im guessing it should look like this.

User Pressed W \> Client sends string saying w to server \> Server calculates movement \> Server sends string saying player position to player \> User updates players position.

But then we have to render other players. So we thought about this

User MPressed W \> Client sends string saying W to server \> Server calculates movement \> Server checks if any others players are in the area \> Server saves data of all players and yourself into a string and adds positions and sends to client.

Fair enough. But imagine if the server had to send over information, like the other players clothing, their health, mana, position, current animated frame.

The string might look like this:

"Bob, 12, 321, 391.34, 2914.2, Left, 0, False, null, null, sword, null, null"

Just for one player! To be sent over. The string concept is becoming long and tedious.

I have re-wrote this several times. And I still do find it confusing to understand the question myself.

But to shorten it down. How do I create a system where its a mmo really.

We've created the server, client art. We've payed for a large server with ddos protection. But we don't know what to send over the sockets.

# Answer
> 1 votes
What if I want to use the arrow keys? It'd be crap.

You have the clients send updates like "I am at `x` moving at speed `p` and turning at rate `m`"

The server should so some quick bounds checking (to prevent cheating) then pass those updates on ASAP.

---

Clients should *query* what they need, for example "get player list" (as some command) might cause the server to send back a list (in whatever) format of the players AND their positions

The client will then be like `Alec` is closest, followed by `Bob` and be like:

> `>` Describe Alec
> `<` Health: 100, max health 120, clothes.....
> `>` Describe Bob
> `<` (so forth)

Obviously don't send these as strings. State machines and UDP are the way to go.

Like expect 4 bytes to be some sort of "command ID", if the command ID is `13` (`get player list`) then expect 2 bytes (the number of players, unsigned int) then expect 3 floats, a number for the length of the name and that length number of bytes. - do this for each player.

---
Tags: java, networking, mmo, data
---


title: Java2D tinting image

text:
# Question
Title: Java2D tinting image
I wanted to know how to tint a (Buffered)Image in Java

With "tinting" I mean that black pixels stay black and grey/white pixels become the colour I want. Of Course not all pictures are grayscale

I tried to paint the Image with 50% Alpha colour, but the results are not satisfying.

Does someone know a Solution for this? Here you can see what I want:

The bottom right picture is, What I have with 50% alpha colour. the Top Right is, what I want.

A somehow linked question to this: Is painting the image via setRGB() for each pixel faster than BufferedImage.getGraphics() and paint on the Graphics Object?

# Answer
> 1 votes
Thanks to the comment above, I found the answer

```
protected BufferedImage tint(float r, float g, float b, float a,
                            BufferedImage sprite)
  {
    BufferedImage tintedSprite = new BufferedImage(sprite.getWidth(), sprite.
            getHeight(), BufferedImage.TRANSLUCENT);
    Graphics2D graphics = tintedSprite.createGraphics();
    graphics.drawImage(sprite, 0, 0, null);
    graphics.dispose();

    for (int i = 0; i < tintedSprite.getWidth(); i++)
    {
      for (int j = 0; j < tintedSprite.getHeight(); j++)
      {
        int ax = tintedSprite.getColorModel().getAlpha(tintedSprite.getRaster().
                getDataElements(i, j, null));
        int rx = tintedSprite.getColorModel().getRed(tintedSprite.getRaster().
                getDataElements(i, j, null));
        int gx = tintedSprite.getColorModel().getGreen(tintedSprite.getRaster().
                getDataElements(i, j, null));
        int bx = tintedSprite.getColorModel().getBlue(tintedSprite.getRaster().
                getDataElements(i, j, null));
        rx *= r;
        gx *= g;
        bx *= b;
        ax *= a;
        tintedSprite.setRGB(i, j, (ax << 24) | (rx << 16) | (gx << 8) | (bx));
      }
    }
    return tintedSprite;
  }

```

where `r`, `g`, `b` and `a` are floats between 0 and 1

---
Tags: java
---


# Question
Title: Is it a terrible practice to NOT initialize an object in its constructor?
I'm currently working on my own game engine, more precisely on the resources management part.

For now, most of my assets inherits of the following - simplified - class:

```
class   Asset
{
public:
    Asset(const char* file);
    virtual ~Asset();

    virtual void    load() = 0;
    virtual void    unload() = 0;
}

```

As you can guess, the constructor and destructor do almost nothing, while `load` and `unload` functions respectively initialize and delete all asset's data.

I'm doing it because I don't want to load a file each time I create an asset object, but instead do it on a method of my `AssetsManager` that would load everything needed.
But I still want to be able to *prepare* other objects using these unloaded assets. For instance, an unloaded texture can be set on a mesh material. This material just won't be able to be rendered if the texture is not loaded.

The problem is, I heard this is a terrible way to code a class structure, especially from programmers supporting the RAII idiom.

Is it a correct way to handle assets? If not, what would be better for this class?

# Answer
So the other answer is good, but I will say this. In C++ the `RAII` idiom means "you never type `object.close()` or `object.free()` or `object.release()` or anything like that, it is a bit laxer on initialisation because of assignment operators.

Suppose we have the following

```
class Object {
public:
    Object() { /* CANNOT doStuff after this, as it isn't ready*/ }
    Object& operator=(const Object&);
    ~Object() { /*code to tidy up*/ }

    void load(Whatever);
    void doStuff();

private:
    /*implementation*/
};

```

I can now do stuff like:

```
Object o1; //not valid here
Object o2; //careful - you cannot use virtuals in a constructor!
o2.load(stuff); //o2 is now valid
o1=o2; //copy-assign, both valid

```

When this code-block ends both will **automatically** be destructed and clean up.

The important part is that the destructor clears up. This means if you have the following:

```
Asset::~Asset() {
    if(isLoaded()) {
        unload();
    }
}

```

Now your destructor will unload stuff - if it is loaded.

What you need is a way to communicate "you cannot use an asset that hasn't been loaded" without exceptions (as exceptions degrade performance quite severely)

If you use this then structures filled with assets will automatically unload when you destroy them, as it should be!

---

## Exemplary uses of RAII

One of my all time favourite C++ things is:

```
1) code.whatever();
2) {Guard g(resource);
3)     do.this.that(BOTH).with(resource);
4) }
5) more.soForth();

```

`g` will be destroyed "at line 4" (proper scoping) thus automatically releasing the lock on resource it holds.

---

## Game engines don't count

Note also that with game engines we care about performance NOT nice code. We're not systems programmers. A good example of this is when you have a virtual function you might need to call loads of times. It is far faster to have some sort of "type ID" and force a cast to the correct type then jump (without devirtualising) to something than it is to do the virtual call.

This is a total anti-pattern and if I saw a systems programmer doing it I'd probably break their legs. It's okay for us chosen few!

---

## Why you need "invalid" things

Vectors and arrays are cheep. Even if you're going for maximum performance that default constructor running isn't going to be the bottleneck (letting the compiler see it in the header file will help as then it can inline it and wont have to do a full-on function call) and premature optimisation is evil.

Suppose you have a `MyVector<T>` which is actually a `T[]` underneath it all, which you get by doing `data=new T[size]` \- this isn't bad to start with (even though it involves `size` calls to `T::T()`), the biggest problem here will be memory allocation (`new` becomes the enemy) - there is literally no need to optimise this now.

Now when you construct your `T[]` you need to have a default constructor (linked lists can get away without this as they construct new nodes as needed) and this is "classic C++" in the sense of "I know that the array is initialised" and I encourage you to do this even though it is "not as fast". If this is the bottleneck you can of course use malloc and inplace new everything you need. You just have to be very careful, so worry about this later.

> **NOTE ABOUT PITFALLS**
> If you change your `MyVector` implementation from something like:
>
> * `data[size+1] = incoming; //will use T::operator=` To
> * `new(data+size+1) (incoming) //will use T::T`

Which may require some tweaking if one of your `T` has an `operator=` for an obscure class but no constructor. Otherwise nothing will change.

> **OTHER PITFALL**
> This one is often missed, right now you have this magic global `new` \- if that goes you'll require an `Allocator&` to everything that might have to allocate. Keep this in mind. If you do switch to a faster more game-friendly allocator, how will your objects get hold of a reference for it?

---

## Life without exceptions

*In theory* stuff like `thing.use(invalidAsset)` should never happen, and usually when it does you'd have an exception.

**Exceptions are the enemy** in the engine, this is why you may find in other projects nothing seems to return a `T&` only `T*` \- this is because you can test a `T*` for being a `nullptr`. Like with exceptions though, no one seems to bother.

Anyway, you should ask "**how can I make debugging these easier?**" the secret is the pre-processor.

Somewhere you need a config file and in it you shall write:

```
#define MYPROJ_SANITY_CHECK            1
#define MYPROJ_SANITY_CHECK_ASSETS     MYPROJ_SANITY_CHECK

```

and another file where you define this:

```
#define MYPROJ_EXIT(MSG) ::MyProject::exit(MSG,__LINE__,__FILE__);
namespace MyProject {
    exit(const char* message, int line, const char* file);
}

```

and make sure the implementation of exit outputs something on `stderr` and EXITS, not exceptions, insta-crash it! (Great place to set breakpoints!)

Then when you use an `Asset` (this is the hard part) you turn this:

```
use(incomingAsset);

```

into

```
#if MYPROJ_SANITY_CHECK_ASSETS == 1
    if(!incomingAsset->isLoaded()) {
        MYPROJ_EXIT("Not-loaded asset passed, loaded expected")
    }
#endif
use(incomingAsset)

```

This way you still get to do checks (which you want!) but you can turn them all off easily (which you also want!)

---

## Real example

```
template<class T> class DeleteWhenDone;
namespace std {
template<class T>
void swap(DeleteWhenDone<T>&,DeleteWhenDone<T>&) noexcept;
}

template<class T>
class DeleteWhenDone {
public:
    DeleteWhenDone() { data = nullptr; }
    DeleteWhenDone(T* source): data(source) { }
    DeleteWhenDone(const DeleteWhenDone&) = delete;
    DeleteWhenDone(DeleteWhenDone&& from) noexcept: data(from.data) { from.data = nullptr; }
    DeleteWhenDone& operator=(const DeleteWhenDone&) = delete;
    DeleteWhenDone& operator=(DeleteWhenDone&& from) {
        DeleteWhenDone tmp(::std::forward<DeleteWhenDone>(from));
        ::std::swap(*this,tmp);
        return *this;
    }
    ~DeleteWhenDone() { delete data; }
private:
    T* data;

friend void ::std::swap<>(DeleteWhenDone&,DeleteWhenDone&) noexcept;
};
namespace std {

template<class T>
void swap(::DeleteWhenDone<T>& A, ::DeleteWhenDone<T>& B) noexcept {
    T* tmp = A.data;
    A.data = B.data;
    B.data = tmp;
}

}

```

The STL isn't enough for engines. https://stackoverflow.com/a/20290701/2112028 (check out this answer on a fast shared pointer, the STL is a systems programming perspective, it's good, but not for engines) So we write our own. This (missing an `operator->`) class is an example of something that takes whatever it points to with it when it is destroyed. Say you have a vector of these, or an array - when it is destroyed these pointers delete what they point to with it.

Notice the default constructor and the way I implement the move operators, this is very common in systems programming and the compiler will optimise it.

I use this example to illustrate something unexpected. Notice I use `nullptr` as my "not initialised" value. Compiling with `-O3 -fno-exceptions` with the following test program

```
DeleteWhenDone<int> getInt() {
    DeleteWhenDone<int> a(new int(5));
    return a;
}
int main() {
    DeleteWhenDone<int> test;
    test = getInt();
}

```

we get the following code

```
0000000000400670 <main>:
  400670:       53                      push   %rbx
  400671:       bf 04 00 00 00          mov    $0x4,%edi
  400676:       e8 e5 ff ff ff          callq  400660 <operator new(unsigned long)@plt>
  40067b:       31 ff                   xor    %edi,%edi
  40067d:       c7 00 05 00 00 00       movl   $0x5,(%rax)
  400683:       48 89 c3                mov    %rax,%rbx
  400686:       e8 85 ff ff ff          callq  400610 <operator delete(void*)@plt>
  40068b:       31 ff                   xor    %edi,%edi
  40068d:       e8 7e ff ff ff          callq  400610 <operator delete(void*)@plt>
  400692:       48 89 df                mov    %rbx,%rdi
  400695:       e8 76 ff ff ff          callq  400610 <operator delete(void*)@plt>
  40069a:       31 c0                   xor    %eax,%eax
  40069c:       5b                      pop    %rbx
  40069d:       c3                      retq
  40069e:       66 90                   xchg   %ax,%ax

```

3 calls to `delete`!! This is BAD (although to a systems programmer this is great)

Earlier when I put the "checking for loadedness in a destructor" I meant it. If we change the destructor to:

```
    ~DeleteWhenDone() { if(data != nullptr) { delete data; } }

```

We get the following:

```
    0000000000400670 <main>:
      400670:       48 83 ec 08             sub    $0x8,%rsp
      400674:       bf 04 00 00 00          mov    $0x4,%edi
      400679:       e8 e2 ff ff ff          callq  400660 <operator new(unsigned long)@plt>
      40067e:       c7 00 05 00 00 00       movl   $0x5,(%rax)
      400684:       48 89 c7                mov    %rax,%rdi
      400687:       e8 84 ff ff ff          callq  400610 <operator delete(void*)@plt>
      40068c:       31 c0                   xor    %eax,%eax
      40068e:       48 83 c4 08             add    $0x8,%rsp
      400692:       c3                      retq
      400693:       66 66 66 66 2e 0f 1f    data32 data32 data32 nopw %cs:0x0(%rax,%rax,1)
      40069a:       84 00 00 00 00 00

```

The last 2 lines are some sort of boundary padding.

The `sub` at the start moves the stack pointer back 8 bytes (a pointer size) so that the call to `operator new` returns the result exactly where it'll be needed (on main's stack). At the end it adds it again so when `main` returns the stack is as expected. You'll see how "truly optimum" this is.

This is the kind of stuff you need to be mindful of.
> 6 votes

# Answer
**First Approach**

A pattern used by several engines is to add either (a) some indirection or (b) extra metadata.

That is, your code can be structured like this (NOTE: all code examples in this post are ad-hoc, probably don't compile, and need a lot of work to make safe and correct):

```
struct record {
  IResource* resource = nullptr;
  unique_ptr<ILoadState> state;
  atomic<int> counter = 0;
};

template <class T> class res_ptr  {
  record* rec = nullptr;

public:
  explicit res_ptr (record* rec) : rec(rec) { if (rec) ++rec->counter; }
  ~res_ptr () { if (rec && 0 == --rec->counter) delete rec; }

  T* get() const { return static_cast<T*>(rec->resource); }

  explicit operator bool() const { return rec && rec->resource; }

  // ... supplementary member functions ...
};

```

That allows you to create a `record` object when you first request a resource without having to finish loading the resource. You can pass that object around as a shared object managed by the `res_ptr<>` smart pointer.

This would be used with some kind of resource loader that can create the `record` object upon request (or return a cached one) and then kick off the resource load on another thread, if you want. Even without threading, this approach lets you unload or recreate the resource object without breaking any references to the `record`. Note that the code below doesn't deal with uncaching record, which you'd definitely want for correctness.

```
class loader {
public:
  virtual type_index get_type() const = 0;
  virtual void* load(string const& path) = 0;
};

class resource_manager {
  unordered_map<string, record*> library;
  unordered_map<type_index, unique_ptr<loader>> loaders;

public:
  // register a helper that knows how to load a particular type of resource
  void register_loader(unique_ptr<loader> load) {
    auto type = load->get_type();
    loaders.insert({type, std::move(load)});
  }

  // load a resource of type ResourceT from the given path path
  template <class ResourceT>
  res_ptr<ResourceT> Load(string path) {
    // check if the resource is already loaded
    auto lib_it = library.find(path);
    if (lib_it != library.end())
      return res_ptr<ResourceT>{lib_it->second};

    // attempt to find a registered loader for the resource type
    auto load_it = loaders.find(typeid(ResourceT));
    if (load_it == loaders.end())
      return {};

    // create and cache all the record machinery
    auto rec = make_unique<record>();
    rec->state = make_unique<state>(path);
    library.insert({path, rec.get()});

    // load the resource now, since we don't have threading in play
    rec->resource = load_it->second->load(rec->state->path);
    return res_ptr<ResourceT>(rec);
  }
};

```

**Second Approach**

An alternative is to just make your smart pointer store extra metadata. You'd get something like this:

```
template <class T>
class res_ptr {
  T* ptr = nullptr;
  string key;

public:
  explicit res_ptr (T* ptr) : ptr(ptr) { if (ptr) key = ptr->get_key(); }
  explicit res_ptr (string key) : key(std::move(key)) {}
  ~res_ptr () { if (ptr) resource_singleton.release(ptr); }

  T* get() const { return ptr; }
  T* get() {
    if (!ptr)
      ptr = resource_singleton.try_load(key);
    return ptr;
  }

  explicit operator bool() const { return ptr; }
  explicit operator bool() { return get(); }

  // ... supplementary member functions ...
};

```

In that case, `resource_singleton::try_load` will take a given input resource path and check to see if the resource is fully loaded. If the resource is fully loaded then it'll add a reference and return that pointer.

This second approach maps well to some forms of resource loading as you can mark up your objects with `res_ptr<>` properties; these will get their key loaded off disk and then automatically resolve when necessary. e.g. you might write code like the following and have everything auto-resolve:

```
// header
class SkinnedMeshComponent {
  string name;
  res_ptr<Material> mat;
  res_ptr<Mesh> mesh;
  res_ptr<Skeleton> skel;

  REFLECT(SkinnedMeshComponent);
};

// source
BEGIN_REFLECT(SkinnedMeshComponent)
  STRING_PROPERTY("name", name)
  RESOURCE_PROPERTY("material", mat)
  RESOURCE_PROPERTY("mesh", mesh)
  RESOURCE_PROPERTY("skeleton", skel)
END_REFLECT(SkinnedMeshComponent)

// data
<object>
   <component type="transform" />
   <component type="physics" />
   <component type="skinned_mesh">
     <string key="name">Scary Zombie</string>
     <resource key="material">/materials/zombie.mat</resource>
     <resource key="mesh">/meshes/zombie.md5</resource>
     <resource key="skeleton">/skeletons/zombie.anim</resource>
   </component>
</object>

```
> 2 votes

---
Tags: c++, resource-management, architecture, initialization
---


# Question
Title: How do you use the distributive law with Quaternions and vectors?
I'm trying to solve for the distance from Obj1 to Obj2 relative to Obj1, because I do not know their global positions, rotations, or the difference between their local spaces.

Thankfully, they are locked to each-other, so their relationship relative to Obj1 is constant across time.

I believe that the following is true, assuming A and B represent discrete samples at different times where the objects moved between A and B:
`Obj1.positionB + Obj1.rotationB * relationship = Obj1.positionA + Obj1.rotationA * relationship + (Obj2.positionB - Obj2.positionA)`

Given that, we can solve for relationship, right? First, move all instances of relationship to the left side...
`Obj1.rotationB * relationship - Obj1.rotationA * relationship = Obj1.positionA + (Obj2.positionB - Obj2.positionA) - Obj1.positionB`

From here, the `AB+AC = A(B+C)` rule tells me to do this: `(Obj1.rotationB - Obj1.rotationA) * relationship = Obj1.positionA + (Obj2.positionB - Obj2.positionA) - Obj1.positionB`

But I know that QuaternionA*Vector+QuaternionB*Vector does NOT equal (QuaternionA\*QuaternionB)\*Vector.

**So, given `QuaternionA*VectorA+QuaternionB*Vector = VectorB`, is it possible to solve for VectorA? How? I'm using Unity, if that's any help.**

(Note that the above assumes that the two coordinate spaces are oriented consistently even though they don't share the same origin. Solving for difference in parent space orientation, if ever necessary, is a different problem.)

# Answer
> 1 votes
There are some issues you might want to clear up in your question, perhaps with some drawings. In any case, here are some things to note:

* If you just need to find the distance from `Obj1` to `Obj2`, why don't you just calculate it as the difference between their positions?
* What is `relationship`? If it is a matrix transform, you may be able to decompose it to find the translation vector. Or even better, apply it to `(0, 0, 0)`.
* If you are 100% sure your math is right, how about you convert your quaternions to rotation matrices? Matrices are much easier to operate with.

---
Tags: mathematics, quaternion
---


# Question
Title: Random/procedural generation of puzzle-platform levels
I have an idea for a puzzle-platform game where the levels would be randomly generated. Creating a random generation is relatively simple. What's not easy is checking that randomly generated level to see if it's possible to complete, or generating a level where completion is possible. I think there are a number of different ways to do this.

Are there any games that employ something like this? How is something like this typically done, if ever?

# Answer
> 1 votes
Since I don't know the way a level is implemented in your game, I will give a general answer.

Typically, the game has a set of known rules (constraints) by which it operates. You need to apply them in your validation algorithm.

My solution for a (I assume) complex game like yours would be, as follows.

After the level has been generated, run a simulation. If the simulation solved the puzzle, you're done. Otherwise, fix the existing level or generate a new one and start over.

A simple example of this can be seen here, where he first generates a world according to a few simple rules (making corridors), places his agents on map and runs simulation to validate the level. If simulation fails, he tries to fix the level. If simulation is still failing, he generates a whole new world and starts over.

Alternatively, you could avoid the expensive game simulation by using a search algorithm like the A\* algorithm, which can serve as a puzzle solver directly on your data structures. Another option might be evolutionary algorithms, although they can be quite computationally expensive and cannot guarantee valid levels.

**EDIT:** As DMGregory noted in the comments, you're better off generating a valid level as you go, rather than fixing it after it's been generated. This will most probably produce better levels and will be computationally cheaper. However, the implementation is naturally harder, especially when you're after complex level generation.

# Answer
> 0 votes
To create a concrete solution, you need to understand the movement constraints (or more so, the movement flexibility) in the platformer without the puzzle elements first. Like DMGregory said, for instance, you need to randomly place platforms within a jumping distance from one another. You also need to define a "possible jump". This jump must not be obstructed in later steps by additional platforms or elements.

After you have a valid platforming level generator, you can throw in puzzle elements without disrupting the initial constraints. For instance, add buttons that open doors, cause platforms (that were initially hidden) to appear out of thin air and so forth.

In order to provide a more specific answer, I must say that you could probably generate the platforms for a LIMBO like game but it appears to me the "puzzles" if you can call them that, are obviously hand crafted in that design.

Procedural generation is good for creating fresh, riveting new combinations of existing elements. In that specific case, it appears that it's pretty linear (the combination is not so important) and the puzzles just appear one after the other.

---
Tags: game-design, algorithm, procedural-generation, platformer, level-design
---


title: OpenGL, Blender and model optimization

text:
# Question
Title: OpenGL, Blender and model optimization
I'm learning OpenGL and there is something I don't understand regarding model loading.

Lets say I found a free .blend model of a tree. The problem is - currently in my program all models have only one texture. But this model use two textures, one for trunk and another for branches and leaves. Actually trunk and leaves are two separated models on one scene.

What to do in this situation? Editing model manually could take a long time (I'm not an expert in Blender). I could join two textures in one and correct UV's automatically. But most likely a lot of space will be wasted on such an automatically created texture. I could also modify my model format (it's more like memory dump + header actually) so I could store N models with N textures as one object. But using N times more VBOs and textures when you actually need only one is inefficient.

I'm wondering maybe there is a well known tool for automatically joining multiple objects in one? Or maybe some good practice for this case? Or something like this.

# Answer
> Actually trunk and leaves are two separated models on one scene.

Normally, when one model needs to be divided up like this into sub-parts or child models like that, the separate sub - objects become child nodes of the parent object in the transform hierarchy (or Scene graph), so that changes made to the parents world transformation are automatically applied to the child meshes. Such a hierarchy allows you to change the parent's position and orientation and stuff without worrying about the child meshes. Blender already stores its models in such an hierarchy.

To solve your trouble, you do not need to change how you store your models at all. All you need to change is how you render the objects in your scene.

You can load the trunk and branches as separate meshes with their own textures (preferably storing them in the same VBO as well, each starting at an offset, and using the offset while calling `glDrawArrays` ). Then after you load the meshes into memory, you can create a hierarchy of their transforms where the trunk is the parent node and the branches are the children. When you want to render the branches, you just need to multiply the local transform of the branches with their parent trunk's transform to get their final transformation matrix.

This way, you save yourself most of the work implementing a texture combiner or making a new format. You just need to design the transform hierarchy.

A nice resource that would help you implement such an hierarchy efficiently is this. It might help you get an idea.
> 1 votes

---
Tags: opengl, 3d, models, blender
---


title: How to make a levels map page?

text:
# Question
Title: How to make a levels map page?
I'm trying to make a levels map page that shows number-buttons in the page. I want to make this page in a XML layout file and I'm actually trying to make something like this:

I know that I should provide a picture for the background and the background is not a problem, but I'm trying to place those buttons in certain places. I can do that by assigning margins to the buttons but then it won't show up the same way on a bigger or a smaller screen. Is there any way to do this?

# Answer
If you want to define the positions of the buttons independant of the screen resolution, you might want to use a relative coordinate system. So a single screen is defined as a 0 (left border) to 1 (right border) and 0 (top) and 1 (bottom).

So a button halfway to the screen is at 0.5 , 0.5. To calculate the actual position, multiply the axis by the screen dimension of that axis. So if the screen is 320 pixels wide, the button appears at 0.5 * 320 = 160 pixels.

In the example your map screen may appear bigger than a single display, so a y coordinate of 2.6 is perfectly valid.
> 1 votes

---
Tags: java, android, xml
---


# Question
Title: Updating object positions after screen moves. Is there a better way?
I am making a top down 2D shooter using SDL2 for fun and I ran into a problem. I have a whole list of enemies each with their position on the screen stored in an array. Now you only see a portion of the map on your screen, because the whole map is too large. I want to have the player be able to move around the map, in which case I have to update the position of all the enemies. The same goes for projectiles and buildings. So I would have to loop over each of these every time the screen moves. I thought that a smarter way may be possible where you keep track of the entire map for each frame and when you render it you zoom in on only the part you need. That way you only have to keep track of one position vector, for instance the point on the map at which you want your screen to be centered. How is this problem normally tackled?

I realize that both methods will take some time, but seeing as the map is not THAT large, maybe 6x the screen, I thought it might be worthwhile. The problem is then that I am rendering the textures using SDL\_RenderCopyEx and then displaying them with SDL\_RenderPresent, and I don't think you can zoom in like that.

# Answer
Create a camera class that holds the position of the camera, this could update to track your player ship.

In the render logic, for each entity you can do 2 things: 1. calculate the position of the entity related to the camera 2. if the entity is not in view, don't render.

So you don't update each entity with your camera position- just keep everything as it is in "world coordinates". You just change the render call in your entity class with the camera in mind (and add the benefit of culling entities that are outside the view). So you convert your "world coordinates" to "screen coordinates": `screen.position = obj.position - camera.position`

This is way better performance wise than drawing everything to a huge texture.

Added benefits is that you could add things like camera shake, briefly cue to a boss etc. to the camera class without affecting the rest of your game logic.
> 1 votes

# Answer
To solve this, you could create a texture the size of your entire map. SDL2 can then render to a texture instead of rendering directly to the screen. Store every object's position (player, enemies and whatnot) in absolute terms (from the top-left corner of the map), and render everything. Once this is done, you can then render a portion of the map texture to the screen, using SDL\_RenderCopy\[Ex\]:

```
// at the beginning of the game:
SDL_Texture* world = SDL_CreateTexture(
    renderer,
    PIXEL_FORMAT,
    SDL_TEXTUREACCESS_TARGET, // the most important, allows you to render to this texture.
    worldWidth,
    worldHeight);
SDL_Rect camera = {0, 0, cameraWidth, cameraHeight}; // change x and y to center the camera wherever you'd like it to be

//
// in your game loop
//
SDL_SetRenderTarget(renderer, world); // render everything to the world texture

// render your enemies, player and all
SDL_RenderCopy(renderer, player, NULL, player_rect); // player_rect should hold the position on the map

SDL_SetRenderTarget(render, NULL); // switch back the renderer so that it targets the screen
SDL_RenderCopy(renderer, world, camera, NULL); // this will render only the portion of world that is bound by the camera rectangle.
SDL_RenderPresent(renderer);

```

this way, you don't have to offset the position of everything depending on where you camera is. You just render as if the whole map was displayed, and then copy a tiny portion of this.

The only problem with that method is that you will render objects that, in the end, are outside the camera and will not be displayed. to solve that, you can check if an object's Rect lies in the camera rect with `SDL_HasIntersection(&camera, &object_rect);`. If not, just by pass `SDL_RenderCopy` for that object.
> 0 votes

---
Tags: sdl2
---


# Question
Title: Procedural Turn Based Puzzle Generation?
Alright, we have a large set of possible moves (what the player is allowed to do). We also have a well defined state of *success* that defines the desired goal. We want to generate a configuration where for the purpose of this question, only 1 set of moves leads to a victory within *k* steps. We also have a solver that can find all possible solutions for a given configuration problem.

For example let's take Chess, how would you place a set of chess pieces on a board such that only a specific set of moves by White will result in Check Mate?

# Answer
I would say brute force it. Let's keep chess as the example.

Let's say you created a chess AI. You could make two of the AIs play a game, while retaining a move history. Once the game is complete, mark the game-board as a "Solved State".

You can generate a bunch of these, tweaking the AI to ensure nice board placement. Would be cool to generate these with grand-master level AI bots.

Then, rewind the game back a few moves to get your "Starting State".

Run your solver from the Starting State, through every single possibility possible based on the rules. You would need to limit the maximum number of moves your solver would attempt (max k steps).

Keep track of each path in a Tree Structure, so that you can ensure that you do not run the same path twice. Once you are done checking all possibilities, look at the tree structure to see if you only have 1 path that is successful at a given size (length of path).

You could run this automatically overnight and see how many you get in the morning.
> 1 votes

# Answer
That sounds like a constraint problem.

I'd recommend writing a model for an existing solver such as Minion or GECODE, perhaps using the Savile Row modeling assistant. These implement many advanced optimisations for solving constraint problems and are likely to be *much* easier to change and more performant than a hand-hacked solution.

Savile Row in particular comes with a directory full of examples for solving similar well-known constraint problems, such as n-queens, knight's tour and Sokoban.
> 1 votes

---
Tags: procedural-generation, puzzle, chess
---


# Question
Title: ASSIMP transformation hierarchy and animations
I don't fully understand the transformation hierarchy used by ASSIMP.

1. According to the docs (http://assimp.sourceforge.net/lib\_html/structai\_node.html) an aiNode's transformation is relative to its parent. Does this mean I need to concatenate its parents (and their parents) matrices with the nodes matrix to get the LOCAL matrix for the model? Or is the nodes transform already per-multiplied with all the parents, meaning transforming the nodes vertices by the nodes transform directly puts the vertices in the models LOCAL space (and not just the 'NODE' space)?
2. Kinda same as 1) but does transforming the vertices with the aiNodes transform put it in the "bind pose"?
3. What is the point of even having a transform per aiNode? Why not just pretransform all the vertices? From what I understand the counter-argument has something to do with animations... but each animation step already has its own position/scale/rotation!

Any help is much appreciated, I don't fully grasp the transform hierarchy which makes it hard to formulate good questions.

# Answer
> 0 votes
To answer your questions:

1. Yes you need to multiply the child node's transform with the parent node's transform to obtain the final world transform for the mesh at that node. You basically have to walk down the hierarchy to the child nodes, multiplying all the transform together to get the transform for each child node's mesh.
2. No, transforming the vertices with the aiNodes transform does not put it in the "bind pose".
3. It is not pre-multiplied so that when you change the transform of the parent nodes, the child node's final transform changes automatically with them (as you are multiplying with the parent's transform, thus applying it on the child node). This means if for example you have a parent car mesh, which have child wheel meshes, changing the transform of the car mesh would automatically affect the transform of the wheels and the wheels would move with the body. If it were'nt the case, and if the transformed were pre-multiplied, then either you would have to transform the wheels separately and make them move, or the wheels stay where they were and only the body moves away, which you might not want. Also, as Syntac\_ mentioned, it gives you more flexibility in regards to what you want to do with the hierarchy and how you want to build the Scene graph. Have a look at this as it explains this stuff better.

# Answer
> 1 votes
You must multiply each node by it's parent's transform (and the parent's node parent's transform, etc), to get the local transform for that node.

Why is it not pre-multiplied? Because it gives you the option to rebuild the hierarchy at run-time after applying transformations to any point of the hierarchy.

---
Tags: animation, transformation, skeletal-animation, assimp
---


# Question
Title: Libgdx are textures off screen rendered?
Let's say that my code looks like this:

```
OrtographicCamera camera=new OrthographicCamera();
camera.setToOrtho(true, 100, 150);
SpriteBatch spriteBatch=new SpriteBatch();
spriteBatch.setProjectionMatrix(camera.combined);
TextureRegion textureRegion = textureAtlas.findRegion("redCircle");
spriteBatch.begin();
spriteBatch.draw(textureRegion, 200, 200);
spriteBatch.end();
//This will try to render a TextureRegion outside of the OrthographicCamera's field of view

```

My question is: should I write my code so that it checks everytime the coordinates of what I am trying to draw, detects if it's offscreen, and in that case skips it (to spped up the rendering), or does Libgdx already do that for me?

# Answer
> 3 votes
Ok, so I tried executing these 2 pieces of code: (camera is `camera=new OrthographicCamera(); camera.setToOrtho(true, 100, 100*screenW/screenH);`, and the 2 texture regions are of size 64\*64, from the same textureAtlas)
Code 1: rendering on-screen

```
public void renderGameScreen(){
    spriteBatch.setProjectionMatrix(camera.combined);
    spriteBatch.begin();
    TextureRegion tr;
    for (int i = 0; i<1000; i++){
        if (Math.random()>0.5){
            tr = R.border;
        } else {
            tr=R.gamebackground;
        }
        spriteBatch.draw(tr, (float)(Math.random()*100), (float)(Math.random()*100));
    }
    spriteBatch.end();
}

```

Versus code 2: rendering off-screen:

```
public void renderGameScreen(){
    spriteBatch.setProjectionMatrix(camera.combined);
    spriteBatch.begin();
    TextureRegion tr;
    for (int i = 0; i<1000; i++){
        if (Math.random()>0.5){
            tr = R.border;
        } else {
            tr=R.gamebackground;
        }
        spriteBatch.draw(tr, (float)(Math.random()*100)+200, (float)(Math.random()*100)+200);
    }
    spriteBatch.end();
}

```

Notice how the two are identical except for the `spriteBatch.draw()` method, which in code 2 is offset by 200 pixels, and is therefore off screen)
Result:
On PC, code 1 was at 10 to 30 fps. code 2 was at 50 to 60 fps.
On android code 1 was at 3-4 fps, code 2 was at 60.
So, I'd conclude that yes, libgdx does check if a texture is offscreen before rendering it.
If there are any flaws in my test that may have caused it to give the wrong result, I'd be glad if someone could point them out.

---
Tags: 2d, libgdx, textures, rendering
---


# Question
Title: Only one object rendered to FBO for Shadow Map
I've been playing around with rendering shadow maps using FBOs in OpenGL. I set up a simple directional light in my engine and managed to get a shadow map rendered. My Scene is a big castle and the shadow was cast over most of the other objects in the scene. Out of curiosity I removed the castle and just added a simple floor and my shadow map no longer renders properly. It seems that only one object at a time is making it through my render pass and onto the shadow map.

Here's an overview of the way the render is structured:

```
void RenderingManager::RenderGL()
{
    PreRenderGL();

    ShadowPassGL();

    //Other user defined render passes here?

    ScenePassGL();

    //Cleanup
    directionalLights.clear();
    pointLights.clear();
    renderables.clear();
}

```

The `ShadowPassGL()` call is fairly simple

```
void RenderingManager::ShadowPassGL()
{
    glViewport(0, 0, 1024, 1024);
    for (unsigned int i = 0; i < directionalLights.size(); i++)
        directionalLights[i]->RenderShadowMap(ShadowShader);
}

```

The `RenderShadowMap(Shader* shadowShader)` call is a bit more complicated but it seems the orthographic view is setup properly, the look at view is also correct. I have verified that the matrices that are generated by my math functions work.

```
void DirectionalLightInternal::RenderShadowMapGL(Shader* shadowShader)
{
    //Bind shadow shader for rendering shadow maps
    shadowShader->bindShader();

    //Send info about the directional light to the shader for shadow mapping
    Vector3 focalPoint = direction * -10;

    //Compute MVP from light's direction
    Matrix4 depthProjection = Matrix4::getOrthographicProjection(-10, 10, -10, 10, -20, 20);
    Matrix4 depthView = Matrix4::getLookAtView(focalPoint, Vector3(0, 0, 0), Vector3(0, 1, 0));

    depthMVP = depthView * depthProjection;

    shadowShader->setGlobalMatrix4("depthMVP", depthMVP);

    //Actually bind framebuffer and render shadow map for texture

    //Bind buffer for drawing
    glBindFramebuffer(GL_FRAMEBUFFER, shadowBuffer);

    glClearDepth(1.0f);
    glClear(GL_DEPTH_BUFFER_BIT);

    //render buffer
    RenderingManager::RenderPass();

    //Clean up
    glBindFramebuffer(GL_FRAMEBUFFER, 0);
    shadowShader->freeShader();
}

```

And the final bit of code that I think is relevant is the `RenderPass()` method which just loops through all renderable objects and tries to render them with `RenderObjectGL(Renderable renderable)`.

```
void RenderingManager::RenderObjectGL(Renderable renderable)
{
        Mesh* mesh = renderable.mesh;

        GLint shaderProgram;
        glGetIntegerv(GL_CURRENT_PROGRAM, &shaderProgram);

        GLuint vPosition = glGetAttribLocation(shaderProgram, "vPosition");
        GLuint vNormal = glGetAttribLocation(shaderProgram, "vNormal");
        GLuint vTexCoord = glGetAttribLocation(shaderProgram, "vTexCoord");

        glEnableVertexAttribArray(vPosition);
        glEnableVertexAttribArray(vNormal);
        glEnableVertexAttribArray(vTexCoord);

        int normalOffset = mesh->getPointSize();
        int texCoordOffset = normalOffset + mesh->getNormalSize();

        glBindBuffer(GL_ARRAY_BUFFER, mesh->getVBO());
        glVertexAttribPointer(vPosition, 3, GL_FLOAT, GL_FALSE, 0, BUFFER_OFFSET(0));
        glVertexAttribPointer(vNormal, 3, GL_FLOAT, GL_FALSE, 0, BUFFER_OFFSET(normalOffset));
        glVertexAttribPointer(vTexCoord, 2, GL_FLOAT, GL_FALSE, 0, BUFFER_OFFSET(texCoordOffset));

        glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, mesh->getIBO());

        //Draw Shape
        glDrawElements(GL_TRIANGLES, mesh->getNumberOfVerts(), GL_UNSIGNED_SHORT, (void *)0);
}

//Render every object in the scene; assume a bound shader
void RenderingManager::RenderPassGL()
{
    for(unsigned int i = 0; i < renderables.size(); i++)
        RenderObjectGL(renderables[i]);
}

```

I figured some images to illustrate the problem would be pretty useful.

When I render with the castle it looks like this:

And the shadow map from the scene is:

Interestingly the shadow map is really just of the castle, the other objects aren't in the shadow map.

Now the scene with just the floor:

And its shadow map:

Which again seems to be of *just* the floor, none of the other objects in my scene. Is there some aspect of FBOs that I'm missing here?

# Answer
After much deliberation and a stroke of insight I figured out what the problem was. It was a problem with my shadow map vertex shader; I wasn't putting the objects into model space. That means that all objects were being rendered at 0, 0, 0 with a scale of 1 and no rotation. OOPS.

Properly applying a model matrix in the shader managed to fix the issue.

EDIT: If you're interested in seeing the exact code that fixed the problem here's a link to the commit on Github: https://github.com/Honeybunch/Brickware-Engine/commit/4908040f3223ae157cdb55244bc6e079f7970327

There was some extra architecture that went into getting the model matrix sent to the shadow shader that might be interesting.
> 4 votes

---
Tags: opengl, c++, shadows, shadow-mapping, fbo
---


# Question
Title: add random walls with an array in 3D xna 4
I'm trying to add walls to my 3D game. I created a wall entity and added model array

```
public Walls()
{
  modelArray = new Model[10];
}

public void Initialize(ContentManager contentManager)
{
  for (int i = 0; i < modelArray.Length; i++)
  {
    rnd = new Random();
    sidesWall = rnd.Next(-4, 4);
    forwardWall = rnd.Next(-8, 0);
    modelArray[i] = contentManager.Load<Model>("wall");
  }
}

```

Draw method:

```
public void Draw(Camera camera)
{
  foreach (Model m in modelArray)
  {
    foreach (ModelMesh mesh in m.Meshes)
    {
      foreach (BasicEffect effect in mesh.Effects)
      {
        effect.EnableDefaultLighting();
        effect.PreferPerPixelLighting = true;
        effect.World = GetWorldMatrix();
        effect.View = camera.ViewMatrix;
        effect.Projection = camera.ProjectionMatrix;
      }

      mesh.Draw();
    }
  }
}

```

It doesn't work and it shows only one wall.

How can I make it work?

# Answer
> 1 votes
Your draw method shows no translation or rotation of each wall, they will end up on the same spot. Your world matrix should(could) be

```
World = Matrix.CreateScale(wallscale) * Matrix.CreateRotation(wallRotation) * Matrix.CreateTranslation(wallPosition);

```

---
Tags: 3d, xna-4.0, model-loader
---