Articles – Page 8 – MagicalTimeBean

The Dilemma of Unsolvable State Detection for Puzzles

Last Saturday was the Escape Goat Alpha 4 playtest, and the next big design challenge has shown itself and thrown down the gauntlet. It’s a hard problem to define, so I’m hoping that writing this will clear it up in my head. It might also make an interesting story for anyone who wants to see the gruesome behind-the-scenes of game design.

Escape Goat is a puzzle game at heart. You’re there in a room, pitted against obstacles and mechanisms, trying to reach the goal. My playtest version of the game had several stages of training, where the player learns the game mechanics, controls, and how the various gadgets operate, before being plunged into a puzzle that takes some problem-solving skills to beat. The first few puzzles would basically solve themselves in a fun and visual exciting way while teaching you how the game works. These rooms were fun to build–basically single-button Rube Goldberg machines that make you go WHOA, COOL and that’s about it. Then come the puzzle rooms.

By their nature, puzzles can enter an unsolvable state if you mess up. There are blocks that drop and can’t be lifted again, crates that break, switches that stay permanently thrown. If you do things in the wrong order, you’re cooked and have to retry the room.

The problem is, the game doesn’t know when it’s in that state. Play testers were poking around in a room for a few minutes trying to solve the puzzle even though it was no longer possible. This just can’t happen in the release version of the game–the lack of feedback is frustrating and boring. The player has to get the memo that the room is now unsolvable, and a retry is required. Detecting and delivering this message is the big challenge I’m facing.

EscapeGoat 2011-07-13 00-04-00-78 — The room in its initial state, when you enter from the top right

Let’s look at one room in particular. This room is the first one where you can actually “lose.” There aren’t many interactive elements, just the three buttons on the top level. The green one operates the push block on the left, the blue one lifts the platforms in the middle level, and the red one releases the top (red) platforms. The proper solution is to hit the buttons from left to right, which transforms the level like this:

EscapeGoat 2011-07-13 00-07-49-56 — Press the green button to shift the lower blocks and create a gap

EscapeGoat 2011-07-13 00-07-55-11 — Press the blue button to lift the blue platforms on the middle level

EscapeGoat 2011-07-13 00-08-06-42 — Press the red button to release the top level platforms and drop the blocks

The blue platforms lift to catch the blocks, allowing access to the yellow button on the bottom right, which opens up the passage to the left. If you hit the red button first, here’s what happens:

EscapeGoat 2011-07-13 00-06-39-71 — Without the blue platforms lifted, the blocks fall too far and barricade the yellow button.

The blocks have fallen and are blocking access to the yellow button on the bottom right. You’re screwed. You have to restart the level from the pause menu or by leaving the room and re-entering. But… how can a new player know the puzzle is unsolvable now? There’s no message. You’re just left wondering what to do next.

I’ve thought of a few solutions:

Design the puzzles so they can’t enter an unsolvable state. Well, this would make for a pretty easy game.
Design the puzzles so that something kills the player when they enter an unsolvable state. This is a better solution than what we have now, but it means inserting a lot of violent gadgets (lightning machines, buzz saws) and having to account for all locations the player could be on the screen.
The game checks to see if it is unsolvable and delivers a message if so. Checking programmatically is something that would add months to the project, if not years, so that’s out of the question. But maybe the room could have a bit of hidden data built in to detect for states that would make the room unsolvable. For example, I could have a hidden block detector checking the area in front of the switch to see if the blocks have fallen there.

I like solution #3 so that’s what I’m going to explore this week. A related problem is how to notify the player that the room can’t be solved anymore. Options include:

Kill the player instantly, which would be really jarring. No good.
Bring up an on-screen text sprite, which is more subtle, but not very thematically interesting.
Have a gadget that activates in the unsolvable state and allows quick restarting of the level, a cool thematic solution but maybe a bit too abstract compared with the on-screen text.

I’ll do some quick tests with options #2 and #3 to see which works better.

Join me

Are you an artist/designer with a game idea, looking for a way to bring it to life?

While I work on Escape Goat, my Soulcaster engine is collecting dust. Let’s put it to use. I’m looking for a skilled designer to make a complete, original game using the awesome technology I’ve developed for Soulcaster I & II. Here are some of the capabilities already built in:

Behavior based AI including dynamic pathfinding
2D tile based maps, with animation and parallax layers
Versatile and blazing fast level editor in Windows
Sprite and actor handling, including collision detection, particle systems
Creature-based controller input abstraction
Multiplayer support (a by-product of an experiment during the production of Soulcaster II)
Menus, animating text, tooltips and other UI goodie

See the game engine in action.

Your game probably has some mechanics not currently in the engine. For example, you may want pixel-based movement instead of smooth grid-based movement. That shouldn’t be too hard to add in. In other words, I’m willing to make small modifications to fit the game design. So long as you want to make a top-view, 2D sprite based game, where all entities are no larger than the tile size of 16×16, it should be workable. If your idea is an RPG that requires a separate battle mode, it’s not going to work–a whole new system is too much for me to add.

Collaboration terms are negotiable, such as sharing of revenue and ownership of IP.

Interested? Have a design that is just too awesome to be sitting around? Use the contact form and get in touch. Link me to any game design or art you have online, and tell me about your background in game design.

More pathfinding and AI

I’ve worked on several new features over the last two weeks, including an upgrade system and a shopping menu. Nevertheless, as I build test maps I continue to find ways to tweak pathfinding so that the monsters behave intelligently, smoothly and aggressively.

