Algorithm for environmental puzzles? (Doors and switches etc.)

[Rune Skovbo Johansen]

I've been trying to come up with an algorithm for creating puzzles with doors and switches (or similar environmental puzzles) but haven't been able to find a solution.

The image at the bottom shows examples of the kind of puzzles I'm interested in. (The 3 puzzles in the image follows the same pattern I came up with that can be expanded to any number of doors, but it doesn't generalize to more varied puzzles.)

Doors and switches are just examples of elements; there could also be boulders and pressure plates and various other puzzle elements. I'm looking for something rather game-agnostic though that can be represented as a graph or similar. E.g. Sokoban puzzles are a bit too specific, in how they only work as top-down grid-based games.

Simple "locked doors and keys" structures as described on squidi.net are easy enough to do but they don't really work as proper puzzles. They can be solved by just repeatedly looking for keys to collect and doors to unlock; you don't have to give it any thought. I'm also not sure how grammar-based approaches could be used to create proper puzzles.

It seems like something that could be broadly useful - this type of puzzles are used in many different games. It also seems like a task that procedural generation should be able to handle fine, but after reading lots of papers on procedural level design and other procedural elements, I still haven't found anything that fits the bill.

This is for runtime generation by the way. I read that answer set programming can do almost anything (explored a bit here) but that it's still too slow (and memory-hungry) to generate stuff on the fly.

Do any of you have any ideas for how to approach this?

Thanks,

Rune

(Question also posted to reddit)

[Ian Badcoe]

Composing a dungeon such that the doors and keys make sense can be done using rewrite rules...

...and you can expand that with a lot of key-like/door-like generalisations.

However I am not sure that a "puzzle" is quite the same thing as a dungeon.  The only thought I have had about puzzle generation was originally about "burr" puzzles, (I have seen a write-up somewhere on automatic burr-puzzle design; search for "burr puzzle automatic generation") but the same idea generalises to sokoban etc.  For that I was thinking an evolutionary or tree-search approach, where the utility function is the number of moves in a successful solution.  It wouldn't be quick, because it would need a nested tree-search to solve each candidate, but as long as you were looking at puzzles with small number of components it could work...

...BUT not in a run-time manner such as you asked for.  Actually I can't tell exactly what you want to generate from this.  You say you want "puzzles" but then give examples that you say are insufficiently "puzzling" because they can be solved by picking up any key and opening any door.  Can you give an example of what would be a satisfactory puzzle so that I can tell what approach might achieve it.  Rewrite rules can do a lot with the right formulation...  e.g. they can do the things in your picture.

Increased puzzlingness could be achieved e.g. by multiple one-use keys of the same type, so that you have to open the doors in the right order, but it is probably still not very satisfying...

Ian


Ian

---

From: Rune Skovbo Johansen <ru...@runevision.com>
To: procedur...@googlegroups.com
Sent: Sunday, 5 January 2014, 13:48
Subject: [pcg] Algorithm for environmental puzzles? (Doors and switches etc.)

--
 
---
You received this message because you are subscribed to the Google Groups "Procedural Content Generation" group.
To unsubscribe from this group and stop receiving emails from it, send an email to proceduralcont...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Adam Smith]

Hi Rune,

You should look at the gem-and-altar example from this PCG textbook chapter on ASP: http://pcgbook.com/wp-content/uploads/2013/10/chapter8.pdf The mechanics for gems and altars (that you have to pick up the gem and put it in the altar before you can use the exit tile) aren't exactly the same as locks and keys (where bringing the lock to the key toggles traversability of the lock itself), but the difference is minor.

The important thing to get from the example comes near the end. What makes a puzzle design appropriate in that example is not just that it is solvable, but that enacting a solution implies certain unavoidable properties across all possible solutions. In the example, the property is spending a minimum amount of time/distance between each step in solving the level (finding the gem, bringing it to the altar, finding the exit). This is just an example property, and any efficiently checkable property of a solution path could replace it.

There's no new algorithm, but to customize the example to a new domain you need to:

- define a set of constraints on valid level designs (for your example: just that they have n locks and n keys over a discrete set of rooms)

- define a space of solutions for a given level design (for your example: that the solution describes a start-to-finish traversal of the map that touches locks and keys in a valid order, keys before locks)

- define a property of solutions that you want to require (for your example: that half of the rooms are touched at least once and that a quarter are touched two or more times? that the locks were opened in an order coherent with a story? that the solution path draws a certain kind of picture on a mini-map?)

