title: Frustum culling takes ages c++

text:
# Question
Title: Frustum culling takes ages c++
I have two ways of doing frustum culling taken from different web sources. First one takes 200ms to check 10k AABBs, second around 50ms for the same box count. I read some forum answers, people say 0.5ms for 10k is ok but I'm totally far away from those numbers. So what am I doing wrong ?

Measuring time here:

```
        auto frustum = camera.getFrustum(); //frustum

        auto n = frustum.pNear;
        auto f = frustum.pFar;
        auto e = frustum.pExtra;

        ArrayList<Pair<vec3, vec3>> planes;
        ArrayList<vec3> v1;
        n.genVertices(v1);

        ArrayList<vec3> v2;
        f.genVertices(v2);

        planes << Pair<vec3,vec3>(v1[0], -n.genNormal());
        planes << Pair<vec3,vec3>(v2[0], n.genNormal());
        for(size_t i = 0; i < 4; i++)
        {
            planes << e[i];
        } //frustum planes array initialization done

        ArrayList<AABB> objs; //10k test aabbs
        for(size_t i = 0; i < 10000; i++)
        {
            objs << AABB(vec3(rand_float()/100,rand_float()/100,rand_float()/100),rand_float()/100);
        }

        auto t1 = timer.getTimeNanoSeconds(); //starting to measure
        for(size_t i = 0; i < 10000; i++)
        {
            rs::CollisionEngine::checkAABBAndFrustumFast(objs[i], planes);
        }
        auto t2 = timer.getTimeNanoSeconds() - t1; //getting time
        println("Collision check of 10k objs: "+ toString(t2/1000000) + " ms"); //printing time

```

Here is slow and fast collision checks:

```
 /**
    *
    * @param box
    * @return 0 - inside, 1 - intersects, 2 - outside
    */
    us checkAABBAndFrustumSlow(AABB box, ArrayList<Pair<vec3, vec3>>& planes)
    {
        ArrayList<vec3> vertices;
        box.genVertices(vertices);

        us totalIn = 0;

        for(int i = 0;i<6;i++){ //six planes for every frustum
            Pair<vec3, vec3> plane = planes[i];
            auto n = plane.v2;

            uint inCount = 8;
            uint pIn = 1;

            for(int j= 0;j<8;j++){
                vec3 v = vertices[j];
                vec3 toVertex = (v - plane.v1).normalize();
                float res = n * toVertex;
                if(res < 0){
                    inCount -=1;
                    pIn = 0;
                }
            }

            if(inCount == 0) return 2;
            totalIn += pIn;
        }

        if(totalIn == 6) return 0;

        return 1;
    }

    using namespace rs;
    vec3 getPosForFrustum(AABB b, vec3 n)
    {
            vec3 max = b.center + b.extent;
            vec3 p = b.center - b.extent;
            if (n.x() >= 0)
            p(1) = max.x();
            if (n.y() >=0)
            p(2) = max.y();
            if (n.z() >= 0)
            p(3) = max.z();

            return p;
    }

    vec3 getNegForFrustum(AABB b, vec3 n)
    {
        vec3 min = b.center - b.extent;
        vec3 p = b.center + b.extent;
        if (n.x() >= 0)
            p(1) = min.x();
        if (n.y() >=0)
            p(2) = min.y();
        if (n.z() >= 0)
            p(3) = min.z();

        return p;
    }

    uint checkAABBAndFrustumFast(AABB box, ArrayList<Pair<vec3, vec3>>& planes){

            uint result = 0;
            for(int i = 0;i<6;i++) {

                auto n = planes[i].v2;
                auto p = planes[i].v1;

                if (n * (getPosForFrustum(box, n) - p) < 0)
                    return 2;
                else if (n * (getNegForFrustum(box, n) - p) < 0)
                    result = 1;
            }

            return result;
    }

```

EDIT: ArrayList is a custom vector like structure

Pair contains a copy of two objects it takes.

# Answer
Main ways to speed up frustum culling (and collision in general):

* **simplified bounding**: you have AABBs (check)
* **fast collision functions**: looks like you are doing this (in progress)
* **spatial partitioning objects in the world**: ???

Spatial partitioning gives the most speed up. Are you doing anything? Depending on game type, there are a ton of easy ways to get massive performance boosts to: frustum culling, collision, picking, AI, etc. all using the same world partitioning.
> 1 votes

---
Tags: c++, collision-detection, optimization, aabb, frustum
---


# Question
Title: Unity method to get a vector, which is x seconds behind another moving vector (A bit like TrailRenderer)
I want a function, which lets me follow a vector with a bit offset or delay, like it's done in the TrailRenderer. I tried to achieve this with the Lerp function, but that didn't work for me like I want, since I had to wait for a specific time until the lerp was done and then updated my targetVector of the Lerp again, which led to a bad result.

Now a possible solution to my problem would be a List, which holds all Positions of my Vector from the past 50 frames or so and I assign the same values to my other Vector with a specific offset. But I was wondering if there is some built in method in Unity, which could achieve this for me.

Edit: This is about moving a Canvas

# Answer
> 4 votes
What you describe, in terms of following a position's exact path with a time delay, might be both more complicated and less satisfying than what you *want*.

Here's a mock-up of two possibilities:

**The object labeled "Path" follows the exact path of the leader object**, a constant amount of time behind it. This means:

* When the leader starts moving, there is a delay before the follower moves. Likewise for stopping.
* Any kinks or jitter in the leader's movement is repeated exactly by the follower.

**The object labeled "Blend" mixes-together its current position with the leader's each frame**, so that it attracts toward it asymptotically.

* The follower always moves directly toward the leader, cutting corners tighter and smoothing out jitter to a degree.
* The follower moves slower when it's close to the leader, and faster when far away, making its follow distance/delay non-constant (but for some applications this gives a pleasant ease-in and ease-out to its motion effectively "for free")

The great thing about the blend approach is how simple the code is:

```
public class BlendFollower : MonoBehaviour {

    public Transform leader;
    public float followSharpness = 0.05f;

    void LateUpdate () {
        transform.position += (leader.position - transform.position) * followSharpness;
    }
}

```

I use this about 80% of the time when I want some quantity to track toward another in games - it works for floats, positions, colours, rotations, etc. It's a super useful little trick.

---

**Edit:** for rotation, you'd use something like this:

```
transform.rotation = Quaternion.Lerp(
                          transform.rotation,
                          leader.rotation,
                          followSharpness);

```

Just ensure the Quaternions you start with are valid (not all zeroes or NaNs) or this will blow up. I often write a `Quaternion.IsValid()` extension method to check this if I'm working with a lot of computed rotations.

---

Note that since this is blending a constant amount *per frame*, so at higher framerates it will be sharper and at lower framerates, spongier. For purely visual effects this is often tolerable, but if gameplay outcomes depend on the follow rate then you'll either want to correct for this or move it to `FixedUpdate` so it's consistent.

Compare this to the path follow:

(Variable framerates account for some of this complexity - if you want to follow a constant number of *frames* behind, rather than seconds, then the code is a bit simpler. Also, I threw in my path-drawing debug gizmo code too.)

```
public class PathFollower : MonoBehaviour {

    const int MAX_FPS = 60;

    public Transform leader;
    public float lagSeconds =  0.5f;

    Vector3[] _positionBuffer;
    float[] _timeBuffer;
    int _oldestIndex;
    int _newestIndex;

    // Use this for initialization
    void Start () {
        int bufferLength = Mathf.CeilToInt(lagSeconds * MAX_FPS);
        _positionBuffer = new Vector3[bufferLength];
        _timeBuffer = new float[bufferLength];

        _positionBuffer[0] = _positionBuffer[1] = leader.position;
        _timeBuffer[0] = _timeBuffer[1] = Time.time;

        _oldestIndex = 0;
        _newestIndex = 1;
    }

    void LateUpdate () {
        // Insert newest position into our cache.
        // If the cache is full, overwrite the latest sample.
        int newIndex = (_newestIndex + 1) % _positionBuffer.Length;
        if (newIndex != _oldestIndex)
            _newestIndex = newIndex;

        _positionBuffer[_newestIndex] = leader.position;
        _timeBuffer[_newestIndex] = Time.time;

        // Skip ahead in the buffer to the segment containing our target time.
        float targetTime = Time.time - lagSeconds;
        int nextIndex;
        while (_timeBuffer[nextIndex = (_oldestIndex + 1) % _timeBuffer.Length] < targetTime)
            _oldestIndex = nextIndex;

        // Interpolate between the two samples on either side of our target time.
        float span = _timeBuffer[nextIndex] - _timeBuffer[_oldestIndex];
        float progress = 0f;
        if(span > 0f)
        {
            progress = (targetTime - _timeBuffer[_oldestIndex]) / span;
        }

        transform.position = Vector3.Lerp(_positionBuffer[_oldestIndex], _positionBuffer[nextIndex], progress);
    }

    void OnDrawGizmos()
    {
        if (_positionBuffer == null || _positionBuffer.Length == 0)
            return;

        Gizmos.color = Color.grey;

        Vector3 oldPosition = _positionBuffer[_oldestIndex];
        int next;
        for(int i = _oldestIndex; i != _newestIndex; i = next)
        {
            next = (i + 1) % _positionBuffer.Length;
            Vector3 newPosition = _positionBuffer[next];
            Gizmos.DrawLine(oldPosition, newPosition);
            oldPosition = newPosition;
        }
    }
}

```

# Answer
> 1 votes
Unity does not store this information, so there is no property or field that holds the old position of objects. Once a frame passes, the old positions of objects are gone.

You can get around this by storing the last few positions yourself and interpolating between them. Here's some code:

