Level Patterns

[DivFord]

I feel like at the moment we're running into a slight problem with our game design. We said we wanted this to be hard, and for people to replay over and over to see how far they could get. And we've made it a puzzle game. So sooner or later, players will have seen all the rooms a few times, and there won't be any puzzle left, because they'll know all the solutions.

My proposed solution is to introduce more procgen into the rooms. At the moment, most of our rooms fall into one of several patterns:

• Obstacles to clear out the way.
• Steps to construct.
• Platforms to jump between (possibly positioning them first)
• Pits/Pools to get over.

So the theory is that we can mark areas of the rooms not with specific blocks, but with one of these patterns instead, then insert a variant of the pattern before creating the room. Any or all of the room could still be hand authored, by specifying a block rather than a pattern.

The main benefit of the system would be that if multiple patterns were included in one room, as in the last example, the overall puzzle would be different each time. This would work most effectively if the patterns were right up against each other, causing the player to see them as a single puzzle, rather than recognizing the individual elements (not the case in my diagram - whoops).

As far as implementation goes, I think if you marked the top left corner of the pattern with an identifier, and filled in the rest with some kind of 'null' character (say, -), we could just do a pass to find patterns, and replace the characters at appropriate offsets with the characters from that pattern.

[ As an aside, we should maybe sort out our map codes. They're kind of crazy at the moment. Could we maybe make a single cell be two characters, one to specify the type of cell (eg. B for block, P for prop, O for obstacle pattern…) and another to specify the particular variant? Maybe just use the row numbers from the sprite sheet, since assigning letters has become so confusing.]

Wooo! Wall of text. What do you think?

[Fyll]

I thought the original plan was to have procedurally generated levels, but it got a bit lost en route.

Also, if generating the rooms is what you want to do, then that would be inside the code, so we wouldn't be using the codes anymore. Until then, they'll probably suffice.

[DivFord]

Well, the idea is the rooms and the patterns are still hand-authored, it's just that patterns are added in to the specified areas of the levels.

So, for example, the room in that last image would be:

B*B*B*B*B*B*B*B*B*B*
B*B*B*B*B*,,,,,,,,B*
B*B*B*B*,,,,S4----BX
B*B*B*B*,,,,------B*
BEO3----,,,,------B*
B*------,,,,------B*
B*B*B*B*B*B*B*B*B*B*

Which has the added advantage that it's closer in shape to the rooms, being broader than it is tall.

In this case, O3 is replaced by the pattern:

Ps,,,,
B*,,,,

While S4 is replaced by the pattern:

PlPlPl
,,PlPl
,,,,Pl
,,,,,,

Giving us the final room:

B*B*B*B*B*B*B*B*B*B*
B*B*B*B*B*,,,,,,,,B*
B*B*B*B*,,,,PlPlPlBX
B*B*B*B*,,,,,,PlPlB*
BEPs,,,,,,,,,,,,PlB*
B*B*,,,,,,,,,,,,,,B*
B*B*B*B*B*B*B*B*B*B*

[mspraggs]

I will do this, as I think it would be a fun problem to wrap my head around :-)

[DivFord]

@mspraggs You know about the notes in the design folder, right? The stuff in this thread is a bit out of date.

[mspraggs]

Yes, I know it's there. I will look in more detail...

This would all have been written before we had our meeting right? Are we still planning on making it puzzle based in a single room (I seem to remember there was the suggestion we move to making it more of a platform)?

[DivFord]

The puzzle/platformer question is still up in the air, as I recall. The patterns should work for either though; platforming challenges are essentially puzzles, but based on skill rather than deduction, so their gameplay function is the same.

[mspraggs]

Cool, and in any case it'd be nice to have some procedural generation for the levels, even if it's a platformer only.

[mspraggs]

I've taken some steps towards doing this. I've changed the way newRoomFromData works, so now there's a std::map that takes the character code and maps it to a handling function, which does whatever's needed for that code. This way it should be relatively straightforward to plug in new blocks and character codes.

