Procedural Map Generation - determine adjacent tiles

Question

I was originally using a 2d Array of "Tile"s to store a procedural generated map with its various contents.

Each Tile contains a List adjacent which allows every single tile to know which vertices are closest to it, touching it on 8 different sides (straight adjacent and diagonally adjacent).

The general idea was taken from Amit's polygonal map generation, but I attempted to simplify it by using a grid setup instead of voronois, however I've run into more trouble than I originally thought would be possible. My current predicament is figuring out adjacency when I've scrapped 2d Arrays.

This is how I was doing it before changing to a list:

private void ConstructAdjacencyList() {

    // Create Adjacency List
    for (int x = 0; x < mapWidth; x++) {
        for (int y = 0; y < mapHeight; y++) {
            // Bool to find position of point
            bool omitLeft = false;      bool omitRight = false;
            bool omitTop = false;       bool omitBottom = false;
            // Enable bools based on position, reset on each loop               
            if (x == 0)
                omitLeft = true;                
            else if (x == mapWidth - 1)
                omitRight = true;               
            if (y == 0)
                omitTop = true;             
            else if (y == mapHeight - 1)
                omitBottom = true;

            // Add entries to list based on bool settings
            if (!omitLeft) {
                // Left center
                islandMap[x,y].adjacent.Add(islandMap[x-1,y]);
                if (!omitTop)
                    islandMap[x,y].adjacent.Add(islandMap[x-1,y-1]);
                if (!omitBottom)
                    islandMap[x,y].adjacent.Add(islandMap[x-1,y+1]);
            }

            if (!omitTop) // Top Center
                islandMap[x,y].adjacent.Add(islandMap[x,y-1]);
            if (!omitBottom) // Bottom Center
                islandMap[x,y].adjacent.Add(islandMap[x,y+1]);

            if (!omitRight) {
                // Right Center
                islandMap[x,y].adjacent.Add(islandMap[x+1,y]);
                if (!omitTop)
                    islandMap[x,y].adjacent.Add(islandMap[x+1,y-1]);
                if (!omitBottom)
                    islandMap[x,y].adjacent.Add(islandMap[x+1,y+1]);
            }               
        }
    } // End Adjacency

    Debug.Log ("Adjacencies Built");
}

The x, y values now are held in islandMap.point (A Vector 2d storing the x and y values generated as follows:)

public MapController() {
    width = height = (int)Mathf.Sqrt (tileCount);

    // Lists for points
    var points = new List<Vector2>();

    // Build a random set of points.
    for (float x = 0; x < width; x++)   {
        for (float y = 0; y < height; y++)  {
            points.Add(new Vector2(x,y));
        }
    }

    map = new Map (points, width, height, lakeTreshold);
}

And the Map itself has the following currently:

public class Map {
   Func<Vector2, bool> inside; // Contains function to randomly seed area
   bool needsMoreRandomness;