```
using UnityEngine;

public class Tracker : MonoBehaviour
{
    public int trailIntervalsCount = 5;
    public float trailIntervalDuration = .5f;
    Vector3[] pastPositions = new Vector3[0];
    int writeIndex = 0;
    float timer;

    public Vector3 GetPastPosition(float secondsAgo)
    {
        secondsAgo = Mathf.Min((trailIntervalsCount-1) * trailIntervalDuration, secondsAgo);
        float intervalsAgo = ((secondsAgo - timer) / trailIntervalDuration) + 1;
        Vector3 posAtFloor = getPositionByInterval(Mathf.FloorToInt(intervalsAgo));
        Vector3 posAtCeil = getPositionByInterval(Mathf.CeilToInt(intervalsAgo));
        float t = intervalsAgo - Mathf.Floor(intervalsAgo);
        return Vector3.Lerp(posAtFloor, posAtCeil, t);
    }

    void Start()
    {
        // Initialize the past positions buffer to our current position.
        FillPastPositions();
    }

    void FixedUpdate()
    {
        if (trailIntervalsCount != pastPositions.Length)
        {
            FillPastPositions();
        }
        timer += Time.fixedDeltaTime;
        if (timer > trailIntervalDuration && trailIntervalDuration > 0 && trailIntervalsCount > 0)
        {
            timer -= trailIntervalDuration;
            pastPositions[writeIndex++] = transform.position;
            writeIndex %= trailIntervalsCount;
        }
    }

    /// <summary>
    /// Fills the pastPositions buffer with the current position.
    /// </summary>
    private void FillPastPositions()
    {
        pastPositions = new Vector3[trailIntervalsCount];
        for (int i = 0; i < trailIntervalsCount; ++i)
        {
            pastPositions[i] = transform.position;
        }
        writeIndex = 0;
    }

    private Vector3 getPositionByInterval(int intervalsAgo)
    {
        // Interval 0 is our current position. BUT we have to offset it to where we "will be" at the end of the interval.
        if (intervalsAgo <= 0)
        {
            Vector3 currentPos = transform.position;
            Vector3 lastPos = getPositionByInterval(1);
            float percentOfInterval = (timer / trailIntervalDuration);
            if (percentOfInterval == 0)
                return currentPos;
            else
                return Vector3.LerpUnclamped(lastPos, currentPos, (1f / percentOfInterval));
        }
        // Interval 1 is our last written position, 2 is the one before that, etc.
        else if(intervalsAgo <= trailIntervalsCount)
        {
            int index = writeIndex - intervalsAgo;
            // Wrap around once
            if (index < 0)
            {
                index += trailIntervalsCount;
            }
            // If we would wrap around twice, clamp it to the end of the trail.
            if (index < 0)
            {
                index = writeIndex;
            }

            if (index < 0 || index >= pastPositions.Length)
            {
                Debug.LogFormat("{0}, {1}, {2}", index, writeIndex, intervalsAgo);
            }
            return pastPositions[index];
        }
        else
        {
            return getPositionByInterval(trailIntervalsCount);
        }
    }
}

```

# Answer
> 0 votes
Assuming you don't care about changes in direction you can multiply the velocity vector of the object by a negative amount, then add that negative vector to the position of the object you're trailing. I think it would be something like this:

```
var positionBehind = rigidbody.velocity * -1.0f;
var trailPosition = rigidbody.position + positionBehind;

```

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


title: Gravity too weak

text:
# Question
Title: Gravity too weak
I am using Bullet Physics and the gravity in my world seems to be too weak.

This means that items fall too slowly and general values don't make as much sense as they should.

While I know that "values" used in bullet are arbitrary, but the general usages suggests that 1 unit == 1 meter.

So gravity would be -9.80665f and one meter cube would be 1.0f,1.0f,1.0f

But when I set my world up in this way it takes about 18 seconds for my box to fall 100 units.

This is much much slower then I would expect.

So am I setting up the world incorrectly?

My world

```
CollisionConfiguration = new btDefaultCollisionConfiguration();
Dispatcher = new btCollisionDispatcher(CollisionConfiguration);
Broadphase = new btDbvtBroadphase();
Solver = new btSequentialImpulseConstraintSolver();
DynamicsWorld = new btDiscreteDynamicsWorld(Dispatcher, Broadphase, Solver, CollisionConfiguration);
DynamicsWorld->setGravity(btVector3(0.0f, -9.80665f, 0.0f));

PhysicsClock.reset();

```

Stepping the world (this gets called 32 times a second)

```
Microseconds = PhysicsClock.getTimeMicroseconds();
PhysicsClock.reset();
DynamicsWorld->stepSimulation(Microseconds / 1000000.0f);

```

My body

```
btCapsuleShape Shape(0.25f, 1.75f);
Body = new btRigidBody(80, &MotionState, &Shape);

Removed    Body.setDamping(0.6f, .9999f);
Removed    Body.setAngularFactor(btVector3(0, 0, 0));
Removed    Body.setActivationState(DISABLE_DEACTIVATION);

```

Adding to the world

```
DynamicsWorld.addRigidBody(Body);

```

Motion state

```
void getWorldTransform(btTransform& centerOfMassWorldTrans) const override
{
    centerOfMassWorldTrans = m_Transform;
}

void setWorldTransform(const btTransform& centerOfMassWorldTrans) override
{
   m_Transform = centerOfMassWorldTrans;
   ...

```

Code used to control the stepping of the world

```
void WorldServer::UpdateWorldThread(void)
{
   LARGE_INTEGER    l_Frequency;
   float            l_TickInterval;

   float            l_Scale;
   float            l_Delay;

   int              l_TickBase;
   LARGE_INTEGER    l_TimeBase;

   LARGE_INTEGER    l_Now;

   QueryPerformanceFrequency(&l_Frequency);                                     //How many ticks per second
   l_TickInterval = l_Frequency.QuadPart / c_WorldUpdateFrequency;  //How many ticks per interval

   l_Scale = l_Frequency.QuadPart / 1000.0f;                                        //Scale for milliseconds

                                                                        //Create a base that will allow us to catch frames up
   QueryPerformanceCounter(&l_TimeBase);        //Store base time
   l_TickBase = 1;                                  //Store base tick

   while (IsRunning())      //While the world is running
   {
************This bit is what calls the method to step the world

      UpdateAll();              //Update
                                  //Number of milliseconds to wait
      QueryPerformanceCounter(&l_Now);
      l_Delay = ((l_TimeBase.QuadPart - l_Now.QuadPart) + (l_TickBase * l_TickInterval)) / l_Scale;

      //If there has been a large delay then we need to reset the base
      if (l_Delay < -c_WorldUpdateDelayTolerance)
      {
         QueryPerformanceCounter(&l_TimeBase);      //Store base time
         l_TickBase = 0;                                    //Store base tick

         LogWarning("World has dropped %.2f ticks.", l_Delay / -l_TickInterval);
      }

      Sleep(max(0.0f, l_Delay));                            //Yield CPU (this allows the thread to execute at a constant frequency)

      l_TickBase++;                                     //Count tick from base
   }

   //LogMessage("World UpdateWorldThread exited.");
}

```

I do have a number of other setting, but when I remove them I still have the same problems.

So what am I missing!

Note I know I could scale the world and simply multiple particular values by a common scale. But should i need to do this when my objects are in the "expected" scale?

I can definitely post more code if needed. Just ask.

I have done some more testing and I can now say that it takes 19.374506 seconds to fall 100 units.

I know this by using the following code

```
   l_Microseconds = m_PhysicsClock.getTimeMicroseconds();
   m_PhysicsClock.reset();
   m_DynamicsWorld->stepSimulation(l_Microseconds / 1000000.0f);

   total += l_Microseconds;

```

When the cube hits the ground I took a look at total and it was 19374506.

# Answer
> 2 votes
After taking a much much much closer look at my code I have managed to find the bug!

I had two problems.

Problem 1, And I can't believe I missed this. In the base class of my object there was a rogue bit of code

Body.setDamping(0.6f, .9999f);

I missed this as it was in the base, not the subclass that I use. It must have been put in there for a reason a long time back.

But that did not solve the problem. Even when I took the dampening out it was still taking around 8 seconds to fall 100 units.

So after yet more code searching it clicked!

Problem 2

I call stepworld 32 times a second. The code for this is in the question. The problem with this is that DynamicsWorld-\>stepSimulation assumes a 60Hz rate by default. So it ends up running approximately 50% slower then it should, And that is why i got an ~8 second fall time when it should be ~4.

To fix this I changed the line to

m\_DynamicsWorld-\>stepSimulation(l\_Microseconds / 1000000.0f, 1.0f, 1.0f / c\_WorldUpdateFrequency);

where c\_WorldUpdateFrequency = 32 (this will match the controlling thread)

And bingo! my objects now fall at the correct speed and all is good in the world!

*So in summary, the 3rd parameter of stepSimulation should match how frequently its being called.*

Thanks for the help.

# Answer
> 3 votes
Let's do a bit of math to see if this is correct or not. Your box starts at `ŷ = 100m`, lets assume it has to travel exactly `-100m` to reach `0m`. Then we can get a result if we insert this into the equation `y(t) = (1/2)·gt² + ŷ`: `0 = (1/2)·(-9.80665)t² + 100`, solving for `t` yields to around `4.5s`, so there must be something wrong with your configuration, as it takes much longer for you.

But as your code seems to look ok, I can't think of many pitfalls. Are you sure about your 18 seconds? Do you have a somewhat constant framerate? Compare your code with the hello world example from BulletPhysics, maybe you find a minor flaw with big influence. Try reducing the mass, as it can have an impact on the stability of the engine, as pointed out by Jon in the comments.

---

Some offtopic-last-tip: It's better to keep physics at a constant simulation time such that it doesn't do more when your game goes laggy. This can be archived by summing the seconds up and subtract until the sum is lower than a certain threshold. Here is an example in pseudo code for you:

```
time += elapsedTime;
while(time >= physicsSimulationTimeStep) //mostly (1/60)s, but you decide
{
    time -= physicsSimulationTimeStep;
    physics.step(physicsSimulationTimeStep);
}

```

---
Tags: bullet-physics
---


title: Reflection areas on texture

text:
# Question
Title: Reflection areas on texture
I have a wheel model. It's use Reflected Diffuse shader and only one texture and only one material. So it should seen like that, right?

But it's seen like that:

I'm really curious about that. What is the name of this technique? I want to search and learn this texturing technique but i don't know it's name.

When I add black texture on wheel material:

You see, texture is completely black. But why material not black completely? This is the question. What is the name of this technique?

Now we see with original texture:

It's really awesome.

# Answer
> 1 votes
I wasn't sure if there was a name for the technique, but I was corrected, (Thank you, DMGregory) and a common name for the technique would be having a "**specular mask**", where a colour channel of a texture "masks" or controls the intensity of the specular reflection. This is demonstrated below in this code which is actually an excerpt from the code of the shader you show in your screenshots.

```
void surf (Input IN, inout SurfaceOutput o) {
    fixed4 tex = tex2D(_MainTex, IN.uv_MainTex);
    fixed4 c = tex * _Color;
    o.Albedo = c.rgb;

    fixed4 reflcol = texCUBE (_Cube, IN.worldRefl);
    reflcol *= tex.a;
    o.Emission = reflcol.rgb * _ReflectColor.rgb;
    o.Alpha = reflcol.a * _ReflectColor.a;
}

```

