Why not auto-generate levels?

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Andrew Davie

Here are some preliminary auto-generated levels. Not tested, just sharing the first results...  they are interesting, and certainly different from my hand-generated masterpieces!


Andrew Davie

#1
Auto-generating and verifying new cave levels

What we're doing, and why. This game needs a lot of levels ("caves") — puzzle rooms with a locked door, a key, a star, and a mix of rocks, doges, walls, and dirt to navigate around. Hand-designing every one of those doesn't scale. So there's a system that invents candidate levels on its own, and — critically — doesn't just trust its own judgment about whether a candidate is any good: it actually builds a real copy of the game with that level in it, runs it on a genuine Atari emulator, and confirms with its own eyes that the level really is solvable before it gets treated as a finished, usable cave.

How it works, step by step:

1. Inventing and improving a candidate. A candidate level starts as almost pure noise: an outer wall, the player, a locked door, a star, a key, and every other cell filled with something random from the game's usual palette of obstacles. Most of these first attempts are garbage — dead ends, or literally impossible. So the system checks whether each one can be solved at all, and if it can, how many moves the shortest solution takes (more moves = a more interesting, harder puzzle, so it scores higher). It then improves the level by repeatedly changing one random cell and re-checking the score: a change that makes things better is kept, a change that makes things worse is normally thrown away — except every so often it's kept anyway, on purpose, specifically so the process doesn't get stuck permanently on a mediocre level just because every small change from there looks worse in the short term. Every time this produces a genuinely new best level, it's saved to disk — the level itself, a picture of the board, and the exact winning sequence of moves.

2. Building a real copy of the game with that level in it. A saved candidate and its winning move sequence are still just a claim on paper. To check it for real, the actual game gets compiled — the same two-part build process (6502 assembly + ARM C) used for genuine releases — with that one candidate level slotted in as the level the game boots straight into (there's already a developer shortcut built into the game for exactly this: skip the menus, land directly in whatever level is being worked on). The level list itself is only edited for the length of this one build and then restored to exactly what it was, so nothing about the real game is disturbed.

3. Running it for real, hands-off, using Gopher2600's HEADLESS mode. Gopher2600 — the Atari emulator used for testing — has a mode built for automation: instead of showing a screen and waiting for a person with a joystick, it reads a plain script of commands and just runs. The same commands a person could type at its debugger prompt by hand — "hold the joystick in this direction," "let go," "press the fire button," "run forward to this exact frame," "dump me a snapshot of the emulator's live memory" — get generated automatically from the winning move sequence the earlier step recorded, so the emulator ends up replaying that exact solution itself, with no human touching a controller.

4. Reading back what actually happened. Once the whole recorded solution has been replayed, the script asks the emulator for a memory snapshot — enough to see exactly where the player character really ended up on the board, in the real, running game.

5. Pass or fail. That real final position gets compared against what the level's solution was supposed to produce. If they match, that's real proof — this level is genuinely solvable on the actual game, not just on paper. If they don't match, the candidate gets flagged as suspicious rather than trusted, so it can get a human look before anyone assumes it's a good level.

Why this matters. Levels that pass this whole cycle aren't just "a computer thinks this works" — they've been built into a real cartridge image and solved by an emulator faithfully reproducing the actual hardware, using nothing but the exact button-press sequence that would work on a real console. Getting that HEADLESS round-trip working reliably took real effort.

It's a pretty awesome thing, actually. Incredible complexity involved, when you really think about it.


Verified shortest solution: 20 moves (score 22748 = moves*1000 - 12*clutter + 4*geodoge_adjacency + 500*wall_adjacency + 40*conglomerate_adjacency + (3000 if anchor_blocks_reverse); clutter=21, geodoge_adjacency=0, wall_adjacency=0, conglomerate_adjacency=0, anchor_blocks_reverse=True)

1. Move right to (3, 3)
2. Move right to (4, 3)
3. Move right to (5, 3)
4. Move down to (5, 4)
5. Move down to (5, 5)
6. Lift the geodoge at (6, 5)
7. Move up to (5, 4)
8. Move up to (5, 3)
9. Drop carried item at (4, 3)
10. Move down to (5, 4)
11. Move down to (5, 5)
12. Move left to (4, 5) -- collect the key
13. Move right to (5, 5)
14. Move up to (5, 4)
15. Move up to (5, 3)
16. Move right to (6, 3) -- collect the doge
17. Move up to (6, 2)
18. Move right to (7, 2)
19. Use key on the door at (7, 1)
20. Move up to (7, 1)
   -> door opens -- LEVEL COMPLETE