From there, you've (implicitly) defined a combinatorial search problem in Sigma_2^P, and any algorithm for that class of problem is available as your content generation algorithm. Different answer set solvers use different algorithms, so they'll run in different amounts of time and use different amounts of memory. Saying ASP is too memory hungry is like saying functional programming is too memory hungry; statements at the level of programming paradigms (as opposed to specific programs in specific languages with specific runtimes) don't make sense.

If you prefer to roll your own generator for this type of problem formulation, an easy way is to glue together two simpler search algorithms that work like independent constraint solvers. I'll follow the naming convention from this paper: https://adamsmith.as/papers/fdg2013_shortcuts.pdf First, find some algorithm to play the role of Elise, the level designer. You could use a SAT solving algorithm like DPLL or a Feasible-Infeasible constraint solving genetic algorithm. To play the role of Fiona, the design assistant, you could use plain old A* to search for solutions (depending on what solution property you are trying to required). Plug these together in a generate-and-test process, and you've got yourself a (possibly approximate) solver for anything in the relevant class of problems. If something is to slow... precomputation, caching, sampling, and learning are possible roads to investigate next.

If you take anything specific away from this email, it should be to focus on how to define your problem (as opposed to how to design an algorithm). While you can heuristically judge the quality of a project-specific content generation algorithm by eyeballing example outputs, this approach doesn't work when trying to develop generic tools (where a quirky stylistic bias of an algorithm in one game might mean a pace-ruining bias in another game).

Adam

[Rune Skovbo Johansen]

Hi Adam,

Thanks for the reply. I've been meaning to give the Potassco project tools a try when I get some time for it; if nothing else then to learn about procedural generation from another angle than I'm used to. I've heard independently from several people that ASP programming is too slow and memory intensive for runtime generation, but of course the specifics depend on the problem at hand. But that said, I need a solution that works in C# for my own purposes, and you said on twitter back in June that "Most ASP solvers are in C++, so you'd have to try Google's PNaCl or Emscriptem to get them into a browser-based game." - which is not really an option for me, since I'm using Unity and need a pure C# solution.

As for how to define the problem, I'm beginning to gain an understanding of what probably makes a puzzle feel like a puzzle. I'm working on a Puzzle Graph framework and tool to define environmental puzzles in the form of graphs with different types of nodes and edges. An edge could be a locked gate and some node could be a pressure plate that opens the gate if you roll a boulder onto it, and things like that. The state of the graph and changes to the state are defined in a strict way that makes it possible to search the state space for the graph. The state space is a graph in itself - often much larger than the graph of the puzzle itself.

Now, with this state space graph available it's possible to find the shortest solution path and other things. By doing a depth first search and marking states as dead ends if they either lead to no other states or back to already explored states, we can get an overview over how long the shortest solution path is; if there's more than one solution, and how many dead ends there are, and how long they are (= how many state changes they involve). I design the puzzle graphs such that there are preferably not two nodes that are trivially connected with an always accessible edge - such two nodes can just as well be collapsed to a single one. This helps pruning "filler" state changes form the state space which don't add any real complexity anyway.

The theory I'm working with is that a puzzle feels like an actual satisfying puzzle if there are multiple non-trivial dead ends in the state space, where non-trivial means they are longer than a few state changes long. I tried to model a puzzle in the framework over a puzzle from the game Lara Croft and the Guardian of Light (graph pictured in the attached image) and when I analyzed it, I found that the solution path was rather long and there were at least a handful long dead ends. In contrast, a "key and door" binary tree as described on squidi.net always have no non-trivial dead ends regardless of the number of doors and keys. It's basically just one long solution path.

I also analyzed the middle puzzles from the image in my first post in this thread, and found that it peculiarly had one long solution and only one long dead end. Basically, if you happened to make the right move from the beginning you'd go down a route to the solution more or less automatically, while if you made the wrong move from the beginning, you'd go down the route of a dead end. That makes for an peculiar kind of hit-and miss puzzle experience that's probably not very desirable.

The good thing about this definition for a "good" puzzle is that it's very general and could be applied to a very large variety of puzzles. If the number and lengths of dead ends can be controlled, it would also be easy to control the difficulty that way, by specifying more difficult puzzles as having more dead ends, and longer solution path(s) and dead ends. I don't know enough about ASP to know if it's a viable kind of criteria to use there but I'm guessing it probably is.

The Puzzle Graph framework and tool is still a work in progress, but the plan is to make it freely available once it's in a usable state.

