Room Technology utilizing Constraint Satisfaction
Room Technology utilizing Constraint Satisfaction
Two weeks in the past, I used to be a part of Roguelike Celebration and gave a chat on room technology utilizing constraint satisfaction. It was nice! Right here is the video of my discuss:
I don’t know why however the sound is a bit jerky at instances. 🙁 And with my horrible accent, it will not be straightforward to grasp sure components. So I’ll transcript the discuss on this article.
Earlier than we begin, you may get the demo code that accompanies the discuss on my GitHub account and the slides here.
So let’s begin by defining, what’s a room generator.
| Earlier than | After |
|---|---|
|
 |
The enter is solely any construction, it may be a constructing, a dungeon, something. And it doesn’t matter what algorithm generated it. Because it appears to be like desperately empty, we wish to fill the construction with objects, decorations and monsters. That’s what’s room technology.
| Earlier than | After |
|---|---|
 |
 |
| Earlier than | After |
|---|---|
 |
 |
It really works for buildings, nevertheless it additionally works properly for caves or dungeons.
 |
 |
And even for outside constructions just like the ruins on the left, or for the market place on this village.
The generator relies on constraint satisfaction problems that I’ll abbreviate as CSP.
A CSP consists of three issues:
- There are variables which in room technology will characterize the objects to put within the room.
- There’s a area for every variable. They’re the finite units of doable values for every variable. In room technology, the domains are merely all of the doable positions for every object.
- There are the constraints, that are predicates on the values taken by the variables. In room technology, we might require that objects don’t overlap, that there are paths to entry objects or we might want particular objects to be in opposition to a wall or in a nook.
Fixing a CSP is simply discovering an task that satisfies all of the constraints.
We will discover two issues. First, it’s very intuitive to make use of. If we wish to have a bathe subsequent to a wall, we simply have so as to add a constraint to take action. And now we have sturdy ensures on the output, which is all the time a pleasant factor in procedural technology.
Now, let’s see the essential algorithm to unravel a CSP. It’s known as the “Backtracking Algorithm”.
That is only a refined brute pressure method, we’ll enumerate all of the doable assignments by recursively assigning the variables one after the opposite.
The one subtlety is that every time we attempt to assign a variable, we test the constraints, if they’re glad we transfer to the following variable with a recursive name. But when the constraints aren’t glad or the recursive name fails, we transfer to the following worth within the area. And if there is no such thing as a worth left within the area, we backtrack to the earlier variable.
def clear up(i, task):
if i >= n:
return True
for worth in domains[i]:
task[i] = worth
if check_constraints(i, task):
if clear up(i + 1, task):
return True
return False
It’s easy as you may see it’s lower than 10 strains of code. And, it really works very properly, if there’s a answer to the issue, it would discover it. And with the constraints that I’m presenting right here, it is usually very quick.
However as we all the time strive the values in the identical order, the solver is deterministic and can all the time output the identical answer. Not splendid for a procedural generator.
Nevertheless, it is extremely straightforward to repair this downside.
We simply need to shuffle the domains every time we wish a brand new room.
In case you are utilizing an exterior library to unravel your CSPs, simply ensure that the choice strategy of values in domains is random.
Discover that the order through which the variables are processed doesn’t matter. And it doesn’t should be random.
In reality, there’s a heuristic known as “Minimal Remaining Worth” that may velocity up the solver considerably. It consists in assigning the variables with smaller domains first as a result of they’re extra constrained than the others.
The construction of the room is solely represented as a 2D or a 3D grid.
A 3D grid could be helpful even for a 2D sport. For instance, in my sport, I exploit a 3D grid with three layers to have the ability to have objects above others.
Cells on this grid could be in three totally different states:
- The empty state, when a cell is free and may obtain an object. These are the black tiles on the images.
- The margin state when a cell is free and we wish it to stay free. These are the gray tiles on the images. We will discover that the connections to the opposite rooms are margin cells to ensure that these tiles stay free.
- The full state when a cell is already bodily occupied by an object or a wall. These are the white tiles on the images.
We may additionally wish to add extra information to a cell like marking it as a wall or a door which can be helpful for sure constraints.
First, I discover it extra helpful if a variable can characterize not just one object however a gaggle of objects. For instance, a desk with two chairs.
We may do this through the use of a number of variables and constraints to pressure the objects to be subsequent to every others. However it will make the CSP way more complicated and tough to unravel for no good purpose.
Then, I specify a collision field which is the bodily area that the objects will occupy.
And a margin field which would be the area across the objects that might want to stay free for gameplay or aesthetic causes.
For instance, we wish area in entrance of the forge to ensure the gamers can entry it.
Lastly, I added the assist for optionally available boolean masks for the 2 bins to have the ability to add finer particulars if wanted. As you may see with the counter.
I specify the lists of objects for my rooms in JSON and here’s what appears to be like just like the definition of a variable.
{
"objects": ["Painting1", "Painting2", ...],
"constraints": [
{
"NextToWallConstraint": {}
}
],
"vary": [1, 3]
}
First, we will discover that for a given variable I pattern amongst an inventory of objects. Within the instance, I wish to add a portray within the room and I select amongst an inventory of them.
Then, let’s observe that the extra we add variables to the CSP, the tougher it will likely be for the solver to discover a answer. And there are some objects like decorations, if the solver fails to put them, it’s not a giant deal, the room stays legitimate.
So I separate the objects in two lists. The required objects that are the objects that the solver wants to put, in any other case the room loses its which means.
And the optionally available objects, the solver will attempt to place them after the required objects however it would simply strive every worth of their domains as soon as and don’t backtrack if it fails to put an object.
What’s good with optionally available objects as they aren’t required, we will make them extra random with for instance a likelihood of look or a random rely. For instance, the work have a spread attribute and the solver will attempt to place between one and three within the room.
I’ll stress extra on that on the finish of the discuss however optionally available objects are very helpful so as to add variability within the generated rooms.
Let’s look rapidly at among the constraints.
The only constraints are the unary constraints. They’re the constraints that take care of just one variable.
For instance, you need an object to be at a sure distance to a wall or in a nook.
The technique for these constraints is simply to take away the values within the area that don’t fulfill the constraint earlier than working the solver.
 |
 |
