How can I estimate the difficulty of user-generated content in my puzzle game?

Question

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:

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).

Answer 1

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.

Answer 2

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.