2

I am making an asteroid generator that creates a 2D array of bools. The generator takes an int parameter, size, that should determine how many True cells will be in the 2D array.

How can I guarantee that there aren't holes in the output array and that the right amount of cells are True?

I saw the question Randomly Generating Clusters in a 2d Array, but I can't think of a way to apply it to my use case since I need to know the amount of tiles that must be generated.

In the code below, I randomly place tiles and then use cellular automata to smooth and make sure there are no holes, but keeping the right number of True cells is the problem, especially since taking out random True cells to meet the correct size would likely create holes.

def create_shape(size, seed):
    # init rng with seed
    rng = random.Random(seed)
    # initial grid values empty and full mass left
    # make the grid size by size so any shape could fit
    grid = [[False for x in range(size)] for y in range(size)]
    mass_remaining = size
    # guarantee the center is something
    center = size // 2
    grid[center][center] = True
    mass_remaining -= 1 # remember to reduce available mass
    # generate random values
    for x in range(size):
        for y in range(size):
            # skip the already filled in center
            if x == y == center:
                continue
            # assign random value
            value = bool(rng.randint(0, 1))
            grid[y][x] = value
            # remember to reduce mass
            if value: 
                mass_remaining -= 1
    # smoothen things out with cellular automata neighbor checking
    for x in range(size):
        for y in range(size):
            # skip the center
            if x == y == center:
                continue
            # get neighbors
            # set neighbors is the count of neighbors set to True
            set_neighbors = 0
            for i in range(-1, 2):
                for j in range(-1, 2):
                    # skip counting self
                    if i == j == 0:
                        continue
                    nx, ny = x + i, y + j
                    if 0 <= nx < size and 0 <= ny < size:
                        # only get in-range cells
                        if grid[ny][nx]:
                            set_neighbors += 1
            # more than 3 -> become True, less than 3 -> become False
            if set_neighbors > 3:
                grid[y][x] = True
                mass_remaining -= 1
            elif set_neighbors < 3:
                grid[y][x] = False
                mass_remaining += 1
            else:
                # otherwise leave it the same
                pass
    # find out how well the mass is staying "in-budget"
    print(mass_remaining)
    return grid

The function often prints out a whole range of different remaining mass quantities, for example, having -14 in "debt" or having 42 extra. I would expect the output to be 0 if the function worked properly.

For example, output like this ...

create_shape(8) ->

[ 0, 0, 0, 0, 0, 0,
  0, 1, 1, 0, 0, 0,
  0, 1, 1, 1, 0, 0,
  0, 1, 1, 1, 1, 0,
  0, 1, 1, 1, 1, 0 ]

... is solid, but has too many set tiles.

Gino Mempin
  • 25,369
  • 29
  • 96
  • 135
IotaHat
  • 23
  • 5

2 Answers2

2

There is no single definite answer to your problem, especially as the underlying task ("generate 2D asteroid shapes") is underspecified and fundamentally subjective. Sure, in principle you could always generate an N tile solid shape e.g. by starting from the top left corner and adding tiles from left to right and top down until you have N of them, but the resulting shape would probably not be a very realistic or "nice-looking" asteroid.

Thus, instead of describing a single algorithm in detail, I'll just suggest a few approaches that should work, and let you pick whichever seems best to you:

  • Start from a single center tile and randomly add new tiles that are adjacent to existing ones. Before adding each tile, check that adding it doesn't leave a hole inside the asteroid; if it would, pick another tile instead. (The connectivity check will probably be the most expensive part of this algorithm, although there are various ways to optimize it. In particular, you can start by only checking the existing immediate neighbors of the new tile; if they're all contiguous, the new tile cannot bridge two separate parts of the edge.)

  • Same as above, but delay the connectivity check until the end. If you find any holes, move tiles from the edge of the asteroid to the interior to fill them.

  • Apply a midpoint displacement algorithm to a circle. That is to say, use the algorithm to generate a random array of radii (with the same radius at each end) and then use those radii as distances from an arbitrarily chosen center point to the surface of your asteroid, as if you were plotting a radar graph. This won't give you an exact area of N tiles, but you can always scale the radii up or down until you get the size you want. The resulting shape will always be star-convex, and thus has no holes. (This will likely work best for fairly large N. One advantage of this scheme is that it'll generalize in a fairly straightforward and efficient way to 3D shapes as well: just start with a randomized polyhedron and apply midpoint displacement to the faces.)

  • Use any algorithm that will usually generate a hole-free asteroid. Then check if there are any holes, and if so, restart. As long as the probability of restarting is low enough, this rejection sampling method will be fairly efficient.

Ilmari Karonen
  • 49,047
  • 9
  • 93
  • 153
0

A top-down technique would be to:

Christophe Roussy
  • 16,299
  • 4
  • 85
  • 85