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.
Bingo! I had originally planned to show off this checkerboarding pattern, but for the sake of visuals I split it up the way I did. This means technically that the chain in the video is actually *not* ergodic but rather 2-periodic. Splitting it up 50/50 does make it settle on a single steady state though (and looks better on video)!
@@Chubby_Bub Go to the numeric simulation and pause. There are a bunch of numbers on screen that represent the probability a ghost is at that position. Shove em all in a vector. In this case it's like a 500-dimensional vector but you can visualize it in 3D as long as you don't try to do something insane like take a cross product. So you've got a vector for the state. Better yet, you've got a space that represents every possible probability-state. (Exercise: What is the natural basis for this space? Is it orthonormal? What do those basis vectors represent?) Now, you'll have to hold both the visualization and the simulated interpretation in mind at the same time for this next bit. Take a single simulation step. _Click…_ The vector changes. _Click… Click… Click…_ Every step makes the vector jump a little bit. (Exercise: What property does every state vector have?) In fact the step function is a linear transformation. You can write it as a square matrix. If the simulation converges, that means that repeatedly applying the linear transformation to the initial vector converges to some other vector. And if you find a vector which is invariant under the transformation, you've found a steady state of probabilities. That's the definition of an eigenvector. By representing the state transition as a matrix you can just do linear algebra to figure out its steady state, if it has one. But wait - there's more. Ghost walks in the maze have period 2: If a ghost starts on a tile and continues walking, at every point in time only half of the board is accessible. The probability of half of the tiles is zero. Those two smart people above are saying you can see this from the Jordan canonical form but I can't picture that because I took my linear algebra class like 150 years ago. Anyway, linear algebra is easy. All you have to do is imagine 500 dimensions and you're good to go.
when i saw that the output of the rng was literally determined by the first bit of the game rom it put a huge smile on my face, its so crazy what early programmers managed to accomplish with so little room to spare
@@lavenderinthedark But they just made it worse by turning a perfectly evenly distributed RNG into a heavily biased RNG. EDIT: Actually the original RNG was bad too so indexing into the rom might be better...
@@Vextrove Because it's sequential. It grows until it hits 8192, then drops and grows again. Indexing into ROM is an attempt to make it non-sequential. And is... mostly-successful.
It's useful if you are trying to get the high score. Knowing which way ghosts are most likely to go at intersections while frightened makes it easier to eat them. Up to 12,000 bonus points can be gained per level from eating frightened ghosts. To put this in perspective, only 2600 points can be gained from eating all of the pellets in a level.
@@jimmyhirr5773 if you're going for maximum score, only 17 out of the 256 levels actually let you eat the ghosts. It's still a little useful to know they're more likely to turn left, but it only matters right at the beginning.
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.
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.
Actually, this is much more common than you might think. Consider as well that adding a table of sufficient size for this would add a significant total to the game's final size, further increasing it's production cost.
Uniformity is not the only desirable feature of a rng. n -> n + 1 achieves this but isn’t very random. n - 5n + 1 isn’t much better; since we only use the last 2 bits all the modulo junk disappears, and the rng literally becomes 01 -> 10 -> 11 -> 00 -> 01, which, while uniform, is very predictable. Even more since we have 4 ghosts, each pulling exactly one random number per turn.
@@klafbang Predictability doesnt matter because the position of the ghosts when they get scared isn't going to be consistent in the first place. Regardless, pulling a byte from the game's memory doesn't really solve this issue in the slightest, it doesn't make the function more random it just adds an extra step.
@@nstbayless It could actually work a whole lot better if they happened to have any compressed data in ROM, since it's highly entropic one could expect the distribution to be a bit more balanced ; I now wonder if Pokémon used the sprite data for the RNG
@@cheaterman49 og pokemon was written by people with a passing understanding of the concept of programming, the way they stored and retrieved some information is responsible for the famous missingno glitch. I forget the specifics but it's wild, so many things in those games just don't work as intended because of the way they're programmed
@@thesquirrelisking I tend to cut them some slack, they were working on a system where doing things properly would have been too slow, they were literally chasing cycles haha
@@thesquirrelisking hey, no offense, but if you think those Gameboy games were coded by people who had very little understanding of programming, I don't think you could hello world yourself out of BASIC. Anyone who's coded in html even once could tell you the amount of work that goes into a fullscale game like that, especially on proprietary hardware.
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.
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.
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.)
you can see this just from the function used, a_(n+1) = 5 a_n + 1. Looking at the bottom 2 bits here is equivalent to looking at each term mod 4. a_(n+1) mod 4 ~= (5 a_n + 1) mod 4 ~= (a_n + 1 + 4 a_n) mod 4 ~= (a_n + 1) mod 4. I'm using ~= to indicate congruence here, can't remember if I'm supposed to use the 3 line equals or not. This result indicates that when looking at the bottom 2 bits, the recurrence actually just always adds 1, never anything more interesting.
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. 👍
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.
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.
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
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
since in many systems small changes explode exponentially, and (as far as we know) quantum mechanics isnt deterministic, this actually isn't true! for a coin flip quantum uncertainty probably isnt relevant, but for say, what the weather will be like in exactly one year? *literally* random
@@terdragontra8900 As far as I understand it, everything is deterministic, it's just often so astronomically complex there is no way a human could ever grasp it. i.e. randomness does not actually exist, it's just our way of describing events where the cause-and-effect chain is unclear to us. Quantum mechanics includes uncertainties for states but this is just a mathematical structure to describe the behaviour of systems, since there is no way to directly observe interactions. The actual interactions play out in a deterministic fashion.
@@bluegum6438 Read up on "hidden variables" and have your mind blown. We've proven experimentally that entangled particles *do not* decide how they will be measured in the future when they are created.
For a more concrete example of true randomness in nature, IIRC it's been observed that it's completely random how far an electron will be from the nucleus of its atom when measured (though the distribution isn't uniform, they tend to hover around predictable distances, but they're still not guaranteed whether or not they'll appear at that distance at all). Another example is how it's random when a radioactive particle will decay, which means that theoretically a lump of radioactive material could at any point just decide not to be radioactive for a full minute or so.
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"
"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?
I don't know if you used Markov chains to teach me about Pac-Man, or if you used my love of retro game mechanics to teach me about Markov chains. Either way, it was a fascinating endeavor. Thank you for sharing it.
This was a really cool video. I have an rgb keyboard with a programmable microprocessor on it and one of the things I've been interested in doing for a while was building a rgb function that uses a markov chain to render a heatmap with the rgbs that predicts the most likely key to be pressed next given any keypress. Seeing you do something very similar here gave me a pretty solid understanding of how that would work! (Also, helped me realize that such a chain needs to include not just single keypresses but combination states where multiple keys are pressed - which makes me think such a chain might exceed the RAM capacity of my poor keyboard!)
I wonder what the resulting odds would be if: 1) the random function index is used directly instead (don't index the rom) 2) If an invalid option is chosen, the ghost tries the counterclockwise direction (instead of the clockwise)
@@klafbang Are you sure? I'm not referring to just 1,2,3,4,5... but the 1,6,31... (the index as explained in 3:26). The current rng is also period 4. I guess it would be more similar (if not the same) as the 25% test
@@TrianguloY the current rng is period 8192; the modulo matters when looking up in the rom. It might be 00 -> 01 -> 00 -> 11 (or whatever). The index you’re using as input is not directly linked to what you output, sou can have a longer period.
It works out like that because of modular artithmetics. Basically, you can move the mods around wherever. ((5n + 1) mod 8192) mod 4) = (5n + 1) mod 4 (as 4 divides 8192) = (5(n mod 4) + 1) mod 4, so the computation without going via rom becomes a simple operation on only the two bits of output, giving it at most 4 possible values.
Oh! I see it now. Since 8192 is divisible by 4 the output is 5n+1 (mod 4) and with modulo operations you can simplify it to (5 mod 4)n + (1 mod 4) which is n+1! So the sequence is 0,1,2,3,0,1,2,3... *alternatively 4n + n + 1 (mod 4) so 0+n+1
YES A NEW VIDEO ABOUT HOW GAMES WORK I'm a student game developper and I just adore watching those video breaking down how the gameplay actually work It would be really cool if you could show us how ai and action and stuff work in some other games, like how do they spawn so much ship in galaga or looking at centiped
Pac-Man is quite representative of how "AI" usually works in games: either a deterministic set of instructions, or pseudo-randomness, or some combination of the two.
I imagine how it works (at least for Galaga) is that while the ships are flying in a line, they're treated as one entity for movement purposes, kind of like the swarms of bats in Breath of the Wild. At least, that's what I'd do. Couldn't tell you for a fact.
indexing into the rom is so whimsical! I'm not sure if it made the generator better or worse, and ultimately it doesn't matter, but they must've been so happy to be able to write that one instruction. It just feels so cute 😄
It made it better. If they just used the index, the ghost movement would have period 4, and the ghosts would just move around in a really obvious pattern. But since they used the entire index (as opposed to a couple bits of it), the ghost movement has period 8192, which is a lot less obvious.
The exact same behavior occurs when eating a power pellet, just the length of time they are frightened gets shorter and shorter until they flash, turn around and instantly are not frightened.
In Ms. Pac-Man, the duration gets shorter and shorter by level until it's only a frame or something, but then it gets longer again and then it gets shorter faster. At least, with the factory settings of the tables I've played.
It's worth noting that even though accessing the game's data seems like a worse idea than just using the uniform index, IF the index was used as the random number and the direction was picked from the lower 2 bits, then the rng order would always follow the sequence (right, down, left, up), because after multiplying by 5 and adding 1, any value ending in 00 would end up with 01, 01 with 10, 10 with 11, and 11 with 00. and 8192 is divisible by 4 so the rule wouldn't break when overflowing.
You're really brilliant to be able to understand and explain all of this. I wonder what the creators of Pac-Man in 1980 would think regarding this video made around 43 years later about the RNG of the frightened ghosts from their game...
_Wow, this video is super-professionally handcrafted and obsessively detailed. Every time I think it's reached the peak of scrutiny, it goes one step further. But I think I've reached the end._ 27:56 *"In reality, the main factor that determines where a frightened ghost is in the maze is when Pac-Man eats the power pellet."* _Oh no._
As someone who only knew the part about them tending towards the bottom left, by making a cheat code to permanently make them frightened and then just noticing where they went, I thank you for going so much further. I never even tried to find out "why", but I have the answer now thanks to you.
Ugh... it's been 15 years since my random processes class in grad school and I never thought I'd have to suffer through a Markov chain again, especially in a retro game video!
Fantastic video. Your brilliant explanation along with the clean graphical style makes it really easy to follow. I didn’t notice nearly 30 minutes had passed! Keep it up ❤
16:51 when you mentioned ergodic chains being the main exception, I immediately thought of the other kind of exception, which would result in it alternating between two steady states every turn, like crypt of the necrodancer if you couldn't stay still or attack. and then later on in the video you have to start it on two tiles to avoid this! feels neat to figure it out before the vid mentioned it.
You said to guess why you placed the ghosts at the door. I can assume it's 1. because that's just where ghosts start at the beginning of the game / that's where an eaten ghost ends up at, which then it is no longer frightened, or 2. that it's the center of the map and is the best possible starting location to attempt to even out probabilities.
You can switch from ghost random direction to ghost random direction priority lists. Instead of choosing between u, l, d, r, you can choose between any random vector [u, l, d, r], and prioritize the vector values from left to right. This will remove bias, and reduce loops.
To put it simply, a Markov chain is a graph of states where the probability of the next state depends only on the current state. This is why RGME had to add one node for each possible entrance into a tile: the entry direction is part of the state.
Thank you for explaining this! It might not be incredibly useful to play Pac-Man with this knowledge, explaining Markov chains and the probability calculation in a familiar context with an application made it really helpful.
A Markov chain is the perfect tool to model this, but the size of it was psychotic lol. I really thought you were going to turn it into a transition matrix and multiply it with the starting matrix to get the next state, over and over rather than simulating stepwise. I don't want to count the number of nodes, but I really wonder if your computer would have enjoyed that giant matrix multiplication
Very cool that the RNG was used to index the rom. Ever since I read that in Donkey Kong in the early levels the chance whether a barrel should go down a ladder vs pass it is dependent on the direction of Jumpman/Mario, I have always thought it would be very cool for the user to affect the RNG by their actions. No doubt there should be a game in such a mechanic where a player can feel like they become "Neo controlling the Matrix" by actually affecting the RNG to control critters in a game by plain actions, would be so cool.
The reason to 50 units of ghosts on 2 adjacent tiles is a parity thing: we can split up all tiles into two groups, just like the black and white squares on a chess board. So if a tile is white, all its neighbors are black and vice versa. If we started with all weight on a single tile, then in each step of the chain, there would be either all weight on black tiles or all weight on white tiles. So we choose two adjacent tiles (one black tile and one white tile), so that the resulting heat map will have non-zero weights on all tiles.
To what extent could this be balanced by changing those "unused" 00s in the ROM into other numbers? I'm guessing not much, as these 00s are already part of the 3rd most popular direction (right)
I like how this is more educational about graph theory (and maybe assembly coding) than really helpful to play Pac-Man better, yet the framing of being about learning some Pac-Man trivia makes my flawed brain find this content way more interesting to watch than a video that was only about graph theory. It's not even the sort of Pac-Man trivia that one could use as "fun trivia", even in conversation with other nerds, but somehow that doesn't matter; it's still a great video! Watching the animation of the graph while listening to you complain about how stupidly big the Markov chain is, making it hard work to calculate I can't help but think "It must have been MANY times more work to draw and animate all those vertices compared to "just" doing the data entry and calculating the chain's steady state! You went above and beyond to actually show *all* those vertices on screen, *and* to not have the arrows between the nodes simply be straight lines, but to instead hve them curve around other nodes. I'm typing this to say that this effort was noticed and very much appreciated! That alone is well worth hitting the subscription button out of pure respect!
I would've loved to see the state of the markov chain after a set number of steps, after setting the ghost position to be random, and the number of steps determined by how long the ghosts stay scared. That way, you could see the actual predicted position of a ghost depending on where it started. On top of this, there is almost certainly a bias on each ghost, according to it's code, (see: last video on Pac-Man) that may bias *where* it ends up as the pellet is eaten... I bet each kind of ghost has it's own unique position distribution simply because of that!
I wrote a Pac-Many style game in Basic on my Atari computer when I was a kid. Basic was very slow, so I needed very simple ghost logic. I decided to pick a direction at random when the ghost reached an intersection. Then, if that direction was away from the player, it would pick a 2nd random direction. That logic actually worked very well. The ghosts would generally move toward the player but with a sufficient amount of random moves that were also away from the player.
This comment might be a bit repetitive and sappy, but I do really like how these videos are designed to be appealing to people both with and without deeper knowledge of the subject. I've been a fan of this channel since the SMB3 1UP video but now that I'm learning computer science and can understand this stuff more, I have a newfound appreciation.
reminds me of the old maze pathfinding mechanics in roller coaster tycoon, you could build a maze that's just a straight line forward but every tile of the maze has a dead end to one side. because of the guests' bias in choosing that direction they almost always got stuck, even though the exit is in plain view. this has been fixed in later versions of openrct2 though
The reason you placed 50 ghosts on the squares near the ghost house is due to the probability they will be coming out of the house frightened. Also you would technically need a markov chain to find out which location they are most likely to be in prior to being frightened. You would then need to determine the probability of which direction they would be going at said vertices. All to determine where you should place ghosts and what their initial trajectory is. Or you can choose the only spots to which there are two trajectories and a high probability they will originate from there. I would also guess the function to leave the house does not have any RNG, there by filtering out any “RNG affecting RNG results. Pardon any spelling errors as I’m typing this on a mobile device.
very well done. there are some edge cases. 1) the 3 reversals. if you eat an energizer just before a reversal, the ghost will turn in the opposite direction briefly, so that changes their behavior 2) grouping, when the ghosts are grouped together, they all act as one i think. however, most of the time, they are either coming up on an energizer when you eat them, or are very close depending on how many you have, usually 3, and sometimes all 4 together 3) eating multiple energizers causing them to reverse multiple times. other than that, great job. later || ||| | | || | ne gative1
I wish you would explain more about the assembly code and programming, explaining what some of the things mean and what they do. I know it's not super practical, but a lot of people don't know how ASM works and it can be very confusing. I was able to understand the main point in this video thanks to the helpful illustrations, but there was a lot of terminology and concepts I didn't get. Seems like I'm the only one who doesn't have the ability to flawlessly understand everything however, since I don't see any other comments talking about this.
Even if the information has no practical application, it's fun seeing how the game works under the hood. And hey, you taught me what a Markov chain is, which is pretty neat.
This is just an interesting fact: 1:12 technically dice and coins aren't random either. It just isn't predictable cause you'd need to know the state of the die or coin at all times. If this was humanly possible it would be considered deterministic. The very best source of randomness is atmospheric noise such as lightning discharges, and coronal mass ejections (from the sun). If one could reverse the mechanics of the sun and find how the coronal mass ejection happened it could be considered deterministic as well, but obviously we cannot.
I love your videos. I've watched all of them, they all are excellent both in content and presentation. They helped me get a basis for many topics in game programming. I only have one question, what are the softwares and/or tools do you use to make the animations on your videos?
I love this stuff. Crawling through disassembly of my favorite old games is one of my favorite things to do. I can give you a _very_ thorough rundown of several SNES RNGs :)
This really shows what difference the tools we have today can make compared to the tools we used to have. It'd be next to trivial to just have a computer sample the bits distribution (or emulate the results) with some time on the side, but back then they did not have the processing power or anything else to make sure their numbers worked. Not... that it hurts the game too bad, I guess?
They probably just played it and thought "This is good enough" and kept it the way it was. They weren't trying to make it cryptographically secure after all.
@Neb6 Seems like it would take a ton of ROM space to store those sine tables. Let's face it, this is the Z80, you're not going to actually calculate sine waves in real time.
22:50 My answer: This is the starting position of the ghosts who can only move either to the left or the right at this point and the propabilities being split there accordingly. This is a special case because none of the ghosts are on a tile so they need a special turn handler with a bias which happens to be 50-50 here. That you later have shown the ghosts coming from their home further supported my answer.
I wonder what other tweaks to the direction function could do. Like, if you pick an impossible direction, try picking the opposite one first instead of clockwise, and only if that doesn't work either, turn clockwise.
It's incredible considering the limited amount of code space Toru Iwatani had to work with in the first place, and yet came up with such a fantastic game with such intelligent programming for even such a simple thing as a frightened ghost. Imagine how optimised current modern computer games would be if such intelligence was used program them. 😀 Thank you for this very detailed explanation.
The hardest part of calculating that Markov chain is that if you lay all the vertices on the board like that, Pac-Man will start eating them before you're done figuring it out
*[**22:54**]:* The assumption of a 50/50 split assumes the lack of bias in direction-picking in 'symmetric' cases, which we know is false by this point.
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.
Bingo! I had originally planned to show off this checkerboarding pattern, but for the sake of visuals I split it up the way I did. This means technically that the chain in the video is actually *not* ergodic but rather 2-periodic. Splitting it up 50/50 does make it settle on a single steady state though (and looks better on video)!
I like your funny words, magic men 😅
what words did i just read
Having learned just enough linear algebra to only half-understand this gives probably a worse feeling than not understanding it at all
@@Chubby_Bub
Go to the numeric simulation and pause. There are a bunch of numbers on screen that represent the probability a ghost is at that position. Shove em all in a vector.
In this case it's like a 500-dimensional vector but you can visualize it in 3D as long as you don't try to do something insane like take a cross product.
So you've got a vector for the state. Better yet, you've got a space that represents every possible probability-state. (Exercise: What is the natural basis for this space? Is it orthonormal? What do those basis vectors represent?)
Now, you'll have to hold both the visualization and the simulated interpretation in mind at the same time for this next bit. Take a single simulation step. _Click…_ The vector changes. _Click… Click… Click…_ Every step makes the vector jump a little bit. (Exercise: What property does every state vector have?)
In fact the step function is a linear transformation. You can write it as a square matrix. If the simulation converges, that means that repeatedly applying the linear transformation to the initial vector converges to some other vector. And if you find a vector which is invariant under the transformation, you've found a steady state of probabilities.
That's the definition of an eigenvector. By representing the state transition as a matrix you can just do linear algebra to figure out its steady state, if it has one.
But wait - there's more. Ghost walks in the maze have period 2: If a ghost starts on a tile and continues walking, at every point in time only half of the board is accessible. The probability of half of the tiles is zero. Those two smart people above are saying you can see this from the Jordan canonical form but I can't picture that because I took my linear algebra class like 150 years ago.
Anyway, linear algebra is easy. All you have to do is imagine 500 dimensions and you're good to go.
Thinking quickly, Dave crafted a random number generator out of an index, a KiB of data, and a random number generator
when i saw that the output of the rng was literally determined by the first bit of the game rom it put a huge smile on my face, its so crazy what early programmers managed to accomplish with so little room to spare
@@lavenderinthedark But they just made it worse by turning a perfectly evenly distributed RNG into a heavily biased RNG.
EDIT: Actually the original RNG was bad too so indexing into the rom might be better...
@@torgematthies2172 why was it bad? Too predictable?
Excellent Dave the Barbarian reference, btw.
@@Vextrove Because it's sequential. It grows until it hits 8192, then drops and grows again.
Indexing into ROM is an attempt to make it non-sequential. And is... mostly-successful.
I like how you admit at the end that none of this really matters in actual gameplay, it's just fun to think about.
Sounds just like all my rng research for speedrunners! 😂 It's really interesting though!! Haha
It's useful if you are trying to get the high score. Knowing which way ghosts are most likely to go at intersections while frightened makes it easier to eat them. Up to 12,000 bonus points can be gained per level from eating frightened ghosts. To put this in perspective, only 2600 points can be gained from eating all of the pellets in a level.
@@jimmyhirr5773 if you're going for maximum score, only 17 out of the 256 levels actually let you eat the ghosts. It's still a little useful to know they're more likely to turn left, but it only matters right at the beginning.
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.
Easily his best video imo.
Maybe Pac-Man ghosts are the reanimated souls of the RCT guests that "mysteriously" drowned in the park's pond.
@@RGMechEx BWAHAHAHAHA!! *beautiful*
Marcel Vos is one of my favorite channels
You beat me to it.
Oh, well. Having another comment that says roughly the same thing (albeit wordierly) on the same video won't hurt anyone.
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.
Actually, this is much more common than you might think. Consider as well that adding a table of sufficient size for this would add a significant total to the game's final size, further increasing it's production cost.
Uniformity is not the only desirable feature of a rng. n -> n + 1 achieves this but isn’t very random. n - 5n + 1 isn’t much better; since we only use the last 2 bits all the modulo junk disappears, and the rng literally becomes 01 -> 10 -> 11 -> 00 -> 01, which, while uniform, is very predictable. Even more since we have 4 ghosts, each pulling exactly one random number per turn.
tbh it is a hilarious idea
That's where Clyde likes to hang out anyway.
@@klafbang Predictability doesnt matter because the position of the ghosts when they get scared isn't going to be consistent in the first place. Regardless, pulling a byte from the game's memory doesn't really solve this issue in the slightest, it doesn't make the function more random it just adds an extra step.
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
The Atari 2600 game "Yar's Revenge" did the same thing. It's a fun trick. I'm sure yet others did this, too.
@@nstbayless It could actually work a whole lot better if they happened to have any compressed data in ROM, since it's highly entropic one could expect the distribution to be a bit more balanced ; I now wonder if Pokémon used the sprite data for the RNG
@@cheaterman49 og pokemon was written by people with a passing understanding of the concept of programming, the way they stored and retrieved some information is responsible for the famous missingno glitch. I forget the specifics but it's wild, so many things in those games just don't work as intended because of the way they're programmed
@@thesquirrelisking I tend to cut them some slack, they were working on a system where doing things properly would have been too slow, they were literally chasing cycles haha
@@thesquirrelisking hey, no offense, but if you think those Gameboy games were coded by people who had very little understanding of programming, I don't think you could hello world yourself out of BASIC. Anyone who's coded in html even once could tell you the amount of work that goes into a fullscale game like that, especially on proprietary hardware.
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.
I shudder at how much work laying out those Markov chain arrows must have been…
As someone who occasionally designs PCBs, I felt that. :-)
i can only imagine they wrote an algorithm to calculate all of the vectors for them. right? right??
@@durdleduc8520 I wouldn't be so sure. RGME has calculated Pokemon sprite decompression and drawn it out by hand before.
Wasn't expecting the seamless transition into a 3Blue1Brown style explanation of Markov Chains, but I love it
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.
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.)
you can see this just from the function used, a_(n+1) = 5 a_n + 1. Looking at the bottom 2 bits here is equivalent to looking at each term mod 4.
a_(n+1) mod 4 ~= (5 a_n + 1) mod 4 ~= (a_n + 1 + 4 a_n) mod 4 ~= (a_n + 1) mod 4. I'm using ~= to indicate congruence here, can't remember if I'm supposed to use the 3 line equals or not. This result indicates that when looking at the bottom 2 bits, the recurrence actually just always adds 1, never anything more interesting.
Now I actually kind of want to see how using this kind of RNG would impact the ghosts' movement.
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. 👍
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.
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.
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
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.
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
since in many systems small changes explode exponentially, and (as far as we know) quantum mechanics isnt deterministic, this actually isn't true! for a coin flip quantum uncertainty probably isnt relevant, but for say, what the weather will be like in exactly one year? *literally* random
@@terdragontra8900 Interesting! I want to learn more about that, outside of the video games it's definitely not a concept Im familiar with
@@terdragontra8900 As far as I understand it, everything is deterministic, it's just often so astronomically complex there is no way a human could ever grasp it. i.e. randomness does not actually exist, it's just our way of describing events where the cause-and-effect chain is unclear to us. Quantum mechanics includes uncertainties for states but this is just a mathematical structure to describe the behaviour of systems, since there is no way to directly observe interactions. The actual interactions play out in a deterministic fashion.
@@bluegum6438 Read up on "hidden variables" and have your mind blown. We've proven experimentally that entangled particles *do not* decide how they will be measured in the future when they are created.
For a more concrete example of true randomness in nature, IIRC it's been observed that it's completely random how far an electron will be from the nucleus of its atom when measured (though the distribution isn't uniform, they tend to hover around predictable distances, but they're still not guaranteed whether or not they'll appear at that distance at all).
Another example is how it's random when a radioactive particle will decay, which means that theoretically a lump of radioactive material could at any point just decide not to be radioactive for a full minute or so.
"How Frightened Ghosts Decide Where to Go"
29 minutes long.
I love this channel.
Me too
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"
"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?
I don't know if you used Markov chains to teach me about Pac-Man, or if you used my love of retro game mechanics to teach me about Markov chains. Either way, it was a fascinating endeavor. Thank you for sharing it.
This was a really cool video. I have an rgb keyboard with a programmable microprocessor on it and one of the things I've been interested in doing for a while was building a rgb function that uses a markov chain to render a heatmap with the rgbs that predicts the most likely key to be pressed next given any keypress. Seeing you do something very similar here gave me a pretty solid understanding of how that would work! (Also, helped me realize that such a chain needs to include not just single keypresses but combination states where multiple keys are pressed - which makes me think such a chain might exceed the RAM capacity of my poor keyboard!)
I wonder what the resulting odds would be if:
1) the random function index is used directly instead (don't index the rom)
2) If an invalid option is chosen, the ghost tries the counterclockwise direction (instead of the clockwise)
1 much, much worse. You’d have a function with period 4, from which you’d pick 4 random numbers per cycle. Each ghost would be 100% predictable.
@@klafbang Are you sure? I'm not referring to just 1,2,3,4,5... but the 1,6,31... (the index as explained in 3:26). The current rng is also period 4.
I guess it would be more similar (if not the same) as the 25% test
@@TrianguloY the current rng is period 8192; the modulo matters when looking up in the rom. It might be 00 -> 01 -> 00 -> 11 (or whatever). The index you’re using as input is not directly linked to what you output, sou can have a longer period.
It works out like that because of modular artithmetics. Basically, you can move the mods around wherever. ((5n + 1) mod 8192) mod 4) = (5n + 1) mod 4 (as 4 divides 8192) = (5(n mod 4) + 1) mod 4, so the computation without going via rom becomes a simple operation on only the two bits of output, giving it at most 4 possible values.
Oh! I see it now. Since 8192 is divisible by 4 the output is 5n+1 (mod 4) and with modulo operations you can simplify it to (5 mod 4)n + (1 mod 4) which is n+1! So the sequence is 0,1,2,3,0,1,2,3...
*alternatively 4n + n + 1 (mod 4) so 0+n+1
This was fascinating to watch. I knew it was complicated, but didn't expect how deep you'd go into it. Really great work!
I would have to agree!
This is a fantastic deep dive study into the behavior of Pac Man. Really well explained. Nice job!
YES A NEW VIDEO ABOUT HOW GAMES WORK
I'm a student game developper and I just adore watching those video breaking down how the gameplay actually work
It would be really cool if you could show us how ai and action and stuff work in some other games, like how do they spawn so much ship in galaga or looking at centiped
Pac-Man is quite representative of how "AI" usually works in games: either a deterministic set of instructions, or pseudo-randomness, or some combination of the two.
I imagine how it works (at least for Galaga) is that while the ships are flying in a line, they're treated as one entity for movement purposes, kind of like the swarms of bats in Breath of the Wild. At least, that's what I'd do. Couldn't tell you for a fact.
indexing into the rom is so whimsical! I'm not sure if it made the generator better or worse, and ultimately it doesn't matter, but they must've been so happy to be able to write that one instruction. It just feels so cute 😄
It made it better. If they just used the index, the ghost movement would have period 4, and the ghosts would just move around in a really obvious pattern. But since they used the entire index (as opposed to a couple bits of it), the ghost movement has period 8192, which is a lot less obvious.
I didn't even know ghosts didn't become frightened in more advanced levels. This game was very slightly before my time and I never got into it.
They spend several seconds frightened in the first level, and then the length of time gets shorter and shorter each level.
The exact same behavior occurs when eating a power pellet, just the length of time they are frightened gets shorter and shorter until they flash, turn around and instantly are not frightened.
In Ms. Pac-Man, the duration gets shorter and shorter by level until it's only a frame or something, but then it gets longer again and then it gets shorter faster. At least, with the factory settings of the tables I've played.
Yes! The long awaited sequel to the PacMan AI video. That's one of my favorite ones you've ever done
It's worth noting that even though accessing the game's data seems like a worse idea than just using the uniform index, IF the index was used as the random number and the direction was picked from the lower 2 bits, then the rng order would always follow the sequence (right, down, left, up), because after multiplying by 5 and adding 1, any value ending in 00 would end up with 01, 01 with 10, 10 with 11, and 11 with 00. and 8192 is divisible by 4 so the rule wouldn't break when overflowing.
You're really brilliant to be able to understand and explain all of this. I wonder what the creators of Pac-Man in 1980 would think regarding this video made around 43 years later about the RNG of the frightened ghosts from their game...
22:58 This is like some kind of *_"quantum map"_* about the probabilities of finding a ghost at any 1 tile :D
9:02 Thank you for answering this very important question I was wondering. It is unfortunate.
_Wow, this video is super-professionally handcrafted and obsessively detailed. Every time I think it's reached the peak of scrutiny, it goes one step further. But I think I've reached the end._
27:56 *"In reality, the main factor that determines where a frightened ghost is in the maze is when Pac-Man eats the power pellet."*
_Oh no._
I myself have found that most of the time when playing, the frightened monsters favor the side bridging corridors. I dunno.
As someone who only knew the part about them tending towards the bottom left, by making a cheat code to permanently make them frightened and then just noticing where they went, I thank you for going so much further. I never even tried to find out "why", but I have the answer now thanks to you.
Ugh... it's been 15 years since my random processes class in grad school and I never thought I'd have to suffer through a Markov chain again, especially in a retro game video!
Fantastic video. Your brilliant explanation along with the clean graphical style makes it really easy to follow. I didn’t notice nearly 30 minutes had passed! Keep it up ❤
16:51 when you mentioned ergodic chains being the main exception, I immediately thought of the other kind of exception, which would result in it alternating between two steady states every turn, like crypt of the necrodancer if you couldn't stay still or attack.
and then later on in the video you have to start it on two tiles to avoid this! feels neat to figure it out before the vid mentioned it.
You said to guess why you placed the ghosts at the door. I can assume it's 1. because that's just where ghosts start at the beginning of the game / that's where an eaten ghost ends up at, which then it is no longer frightened, or 2. that it's the center of the map and is the best possible starting location to attempt to even out probabilities.
You can switch from ghost random direction to ghost random direction priority lists. Instead of choosing between u, l, d, r, you can choose between any random vector [u, l, d, r], and prioritize the vector values from left to right. This will remove bias, and reduce loops.
To put it simply, a Markov chain is a graph of states where the probability of the next state depends only on the current state. This is why RGME had to add one node for each possible entrance into a tile: the entry direction is part of the state.
Just when I was beginning to wonder about rendering in NES Rad Racer, you post once more to satiate my retro programming wizardry wonder.
Very much appreciating the Pacman charts for the 3-way intersection probabilities
“This RNG function has uniform output.”
“Great! Let’s just truncate it to one byte and-”
“Make it not uniform.”
*[**23:30**]:* Really nice when the math is in-line with common sense! (:
Love me a video that's 30 minutes of "here is exactly why this happens, and also why it doesn't matter one bit." It's an absolute delight for me~
Thank you for explaining this! It might not be incredibly useful to play Pac-Man with this knowledge, explaining Markov chains and the probability calculation in a familiar context with an application made it really helpful.
A Markov chain is the perfect tool to model this, but the size of it was psychotic lol. I really thought you were going to turn it into a transition matrix and multiply it with the starting matrix to get the next state, over and over rather than simulating stepwise. I don't want to count the number of nodes, but I really wonder if your computer would have enjoyed that giant matrix multiplication
The original Pac-man video was actually how I found this channel.
Very cool that the RNG was used to index the rom. Ever since I read that in Donkey Kong in the early levels the chance whether a barrel should go down a ladder vs pass it is dependent on the direction of Jumpman/Mario, I have always thought it would be very cool for the user to affect the RNG by their actions. No doubt there should be a game in such a mechanic where a player can feel like they become "Neo controlling the Matrix" by actually affecting the RNG to control critters in a game by plain actions, would be so cool.
finally! a use for math
Didn't expect to see you here.
Incredibly well taught. Definitely learned a lot. I'm amazed tho' how you put more effort on one video than I did for my master's thesis.🥴
The reason to 50 units of ghosts on 2 adjacent tiles is a parity thing: we can split up all tiles into two groups, just like the black and white squares on a chess board. So if a tile is white, all its neighbors are black and vice versa. If we started with all weight on a single tile, then in each step of the chain, there would be either all weight on black tiles or all weight on white tiles. So we choose two adjacent tiles (one black tile and one white tile), so that the resulting heat map will have non-zero weights on all tiles.
To what extent could this be balanced by changing those "unused" 00s in the ROM into other numbers?
I'm guessing not much, as these 00s are already part of the 3rd most popular direction (right)
Balancing the Rom numbers would just push the probabilities of each direction closer to 25% so all in all, very little would change.
Power is unpredictable sometimes. Great video as always!
I like how this is more educational about graph theory (and maybe assembly coding) than really helpful to play Pac-Man better, yet the framing of being about learning some Pac-Man trivia makes my flawed brain find this content way more interesting to watch than a video that was only about graph theory. It's not even the sort of Pac-Man trivia that one could use as "fun trivia", even in conversation with other nerds, but somehow that doesn't matter; it's still a great video!
Watching the animation of the graph while listening to you complain about how stupidly big the Markov chain is, making it hard work to calculate I can't help but think "It must have been MANY times more work to draw and animate all those vertices compared to "just" doing the data entry and calculating the chain's steady state! You went above and beyond to actually show *all* those vertices on screen, *and* to not have the arrows between the nodes simply be straight lines, but to instead hve them curve around other nodes. I'm typing this to say that this effort was noticed and very much appreciated! That alone is well worth hitting the subscription button out of pure respect!
I would've loved to see the state of the markov chain after a set number of steps, after setting the ghost position to be random, and the number of steps determined by how long the ghosts stay scared. That way, you could see the actual predicted position of a ghost depending on where it started.
On top of this, there is almost certainly a bias on each ghost, according to it's code, (see: last video on Pac-Man) that may bias *where* it ends up as the pellet is eaten... I bet each kind of ghost has it's own unique position distribution simply because of that!
I wrote a Pac-Many style game in Basic on my Atari computer when I was a kid. Basic was very slow, so I needed very simple ghost logic. I decided to pick a direction at random when the ghost reached an intersection. Then, if that direction was away from the player, it would pick a 2nd random direction. That logic actually worked very well. The ghosts would generally move toward the player but with a sufficient amount of random moves that were also away from the player.
This comment might be a bit repetitive and sappy, but I do really like how these videos are designed to be appealing to people both with and without deeper knowledge of the subject. I've been a fan of this channel since the SMB3 1UP video but now that I'm learning computer science and can understand this stuff more, I have a newfound appreciation.
Can't wait to look up that ergodic fact :D
oh my god its like watching alternate realities play out at the same time this is wonderful
I watched your other Pac-Man video! I can't BELIEVE that you made ANOTHER!
reminds me of the old maze pathfinding mechanics in roller coaster tycoon, you could build a maze that's just a straight line forward but every tile of the maze has a dead end to one side. because of the guests' bias in choosing that direction they almost always got stuck, even though the exit is in plain view. this has been fixed in later versions of openrct2 though
ohhhh im a little ghost and im so scared of the yellow circle man ooooh
Man this must have taken a ton of quarters to figure out 😀
The reason you placed 50 ghosts on the squares near the ghost house is due to the probability they will be coming out of the house frightened. Also you would technically need a markov chain to find out which location they are most likely to be in prior to being frightened. You would then need to determine the probability of which direction they would be going at said vertices. All to determine where you should place ghosts and what their initial trajectory is. Or you can choose the only spots to which there are two trajectories and a high probability they will originate from there. I would also guess the function to leave the house does not have any RNG, there by filtering out any “RNG affecting RNG results. Pardon any spelling errors as I’m typing this on a mobile device.
I would have never thought a video about a retro game RNG could be so deep and interesting
FINALLY the third installment in the series. remember watching these 2 years ago lol
His voice is really calming.
That's why I love this channel.
Power pallets still turn ghosts around, even if they dont become frightened.
One could argue they are frightened for exactly zero frames.
this completes the pacman mechanic trilogy
very well done.
there are some edge cases.
1) the 3 reversals. if you eat an energizer just before a reversal, the ghost will turn
in the opposite direction briefly, so that changes their behavior
2) grouping, when the ghosts are grouped together, they all act as one i think.
however, most of the time, they are either coming up on an energizer when you
eat them, or are very close depending on how many you have, usually 3, and sometimes
all 4 together
3) eating multiple energizers causing them to reverse multiple times.
other than that, great job.
later
|| ||| | | || |
ne gative1
8:13 "genreator" nice.
I wish you would explain more about the assembly code and programming, explaining what some of the things mean and what they do. I know it's not super practical, but a lot of people don't know how ASM works and it can be very confusing. I was able to understand the main point in this video thanks to the helpful illustrations, but there was a lot of terminology and concepts I didn't get. Seems like I'm the only one who doesn't have the ability to flawlessly understand everything however, since I don't see any other comments talking about this.
I really love the probability simulation and the vs. actual measured simulation.
Even if the information has no practical application, it's fun seeing how the game works under the hood. And hey, you taught me what a Markov chain is, which is pretty neat.
This is just an interesting fact:
1:12 technically dice and coins aren't random either. It just isn't predictable cause you'd need to know the state of the die or coin at all times. If this was humanly possible it would be considered deterministic. The very best source of randomness is atmospheric noise such as lightning discharges, and coronal mass ejections (from the sun).
If one could reverse the mechanics of the sun and find how the coronal mass ejection happened it could be considered deterministic as well, but obviously we cannot.
So for all practical purposes, dice and coins might as well be perfectly random.
Except the fact that atmospheric noise is random makes dice random as the forces from the atmospheric noise affect how the dice moves.
I love your videos. I've watched all of them, they all are excellent both in content and presentation. They helped me get a basis for many topics in game programming. I only have one question, what are the softwares and/or tools do you use to make the animations on your videos?
It's all mostly After Effects!
I'm guessing the 50/50 thing is just to split it more evenly based on the ghosts starting inbetween 2 tiles
I didn't expect to find a spoiler from a 43 year old game. I never made it far enough in the game to have the ghosts stop being frightened.
Back in the 80s I was at a motel that had some arcade games in a basement and a guy was playing pac-man and the bottom was filled up with keys.
I love this stuff. Crawling through disassembly of my favorite old games is one of my favorite things to do. I can give you a _very_ thorough rundown of several SNES RNGs :)
I like the idea that, despite being code controlled by a RNG, the ghosts still have unequal biases when making chooses just like actual people.
wooo a new RGME video!! These videos are what really got me into looking at how low level systems work
This really shows what difference the tools we have today can make compared to the tools we used to have. It'd be next to trivial to just have a computer sample the bits distribution (or emulate the results) with some time on the side, but back then they did not have the processing power or anything else to make sure their numbers worked. Not... that it hurts the game too bad, I guess?
They probably just played it and thought "This is good enough" and kept it the way it was. They weren't trying to make it cryptographically secure after all.
@Neb6 Seems like it would take a ton of ROM space to store those sine tables. Let's face it, this is the Z80, you're not going to actually calculate sine waves in real time.
Damn stellar job animating those graphs dude!
22:50 My answer: This is the starting position of the ghosts who can only move either to the left or the right at this point and the propabilities being split there accordingly. This is a special case because none of the ghosts are on a tile so they need a special turn handler with a bias which happens to be 50-50 here.
That you later have shown the ghosts coming from their home further supported my answer.
I wonder what other tweaks to the direction function could do. Like, if you pick an impossible direction, try picking the opposite one first instead of clockwise, and only if that doesn't work either, turn clockwise.
It's incredible considering the limited amount of code space Toru Iwatani had to work with in the first place, and yet came up with such a fantastic game with such intelligent programming for even such a simple thing as a frightened ghost. Imagine how optimised current modern computer games would be if such intelligence was used program them. 😀 Thank you for this very detailed explanation.
I love all of your videos! they are so well researched, the visuals are perfect, and all of it is super informative
good & clear explanations... with even better visual graphs! 👏
108.10% pedagogy here!
I would love the see a making of of this video. Such beatiful and easy animations/illustrations :)
Excellent! Phenomenal video as always, RGME.
CS Teachers: "Derefencing naked pointers is undefined behavior"
Pac-Man Programmers: Hold my osake
The hardest part of calculating that Markov chain is that if you lay all the vertices on the board like that, Pac-Man will start eating them before you're done figuring it out
Fantastic visualisations of the state transition graph!
was just rewatching the pacman AI explained video and noticed this one was new, great timing haha
Incredibly fascinating. Thanks again for your polished infotainment on old school hard and software.
Huh. So Clyde's always hiding in the Fright-favored corner of the map.
*_T H E L O R E_*
*[**22:54**]:* The assumption of a 50/50 split assumes the lack of bias in direction-picking in 'symmetric' cases, which we know is false by this point.