Rune

[Julian Togelius]

That's an interesting definition of what makes something feel like a
puzzle, but I think it risks encompassing a bit too much. To begin
with, almost any labyrinth or maze with a reasonable branching factor
would be a satisfying puzzle according to this definition, as there
are many non-trivial dead ends in state space, namely the dead ends in
the maze. Maybe you are looking for problems where dead ends in action
space outnumber dead ends in physical space? This implies that it is
not enough to get to the right place, but you also need to get to the
right place in the right sequence.

Given that you have a function for measuring the puzzle-ness of a
problem/environment/level, you could easily adopt a search-based
approach. (Of course, you all knew I was going to say this...) Simply
use your puzzle-ness function as an evaluation function. ASP might be
better for this problem, but I'm pretty sure evolution would work as
well, and whatever works works.

> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "Procedural Content Generation" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to proceduralcont...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.



--

Julian Togelius
Associate Professor
IT University of Copenhagen
Rued Langgaards Vej 7, 2300 Copenhagen, Denmark
mail: jul...@togelius.com, web: http://julian.togelius.com
mobile: +46-705-192088, office: +45-7218-5277

[Rune Skovbo Johansen]

Replies inline below.

On 17 January 2014 18:59, Julian Togelius <julian....@gmail.com> wrote:

That's an interesting definition of what makes something feel like a
puzzle, but I think it risks encompassing a bit too much. To begin
with, almost any labyrinth or maze with a reasonable branching factor
would be a satisfying puzzle according to this definition, as there
are many non-trivial dead ends in state space, namely the dead ends in
the maze.

Well, you could think of a maze as a kind of puzzle where the physical navigation is what's tricky about it. In this case the evaluation of dead ends in the state space will work fine for evaluating the puzzle-ness and difficulty of the maze.

If instead you're interested in a puzzle that's not about physical navigation, then you can collapse all always-connected nodes before performing the evaluation, like I mentioned. In this case a classic maze would collapse into a single node and the evaluation would show zero dead ends.

So partly, it's a matter of how you choose to represent your puzzle as a graph, and making sure that the graph encompasses only the information you're interested in.

 

Maybe you are looking for problems where dead ends in action
space outnumber dead ends in physical space? This implies that it is
not enough to get to the right place, but you also need to get to the
right place in the right sequence.

Yes, I agree something like the ratio of state space dead ends to physical dead ends, or physical nodes, would be a good extra rule in the evaluation. Even when collapsing always-connected nodes, it would still be possible to construct puzzles where each node is only visited once, and a rule like this would prevent that.

 

Given that you have a function for measuring the puzzle-ness of a
problem/environment/level, you could easily adopt a search-based
approach. (Of course, you all knew I was going to say this...) Simply
use your puzzle-ness function as an evaluation function. ASP might be
better for this problem, but I'm pretty sure evolution would work as
well, and whatever works works.

