Puzzle vs Mario

[DivFord]

Time to ask the hard question: Is our puzzle-platformer a puzzle game, or a platform game?

More seriously, this is the problem as I see it: We have puzzle elements, and we have randomised levels. Randomly generated puzzles are really hard to do. Do we embrace that challenge and try to break new ground, or do we set our sights on something more feasible? The second option would either mean taking out the puzzles, or taking out the randomisation.

[mspraggs]

I think it should be possible to make a puzzle game from everything we currently have. The blocks that the drain beam acts on and the steel crates are pushable/pullable. All that's needed is to be a bit more creative with how the levels are designed, and maybe make use of pickups and the inventory system.

Plus we should figure out level progression, so that it gets harder and isn't just plain random. Maybe we could have a weighting for each room so that the chances of getting an easier room go down the further through the level you get?

[DivFord]

Agreed, but I think the randomness (as it currently exists) conflicts with the creativity. If we're presenting random levels, the assumption is that the player can replay the game and have it be different. If you just took Portal (or a puzzle game of your choice) and presented the levels in a randomised order, I think it would make the game strictly worse.

[Fyll]

Let's ask, what do we mean by a puzzle?

The way I'm seeing it is as some sort of obstacle that needs to be overcome ideally by thinking, with the key point that the player shouldn't know the answer before encountering the puzzle. Under this, most of the things we have in at the moment aren't puzzles (as the answer is always the one same thing, e.g. Crate? Smash. Water? Freeze).

Obviously, randomly generating puzzles will be hard. Potentially, sticking the patterns closer to each other might allow fancy puzzlesque interactions, but I really don't know how we might go about doing a very good system.

Also, enemies don't generally fit into a puzzle game, as they tend to require faster action in an otherwise slow and pensive game. Not that I have many experiences with puzzle sided puzzle-platformers.

[DivFord]

I like your definition.

I believe there are two currently existing patterns which provide a puzzle: the 3x3 pile of crates, and the version of that with an explosive barrel in. Since you're making a staircase, smashing all the crates actually fails the puzzle. It's only a puzzle once though, since, as you hinted at, it doesn't interact with anything else in the level.

I was thinking along similar lines with the 'sticking patterns closer to each other' idea. I'm going to explore that on paper, and see if we can take it anywhere.

Enemies can work in a puzzle game, you just have to design them differently. In a stealth game, the enemy AI is the puzzle. Nintendo's bosses also tend to have a puzzle quality to them. My brother was telling me about a puzzle platformer he found that had a sea monster you had to scare away with your torch beam. I think that's another approach to take, where monsters are manipulated by your tools, rather than killed.

[DivFord]

I wanted to test how much of a puzzle I could make with just crates, so I made a new level and have pushed a version with just that. Let me know if you find the puzzle interesting so I know if I'm on the right track or not.

I disabled rotation on crates. It find it makes it easier to build puzzles with them because they slide into holes easily.

[Fyll]

The level looks nice! I can see why you wanted the rotation off though.

[mspraggs]

Just to keep the momentum going: any more thoughts or progress on this?

[Fyll]

Not really! :P

Having thought about it while eating dinner though, let's see what my brain came out with.

Doing a platformer would put the emphasis on the physics, and I really don't think the physics are up to that. Obviously, this would mean a bit of a rewrite, and bleargh to that. Also, I feel that as a game, a straight up platformer would just be somewhat less interesting.

However, trying to come up with some method for randomly generating puzzles sounds like a nightmare. I assume it'd have to work somewhat along the lines of trying to write a procedural sentence generator, i.e. taking a number of puzzle components (words) from a number of different sets (nouns, verbs, etc.), then combining them by way of some really complicated rules (grammar) into something with actual meaning (a sentence).

Now, having tried to write a random sentence generator, I can vouch for the fact that this is a really hard task. This is possibly a bit more complicated than what we want, but it seems to me like it would be the best way to do it (in terms of user experience).

The part of me that wants a cool game wants a puzzle game. The part of me that wants a doable game wants a platformer. The part of me that's realised it's going to be involved in programming one of these is crying in the corner.

[mspraggs]

