I have started to work on a Pacman style game and I want it to have randomly generated maps. I quickly realized, however, that I don't really know how to make a randomly generated Pacman style map that looks good. Does anybody on here have a Pacman game with a random map system that I could look at?

I know how to make randomly generated mazes, but since Pacman doesn't really have a "maze" the algorithms that make mazes don't produce good looking Pacman levels (in my opinion at least).

The main problem I realized is that you can't just randomly put a bunch of walls on the screen. I am trying to preserve one thing about the original Pacman game's walls:

The game only has one path of dots on the screen that can be followed. In other words, you can think of the Pacman grid as being a system of tunnels that are only as big as Pacman and no bigger. The walls interlock to form tunnels that are only as wide as Pacman. If you randomly put a bunch of walls on the screen it's hard to preserve that feature.

What I currently have is a system that produces a bunch of walls like in the jpeg shown below:

{"name":"591485","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/9\/692858f501f5f82ca8ed39648c9a17d8.jpg","w":632,"h":477,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/9\/692858f501f5f82ca8ed39648c9a17d8"}

You'll need to make the walls thin and not tileset blocky.

You could do what you just did with the ground generation, then go through the map and see which directions you can move. For each of the tiles' up|down|left|right; if it is impassible, then put a wall (line) there.

Also remember that pacman maps are left-right symmetric.

That may work well if you generate 1/4 of the map and mirror vertically and horizontally to make an entire map. That would keep the symmetry there. For example:
{"name":"img","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/9\/a969d0f721a1e754b1a5d2d2edc68297.jpg","w":632,"h":477,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/9\/a969d0f721a1e754b1a5d2d2edc68297"}

Thanks for the replies. I think I will mirror the map like you two suggested. I also changed my random block system a little to generate smaller blocks. When I get my grid code finished I'll show you all what it looks like.

Here's my pacman-oriented random map generator. Comes from my unfinished project of a pacman clone

If you run t1.exe in /test you should get an image dump of the generated map. It looks like I wrote that in 2005, so I can't guarantee I can give much help about it, but comments are in the code and you can of course ask, I try to answer to my best

Included is the Mersenne Twister(downloaded at the time of coding) random number generator.

[edit]

It doesn't generate mirrored maps, and it supports any resolutions, but the map checking code for 1280x1024 can be a bit slow, the algorithm is very simple.

Here's an image of a generated map @ 640x480

{"name":"591503","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/b\/7\/b792f1dd3909746045183a3d8c39aa80.png","w":640,"h":480,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/b\/7\/b792f1dd3909746045183a3d8c39aa80"}

I don't like the dead ends all over the place.

Marco, did you post a link to your code? I am not seeing any download links for your code in your post.

Anyway, I added a symmetrical setup now with a gap area where the ghosts' "base" is going to be. In the following screenshot there are no variations in the wall blocks because I got rid of some of my earlier code. I am working on a new block making system where I have to hand design the blocks (the blocks are represented in the program by integers ). Once I put a block in I can have the block randomly be flipped vertically, horizontally, or rotated to add some variations to make one block look like a different block. Right now there is only one block type in the game. Eventually I am going to put bitmaps in to make the blocks look a little better than a filled rectangle.

{"name":"591506 ","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/6\/66c62cb0f8dfff0e60f260cd840c900c.jpg","w":460,"h":443,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/6\/66c62cb0f8dfff0e60f260cd840c900c"}

Personal taste IIRC there were in the original PacMan, don't they?

[edit]

It's attached in my previous post

That's just the thing; there weren't. There are no dead ends in Pacman.

Marco, the program stuff you attached is missing the "map.c" file.

Cool So mine could have a special feature

[edit]

Sorry, attached here the right package.

Here's a tip. Start with a basic map that has no walls, but all the intersections laid out. (Thus a map made entirely of 4-way intersections except for the map boundaries.) Now, add walls at random, making sure to maintain symmetry, but before you add a wall, check the two spaces the wall will affect. If either of those spaces already has two walls around it, do not place the new wall and move on. This will prevent dead ends from forming.

Keep this process up until you have a suitable number of 2-way, 3-way, and 4-way intersections. Also make sure to have a bailout in case it becomes impossible to construct more walls without breaking the randomization limitations.

--- Kris Asick (Gemini)
--- http://www.pixelships.com

Part of the problem is that I started by coding the walls as blocks that are drawn from an array. The walls are blocks and not actual walls. Generally, when making a maze using a maze algorithm you assign vertical or horizontal walls to each cell in the maze. However, I wanted to try something a little different so my walls are not actual walls but instead are blocks. I had started out doing it like that because I realized that Pacman doesn't use a maze and I didn't want to have to tweak a standard wall drawing algorithm to make a good Pacman level.

I am kind of getting some neat results now, this is a recent screenshot with only two different block types implemented:

{"name":"591540 ","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/1\/8155214619a3533f0730ea0c0b5c58e0.gif","w":483,"h":429,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/1\/8155214619a3533f0730ea0c0b5c58e0"}

If I could add my own 2 cents here...

Looking at your original snapshot, you could probably reproduce a random map by having several 9x9 grids pre-defined (I think you need about 32, IIRC. This comes from a post about tile transitions. About halfway down (Figure 3), he shows several "corners" and "sides" together.

If you were to take this approach, and randomly select any of the tiles (0..31), you could create a map very similar to what you originally posted here, and do some simple checks to make sure you don't have any boxed-in areas. Then when your map is fully generated, erase the "ghost house" in the middle, and go from there.

As you would only need to randomly generate the map before the level starts (like in a menu screen, waiting for user-input), all your expensive tests could be done before the map is even shown to the player.

You could also combine this with a pathfinding (like A*) algorithm to test that all "routes" are accessible for PacMan as well as for the Ghosts.

Although, I do like Marco's blue PacMan map quite a bit...