[Fyll]

Looks... Nice.

As a suggestion (although this is mentioned somewhere above), would it be better in the long run to have the codes for each object be 2 characters long? E.g. BD would be a Block of Dirt, whereas PC would be a Prop that was a Crate. I mention this because what with blocks, props, enemies, and pickups all needing separate codes, it's already getting a bit silly.

Also a suggestion, but can we change entrances and exits? Seeing as they're identical to air blocks, could the function that adds an entrance/exit just add an air block, instead of adding an entrance or exit block? This'd save us from using those characters (E and X), and would reduce the number of different blocks we have. Further to this, if two characters are used for each thing, the entrance and exit could be prefix code (like the B and P above). This way, we could have entrances underwater or whatever.

[mspraggs]

I see the motivation to have two characters for each block. My only concern is that it'll reduce the readability of the level data when editing levels. With each block being a single character at the moment, it's easy to see at a glance how the level is structured. I worry that as levels get bigger, and it'll more difficult to determine which block you're looking at.

However, I absolutely agree we need to be able to pack more information into the level files. For example, if we're going to have some probabilistic elements to block generation, this will need to be encoded somehow.

I'll look again at David's design documents for inspiration.

[DivFord]

I found two-character blocks were actually more readable. On a fixed width font, it makes them more square, so the whole thing ends up closer to the actual shape of the level. In any case, weren't we planning on making a level editor? I'm sure that was mentioned.

[mspraggs]

Ah ok, I can see that being the case. Would there be any way of working probabilistic blocks into the layout? I've been reading the article on level generation in Spelunky again, and it could be quite neat to have something like this.

[DivFord]

Well, the easiest way would be to just make variant levels/patterns for each of the possible combinations you wanted, but I can see how individual probabilistic blocks would be preferable. Maybe we could have B* be a stone block, and %* be a 50% chance of a stone block? Assigning specific probabilities probably isn't possible with only two characters. You could have a symbol for 25%, another for 50% and a third for 75%, which might be enough...

[Fyll]

The Room class has the capacity for a given type of thing to appear at regular intervals. It'd probably be very straightforward to add a yes-or-no X% block of a specific type (e.g. '%1' is a 10% chance of a stone block, '%2' is a 20% chance, as David suggested).

Having a percentage choice between options (e.g. 50% chance stone, 50% chance water) would be really hard I imagine. Unless we don't restrict the code to be two characters wide, and have each prefix symbol know how many things to accept (e.g. % accepts 2 numbers (the percentage), B accepts 1 character (the block code), $ accepts 2 characters and 2 numbers (the two things to consider, and the probability of it being the first)). This'd make the level files really hard to read manually, but if we're making a level editor, that shouldn't be a problem.

[mspraggs]

An alternative I thought of would be to have two files, one containing the types of blocks and the other containing the probabilities of them appearing. This might be overkill though.

Do we need to have two letters to determine the block type? Unless we're going to have more than 26 types of block, or more than 26 props, we could have the first letter being the type of block/prop/unit/thing and the second being the probability of it appearing.

[DivFord]

The idea of the prefix char was to make things more readable, by allowing us to pick characters that correspond logically to the prop or block. We were running into the problem before that multiple blocks/props began with the same letter, so we ended up using weird codes for them.

With the random blocks, I think we need to determine why we want them. Unless there's a concrete game-design reason, I don't think they're worth all this effort. As I see it, they could serve one of two purposes:

1) Adding variety to the level shape. If they were only used in places where they wouldn't block the players progress, they could help hide the fact that the same levels/patterns are being reused. If this is what we want, then there's a fairly limited pool of suitable blocks. We could go back to the original system of having a list of blocks that can be used randomly, and the random block code would no longer need to specify block type. In that case, % followed by a number would probably be enough (multiply number by 10, use as percentage chance).