The problem here is that the evaluation takes enough time (I didn't time it but maybe 50 ms for a good puzzle on my computer?) that repeating it hundreds of times as part of a puzzle generation isn't an option for fast runtime generation.

What I really hope exists is an algorithm that generates good (or at least valid) puzzles as an integral part of the algorithm rather than needing an iterative test and refine approach. The locked door and keys structure for levels can be done like this, taking any binary tree as input, but the result just isn't proper puzzles. It's conceivable though that an algorithm can be constructed that generates more proper puzzles as well, without needing constant evaluation.

Rune

[Adam Smith]

"By doing a depth first search and marking states as dead ends if they either lead to no other states or back to already explored states, we can get an overview over how long the shortest solution path is"

Be aware that the dead ends that you find in a process like this will be very sensitive to the order in which you visit the decedents of any given node. In the image below, I've taken a made up space and sketched out the graph that depth-first search might uncover, following a right-hand rule. The starting node is marked S, and the very last node visited in the search is marked F (which happens to very close to the start in this run). Whether the grid represents real space or abstract state space isn't important.

If you rotate the map ninety degrees or flip it vertically, you get very different results. In this case, there are very few actual dead-ends in the space, and most of those identified are simply artifacts of exploration order.

Because of this phenomenon, I haven't been able to make effective use of properties of search trees in my puzzle design efforts. It's tempting to define difficulty as a function of branching factor and recursion depths, but something like raw DFS simply can't report metrics you need from a single run. I suppose you could get marginalized statistics from many many runs with a random tie-breaking strategy. At least then you are orientation invariant. However, these average metrics are only one summarization of a large possibility space from which the player is going to see one concrete realization (which might be very far from the average metrics).

This keeps pointing me back to the idea that you have to have some sort of goal for what the player should actually see or do on a valid path (as opposed to metrics over spaces or combinations of actions they don't try), and then design to make that goal unavoidable in the process of solving the puzzle.

--

[Rune Skovbo Johansen]

Oops, when I said depth first search, I meant breadth first search... Bad mistake to type that wrong, since this makes a big difference.

With breadth first search, exploration order will still make differences in which paths are makes as dead ends and which are marked as part of the solution (or a different dead end) when two alternative paths that lead to the same state are equally long, but at least the differences shouldn't make a difference to the statistics of the numbers and lengths of paths.

Rune

---
You received this message because you are subscribed to a topic in the Google Groups "Procedural Content Generation" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/proceduralcontent/bFTkuSv2EUE/unsubscribe.
To unsubscribe from this group and all of its topics, send an email to proceduralcont...@googlegroups.com.

[Cameron Browne]

Hi Rune,

Thinkfun used the following metric when generating a new batch of Rush Hour puzzles: prefer challenges with both a long and a short path to solution (among other undisclosed metrics): http://www.thinkfun.com/microsite/rushhour/creating2500challenges

They deemed a challenge more likely to have more depth or replay value if the player was likely to find an easy (but inefficient) solution, but had to look harder for the optimal solution. Such optimal solutions would often involve a "trick" that required some insight on the player's part.

Don't know whether this is relevant to your case, but may be worth checking out.

Regards,

Cameron

[Rune Skovbo Johansen]

Hi Cameron,

Thanks for the link to the article - that's very interesting!

The article mentions that "I was looking especially for challenges that were simple to solve, but tricky to find the best solution" and implies that they did manage exactly that. I assume that means there's a solution with many steps that's easy to find and a different solution with fewer steps (hence "better") which is nevertheless harder to find.

This is interesting since currently I have only been operating with the assumption that more steps = more difficult, so that if the same puzzle contained multiple solutions, the one requiring fewer steps would be the simpler one. While I'm not surprised this is not always the case in practice, I'm very curious how they assess the difficulty of a solution when not just given based on the number of steps performed.

They mention that their "virtual player" can look three steps forward, but I can only make sense out of that if it's combined with some heuristic of how close a given state is to the goal state. More difficult puzzles would then perhaps be puzzles that require going though low-scoring states - similar to a maze where the solution path requires going in the direction away from the goal. If that's a correct interpretation of their method, then I'm curious what their state scoring heuristic is and whether it's underlying principle can be transferred to other types of puzzles.

Rune

[Bedrich Benes]

Hi Rune,

Paul Merrell had some very interesting papers on procedural modeling that are related to your problem.

I suggest this web: http://graphics.stanford.edu/~pmerrell/  

best regards

----

Bedrich Benes

Associate Professor of Computer Graphics Technology

Purdue University

http://hpcg.purdue.edu/bbenes

[Rune Skovbo Johansen]

Hi,

I'm digging up this old thread just to mention that the PuzzleGraph tool that I mentioned I had begun working on is now released, free and open source.

Article: http://www.gamasutra.com/blogs/RuneSkovboJohansen/20160406/269732/Working_with_puzzle_design_through_state_space_visualization.php
Video: https://youtu.be/NeTjbfAbNyA
Tool itself: https://runevision.itch.io/puzzlegraph
Source code: https://bitbucket.org/runevision/puzzlegraph

It's not procedural generation as such, but as discussed in this thread, might be an interesting foundation to build procedural puzzle generation on top of, though I didn't get far with that myself so far.

Rune

[Ian Badcoe]

Hi,

Are you aware of the facebook group also devoted to PCG topics?

https://www.facebook.com/groups/procgen/

That would be another good place to post this...

---

This is very cool.

Somewhere down the list you'll find some posts were I was talking about some possibilities for graph-based level generation, where one starts with a simple trivial seed graph (entrance -> X -> exit) and randomly chooses rewrite rules to complexify it iteratively.

The point I have got to is where on non-cyclic graphs, point-based rewrites can generate guaranteed-solvable door/key systems of arbitrary complexity.  When the level contains cycles, however, the problem becomes more difficult.  Two failure modes become possible:

1) puzzle is interesting but player can got the other way and walk around it

2) each branch of the cycle contains a puzzle and they mutually block each other

