37
\$\begingroup\$

This is not related to a Minecraft clone.

I am currently writing a turn-based strategy game like Final Fantasy Tactics. The game is played on floating voxel-style islands, which are generated from heightmap images (will soon be dynamically generated using system.drawing). I already wrote the world generator (15 minute mock up) and the voxel world optimizer.

My only issue is that the voxel world optimization takes around 900ms to complete (a suggestion that I received on Stack Overflow recommended Parallel.ForEach and that dropped it down to 260-300ms). I wanted to show you guys some code and see if someone could assist me in dropping the opt-time down to around 100-200ms.

Here is my current Heightmap (the System is very crude at this point):

HeightMap Mockup

And here is a brief rendering of said Heightmap:

HeightMap Rendering

The World Optimizer that I have already written takes into consideration when faces cannot be seen, and then if that can be asserted, hides said faces (the land masses are hollow despite having voxels present). Again, I just need someone to help me optimize the optimizer so that It can work faster.

Here is my world optimizer; I will provide any other source code if required.

Full project source can be downloaded here. (OpenTK required & precompiled demo included)

using GameProject.Game.Framework.Geometry;
using System.Collections.Generic;
using OpenTK;

namespace GameProject.Game.Framework.Generators {
    public enum OptimizationType {
        FullOptimization
    }
    public static class WorldOptimizer {
        public static void OptimizeVoxelWorld( List<Voxel> world , OptimizationType optimizationType ) {
            switch( optimizationType ) {
                case OptimizationType.FullOptimization:
                    DoFullOptimization( world );
                    break;
            }
        }

        private static void DoFullOptimization( List<Voxel> world ) {
            /**
             * Loop Through The Voxel Collection and collect
             * potential neighbors.
             */
            foreach( Voxel currentVoxel in world ) {
                Vector3 backNeighbor = currentVoxel.Location;
                backNeighbor.X += 2.0f;
                Vector3 frontNeighbor = currentVoxel.Location;
                frontNeighbor.X -= 2.0f;
                Vector3 leftNeighbor = currentVoxel.Location;
                leftNeighbor.Z -= 2.0f;
                Vector3 rightNeighbor = currentVoxel.Location;
                rightNeighbor.Z += 2.0f;
                Vector3 topNeighbor = currentVoxel.Location;
                topNeighbor.Y += 2.0f;
                Vector3 bottomNeighbor = currentVoxel.Location;
                bottomNeighbor.Y -= 2.0f;

                /**
                 * This is the part that needs to be fixed.
                 * Basically we loop back through the collection
                 * AGAIN for every voxel. This means that we
                 * check every voxel at least twice, if not up
                 * to six times...I think.
                 */
                foreach( Voxel voxel in world ) {
                    if( voxel != currentVoxel ) {
                        if( voxel.Location == backNeighbor ) {
                            currentVoxel.ShowBackFace = false;
                        } else if( voxel.Location == frontNeighbor ) {
                            currentVoxel.ShowFrontFace = false;
                        } else if( voxel.Location == leftNeighbor ) {
                            currentVoxel.ShowLeftFace = false;
                        } else if( voxel.Location == rightNeighbor ) {
                            currentVoxel.ShowRightFace = false;
                        } else if( voxel.Location == topNeighbor ) {
                            currentVoxel.ShowTopFace = false;
                        } else if( voxel.Location == bottomNeighbor ) {
                            currentVoxel.ShowBottomFace = false;
                        }
                    }
                }
            }
        }

        /**
         * Add this feature later with bitwise flags and other sorts of glorious sugar.
         */
        private static void DoFullControlOptimization(List<Voxel> world) {

        }
    }
}

Suggestion #1; Use Parallel.ForEach loop (drops time down from 900ms to 260-300ms)

using System.Threading.Tasks;
using GameProject.Game.Framework.Geometry;
using System.Collections.Generic;
using OpenTK;

namespace GameProject.Game.Framework.Generators {
    public enum OptimizationType {
        FullOptimization
    }
    public static class WorldOptimizer {
        public static void OptimizeVoxelWorld( List<Voxel> world , OptimizationType optimizationType ) {
            switch( optimizationType ) {
                case OptimizationType.FullOptimization:
                    DoFullOptimization( world );
                    break;
            }
        }

