Procedurally generated maps

By Joost Valentijn

source code: https://gitlab.fdmci.hva.nl/valentj3/gamelab

For this assignment I tried procedurally generating StarCraft II maps. Using Voronoi diagrams, Delaunay triangulation, A* and Perlin noise I tried creating natural looking maps that look like StarCraft maps.

Table of contents
1. Preliminary study
2. What is a StarCraft map?
3. Generation of base locations
4. Creation of a graph
5. Reflection
6. Map feel
7. Blobs
8. Mesh creation
9. Peek into the future
10. Sources

Preliminary study
There have already been studies done on the creation of StarCraft 1 maps. A paper written for the 2010 IEEE Conference on Computational Intelligence and Games (CIG) uses a multi-objective evolution algorithm: an algorithm with different fitness functions that tries to find the best combination of these fitness functions to get the best results. (Togelius et al., 2010) I wanted to try an algorithmic approach instead of an AI approach.

What is a StarCraft map?
A StarCraft map is a connected grid where bases and open areas are connected with other open areas and bases. What I noticed, while trying to define a StarCraft map, are some circles (bases and open area’s) that are connected with rectangles (roads that lead from one area to another). By generating points and connecting them through a graph-like structure I aim to procedurally generate a map. This way I can create a graph where the vertices are the open areas and the edges the roads in between them.

What makes a SCII map a SCII map?

  • The main-base always has one walkable exit (with exception of jump-up spots) that leads towards the natural base.
  • After the natural base there is a chokepoint that leads to multiple locations (often 2/3) from where there is at least one base.
  • Every chokepoint or base location should have at least 1 and a max of 5 roads to other chokepoints and bases.
  • Every base should be reachable.
  • A base exists of two different resources: Vespine gas & Minerals. These resources are mostly in the same pattern.
  • A map is always mirrored in some axis.

Generation of base locations
The first step in the process is generating the circles. At first I tried to randomly generate some circles. This first try of generating circles failed because there was too much randomness. The circles would generate on top of each other and that is not what I want. There needs to be some type of structure in the circles. To do this I tried to generate a circle in the bottom left corner and tried to generate the next circle in a radius around it avoiding walls and other circles. I could not make that work in one day and thus I proceeded to find some algorithms that have already been figured out.

Poisson disk sampling
“Poisson disk sampling is a technique for randomly picking tightly-packed points such that they maintain a minimum user-specified distance.” (Vanga, 2018)
With poisson disk sampling I can generate points with a minimum distance from each other inside a grid. This can come in handy because now I have randomly generated points that visualize my bases and open area’s. That is exactly what I need for the creation of the map.

Now the next step is creating a graph out of these points. What I want is a graph where the points close to each other are connected after which I can remove some of the connections to make it a random map. To do this I use something called a Voronoi diagram.
A Voronoi diagram uses Delaunay triangulation to create Voronoi sites. These sites are created by edges between different regions. When creating a Voronoi diagram a list of connected sites are created. These are the sites that share an edge with each other. The connections coming out of the Voronoi diagram are used to create my starting graph.

(Galishnikova, 2018)

Creation of the Graph
When generating the Voronoi diagram and extracting the grid from it we get the following outcome:

This is of course a good start but not a map yet. To make it a map I am going back to the definitions I set for each SC II map:
The main base should only have one walkable exit. The natural base should lead to either 2 or 3 places. The rest can have up to 5 roads.

To create a good graph I first started with finding the main base. To do this I used an input start position that is an enum with 4 possibilities: topLeft, topRight, bottomLeft, bottomRight. With the reflection axis and the positions of the bases I tried to find the closest point to whichever start position is chosen.

Now that we have a start position it is time to remove some edges to create the map. To make it pseudorandom I thought about a way to define which edges should stay and which should go. To do this I created an array that holds the amount of edges each point should be able to hold. Every edge has a boolean that states if an edge is active. This starts as false, so each edge is inactive.

Starting from the main base I…

  1. set the vertex to watched.
  2. find the edges connected to the vertex that are not used yet.
  3. check if the edge limit is already satisfied. If so, I go on to the next vertex.
  4. calculate the amount of edges necessary to reach the satisfied amount of paths.
  5. add random edges either until there are no more edges or until the edge cap for this vertex is reached.
  6. enqueue the vertices that were connected to those edges and run the same algorithm on these edges.

When running this algorithm you get something like this:

It is starting to look like a map but it isn’t one yet. The first problem is that some points are not connected at all. To make sure that everything is connected to the whole grid I want to check if every point is connected to the main base and if it isn’t, connect that point to a nearby point.
With A* I can easily find the points that are not connected to the main grid. A* can also find the closest point in the area because it needs a distance estimation to work anyway.

All the points are now connected. Time to reflect the map.

Reflection
For the reflection I have 4 possibilities:

When mirroring on the x-axis or y-axis, the points only reflect on the axis. The inversed flips and then reflects the points.