I've been considering a couple of approaches to conquering this limitation.  Neither was quite like yours as neither was a whole graph analysis, however I did also have some approach like yours in the back of my mind as the "completely general" solution.  My two ideas where:

1) I could generate more sophisticated re-write rules that accommodate cyclic graph input without invalidating the graph (see my mail on "graph rewriting" a few months back...)

2) I could lay-out all the order-dependent level components (doors, keys etc) in phase#1 where there are no cycles.  Then in phase#2 introduce cycles in such a way that they don't change the parts of the topology that phase#1 mechanisms relied on

The completely general solution, which might incorporate something like your technique, would be simpler:

1) from a valid graph

2) make any arbitrary edit

3) analyse the state-space, if invalid revert to previous graph

4) goto 1

But the problem with this is that it could be very inefficient, and involve a lot of attempted edits that fail.

There is also the risk of incorporating features in early successful edits which block so many future edits that reaching a desired target complexity becomes impossible...

--

I imagine scale is something of a problem, however?

e.g. I imagine that the typical number of state nodes has a something like N*2^X dependency on the input size (N = basic number of nodes and X = number of switchable nodes) for a level with a hundred locations and ten doors this will quickly become intractable...?

One approach might be to simplify the full graph into only those parts that matter for the analysis.  e.g. any simply-connected sub-graph of nodes can be reduced to a single node...

But obviously this won't help where the complexity stems from functional puzzle nodes.  Could one decompose the level into sub-puzzles that solve separately; or semi-separately, e.g. in the sense that puzzle-a requires solving puzzle-b, but there is nothing in the state changes required for puzzle-b that depends on any state required for puzzle-a, thus puzzle-b can be solved as an orthogonal problem to puzzle-a and the only requirement of puzzle-a on puzzle-b is its 1-bit solution state...?

Ian

---

From: Rune Skovbo Johansen <ru...@runevision.com>

To: Procedural Content Generation <procedur...@googlegroups.com>
Sent: Thursday, April 7, 2016 11:04 PM
Subject: Re: [pcg] Algorithm for environmental puzzles? (Doors and switches etc.)

Hi,

I'm digging up this old thread just to mention that the PuzzleGraph tool that I mentioned I had begun working on is now released, free and open source.

Article: http://www.gamasutra.com/blogs/RuneSkovboJohansen/20160406/269732/Working_with_puzzle_design_through_state_space_visualization.php
Video: https://youtu.be/NeTjbfAbNyA
Tool itself: https://runevision.itch.io/puzzlegraph
Source code: https://bitbucket.org/runevision/puzzlegraph

It's not procedural generation as such, but as discussed in this thread, might be an interesting foundation to build procedural puzzle generation on top of, though I didn't get far with that myself so far.

Rune

On Friday, January 17, 2014 at 6:49:01 PM UTC+1, Rune Skovbo Johansen wrote:

Hi Adam,

Thanks for the reply. I've been meaning to give the Potassco project tools a try when I get some time for it; if nothing else then to learn about procedural generation from another angle than I'm used to. I've heard independently from several people that ASP programming is too slow and memory intensive for runtime generation, but of course the specifics depend on the problem at hand. But that said, I need a solution that works in C# for my own purposes, and you said on twitter back in June that "Most ASP solvers are in C++, so you'd have to try Google's PNaCl or Emscriptem to get them into a browser-based game." - which is not really an option for me, since I'm using Unity and need a pure C# solution.

As for how to define the problem, I'm beginning to gain an understanding of what probably makes a puzzle feel like a puzzle. I'm working on a Puzzle Graph framework and tool to define environmental puzzles in the form of graphs with different types of nodes and edges. An edge could be a locked gate and some node could be a pressure plate that opens the gate if you roll a boulder onto it, and things like that. The state of the graph and changes to the state are defined in a strict way that makes it possible to search the state space for the graph. The state space is a graph in itself - often much larger than the graph of the puzzle itself.

Now, with this state space graph available it's possible to find the shortest solution path and other things. By doing a depth first search and marking states as dead ends if they either lead to no other states or back to already explored states, we can get an overview over how long the shortest solution path is; if there's more than one solution, and how many dead ends there are, and how long they are (= how many state changes they involve). I design the puzzle graphs such that there are preferably not two nodes that are trivially connected with an always accessible edge - such two nodes can just as well be collapsed to a single one. This helps pruning "filler" state changes form the state space which don't add any real complexity anyway.

