4
\$\begingroup\$

I'm currently working on my 2D survival game, where the world is infinite and generated by perlin noise. I wanted to also include biomes and this article interested me - http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/ .

I downloaded the source ported to C# and edited it to 2D, but there's the problem. I generated simple map 100x100 but then, I dont know how to convert those polygons into the tiles. I tried a simple technique:

for (int x = 0; x < map.GetLength(0); x++)
        {
            for (int y = 0; y < map.GetLength(1); y++)
            {
                float rozdilP = 100000f; Biome b = BiomeTypes.Snow;

                foreach (Center center in EnvironmentService.MapGenService.Centers.Values)
                {
                   float rozdil = Vector2.Distance(new Vector2(x, y), new Vector2(center.Point.X, center.Point.Z));
                    if (rozdil < rozdilP)
                    {
                        rozdilP = rozdil;
                        b = center.Biome;
                    }

                }
                map[x, y] = b;
            }
        }

it works, but it's really, really slow. Isn't there any better solution or algorhytm for this or is the polygon method of generation supposed to be used only in 3D?

Ty for your time and answer :) enter image description here

\$\endgroup\$
1
\$\begingroup\$

Please, at all cost, avoid using vector2(or 3 or 4 for that matter).Distance(). If you can, use DistanceSquared() instead. To get the actual distance, XNA uses the pythagorean theorem, which ultimately means that it needs to use the square root function. This is a relatively slow function. So use this instead:

for (int x = 0; x < map.GetLength(0); x++)
    {
        for (int y = 0; y < map.GetLength(1); y++)
        {
            float rozdilP = 100000f; Biome b = BiomeTypes.Snow;

            foreach (Center center in EnvironmentService.MapGenService.Centers.Values)
            {
               float rozdil = Vector2.DistanceSquared(new Vector2(x, y), new Vector2(center.Point.X, center.Point.Z));
                if (rozdil < rozdilP * rozdilP)
                {
                    //rozdilP = Mathhelper.sqrt(rozdil); (Unless you really need this one, don't use it)
                    b = center.Biome;
                }

            }
            map[x, y] = b;
        }

When handling a square root function, you really need to ask yourself if you NEED to use it, or if it only seems logical to you. Because knowing that it costs a lot of processor power, you might have to come up with a calculation that seems a bit convoluted, but is much faster. Especially, of course, in a loop function.

\$\endgroup\$
0
\$\begingroup\$

There is only 1 optimization you need to implement:

Vector2 Min, Max;
Min = poly.Vertices[0];
Max = poly.Vertices[0];
for (int i = 1; i < poly.Vertices.Length; i++)
{
    Vector2 Vertex = poly.Vertices[i];
    if (Vertex.x < Min.x)
    {
        Min.x = Vertex.x;
    }
    else if (Vertex.x > Max.x) {
        Max.x = Vertex.x;
    }
    if (Vertex.y < Min.y)
    {
        Min.y = Vertex.y;
    }
    else if (Vertex.y > Max.y) {
        Max.y = Vertex.y;
    }
}

This calculates the minimum and maximum of the polygon on the X and Y axes. On the grid, this allows you to cull out all grid nodes outside of the polygon's bounding box.

i.e.:

for (int i = (int)Min.x; i < (int)(Max.x + 1); i++)
{
    for (int j = (int)Min.y; j < (int)(Max.y + 1); j++)
    {
        CheckNode (i, j);
    }
}

The number of checks goes from the total number of grid nodes to only the grid nodes relevant and surrounding the polygon.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.