2) Small obstacles. If random blocks were only ever things that the player can destroy (dirt, crates, etc.) they could work as extra obstacles to overcome. If this is what we want them for, it would make more sense to implement a 1x1 obstacle pattern, so as to integrate random blocks into the pattern system. Since we're already setting that up to pick obstacles that fit the players tool-set, it would make sense to have a single system.

[mspraggs]

A 1x1 pattern does sound like a good solution to this problem and a good way to keep things consistent.

I'll rejig the level loading code to require two characters instead of one.

[mspraggs]

I have now changed the level parsing to use two characters for the block code instead of one. You may notice some differences to the game:

• Menu signs not present - working on a fix
• There's only one level - I wanted something easy to test, so I used the test level only
• For some reason friction/prop collisions have gone a bit mental, so now all props can be moved around - again, looking to fix.

Also, stone blocks are no longer asterisk, they are now 's', which I think is more canonical with the rest of the block naming.

EDIT: After some investigation I think these new bugs are a result of comparing block/prop character code_ member variable in Object. How widespread is the use of Object::code() when handling interactions etc.?

[Fyll]

While I can't comment on the Menus, the dodgy collisions are my fault. I've been trying to rewrite the collisions, and accidentally left a test version in the code. While it does work perfectly, it does have the problem that you can push everything around. I'm still trying to think of a fix.

If you want to go back o the old version, you should be a able to change the #if 1 to a #if 0.

EDIT: In answer to your question, I'm pretty sure it's only used in the tile updating function. If you change matchCode() to also check that the two things are the same type, that might fix it.

[mspraggs]

Hmm ok. I did go through and change matchCode, but it was late last night and chances are I missed something, so I'll go back and have another look.

[DivFord]

Menus are a bit weird. I think we suggested moving them to be a variant of stone, rather than an entire block type. Of course, that would mean programming in block variants…

[mspraggs]

They aren't encoded in the level file as a different block type, as in they weren't when I began making changes, and I kept it that way. I think the menu screen uses a different tile set to the standard levels (there are two different sets of stone in the sprite sheet). Perhaps I've accidentally set it to use the standard tile set somewhere without realising.

[DivFord]

If I recall correctly, the menu mixes normal stone and "sign" stone. I may be wrong though, Iain programmed that part. The plan was to get rid of that second type of stone, and just shift the two signs into the empty space on the end of the top line.

[Fyll]

The Sign blocks are a separate type of Block, with the quit and start signs already on them. This was a hack (although, a very nice hack) to get the signs to be visible there with no extra code necessary.

They should be in the version you've got (they use the code 'q').

Having looked at the code, you'd changed the q's to s's on the menu level. I've changed them back and pushed.

[mspraggs]

Really? The menu level before had asterisks... Maybe I'm not looking far enough back in the commit history. I did try the Bq code, but because that's a different code to Bs, it rendered differently.

Ah I see now (after looking at the commit log). I was editing Menu.txt from the older version, which hadn't been updated to use q, then using collect_levels.py to compile the levels into levels.cpp, hence I carried forward the error. I've changed Menu.txt so collect_levels.py can still be used.

[Fyll]

Ah, oops. I've only been editing the levels.cpp file.

[mspraggs]

I have now updated the way collect_levels.py works so that an arbitrary number of individual levels and level groups. The configuration is stored in an xml file (see levels/active_levels.xml for an example). The call to collect_levels.py goes like this:

python collect_levels.py <xml input> <output stem>

Where the output stem is the shared name of the source and header files (e.g. "lib/levels").

collect_levels.py now depends on the jinja2 template engine, which you can install on Ubuntu using apt-get install python-jinja2. Installation on OSX should also be straightforward. Download the source, extract and change into the new directory, then run python setup.py install.

The header and source file templates can be found in the levels directory, named template.cpp and template.hpp.

Whilst this may seem a bit extravagant, I feel it's the easiest way to automate the gathering of level files into a single pair of source/header files, with arbitrary grouping and variable naming. This will greatly simplify the grouping of patterns according to their type (e.g. left to right 4x3, etc.).