The part most relevant to your question are the lines `reflcol *= tex.a;` and `o.Emission = reflcol.rgb * _ReflectColor.rgb;` where, first, the alpha channel of your base texture is factored into the colour of the reflective cubemap texture and then that colour is made to be the `Emission` term of the output. The Unity wiki says that the Emission term shows up even if the surface is in absolute darkness, like it might be if it were in shadow. This also explains why the reflection showed up even if the texture was nearly completely black.

So, you could say that the shininess of the surface depends on where the base texture is or isn't transparent, and if you opened up the texture for the tire in an image editor, you'd see that some sections like the tire treads would be mostly transparent.

---
Tags: unity, 3d, textures, 3dsmax, reflection-rendering
---


# Question
Title: How to do moving Rorschach using Perlin noise in c# without shaders?
I want to be able to make a moving Rorschach using Perlin noise like in this question but I know nothing about shaders. Is there a way to do it in just c#?

# Answer
> 1 votes
Honestly, I think trying to do this with the CPU is just way more work than it's worth. This is the kind of texture operation GPUs were made to simplify & accelerate for us.

This animation was created using this shader code:

```
Shader "Unlit/Rorschach"
{
    Properties
    {
        _MainTex ("Texture", 2D) = "white" {}
        _BlackLevel("Black Level", Range(0, 1)) = 0.27
        _Contrast("Contrast", float) = 60
    }
    SubShader
    {
        Tags { "RenderType"="Opaque" }
        LOD 100

        Pass
        {
            CGPROGRAM
            // Most of this is boilerplate Unity creates for us
            // when we create a new shader. I removed the fog stuff...
            #pragma vertex vert
            #pragma fragment frag

            #include "UnityCG.cginc"

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

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

            sampler2D _MainTex;
            float4 _MainTex_ST;
            // ...and added these variables to tune the blobbiness:
            float _BlackLevel;
            float _Contrast;

            v2f vert (appdata v)
            {
                v2f o;
                o.vertex = mul(UNITY_MATRIX_MVP, v.vertex);

                // Convert texture coordinates into range [-1, 1].
                // This makes our symmetry calculations neater.
                o.uv = v.uv * 2.0f - 1.0f;

                return o;
            }

            fixed4 frag (v2f i) : SV_Target
            {
                float2 mirrored = abs(i.uv);
                // Mirror the x direction to get the classic symmetrical look,
                // and multiply by texture scale so we can handle rectangular quads.
                float2 uv = float2(mirrored.x, i.uv.y) * _MainTex_ST.xy;

                // These arbitrary magic numbers just scroll two samples of the noise texture
                // at different scales/directions/offsets so it doesn't look too regular.
                // Changing these values will change the movement speed/direction/blobbiness.
                float noise = tex2D(_MainTex, 0.3f * uv + _Time.x * float2(0.2f, 0.1f)).r
                    * tex2D(_MainTex, uv + _Time.x * float2(-0.3f, -0.1f) + float2(0.2f, 0.3f)).r;

                // Calculate a gradient that's brightest at the edges, to feather out the blob.
                float mask = max(mirrored.x, mirrored.y);
                mask *= mask * mask * _BlackLevel;

                // Threshold the sum to get the desired blobbiness.
                return saturate((noise + mask - _BlackLevel) * _Contrast);
            }
            ENDCG
        }
    }
}

```

To use this, right-click in Project browser and select New -\> Shader, then paste this code in. Then select New -\> Material and choose the Rorschach shader from the dropdown (Under Unlit/Rorschach). Slap that material on a Quad and you'll be able to preview the effect live in the editor.

Assign a tiling noise texture as the texture (I borrowed the noise used in this procedural cloud tutorial) and play with the `Texture Scale`, `Black Level`, and `Contrast` parameters until you get the look you want.

You can do this CPU side with a big array of `Color32` objects, replicating the math above (using your turbulence functions instead of the `tex2D` samples) in a loop, and then using Texture2D.SetPixels32() but I think it's likely to be both messier to code AND slower to run.

# Answer
> -2 votes
Yes, and it appears to be straight forward. You need to create perlin noise then apply a filter that would take that noise and if its below a certain threshold return black, otherwise return white. Then you can invert the image along the x and y axes to get the "rorshasch" look.

The actual implementation is beyond the scope of the site, so heres a link to a pure written c# algorithm for the noise.

https://lotsacode.wordpress.com/2010/02/24/perlin-noise-in-c/

Filtering the output and then inverting it along the axes ought be easy enough to work out on your own.

Wikipedia also has a perfectly servicable pseudocode implementation that could be easily ported.

https://en.wikipedia.org/wiki/Perlin\_noise

edit: The page you linked had a link to this: http://paulbourke.net/texture\_colour/perlin/ within is the original c implementation of perlin noise which is about as canonical as you get!

---
Tags: unity, c#, perlin-noise
---


title: Smoothing a rotation vector

text:
# Question
Title: Smoothing a rotation vector
I am currently using OpenCV to track the face of a person.

With this I extract the feature points and calculate the objects heads pose by applying the "solvePnP" function.

This function gives me a translation vector and a rotation vector.

I can later apply this to a camera in Unity so that it rotates around the object simulating the face moving around.

This works fairly well, and the head moves as the user moves his head however it is very jaggy.

I figured that smoothing the translation vector would be as easy as calculating the average of the current and previous points.

But I am having a hard time smoothing the rotation vector.

The data comes as a vector (here are some consecutive examples):

```
[2.918782807448489; 0.1896564461354077; -0.2327480775908206]

[2.922645604179207; 0.1834802203843292; -0.1842765118011375]

[-3.339417618845302; -0.2022563569884805; 0.1950620807331237]

[2.884993823241512; 0.1935712993426144; -0.2426539399793146]

[-3.341933025273495; -0.2062648239738171; 0.2609849753763552]

```

Which I would like to "smoothen". The opencv documents state the following about this vector:

> Output rotation vector (see "Rodrigues") that, together with tvec, brings points from the model coordinate system to the camera coordinate system.

I've tried adding the previous plus the current rotation vector and then normalizing it and even though it seems a lot more stable it flickers between being upside down and not.

http://answers.unity3d.com/questions/437111/calculate-vector-exactly-between-2-vectors.html

Does anyone know what am I doing wrong?

# Answer
So I guess you could save like the last 10 rotations in a List and get the average of them with this function. The function return could be set as your final rotation. This should smoothen your rotation.

```
private Quaternion calcAvg(List<GameObject> rotationlist)
{
    if (rotationlist.Count == 0)
        throw new ArgumentException();

    float x, y, z, w;
    foreach (Quaternion q in rotationlist)
    {
        x += q.x; y += q.y; z += q.z; w += q.w;
    }
    float k = 1.0f / Mathf.Sqrt(x * x + y * y + z * z + w * w);
    return new Quaternion(x * k, y * k, z * k, w * k);
}

```

Further discussion on this topic can be found here, which is also the source of the code I posted above : Calculate average of arbitrary amount of quaternions (recursion)
> 2 votes

---
Tags: camera, rotation, vector
---


title: How to buffer an image in winbgim?

text:
# Question
Title: How to buffer an image in winbgim?
So ive always had problems with buffers and never used them before. I read up on the topic online but since winbgim is so old i couldnt find any definite answers to the topic. So im gonna ask them here. I found getimage and putimage but i dont know if those are what im looking for. Maybe theres a much better option!

***What i have done so far:***

* Ive searched for the answer online.
* I looked through some posts here on the forum
* I looked at the winbgim docs

***My current code:***

My current code is using the readimagefile function and it does work well. But the problem is that on systems that have an os greater than win7 ( i dont know why its fine on win 7 ) the disk is used 100% because it keeps reading the images over and over again from the actual files rather thier buffers.

Heres the decoder function i made. Its pretty messy. I just made it. Im still working on it. Its reading from a globally defined array ( I dont wanna use an dynamic array for personal reasons so i had to put it there because a \[400\]\[13\] array kinda produces an stack overflow error )

***Here it is:***

```
 void decodelevelAndDraw(int minx, int maxx) {
    int x = 0, y = 0;
    while (y != 13) {
        while (x != maxx) {
            if (levelcode[x][y] == 1) {
                //x -= minx;
                readimagefile("question.jpg", x * 70 - minx * 70, y * 70, 70 + x * 70 - minx * 70, 70 + y * 70);
                //printf("Block added at %d;%d", x * 70, y * 70);
            }
            else if (levelcode[x][y] == 2) {

                if (levelcode[x][y - 1] == 2) {
                    readimagefile("DRECK.jpg", x * 70 - minx * 70, y * 70, 70 + x * 70 - minx * 70, 70 + y * 70);

                }
                else if (levelcode[x + 1][y]== 2 && levelcode[x - 1][y] != 2) {
                    readimagefile("grass_side.jpg", x * 70 - minx * 70, y * 70, 70 + x * 70 - minx * 70, 70 + y * 70);

                }
                else if (levelcode[x - 1][y] != 2 && levelcode[x][y - 1] == 2) {
                    readimagefile("dreck_side.jpg", x * 70 - minx * 70, y * 70, 70 + x * 70 - minx * 70, 70 + y * 70);

                }
                else if (levelcode[x + 1][y] != 2 && levelcode[x][y - 1] == 2) {
                    readimagefile("dreck_side_right.jpg", x * 70 - minx * 70, y * 70, 70 + x * 70 - minx * 70, 70 + y * 70);

                }
                else if (levelcode[x - 1][y] == 2 && levelcode[x + 1][y] != 2) {
                    readimagefile("grass_side_right.jpg", x * 70 - minx * 70, y * 70, 70 + x * 70 - minx * 70, 70 + y * 70);

                }

                else readimagefile("grass.jpg", x * 70 - minx * 70, y * 70, 70 + x * 70 - minx * 70, 70 + y * 70);

            }
            else if (levelcode[x][y] == 3) {
                readimagefile("1Punch.jpg", x * 70 - minx * 70, y * 70, 70 + x * 70 - minx * 70, 70 + y * 70);

            }
            x++;
        }
        x = 0;
        y++;
    }
}

```

***More information:***

So this is for a class project so i have to use the winbgim version of graphics.h . Im using visual studio 2015 community edition with a version identical to this one for the mingw compiler. If you need like the full project feel free to ask. I will send you anything you need.

So my question is: How can i load an image into a buffer so it can be loaded quicker into the game without slowing down the dd? Please add precise and full explanations so I understand the code instead of just copy and pasting it from your answer / some websites ! I am at a loss here and could really use some of your help.

Have a nice afternoon!

