4
\$\begingroup\$

I'm making a puzzle game where one player makes a puzzle, and other players attempt to solve the puzzle the first player made. The puzzles are a grid of squares that may contain different kinds of traps. There's a wide variety including the following:

  • Traps that do initial damage, but don't fire again when you step on them again
  • Traps that do initial damage, and continue to fire every time you step on them again
  • Traps that do initial damage, and then do damage over time, but who's effect can be stopped with an antidote
  • Traps that do initial damage, and damage over time, but who's effects can not be stopped

In addition to all these traps, I have walls, keys, locks, and blank tiles as well.

I'm currently showing the players attempting to solve the puzzle a "difficulty" rating that I got by taking all traps that deal damage divided by all tiles total. It seems accurate with small puzzles (4x4, 5x5), but when you scale it up (20x20, 25x25), you get deceptively low ratings for extremely difficult puzzles because of the sheer size of the puzzle.

This has led me to try to find a better solution for a difficulty rating. Things I've considered:

  • Figuring out a "damage per tile" average by taking the damage all the tiles do divided by all eligible tiles a player can walk on (factor out walls), but with this approach, I can't figure out how to factor DoT (Damage over Time) tiles into it. For instance, after 10 tiles, I can give an average amount of damage a player will take with regular traps, but how do I give them an average with a DoT trap? They could activate it on the first tile or the last, and the damage numbers are significantly different.

  • Figuring out a "difficulty score per tile" and trying to factor that into a rating. All tiles are currently given a "cost" (the amount it costs the player to use them when creating the puzzle), and that number roughly correlates to how much difficulty the tile adds. I was thinking about using that number to get a difficulty rating, but I'm unsure how I'd use it correctly.

  • Trying random solutions and seeing how long it takes a bot to solve it. I don't think this is a good solution for a number of reasons. It could be solved on the first try by sheer luck, and hide how difficult the puzzle is. Plus, with keys and locks, backtracking is required, and I think the computing time to run these simulations would be cost prohibitive.

  • Ditch difficulty ratings all together. If I can't figure out an intuitive way to show the player how difficult a puzzle is at a glance, I might just have to remove it.

I realize some of this might be hard to visualize, so here are some pictures of a puzzle and it will hopefully help you see what I mean:

This picture shows a puzzle including tiles that would normally be hidden from the user until they were activated (such as spikes/nails)

The user starts at the star and makes their way to the exit. This is a view with all the tiles visible, and when the user attempted to solve it, a lot of the tiles you see in that picture would be hidden from them until they were "activated" (by the user stepping on them).

\$\endgroup\$
  • \$\begingroup\$ Here's a simple tweak: instead of scaling the difficulty by the number of tiles, try scaling by the perimeter (width + height) * k. That should solve large drop-off in difficulty for large puzzles. \$\endgroup\$ – congusbongus Feb 11 '14 at 22:41
3
\$\begingroup\$

I would write a puzzle solver using Dijkstra's algorithm, which would find the optimal solution for the puzzle. This algorithm trivially returns two measures for the difficulty:

  • How many steps are in the optimal solution
  • How many iterations did the algorithm take to solve the puzzle

The higher the numbers, the harder the puzzle is. You need to experiment how to combine these values when calculating the difficulty.

In Djikstra's algorithm you need to implement a check to ensure that a node is not visited twice. Because of powerups and keys this check needs to be a little more complex. You need to record the state of the player (health and possessed keys) for each visited node and compare that as well. If the state of the player is better than previously, a node can be visited again.

This algorithm will take some time to run on more complex puzzles, but I believe it would be fast enough to be practical, as it only needs to run once.

If this is not sufficient, you could try optimizing it with A* or D* Lite. Neither of those would be very easy though in your situation because of the dynamic nature of the level.

\$\endgroup\$
  • 1
    \$\begingroup\$ My concern is that with a puzzle like the one I linked, I think this algorithm would probably work. Imagine a puzzle that's 10x10, completely filled with bombs except for a single pathway that gets to the finish. The algorithm would find the solution rather quickly I'd imagine, and there may not be many steps in the ideal solution, but for a player who doesn't know where that path is located, the puzzle is very difficult. That's what I'm trying to capture. Do you think this algorithm would do that? \$\endgroup\$ – snollygolly Feb 11 '14 at 13:53
  • 1
    \$\begingroup\$ @SLoW puzzle evaluators are all going to be very specific to the puzzle at hand. The best you can do is find some suitable metrics and experiment with a weighting system that fits best. \$\endgroup\$ – congusbongus Feb 12 '14 at 0:29
2
\$\begingroup\$

Assuming that you have an online game with a non-trivial number of players.

Do note that the difficulty rating doesn't need to be fixed and unchangeable.

First, make any heuristic to roughly estimate the initial difficulty - any of your own simpler suggestions would work, don't put much time in it, anything that's somewhat sane would be enough.

Second, measure how your players behave on the existing levels (where you're sure of the difficulty rating) - what is the % of failures, time spent on the level.

Third, as soon as real, live players have played the new user-created puzzle a few times, ditch the initial estimate and update the difficulty according to how they behaved on that new puzzle - if the time/failure%/whatever is similar to the existing 4-star puzzles, label it with 4 stars, etc.

\$\endgroup\$
  • \$\begingroup\$ That's an interesting idea. The way the game is, once a puzzle is solved, it's no longer playable by anyone else. So any attempts prior to solving it must be failures. I'm already showing how many people have attempted it so far, so maybe factor that number into the difficulty? \$\endgroup\$ – snollygolly Feb 12 '14 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.