Jump to content
  • Advertisement
Sign in to follow this  
ChristianFrantz

Optimization of a method

This topic is 2100 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

The method below works fine for what I want to accomplish. The problem with it is that it is way too slow so I'm hoping that someone can help me out with it. Without the method, the game loads almost immediately but with the method, it takes 2 or 3 minutes for the window to even open.

 private void CheckAdjacentCubes(List<Cube> cubes, List<Cube> cubeToDraw)
        {
            //cubes is main list of cubes
            //cubeToDraw is the list of cubes to draw after adjacency check

            foreach (Cube cube in cubes)
            {
                foreach (Cube adjacentCube in cubes)
                {
                    if (cube.World.Translation.Z + 0.5f == adjacentCube.World.Translation.Z - 0.5f)
                    {
                        backSide = true;
                    }
                    if (cube.World.Translation.Z - 0.5f == adjacentCube.World.Translation.Z + 0.5f)
                    {
                        frontSide = true;
                    }
                    if (cube.World.Translation.X + 0.5f == adjacentCube.World.Translation.X - 0.5f)
                    {
                        rightSide = true;
                    }
                    if (cube.World.Translation.X - 0.5f == adjacentCube.World.Translation.X + 0.5f)
                    {
                        leftSide = true;
                    }
                    if (cube.World.Translation.Y + 0.5f == adjacentCube.World.Translation.Y - 0.5f)
                    {
                        topSide = true;
                    }
                    if (cube.World.Translation.Y - 0.5f == adjacentCube.World.Translation.Y + 0.5f)
                    {
                        bottomSide = true;
                    }
                }

                if (bottomSide != true || topSide != true || leftSide != true || rightSide != true || frontSide != true || backSide != true)
                {
                    cubeToDraw.Add(cube);
                }

                bottomSide = false;
                topSide = false;
                leftSide = false;
                rightSide = false;
                frontSide = false;
                backSide = false;
            }
        }

I'm assuming it's because I'm looping through every single cube in the list, and with a 20x20x10 chunk that'll take a while. Any thoughts on what I could do differently?

Share this post


Link to post
Share on other sites
Advertisement
For one, I’ve heard that “foreach” is extremely slow.

For another, you are checking every single side of the cube even though it will get added to the list if any sides are not touching. In other words, there is no reason to continue checking sides as soon as a single side is found not to be touching.
 
 private void CheckAdjacentCubes(List<Cube> cubes, List<Cube> cubeToDraw)
        {
            //cubes is main list of cubes
            //cubeToDraw is the list of cubes to draw after adjacency check

            foreach (Cube cube in cubes)
            {
                foreach (Cube adjacentCube in cubes)
                {
                    if (cube.World.Translation.Z + 0.5f != adjacentCube.World.Translation.Z - 0.5f)
                    {
                        cubeToDraw.Add(cube);
			break;
                    }
                    if (cube.World.Translation.Z - 0.5f != adjacentCube.World.Translation.Z + 0.5f)
                    {
                        cubeToDraw.Add(cube);
			break;
                    }
                    if (cube.World.Translation.X + 0.5f != adjacentCube.World.Translation.X - 0.5f)
                    {
                        cubeToDraw.Add(cube);
			break;
                    }
                    if (cube.World.Translation.X - 0.5f != adjacentCube.World.Translation.X + 0.5f)
                    {
                        cubeToDraw.Add(cube);
			break;
                    }
                    if (cube.World.Translation.Y + 0.5f != adjacentCube.World.Translation.Y - 0.5f)
                    {
                        cubeToDraw.Add(cube);
			break;
                    }
                    if (cube.World.Translation.Y - 0.5f != adjacentCube.World.Translation.Y + 0.5f)
                    {
                        cubeToDraw.Add(cube);
			break;
                    }
                }
            }
        }

L. Spiro Edited by L. Spiro

Share this post


Link to post
Share on other sites

You could implement the voxel storage as a tree, each leaf is connected another leaf, only if that block is adjacent. Then when you add or remove block dynamic you could just go the the leaf where the near block is at and attach it or just add a new leaf if it doesn't have adjacent blocks. You could also use divide and conquer and divide those chunks in small pieces and calculate them parallel. The method it self can be optimized if you pre-cache the position

 

if (cube.World.Translation.Z + 0.5f != adjacentCube.World.Translation.Z - 0.5f)
{
  cubeToDraw.Add(cube);
  break;
}
if (cube.World.Translation.Z - 0.5f != adjacentCube.World.Translation.Z + 0.5f)
{
  cubeToDraw.Add(cube);
  break;
}
auto bZ1 = cube.World.Translation.Z - 0.5f;
auto bZ2 = cube.World.Translation.Z + 0.5f;
auto cZ1 = adjacentCube.World.Translation.Z - 0.5f;
auto cZ2 = adjacentCube.World.Translation.Z + 0.5f;

if (bZ1 != cZ2 || bZ2 != cZ1 || ....)
    cubeToDraw.add(cube)

