I'm trying to figure out a good algorithm to randomly generate levels for a game with the same rules of 'The Adventures of Lolo'. It was a rather interesting cross between a standard 'push the blocks around' puzzle game and something else all its own, having both the standard puzzle 'stand there and figure it out' side and also a realtime 'RUN!' side on some levels. The difficulty in generating levels is that I want the difficult to be configurable, so that the game could generate levels of increasing difficulty without increasing too much each time. Of course, all levels must be solvable. It'd be nice if the computer could show how to solve the levels as well. I'm at a loss for how to solve this game other than a completely random search, and that would be extremely undesirable (since it means it could take forever for the AI to solve a level). I'd appreciate any help you could offer in both the AI for solving such a game and the AI for generating new levels of a certain difficulty. Even help on judging difficulty programatically of a level would be appreciated - it would probably involve things like how many moves need be made of blocks, how often you must switch between areas (ie move block #1 a single space, then #2, then #3, then #1 again, etc), how much room there is for error (in some levels, moving a block incorrectly can be fixed and it can be moved back into the proper space, but on others a single mistake means you must 'suicide' and start the level over again), and the creatures on the level. I guess one way to evaluate it would be to purposefully make the AI 'mess up' when solving it and see how many times out of 100 a random mistake was correctable or something like that (presuming the solving part is fast enough). Below is a description of the game I'm talking about. You can get more detailed info Here. The first walkthrough is excellent. The (mechanical) point of the game is to collect all the hearts by touching the tile they are in, which will open up a treasure chest. Stepping on the treasure will remove all creatures from the level and open the door to the next level. The levels consist of various tiles and creatures with different properties(see the end of this post). Certain hearts will give the player 'shots', which can be used to turn monsters temporarily into eggs that can be pushed around. When the timer expires, the egg turns back into the monster(with the original facing). Shooting an egg destroys the monster completely, but it will reappear after a number of seconds in its original location. Certain levels have powerups (hammer, ladder, arrow) that you start with. You can't use the power ups until you get X(varies by level) hearts, at which time it becomes active. Everything starts on tile boundries, but the player can move in half-tile increments and can move blocks on the half-tile boundaries. This is helpful because a block on a half-tile boundary blocks creatures and shots aligned with any corner of it (so a single block could at best block 4 shots) Tiles: brick & bridge - standard walkable tile, blocks nothing grass - blocks creatures but notthe player sand - player moves slowly, but creatures move normally boulder1 - block everything tree - blocks player, creatures, and player shots, but creature shots can pass water2 - blocks player and creatures but not shots arrow3 - player cannot move against arrow direction, but creatures can move freely over them Creatures: snake - motionless, blocking the player, creatures, and all shots sleeper - wanders, and when it touches the player it stops permanently golem - wanders, can push player around. It will stop moving when touching player if it can't push, but it will move again if you move away dragon4 - after waking, shoots projectiles in certain direction (they have travel time, so it is possible to avoid them) skulls4 - after waking, wanders & kills on touch armadillos - wanders, kills on touch medusae - motionless, but shoot 'lasers'(instant kill, no travel time - you die if you get in the line of fire) in all 4 directions don medusae - as medusae, but moves either horizontally or vertically, bouncing back and forth 'Items': heart - collect all of these to open the treasure chest treasure chest - after collecting all hearts, collect this to clear level of monsters and open door to next level blocks - simmilar to boulder, except that the player can push it around 1 - the boulder can be broken with the hammer powerup 2 - water can be crossed with a bridge powerup or temporarily by pusing an egg into it (the egg wil float around a predetermined path and sink at the end, and only one can be in the water at once) 3 - the arrow's direction can be changed using an arrow powerup 4 - these creatures do not become active until all hearts are collected ('waking' them)

Quote: Original post by Extrarius
The difficulty in generating levels is that I want the difficult to be configurable

If that's the most difficult thing you have here, I must congratulate you. Simply creating interesting Lolo puzzles of say, constant medium difficulty, seems like a helluva hard problem to me already.

For search, a breadth first search might work. I've used it for a Sokoban-like game that had enemy turrets like medusae in Lolo. Of course with some heuristics it might do better. Like how many hearts you have collected. I think you should just ignore the random-walking creatures in the search unless they really block some route, in which case you should insert a block there.. But determining that can be a problem.

On my way to bed ... thinking of Lolo and his sister ...

Player needs to get from zone to zone. A zone's path is blocked by a certain obstacle. player needs to overcome these obstacles to progress to the next zone. For example, the following are all situations that fit the above model:

snakey in the way: shoot snakey and use as a bridge
block in the way: move block
medusa's LOS in the way: move block in medusa's LOS
boulder in the way: break boulder with hammer

this way, a level can (and is) be made up of several zones (some zones are used multiple times) in which the player needs to accomplish a certain finite goal to progress to the next zone. A map can then be created from script, with only the zones (one or more tile locations) and the obstacles. Filler tiles are then added (if needed)

This is fine for simple maps. Maps that rely on timing (the snakey-island, and pretty much all of the 'running' levels you spoke of) would require ... I don't know .. alot more calculations.

difficulty: a few thoughts: number of zones, number of obstacles, ratio of obstacles to zones, etc. - tired now.

I love the game though - I'll be one of the first to test it out I hope.

EDIT: the above method gives no thought to *location* of zones. tiles like sand and creatures like dragon imply a timing-based solution, with location being very important.

Making puzzles beyond simple labyrinths (Nethack, Diablo) is a very challenging problem. I'm only thinking of generating Sokoban maps and it's already making my head hurt. Do you have any starting pointers, Extrarius, of how you'd go on even approaching a problem like this? It could help us if we didn't have to start thinking from point zero.

I've built a fair share of puzzles for various games and a computer generator could work in a similar way as I do. That is, start with the ending and the start, then add some obstacle, add more obstacles, add items that help you go around the obstacles, remove obstacles that don't fit, and do this until the puzzle seems tough enough (long solution). And if it doesn't seem to lead to anything in N iterations, start over. An "obstacle" need not be a single block of wall or a single enemy, but it can be a river or something similarly complex. But for this method to work, you need a *fast* way to solve a puzzle, perhaps somehow using information from the solution of the previous iteration of the puzzle.

Quote: Original post by Anonymous Poster
a computer generator could work in a similar way as I do

But.. for the best puzzles I usually come up with the whole idea in my head, somehow almost instanteously, and then just do it (and modify/polish it a bit when it's laid out). But I can't inspect those routines so it's of course useless in getting a computer to generate maps.

MdLeadG: I've been thinking along the same lines as you have in reguards to solving the puzzles, except instead of 'zones' I've been using the basic idea of 'node' just like you would use in A* or somesuch.

Not counting the realtime component, there are really very few moves you can make at any one time in the game. In most cases, there are only 3-4 objects you can interact with at any one time, and of course that interaction(for ex blocking a line of fire) opens up new paths to objects you can interact with(for example walking past the medusae you just blocked to get to the last heart).
The realtime component isn't TOO much of a problem in most cases because it just limites the choices further - if you're being chase by an armadillo, running toward it will kill you practically always, so all moves going toward it would have extrmely high weight in the A* search done to get from object to object (unless there was a barrier between it and you of course). The realtime component does introduce many new possibilities, but thinking about it I'm not sure that it introduces so many that a smiple game state search couldn't quickly solve any map.

I really need to code up a prototype so I can try to make a simple solver that can solve manually created maps.


Anonymous Poster: I think the best solution for this might be to start wtih a blank maze, add in some typical 'maze walls' consisting of water, bushes, and boulders, and then do as you say - start with lolo in the door, place an obstacle (a medusae for example wih a LOS on the door) and then compute how lolo could have go past (block the LOS with a snakey for example), then do 'backwards moves' (have lolo pull the egg from somewhere that it could have been pushed from, essentially playing the solution in reverse) and repeat effect then cause until lolo is far away from the door with several steps to take to get there.

I need to make a prototype for trying this kind of thing out as well.

Cool, looks like you're on the right track. About the realtime component - I guess it doesn't matter that much, considering you'll be doing multiple tests and then checking against a set of limits. Eg, the human reaction time is considerably higher than that of a computer algo, so you'll need a comfortable amount of leeway in that respect.

Let me know when there are some screenshots of your game.

I'd suggest taking a very non-intuitive approach to random level generation... try generating the block and monster positions before generating the terrain, for instance. Or, create a set of the possible "puzzle elements", which are individually solvable and can be strung together or combined into more complex puzzles. This is probably a real deep topic... you might try prototype-solving the problem in a functional language (or at least very abstract pseudo-code) before writing any code at all.

Use back-tracking to create the level. That way you have the solution and you know it is solvable.

Quote: Original post by Zefrieg
Use back-tracking to create the level. That way you have the solution and you know it is solvable.

How do you know if adding some obstacle will make the puzzle unsolvable?