Randomly generated map with 10 rooms, 40% chance of adding a connection between neighboring rooms if one isn't there already.

Articulation points and bridges in the graph are highlighted in red; these are useful to know for puzzle generation purposes. The analysis algorithm is apparently flawed because one of the rooms isn't highlighted that should be, but that's probably an easy fix once I add a seed mechanism so I can recreate the same graphs over and over.

Gambrinus wrote:

Creating a roguelike?

Not sure if that, or a hack-n-slash. I'm calling it a Runtlike.

This one is better; I fixed the problem with detecting some articulations and bridges. 20-room map, same 40% chance of additional connections.

Lummox JR wrote:

This one is better; I fixed the problem with detecting some articulations and bridges. 20-room map, same 40% chance of additional connections.

So keen for this. Be sure to keep us up to date :-)

Definitely want all the details.

That's just regular text mode in Dream Seeker. I'm looking to make this a graphical game, but text mode is useful for analyzing the map.

The core I've got so far is just the big-picture map generation stuff you see here, with puzzle generation coming next. I want to figure out a satisfying way of adding puzzles so that the user is forced to explore much of the map, possibly also including secret areas that don't contain puzzle keys. This is why I needed to do analysis of articulation points and bridges in the graph.

Bridges are of course natural puzzle choke points. These can be represented by locked gates or guarded passes in the room the player encounters before the bridge. (This kind of analysis BTW can be done for maps that look nothing like Runt. If you wrote an algorithm to map out a castle interior, and could convert the rooms into a graph representation, you could use the same graphing algorithms for puzzle generation.) Articulation points might not be as useful to know, except that you know if a user is going to eventually have access to the whole map, they will have to be in those rooms, regardless of puzzles. Putting a tougher creature in some percentage of them to up the danger factor would be sensible.

For puzzle generation, my goal is to start the player near the center, or near the center of a large independent chunk of the map (e.g., if there's a bridge that splits it nearly in half I'd just look for the center of the first half) and use dead ends as key or treasure locations as much as possible. Ideally puzzles should be encountered before keys, and far apart on the map from each other. I'll need a puzzle dependency graph, because where puzzles open up different map areas via bridges I'll have to mark each section of the map as whether it's dependent on that puzzle; in that way I can avoid putting a key before the puzzle that unlocks access to it. Not all puzzles need be bridges either; I can stick a puzzle in a room which could be something like a chest that requires a certain key, an NPC wanting a trade (if I go that route), a statue missing a doodad, etc.

BTW, I discovered something in the making of this that I'll be fixing in the parser in 512. Specifically this line in my code:


The goal of this was to assign the x and y vars before calling GetRoom(). This didn't work the way I was expecting it to with chained assignments, and the reason was that I derped out and forgot DM would interpret that as a named argument list. But sometimes doing the assignment is desirable. I thought the best way to do that would be to enclose the assignments in parentheses, but of course the parser doesn't actually recognize any distinction. So, I had to make a few tweaks.

In 512, this will do the assignment instead of treating x and y like named arguments:



That aside, I've been pondering puzzle generation and to help with that I've added a "bridge rating" system that can analyze each bridge to see how much of the map is on either side. That's the number of rooms on the smaller side divided by the total number of rooms. The closer a bridge rating is to 0.5, the more important that bridge is because it comes closer to bisecting the map. Puzzles on higher-rated bridges will tend therefore to open up big spaces and should be treated as more important.

Lummox JR wrote:

BTW, I discovered something in the making of this that I'll be fixing in the parser in 512. Specifically this line in my code:

The goal of this was to assign the x and y vars before calling GetRoom(). This didn't work the way I was expecting it to with chained assignments, and the reason was that I derped out and forgot DM would interpret that as a named argument list. But sometimes doing the assignment is desirable. I thought the best way to do that would be to enclose the assignments in parentheses, but of course the parser doesn't actually recognize any distinction. So, I had to make a few tweaks.

In 512, this will do the assignment instead of treating x and y like named arguments:

That aside, I've been pondering puzzle generation and to help with that I've added a "bridge rating" system that can analyze each bridge to see how much of the map is on either side. That's the number of rooms on the smaller side divided by the total number of rooms. The closer a bridge rating is to 0.5, the more important that bridge is because it comes closer to bisecting the map. Puzzles on higher-rated bridges will tend therefore to open up big spaces and should be treated as more important.

Some expressions I never imagined, very good =D

The lock-and-key puzzles above are arranged from A to G, and some can be solved in a non-linear order. Wherever you see a letter on a path it represents a lock, and a letter in a room represents one of the keys for that lock. If there's more than one key for a lock, all of them are required to open it. (The topological order is A<D, B<C, B<E, C<D, D<F, E<F, F<G. There are two A keys, two D, and two F.)

This puzzle generator needs more work, and I realized not too long ago that I put the cart before the horse when it came to generation.

The generator as it stands now chooses a puzzle structure without giving thought to the map. It's told to create N lock-and-key puzzles. Each lock has a 20% chance of needing more than 1 key (randomly 2 or 3, if so). The puzzle algorithm works like this:

- Create a list of unsatisfied keys, in numerical order by puzzle number. E.g., this might be 1,2,3,4,4,4,5,6,7,7.
- Starting at P = N-1 and going back to 1, randomly pick a higher number Q from the list of unsatisfied keys.
- Mark in the requirements for puzzle Q that it requires puzzle P. Conversely, mark that P is required for Q. (The generator maintains two lists of lists: required and requiredby.)

Once the puzzle layout is ready, the map is checked for bridges where each lock can go, starting at puzzle N and working backwards. Anything that occurs after another puzzle that requires N is taken out of the running. (E.g., when placing puzzle 5, which is needed to complete 7, 5 can't be behind 7.) Bridges with only one (non-excluded) room behind them are preferred, to the point where only bridges with the fewest rooms behind them are even considered. Of those, the bridges that are farthest from the puzzles N is needed for are weighted higher. If there is no acceptable bridge, the map is too inter-connected, so a random connection is cut and the map is re-analyzed for bridges until one can be found.

Key placement is the easiest part. Starting from N and going back to 1, the keys for N are placed one by one. First the algorithm looks at the list of N's immediate requirements, and fills the highest of those first; e.g. if puzzles 4 and 6 complete 7, then the first 7 key is placed after bridge 6 but before bridge 7; the second 7 key is placed somewhere after bridge 4 but before 7. Any remaining keys can be placed anywhere before N. To choose which room the key goes in out of all the available ones, rooms are weighted by this formula:


Now this algorithm seems to work okay, but I've noticed it completely fails to take advantage of bridges near the center of the puzzle; which makes sense, because I told it to. And the reason for that is, I'm generating the puzzle layout before considering where it goes on the map, rather than choosing the bridges I want and then figuring out how to turn those into puzzles. Key placement should work the same either way, but the way bridges are chosen needs to be smarter.

Are you planning to play around with irregularly shaped rooms?

It could be a lot of fun, both programming and playing.

Just some kaiju-fu. Nothing special. Got tidy it up a bit more (remove black space, some other fixes) but I'm liking the looks of things so far.



The ability button is for kaiju players, and was just testing to see how big it looked on screen. Can reduce via feedback, etc.