But like Batterius said, its the design rather than the method.

Edited by Wolftein

Share this post


Link to post
Share on other sites

Well i went with the 3d array after researching octrees for a bit because they confused me. I understand how they work, but I still have a few questions about them. Is the whole map a giant octree, or do I need one for each chunk? And even with an octree, I'm not quite sure how to use it to check for adjacency of my cubes. I haven't put any into action yet, but I figure I'll give it a shot today.

 

Anywho, the following bit of code doesn't work and I don't know why. The CubesToDraw list has no values in it at all. This is my attempt at using a 3d array :P

 private void CheckAdjacentCubesArray(Cube[, ,] cubes)
        {
            for (int x = 1; x < chunkWidth - 1; x++)
            {
                for (int y = 1; y < chunkHeight - 1; y++)
                {
                    for (int z = 1; z < chunkDepth - 1; z++)
                    {
                        if (cubes[x, y, z].World.Translation.Z + .5f == cubes[x, y, z + 1].World.Translation.Z - .5f)
                        {
                            backSide = true;
                        }
                        if (cubes[x, y, z].World.Translation.Z - 0.5f == cubes[x, y, z - 1].World.Translation.Z + 0.5f)
                        {
                            frontSide = true;
                        }
                        if (cubes[x, y, z].World.Translation.Y + 0.5f == cubes[x, y + 1, z].World.Translation.Y - 0.5f)
                        {
                            topSide = true;
                        }
                        if (cubes[x, y, z].World.Translation.Y - 0.5f == cubes[x, y - 1, z].World.Translation.Y + 0.5f)
                        {
                            bottomSide = true;
                        }
                        if (cubes[x, y, z].World.Translation.X + 0.5f == cubes[x + 1, y, z].World.Translation.X - 0.5f)
                        {
                            rightSide = true;
                        }
                        if (cubes[x, y, z].World.Translation.X - 0.5f == cubes[x - 1, y, z].World.Translation.X + 0.5f)
                        {
                            leftSide = true;
                        }

                        if (bottomSide != true || topSide != true || leftSide != true || rightSide != true || frontSide != true || backSide != true)
                        {
                            CubesToDraw.Add(cubes[x, y, z]);
                        }

                        bottomSide = false;
                        topSide = false;
                        leftSide = false;
                        rightSide = false;
                        frontSide = false;
                        backSide = false;
                    }//end z
                }//end y
            }//end x

        } 

I kept the bool variables in there just because most of the method was copy and paste. I don't know why CubesToDraw doesn't get anything added to it, but I've stared at it long enough that I've decided to just figure out how an octree could work in my case

Share this post


Link to post
Share on other sites
if (cube.World.Translation.X + 0.5f == adjacentCube.World.Translation.X - 0.5f)
...
if (cube.World.Translation.X - 0.5f == adjacentCube.World.Translation.X + 0.5f)
...

Maybe:

cube.World.Translation.X - adjacentCube.World.Translation.X == -1.0f 
cube.World.Translation.X - adjacentCube.World.Translation.X == 1.0f

if(absf(cube.World.Translation.- adjacentCube.World.Translation.X) == 1.0f)

 

I dont know will it work with floats corectly

private void CheckAdjacentCubes(List<Cube> cubes, List<Cube> cubeToDraw)
        {
            foreach (Cube cube in cubes)
            {
                foreach (Cube adjacentCube in cubes)
                {
                    if (absf(cube.World.Translation.X - adjacentCube.World.Translation.X) != 1.0f ||
                        absf(cube.World.Translation.Y - adjacentCube.World.Translation.Y) != 1.0f ||
                        absf(cube.World.Translation.Z - adjacentCube.World.Translation.Z) != 1.0f)
                    {
                        cubeToDraw.Add(cube);
			break;
                    }
                }
            }
        }
Edited by serumas

Share this post


Link to post
Share on other sites

 

For one, I’ve heard that “foreach” is extremely slow.


Do you have a source for that? Would be interested to see it.

 

 

Foreach requires a small amount of space for a hidden temporary object to yield over iteration, and that amount of space depends on the things being iterated over and the implementation (MS vs Mono).  It isn't usually too bad or even noticeable, unless you are in an extremely constrained environment.

 

In one game engine being ported to handhelds we discovered that a foreach() over one of our largest collections of game objects unexpectedly required around 100KB of space. By itself that isn't much, until you consider that you could potentially iterate over the collection with a regular for() loop using just a single integer to index into the collection.

 

Another consideration is that if your game implements a "pause the world" type of save game system so that all C# code is frozen mid-execution, the internals of foreach can be difficult to serialize when the execution environment is written to disk. In our engine we discovered that we could only save a single foreach loop, if two foreach loops were nested the deserialized world would be corrupt.

 

 

As for the algorithm, beyond the earlier suggestions of spatial partitioning and early exit, another improvement that can be made is that the current algorithm tests A against B, and then tests B against A.  You can reduce the processing by half because if one is true, both are true, if one is false then both are false.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!