One issue is the weight given to creature positions on the map. I give walls and trenches a weight of 9999 to ensure they are never a preferable part of the path. I also poll the creature positions to give creatures some weight–without this, the monsters don’t bother to move around one another, and it’s just not scary.

Fine-tuning of the weight added to squares occupied by creatures has paid off. Below are three examples of too little, too much, and just right. All three screens were taken at the same point after game start, and you can see how many more monsters can reach the player with the proper weight bias.

Weight 0 (no bias). The monsters form a line and get congested. Only 9 creatures have gotten in so far.

Monsters are shaded different colors to show their current movement mode:

Red: Full pathfinding (cannot see target)
Yellow: Uncrowding (cannot reach target and only has one direction to move)
Violet: Has line-of-sight to target and moves toward it Gauntlet-style
Blue: Adjacent to target (attacks repeatedly)
Black: Crowded, no movement options (stunned briefly)

Bias of 50. Still only 9 monsters make it into the hero's room. They take too many extra steps to avoid each other and zig-zag.

Bias of 5. This is the best number I found--14 monsters have reached the hero in the same time. That's a 50% improvement.

Multiple Target Pathfinding

Proper enemy pathfinding AI is crucial to the game design. Prescribed routes were out of the question, since they could be blocked easily and the game wouldn’t be very difficult.

Tarchon uses two different types of movement AI:

Gauntlet style, or simple line-of-sight. If there is no obstacle between the monster and his prey, he’ll just move forward. This looks good in an open area, and doesn’t use much CPU. However, if there are walls between you and the monster, you’ll see the Gauntlet Effect: monsters crowding against the wall trying in vain to break through it.
Full pathing with the Djikstra algorithm. I can’t use the A* algorithm because monsters are going to path to the summoned creatures, hoping to kill them, as well as the main character. A* is much faster because it can favor the direction towards the target “as the crow flies” and be right most of the time, saving lots of CPU. Djikstra maps a path to every walkable square within a radius and takes a ton of CPU.

My first solution was to have each monster launch a pathfinder from its square, looking for any tasty targets in their aggro radius. Since the algorithm cost so much CPU, I set this to a range of about 4 squares in each direction.

This didn’t work out. There would be visible monsters just sitting there, not chasing after the player unless he got really close. Increasing the aggro range to 8 or 9 solved this, but at a tremendous CPU cost. It was bogging down my laptop to have even 20 monsters on the screen.

How Pathing Works

Imagine you are stuck in a labyrinth where the walls are blocks of equal size. At some point, a wizard is going to warp you to a random place in the labyrinth and unleash an undead man-bear on you. It’s vital that you find the shortest path back to the exit from wherever you find yourself. Fortunately, you have a piece of chalk with you.

You use the chalk to draw a 1 on the first tile next to the exit. This means there is1 step left until the exit. You then turn left and mark this tile with a 2, move forward and mark this tile with a 3, and so forth. When you reach a dead end, you backtrack until you find a tile that hasn’t been marked yet, and continue your path there. All you are doing is marking tiles with the value of the adjacent tile +1.

Pretty soon you’ll have marked every floor tile in the maze with a number. When you get teleported, you can see the numbers on all adjacent tiles, and move to the tile with the lower number. No guessing, just following the path you’ve already found.

Solution: Large Radius Pathing from Heroes, Line of Sight and Uncrowding

The shortest path from point A to point B is also the shortest path from point B to point A. So rather than have the monsters calculate their own paths, I have the player and summons calculate a large path using their position as the source. The monsters then request this path data from the gamestate, and can pick the closest target and move there. Because there are only 4 possible heroes on screen at once, this cuts down tremendously on CPU usage.

Gauntlet-style movement still has its place. When the monster has a line of sight to a target, he won’t even bother to use pathing anymore. This not only takes less CPU, but it looks better. Pathing in a large open space can be awkward because the monsters usually move in large horizontal and vertical paths, rather than zigzagging to close the distance to their target.

Another optimization is uncrowding. Before a monster even attempts to use pathing or line-of-sight movement, he checks to see if he can even move in any direction. If not, he gets stunned for 30 frames under the assumption that it’ll be a while before a path opens up. If there is only one direction to take, he will sometimes move in that direction, even if it is away from his target. This helps cut down on the “conga line” phenomenon at bottleneck points.

Pathing torture test: over 100 monsters

Special thanks to Gauntlet, Final Fantasy and Legend of Zelda for the placeholder sprites.

tarchon_pathing1 — On game start, the main character broadcasts his path. Each monster hooks into it and takes the first step towards him.

tarchon_pathing2 — More monsters have spawned and our hero's about to get mobbed. Notice the monsters at the top moved upward (out of the path) to reduce crowding.

tarchon_pathing3 — Over 100 monsters are on the map here. They've overwhelmed our hero.

You can see the uncrowding behavior in bottom right area of the final screen. Monsters have moved downward, away from the player, to rally and let the other monsters through.

Maze Solving

The monsters are pretty smart at this point. Check out how easily they solve this maze and overwhelm our hero:

maze1b — The four moblins have found their path and are on the move.

maze1c — The first two have taken a left turn at the fork because this is a shorter path. But the second two go straight, because there are already creatures using the shorter path. They are considering that a longer path because of the higher chance of being blocked by the first two creatures. With this system, the monsters can flank the hero.

maze1d — They've found the hero, ganked him, and assume their uncrowded formation.