How would you go about generating these puzzles?
Monkey Forums/Monkey Programming/How would you go about generating these puzzles?
| ||
| I love Inspector Parker, it was one of the games that really rekindled my interest in the Indie scene as a developer. http://www.shockwave.com/gamelanding/inspectorparker.jsp <- Play in browser http://www.bigfishgames.com/download-games/128/inspectorparker/index.html <- Download This might be a little hard to follow, if you haven't played the game, but here goes: Every level is randomly generated consisting of a number of floors, each with a number of rooms, in which are scattered objects related to the crime you are trying to solve. The same object will appear numerous times in numerous rooms. You also receive a number of clues. The clues are things like, "The bottle of laudanum is one room to the left of the old lady," "The man in blue is in the same room as the rocking chair," "The knife is 2 rooms above the spider," or, "The baby is X rooms to the right of the ransom note." You use these clues to select the right knife, the right old lady, etc, until you have found them all, then you have solved the crime. As far as I know, every level provides enough clues to be solved. I'm curious how other developers would go about generating such levels, and the clues to go with them. How would you select the "real" knife from all the knives you throw into the rooms; how would you decide when to give an exact number of rooms in a clue, and when to say "X" rooms; how would you make sure all the clues meshed, properly; how would decide how many and which type of clue to provide so the level can be solved? Step one seems easy enough, just select one of each item at random. Generating clues seems simple if you're only working with rooms that touch, but when the stages grow taller and wider, and things can be separated by multiple rooms, it gets tougher. I'm not really satisfied with the solutions I've come up with, so far, and I am wondering how other people would solve these challenges. I have a feeling there's some elegant grid-based solution I am missing. |
| ||
| Everett Kaser (http://www.kaser.com) is the king of this type of game. I'm pretty sure the technique for any sophisticated game of this type is to build a solving engine, generate random boards, and add clues (just true 'statements' selected at random) until the engine can solve it. If it takes a while to generate a puzzle, you can pre-generate them and embed them in the game. That's not the only way to generate such logic puzzles (my 'Detective Chess' (http://bindweed.com/webgames/detectivechess/detectivechess.htm) doesn't use it, but it's probably the best and most general way. Detective Chess uses an exhaustive search of all possibilities rather than a true solving engine. It works because when I generate fixed positions for chess pieces, the number of combinations required to make an interesting puzzle doesn't get out of hand. That's not going to work for every puzzle type, though. If I wanted to make similar puzzles without the fixed piece positions, I'd need a real solving engine, because exhaustive search wouldn't be feasible (for 5 pieces, I'd have to solve for 7624512 possibilities, instead of only 120). I think that is probably the case for all but the smallest Inspector Parker type puzzles. |
| ||
| Now that's interesting. Thank you for both the link, and the thoughts on generating the puzzles. I've used a similar solving technique for other types of games, including one particular approach to Match-3. So, you're saying the generation flow might looks like this: - Create a grid of X by Y rooms - Place items in the rooms - For each type of item, designate one as the "correct" item* - For each correct item, generate a true statement about that item's relationship to another "correct" item, such as "The spider is two rooms above the knife." -- Check if this clue, plus all other clues about this item, expose this item as definitely being the correct one* -- Check to see if marking that item is enough to solve the case - Go back to the clue generating code. Repeat until board is solvable. * Otherwise, you're generating clues about random objects. Instead of THE spider is next to the knife, you get A spider is next to A knife. ** No point making, like, twenty clues about the spider when the first two clues definitively reveal which spider is correct. Does that sound about right? |
| ||
| - Create a grid of X by Y rooms - Generate one of each type of item for each room that may hold such an item (i.e. N creatures including one spider, N weapons including one knife.) In most Everett Kaser games, N = X*Y I..e. each room has one of each kind, but it seems Inspector Parker uses a smaller N. - There is no special meaning of a 'correct' item: each room that can have an item has exactly one item of that kind. The puzzle is solved when you have identified them all. Repeat: - Create and add a random clue - Try to solve puzzle Until puzzle is solvable There is a further stage which is in fact done (or something very similar) in Detective Chess but I forgot to mention: For each clue: - Remove this clue - Try to solve puzzle - If puzzle is unsolvable, put back clue This should answer your ** point. You may have twenty clues about the spider, but most of them will be knocked out again in the final stage. However, I do agree it might help in some puzzles if you use a heuristic to select good clues. One might be that the clue made some measure of progress in the first loop; another might be that it references objects that are not referenced much in other clues. Or you could combine both. |
   |