The theory I'm working with is that a puzzle feels like an actual satisfying puzzle if there are multiple non-trivial dead ends in the state space, where non-trivial means they are longer than a few state changes long. I tried to model a puzzle in the framework over a puzzle from the game Lara Croft and the Guardian of Light (graph pictured in the attached image) and when I analyzed it, I found that the solution path was rather long and there were at least a handful long dead ends. In contrast, a "key and door" binary tree as described on squidi.net always have no non-trivial dead ends regardless of the number of doors and keys. It's basically just one long solution path.

I also analyzed the middle puzzles from the image in my first post in this thread, and found that it peculiarly had one long solution and only one long dead end. Basically, if you happened to make the right move from the beginning you'd go down a route to the solution more or less automatically, while if you made the wrong move from the beginning, you'd go down the route of a dead end. That makes for an peculiar kind of hit-and miss puzzle experience that's probably not very desirable.

The good thing about this definition for a "good" puzzle is that it's very general and could be applied to a very large variety of puzzles. If the number and lengths of dead ends can be controlled, it would also be easy to control the difficulty that way, by specifying more difficult puzzles as having more dead ends, and longer solution path(s) and dead ends. I don't know enough about ASP to know if it's a viable kind of criteria to use there but I'm guessing it probably is.

The Puzzle Graph framework and tool is still a work in progress, but the plan is to make it freely available once it's in a usable state.

Rune

On 17 January 2014 01:38, Adam Smith wrote:

Hi Rune,

You should look at the gem-and-altar example from this PCG textbook chapter on ASP: http://pcgbook.com/wp- content/uploads/2013/10/ chapter8.pdf The mechanics for gems and altars (that you have to pick up the gem and put it in the altar before you can use the exit tile) aren't exactly the same as locks and keys (where bringing the lock to the key toggles traversability of the lock itself), but the difference is minor.

The important thing to get from the example comes near the end. What makes a puzzle design appropriate in that example is not just that it is solvable, but that enacting a solution implies certain unavoidable properties across all possible solutions. In the example, the property is spending a minimum amount of time/distance between each step in solving the level (finding the gem, bringing it to the altar, finding the exit). This is just an example property, and any efficiently checkable property of a solution path could replace it.

There's no new algorithm, but to customize the example to a new domain you need to:

- define a set of constraints on valid level designs (for your example: just that they have n locks and n keys over a discrete set of rooms)

- define a space of solutions for a given level design (for your example: that the solution describes a start-to-finish traversal of the map that touches locks and keys in a valid order, keys before locks)

- define a property of solutions that you want to require (for your example: that half of the rooms are touched at least once and that a quarter are touched two or more times? that the locks were opened in an order coherent with a story? that the solution path draws a certain kind of picture on a mini-map?)

From there, you've (implicitly) defined a combinatorial search problem in Sigma_2^P, and any algorithm for that class of problem is available as your content generation algorithm. Different answer set solvers use different algorithms, so they'll run in different amounts of time and use different amounts of memory. Saying ASP is too memory hungry is like saying functional programming is too memory hungry; statements at the level of programming paradigms (as opposed to specific programs in specific languages with specific runtimes) don't make sense.

If you prefer to roll your own generator for this type of problem formulation, an easy way is to glue together two simpler search algorithms that work like independent constraint solvers. I'll follow the naming convention from this paper: https://adamsmith.as/ papers/fdg2013_shortcuts.pdf First, find some algorithm to play the role of Elise, the level designer. You could use a SAT solving algorithm like DPLL or a Feasible-Infeasible constraint solving genetic algorithm. To play the role of Fiona, the design assistant, you could use plain old A* to search for solutions (depending on what solution property you are trying to required). Plug these together in a generate-and-test process, and you've got yourself a (possibly approximate) solver for anything in the relevant class of problems. If something is to slow... precomputation, caching, sampling, and learning are possible roads to investigate next.

If you take anything specific away from this email, it should be to focus on how to define your problem (as opposed to how to design an algorithm). While you can heuristically judge the quality of a project-specific content generation algorithm by eyeballing example outputs, this approach doesn't work when trying to develop generic tools (where a quirky stylistic bias of an algorithm in one game might mean a pace-ruining bias in another game).

Adam

--

---
You received this message because you are subscribed to the Google Groups "Procedural Content Generation" group.
To unsubscribe from this group and stop receiving emails from it, send an email to proceduralcont...@googlegroups.com.
For more options, visit

https://groups.google.com/d/optout

.