        private static void DoFullOptimization( List<Voxel> world ) {
            /**
             * Loop Through The Voxel Collection and collect
             * potential neighbors.
             */

            // Parallel.ForEach drops Opt-Time down to 260-300ms!
            // Was 900ms with regular for-each loop.
            Parallel.ForEach( world , currentVoxel => {
                Vector3 backNeighbor = currentVoxel.Location;
                backNeighbor.X += 2.0f;
                Vector3 frontNeighbor = currentVoxel.Location;
                frontNeighbor.X -= 2.0f;
                Vector3 leftNeighbor = currentVoxel.Location;
                leftNeighbor.Z -= 2.0f;
                Vector3 rightNeighbor = currentVoxel.Location;
                rightNeighbor.Z += 2.0f;
                Vector3 topNeighbor = currentVoxel.Location;
                topNeighbor.Y += 2.0f;
                Vector3 bottomNeighbor = currentVoxel.Location;
                bottomNeighbor.Y -= 2.0f;

                /**
                 * This is the part that needs to be fixed.
                 * Basically we loop back through the collection
                 * AGAIN for every voxel. This means that we
                 * check every voxel at least twice, if not up
                 * to six times...I think.
                 */
                foreach( Voxel voxel in world ) {
                    if( voxel != currentVoxel ) {
                        if( voxel.Location == backNeighbor ) {
                            currentVoxel.ShowBackFace = false;
                        } else if( voxel.Location == frontNeighbor ) {
                            currentVoxel.ShowFrontFace = false;
                        } else if( voxel.Location == leftNeighbor ) {
                            currentVoxel.ShowLeftFace = false;
                        } else if( voxel.Location == rightNeighbor ) {
                            currentVoxel.ShowRightFace = false;
                        } else if( voxel.Location == topNeighbor ) {
                            currentVoxel.ShowTopFace = false;
                        } else if( voxel.Location == bottomNeighbor ) {
                            currentVoxel.ShowBottomFace = false;
                        }
                    }
                }
            } );
        }

        /**
         * Add this feature later with bitwise flags and other sorts of glorious sugar.
         */
        private static void DoFullControlOptimization(List<Voxel> world) {

        }
    }
}
\$\endgroup\$
0

3 Answers 3

Reset to default
21
+50
\$\begingroup\$

To solve this problem, I made each Voxel aware of its neighbours, this was achieved in the world generation/height-map loading phase.

Then I was able to change the optimization algorithm to the following (found in Program.cs):

private static void DoFullOptimization(IEnumerable<Voxel> world)
{
    foreach (var currentVoxel in world)
    {
        var visibleFaces = Faces.None;
        if (currentVoxel.BackNeighbor == null)
        {
            visibleFaces |= Faces.Back;
        }
        if (currentVoxel.FrontNeighbor == null)
        {
            visibleFaces |= Faces.Front;
        }
        if (currentVoxel.BottomNeighbor == null)
        {
            visibleFaces |= Faces.Bottom;
        }
        if (currentVoxel.TopNeighbor == null)
        {
            visibleFaces |= Faces.Top;
        }
        if (currentVoxel.LeftNeighbor == null)
        {
            visibleFaces |= Faces.Left;
        }
        if (currentVoxel.RightNeighbor == null)
        {
            visibleFaces |= Faces.Right;
        }

        currentVoxel.VisibleFaces = visibleFaces;
    }
}

This does mean I moved the performance hit to the world loading, however loading the sample height-map image and generating the voxels only took 21ms and the optimization took 0.96ms (yes, less than 1ms).

My entire solution can be found on BitBucket here.

The key in the loading phase is to keep track of the loaded neighbors, I do this in the WorldLoader by having a Dictionary<Vector3d, Voxel>. I only bother searching for the left/back/bottom neighbors because my Voxel implementation already deals with setting the other end of the relationship between neighbours (if x.LeftNeighbor = y then y.RightNeighbor == x).

Note

