Now Reading
How does Cave/Glade Generator Work – BorisTheBrave.Com

How does Cave/Glade Generator Work – BorisTheBrave.Com

2023-11-21 19:50:41

Watabou’s Cave Generator is one in a sequence of RPG-ready map mills that Watabou has created over time. All his work oozes fashion, however the cave generator was all the time the one I discovered most mysterious.

I found that all the factor was exported with extraordinarily readable javascript, so naturally I began to poke and prod. Let’s go over the way it works.

We’ll deal with how this map is generated for model 2.0.2:

Getting began

The principle factor to initialize are tags. These are randomly picked, however can be set by the consumer.

Tags management the later technology steps. Generally they change between totally different algorithms, however extra generally they act as presets for numeric parameters. I’ll discuss with tags like this when they’re referenced. Some tags are mutually unique – e.g. solely one in all small / medium / giant may be chosen.

Another world parameters are randomly chosen in the beginning, comparable to chamber measurement and connectedness desire for space progress. This provides every dungeon a extra constant really feel throughout the map.

Like all procedural mills, there’s a seed parameter that controls all sources of randomness. This allows permalinks for maps by storing the seed.

The hidden grid

It’s not apparent, however in actual fact the whole lot within the generator is completed on a hex grid. Let’s see the ultimate output once more, this time with all of the graphical particulars turned off – no wobbly strains, no random rocks, no water, no superimposed sq. gridlines.

Now you may see the precise specifics of the map. However how is the structure truly achieved?

Grid To Mesh

After creating the hex grid, it’s instantly transformed into a knowledge construction known as a Doubly connected edge list, which is basically a elaborate method of representing a mesh of polygons and their neighbours. Every little thing within the generator operates on this mesh information construction – it’s not tied to hexes in any respect. I used to be capable of hack in sq. grids with out a lot issue, the writer simply didn’t discover a use for this characteristic.

An output created utilizing a sq. grid

Seed Development

The vast majority of the map is generated with an algorithm known as seed progress1. It picks a random beginning location after which provides adjoining cells at random till a predetermined measurement has been met. That is then repeated to offer a number of areas. Areas should not permitted to the touch one another.

Many of the particulars of the technology are decided by tags:

The variety of areas is 9-19 for a giant map, 3-8 for a medium and 2-3 for a small. If no tags are current has a 1 in 20 probability of choosing 2 or 20, in any other case it makes use of a random method.

The scale of every space can also be a random operate. For hub generations, there may be one space of measurement 60-79, and different areas of measurement 8-13. For chamber, a random chamber measurement is chosen between 11-14, after which every space is randomly offset from that by 0-2. And for burrow, it makes use of method 10 + 80 * pow((rand() + rand() + rand()) / 3, 3) which supplies rooms round measurement 23, however often a lot bigger.

When selecting which cell so as to add to the realm, they’re weighted otherwise in line with numerous algorithms. By default, it weights every cell as pow(c, gamma) the place c is the variety of adjoining cells already within the space, and gamma is a random variable indicating the desire for connection. Excessive gamma tends to trigger rounder areas with fewer jutting items. cavities fixes the gamma of 6, whereas coral makes use of a unfavourable gamma so every space prefers slim tendrils. chaotic prefers cells with 2 connections.

coral might be essentially the most distinctive fashion.

Constructing doorways

Now its time to attach up all of the areas. First, the algorithm identifies all cells that border two parts.

The potential area-pairs are then culled. For tree, a easy depth first search ensures every space is simply reachable a single method (no loops). For linked, if it finds 3 areas all adjoining, it disconnects one pair. In any other case, all pairs are stored.

For every pair, a single door cell is randomly chosen from amongst the probabilities and added to the map.

Constructing Corridors

Some areas are randomly chosen to shrink to corridors. It prefers areas with numerous doorways for the realm, and a few tags, significantly burrows, drastically enhance the possibilities.

To shrink an space, factors are repeatedly eliminated, and flood-fill is used to make sure that the doorways are all nonetheless linked, which I describe extra in Chiseled Paths Revisited.

See Also

At this level, exits are chosen too, that are randomly chosen from eligible border cells. Cells farther from the middle get greater weights. The precise variety of exits may be managed with tags sealed, entrance, passage, junction.

Water

The water is solely an unbiased Perlin noise, which is in contrast in opposition to a threshold. It’s extra apparent in v2.1.0, the place you may play with a slider.

Tough outlines

The hexagonal nature of the partitions is hidden by way of a number of steps:

  • Each edge is subdivided
  • The define is smoothed (“bumpiness”)
  • Vertices in corridors are moved in direction of the face heart.
  • The factors are randomly offset (“irregularity”)
  • Two extra iterations of subdivision and randomness (“roughness”)
  • The boundary is transformed to curves with Chaikin’s Algorithm (not proven in gif)

Cosmetics

Some random small polygons are dropped on the map to make stones and rubble. Dyson hatching is utilized close to the boundary.

Title

The title of every map is generated utilizing a Tracery script. Many options contribute to the alternatives – “demonic” names are extra seemingly for sure tags, and the presence of water will increase the possibility of damp names like “Lavatory”.

The highest-level rule provides you an concept of what it’s like:

	"title" : [
		"#compound_noun# #noun#",
		"#adj# #noun#",
		"0.2?-#noun# of #fantasy#",
		"!LARGE&0.2?-#person#'s #noun#",
		"!SMALL&0.1?-#noun# of #epic_noun#"],

Glade Mode

Glade mode re-purposes all the generator for making forest clearings. The principle variations are the bushes randomly drawn alongside the border, and the title generator switches to a distinct script. I really like how one can change it on and see the identical map utterly re-interpreted.

Abstract

Oleg’s generator illustrates a typical maxim in procedural technology. Nice outcomes don’t come from making use of a brilliant superior algorithm, however reasonably by combining a number of easy guidelines successfully, and with an eye fixed to the look and elegance you’re aiming for.

For my part, A number of the guidelines used right here, notably seed progress, and path chiseling provide a pleasant steadiness of simplicity to helpful outcomes and are usually underappreciated as strategies.

Source Link

What's Your Reaction?
Excited
0
Happy
0
In Love
0
Not Sure
0
Silly
0
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top