[mspraggs]

I have now implemented pattern parsing and gathering. The code automatically detects the width and height of the pattern from the template, so there's not need to put the pattern dimensions in the code. It also automatically determines which rows the entrance and exits are on. With the dimensions, initial code and entrance/exit points, it then looks up the relevant std::vector<std::string> in levels.cpp, using the getLevelGroup function, which is generated by collect_levels.py.

It seems to work ok, though I've yet to test it with a variety of templates/patterns. Also, it may have (many) security vulnerabilities, since input sanitization isn't particularly strong, so this may need some work.

EDIT: I won't close this just yet, purely because I haven't thoroughly tested the implementation.

[Fyll]

On input sanitisation, surely as it's being read from levels.cpp it'll all be correctly formatted, and if not, will be caught in debugging.

Either way, nice to have that done. That brings everything a big step closer to looking like a proper game...

[DivFord]

I definitely like the feel of this, though I don't entirely understand the implementation.

What does the auto-detection of dimensions, entrances and exits actually do? I feel like there's a risk that without formalized patterns, we could end up putting a pattern in a level and forgetting to make any pattern files that fit it. With a finite number of pattern types, we'd have a clearer idea of what assets need creating. I may just be misunderstanding you.

A small quibble: the file-naming is a little confusing. Having the pattern files called 'level1.txt' seems a bit odd.

@Fyll: I think a tweak to the scrolling code may be in order. In this new level you can't always see where you're jumping to, since it only looks a very short distance ahead.

[Fyll]

@DivFord: There's a constant called PUSH_SCREEN_BORDER. It contains how close to the edge you have to be before the screen starts moving with you. Feel free to tweak it to your hearts content.

Actually, playing around on the test level I notice that the random chunk is getting re-chosen every time I die. I assume this is behaviour we don't want, so the level reload code could possibly do with a tweak.

[DivFord]

Ah, I just remembered my other question. Is the implemented pattern supposed to be anything in particular? The entrance and exit don't seem to match any of the patterns I suggested, and I'm not sure what PR stands for (wouldn't that be a prop?). Unless it's platform. Why did I assign the same code to platform and prop?

[mspraggs]

Initially I thought the dimension detection and entrance/exit detection would give us more flexibility when putting patterns in. I could add a warning to getLevelGroup so that if none of the if-statements are true, then it spits out a warning, or exits, or something.

The file names can easily be changed. Take a look in levels/active_levels.xml for how to do this, then rerun python collect_levels.py levels/active_levels.xml lib/levels to regenerate levels.cpp/levels.hpp.

To be honest the "R" doesn't have any meaning in the code other that when looking up the correct vector to use. It's just a label I used to mean that you must traverse the block rightwards. The P I agree is also a bit confusing, but originally it mean pattern. This is how the implementation works:

1. Determine width and height of pattern, and entrance exit offsets from the first row.
2. Build a variable name from the passed pattern using the following formula: <original code>_w<width>h<height>_e<entrance offset>x<exit offset>.
3. Get the variable using getLevelGroup and the constructed variable name.
4. Pick a new pattern at random.
5. Call parseRoomData on the retrieved pattern to add objects from the new pattern.

The fact that parseRoomData is called recursively has the added nicety that you could potentially embed a pattern within a pattern, if you wanted additional levels of complexity.

EDIT: Ah yes I see what you mean now, the first letter in your proposal stood for what type of pattern it was. This can of course be restored, and fairly simply I think.

[DivFord]

Neat. I left recursion out of the original design because I thought it would be too complicated to implement. Glad you managed to get it in, that opens up a lot of design space. Have you tested it?

[mspraggs]

Well it sort of happened by accident, as I put the room data string loop into it's own function to reduce code duplication. This is called on the sub-pattern that gets picked, so it could potentially be recursive, though I haven't tested it, no.