So in case you add a constraint that an object must be in opposition to the north wall, the area can be solely the purple cells of the primary row. And in order for you the article to be in a nook, the area can be solely the 4 purple cells within the corners.
The 2 subsequent constraints are so vital for room technology they usually should be applied effectively that I baked them straight within the solver.
To rapidly test the overlap between objects, we’ll simply reuse the grid we obtained as enter however we’ll replace it after every task or backtracking. After an task, we add the article, and after a backtracking, we take away the article.
The connectivity constraint implies that every one the free cells should be reachable.
You may test that utilizing a easy depth-first search algorithm. However you would wish to run the DFS after every task which may very well be very costly.
There’s a little trick that may assist so much.
 |
 |
If we have a look at the tiles across the object we simply positioned, and the free tiles are in a single piece, then we’re certain that the room remains to be related.
 |
 |
|---|---|
| Don’t disconnect | Do disconnect |
Nevertheless, if the encircling is in two or extra items then, we might have disconnected the rooms and we have to run the costly DFS to test. This heuristic can save us a lot of the DFS calls.
To this point so good however now we have a problem and it has a reputation, it’s known as the “10’000 bowls of oatmeal Drawback”.
It says that we will very simply generate loads of bowls of oatmeal by simply altering the place or the rotation of every oat, however they may all look the identical.
In our case:
- the bowl is the room.
- the oatmeal is the objects.
And as you may see on the image, if we use the identical enter, the solver simply transfer the objects within the rooms and we get a really related output.
The answer to the ten’000 bowls of oatmeal downside is in fact, as all procedural technology practitioners know, to generate totally different bowls. Totally different shapes of bowls, totally different colours of bowls. And that manner, all of the bowls are totally different!
In fact, I’m kidding however there may be an thought there to mitigate the difficulty.
In the event you change the context through which the objects are seen, the sample could also be much less recognizable.
You may play on the form of the construction, the textures, the skins of objects, and so on.
However the true answer to the ten’000 bowls of oatmeal downside is in fact to vary the inputs.
First, don’t overuse a room template. Specifically, keep away from utilizing the identical room template for 2 rooms shut to one another.
Then, use various and optionally available objects. As defined, it helps so as to add variability within the room templates. That’s what we will see on the animation.
One of the best answer is to have a better stage generator to generate the inputs to make the room very totally different or in order that they’ve extra which means.
For instance, perhaps you must generate a home for a personality. And you’ve got already generated the hobbies for this character. Let’s say he’s keen on astronomy. That might be good, in case you can inject this which means into the room generator and place a telescope in the home.
One good and easy technique to obtain this, that I’m utilizing in my sport, is to make use of tags and triggers.
Your different mills will generate a context which is only a bag of tags. In our instance, it would comprise the tag “hobby_astronomy”.
{
"objects": ["Telescope"],
"set off": "hobby_astronomy"
}
Then, within the object description, you simply add a set off that may add the article provided that the given tag is within the context.
That manner, your mills are solely loosely coupled. And in case you want it you may make extra superior circumstances on your triggers utilizing propositional logic.
To conclude, I might say the utilizing CSP in your mills is straightforward to purpose about and simple to implement. However watch out of the ten’000 bowls of oatmeal situation.
Listed here are some references if you wish to go additional in among the subjects we handled:
In case you are all for my adventures in the course of the growth of Vagabond, you may comply with me on Twitter.