This started with the idea of generating a tile-based dungeon. Rather than reading up on how others have done it, I wanted to see what I could come up with independently.
I remembered pen and paper games from my childhood like Hero Quest and Space Crusade. Space Crusade had rectangular room tiles which could be arranged in many different ways to create ship layouts. This seemed like a good starting point.
I wrote a short program which shuffles rectangular tiles on a grid to create a dungeon map using a technique called Simulated Annealing. Here's a video of the program arranging 100 rooms into a dungeon layout. It finds a solution after 254 moves. The program runs faster than the video shows - it's slowed down to make the process more visible.
The code was written in Python, using numpy matrices to represent the grid. The results are rendered using the OpenGL, and saved to disk with PIL (the Python Imaging Library).
In the real world, annealing is a heat-treatment process used on glass and metal. My understanding of real annealing is very rough, but here it goes. The material is heated up to the point where the internal structure can change more easily, but not so hot that it becomes liquid or changes shape. This allows the structure to settle naturally, which can improve the material. The goal is to make it stronger, harder less brittle, etc. The material is then cooled in a controlled way, leaving it with the new and improved structure.
But what does annealing have to do with software? Before I answer that, a quick note on heuristics.
When there is no method for solving a problem directly, and too many possible solutions to try them all in a reasonable amount of time, how can we search for an answer? Taking the dungeon layout problem as an example, the number of possible arrangements of 100 tiles on a grid is very large, so we can't just try random layouts until we stumble on a valid one.
Instead we can use a heuristic. Essentially, a "rough" method which isn't particularly clever, and may not solve the problem perfectly, but generally produces a reasonable solution. Simulated annealing is a heuristic search.
Let's start with a definition from Wikipedia:
Simulated annealing (SA) is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space.
More simply, Simulated Annealing is a method for searching for a reasonable solution when there are too many possibilities to try them all. The name "annealing" comes from the heat-treatment process, which apparently inspired the simulated annealing technique. Simulated annealing gradually improves the quality of a solution, similar to the way real annealing works on materials, and uses a "cooling" effect.
To apply simulated annealing, we first need a measure of the quality of a solution.
Next, we make small random changes to gradually improve a bad solution into a good one. If a small change would improve the quality measure of the solution, we make the change and continue. Generally, if a change would reduce the quality measure, we don't make that change.
However, for many problems, it is possible to get stuck on a solution with low quality, but which is still better than all nearby solutions. A "local optimum". Any small change from there would reduce the quality measure, so the process cannot progress through the solution space toward a good solution.
To get around this issue, simulated annealing uses an exponential cooling process. Initially, the solution has low quality and high temperature. When it is hot, there is a high random chance that we make a chosen move even if it reduces the quality measure. This allows backtracking away from local optima. As the quality increases and the system cools, the chance of accepting a "backwards" move is reduced, and only moves which improve quality are made.
First, a quality measure. A good dungeon layout has:
I used two measurements which I called "disconnectiness" and "overlappage". I'm sure they have real mathematical names, but I don't know them. Disconnectiness and overlappage are bad, so a good layout has low values - ideally zero.
We start with a random layout of rectangles on a grid. Next, we pick a change to the layout: move one room to a random location. If the changed layout would have lower disconnectiness and overlappage, it is better. We continue annealing until there is no disconnectiness or overlappage, or until an iteration limit is reached.
I originally read about Simulated Annealing in The Algorithm Design Manual by Steve Skiena. He mentions the application of PCB (Printed Circuit Board) layout, which seemed like a similar (but of course more complex) problem to laying out dungeon tiles. I've worked with engineers who use CAD tools to lay out circuit boards, and heard their opinions on automatically generated layouts (terrible and bizarre), so I was curious to see what kind of wacky dungeons simulated annealing might come up with.
I remembered pen and paper games from my childhood like Hero Quest and Space Crusade. Space Crusade had rectangular room tiles which could be arranged in many different ways to create ship layouts. This seemed like a good starting point.
I wrote a short program which shuffles rectangular tiles on a grid to create a dungeon map using a technique called Simulated Annealing. Here's a video of the program arranging 100 rooms into a dungeon layout. It finds a solution after 254 moves. The program runs faster than the video shows - it's slowed down to make the process more visible.
The code was written in Python, using numpy matrices to represent the grid. The results are rendered using the OpenGL, and saved to disk with PIL (the Python Imaging Library).
Real Annealing
In the real world, annealing is a heat-treatment process used on glass and metal. My understanding of real annealing is very rough, but here it goes. The material is heated up to the point where the internal structure can change more easily, but not so hot that it becomes liquid or changes shape. This allows the structure to settle naturally, which can improve the material. The goal is to make it stronger, harder less brittle, etc. The material is then cooled in a controlled way, leaving it with the new and improved structure.
Heuristics
But what does annealing have to do with software? Before I answer that, a quick note on heuristics.
When there is no method for solving a problem directly, and too many possible solutions to try them all in a reasonable amount of time, how can we search for an answer? Taking the dungeon layout problem as an example, the number of possible arrangements of 100 tiles on a grid is very large, so we can't just try random layouts until we stumble on a valid one.
Instead we can use a heuristic. Essentially, a "rough" method which isn't particularly clever, and may not solve the problem perfectly, but generally produces a reasonable solution. Simulated annealing is a heuristic search.
Simulated Annealing
Let's start with a definition from Wikipedia:
Simulated annealing (SA) is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space.
More simply, Simulated Annealing is a method for searching for a reasonable solution when there are too many possibilities to try them all. The name "annealing" comes from the heat-treatment process, which apparently inspired the simulated annealing technique. Simulated annealing gradually improves the quality of a solution, similar to the way real annealing works on materials, and uses a "cooling" effect.
To apply simulated annealing, we first need a measure of the quality of a solution.
Next, we make small random changes to gradually improve a bad solution into a good one. If a small change would improve the quality measure of the solution, we make the change and continue. Generally, if a change would reduce the quality measure, we don't make that change.
However, for many problems, it is possible to get stuck on a solution with low quality, but which is still better than all nearby solutions. A "local optimum". Any small change from there would reduce the quality measure, so the process cannot progress through the solution space toward a good solution.
To get around this issue, simulated annealing uses an exponential cooling process. Initially, the solution has low quality and high temperature. When it is hot, there is a high random chance that we make a chosen move even if it reduces the quality measure. This allows backtracking away from local optima. As the quality increases and the system cools, the chance of accepting a "backwards" move is reduced, and only moves which improve quality are made.
Dungeon Annealing
First, a quality measure. A good dungeon layout has:
- every room connected to at least one other room, and
- no two rooms overlapping each other.
I used two measurements which I called "disconnectiness" and "overlappage". I'm sure they have real mathematical names, but I don't know them. Disconnectiness and overlappage are bad, so a good layout has low values - ideally zero.
We start with a random layout of rectangles on a grid. Next, we pick a change to the layout: move one room to a random location. If the changed layout would have lower disconnectiness and overlappage, it is better. We continue annealing until there is no disconnectiness or overlappage, or until an iteration limit is reached.
Further Reading
I originally read about Simulated Annealing in The Algorithm Design Manual by Steve Skiena. He mentions the application of PCB (Printed Circuit Board) layout, which seemed like a similar (but of course more complex) problem to laying out dungeon tiles. I've worked with engineers who use CAD tools to lay out circuit boards, and heard their opinions on automatically generated layouts (terrible and bizarre), so I was curious to see what kind of wacky dungeons simulated annealing might come up with.
No comments:
Post a Comment