Okay, well I messed up. In the last entry, I said that Ms Pac-Man was pointlessly gendered because the only difference was the bow on her head. This was incorrect. Not only does she have lipstick but also the gameplay of Ms Pac-Man is significantly different. Without going into too much detail, here are the differences:
I forgot to mention the fruit. In both games the player character is given fruit to eat. In the original game, this fruit appears near the middle of the maze and stays there. In the later version, fruit appears and moves around the maze and the player character chases it as well as being chased. There are also different mazes at different levels, whereas in the first game the same maze is simply repeated, four in fact, depending on the level. Ms Pac-Man has more dead ends, and I’ll come back to the maze issue in a bit as it’s quite significant in what I’m doing.
The ghosts’ AI is improved. Pac-Man has predictable ghost movements. Ms Pac-Man’s ghosts have more randomised behaviour although if I recall correctly the behaviours exhibited previously are mixed between the characters. This makes their movements harder to anticipate.
The second game gets faster as it goes along, which of course is similar to Space Invaders except that in that game it’s an unintentional feature resulting from the game having less work to do per loop as the invaders are shot. Regulating the speed of games was, incidentally, an issue for a long time as the same games were played on faster computers, and there used to be a utility to slow down older games, which is presumably still a problem for DOS games written in the early 1980s CE. Back at the very start of the IBM 5150’s history, and I’ll explain that in a bit for people who don’t know, some games didn’t use the operating systems – argh, look, I’ll just explain this whole thing. It would be remiss of me to mention this intriguing aspect of computing in the ’70s. I’m about to make a massive digression, which will go in another post (not here yet).
But anyway, yeah, Ms Pac-Man used to get faster as the game progressed, which entirely makes sense and was not a bug made into a feature. It also wasn’t developed by Namco and in some countries ended up outselling the original game.
Pac-Man and Ms Pac-Man both use imperfect mazes because they’re not supposed to be puzzle games but chasing ones. A perfect maze has exactly one route through it. If these games were like that, the risk of getting stuck in a dead end would be too great, the game would be too hard and it wouldn’t be fun any more. It probably wouldn’t be unplayable but it would be immediately hard. Yesterday’s type-in maze is quite conventional:
There are maze-drawing and maze-solving algorithms. I know more about the latter than the former, and the one I remember involves choosing a side to follow and finding your way out that way, which doesn’t work if the maze includes islands. As for drawing, a perfect maze is basically a tree in graph theory terms. This makes sense if you imagine something like a tumbleweed curled up in a two-dimensional box.
This is an example of a perfect maze with the entrance at bottom left and the exit marked in orange. If you straightened this out, you’d end up with a sort of tree-like structure, so one solution would be to come up with a tree and roll it up. Unsurprisingly, there turn out to be many different ways of drawing mazes and whereas I could get hung up on exploring them all I want to get a move on, so I’ll just mention a few. Incidentally, I’m aware Pac-Man doesn’t use that kind of maze and I’ll come to that.
A maze is a grid of cells and a set of pathways. A good maze is one with neither zero nor all possible paths through it. In other words there should be at least one path through a maze. A perfect maze has just one path between any two points. Making a maze involves either burrowing through a block or putting walls up. A graph, in graph theory terms that is, with a single path is a tree. This immediately suggests to me another game where you start as a single-celled organism and work your way through a maze to one of the species alive today. You’re presented with your “amoeba” (which it isn’t, but let’s not get into that) and two different descendants. You choose one of them and are presented with two further descendants, or even more than two. Your goal is to reach a particular organism, and of course many people would want to aim for a human. Just a side thought, and there the maze is not visible to the player. I think this might be what Spore is but I don’t know.
On making the maze, nodes cannot be visited twice. If that happens, a dead end is created, or a closed-off path. When this happens, retrace your steps until other options exist, then move forward again. This is known as the Depth First Search. Another option is Hunt And Kill. With this, you start somewhere and move in a random direction, burrowing out a passage to places you haven’t been before until the current position has no neighbours which haven’t been reached. Then you go across the grid looking for unreached cells which are next to reached ones, link the two and start from that cell. Carry on doing this until all the cells have been visited.
I don’t plan to do either of these, partly because I find them hard to understand, but there are lots of other ways to do it. The one I plan to use was discovered by a Minecraft player and is called “Origin Shift”. It’s a bit weird because you start off with a perfect maze and modify it to make another one, which sounds pointless, but perfect mazes can be very boring. For instance, they can just be a load of horizontal tunnels, the last of which reaches the exit, but they’re all parallel and linked by a vertical tunnel at the other end leading from the entrance. In terms of graph theory, this can be thought of as a grid of directed nodes, i.e. each one has an arrow pointing to another one, and one’s the origin, i.e. the entrance or rather the starting point, and points to nowhere. You follow the arrow to the next node, and at this point I realise I haven’t understood it, which is useful because I need to and that’s partly why I’m writing this. Right. Choose a random neighbouring node to point to it, then shift the origin to that node and make it point towards the one you’ve just visited. Set the new origin node to point to nowhere. Keep doing this, and the maze will gradually become more interesting and complex.
The way I’ve conceptualised this, and I don’t know how to express this in Python right now so I’m going to call it a two-dimensional array, is to have five characters as labels for the arrows, the origin being “O” or “0”, and the others being either “N”, “S”, “E” and “W”, or “U”, “D”, “L” and “R” (Up, Down, Left and Right). I don’t like the compass direction approach because I think there’s a cultural bias which puts north at the top, so it’ll probably be the second, and yes I know nobody will be aware. So the array starts out as rows reading “RRRRRRRD”, with the last one as “RRRRRRRO”, and the algorithm then changes the letters appropriately. It occurs to me, as it has before, that there are only five options and a character array is really wasteful, particularly in Python 3 which uses Unicode and so sixteen bits per character, and I really despise how sloppy memory use is nowadays although I’m not sure why it would matter any more, so it goes somewhat against the grain to use sixteen bits per node rather than three but I’ll probably do it anyway. This process can go on as long as you like, even forever, and in fact it could even go on while the game is being played, and the easier mazes would be simpler and therefore more boring than the later ones.
Okay, so this is all very well you might be asking yourself, but what about Pac-Man? Surely it can’t work with a perfect maze? Well no, but that’s the beauty of the thing! I haven’t tried this yet, but this algorithm produces one perfect, and therefore hard, maze, but from this maze four further symmetrical mazes can be derived. This works well with square mazes. If you cut each maze vertically down the middle, “throw away” one side and create a mirror image on the other, you then have a more Pac-Man-like maze. You can do this four times, two vertically and two horizontally, so five mazes are available from this original one. These can all be organised into the same three-dimensional array. They would become familiar, but the issue is not to solve the maze but to run around it. Needless to say, probably, there would be tunnels inserted on either side to make it possible to pass through when it wraps around.
Why not just throw the original maze away though? Well, remember this is a Pac-Man game for mental health issues. The original maze is to be used to represent depression, because it has many dead ends and you can easily become trapped in it.
I’m sure you’ve noticed the massive digression in this post which seems to lead to a dead end. I wonder if there’s a way of mapping a piece of writing and turning it into a maze.
A Box Of Chocolates 