Hey all, I'm generating random Pacman maps for my Tiny TV Jam game. So far, I have what are called "perfect" mazes being generated, using a common algorithm similar to recursive backtracker. The problem is that a "perfect" maze is one with a start, an end, and only 1 path from start to end.
Pacman mazes aren't designed in such a way, as they are what are called "fully braided" mazes - they have zero dead ends, so all corridors are interconnected. I've done a little research into how a fully braided maze might be generated, and unfortunately there don't seem to be any actual algorithms for doing this. I have only found people who have asked about how to do it, but no real clear answers, only hints about how one might go about doing it.
The best suggestion I found was to generate a normal "perfect" maze, as I am doing now, and then making a "walker" that goes through the maze once it's generated, looks for dead ends (an open tile that's only connected to 1 other open tile), and then removes them either by deleting a wall to connect it to another corridor (if possible), or if not possible to connect it to another corridor, PLACE a wall to fill in the dead end. Then have it repeat walking through again until it's covered all open tiles and verifies all the dead ends are removed.
The problem is that this all sounds a little bit over my head. I have no idea how to go about doing this. I know that the game will not be playable if there are dead ends in the map, because the AI will inevitably get you at the dead end, so it would make the game impossible. Here's my map generator (press Z to generate new maps; orange tiles are walls, purple are paths):
I can help!
Thanks to the way your generation algorithm works, every dead-end will be separated from another path by just one wall. So all you have to do is detect dead-ends (floor tiles surrounded by 3 wall tiles) and then remove any one of the 3 walls surrounding it!
Special case though: if the wall you're removing is on the border of the map, you should also remove the one at the opposite border if you want your map to loop!
So it'll work a bit like the collision system then? Like, iterate through each tile, if the tile is open, check the pixels on either side to determine how many are open? Or is there a better way than pixel checking?
The whole grid is stored in an array, with open ones being true and walls being false (or maybe it's vice-versa, I'm not looking at the code as I write this), so maybe it'd be faster to loop through the array? The only problem with that is that it could be a bit complex due to the arrangement of the map and the array elements. I almost feel like checking the pixels would be easier to implement, but I'm not sure.
Side note: The algorithm can also tend to sometimes generate long corridors - walls several cells in length without openings. I think in Pacman, there's never a wall that's more than 3 tiles wide, so opening up some of the longer walls may also help make the maps more Pacman-like.
I think you would be better off checking the array directly.
You just have to make sure you get your coordinates right. But yeah basically you're checking every cell's neighbors and if that cell has three 'false' (wall) neighbors, then you just make a random one of these neighbors 'true' (floor).
Yeah I think you're right. Checking every pixel just sounds horribly inefficient, especially when we have an array with all of the info we need already in it. I think opening up doors in long walls will be a very similar function as well. The only thing I need to check is that it doesn't create a "room" in doing so, since all corridors must be 1 tile width.
I think the check would be something like, if there are more than 3 wall cells along a horizontal or vertical path, we need to remove 1 cell from the wall. Then, in order to not create any 2-wide openings, eligible cells for deletion cannot have more than 2 open cells already touching them. So, any wall with 3 open cells touching it cannot be deleted, and any cell with 2 or less can be marked safe for removal. We can then build a list from that and choose one at random to remove.
Thanks man, it's all starting to make a lot more sense in how to do it! I just hope I'll be able to finish this game in time before the jam ends. The AI code is already done (explained here and demo), but basically we will run a function like this whenever we are at an intersection:
function dst(fx,tx,fy,ty) return sqrt((fx-tx)^2+(fy-ty)^2) end
This returns the distance between points A and B. For every valid tile the AI can move to next, you just use that to find which one is the shortest distance to the player. It's not as accurate as A but I think A would make a Pacman-style game too difficult for the player, since the AI would never make mistakes or take sub-optimal paths - it would be too relentless. Unless you purposely coded it to sometimes do some dumb moves, but then you may as well use an algo like this one anyway. I think there will be 2 ghost AIs instead of 4, given the map size. One will have the target tile being the player's current cell position, so he will usually be chasing you, and the other will target a few tiles in front of the player, so he will be trying to always get in front of you. This will add some challenge and make them have individual 'personalities'/strategies, and less likely to group up on top of each other.
The last thing to do for the game will be, as you move along the purple paths, the cells you touch turn black. So basically, you are going to be eating the purple tiles, like the pellets in Pacman. You complete the level when you have covered the whole maze. I also want to add power pellets near the corners (just find a random open tile near each corner and place one there, I guess), so you can make the AIs vulnerable, at which time they turn blue for a short time and you can eat them, like in the real game!
It's going to be quite some work, but I think I can do it in time provided the map stuff doesn't prove too challenging to work out. If it comes down to it, I could just have a set of a few pre-designed maps and have it choose one at random, but this takes away from replayability, I think, and also the procedural maps are a good learning challenge.
Anyway, /rambling, and thanks so much for the help!
Alright, I got it! Thanks a ton @TRASEVOL_DOG for the advice!
No dead ends, no rooms, and no walls that are longer or wider than 3 tiles! :D
Press Z to generate new levels. Player spawns in different locations each time.
I wouldn't even call Pac-Man levels "mazes". You can hardly get lost. :)
How about something like this:
- Map only has an outline rectangle you can walk along
- Pick a x/y coordinate and go up/down both ways until you hit a walkable tile (you could first do horizontal and then vertical lines, lines could be mirrored so you have a nice symmetry)
- Continue until good enough (ratio of walkable tiles vs. non-walkable tiles is higher than 20 % for example)
@kometbomb yeah, you're technically right about them not being mazes, but also technically not :P They are considered "fully braided" mazes, which is a type of maze which has no dead ends. There is no start or end though to these maps, so that does certainly make them less maze-like. While in Pacman, the goal is to cover every walkable tile in the level (every tile has a pellet that has to be collected, so the goal is just to cover the entire maze), there is still no set "endpoint".
So to generate them, I started by generating a normal maze (using a standard algo that generates a start point, end point, and a single solution to get from start to end), complete with dead ends, and then remove the dead ends so that all paths are interconnected. Then what I chose to do additionally was make it so that no walls are longer or wider than 3 tile lengths, because having long corridors with no outs would make the game too hard, I think. Also the levels come out more Pacman-y.
The method you suggested for generating the maps is definitely a good one and I hadn't thought about doing it that way. Probably much simpler than the method I chose, but I'm going to basically call the map generator done for now, unless bugs are discovered or someone wants to come up with a way to make levels that come out nicer.
As for accounting for the number of path tiles vs. wall tiles for consistency between generated levels, it seems like the levels I'm making here are fairly consistent in that regard. I'm not going to say they all have the same ratio of paths:walls, but they seem pretty close. One thing I think could be better is that some levels have more tedious obstacles than others; more small stuff that you will have to go around. That could lead to some inconsistencies in difficulty. Just like in regular Pacman, you will have to cover the entire map, so levels like the picture below might be more of a pain than others:
[Please log in to post a comment]