I don't think it necessarily difficult, so much as will require a lot of work. Part of the reason that generating random sentences is hard is (a) natural language processing is hard (b) English is a super complicated language.

Rather than trying to think up a solution from scratch, perhaps we should have a read around how procedural generation is done in other games and figure out the best approach for our case? Something that is well covered is procedural maze generation. Could we treat each room as a maze, but put constraints on the vertical paths so that they're passable in some way?

Basically I think we should have an algorithm that generates the path from the entrance to the exit and then puts in obstacles and other paths that lead nowhere. In this sense it would be more maze-like. Admittedly getting vertical movement into this would have to be thought about. What do you think?

[mspraggs]

Just dumping some reading here for future reference if we go down the puzzle path:

• http://gamedevelopment.tutsplus.com/tutorials/create-a-procedurally-generated-dungeon-cave-system--gamedev-10099
• http://pcg.wikidot.com/
• http://pcgbook.com/
• http://www.gdcvault.com/play/1021877/Constructing-the-Catacombs-Procedural-Architecture

Feel free to edit this post to add links you think might be useful.

[DivFord]

The grammar idea and the maze idea both sound like they would be worth exploring at least. Prototyping standalone concepts in python or javascript is probably a good way to work out what we're doing.

My take on the problem was to try generating levels from a graph, with lots of emphasis on moving props between nodes. I've been testing it as an extension to the editor, but it's not ready to show yet.

With regards to vertical movement, this GDC talk is pretty interesting: http://www.gdcvault.com/play/1021877/Constructing-the-Catacombs-Procedural-Architecture (specifically the section on upwards mobility).

And, while we're posting links to PCG stuff, the PCGbook is pretty neat.

Procedural puzzles are something of an obsession for me. Partly that's because they haven't been done very much, which is bad news when it comes to looking for existing solutions… One time, I analyzed the levels in Portal to see how they were structured. My main take away from that (and from playing with this thing) is that the overall structure of the puzzle is rarely the puzzling part. Most of the challenge in portal comes from working out how to overcome an individual element, or from the actual execution (i.e. platforming, aiming, timing). In short, while maze generation sounds interesting and I want to explore it further, I suspect it will lean more towards confusion than puzzles.

As a side note, here's a link to my other game. It's also trying to generate puzzles, though not as the primary focus. If you think the technique might be transferrable, I can try to explain how it works. (Two controls nobody works out: click scroll wheel or press enter to interact, press i to open your inventory).

[mspraggs]

What I meant was we should explore any ideas to exhaustion to ensure that we don't waste huge amounts of time effort reinventing the wheel. For example with the graph idea there are existing ways to represent and manipulate graphs, and if those satisfy our needs we should just adopt one of them.

EDIT: Also I'm wondering whether there's some generic concepts in procedural generation that are transferable across different content types (aside from the obvious RNG requirement).

[DivFord]

So, our design process is a depth first search? :P Sounds like a good plan.

There are certainly a few concepts which see a lot of use across PCG. Pathfinding, Perlin noise, Poisson distributions, Grammars, Cellular Automata… A lot of them are so simple that it's easier to rewrite them on a case-by-case basis than to try making a generic version, but noise functions can definitely be generic.

[mspraggs]

What could possibly go wrong?

[Fyll]

While English is a needlessly complicated language, my point was more that, with a language, there is a difference between a string of words of the appropriate types and an actual coherent sentence. I assumed there was a similar difficulty between building a puzzle from puzzle elements as opposed to just putting a series of puzzle elements next to each other.

The maze approach seems interesting but I agree that vertical movement would be a problem. At the moment you can only jump one Block high, so there likely wouldn't be much in the way of alternate paths for dead ends without it being really obvious or overly punishing. Maze style puzzles also have the disadvantage (I'd imagine) of being systematically solveable.

Admittedly (as I've probably mentioned several times now), I don't really know much of the theory behind procedural generation, but I'll have a poke around this evening.

[DivFord]

"At the moment you can only jump one Block high" <- Which is exactly why you programmed the passable platforms. There is method to my madness!

[Fyll]

Ah! I'd assigned them in my head as moving platforms for crossing terrain rather than going somewhere else.

[Fyll]

A quick question:

Reading around, it seems that a common technique when procedurally generating levels is to write some sort of AI that will play through it (to check that it is completable). I don't think it's possible to write an AI to solve puzzles without knowing the structure of the puzzles beforehand, so would we even be able to see that a generated level was completable?

This came up because I've been considering writing such a level-completing-AI, but then bumped into this stumbling block (not that I've started yet, mind).