   public List<Tile> islandMap; // Previously was Tile[,] islandMap
   public int mapWidth { get; private set; } // Calculated as Sqrt(totalPoints)
   public int mapHeight { get; private set; }

Along with other methods such as the ConstructAdjacencyList() method I'm currently stuck on.

So how can I go on about constructing an adjacency list of surrounding points without relying on array positioning? Could I temporarily reference the entire list from an array, place references to each tile in the entire list in this 2d array, setup adjacencies and then remove the array without losing the information? I believe it would only use references, so it should be fine... Each tile contains an index to store the order with which it was built like so:

foreach (var point in points) {
        var p = new Tile { index = islandMap.Count, point = point };
        p.border = point.x == 0 || point.x == mapWidth || point.y == 0 || point.y == mapHeight;
        islandMap.Add (p);
        tileLookup[point] = p;
    }

Sorry if this is too long... I just realized it's quite massive -.-

There's a couple of ways to tackle this, but the size of your tile map may dictate which solutions are more appropriate - approximately how many tiles are you dealing with? — Pikalek, Mar 28 '16 at 15:23
Hi Pikalek, thanks for replying. I'll be looking at inputting about a maximum of 3000 points, currently hovering under 300 points. For one time computational time it's not as big of a deal honestly, provided it works. — Ben, Mar 28 '16 at 16:25
Also, what I tried to do was as follows: `Tile[,] tempArray = new Tile[mapWidth, mapHeight]; int count = 0; for (int x = 0; x < mapWidth; x++) { for (int y = 0; y < mapHeight; y++) { tempArray[x,y] = islandMap[count]; count++; } }` In an attempt to map all list elements to the 2d array, and then compute the logic from there onwards, I haven't yet tested if this is correct or not however, since I'm having trouble wrapping my mind around how to correctly test and debug this information. — Ben, Mar 28 '16 at 16:27
You could store the adjacency as part of your Tile object model. Say, store a List for each tile, which holds references to each tile that the current tile is adjacent to (up to 8 max). Or you could store the 2d x & y co-ords in your tile model and then just use standard 2d logic for adjacency from there. — ManoDestra, Mar 28 '16 at 20:10
@ManoDestra This is already the way it's setup. My question relates towards populating that specific list present in each tile object. Check my own answer for clarification. — Ben, Mar 28 '16 at 21:54

score 0 · Answer 1 · edited May 23 '17 at 12:31

Assuming you haven't done anything to mess with the order of the points, you can treat a 1D list/array as 2D list/array. The example I linked is in C, but the idea language agnostic.

That being said, assuming that you're only going to do this once during the initialization & given the relatively low number of points, you could just as easily brute force it with a function that loops through the point list & picks out the neighbors as needed. My C# is a bit rusty, but I'm talking about something like this:

private List<Vector2> getAdjacenctPointList(List<Vector2> pointsList, Vector2 point){
  var adjacencyList = new List<Vector2>();
  foreach (var pt in pointList){
    var offset = Math.abs(pt.x - point.x) + Math.abs(pt.y - point.y);
    if(offset > 0 && offset <= 1.0){
      adjacencyList.add(pt);
    }
  }
  return adjacencyList;
}

Thanks for the reply, I actually solved this in a simpler way using the same basic idea of treating a list as a 2d array. however I made it literally as such. I'll post my own as an answer up as well. — Ben, Mar 28 '16 at 21:22

score 0 · Answer 2 · edited Jun 20 '20 at 09:12

The final answer I went with which was the least amount of work involved and allowed me to recycle my original 2d Array code posted above was to simply construct a temporary 2d array and store all the references to it in it - create all adjacencies as necessary and then dispose (simply by losing scope) of the 2d Array.

Here's the actual method with the 2d array system in place. First couple statements followed by the nested for loop was all it took:

private void ConstructAdjacencyList() {
    Tile[,] tempArray = new Tile[mapWidth, mapHeight];

    int count = 0;

    // Populate the temp 2D array with list references
    for (int x = 0; x < mapWidth; x++) {
        for (int y = 0; y < mapHeight; y++) {
            tempArray[x,y] = islandMap[count];
            count++;            
        }
    }

    // Create Adjacency List using our TempArray
    for (int x = 0; x < mapWidth; x++) {
        for (int y = 0; y < mapHeight; y++) {
            // Bool to find position of point
            bool omitLeft = false;      bool omitRight = false;
            bool omitTop = false;       bool omitBottom = false;
            // Enable bools based on position, reset on each loop               
            if (x == 0)
                omitLeft = true;                
            else if (x == mapWidth - 1) // Optimize with if else to split checks in half.
                omitRight = true;               
            if (y == 0)
                omitTop = true;             
            else if (y == mapHeight - 1)
                omitBottom = true;

            // Add entries to list based on bool settings
            if (!omitLeft) {
                // Left center
                tempArray[x,y].adjacent.Add(tempArray[x-1,y]);
                if (!omitTop)
                    tempArray[x,y].adjacent.Add(tempArray[x-1,y-1]);
                if (!omitBottom)
                    tempArray[x,y].adjacent.Add(tempArray[x-1,y+1]);
            }
            
            if (!omitTop) // Top Center
                tempArray[x,y].adjacent.Add(tempArray[x,y-1]);
            if (!omitBottom) // Bottom Center
                tempArray[x,y].adjacent.Add(tempArray[x,y+1]);
            
            if (!omitRight) {
                // Right Center
                tempArray[x,y].adjacent.Add(tempArray[x+1,y]);
                if (!omitTop)
                    tempArray[x,y].adjacent.Add(tempArray[x+1,y-1]);
                if (!omitBottom)
                    tempArray[x,y].adjacent.Add(tempArray[x+1,y+1]);
            }               
        }
    } // End Adjacency

    Debug.Log ("Adjacencies Built");
}

To ensure this worked out as I wanted it to, I tested it visually by setting one random cube and tested various points all around the area to ensure there were no mistakes and there weren't.

The end result is as expected, depicted below:

Thanks for the help :)

Procedural Map Generation - determine adjacent tiles

2 Answers2