Pac-Man Vs Ms Pac-Man And Mazes

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.

110 Possible Blog Posts

Or, if you prefer, nine dozen and two.

I don’t know if any of you blog using WordPress, but one of the things you get after a while of using tags (I only started doing that fairly recently) is a list of the ones you use most often. Probably because of the decimal bias of our cultural hegemony, it lists the ten. In my case, this is probably not a good guide to getting more readers but then I’m not particularly interested in doing that, except maybe as a kind of game in which I hope I wouldn’t become emotionally invested. It makes me want to draw a diagram, or rather a pattern:

Apparently this is called a “complete graph” and is described as a simple undirected graph in which each pair of distinct vertices is connected by a distinct edge. The above image shows a K₁₂ , apparently. Because of the decimal bias, my ten tags can be linked up in a similar diagram with rather fewer edges. I used to have hours of “fun” getting computers to draw ever more complicated complete graphs. The distinction also ought to be made between undirected and directed complete graphs of this kind.

There is bound to be an equation which tells you how many edges are needed for a given number of vertices, and in fact there is. It’s:

w_n+2=n!e_n

. . . where “e” is Euler’s constant. No, hang on a minute, that isn’t it apparently as it isn’t necessarily an integer and these obviously will be, so it’s:

(n(n-1))/2

Okay, so plugging in my ten tags gets me (10(10-1))/2, which is forty-five. So much for my title then! I’d worked it out at a hundred and ten but it seems it’s smaller. So then: ninety blog posts.

Here’s what I’m thinking. I have ten tags listed. A fairly crude way of generating blog post ideas would be to combine pairs of them, perhaps in both directions. They are: Philosophy, Ethics, Christianity, Judaism, Veganism, Racism, Evolution, History, Star Trek, Politics. Most of the time, if I blog on one subject on that list it’s likely to involve more than one of the others, which adds to the number of possible combinations in the graph, but it would also be interesting to see what I’ve missed, using those as major foci for a post. For instance, veganism and racism is something I’ve written about before, but not in a “pure”, more focussed sense, and there’s also racism and veganism, which could be something quite different. In pursuit of that combination, there is a lot to be said. For instance, veganism is perceived as a very White project even though, for example, I-Tal diet in its most complete form is RastafarIan and there’s also the question of the growth of supposèdly vegan products in the Third World as cash crops for export and forcing up the prices of something like quinoa, putting it out of reach of the communities which have traditionally eaten it. All very fruitful subjects. There are apparently forty-five pairs of tags in one direction and another forty-five in reverse. Judaism and Christianity is another interesting subject which it would be very easy to write something about, but writing something original and respectful might be a lot harder.

Thinking about writing in this way links mathematics and composition, but as a fairly naïve mathematician I may not be the person to do that. I often find that when I try to connect mathematical activity to something usually considered non-mathematically, I come up with a lot of mind game-type ideas but not much which is particularly applicable, or sometimes something which fits quite well into a particular mathematical activity but is also amenable to common sense. The question in my mind right now is, how useful is it to think of pairs of blog tags as a complete digraph? Is “evolution and Star Trek” a different topic to “Star Trek and evolution”?

Incidentally, the reason “Star Trek” crops up in that list is that I’ve reviewed every episode of “Star Trek TOS” and written several other more general posts on the series. It’s the kind of thing you might expect to generate a lot of views, or maybe not because so many people must be writing about it. I feel, unfortunately, that although it’s a major cultural phenomenon it’s also quite naff to write too much about it.

The above graph apparently also forms the net of an eleven-dimensional simplex, because every complete graph is a projection (the way it’s represented here, in two dimensions) of a simplex of K_n-1 dimensions. Hence this image:

is the net of a tetrahedron. And it clearly is: you can see the faces at the front and back, paired off and seemingly at right angles to each other. Each vertex connects to each other by three edges, and that gives the essence of the simplex in a way. My K₁₀ graph would presumably have each vertex joined to the other nine, each edge forming a polygon enclosing a face, each such polygon enclosing a tetrahedral cell, each tetrahedral cell forming the solid limiting a four-dimensional simplex, and so on. Each one of these encloses a possible combination of tags, more than one this time, and we’re in the realm of factorials and the possibility of more than three and a half million possible blog posts which can be appropriately tagged in various ways from that list, and will be found in the depths, if that’s the right word (it isn’t). This, then, is the hyperspatial approach to blogging. Each tag is located at a precise location relative to the others in hyperspace and since the links between them need not be mere edges but triangles, each blog post can be considered to be written on one of the faces of this nine dimensional simplex, either tapering towards the bottom or getting longer and longer lines as it goes on. You can hold this cluster of blog posts in your nine-dimensional hand-things and turn it this way and that to read each one of the ninety posts, all of which are on the surface of the polytope. If you happen to be a nine-dimensional entity, that is. Some of these are probably already written but I don’t know what they are.

This suggests a way of viewing blog posts via a virtual tesseract, merely four-dimensional and with each face of each of the eight cubes having a post written on both sides, four dozen in all, manipulable via one’s viewing device while wearing 3-D glasses or a VR headset. But all of this is fanciful and it isn’t clear how it would help one blog.

Leaving all that aside, it’s also possible to use the same old AI as I’ve been using for a lot of other things to finish my list of tags with others. It’s quite interesting what happens when I do this, because it fills my list in with the subjects I deliberately avoid on this blog, such as gender identity and trans stuff. InferKit just now gave me this:

Harry Potter
Animals
Politics
Military
Religion
Science
Food
Smart People
Animals and Animals
Writings
David Icke
Family Values
Hot Car Deaths
Holocaust
Asian-American

“Animals and Animals” is a little like “Vulcan And Vulcan” even though it hasn’t seen it. I don’t really want to blog about Harry Potter, although “Hot Car Deaths” is a depressing but possible subject. “Asian-American” strikes me as something you really should be in order to write about it, except that it is interesting how America sometimes seems like the extreme Far East even beyond Asia, so that has possibilities. DeepAI gives me “Science, Education, Welfare, Vacation, Innocent and Damn Law,”, then it seems to turn into a government form of some kind with things like “Pregnancy”, “Birth Year” and the like. This is not very useful and probably reveals the kind of text it thinks I’m writing.

I’ve done all this before, of course.

This blog is naturally a meandering mess of brain dumps, and consequently these two methods vaguely reveal some topics I might want to write about but they’re unlikely to get much readership, and that’s fine. However, I would say this. I suspect that if you’re serious about blogging and already have a blog which has a direction, a focus and a significant readership, you could do worse than to use these techniques. Maybe you’ve written about every combination of tag pairs. Finding out which ones you have and haven’t and colouring in the edges on the resultant complete graph would probably reveal where the large gaps are in your coverage, although some might be nonsensical. I don’t think any of mine would be though, so I suspect yours wouldn’t be either. Just two tags is rather limited, and if you open it up to all combinations, unless you’ve automated the process in some way you just will not have written hundreds of thousands of blog posts, meaning that some of the combinations will be stimulating and novel. As far as predicting tags is concerned, I found it tended to fill in things that I was genuinely interested in but hadn’t blogged about. This would also seem useful. You could also take all the AI-completed tags and build your own complete graph from those. It seems to me that there are likely to be other applications of graph theory to blogging which I have yet to become aware of. Worth investigating maybe?