[DivFord]

Huh. I thought I'd replied to this…

I'm not really sure I understand where you're coming from with the AI not knowing the structure, but I can weigh in on the PCG question. Procedural Generation has two core approaches:

1) Set up a constrained system such that whatever it generates will be useable.

2) Generate stuff, then evaluate it to see if it's useable.

The second approach is generally able to produce more varied content, but potentially leads to much longer generation times, depending on what subset of the generated content is actually useable.

Personally, I favour the first approach for anything generated at run-time. If it's a tool for me to use to create content, and the end-user never has to run it, I'm more likely to use the second approach.

The 'level-completing-AI' is clearly an example of the second technique. It's hard to be sure, but I'd be willing to bet that the set of interesting and solvable puzzles is significantly smaller than the set of all possible 'puzzles'.

Not to mention, an AI that checks if puzzles are possible is one thing, but an AI that checks if puzzles are interesting is a whole different kettle of fish. People have made metrics for evaluating the challenge of a platformer level, but I don't know how you'd do the same for puzzles.

Long story short, I don't think the AI is a sensible option.

[Fyll]

Yeah, my thoughts on the AI are pretty much as you say (except worded worse :P), hence my reluctance to try to write an AI that can figure out what is fun.

So we're happy to rule out run-time generation, as that would need some sort of AI or the like to decide if a level should be kept. By your choices, that leaves either setting up a constrained system or just randomly spamming levels beforehand and manually checking if they're okay.

If we were going for a single type of puzzle (a la (I believe) The Witness), then I could see writing a constrained system as realistic, but trying to define an underlying set of rules for the basic puzzles of the form "interact with objects (each responding differently) by way of a number of different methods (e.g. guns, pushing) and have something interesting happen", then I think we're being a bit too vague. I imagine that the best fix for this worry would be to narrow our puzzle types down (e.g. just do block pushing puzzles, although that'd probably still be too wide...).

The alternative of spam-and-choose has the advantage that we have code set up already for reading in level files, and we could ensure that things are interesting (I'm pretty sure we humans will be better at judging what qualifies as a fun thing for a goodly while yet!). The obvious downside, is the fact that we'd have to check through a stupidly large number of levels/patterns to get a half-way decent number of good levels/patterns.

[DivFord]

If we're weren't generating puzzles at run time (spam and choose), it would probably be better to just design the puzzles ourselves…

That said, I do enjoy PCG (could you tell?), so I prefer the constrained system approach.

Have I shown you this before? I'm not saying it's necessarily the right way to go (I wasn't happy with my last implementation of it), but it at least suggests a way for the object interaction puzzle to work. In simple terms, each object has input and output options, and we use them to link a series of objects together.

I don't know that we need to narrow our puzzles to the extent you're suggesting, but it might be worth everyone just designing some levels so we can work out what sorts of puzzle work well within our system. Iterative design and all that...

[Fyll]

That's probably smart. I assume we're allowed to make up new stuff for the game in doing so, as it's a bit bare-bones at the moment, and there'd only be so many different sorts of puzzles we could come up with.

[DivFord]

That makes sense. It'll probably be useful to be adding content we need for puzzles rather than just stuff we think we can make.

[Fyll]

As a thought I had (you may all have realised this yonks ago, but I just thought of it so want to write it down somewhere in case I forget), if we are going for a puzzle game, then we should probably remove lives. It seems cruel to make the Player game over just because half of the puzzle was off-screen 3 times in a row, so they kept accidentally making the level unwinnable.

Now, if we kept the levels small, it might be okay, but it does seem a tad unfair if the levels are not entirely viewable at any given time. Adding some sort of map or free scrolling camera option might fix that though.

I haven't designed any levels yet (sorry, I've been pretty busy recently what with term starting again), but just wanted to mention these thoughts.

[DivFord]

I was wondering about adding a telescope arm.