# Answer
> 0 votes
So, as you know, `readimagefile` displays an image to the screen by reading it off the disk, and on some systems, it apparently only ever reads it from the disk without caching the image. So, what we need to do is move calls to `readimagefile` out of the loop and into some initializing portion of the code. You mentioned `getimage` and `putimage` in your question, and I think that may be the key to solving your problem, because if you use `readimagefile` to put the image on the screen from the disk, and then grab the image from the screen and store it in memory using `getimage`, you can call `putimage` many times in a loop without worrying about loading the image from the disk every frame. So, I haven't actually run this code, so I can't guarantee that it works because I'm unfamiliar with the library, it involves void pointers and somewhat C-like memory management, and I'm assuming you want C++. That being said, here is what I think you could do.

```
const unsigned int IMAGE_WIDTH = 32, IMAGE_HEIGHT = 32;
//Allocate the memory we need so we can store the image. Allocated as char here, as they are essentially always a single byte,
// and I'm assuming the imagesize function wants the count for the space needed to be in bytes.
void* test_image = new char[imagesize(0, 0, IMAGE_WIDTH, IMAGE_HEIGHT)];
//Put the image on-screen from disk
readimagefile("yourimage.jpg", 0, 0, IMAGE_WIDTH, IMAGE_HEIGHT);
//Take the image from the screen and put it in memory
getimage(0, 0, IMAGE_WIDTH, IMAGE_HEIGHT, test_image);
//Maybe put something here to clear the screen so you can perform the same process again for another image

while (some_condition) { //Just a generic indication that you have a loop
    /*some necessary code before*/

    //Feel free to call putimage in the loop
    putimage(43, 75, test_image, COPY_PUT);

    /*some necessary code after*/
}

//If you're not going to use the image anymore, free up its memory
delete[] test_image;

```

---
Tags: c++, graphics, visual-studio
---


title: How do animation works with mesh?

text:
# Question
Title: How do animation works with mesh?
I'm currently developing a game using OpenGL and my dev has run into a small problem. I'm having some problems understanding how "array of vectices works with animated object". For example, if we have a 3D object is there a different array for each frame of the animation or is there an instruction which does the animation ?

So, does a 3D objet file look like this :

Idle Frame 1 mouvement animation Frame 2 mouvement animation Frame 3 mouvement animation

All of the above being big array containing vertices and texture coords ?

Thank you for the answer and explaning this thing to me !

# Answer
> 3 votes
There are two common ways to animate something.

