It's ugly, but it exists!
Well, I created a simple puzzle game to test the power of my search-and-reroute algorithm. Here it is: AdaptAmaze (1.3 megs).
This is a proof of concept. It isn't a game by any stretch of the imagination. But it is good to see the algorithm work. (It's actually slowed down a bunch here, for debugging purposes.)
You control your little blue token with WSAD controls, trying to get to the little green token. In a transparent attempt to make it more "gamelike", there's a fog limiting your visible range. Press "F" to toggle it.
The maze starts completely random. It probably cannot be solved as it stands. I have given you the power to choose your destiny. "P" finds a path and modifies that path towards the difficulty level you've specified.
The two text boxes in the upper left control size (smaller is more tiles) and difficulty (higher is more steps). Don't worry - modifying them prints a clear message, so you don't have to remember.
All you need to remember is WASD, F, and P.
By the way, the game has a hardcoded 10 iteration limit. This is fine in most situations, but in the most extreme situations (such as being 3 steps away and setting the difficulty to 30, or visa-versa) it can simply not work. Repeatedly re-engaging the path engine can usually "drill" a more suitable solution into the game.
In a game with more complex constraints, this wouldn't be a problem. The "space" between you and your target would stretch. Also, it would be passably easy to create special cases for the extreme situations.
But I didn't. :)
This is a proof of concept. It isn't a game by any stretch of the imagination. But it is good to see the algorithm work. (It's actually slowed down a bunch here, for debugging purposes.)
You control your little blue token with WSAD controls, trying to get to the little green token. In a transparent attempt to make it more "gamelike", there's a fog limiting your visible range. Press "F" to toggle it.
The maze starts completely random. It probably cannot be solved as it stands. I have given you the power to choose your destiny. "P" finds a path and modifies that path towards the difficulty level you've specified.
The two text boxes in the upper left control size (smaller is more tiles) and difficulty (higher is more steps). Don't worry - modifying them prints a clear message, so you don't have to remember.
All you need to remember is WASD, F, and P.
By the way, the game has a hardcoded 10 iteration limit. This is fine in most situations, but in the most extreme situations (such as being 3 steps away and setting the difficulty to 30, or visa-versa) it can simply not work. Repeatedly re-engaging the path engine can usually "drill" a more suitable solution into the game.
In a game with more complex constraints, this wouldn't be a problem. The "space" between you and your target would stretch. Also, it would be passably easy to create special cases for the extreme situations.
But I didn't. :)
posted by Craig Perko at 4:18 PM
4 Comments:
Interesting... But I don't know if the algorithm works quite the way it needs to.
From what I've read, this is how I understand how the system is supposed to work. The object it to get to the green destination. The challenge level is then the number of rooms that you have to pass through to get to end. The path-solving/modifying algorithm's job is then to analyze the current (if available) path and modify it more closely matches the challenge rating you have set.
I found that the program was unable to determine (in most circumstances) how difficult the current path was. In fact, in most cases where a path did not exist, the goal should have been to modify it so that it would be closer to a real path. The program seemed to change unrelated areas of the map without altering the goal area at all.
I also have a question: Are the initial mazes generated logically, or randomly? It would make more sense to build the maze so that it is a logical, solvable maze with a given difficulty. If the analyzed map then becomes to difficult, due to player alterations, the system can generate new paths within the maze.
Actually, I think it would prove the original algorithm much better than an initial random set. I assume that the games that Perkplot is used with will not be randomly generated, but will contain at least some logical, and solvable, content. Then through play and player alteration of the base system, the game alters itself to become more or less challenging to suit.
Of course non-random seeds would be better, but I don't have the time to make a dozen complex mazes. So, random has to be acceptable.
I did notice that it occasionally gets "stuck" - I'm not sure why that is. But when the algorithm isn't stuck, it's not modifying random things at all.
When it's making an existing path longer or shorter, it modifies only the path! However, it modifies the shortest path. Are you sure what you see as "random pieces" isn't just another path to the goal?
Also, when there's no existing path, it doesn't clear a direct path. It clears a path that should take (difficulty) steps to run through. So, when it randomly modifies bits of the map to create a valid path, it's not random at all. It's finding the piece of the path that is likely to produce a valid path of the right length.
There are two tweaks I would make. First, I would make it search from both places instead of simply searching for the goal from the player. That would help, but it's not all that critical for this little program.
Second, I could make it check when it's clearing a valid path that it's not breaking through into a part of the map that was already available in comparable time. That's actually pretty easy to do, it just didn't occur to me. I might do this tomorrow and see if it makes a notable difference. (This is probably what's happening with the "random pieces of the map"...)
Because the iteration is stuck at 10, it can fail to finish "drilling" a proper path, but none of its actions are random.
I wouldn't necessarily design a set of mazes. I'd write a simple algorithm to intelligently design an initial path through the random (or empty) area. From there you would then know that a path exists. You could then measure the difficulty of the path (number of steps from start to finish, number of turns required, number of doors, number of dead ends/false paths) to quantify a challenge rating.
Then you could allow the system (knowing a path exists) to alter the path (opening/closing walls) to create an easier/harder maze. The example seems to work, but I don't know what it is doing behind the curtain, so I have no idea if it actually proves your hypothesis.
Hmmm. That would require another algorithm...
This one creates "mazes" literally by slapping random walls up. Each room's wall (each has four walls) has a 40-50% chance of being up, with another 20% chance that the room is blocked entirely.
I wanted to simulate an attempt to modify a terrible writer's game. I wanted to show that even if what they wrote made no sense at all, it is still possible to find a route.
Obviously, this is a labyrinth, not a plot, so there is a limit to how far you can stretch what is shown.
If I want to prove better, I'll do it using an actual meta-plot system, rather than modifying the labyrinth game.
Post a Comment
<< Home