Acmlm's Board - I2 Archive - General Gaming - Game Theory: Testing to prevent "unsolvable" puzzles in games
| User | Post |
Rydain
Posts: 735/738 |
Take your time.  I'm looking forward to seeing what you have put together. |
Wopple
Posts: 41/41 |
It is actualy referring to any "code" in general, and the analysis of that code. Of course, within the context of a certain simple games like tic tac tow or tetris or somethign like that, you could make an algorithm for chcking for certain things in a design or pre design, but the proof is more that you cannot write code that will check for infinite loops within other code (which would basically be a game with such a problem.
My Layout: odd. I do remember, awhile ago, I tried to change it ended up losing it somewhere between previews and edits. So I then checked and my layout worked fine. But if it was messing stuff up, then I guess it was *shrug*
Proof comming soon, about to leave work now... |
Rydain
Posts: 729/738 |
Yes, it was me...and although I haven't worked on my text adventure engine in four years, I would love to see your proof because the subject still fascinates me. What context of puzzles are you referring to - a specific genre, a specific complexity, all puzzles? I can understand that a complex setup like a text adventure with many required tasks would be difficult to prove solvable (assuming it was even possible to begin with), but what about simpler cases?
Dark Cloud and its sequel (PS2) are games with randomly laid out dungeon levels that are always solvable. They'll frequently contain a locked door and a key in a treasure chest somewhere, but you will certainly find the key on your side of the door. I don't know the exact mechanism used to create the layouts, and I've never tried to find out. For all I know, it could randomly select from some sort of limited set of possibilities, and all of them could be set up in such a way that a key chest would not fall on the wrong side of the door to begin with. However, because there is only one simple puzzle involved, I'd think that a truly randomly generated Dark Cloud level could be checked for solvability. Knowing the coordinates of the key chest and the starting position of the player, try to draw a line between the player and the chest. I don't know much about path finding algorithms and what I do know is rusty, but considering that games can move enemies toward you along traversable surfaces, why would this not be possible? |
Squash Monster
Posts: 671/677 |
I ran into this problem when planning out how to make a level generator for a Metroid-like game. I'm pretty sure my solution works, so I'll walk through that. Note that my solution might be considered cheating by some, as it generates games without any possibility of having a "key behind its door" problem instead of detecting that problem in already generated games.
It would be a headache beyond all imagination and a complete computer-eater to generate a chunk of level and then have some form of AI walk through and try to figure out how to get through everything. The first rule of level generators is to never try to do anything delicate once you're getting to the phase where you actually start laying down tiles.
In this case, it's going to be best to make generating the order and rough location of all the items the very first thing you do.
To do this, we'll use a tree structure. For those unfamiliar with the term, a tree is a set of linked nodes meeting the condition that there's exactly one path of links between any two nodes.
For this specific problem, we're going to make it so there are three special types of nodes. One node will be the starting location node. Some nodes will be item nodes -- these are each associated with one item (a key item node is a place you can get a key). And some nodes will be obstacle nodes -- these are each associated with one item as well (a key obstacle node is a door).
1.) Start with one node, this is the player starting location.
2.) Repeat the following steps 3 and 4 until you're sick of it.
3.) Add an item node with a link to a random existing node.
4.) Add an obstacle node coorisponding to that item with a link to a random existing node.
Now, there are a few more steps you'll want to do before getting out of tree mode if you want the game to be reasonably interesting. If you don't want to, just skip to step 8.
(Add an additional list of items to the obstacle node definition. The original item is going to be the required obstacle. The other items are all optional obstacles. When finishing up the generation, the generator can randomly decide whether or not to put these in.)
5.) Repeat 6 and 7 until no changes are made or you're sick of it.
6.) Trace from each item node back to the starting node. Make a list of all the obstacles in the way (including optional obstacles).
7.) Go through the entire map and add all the obstacles you just listed to the obstacle list of any obstacle that already lists the item you started with in 1.
8.) Generate the game using that tree as a pattern.
Also note that before you generate, you can safely link any random pair of obstacle nodes. Mind you, this makes the structure no longer a tree, so if you're going to want tree properties later on, don't do this. Also note that you probably want to do this after figuring out where all the nodes are going to be in 2D space, so you don't have any links that overlap anything. |
HyperLamer
Posts: 7926/8210 |
For a simple game (particularly a puzzle game since they're all logic), it's probably possible to write an AI system that would basically play the game itself and report anything it can't figure out. |
Tamarin Calanis
Posts: 1753/1802 |
Alright, Wopple, I dunno what the hell is wrong with your layout. I tried something that seemed like it'd fix it, but it didn't appear to do anything.
It appears that you've closed too many tables, but I'm not sure.
Anyway, that was just explaining my edit, so you eren't confused. |
Colin
Posts: 11079/11302 |
I think it could PROBABLY be done but you'd be looking at a complex piece of coding. The key thing might be able to be done of, for example, the game checked to see where the player's starting position was and compared it to the key's location.
It would all depend on the game and its complexity though. I have a feeling some less complex games could have such an algorithm, but more complex ones... no. |
Wopple
Posts: 40/41 |
A looooooooooooooooooooooooooooooooooooong time ago someone, I believe Rydain, posted a thread asking if anyone knew how to code something that would check and see if a game would ever stop the player dead, for example, the key for a door is behind it, etc.
The answer, which I don't think was given then, is a resounding NO and it can be proven. I wanted to start this thread partialy as a mental playground and aldo to keep other from trying.
I will post and proof and discuss it later, once more people have responded with a "duh" or "Wait, you can't" or "Who gives a shit!?" |
|