One of them is what you described: morphs or per-vertex animation. You have number of different models representing each frame in your animation, and you interpolate the position of the vertices individually between the previous frame and the next to achieve smooth animation. This technique is usually applied in facial animation or other small details. (Interestingly, it also formed the entire basis of animation with Quake 2 and Quake 3's MD2 and MD3 model formats.)

The other technique is the far more common skeletal animation, where you have a single model in a reference pose, and a "skeleton" consisting of "bones" which the vertices inherit the transformation of, and which bone they move along with depends on which bones the vertices are assigned to using "weights" given to each vertex.

---
Tags: opengl, 3d, animation
---


# Question
Title: Can I use fonts under C:\Windows\Fonts for text in my game?
I'm using Unreal Engine and their UMG system which comes with only one font by default ("Roboto").

The engine allows importing new fonts so I'm wondering whether I can use the fonts already available with Windows 10 under C:\Windows\Fonts. I know I can't redistribute these fonts but does merely including text (which uses the font) in a game and distributing the game count as distributing the font? I mean it's not like the TTF file is being given away with the game in its raw form.

I've read these two related questions but I'm still not 100% sure so I thought I'd ask this forum.

Main menu fonts and logos are all I care about right now, so I could just create these as images in Photoshop and bring them into the engine (that sounds perfectly safe, right?)

All in all, I never imagined getting a nice looking font for one's game could be so time-consuming!

# Answer
Just because a font came with your OS and you paid for the OS you can not use it for anything if it is not free. You could set yourself up for a lawsuit.

Those fonts come under a Liberal license and if your game is targeted at Windows only then yes you can use the fonts. If you package your game for the 3ds or Vita and include windows fonts MS can sue you if they want to. Even if MS doesnt bite, you get those rogue lawyer guys that patrol the internet.

On the one font issue, the engine comes with one font because there are thousands of free fonts available all over the net.

You'd need a lawyer to go through the actual fonts license and tell you what is okay and what isnt. Or just save yourself the headches and go to https://www.google.com/fonts and use those.
> 2 votes

# Answer
This is explained on Microsoft's FAQ about font redistribution and licensing.

**tl;dr:** If you would like to distribute the font files with your game, you need a license from the copyright holder, and in many cases this isn't Microsoft because they licensed many fonts from other companies.

Most (but not all) fonts allow *embedding* under different conditions which vary from font to font. Some only allow it when the end-user can not edit any text which appears in that font ("*print and preview*"). You can check the license conditions and copyright holder of a TTF file by right-clicking on it and then going to `Properties -> Details` .

You are always free to *reference* the font in your game without including the font files. The caveat is of course that it will cause problems when the end-user doesn't have that font installed on their operating system.
> 2 votes

---
Tags: legal, unreal-4, fonts
---


# Question
Title: How to convert Triangle/OBB test to OBB/OBB test?
I'm using the collision library OZCollide and I want to do OBB vs. OBB collision tests. The problem is, that this function doesn't seem to exist but instead there is a AABB vs. OBB and a Triangle vs. OBB function. I'm not very comfortable with OBB intersections, but I think the necessary code is already there!

Can anyone help me by using this code for OBB/OBB Testing?

The code is here.

This code doesn't belong to me, It's Igor Kravtchenko's!

# Answer
You could convert one of the OBBs to an AABB by applying the inverse of the first OBBs transform to both OBBs.

Now the first OBBs is an AABB and the other is still an OBB, so you can use the AABB vs OBB function to test if they overlap.

If the collision function returns a normal/position, you must transform them by the fist OBBs transform to put them back into world space.
> 0 votes

---
Tags: c++, collision-detection, bounding-boxes
---


title: Collider Effeciency Question

text:
# Question
Title: Collider Effeciency Question
I'm creating a game where hundreds of rockets with colliders attached are shooting at a player. Should I write my script where:

1: The player script reads the collision from hundreds of rocket colliders or 2: Each rocket collider updates information when colliding with the player

Thanks!

# Answer
After a bit of thought but no testing, it depends on your rockets.

1. If the rockets are going to hit only the player then check on the script attached to the player and do everything there including destroying the rocket.
2. If your rockets are going to hit more than the player then it's best to let the rockets do the collision checks on the rocket and have it subract the health of the hit object.

I'l give you an example. I'm working on a game with swords. I had to do it a bit more complex but the sword has the script that gets the object collided with and tells the hit object to subtract its life.

In my case though, the info is sent to an Animation event for further checks.
> 1 votes

# Answer
After some consideration I'm completely changing my previous answer.

It would be more effective to implement a `OnCollisionEnter` method on the player that will do logic when a rocket hits him. That way less collision will have to be calculated and the physics engine will only have to keep track of the position of the rockets colliders and the rockets velocity. No need to do any checks or calculations on each of the hundreds of rocket objects.
> 1 votes

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


# Question
Title: How to increase the difficulty setting as close as possible to maximum difficulty automatically?
I have a simple 2D version of Mini-golf. The goal is to manage to clear each level in the least amount of shots, the ball is bouncing at most 3 times (stops on the 4th hit) from a wall but not reducing in speed, there is no out of bounds and no obstacles that would remove the ball. Now I would like to add some water/ instant death obstacle at the most annoying places.

**How do I find those places?**

The player can aim in a 360 radius, if I set the goal of managing a given level in 2 shots, there are 129,600 ways of how the player could shoot the ball. While it should be possible to simulate all of those shots fairly easy, I don't want to add randomly water and check if the level is still possible to clear, rather simulate the level, record all places the ball went over and place on the spots with the most hits water.

**What is the best strategy/ a good algorithm to blockade the most ways but to guaranty that at least one way stays clear?**

Does the strategy change significantly if moving obstacles (on a fixed path, same rule for bouncing as normal wall) are included?

# Answer
> 1 votes
You could approach the problem from the opposite direction:

1. Start with an empty level
2. Generate a random path with `n` puts, where each put consists of `m` reflection points (the higher the difficulty, the larger the values for `n` and `m`)
3. Generate an apropriate reflector at each of the reflection points.
4. Place some random obstacles on the direct lines between the start/end-points of the puts, but not on the path itself.

---
Tags: unity
---


title: Why can I not change a Sprite directly?

text:
# Question
Title: Why can I not change a Sprite directly?
I am changing the Sprites on an array of Images. I could think of two ways to go about it. The first way being:

```
var images = GetComponentsInChildren<Image>();
foreach(var image in images)
{
    if (!image.sprite)
    {
        image.sprite = GetMySprite();
    }
}

```

This way works perfectly. But if I try to grab the sprite itself like so:

```
var images = GetComponentsInChildren<Image>();
foreach(var image in images)
{
    var sprite = image.sprite;
    if (!sprite)
    {
        sprite = GetMySprite();
    }
}

```

It does not work. The Sprite gets assigned, but it is not the original Sprite. The Sprite attached to the Image remains null.

At first I thought, maybe Sprite is a struct? But it is not - it is a sealed class extending Object. (And I don't think that would necessarily explain it anyways).

So why must I retain the reference to the Image when changing its Sprite attribute?

Relative Documentation: Unity Image, Unity Sprite

# Answer
> 2 votes
Let's take a closer look at what's actually happening here step by step.

```
var sprite

```

You create a new variable `sprite` which doesn't point to anything yet.

```
sprite = image.sprite;

```

And in the same line you point the variable to the same object as a different variable `image.sprite` is pointing to.

```
sprite = obstacles[obstacleIndex].GetIcon();

```

Now you point `sprite` to a completely different sprite. But this doesn't do anything with the original variable `image.sprite` from which you obtained the original value of the variable `sprite`.

If you want this change to matter for the original source, you need to write the new value of `sprite` back to `image.sprite` by adding this line:

```
image.sprite = sprite;

```

# Answer
> 0 votes
`sprite` *is* changed!

But, that's not what you want. You want to change `image.sprite`. They are both different *references* to some `Sprite`.

You're creating a second reference and then changing the second reference, rather than the reference image has. So just change `image.sprite`, not `sprite`.

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


# Question
Title: How to load textures at other times than startup in XNA using vb.net?
I've encountered a problem with my game project lately. When I load more than a certain number of textures (around 1000) at startup I recieve an error regarding memory, because I have to use 32-bit in XNA. I am self-taught and so have only basic knowledge of the "correct" ways to program a game. The project itself is getting very big and although I try to compress images together etc, I will have to use more than 1000 textures throughout the project.

**My question is this**: How can I load textures at other points of time than at startup in XNA, using vb.net? (I'm not using classes at all that I'm aware of, so I hope to stay away from that if possible)

# Answer
First things first: You are free to call the ContentManager at any point in your game cycle (you're not restricted to the use the `LoadContent()` method created in the main class).

This doesn't solve your memory problem though, so on to part two:

If you run into memory issues because you have too much content loaded at the same time, you should only load the content that you actually need at that point in your game.

To free memory from loaded content, you can use `Content.Unload()` to release all content that the ContentManager holds. Note: `Texture2D.Dispose()` **does not free up memory** for Textures that are loaded via the ContentManager- as the ContentManager is in control of the lifetime of its content! (Sidenote: one *should* call `Dispose()` on content that is unmanaged -created without the ContentManager- though!)

A `Content.Unload()` releases **all** the content it contains so one might separate "generic" game content from "level specific" game content. Luckily you are able to create your own instance of the ContentManager so you can control what content is kept and what content is unloaded, like so:

C#:

```
ContentManager levelContentManager = new ContentManager( Game.Services, Content.RootDirectory );

```

or VB.Net

```
levelContentManager As New ContentManager(Content.ServiceProvider, Content.RootDirectory)

```

Now use:

```
levelContentManager.Unload()

```

when your level is completed and the level specific content is no longer used.

See also:

An example application would be in a game like Street Fighter (only used as example, Street Fighter wasn't build in XNA). The "Generic ContentManager" holds generic data: the titlescreen, the "Get Ready, Fight!" letters and healthbars. The other "level ContentManager" only loads the sprite info of the selected chars and level.

When the characters and level object are created, have those objects load their content via the "level ContentManager". When the fight is over and the game goes back to the title screen: the "level ContentManager" unloads to free up the resources.

When the players start a new fight, the "level ContentManager" is used again to load the now selected characters and level data and the cycle repeats.

This way, the memory only holds the content it is actually using.
> 0 votes

# Answer
So the answer seems a lot easier than I expected, if I'm doing it right at the moment(?).

I simply Load the content needed for all "Worlds" in the beginning of the game (in the Protected Overrides Sub LoadContent()) and then Dispose() and Load.Content() depending on what World is loaded later (in any Sub I choose):

```
TextureName = Content.Load(Of Texture2D)("")
TextureName.Dispose()

```

If there isn't any problem I'm not yet aware of, this seem to do the trick and does not leave me with the memory error in the start.
> 0 votes

---
Tags: xna, textures, vb.net
---


title: Unity NavMesh Step Issue

text:
# Question
Title: Unity NavMesh Step Issue
I have a scene in my game that takes place in a subway. I created a NavMesh so I can easily have the enemies chase the player. There seems to be a problem though as them enemies sometimes have a problem crossing the track. When looking at the NavMesh it appears that some parts of the track stick out above the NavMesh and I believe this is the reason the enemies sometimes have problems crossing the track. I have tried changing the step height up and down but that doesn't seem to change anything. What can I do to make the NavMesh cover the track in all spots so enemies can cross the track anywhere? Or is there maybe something else causing the enemies to not be able to cross the track in some spots?

**EDIT**

The rails and the ground are the same object and it is set as Navigation Static. Do they need to be 2 different objects for this to work?

# Answer
The Step Height setting is not affecting your enemies' pathing because the objects in question are not part of their navmesh, so they don't even recognize them as something they *could* path over.

You should be able to select the rails and mark them Navigation Static prior to baking your navmesh to include them in the baking process. Then you can step over them using Step Height.

---

Alternatively you could add Navigation Obstacle components to the rail, and your AI would attempt to walk around them. This likely isn't going to be the behavior you want though.
> 1 votes

---
Tags: unity, navmesh
---


# Question
Title: Whats a good way to make realistic brick walls?
This is a screencap from Blackops III:

I tried this using 5 maps including displace and normal, but it still looks too flat. I was wondering what a good method or workflow is to make walls actually look like theyre popping out, like what the steps are. For example, do people displace in their modeling software and import the mesh? I just want to hear the steps you guys of the community would take to produce this effect. Thanks.

My wall:

# Answer
Of course, it's possible to do this by just modelling all the bricks. That's likely to be prohibitively expensive for any non-trivial scene though.

Normal mapping is a very common starting point for this sort of effect. Normal mapping produces the appearance of ridges, bumps and other surface aberrations without the addition of extra triangles in the mesh (which are far more expensive, performance-wise). It works by encoding surface normals into a texture as RGB components, mapping that texture to a polygonal surface, and then using the sampled surface normals from the texture per-fragment to perform lighting, instead of the actual polygon surface normal (which doesn't vary as much over the surface like the normal map's encoded normals do).

There is a related technique called parallax mapping, which effectively does the same thing except does it by shifting texture coordinates around based on a function of the view angle relative to the surface normal and height map value for the surface as well. Parallax mapping can typically achieve great depth effects than normal mapping alone.

You can also modify normal mapping to support self-shadowing.

Both of these techniques -- and essentially all of the techniques that would be used to produce the scene you're envisioning *without* resorting to simply modelling all the bricks -- are about faking data related to light propagation and simulation.

What that means is that you *also* need a reasonable lighting model in your game (or modelling tool) to see truly excellent results, and some of these lighting models themselves involve significant investments in other techniques such as generating offline light probe information for computing diffuse bounces and global illumination.

Unless you spend fairly significant time and energy modifying your modelling tools to support exactly the same rendering pipeline as the game engine you're using, and supply the modeller with similar data, it's possible that the result in the modeller won't look the same (or as good) as the result in the real game. Keep that in mind when you're feeling potentially discouraged about the way your implementations look.
> 0 votes

---
Tags: textures, procedural-generation, effect
---


title: How to send an interface message?

text:
# Question
Title: How to send an interface message?
I come from Unreal, still using it. There, how it works is like this:
Let's say you as a player have a laser gun or something, and when shooting, you use raycast to see if you've shot anything, and if yes, you send an interface message (let's say Damage() function of IDamagable interface) to the hit result, if any.

Now, if the hit result implements that interface and has a Damage() function, it gets damaged. (And of course, if it doesn't implement the interface, nothing happens.)

But in Unity, I don't know how to send that interface message to the hit result (saying "if you have IDamagable implemented, call your Damage() function), but if it doesn't have it, that's fine either.

I've watched many videos on interfaces in Unity, but I still don't know how to achieve the same as in Unreal.

# Answer
> 5 votes
## Method 1 - Unity UI Event System

Thanks to Byte56 for pointing out that there's a new approach to messaging in Unity, which is much more similar to what the asker describes in Unreal.

> One quick heads-up: This approach is quite verbose compared to what I'm used to. If you just need a quick way to call a method on another object, without all the loosely-coupled robustness of the Event System, scroll down and I'll include some other options.

You'd start by creating a new C# script that defines an interface inheriting from `IEventSystemHandler`:

```
using UnityEngine.EventSystems;

public interface IDamagable : IEventSystemHandler
{
    void TakeDamage(DamageEventData damageData);
    void ToggleInvulnerability();
}

```

Each method you define in this interface becomes a message that you can send. If the message needs data, then we'll also need to define our data object by extending `BaseEventData`:

```
using UnityEngine.EventSystems;

public class DamageEventData : BaseEventData
{
    // This doesn't have to be in this scope, but I didn't want to create
    // yet another script file for it, so this seemed the most logical place
    public static readonly ExecuteEvents.EventFunction<IDamagable> takeDamageDelegate
    = delegate (IDamagable handler, BaseEventData data)
    {
        var casted = ExecuteEvents.ValidateEventData<DamageEventData>(data);
        handler.TakeDamage(casted);
    };

    public float damageAmount;

    public DamageEventData(EventSystem eventSystem,
                           float damageAmount,
                           ) : base(eventSystem)
    {
        this.damageAmount = damageAmount;
    }
}

```

What's up with that delegate? Since our interfaces can contain multiple methods, Unity's Event System uses a delegate to link up the right handler method and provide it the correct data type. You can do this inline, but having it defined statically somewhere is a bit friendlier to the garbage collector. (Example borrowed from this Event System walkthrough)

Next, ensure any script component you want to receive these messages implements your interface:

```
public Explodable : MonoBehaviour, IDamagable
{
      public Transform explosionPrefab;
      public float damageThreshold = 0.5f;

      public void TakeDamage(DamageEventData damageData)
      {
          if(damageData.damageAmount > damageThreshold)
          {
              Instantiate(explositionPrefab, transform.position, transform.rotation);
              Destroy(this);
          }
      }

      public void ToggleInvulnerability()
      {
          // No-Op: I declare by fiat that explodable objects are never invulnerable.
      }
}

```

Finally you can send this message to all scripts on a given GameObject that implement your interface:

```
if(Physics.Raycast(ray, out hit))
{
   DamageEventData data = new DamageEventData(
                                EventSystem.current,
                                damageAmount);

   ExecuteEvents.Execute<IDamagable>(
                                hit.transform.gameObject,
                                data,
                                DamageEventData.takeDamageDelegate);

   // If your message has no data - eg. the ToggleInvulnerability() method,
   // you can replace that delegate in the last argument with:
   // (handler, data) => handler.ToggleInvulnerability
}

```

Whew, that was a bit of a marathon. You can use other methods of the ExecuteEvents class to search the hierarchy for a recipient of the message, or broadcast a message up the hierarchy. The docs say you can also recursively send a message down the hierarchy, but I haven't found the method for that yet.

## Method 2 - Just grab the component you need

If your message/interface describes a type of behaviour that maps well to a single component, then you might as well make it a component and address it directly:

```
var damagable = targetObject.GetComponent<Damagable>();
if(damagable != null)
    damagable.TakeDamage(damageAmount);

```

Strictly speaking this is more tightly coupled - but for a lot of gameplay we don't need the industrial grade decoupling the Event System was introduced to handle (primarily for UI widgets). The separation of a Damagable component MonoBehaviour from the rest of an object/character's behaviour logic scripts already decouples it enough for our purposes, I would claim.

You can also do this with interfaces, if you have multiple components that care about the same kinds of messages:

```
var damagables = targetObject.GetComponents<IDamagable>();
foreach(var damagable in damagables)
    damagable.TakeDamage(damageAmount);

```

GetComponent has some performance cost, so try to cache these component references if you're using them frequently. For things that happen only a handful of times per frame though, it's still quite reasonable to use.

## Method 3 - Old SendMessage approach

This is how it worked in Unity 4 & earlier. Because the Event System in Method 1 is described as a replacement for this, don't expect this to stick around in future versions.

But if you just need something quick & dirty, it's hard to get moreso than this:

```
targetObject.SendMessage(
                       "TakeDamage",
                       damageAmount,
                       SendMessageOptions.DontRequireReceiver);

```

Then in your recipient scripts, you'd include a method with the *name* TakeDamage:

```
public void TakeDamage(float damageAmount)
{
    hp -= damageAmount;
    if(hp <= 0)
      Die();
}

```

Note that this method doesn't need to be `public` \- Unity calls it using reflection with the name you pass, no interfaces or anything - but I like marking it that way to remind myself that it's called externally.

Note that this reflection and string manipulation isn't all that cheap in terms of performance, so definitely don't use this for something that's running many times every frame. This approach also tends to obfuscate the call stack when debugging, and needs to be manually refactored if you ever change the names of your methods. For these reasons it's commonly considered an anti-pattern, so use it very cautiously if you use it at all.

---
Tags: unity, scripting, interface
---


# Question
Title: How can I generate 3D noise in chunks for terrain?
I'm trying to create a voxel engine that uses marching cubes to create smoothed terrain. I have most of it implemented, but I'm struggling with how I should create a noise function in three dimensions. I have a 2D Perlin noise generator implemented (or I could use the Unity built-in one, I guess). What can I use for 3D?

I'm also interested in the noise function being usable in chunks with uniform output. That way, with one seed, I could create a level in parts that would still all work properly.

# Answer
> -2 votes
Thanks to some of the above comments I did find my answer. I forgot to post my answer, but I thought I would go ahead and add it for anyone who is curious. I recommend looking at the original algorithm and also the above mentioned link to explain the general idea.

I chose to use three-dimensional Perlin Noise (by Ken Perlin originally). This is a smooth generated noise that can be visualized much like sin waves in 3D. The values vary slowly and the algorithm uses a seed to generate a permutation table. This table and an (X,Y,Z) coordinate is used to determine the noise value at a particular location. The pattern does repeat eventually, but seems to work well for a voxel engine. Since the computation is expensive, I recommend doing the computation on the GPU or limiting its use.

---
Tags: unity, 3d, terrain, perlin-noise
---


title: Finding holes in mesh

text:
# Question
Title: Finding holes in mesh
I have a mesh that has holes. I found a paper, An Automatic Hole-Filling Algorithm for Polygon Meshes

It details an algorithm that uses a k-d tree for finding holes (from a manifold triangle mesh). The steps are as follows:

> Step1: Compute the center of each triangle and the correspondences between the center and three vertexes of the triangle;
>
> Step2: Set up the Kd-tree according the centers of triangles;
>
> Step3: Search the Kd-tree and check up the topological connectivity of the corresponding edges, and find the boundary edges;
>
> Step4: Distinguish the different boundary loops according to the topological connectivity of vertexes;

I do not not understand how this algorithm actually finds the hole, can some please explain this in Layman's terms so that I can implement it --- I know there are probably better way out there of finding holes but I need to understand this particular algorithm.

Please help

# Answer
I took a glance at the paper and it was very vaguely written (even for academic papers).

If you check the papers that cited them, they only used the paper as reference for their filling algorithm and not their "novel" hole-detecting algorithm.

It raises questions like:

---

What is k?

What is the center? (there are different centers, like the circumcenter \[what I'm thinking they used\] in Delaunay's algorithm for meshing)

What topological connectivity?

---

What is the reason you want to understand that specific algorithm? (I wrote this as an answer since it's nicer to write haha)

EDIT:

If we know the adjacency matrix of the mesh, the solution is trivial (check for triangles (quads) with less than 3 (4) edge connections)

Otherwise, we would normally check every edge with every other edge O(n^2) with n triangles (meshes)

If we wanted a kd-tree implementation, we would get anywhere from O(nlog(n)) to O(n^2) since it's not too easy to implement self-balancing kd-trees.

Let's assume we have a kd-tree implementation done.

We get the circumcenters of all triangles (quads) and place them in a kd-tree. If the distance between two centers is less than the sum of the two corresponding radii that come from the circumscribed circles, they are possible connected triangles (quads).

That's all I got, maybe someone else can give deeper insight in this problem.
> 3 votes

# Answer
I don't know about using a KD Tree for this but to find holes in a triangular mesh you must find all the border edges of the mesh which belong only to one triangle.

One algorithm would be to iterate over every edge of the mesh and maintain a set of border edges. For every edge, if the edge is not in the set, then add it. If the edge is already in the set, then remove it. Once you have iterated over all of your edges this set will contain all the border edges of your mesh.

You can then start with any border edge and add neighboring border edges to it until you make your way back to the first border edge. You just found a hole. Repeat this until no more border edges are left and you've found all the holes.
> 0 votes

---
Tags: graphics, 3d-meshes
---


# Question
Title: XNA realistic water: How to clip along a mesh instead of a plane
I hope you can help me with the following problem:

I'm developing a 3d game (in XNA) with an ocean. I want it to look semi-realistic. So far, I'm rendering 4 things:

* The ocean floor (terrain) on the view matrix (refraction)
* The terrain above water on the mirrored view matrix (reflection)
* The terrain above water on the view matrix (actual terrain)
* The water, which is simply a plane, using the refraction and reflection rendertargets, the fresnel term, and a normal map to give the impression of small waves.

Instead of a flat plane, I want to render the water on a mesh, to get some actual waves going. This is where I've been stuck for a while now. It's quite simple to clip the terrain along that plane, but is it possible to clip a mesh along another mesh? Or am I going about this the wrong way?

# Answer
Honeybunch supplied quite a bit of information on creating waves. It's something I can definitely use, but not exactly what I was looking for. I'm posting an answer to my own question because I figured out how to do it. For future reference:

Before rendering anything, I render the water to a rendertarget (let's call it RT\_WaterHeight) using a custom shader. The height of the water determines the output color. Let's say my base water level is at 15 units high, and my haves have a maximum amplitude of 5. That means at any point, the height of the water is between 10 and 20. The custom pixel shader calculates this (It's probably better performance-wise to precalculate a multiplier and pass that into the shader as an argument). and renders everything from black to white. 10 = black. 20 = white.

Then, with everything I render, I determine if it's above or below water by comparing its height to the same pixel on RT\_WaterHeight. Everything is drawn using custom shaders, so in the pixel shader I can call "discard" if it shouldn't be drawn.

EDIT: This is what I used to do. It results in strange artefacting when looking at a terrain with the camera just above the water. Instead of rendering everything to a target and using that in the terrain shader.... I just sample the water's height map in the terrain shader.
> 1 votes

# Answer
Wave generation isn't a simple task.

The easy way is expensive. Right now you're rendering your water as a plane, why not just render all of your textures onto a more complex mesh? You could, with an algorithm, take your water plane and re-buffer it to take on a new shape every frame. It's messy and very intensive but it can work.

Here are some resources for the FFT wave generation algorithm:

https://developer.nvidia.com/sites/default/files/akamai/gamedev/files/sdk/11/OceanCS\_Slides.pdf

http://www.edxgraphics.com/blog/simulating-ocean-waves-with-fft-on-gpu

Of course these resources (and many others) are using geometry/compute shaders on the GPU. The GPU can do all this re-buffering MUCH faster than the CPU but XNA is built over DX9 and only DX11 and up supports geometry shaders. Monogame has plans to support geometry shaders but it's not there yet.

If you use an algorithm that's less intensive than FFT like basic sin wave generation it might be less harsh on your CPU cycles. Here's a report on wave generation using DX9 (no geometry shaders) http://www.jamesgamlin.com/oceanwaves%20report.pdf
> 1 votes

# Answer
I would use a bump map - a texture of the waves, and then use some shader magic to make it *look like* there are waves. This is relatively cheap compared to creating custom meshes. The downside is that there are some edge artifacts and you need to make sure to resize all your render targets when you resize the viewport.

There's a Riemers page on this:

http://www.riemers.net/eng/Tutorials/XNA/Csharp/Series4/Moving\_water.php

The situation you described is very similar to what they are making there and should integrate into your water plane easily.
> -1 votes

---
Tags: xna, water, waves
---


# Question
Title: How do I implement a retro-style password-based "savegame" system?
How would I make a password system for a single-player game like the ones used in older console games?

For example, *Mega Man X* saves work by giving you a series of numbers that you can enter later to load your save.

# Answer
First, break down your game state (or rather, the aspects of the state you want to save). In the case of a Mega Man style game, you might track which of the end-level bosses you've killed, the number of energy-tank-like powerups you have, and so on.

Pack all of that data into a bit field, that is, assign an appropriate number of bits to each value:

* Killed boss 1 (one bit)
* Killed boss 2 (one bit)
* Killed boss 3 (one bit)
* Killed boss 4 (one bit)
* Energy tanks (*x* of 5 total) (3 bits)
* Unlocked some achievement (one bit)

Our example has 8 bits total, which means a single character can represent a password. In practice, your game is likely to have more state and thus require more total bits and thus more characters. As noted in the comments here and elsewhere in this question, this approach works for "retro" games or other games where the size of the captured game state is reasonable. Beyond a certain point, you may discover that the complexity of the passwords necessary to encode your state is too large.

To decrease the likelyhood of casual observation cracking the password, you can transform the bit layout so that you introduce dummy bits (which have no effect on the game state but which make the password look different when you interpret all the bits as characters) or run it through some reversible hash-like operation to scramble the bits around so that all the "killed box *X*" bits are not right next to eachother, making corresponding sequential-state passwords look very different, or introduce checksum values.

If you dig around, there's a fair bit of information on the systems employed for some of the more-popular passworded games out there:

You could read up on those for additional inspiration.
> 33 votes

# Answer
Those games did only save a state I believe. The password just references a level to load. Just use a dictionary for something like this.

If it is a little bit more complex like having a certain weapon or booster you can encrypt the state to a short (but long enough) hash code.

But I strongly advice you to not use this. Password will spread fast on the Internet and soon everyone had won your game.
> 3 votes

# Answer
Well you could basically do it this way:

Bosses killed = 7

Amount of coins = 36

Owns Sword = 0(No)

Owns Heart = 1(Yes)

Current Level = 6

Current World = 9

Health = 100

Code = 7V36R0A1T6O9A100

Basically every letter separate The Types
> 2 votes

# Answer
While solutions like *Josh Petrie's* character-to-state system have benefits (small save size, works on all copies of the game), they couple the games design and state system to be intrinsically to the password system. Any change to the password or state or design and the entire system falls apart.

A far simpler solution would be to build your save system as per normal, and simply add a password system over the top. This can be as simple as saving the password in the save (possibly doubling as file name) and validating it on load, or as complex as using one of the many encryption libraries around (which is pretty trivial).

---

There seems to be some confusion around this answer.

1) The op has simply asked for a password that let's them load a save... there is no requirement that the password *be* the save.

2) Many games today have significant save storage requirement, we just built a quick save/load system internally that was producing 10MB files... for a quiz game! *Josh Petrie's* save system, while valid is very limited - as soon as the store system becomes non-trivial the passwords would have to be of enormous length to persist all pertinent data.

For example, what happens if there are 30 bosses? 20 achievements? Are we halfway through an achievement? What level is he at? How many bits are we putting aside for health, lives, coins, xp? What if the snapshot is not of state between levels... but half-way through a level - the positions of the player, enemies, projectiles, destructed/altered terrain suddenly add up to a lot of state that needs to be stored.

For perspective, assuming a 30 character alphabet and a ten letter password we have roughly 50 bits worth of information to store. It's not uncommon to see a game/engine use up to 320 bits just to store a single object's position, rotation and scaling. Sure, you can do all kinds of optimisation tricks to do more with less... but ultimately you're using up the time dedicated to making the game fun - one of the worst optimisations you can make.
> -3 votes

---
Tags: savegame
---


# Question
Title: Quaternion not giving correct value back. What am I doing wrong here?
Right so I made a quaternion and assigned it a value but it reports back the wrong value.

Here is the relevant code...

```
Quaternion LeftTurnLimit = Quaternion.identity;
float test = 0.1f;

LeftTurnLimit = Quaternion.Euler(test, 0, 0);
Debug.Log(LeftTurnLimit);

```

Expected result: (0.1, 0, 0) / (x, y, z) Result: (0.0, 0.0, 0.0, 1.0) / (x, y, z, w)

So what am I doing wrong here?

# Answer
**Rounding**.

If you attach the debugger and look at the values of your quaternion:

You'll see that the values are just too small to be displayed with one tenth precision, as the debug value is displayed.

You can confirm this by looking at:

```
Debug.Log(LeftTurnLimit.eulerAngles);

```

This will output the initial value you put in : 0.1, 0, 0

**To address the differences in what you expected, vs what you got out.**

Quaternions and euler angles are different, but with a similar goal. They're different ways of representing rotations in 3D space. They may have some commonly named components, but they store different information, because the process for converting the data stored into a rotation are different. If you want specifics about how each of them work, you should research the one you're interested in. You can ask specifically about anything you don't understand in a new question, after researching.
> 3 votes

# Answer
Quaternions are different than Euler angles; Euler angles has 3 components (x, y, z) while Quaternions has 4 (x, y, z, w). If you want your result in Euler angles, use following code piece:

```
Quaternion LeftTurnLimit = Quaternion.identity;
float test = 0.1f;

LeftTurnLimit = Quaternion.Euler(test, 0, 0);
var LeftTurnLimitEuler = LeftTurnLimit.eulerAngles;
Debug.Log(LeftTurnLimitEuler);

```

Here is the related API page: http://docs.unity3d.com/ScriptReference/Quaternion-eulerAngles.html
> 0 votes

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


# Question
Title: Unity3D: Entering a trigger disables a few bools for no reason
I'm trying to make it so when an object enters a collider with the tag "Down" a single boolean turns false, but the problem is that more than one booleans(*canGoUp, canGoLeft, canGoRight*) are turning false for no reason, here's my code.

```
void OnTriggerEnter(Collider col)
    {
        if(col.gameObject.tag == "Up")
        {
            canGoUp = false;
        }
        if (col.gameObject.tag == "Down")
        {
            canGoDown = false;
        }
        if (col.gameObject.tag == "Left")
        {
            canGoLeft = false;
        }
        if (col.gameObject.tag == "Right")
        {
            canGoRight = false;
        }

    }

    void OnTriggerExit(Collider col)
    {
        if (col.gameObject.tag == "Up")
        {
            canGoUp = true;
        }
        if (col.gameObject.tag == "Down")
        {
            canGoDown = true;
        }
        if (col.gameObject.tag == "Left")
        {
            canGoLeft = true;
        }
        if (col.gameObject.tag == "Right")
        {
            canGoRight = true;
        }
    }

```

The other parts of the script work well, but not the "Down" one, here are two objects compared to each other:

# Answer
Apparently there were a few more objects with those tags which were colliding with the object and that's why this "bug" appeared. Deleted those objects and fixed it.
> 0 votes

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


# Question
Title: How to compute a transformation matrix that describes each position and rotation on a sphere?
I am having an issue constructing my transformation matrices, for this sphere problem.

I know the 3d coordinate of the center, and the radius of, the sphere.

Since I know the radius and center of the sphere, it's easy to compute all positions on the sphere, but I'm not sure how I should compute the rotation matrix?

Each point has to be rotated such that it points toward the object, and the only thing that tells me the orientation of the vector is the difference between the 3d point on sphere and the 3d point of the object.. But one vector doesn't seem enough to construct a whole rotation matrix?...

Could I extract a rotation matrix, that "tells" the point how it should be rotated to look at the object?

# Answer
Indeed, you need an additional *orientation* hint for this to work.

It is quite common to use an “up” vector in addition to the view vector that you computed. Most 3D libraries have some kind of “lookat” function: `Transform.LookAt` in Unity3D, `glm::lookAt` in glm, or the deprecated `gluLookAt` in ancient OpenGL.

Note that if the “up” vector is constant or only depends on the position, you will have discontinuities in the resulting transformation. This is mathematically unavoidable. One possibility is to use *e.g.* `(0,0,1)` as a constant “up” vector, and just disallow the viewer from being exactly in `(0,0,1)` or `(0,0,-1)`.
> 0 votes

---
Tags: rotation, matrix, transformation
---


# Question
Title: Select motion path from curve in Maya Python
I need to obtain the motion path attached to a curve in maya using Python. This is the situation as shown in the editor:

I want to obtain **motionPath1** by calling a method on **curve3** since they look like they are related.

However, I have tried pleny of list methods (listAttr, listHierarchy, etc) but they only return the **curveShape3**.

What is the command, if it exists at all, to get the name of the motion path in Python knowing the object **curve3**?

# Answer
> 1 votes
You need to get motion path node name from curve shape.

```
import maya.cmds as cmd
shape = cmd.listRelatives( 'curve3' )
mPath = cmd.listConnections( shape, type = 'motionPath')
print mPath

```

---
Tags: python, maya
---


title: OpenGL perspective matrix far plane

text:
# Question
Title: OpenGL perspective matrix far plane
The near plane clips at exactly the value I set just fine but instead of clipping at 1000 the far plane clips at 1.

Here is the code for the projection matrix:

```
public static Matrix4f perspective(Matrix4f dest, float fov, float aspectRatio, float near, float far) {
    if (dest == null)
        dest = new Matrix4f();

    float tanHalfFOV = (float) Math.tan(fov / 2);
    float range = near - far;

    dest.m00 = 1.0f / (tanHalfFOV * aspectRatio);
    dest.m10 = 0;
    dest.m20 = 0;
    dest.m30 = 0;
    dest.m01 = 0;
    dest.m11 = 1.0f / tanHalfFOV;
    dest.m21 = 0;
    dest.m31 = 0;
    dest.m02 = 0;
    dest.m12 = 0;
    dest.m22 = (-near - far) / range;
    dest.m32 = 2 * far * near / range;
    dest.m03 = 0;
    dest.m13 = 0;
    dest.m23 = 1;
    dest.m33 = 0;

    return dest;
}

```

The near plane is 0.1 and the far plane is supposed to be 1000.

# Answer
Your whole matrix is incorrect. For example, this is one of the ways it should look like:

So, in code:

```
dest.m00 = 1.0f / (tanHalfFOV * aspectRatio);
dest.m10 = 0;
dest.m20 = 0;
dest.m30 = 0;
dest.m01 = 0;
dest.m11 = 1.0f / tanHalfFOV;
dest.m21 = 0;
dest.m31 = 0;
dest.m02 = 0;
dest.m12 = 0;
dest.m22 = -(far + near) / range;
dest.m32 = -2 * far * near / range;
dest.m03 = 0;
dest.m13 = 0;
dest.m23 = -1;
dest.m33 = 0;

```

And you calculate range the wrong way, it needs to be far - near, not near - far.
> 1 votes

# Answer
As far as I can tell by comparing to GLM perspective matrix implementation, your range is computed negative and you are missing some negative signs. Below are the corrections.

```
float range = far - near;
...
dest.m32 = - 2 * far * near / range;
dest.m23 = - 1;

```

Check it out on their git. I am not sure just which matrix you need, this answer is for the RH one. Check the link for other implementations.
> 0 votes

---
Tags: opengl, java, matrix, perspective
---


# Question
Title: How do I flip Player in 2D Touch Movement?
How do i flip my Player in 2D when i got touch movement? I got Buttons to move but how do I flip the player now if i walk to the right cause my player faces to the left..?

here is my Player Script:

```
using System.Collections;

public class PlayerController : MonoBehaviour {

    public float speed = 10, jumpVelocity =  10;
    public LayerMask playerMask;
    public bool canMoveInAir = true;
    Transform myTrans, tagGround;
    Rigidbody2D myBody;
    bool isGrounded = false;

    // Use this for initialization
    void Start ()
    {
        myBody = this.GetComponent<Rigidbody2D>();
        myTrans = this.transform;
        tagGround = GameObject.Find (this.name + "/tag_ground").transform;
    }

    // Update is called once per frame
    void FixedUpdate ()
    {
        isGrounded = Physics2D.Linecast (myTrans.position, tagGround.position, playerMask);

        #if UNITY_ANDROID && !UNITY_IPHONE && !UNITY_BLACKBERRY && !UNITY_WINRT
        Move(Input.GetAxisRaw("Horizontal"));
        if(Input.GetButtonDown("Jump"))
           Jump();
        #endif
    }

    public void Move(float horizontalInput)
    {
        //Er klebt nicht mehr an den Waenden
        if (!canMoveInAir && !isGrounded)
            return;

        Vector2 moveVel = myBody.velocity;
        moveVel.x = horizontalInput * speed;
        myBody.velocity = moveVel;

    }

    public void Jump()
    {
        if(isGrounded)
            myBody.velocity += jumpVelocity * Vector2.up;
    }

}

```

# Answer
Flipping object through can be done through scaling. If you set scale to -1 in X then it'd be flipped in X axis, similar for other axes.

You can just use your `horizontalInput` to determine if you are going left or right, and obviously if your `horizontalInput` is negative then your going left and vice versa.

```
public void Move(float horizontalInput)
{
    ...
    // Here is the flipping stuff
    if (horizontalInput != 0)
    {
        Vector3 flip = Vector3.right * horizontalInput * myTrans.localScale.x;
        myTrans.localScale = flip;
    }
}

```

As you taking `horizontalInput` with `Input.GetAxisRaw` means with no smoothing filter so I did multiply it directly, but if you change it whenever then you have to make some change in code also, what you have to do is just change

```
Vector3 flip = Vector3.right * horizontalInput * myTrans.localScale.x;

```

## To

```
Vector3 flip = (Vector3.right * horizontalInput).normalized * myTrans.localScale.x;

```
> 1 votes

# Answer
You can simply do `GetComponent<SpriteRenderer>().flipX = true;`
> 0 votes

# Answer
**Disclaimer: as Valryon said, this is not the right way to do that anymore.**

Your Question is not clear, but I think what you want to do is flip the entire GameObject.
To do this, simply do `myTrans.localScale *= -1` when the player changes direction.

You can also do something like this:

```
if(horizontalInput <  0)
    myTrans.localScale = new Vector2(1, 1, 1)
if(horizontalInput >  0)
    myTrans.localScale = new Vector2(-1, -1, -1)

```

at the end of the Move(float horizontalInput) function.
> -1 votes

---
Tags: 2d, movement, unity
---


# Question
Title: Why is my A* Pathfinding incredibly slow?
I'm trying to use A\* to make my enemies move about, but it takes up to 20 seconds to get a path to walk.

My grid is only 64\*64.

This is my code:

```
 #include "AStar.h"
#include "Node.h"
#include "EntityManager.h"
#include <algorithm>
#include <iostream>
#include <unordered_set>
#include <queue>

using namespace Dotmk_AI;
using namespace Dotmk_Managers;

AStar::AStar()
{

}

std::vector<Node*> AStar::GeneratePath(Node* start, Node* goal)
{
    std::vector<std::vector<Node*>>* pNodeMap = EntityManager::GetAStar()->GetNodeMap();

    std::vector<Node*> openSet;
    std::unordered_set<Node*> closedSet;

    make_heap(openSet.begin(), openSet.end());

    start->g = 0;

    openSet.push_back(start);
    push_heap(openSet.begin(), openSet.end());
    while (openSet.size() > 0)
    {
        Node* currentNode = openSet[0];
        for (int i = 0; i < openSet.size(); ++i)
        {
            if (openSet[0]->f < currentNode->f || openSet[0]->f == currentNode->f && openSet[0]->h < currentNode->h)
            {
                currentNode = openSet[i];
            }
        }

        Remove(&openSet, currentNode);
        closedSet.insert(currentNode);

        if (currentNode->x == goal->x && currentNode->y == goal->y)
        {
            goal->parent = currentNode->parent;
            break;
        }

        for (Node* neighbour : GetNeighbours(currentNode, pNodeMap))
        {
            if (neighbour != nullptr)
            {
                if (Contains(closedSet, neighbour) || neighbour->e == 0) continue;

                int newMovementCostToNeighbour = currentNode->g + GetDistance(currentNode, neighbour);
                if (newMovementCostToNeighbour < neighbour->g || !Contains(openSet, neighbour))
                {
                    neighbour->g = newMovementCostToNeighbour;
                    neighbour->h = GetDistance(neighbour, goal);
                    neighbour->f = neighbour->g + neighbour->h;
                    neighbour->parent = currentNode;

                    if (!Contains(openSet, neighbour)) openSet.push_back(neighbour);
                }
            }
        }
    }
    std::vector<Node*> nodes;
    Node* current = goal;
    while (current != nullptr)
    {
        nodes.push_back(current);
        current = current->parent;
    }
    reverse(nodes.begin(), nodes.end());
    nodes.pop_back();
    std::cout << nodes.size() << std::endl;

    return nodes;
}

int AStar::GetDistance(Node* nodeA, Node* nodeB)
{
    int distX = abs(nodeA->x - nodeB->x);
    int distY = abs(nodeA->y - nodeB->y);

    return 1 * (distX * distX + distY * distY);
}

std::vector<Node*> AStar::GetNeighbours(Node* _pNode, std::vector<std::vector<Node*>>* _pNodeMap)
{
    std::vector<Node*> neighbours;
    neighbours.reserve(8);
    for (int x = -1; x <= 1; ++x)
    {
        for (int y = -1; y <= 1; ++y)
        {
            if (x == 0 && y == 0) continue;

            int checkX = _pNode->x + x;
            int checkY = _pNode->y + y;

            if (checkX >= 0 && checkX < 64 && checkY >= 0 && checkY < 64)
            {
                neighbours.push_back((*_pNodeMap)[checkX][checkY]);
            }
        }
    }
    return neighbours;
}

bool AStar::Contains(std::vector<Node*> _pVector, Node* _pNode)
{
    return find(_pVector.begin(), _pVector.end(), _pNode) != _pVector.end();
}

bool AStar::Contains(std::unordered_set<Node*> _pVector, Node* _pNode)
{
    return find(_pVector.begin(), _pVector.end(), _pNode) != _pVector.end();
}

void AStar::Remove(std::vector<Node*>* _pVector, Node* _pNode)
{
    int pos = find(_pVector->begin(), _pVector->end(), _pNode) - _pVector->begin();
    auto it = _pVector->begin() + pos;
    rotate(it, it + 1, _pVector->end());
    _pVector->pop_back();
}

```

and this is my node class

```
class Node
{
public:
    Node(int _x, int _y, int _e);
    ~Node();

    std::vector<Node*> neighbors;
    Node* parent;
    int f, g, h, x, y, e, penalty;
};

```

Is there anything I'm doing wrong?

EDIT: Setting it on Release mode will make the pathfinding ALMOST instant, but still noticable. I've taken much of your guys advice and improved the code.

# Answer
The problem was this:

```
bool AStar::Contains(std::vector<Node*> _pVector, Node* _pNode)
{
    return find(_pVector.begin(), _pVector.end(), _pNode) != _pVector.end();
}

```

It made a copy of the vector every single time it was called, wich made it incredibly slow. Making it a pointer to the vector increased the time from about 30 Seconds to only about 6 Ms.

After implementing a custom heap like structure, it is now only 1 Ms or even 0 Ms at certain times.

Like Trevor Powell also said, the problem was also rooted in running the game in Debug mode, wich made it way worse.
> 2 votes

# Answer
I see a few issues.

1. you are doing a lot of linear scans over vectors (at least 2 for each neighbour for each node you examine). This will be pretty slow. You don't even need the closed set if you just have a `bool isClosed` in the Node.
2. You should sort the openset or make the openSet a min heap of some description. This will make the search for the next node a lot faster.
3. erase will move all nodes in the vector up one which is again a linear scan. Instead it's cheaper to just swap the node with the last one and pop\_back (at least when not keeping it sorted). When using a proper min heap that operation will become a O(log n) operation.

Finally if all enemies are going to the same goal (like the player) then you can simply flood fill the entire arena once (making the `parent` field point to the next node) and use that for pathing.
> 7 votes

# Answer
Since performance is the most important thing - I would rewrite this to use arrays rather than standard library containers. The problem with using data structures designed and developed by someone else is that if you don't understand how they're implemented you'll very easily end up performing millions of unnecessary operations - including memory allocation and deallocation - without noticing anything except the performance hit when running the code with a large number of nodes.

There's only one quick win I can see which would be to make the following change to your GetNeighbours function:

```
std::vector<Node*> AStar::GetNeighbours(Node* _pNode, std::vector<std::vector<Node*>>* _pNodeMap)
{
    std::vector<Node*> neighbours;
    neighbours.reserve(8);
    // Keep a count of the number of Neighbours found
    int neighboursFound = 0;
    for (int x = -1; x <= 1; ++x)
    {
        for (int y = -1; y <= 1; ++y)
        {
            if (x == 0 && y == 0) continue;

            int checkX = _pNode->x + x;
            int checkY = _pNode->y + y;

            if (checkX >= 0 && checkX < 64 && checkY >= 0 && checkY < 64)
            {
                neighbours.push_back((*_pNodeMap)[checkX][checkY]);
                // Return early from the function once all the neighbours are found
                if(++neighboursFound == 8) {return neighbours;}
            }
        }
    }
    return neighbours;
}

```

Now the other thing I vaguely remembered (then a quick bit of reading confirmed) about standard library containers is that using the push\_heap and make\_heap functions will call the less than '\<' operator for your node class. I'm not sure if you have that defined somewhere else and haven't included it, and I also don't know what happens if you use it but haven't defined it, but I have an inkling that all of your code relating to using a heap may actually not be doing anything useful without it.

If it doesn't sort your open set the way you think it does, then that would mean that at every step of the way each node would be compared to all of the nodes around it - if they were closer than the node being considered they'd eventually be processed in the order they were added. So if your nodes where on opposite sides of the grid it would consider most of the nodes rather than only the potential shortest path.

The test to see if I'm right would be to add an overloaded less than operator which I think is something like the following (I haven't done OO C++ for a while) to your Node class.

```
bool Node::operator<(const Node& a, const Node& b) {
    return a.h < b.h;
}

```
> 3 votes

# Answer
> EDIT: Setting it on Release mode will make the pathfinding ALMOST instant

This is probably the key piece of information.

Although you don't say so, your problem is presumably that you're using the STL in a debug build in something being compiled within Visual Studio.

Visual Studio's implementation of the STL is notoriously (and catastrophically) slow in debug builds, and double-particularly for the creation and copying of templated container classes.

One thing you can do to vastly improve STL performance in debug builds in Visual Studio is to turn off your program's usage of the debug heap, which you can do by setting `_NO_DEBUG_HEAP=1` in your project's environment variables. (more details on the Microsoft MSDN blog)

Some folks report speed improvements from disabling STL iterator sanity checking (by adding `#define _SECURE_SCL 0` to a prefix file), but I've never found this to make a notable difference in my projects, whereas disabling use of the debug heap makes all the difference in the world.

Alternately, you can always switch to using an alternate implementation of STL, instead of the one provided by Microsoft. EASTL is apparently popular, and doesn't suffer from the same performance problems as Microsoft's default implementation. I've not used EASTL myself, but I've heard other people say nice things about it, so it might well be another option.
> 1 votes

---
Tags: c++, performance, path-finding
---