How Frightened Ghosts Decide Where to Go

How do the frightened ghosts in Pac-Man decide where to move? It's all explained right here.
LINKS

[stanleydodds]

Markov chains are great. I was going to point out that this is a perfect example of a discrete time markov chain problem, but then it showed up in the video. Since you already covered that, I guess I'll add that a different way to solve this is to view it as an eigenvector - eigenvalue decomposition of the transition matrix, which is usually the way that I think about discrete markov chains.

The benefit that comes with looking at the various eigenspaces instead of just simulating it, is that the additional information of having all of the eigenvectors and values is able to encapsulate all of the slightly tricky situations that you can encounter.

For example, you mention that you needed to start it on 2 adjacent squares, and this is because of the checkerboard nature of adjacent cells on a square grid. There is a parity, and ghosts can only move from one parity to the other at each time step. So if you only started on one square, at every time step only half of the squares would have any non-zero probability on them. By getting the jordan normal form, you can easily see what would happen in the limit for starting on 2 adjacent squares, starting on just 1 square, or anything else.

[einootspork]

I like how you admit at the end that none of this really matters in actual gameplay, it's just fun to think about.

[ItsMisterMarbles]

The issues with the clockwise-turn behavior making bad distributions is very similar to an issue with mazes in Roller Coaster Tycoon. Marcel Vos did a video about it on his channel about how you could abuse this to make a short maze that is practically impossible for guests to get through.

[fluffberrieh]

Thinking quickly, Dave crafted a random number generator out of an index, a KiB of data, and a random number generator

[EebstertheGreat]

This description of Markov chains is actually quite intuitive, and I think that's a very important lesson. Markov chains come up all the time when analyzing video games, and also just in general, so they are a good tool to have.

[WishMakers]

The idea of grabbing a *byte from the game's code* as an RNG output has got to be one of the funniest things I've heard of all day

[kaidurbin]

For anybody wondering why they didn't just use the bottom two bits of the index, I just wrote a program to test the results of what would happen if you just used the bottom two bits for the direction, and the results showed that it would output RIGHT, DOWN, LEFT, UP in sequence over and over again, which is *definitely* not ideal. And if you were to try to get tricky and use a different pair of adjacent bits in the number, while the end result would be better, it still wouldn't be ideal as the values would tend to clump together. (eg. six RIGHTS appearing in a row followed by a long stretch without any RIGHTS.)

[ozziegerff]

Imagine making a good rng function and being like this needs to then read off memory values, ruining its perfect odds. Now the ghosts have a crying corner for when they get scared.

[kevinr.]

Fun fact: RollerCoaster Tycoon 2 (and probably the first game, but I can't say for sure) has the same clockwise bias issue with the "pathfinding" algorithm for the hedge maze attraction. This means that it is possible to create a maze that takes significantly longer on average for guests to complete if the entrance is on one side than if the entrance is on the other. I'm pretty sure the RNG function itself is reasonably non-biased, though. (Or at least less biased than Pac-Man's.)
When Marcel Vos made a video pointing this out, OpenRCT2 _immediately_ changed the pathfinding algorithm to be less biased.

[minerharry]

I shudder at how much work laying out those Markov chain arrows must have been…

[ryanlutes]

I recently coded a turn-based Pac-Man clone in C# as part of a larger project, and one of the major sources I used for information on the ghost behaviors was a RGME video, so, just wanted to say thank you for all the wonderful documentation you do. It's not just informative, but entertaining too. 👍

[MarioDSLife]

I was supposed to do a course involving Markov Chains but given how boring lectures are, I barely learnt anything. However when the same concept (which I’m new to) is applied into one of my favorite video games, I understand it well. I wish more lecturers would provide applications to the theories we learn, I think we’d all learn better that way. Thank you for the video.

[jonatanmonsalve]

The incredibly INSANE amount of work put into calculating, illustrating, and *especially* animating information that would be of virtually no use to us whatsoever other than maybe to appreciate how programmers of the past used to solve problems... is just beautiful. This is art.
When I saw the title and the duration of the video I was like "How can you spend 30 minutes explaining something like this!?", but after watching it, I feel way more satisfied with the whole markov and path deduction explanation than I would have been if you have stopped after the RNG and path choosing percentage explanation. Great video.

[SuperSpybob]

"How Frightened Ghosts Decide Where to Go"

29 minutes long.

I love this channel.

[cxreykx]

The fact that randomness is arguably impossible makes sense, you could argue a coin flip isn't random, it's based on height of the flip, speed, how fast it's spinning, which I guess - in theory - one could be precise about

[mrshurukan]

This markov chain you tought me in this video came in clutch for my programming olympiad. Thank you so much!!!

I had a task where I had to simulate a castle guard moving from starting position in the middle of the castle to one of two gates (picked by chance), but along the way to the chosen gate he might decide he forgot something and come back (also decided by given chance). Once he's back he can pick either gate again.

However if he reaches one of the two gates he doesn't come back as he's out of the castle. The task is to compute probabilities of him reaching gate 1 and gate 2

I immediately though of this video!! I progeammed the solution in about 10 minutes and was the first to score 100 in that particular task. You are the GOAT, man

[MidnyteSketch]

A nice coincidence that most of the pie charts for the 3-way intersections end up with you drawing Pac Man eating the lesser option.

[theecube]

i love that, in addition to being an excellent video on probability states (and more!), it's also an object less in game design (specicially, in how to actually finish a game and not get stuck in the weeds)

"yes, it's not mathematically perfect, but given how it will *actually* be used it'll be good enough"

[SSJTim]

Wasn't expecting the seamless transition into a 3Blue1Brown style explanation of Markov Chains, but I love it

[eizneckam]

"This will give us a heat map of where frightened ghosts like to hang out in the maze" is my favorite no-context sentence from these videos now. Amazing video as always!
Edit: I'm guessing the 50 ghosts each is because the RNG is called to determine which tile the ghosts come out of the house on initially?