Top Men (prev: SDQ) [7DRL 2017] Complete!

[Magma Fortress]

Edit: The game is now available to play on Android.  Play Store Link



The basic plan here is to make an entirely deterministic game.  Not just combat but enemy movement and so on too.

Have a few ideas on how to make this a little more "roguelike" and less "puzzle" but have no idea how well they're going to work or if we'll get time to implement them so if you're not a fan of sokoban, you might want to give this one a miss.

The main goal is to just get something playable available on the play store by the end of the week.

[Magma Fortress]

I'm thinking I might have to call that "day 0" - mostly spent it setting things up.

The absolute basics are in place, which took a while as I have a somewhat complicated plan for level generation in this game and wanted to get things prepared for that.

Overall, quite a fun day of programming

[Magma Fortress]

Hit some major snags with my idea today.

The basic aim for this game was to generate puzzle rooms that were quite difficult yet guaranteed to be solvable.

The game play would involve a race against the clock to solve them as well as possible.

To make it a bit more interesting, I wanted to give the player some tactical choices in each room.  Do you take your time, trying to get the solution completely worked out?  Do you try and rush through it, only partially solving it?  Maybe you focus on objectives that give bonus time to draw out the game or you could focus on the objectives that increase score for a faster but possibly higher scoring game.  I also had some ideas for character progression within each game by essentially modifying the rules of how you can interact with the world.

The current approach I've been trying is to generate somewhat random/empty rooms where the player is standing by the exit and then do a backward search of possible actions, filling the room with things the player will have to deal with.  Since all the monsters/interactions in the game are deterministic, I'm able to run things backward "fairly easily". 

The problem I'm having is that the number of possible interactions is so vast, any kind of exhaustive search is impossible.  To generate a puzzle requiring enough actions to be challenging, I need some kind of heuristic that allows me to search in the direction of "interesting puzzle to solve..."

The best rooms I've been able to generate so far are ones without any monsters - just straight up sokoban puzzles.  They're not too bad, just not quite what I had in mind.  I'm basically handing a scrambled rubix cube to the player in each room.

I think I need to take a break and rethink my approach.

Does anyone one know of any games that are able to procedurally generate challenging/interesting puzzles that are guaranteed to be solvable?

[jtolmar]

In case you haven't already seen it, there's a paper on generating sokoban levels: http://larc.unt.edu/ian/research/sokoban/. If I recall correctly, their algorithm is a lot like yours: search backwards, preventing moves that return to an old state. The one optimization they made was to count "move to anywhere the player can reach and push a block" as one move in the search.  Might have been "push a block any number of spaces" (adding all to your queue) instead.

I think you could easily extend that to include some block-like monsters (the medusa and especially the dragon in The Adventures of Lolo), alternate types of blocks (ice blocks of course), and items that fiddle with blocks (Ittle Dew and Ittle Dew 2 have lots of these. I wouldn't recommend trying to play those for ideas during 7DRL week though).

The Legend of Zelda is the game most people will think of if you say dungeon plus puzzles. Most of their monsters are just obstacles, sometimes with their own self-contained puzzles, that you need to kill because they're getting in the way of dealing with your puzzles. So just generating the puzzle and sprinkling some irrelevant monsters in would put you in some auspicious company.

[Magma Fortress]

Thanks for posting that paper.  It seems to support my current theory on how the search needs to be performed.



I've been thinking this over last night (at the expensive of my sleep) and it seems to me that performing an exhaustive search is really the only way to go in generating good puzzles.  The difficulty of a puzzle is basically determined by its simplest solution.  It's no good generating puzzles with a known complex solution when the player can simply solve it by taking some shortcut.  The goal of generation basically becomes to ensure that the simplest solution is as hard as you're aiming for.

Sokoban works well for this type of generation because it has a single "completed" state, which you can measure your "distance" from.  The rules I had last night allowed many different completion states.  Monsters left unkilled, random boxes around the room, for example.  The player could keep making changes to the world (generating new states to explore) without actually "progressing" in any meaningful way.  This resulted in unnecessarily complex solutions to puzzles that could be solved in trivial ways.

Backward searching a rogue-style game turns out to be a fair bit more complex than forward searching.  Even in the simple example of sokoban rules:
- playing forward: When the player moves North, the world goes from a single defined state to another.
- playing backward: When the player moves South, did they previously step toward that box or did they push it?  Did they just push a box into a hole leaving neither behind?  A single action now results in multiple extra world states to explore.

The way I'm currently loading/saving states and undoing/redoing turns is also very inefficient.  I was hitting memory limits trying to store every explored state even with 5x5 rooms.  It's partly because the engine was thrown together so quickly and I was trying to keep things generic enough to support all sorts of different rules, which those optimisations wouldn't allow.

It'd be so easy to let the scope for this get out of control.  I need to keep reminding myself I only have half a week left.

[Magma Fortress]

Day 4.


Spent some time today with the profiler optimising my level generation.  It's now 1500 times faster than what I had a couple of days ago...  There's still more I could do to speed things up but I wanted to skip that for now and get some more of the actual game mechanics implemented.  Even with basic sokoban rules, I'll still need to add a system that generates a pool of levels in the background so you don't have any delay moving from one room to the next.


You can now solve the room or just run into the next room to skip that puzzle and get a new one.  Loads more to do before there's any real "game" here.

[Magma Fortress]

Day 5 and 6.

- a bunch of changes were required to allow new level generation in the background while the current one is being played
- generated levels are evaluated on their difficulty and interest (fairly subjective rating of how fun/dull it is)
- touch input for selecting/moving boxes
- very basic animation

I've cut the vast majority of ideas I had for this game and I'm still not sure if I'm going to finish this in 7 days.  Monsters and items have been completely cut so we're down to basic sokoban rules.

A large part of the week has been spent messing with the level generation/evaluation algorithm.

The other factor slowing me down is my choice to write this game in Kotlin (a language I've never used before.)  I'm finding Kotlin itself great to use but have a habit of trying to make use of all its fancy new features in my game.  The property delegate my World class uses to save/load state is very neat but took a me a fair chunk of time to figure out

[Magma Fortress]

Day 7


The game is finished!  (but not uploaded yet.  It's getting late and sorting out the Android store listing it's going to take a little while)


Quite a busy day getting a lot features in place and last minute issues sorted.
- a lot of the game play elements were put in today: timer, score, etc.
- difficulty now ramps up during each game.  I've spent a bunch of time trying to tweak the difficulty evaluation algorithm.  You still get some rather easy ones later in the game and "out of depth" puzzles early on but I think it just adds to the fun.  You have the option of skipping them for a small penalty and deciding when you're better off skipping a puzzle is one of the more interesting choices in the game.


Should hopefully have this available on the play store in about 12 hours from now.

[Magma Fortress]

Top Men is now available to download


link


I'm really up to 8.5 days now including my "day 0" so I was keen to get something released but there are still a couple of things I'd like to change.
- There's no tutorial or instruction on what to do so read the store desciption first.
- You may find it taking a while to load levels during you're first game, especially if you have an older device.  It generates a pool of them in the background so after the first minute or so, this shouldn't occur.  I'll probably supply a bunch of premade levels in a future version to avoid this issue.
- Various minor graphical glitches.


Anyway, give it a go if you're keen.  Or hold off for a little when a few more things will hopefully be ironed out.


I'd like to come back to this after a little break and spend some more time trying to work monsters into this game.  We'll see.