5
\$\begingroup\$

I'm doing 2d topdown procedurally generated world. I'm generating perlin height values, and when certain value is crossed I'm generating one level higher, while edging biomes creates cliff of the mountain. Cliffs cannot be crossed so now I'm curious how would I do access to the generated mountain. I've got stairs tiles but I need help finding proper way of finding correct place on the mountain to actually generate them.

This is what mountain could look like :

enter image description here

Obviously stairs can be generated only on places where mountain is facing down(where the cliff is). I'm not sure when is ideal time to actually do this. During generating perlin or when rendering cliff(but then there is problem to find correct spot in the mountain to generate them. Also There should be only some stairs in the mountain not in every single cliff facing down.

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

There may be a way to do this more simply during the conversion from noise to tiles, but here's a sketch of a way that could work starting from the tiles:

If, for each ring of cliffs, we had an array containing the coordinates of the downward facing edge tiles of that that ring, then it would be easy to just pick a random one of those and replace it with stairs.

If, for each ring of cliffs, we had an array containing the coordinates of the all of the edge tiles, then it would be easy to filter to just the downward facing ones.

So, If we can get, for each ring of cliffs, an array containing the coordinates of the all of the edge tiles then we'd know what to do. That's the hard part.

A conceptually simple method to get those rings is to first scan over all the tiles and collect the coordinates for the downward facing tiles.

Then, for each of those tiles have a loop look starting from that tile and looking in all directions for tiles that are part of the ring, (that is, the tile is any of the edge tiles) collecting the results into an array. This is similar to a standard flood-fill algorithm, but instead of painting a tile, push it into the ring.

As described you'll end up with many duplicate rings, so you can sort the coordinates in order to make them exactly the same and then remove the duplicates.

You should now have one array for each ring, which you can then filter down to the downward edges, and then randomly choose a place from that filtered list, as described above.

There's several places this could be sped up if needed, by reducing duplicate work, but that could be a separate question. Plus, once a slow version is implemented, you can write a faster version and confirm the results are the same on an example.

\$\endgroup\$
2
\$\begingroup\$

We can simplify Ryan1729's method (getting rid of the rings and sorting) like so:

  1. Choose any tile that is not a downward-facing cliff as the start of a flood fill. Mark it visited and add it to an "open set".

  2. While the open set is non-empty, remove a tile from the open set. For each of its neighbouring tiles not yet marked as visited...

    • If the neighbour is a downward-facing cliff, mark it visited and add it to a "cliff list".

    • If the neighbour is at a different elevation, skip it.

    • Otherwise, mark it visited and add it to the open set.

  3. Once you empty the open set, you've visited every tile that can be reached without crossing a cliff. Now it's time to punch some holes. Iterate over your cliff list in a random order...

    • If the cliff has no unvisited neighbour above or below (ie. either both already visited, or it borders the edge of the map), remove it from the list and keep going - it's not needed to expand our reachable area.

    • When you find a cliff with an unvisited neighbour above or below, convert it to stairs, and add the unvisited tile it borders into your open set.

    • Doing this just once will give you a single entrance leading up each hill / down into each valley. Instead, you could randomly select some fraction of the cliff tiles with this property to convert to stairs (possibly checking that they're not already next to another stairway if you want to avoid clumps)

  4. Once you've converted at least one cliff to stairs, loop back to 2, since our open set is non-empty again.

  5. Once the open set and the cliff list are both empty, we've visited every cell in the map and punched holes in cliffs so that every hill or valley is connected.

\$\endgroup\$

You must log in to answer this question.

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