My points are created on a rectangle going from (-width / 2, -height /2) to (width / 2, height /2). Because I want to reflect the points in a certain axis, we only need to spawn points on half of the map. This makes it really easy to mirror the points. You just multiply the x position of a point with -1 to reflect it in the y-axis. For example a point (-15; -8) reflected in the y-axis becomes (15; -8) (Persico, 2023)
I do this for all of my base points.

Now we have the reflection, but the two graphs are still not connected to each other. To do this I just figured I would use the distance between points and if they are under a certain threshold they connect to each other.

Map feeling
Right now the map is just a graph, but we want a map with a grid shape that looks natural. Starting out with a Voronoi diagram gave me the idea to use it to create a natural looking base structure. Every site that is inside a base circle gets added as a base site (a site that belongs to a base). Every site inside a path gets added as a path site. The rest are wall sites. For the paths and bases i expanded the borders so it better resembles a SCII map

Now to draw the map at first we are using the Voronoi diagram to make more natural shapes. This Voronoi diagram needs to be converted to a grid shape. To do this I calculate for all rectangle in which type of site they are.


This takes about a minute to calculate which for a pretty simple thing is way too long. It also doesn’t really give the outcome I want. So I tried another solution. Blobs.

Blobs

Blobs can be created with Perlin noise. (The Coding Train, 2019) To create a blob I use 2D Perlin noise. In the noise I draw a circle and I read out the values from this circle. The reason I am reading out the noise in a circle shape, is because this way the first and last value are the same and there is no weird cut between them. Because the Perlin noise can sometimes be more than 1 according to the unity documentation we have to check if the circle is inside the bounds of the max radius. Now the points belonging to the circle are multiplied with the offset created by the noise which in turn creates a natural shape.

private void DeformCircle(KeyValuePair<Vector2, List<MapBlock>> circleToEdgeBlock, float difference)
    {
        Vector2[] circle = new Vector2[361];
        int count = 0;
        for (float i = 0; i < Mathf.PI * 2; i += Mathf.Deg2Rad)
        {
            float xOffset = (Mathf.Cos(i) * difference) + circleToEdgeBlock.Key.x;
            float yOffset = (Mathf.Sin(i) * difference) + circleToEdgeBlock.Key.y;
            float offset = Mathf.PerlinNoise(xOffset, yOffset) * (_maxRadius - _radius) + _radius;
            if (offset > _maxRadius)
            {
                offset = _maxRadius;
            }

            circle[count] = new Vector2(Mathf.Cos(i) * offset, Mathf.Sin(i) * offset) + circleToEdgeBlock.Key;
            count++;
        }
        circles.AddRange(circle);

        foreach (MapBlock mapBlock in circleToEdgeBlock.Value)
        {
            if (mapBlock.GridType == GridType.BASE)
            {
                continue;
            }
            if (MathHelper.CheckInsideOfPolyGon(circle, circle.Length, mapBlock.Centre) % 2 == 1)
            {
                mapBlock.GridType = GridType.BASE;
                
            }
        }
    }

Mesh creation

The colours don’t resemble a SC II map so I am creating a mesh with a tile map from SC I (because I could not find a tile map from SC II).
Every rectangle has four points, so we need width * height * 4 amount of vertices.

Going from the centre, the centre points are translated to the corners by adding or removing 0.5 to both axis. For the triangles it is pretty easy: The bottom right, bottom left and top left corners are one triangle and the bottom right, top left and top right are another one.

For the uv’s I tried changing the percentage of the whole png shown inside one rectangle of the map and found that 1/16th looks good.


Peek into the future

For the future I would like to try creating a pathfinding algorithm inside this map that takes into account the walls, other units and structures and that actively tries to run around each other using something like a flocking AI. Either that or naturally generating resources in the right areas seems like a fun challenge.

Sources

Galishnikova, V. V. (2018, December). Voronoi diagram in a plane. Research Gate. https://www.researchgate.net/figure/Voronoi-diagram-in-a-plane_fig1_325582898

Persico, A. (2023). Reflection Over The X and Y Axis: The Complete Guide — Mashup Math. Mashup Math. https://www.mashupmath.com/blog/reflection-over-x-y-axis

Strike Tactics. (n.d.). http://striketactics.net/devblog/starcraft-1-pathfinding-technical-analysis

The Coding Train. (2019, February 25). Coding Challenge #136.1: Polar Perlin Noise Loops [Video]. YouTube. https://www.youtube.com/watch?v=ZI1dmHv3MeM

Togelius, J., Preuss, M., Beume, N., Wessing, S., Hagelbäck, J., & Yannakakis, G. N. (2010). Multiobjective exploration of the StarCraft map space. Computational Intelligence and Games. https://doi.org/10.1109/itw.2010.5593346

Uriarte, A., & Ontañón, S. (2013). PSMAGE: Balanced map generation for StarCraft. Computational Intelligence and Games. https://doi.org/10.1109/cig.2013.6633644

Vanga, M. (2018, February 13). Poisson Disk Sampling in Processing. Sighack. https://sighack.com/post/poisson-disk-sampling-bridsons-algorithm

Leave a Reply

Your email address will not be published. Required fields are marked *