0
\$\begingroup\$

I'm currently working on a generated(Perlin Noise) 2D Cave System with Unity.
The Caves currently look like this:
Map Example

What I want to do is spawn the Player (and other stuff) in the big Part of the Cave and not the small ones, so I wanted to have some sort of List of all the Tile(positions) of the Big Room.

I thought about a Pathfinding algorithm for finding like the two furthest away points and determine the distance, but I had no clue how to find those starting points.

The final function should look like this:

List<Vector2> GetLargestRoom(int[,] map) // where int[x,y] is either 0 or 1 for solid/ not solid
\$\endgroup\$
3
  • \$\begingroup\$ Is your caved stored as polys or is it represented by a 2d grid/array? \$\endgroup\$
    – Pikalek
    Aug 19, 2021 at 22:28
  • \$\begingroup\$ A 2D Array of Integers where 0 is solid and 1 is not. In Unity i stored it in a Tilemap Component @Pikalek \$\endgroup\$
    – Jonas Re
    Aug 19, 2021 at 23:09
  • 1
    \$\begingroup\$ You may be interested in algorithm to find suitable locations to place a town on a heightmap \$\endgroup\$
    – DMGregory
    Aug 20, 2021 at 1:05

1 Answer 1

3
\$\begingroup\$

To start with, we need to break down what is meant by room or cave. With respect to the 2D array in the problem description, a room is a collection of elements that are 'connected'. For any given starting point, we can identify all the elements of a connected region using a flood fill algorithm.

The flood fill algorithm presented below works as follows:

  • tag the starting point
  • place a starting point in the work queue
  • while the work queue isn't empty
    • remove an element from the queue
    • get the neighbors of the current element
    • for each valid neighbor (meaning it's not a wall & hasn't already been tagged)
      • tag it (the neighbor) & add it to the queue

When the work queue is empty, all of the elements that are reachable from the starting point will have been visited and tagged. Because the problem description requests a list of all the element locations, whenever an element is tagged, it will also be added to a list.

Flood fill alone isn't quite enough to solve the problem though. We still need a way to find the starting point of the largest room. Since we don't necessarily know where the largest room is, we'll need to iterate over the 2D array and look for it. If we encounter an element isn't open or has already been tagged, we can skip over it. If we encounter an open element that hasn't previously been identified as belonging to a region, we flood fill starting at that location.

There are a couple of options regarding what to do each time the flood fill finishes with a region:

  • Compare the most recently found region against the largest know region & only keep track of the largest.
  • Keep track of all the regions and then find the largest.

The second option requires a bit more memory, but also provides some extra benefits that might be useful when dealing with procedurally generated caves. Also, after seeing the solution for the second, it's pretty trivial to trim it back down it the first option. Since the second option provides more flexibility and isn't significantly more complex, it's the solution we will examine.

Here's the code:

using System.Collections;
using System.Collections.Generic;
using System.Numerics;

namespace LargestRoomProject
{
    public class CaveGridManager
    {
        public int[,] regionID;
        public List<List<Vector2>> regionCoords;

        // helper class for dealing with a map
        // assumes 0 == wall & 1 == open
        public CaveGridManager(int[,] data)
        {
            regionID = new int[data.GetLength(0), data.GetLength(1)];
            for(int x=0; x<regionID.GetLength(0); x++)
            {
                for(int y=0; y<regionID.GetLength(1); y++)
                {
                    regionID[x,y] = -1;
                }
            }
            regionCoords = new List<List<Vector2>>();

            for(int x=0; x<data.GetLength(0); x++)
            {
                for(int y=0; y<data.GetLength(1); y++)
                {
                    if(data[x,y] == 1 && regionID[x,y] == -1)
                    {
                        regionCoords.Add(FillNewRegion(data, x, y));
                    }
                }
            }
        }

        // start a new region at the x,y coords, fill it with the next available regionID and
        // return a list of the x,y coords of that regions
        private List<Vector2> FillNewRegion(int[,] data, int x, int y)
        {
            int ID = regionCoords.Count;
            List<Vector2> coords = new List<Vector2>();
            regionID[x, y] = ID;
            Queue queue = new Queue();
            coords.Add(new Vector2(x, y));
            queue.Enqueue(new Vector2(x, y));
            while (queue.Count > 0)
            {
                Vector2 curr = (Vector2)queue.Dequeue();
                foreach (Vector2 neighbor in (ValidNeighbors(curr)))
                {
                    if (data[(int)neighbor.X, (int)neighbor.Y] == 1 && regionID[(int)neighbor.X, (int)neighbor.Y] == -1)
                    {
                        regionID[(int)neighbor.X, (int)neighbor.Y] = ID;
                        coords.Add(neighbor);
                        queue.Enqueue(neighbor);
                    }
                }
            }
            return coords;
        }

        // returns a list of the valid cardinal direction neighbors for the given location on the grid
        private List<Vector2> ValidNeighbors(Vector2 v)
        {
            List<Vector2> neighbors = new List<Vector2>();
            if (v.X - 1 > 0)
            {
                neighbors.Add(new Vector2(v.X - 1, v.Y));
            }
            if (v.Y - 1 > 0)
            {
                neighbors.Add(new Vector2(v.X, v.Y - 1));
            }
            if (v.X + 1 < regionID.GetLength(0))
            {
                neighbors.Add(new Vector2(v.X + 1, v.Y));
            }
            if (v.Y + 1 < regionID.GetLength(1))
            {
                neighbors.Add(new Vector2(v.X, v.Y + 1));
            }
            return neighbors;
        }

        // convenience method to get the coords of the largest room on the map
        // assumes 0 == wall & 1 == open
        public static List<Vector2> GetLargestRoom(int[,] data)
        {
            CaveGridManager mgr = new CaveGridManager(data);
            List<Vector2> largest = new List<Vector2>();
            foreach (List<Vector2> list in mgr.regionCoords)
            {
                if (list.Count > largest.Count)
                {
                    largest = list;
                }
            }
            return largest;
        }
    }
}

The class above can be used a couple of different ways. The simplest to pass a rectangular int[,] to the static method & get back a list of coords as described in the original problem statement:

List<Vector2> coordList = CaveGridManager.GetLargestRoom(map);

For any given x,y location on the map, we can immediately see which room (if any) it belongs to by checking regionID[x,y]. Assuming there's a room there (that is to say regionID[x,y] >= 0) we can then immediately get all of the coords for that room by checking regionCoords[n] (where n is the ID of the room. If desired, these features can help us use the class in other ways. For instance, we could find rooms that are below a certain threshold & fill them. Or include some methods for connecting separate rooms with tunnels.

The flood fill algorithm used here is the four-way stack/queue based non-recursive implementation. It has the advantage of being relatively easy to understand and it has been optimized to check elements before committing them to the queue. It's likely to be fine for most cases, but if profiling the application reveals a problematic bottle in the flood fill code, there are some known optimizations that may help. For instance, it could be optimized further to take advantage of span filling.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .