search

schrum2 / MM-NEAT

Modular Multiobjective (Hyper) Neuro-Evolution of Augmenting Topologies + MAP-Elites: Java code for evolving intelligent agents in Ms. Pac-Man, Tetris, and more, as well as code for Procedural Content Generation in Mario, Zelda, Minecraft, and more!
http://people.southwestern.edu/~schrum2/re/mm-neat.php
Other
50 stars 20 forks source link

Backtracking Dungeon Creation from Graph Grammar #365

Closed schrum2 closed 5 years ago

schrum2 commented 5 years ago

I think this will solve the problem with the goal placement, and will also force the dungeons to obey other placement rules that are perhaps being ignored as well.

First, this solution assumes that an inability to place a room isn't overly common. If this is true, then the dungeon can be created via a backtracking search for a complete dungeon that obeys the graph grammar. In other words, you generate a random dungeon component, see if it is legal to place it, and then only continue if you succeed. If it is impossible to place it then you can generate a new random component instead. However, it might not be possible for any component to fit, in which case you can back track.

This means that you don't only not place the current component, but you undo the placement of the preceding component as well and replace that one with a new random choice. If that works, you move forward, but if not then you back up again, potentially all the way to the placement of the first component.

This is a bit different from traditional backtracking, since it involves randomly generated components ... we don't really have a way of knowing when we've exhausted all possibilities and should therefore back track. However, I'm sure we can adapt the general idea to make this work.

jakegut commented 5 years ago

This has been implemented and will be the preferred method to generate a dungeon from the graph as it passes seeds 0 - 100. Closing.