I am not a GameDev so my X, Y and Z are probably all the wrong way round or referring to the wrong thing!

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Whoa, nice. And please do. \$\endgroup\$ Commented Sep 10, 2014 at 22:44
  • \$\begingroup\$ Nice, waiting for the pre-processing part, where is the real magic! \$\endgroup\$ Commented Sep 11, 2014 at 5:34
  • \$\begingroup\$ I have placed meta question on the situation we have here. See my description and reasoning there and join the discussion to show your opinion, please. \$\endgroup\$ Commented Sep 11, 2014 at 7:58
  • \$\begingroup\$ @firda I've updated my answer with an explanation of what I did and a link to my sample project, I will join the discussion on meta. \$\endgroup\$ Commented Sep 11, 2014 at 9:14
  • 1
    \$\begingroup\$ I like the generic dictionary approach. Realistically, I can have a loading screen or something for the initial building/cacheing. I choose this as the answer; thank you! \$\endgroup\$ Commented Sep 11, 2014 at 16:15
15
\$\begingroup\$

You know that those two loops are the problem (quadratic complexity - O(n2)), so, you want to decrease that somehow. Parallel.ForEach will use other cores to gain some speed, but best would be to use different structure - something 2D or 3D, to help you find the voxels faster. If 3D eats too much memory, 2D should still help (with list of voxels up/down). If that is still too much, try utilizing R-tree whis is perfect for nearest neighbor search. Finally you can just throw the structure away, once the job is done.

EDIT: Just small note, see comments below: The heightmap is in fact already that 2D/3D structure that can be used to find the neighbours.

EDIT2: Utilizing both the Parallel.ForEach and the heightmap should give the best performance. (note: we abviously came to similar idea with the author to use the Parallel.ForEach at the same time, I didn't see his update.)

\$\endgroup\$
6
  • \$\begingroup\$ I will look into an R-Tree soon, thanks. If I find a solution I will post it here. \$\endgroup\$ Commented Sep 10, 2014 at 21:19
  • \$\begingroup\$ Looking forward to see it :) R-tree or possibly that octree would be nice, but could be an overkill. \$\endgroup\$ Commented Sep 10, 2014 at 21:31
  • \$\begingroup\$ Rather moved to comment: Could you (Krynn) include the code of loading phase, where you create the voxels using the height map? Maybe, the optimization could be done using the heightmap, where you know which voxels are neighbours - you don't even need to have them created, to hide the faces of the one you are currently creating, the heightmap may indicate it immediatelly from surrounding pixels. \$\endgroup\$ Commented Sep 11, 2014 at 8:44
  • \$\begingroup\$ I don't think an octree would be overkill. Coming to think of it the octree opens other optimization possibilities like rendering whole tiles of the same height and material as one primitive (which increases throughput) and making spatial queries more efficient. \$\endgroup\$ Commented Sep 11, 2014 at 10:37
  • 1
    \$\begingroup\$ I just rewrote the heightmap generator; I am not comfortable with pasting it anywhere because it is the only thing that makes my game harder to replicate. As of right now the heightmap loader takes 12 different shades of color supporting up to 12 layers of voxels(y 22 in 3D space). And it can load a 100*100 png in less than 30ms. It is the one thing that I want to keep as proprietary...even if someone could write it on their own. \$\endgroup\$ Commented Sep 12, 2014 at 21:16
3
\$\begingroup\$

After a few hours slaving over Visual Studio I was finally able to produce a solution (based upon @Lukazoid's post). This solution uses a generic dictionary which holds a Vector3 as a key and Voxel as a value. All you have to do is ask if said voxel exists.

Here is my VoxelWorld class:

using GameProject.Game.Framework.Generators;
using GameProject.Game.Framework.Geometry;
using System.Collections.Generic;
using OpenTK;

namespace GameProject.Game.Framework.DataStructure {
    public class VoxelWorld {
        public List<Voxel> Voxels;
        public Dictionary<Vector3 , Voxel> SpatialStore;
        public VoxelWorld() {
            Voxels = new List<Voxel>();
            SpatialStore = new Dictionary<Vector3 , Voxel>( new Vector3EqualityComparator() );
        }

        public void AddVoxel( Voxel voxel ) {
            Voxels.Add( voxel );
            SpatialStore.Add( voxel.Location , voxel );
        }

        public Voxel GetVoxelAt( Vector3 location ) {
            return SpatialStore.ContainsKey( location ) ? SpatialStore[ location ] : null;
        }

        public void Rebuild() {
            WorldOptimizer.OptimizeVoxelWorld( this , OptimizationType.FullOptimization );
        }
    }
}

And my optimizer, which can now process the spatial store in about 9-10ms. I am sure there are still some other things I can do to make it faster; if I discover any I will gladly throw them up here for everyone to see.

using System.Threading.Tasks;
using GameProject.Game.Framework.DataStructure;
using GameProject.Game.Framework.Geometry;
using System.Collections.Generic;
using OpenTK;

namespace GameProject.Game.Framework.Generators {
    public enum OptimizationType {
        FullOptimization
    }
    public static class WorldOptimizer {
        public static void OptimizeVoxelWorld( VoxelWorld world , OptimizationType optimizationType ) {
            switch( optimizationType ) {
                case OptimizationType.FullOptimization:
                    DoFullOptimization( world );
                    break;
            }
        }

        private static void DoFullOptimization( VoxelWorld world ) {
            Parallel.ForEach( world.Voxels , currentVoxel => {
                Vector3 backNeighbor = currentVoxel.Location;
                backNeighbor.X += 2.0f;
                Vector3 frontNeighbor = currentVoxel.Location;
                frontNeighbor.X -= 2.0f;
                Vector3 leftNeighbor = currentVoxel.Location;
                leftNeighbor.Z -= 2.0f;
                Vector3 rightNeighbor = currentVoxel.Location;
                rightNeighbor.Z += 2.0f;
                Vector3 topNeighbor = currentVoxel.Location;
                topNeighbor.Y += 2.0f;
                Vector3 bottomNeighbor = currentVoxel.Location;
                bottomNeighbor.Y -= 2.0f;

                if( world.SpatialStore.ContainsKey( frontNeighbor ) ) {
                    currentVoxel.ShowFrontFace = false;
                }
                if( world.SpatialStore.ContainsKey( backNeighbor ) ) {
                    currentVoxel.ShowBackFace = false;
                }
                if( world.SpatialStore.ContainsKey( leftNeighbor ) ) {
                    currentVoxel.ShowLeftFace = false;
                }
                if( world.SpatialStore.ContainsKey( rightNeighbor ) ) {
                    currentVoxel.ShowRightFace = false;
                }
                if( world.SpatialStore.ContainsKey( topNeighbor ) ) {
                    currentVoxel.ShowTopFace = false;
                }
                if( world.SpatialStore.ContainsKey( bottomNeighbor ) ) {
                    currentVoxel.ShowBottomFace = false;
                }
            } );
        }

        /**
         * Add this feature later with bitwise flags and other sorts of glorious sugar.
         */
        private static void DoFullControlOptimization( List<Voxel> world ) {

        }
    }
}

And you will also need this, too, which is a Vector3 comparator extension. (new edit brings the optimization time down to 9-10ms)

using System.Collections.Generic;
using OpenTK;

namespace GameProject.Game.Framework.DataStructure.ComparatorExtensions {
    public class Vector3Comparator : IEqualityComparer<Vector3> {

        public bool Equals( Vector3 left , Vector3 right ) {
            return (left.X == right.X) && (left.Y == right.Y) && (left.Z == right.Z);
        }

        public int GetHashCode( Vector3 obj ) {
            return obj.GetHashCode();
        }
    }
}
\$\endgroup\$
6
  • \$\begingroup\$ Just another hint: try to utilize both the Parallel.ForEach and the heightmap, to disable some faces. That should give you the best performance ;) \$\endgroup\$ Commented Sep 12, 2014 at 21:13
  • \$\begingroup\$ I know, but I like my approach because I can now move into a "destructible world" mentality and easily reconstruct the entire level. I want the loader to only load; the optimizer to only optimize. \$\endgroup\$ Commented Sep 12, 2014 at 21:19
  • \$\begingroup\$ Sure, I like the idea with the dictionary as well. I was as well thinking about other possibilites it can bring. Brilliant idea Lukazoid had. \$\endgroup\$ Commented Sep 12, 2014 at 21:21
  • \$\begingroup\$ Certainly. Especially because I can literally just pass in a Vector3 and get out the voxel at that location. \$\endgroup\$ Commented Sep 12, 2014 at 21:24
  • 1
    \$\begingroup\$ You may actually find the overhead of Parallel.ForEach outweighs the benefits, profile both to be sure. \$\endgroup\$ Commented Sep 13, 2014 at 1:11

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.