One thing you neglect to mention is that the programmers of Pacman, made a conscious decision to use JUST ONE BYTE to count the levels in the game. If they wanted, they could have used two bytes to store the level number, thus increasing the level count to 65,535. or (1111 1111 1111 1111). So, it's not so much tied to the fact that it's an 8 bit computer, it's only "8 bit" because the accumulator registers in the CPU are 8 bit (although the program counter and indexing registers are 16 bit), and the data bus size is also 16 bit. They probably surmised that no one would ever achieve level 256 (and, for quite some time, no one did), plus, it just makes life easier to use just 1 byte to store values whenever possible.
John Laury To clarify, '8-bit' isn't simply the width of the accumulator(s). It was usually the maximum width of the data path. Most had 8-bit data busses, and 16-bit addressing, not 16-bit data busses.
+John Laury I think the game designers of pacman never tested it far enough to get to 256. They probably never thought anyone would get that far. A better solution in my opinion would be to just add a win screen at 256 (so, if the level counter is 255 and the player wins that level, show a "You Won" screen).
***** Yeah, that would have been the thing to do, or, which was more common in those days, simply "wrap" around to the first level, effectively starting the game over, but with the score left in tact, was more common in those days. You have to understand, these were arcade games, and arcade owners made money when you plopped another quarter every 5 to 10 minutes, so games came with DIP switches that could be flipped to increase difficulty, and even hacker boards were sold by 3rd parties, that would "add on" difficulty for games that didn't have harder difficulties, or the hardest difficulty had been mastered by players. It was much cheaper to invest in an add on board that cost a few hundred dollars to increase the difficulty and kept the quarters flowing rather than buying a new game. Many game hacks/alternate versions came about from these 3rd party boards. As a matter of fact, that's where Mrs Pacman came from, not from Namco. The last thing arcade owners wanted was someone dropping a quarter and owning the machine for the next 4-5 hours while they played a game to completion, thus, arcade machine makers never really programmed endings into the games. They also underestimated the skill level players would achieve. Using MAME and unlimited lives cheat codes, I played a bunch of games I used to play as a kid to the "end", either when the score turned over, it reached an ending, or when the level returned to level 1, and none of the games ever had an official "you made it" ending.... None. They all just flipped either the score, or returned to level 1, and, Pacman of course had it's famous split screen glitch. Interestingly, Pac Man 256 is now out recently for phones and tablets (I have it on my Apple TV), and it's based on that glitch, which is a really cool nod to this cool glitch.
@Ismary Alonso with nbt editing you can get up to 127 and down to -128. These are the upper and lower bounds of signed 8 bit integers. As for why the soft cap of 64, I don't know.
It would have been useful to point out that the "bitness" of a computer isn't necessarily related to how high it can count. Most 32-bit desktop and console processors out there can handle 80 (and sometimes even 128) bit floating-point numbers, and / or are able to associate two 32-bit registers to handle 64-bit integers. The "bitness" of a CPU / computer generally relates to three things: instruction size, integer register size and address size. "How high they can count" is a mix of hardware and software, because CPUs have more than one register, and registers of more than one type. I realise this is just meant to be an explanation for the general public, but it's not a very good idea to mislead people into thinking they know what a term means by pretending to have given a complete explanation when you haven't.
This videos are incredible, aren't they? For years I could't for the life of me understand surface tension. And one of these science channels, idk if it was minutephysics or some other, but the first time I watched it I've got it. They explain it in a easy and yet full and detailed way. Just amazing.
Simple way - The zeros basically say this, 0000 = 8421. To get a number, you turn a 0 into a 1, so to get a two, you change the second 0 into a one. With higher bit programs you can have more options, with each zero added ass another bit, it is double the number before.
You can add two or more bytes together to form larger numbers, but that takes up more memory, which was precious back then. Two bytes together can make numbers up to (256*256) 0-65535, four bytes (256*256*256*256) 0-4294967295 and eight bytes 18446744073709551615.
Adding to what GigaBoost said about using several 8-bit numbers: In the CPU, there are things called flags. There's one flag in particular that switches on when a calculation results in an overflow (such as 255 + 1 = 0). You check the value of this flag whenever you do a calculation to know when to change the second number.
I love the whole video, but for me this was the best bit: "It's taken me 15 years to get to the point where I can explain it to you." It reminded me of another quote: "So long as men cherish the dream of getting something for nothing, money without working, knowledge without study, power without knowledge, and virtue without asceticism, so long will pseudosecret and initiatory societies continue to flourish, with their imitative hierarchies and their mumbo-jumbo that imitates the real secret language, the language of technicians." (Bergier & Pauwels)
Thanks very much for this video! As a long time player of video games, I've often encountered the 255 limit in 8-bit games (255 possible colors, 255 possible rupees, etc) and even now up to playing World of Warcraft (a 32-bit game) with its limit of 2.147 billion gold :) I've known that it was related to to limitations of binary, but this did a wonderful job of explaining exactly why.
this MUST be the reason for 255 all stat in final fantasy. you have explained something that NO ONE ELSE could explain. i thank you with deep gratitude. =)
@Jeffrey Black: ( No reply button? ) "...effectively a 4 digit base 256 number when adding in 8bit". I see why you think this and if you want to insist on your right to think of it this way, then I'm not about to persuade you otherwise. I don't think of this the way you do and I'll explain why. First off, no mathematician who uses bases does this any other way: There is one symbol per digit and Not a group of symbols in one base reconceptualised as one symbol in a different one. Why add that pointless extra step? The number of seconds in a minute ISN'T in base sixty. It's a 60 interval fraction written in base ten. If it was base sixty then this logic would continue further along the digits without limit. It doesn't. It goes for minutes and seconds and not hours or fractions of a seconds. There are not sixty hours in an 'hexacontour', there's no such thing. Therefore the time and angles analogy is certainly not an example of base 60 or 360. Secondly, carry does Not occur on the eight bits as a whole. I can't draw a diagram in this box with ASCII but what happens at the logic level in a byte is that eight additions are performed between the two-bytes added. One for each bit. Each carry condition is only a carry on One bit. Bit zero takes it's carry condition from the carry flag and wen there is a carry condition on bit 7 ( the eighth bit ) the overflow on this one-bit addition is placed into the carry flag. Try it with a pen and paper. Take any two eight-bit binary numbers, add them. In Every single case when a carry condition occurs that carry occurs on the addition at bit 7 of seventh but of the two values, plus the carry condition from bit. In other words, the CPU has Not done a single addition on two digits A and B with 256 values each, as you suggest, it has performed eight one bit additions. This is why it is called an 8bit CPU in the first place: The number of data lines the CPU will operate on at a time. You can, if you like continue to think of this otherwise, but besides not helping in any technical way, it will hinder you as it can only come from a lack of insight into what actually happens.
On say, a 6502 CPU, you can put the microprocessor into binary-coded-decimal mode with the SED instruction. An eight bit memory address can hold sixteen different values in each of its two four-bit nybbles. This mean each can be use to hold the ten values representing 0-9. Which, in Hexadecimal is exactly what you see: 10011001 in binary = 153 base 10 but 99 in base 16. Add 1 to this and, when in decimal mode, instead of going to the next hex value (9A) it resets to 0 and sets the carry flag.
This is extremely incomplete. It's a very good explanation, but if the computer could only count to 255, then why does the score go higher? Different elements of the game are store in different memory registers and the programmer chooses the allocation of those memory resources. The reason the level stops the game at 255 is due to the fact that it is stored in memory as an 8 bit integer. The score uses multiple 8 bit allocations to store its value and can count higher. This is true for integers.... floating point operations are a completely different story altogether. In fact, floating point calculations in early computers were so complex, they sometimes utilized dedicated processors to handle the math called co-processors.
Thanks! I always wondered how the game was anything else but a 1-255 simulator, as it seems like the entire 8-bit processor is being used for counting what level you were on.
What brought this all up is the fact that the processor in a Pac-Man machine is an 8-bit processor--it can hand 2^8 (256) addresses (0-255, hence the level cap at 255). The number in "#-bit" is the power that the 2 is raised to. A 32-bit processor has address spacing for 2^32 and a 64-bit processor can handle up to 2^64 addresses. You mentioned the address bus (/wiki/Address_bus). This is, in fact, the determining factor of how many bits a processor can be described to have.
Ah I remember when I was a lad playing WoW on a private server running on my own machine and could not set my characters level higher than 255. I remember being perplexed as to why 255 specifically was the max! Created my love of programming that did.
Just to clarify on how the carry bit is used in addition: least significant byte: clear the carry bit. Add number, add next number with carry to next significant byte, keep going until all bytes handled. Usually only a low and high byte. The carry being used as INTENDED.
Now, saying that it's IMPOSSIBLE to count any higher than 255 on pacman is wrong. They could have just used two bytes to store the levels in if they wanted to. Then they would be able to store around 65 000 levels. They just thought: "well, we want to make the game consume the least amount of memory possible, so let's just use a 8 bit byte to store the levels. I mean, nobody will ever be able to make it to level 256 right?"
+BrianAwesomenes you can usually combine registers. having to remember my zilog z80 microprocessing classes from 15 years ago but I am sure I combined registers to work with 16 bits at points in my project.
.. incrementing a 16-bit register called AX. In assembly, it might look like this: INC AX Now, let's assume that AX had a value of 65535. What happens is that it gets wrapped back to zero, and a CPU flag gets set to indicate overflow. A program can check this flag, and take appropriate action. For example, when using two adjacent 16-bit memory locations to represent a 32-bit value, the program can increment the second location when the first location wraps. Doing this allows a...
Going by this explanation, you would think that it would just loop back to the first level (level 0) after level 255. But it's much more complicated and much stranger than that. Retro Game Mechanics Explained has a great video on this.
For people wondering why 2^8 equals 256 and not 255, think about it this way: 0 is the first number. The year 2000 is in the 21st century in the same way that 255 is the 256th number.
8bits are called a byte. So the biggest number being able to be stored in one byte is 255. If you want to have bigger numbers, you need to take more bytes. For 3560 you need two bytes. It would be 0000 1101 1110 1000.
The level is single byte. The level can be stored as a larger number composed of several smaller numbers, effectively as a base 256 number, where each digit is a binary number between 0 and 255. When you add 1 to 255 in 8 bit, you get a buffer overflow, which is detected and can be handled when using larger numbers.
I think this explanation is unsatisfactory. the problem isn’t the 8 bits of the CPU, but the software of the game. At that time everyone of us were playing with the 8080 and 8085 chips from Intel and we could do operations on mumbers bigger then 255, obviously. The pre- IBM computers had 8 bit processors and could do floating point math and big integer math as well. Well, as said, the problem wasn’t in the 8 bit registers, but that the variable used to store the game level was a byte variable ( wich had 8 bits) and not an integer variable which had 16 bits ( 2 bytes)
Due to the 8-bit data path and 8-bit CPU, operations on 16 bit numbers (which typically had to be loaded into two 8-bit registers emulating one 16-bit register) were much more expensive than operations on 8-bit numbers.
RonJohn63 Yes, but not impossible. A counter that consumed very tiny CPU time ( since it would be modified once every level change) could have been16 bits long. The only excuse might be the very small amount of memory of the 6507 (8KB)
FSRubyc /Yes, but not impossible./ Well sure. They even had assembler libraries to do 32-bit floating point math. But it was *s-l-o-w*. /The only excuse/ And a damned fine excuse it was. Do you know how expensive RAM was back then? /the 6507/ The Pac Man arcade game ran on a Z-80. Even so, they used as little RAM as possible, and used as many tricks as possible so as to not waste any precious cycles and bytes.
No. I'll explain what happens: If a byte contains 255 and 1 is added, it 'rolls over' to 0. Unless you write the code to take this into consideration that's what happens, it's that simple :) Now, there are different ways to add 1 to a byte. You could say, for example: LDA level (take the number in the byte labelled 'level' and store it in accumulater A) INCA (increase the number in A by 1) STA level (store the number in A in the byte labelled level) (continued)...
Because the various game values were stored in different areas. The computer had multiple registers that met together in order to have a high score. The designers likely believed that nobody would ever play up to level 256 and so they stored the level data in an 8 bit register - limiting the game to 255 levels.
This video is slightly simplistic. 8-bit computers can only count to 255 if they use a single memory location. Pacman does this for counting levels. But if the software is designed to used two memory locations for the count, then it can count to 65,535. And if it uses four locations, it can count to 4,294,967,296. And using floating point notation, taking eight memory locations, then software running on 8-bit computers can handle a wide range of numbers from the tiniest decimal fractions, up to more than the number of atoms in the universe!
in simple and graphical terms , picture it like this Here's 1 bit 0 now you take 8 of those and put them together and you get 1 Byte 00000000 this is what is in 1 Memory register so this number can be from a min of 00000000 - 11111111 Just like if i said to you, write down the smallest and largest 8 digit number, you would write 00000000 - 99999999 right. ok so the highest number per memory register is 255 Now, Registers connect together in series, as follows... 1st register 2nd register 3rd register and so on to get 00000000 00000000 00000000 now the program could look at each digit in the score as a register so it would only need a max number of 00001001 =9 per register hence to make the number 22323542 8 registers are used to produce this 2 2 3 2 3 5 4 00000010 00000010 00000011 00000010 00000011 00000101 00000100 2 00000010 does that help any
We're now seriously off-topic, but you're getting close to Binary Coded Decimal (BCD). Notice that you can encode 0-9 in 4-bits, so you can fit two BCD digits in one byte. So you can hold your 8-digit decimal number in 4-bytes of BCD as follows: 0 2 2 3 2 3 5 4 00000010 00100011 00100011 01010100 :-}
You are right. For an 8 bit computer to store/access/use 16 bit numbers, it has to use two 8 bit numbers. In the CPU, there are things called flags. There's one flag in particular that switches on when a calculation results in an overflow (such as 255 + 1 = 0). You can use this flag to add one to another number.
Microprocessors have a register that has "flags" that are set or cleared depending on a few conditions for the last computation. One of them is called the "carry" flag, which is set to 1 if the the highest place had a carry. You could use it to detect that the result was too large for the register. There are usually instructions that you can use to take the carry into account, so an 8-bit computer can technically count beyond 255, but 255 is the largest result you can get with one instruction.
Another way is to divide the number by two unlit you reach 1 or 0. And every time you divide it, write down whats left(1 or 0). Then just flip it. eg. 37/2 = 18 (1) 18/2 = 9 (0) 9/2 = 4 (1) 4/2 = 2 (0) 2/2 = 1 (0) 1/2 = 0 (1) so 37 DEC = 100101 BIN
Even your Computer can "only" count from −9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 (0 to 18,446,744,073,709,551,615 If it is unsigned) (If you have a 64-Bit OS & Processor)
Yep. You can deal with more than 8-bit numbers, but it's not automatic. You'd have to more manually. There might be an add instruction, which adds one byte to another. If this caused the number to wrap around, it would set the carry flag, which is a bit in a special status byte. There might also then be a different add command that not only adds two bytes, but also adds one if the carry bit was set. So you could carry the one between adding the lower and higher bytes of a multi-byte number.
Exactly. What everyone is forgetting here is the Apple II was an "8-bit computer" and it certainly could count higher than 255. Businesses used them to run their accounting on Apples, and they certainly had to deal with more than $255 at a time. It was the PacMan programmers who failed, not the 8-bit computers.
There's several ways you can do this. A byte in the processor can only count up to 255, but in the case of the high score, you can just have four bytes which each only count up to 9. When one reaches 9, make it go to value 0000 0000 and add 1 to the next byte instead.
To try and illustrate my point about the base of the number being represented being independent of the ability of a number of bits to represent it: In decimal (base 10), the number nine is 9 and in binary this is 1001. Now note that in base 20, the number nine is still just 9 and that this doesn't affect the binary representation which is still just 1001. Sorry if you understood this already. If you meant coding a different base into binary, as with BCD then please refer to my previous comment.
There's no level 0, when the computer overflows and only reads 00000000 instead of the real value it tries to look up in a part of memory used by something else, the computer doesn't know that what is looking at is not a level so it does it best to display as graphics it but is just gibberish when is displayed on screen.
burnsy96 Also, I'm not 100% sure, but if I recall correctly the program will write that 1 it can't write in the level-amount byte somewhere else in the memory, which surely screws everything up.
burnsy96 one solution to integer overflow is to saturate at a maximum value. I'm just taking a shot in the dark, but the code could have included a conditional statement to restrict incrementing the level integer to when it's NOT 255, as a method of saturating at the ceiling of signed 8-bit integers. Similarly, as counting down beyond 0 for a signed integer will yield the highest value for an n-bit signed integer, one might choose to saturate the value of the integer at 0, but I'm not sure if the terminology is the same(as in, "saturation").
Each bit doubles the amount of numbers it can display so that double each time (2^n) But one value is zero so the highest it can count to is one less (2^n-1)
+rubixman7x7 There was no other reason other than to save storage space. There are 8-bits to a byte of memory. Pac-Man most certainly required more than 1 byte of memory. The 255 explanation in this video is wrong. It was quite frankly, a design decision based solely on the idea that no one could get to that level. To handle a level higher than 255, after all 8-bits are full, the game would only have to store the 255 in 1 byte than move on to the next byte, if that makes sense. In fact, in computing 0 is considered a number and thus the limit is actually 256 numbers despite capping visually at 255. Which means the computer could have considered 0(or 0 0 0 0 0 0 0 0 in binary) as level 1. So even IF the game was limited by the 8-bits/1 byte, they could have easily made a level 256. Take an IP address for example, for each number in the sequence you can put 1-255, but it can also be 0. It's understandable to be confused as the guy explaining it is only considering the processing portion of a computer, and not the storage portion. This is what RAM(Random Access Memory) is. It's a place to store information. This is why the score can get much larger than 255. And why you are absolutely right to assume that they could have gone higher in levels. It simply came down to cost to consumer and design. Pac-Man was created in a time when storage limits were much, much lower for around the same cost. So when it came down to whether or not to tip over from 1 byte to 2 bytes and so on, they really scrutinized as to whether or not it was worth it. So the designers simply said, no one will get that high so we will reserve just 1 byte for level data.
I still sob a little when I think back to 16-bit PCs. Things were so much simpler then. Windows was crap, obviously, but all the DOS/4GW games made it the happiest time of my life. :)
I love how he explains binary or should I say 0100100100100000011011000110111101110110011001010010000001101000011011110111011100100000011010000110010100100000011001010111100001110000011011000110000101101001011011100111001100100000011000100110100101101110011000010111001001111001
Don't be concerned, Dr James is now one of the most highly educated people on our planet, top 1%. Not only that, James has a PHD in physics, so if he doesn't screw up his life too much he is up for a pretty cosy journey to his deathbed. You don't need to be concerned :P
The number of bits/bytes used to store a number is a programming decision. The programmer decided 1 byte was enough to store the level. It was a sensible decision, it takes hours to cause PacMAn to malfunction.
but is the first level called lvl 0? There should actually be 256 levels, as level 0 is the first level, and 8bit contains 256 numbers (including 0) Am I wrong?
If one of the other commentors was correct, they used the Level Number (starting with 1) to show how many fruits to display, and when the Level Number is 0, it never knows when to stop printing fruit.
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384.... every next number is 2^(N+1) from the previous... which N starts counting from 0 for the first bit. Basically using 4 logical gates of on/off can process 0 -15 which is 16 states of data. A convenient way to process large numbers by using the least possible logic gates.
I don't think this video is very good, I'm sorry to say. First, I think he could have easily gone much deeper into binary arithmetic--the places are all multiples of 2--1, 2, 4, 8, . . . 128, 256. That would have given the viewer a much more interesting understanding of binary. But second, I don't think he actually explained WHY it ruins the game. I don't know this for sure, but normally the reason it dies is that the programmers made a mistake. They did not think anyone would ever get to 255, so they did not bother checking to make sure it did not go over 255. So when it adds 1 to 255, I will bet you it actually WRITES OVER the next byte over, destroying whatever information is in the bit one to the left of the level byte. That information was important to the program, and when it gets written over it destroys the game. By the way, this video could have gone much deeper in a very interesting other direction. This issue is exactly how most security problems are exploited by hackers to this day. Programmers make this mistake all the time--forgetting to check "overflows." It frequently messes up the computer just like it did in pacman--when that glitch happens, the hackers then have a doorway to write over whole swaths of code with their own evil code.
The glich happens when you hit 256 and is a space issue. if you you are thinking about the score, it is using a multiple of binary code and displays its answer ( dont forget you can add, subtract divide and multiply binary )if you look the score it dosn't go by ones or twos it happens in the hundreds and thousands furthering my point. the space and how much each thing takes obviously plays a role in this but is hard to explain.
I'm a computer programmer. '0' is considered whatever state the system designers wants it to be. In electronics terms, there is no Zero state, there are two voltages, and the higher of the two voltages is usually the one used for Zero. So, Zero definitely doesn't mean an 'off state'. As has been mentioned before in this thread by somebody who was correct, you can use '0' in your counter to be the internal number for level '1', and have 65536 levels.
I once failed to persuade my friends we'd be better off with binary than decimal. :) In decimal you count to 10 on your fingers, in binary you can count to 1023. :)
The equation for finding the total number of values for any binary number is take the number 2 and raise it to the power equal to the number of bits, represented by x. For example: For a 4-bit number, let x = 4. The equation is n = 2^x, which equals 16. A 32-bit number would be 2^32, which is approximately 4.2 billion bits, or 4.2 GB. This explains why 32-bit operating systems cannot utilize more than 4 GB of RAM at a time, and the reason for the move to 64-bit OS's.
There's a trick too: most of these game only display thousands, so they basically add dummy 0s when drawing in the screen. However, you could also have two numbers to represent the score. Supposed we have the score numbers A and B: 1. Both numbers start at 0 2. Each time score A reaches 255, add 1 to score B and reset score A 3. Smart ass converting without exceeding the 8-bit limit to display it on screen.
Well, technically, they were; just not 32-bit integers. 8-bit integers, that we now usually call "char" are just one specific type within the more general integer structure. 16-bit integers and 64-bit integers are other usual types of integers. Back to the original question, the answer would be that a 8-bit computer's hardware can not count above 255. but using software-side computation, we can expand this limit, theoretically indefinitely; In practice, it's limited by usable memory.
The software programmer handles it. You are given instructions which respond to the carry state of an arithmetic operation. On a 6502, the one I know, you get BCS ( branch on carry set ) meaning you can easily branch out to a subroutine which handles the carry condition. On the Z80, the CPU used for Pacman, you have JP C ( Jump on carry condition ), which is functionally very similar. But both have ADC, meaning you can add, along with the carry, just like with written arithmetic, but on the CPU.
Pretty accurate, although it is 'arithmetic overflow', not 'buffer overflow'. 'Arithmetic overflow' occurs when a carry condition has been met, such as 128+128, whereas buffer overflow occurs when a buffer is asked to take more information than it has space to hold.
If you find that interesting: Windows Server 2012 (the newest version of the Windows Server OS) is tested and certified to run 4TiB--that's Tebibytes--of RAM (don't ask me where they got 4TiB of RAM or what motherboard they used that supported that much RAM). If you recall that large number from my first comment...18 EiB...that's about 4.7 Million times larger than 4TiB (there's Pebibytes between there too)...It's 1024^2*18/4 times larger (in case you wanted to run that in a calculator).
Nobody would program 255 similar levels Here's what they did: They in fact designed one level. Beating a level increments the number for the level. Other variables also get changed to ramp the difficulty up. Because it was only allotted 1 byte of storage, the maximum level is 255 instead of 15. They did not expect anyone to get there, so they didn't see the need to test it past level 2. The different variables somehow cause the mapping algorithm to bug out when it returns to level 0 (256).
What actually happens is, the level number increment isn't trapped so following the overflow the software later misses a bounds check which occurs before drawing the fruit on the bottom of the screen. This check now thinks you are on a low level therefore doesn't truncate this number prior to fruit drawing. The software then proceeds directly to a routine made to draw one fruit for every level, which only works between level 1 and 7. On level 0 it wraps and draws 256 fruit overwriting the maze.
Actually the 255 limit is simply the limit of a single math operation. When the number rolls over there is a bit in the ALU of every processor typically called the carry flag. This flag can be used to string multiple math operations together to achieve any number of bits you want to use to represent a number. Additionally with the exception of some of the simplest 8 bit processors, the ALU can do 16-bit addition for computing addresses. This may be done using two 8-bit operations or may be done using dedicated 16-bit adders. Thus most 8 bit CPU can address much more than 256 words of memory. A processor than cannot use more than 256 words would be pretty limited because you need both code and data memory to do anything useful. Some CPUs don't bring all of the address bits out to pins on the chip thus creating an hardware limitation on the amount of memory it can address. The biggest difference between a computer and a simple calculator is the ability to use logic to extended operations beyond a fixed size representation of values.
No. A variable is just an address that points directly to where that information is stored. The way you define the variable tells the computer how big it's data stack will be. Basically, the instructions for the computer are all in a stack, too, and a pointer tells the computer which instruction is next. When it gets to a variable, it hops out of it's stack of instructions and pulls that variable's stack. 1 slot in a stack = 2 bytes (8 bits). It matters on how you define the variable.
Think about it this way.. You read the number from the RIGHT instead of from the left. The first number means 1, the next number means 2, the third number means 4, the fourth number means 8, the fifth number means 16 and so on. It doubles every time. You write a 1 if you want to add the number, and you write a 0 if you want to skip it. 10010 is 18. Why? I wrote a 1 in the "2-place" and a 1 in the "16-place". I need to add those numbers together. I wrote 0 in the others, so I had to skip them.
Well, if I've understood your query correctly; usually, you have to implement a software solution to accommodate for limitations in the base hardware. Typically, an eight bit video game would reserve six bytes for score. Handling an eight byte score display requires an eight step loop to update it, e.g.: INIT: LDA #$30 ; ASCII: '0'. LDX #$07 LOOP: STA SCORE,X DEX BPL LOOP RTS Above resets score table. Then, to update score array; post following....
That actually is true; I once read a few articles on the kill screens of games such as Dig Dug, Galaga, Donkey Kong, and, of course, Pacman. After the game runs out of regular fruits to display, it displays random 2x2 tiles along the bottom of the screen, and then down the right, covering over some of the previously written sprites.
It's a good question.... there's even some dispute at the higher level because whether or not your computing device is 8/16/32/64 bits, etc, can affect sales and marketing. Whereby you do strictly do get 16bits with two bytes, you don't, necessarily, end up with a 16bit number or CPU. So, a 16bit+ CPU is not one which merely combines bytes. 8bit micros can typically handle 16bit numbers using two bytes but they require more than one operation to do it.
That's a neat question. Usually, it uses a variety of Binary Coded Decimal. Often this feature is supported by the CPU, as it is on a 6502 microprocessor, but it can easily be achieved in software too. The process is in fact a little bit difficult to completely explain in one 500 character box, and, there is more than one clear way of doing it.
It doesn't explain how the code thinks and how the bug is created. It's not all about the numbers, it's the FRUIT COUNTER that glitches because of the number that "doesn't exist." It rolls to 0 but 0 rolls back to 255, creating 255 fruits shown primarily in hexadecimal code onscreen. That's basically how it happens in a nutshell.
Good video, one tiny error though - processors don't limit number widths - implementations do. For example, the latest LLVM apparently now supports arbitrary-width integers. That means you could have a uint65536 if you wanted to, even on an 8-bit processor. Performance is another question, though. That's (probably) part of the reason why your score isn't limited to 255 in Pac-Man.
It's nice to see you agree with me that BCD isn't hard to explain and that it doesn't answer his question despite saying the exact opposite before my reply. The only confusing part is that you're telling me it's irrelevant to his question like I didn't just say that.
actually 2^16 is 65526. 15 bit lines counting up to their maximum hit 65525 and can't continue unless there is a 16th line. a 16 bit processor would actually stop at 131,171 because 2^17 is 131,172, so it can count up to 1 under this because it had 1 less lines than the 17, or the next power :p
... that could access more than 64k of memory. Of course, the way old 16-bit 80x86 processors (or 32-bit 80x86 processors in 16-bit mode) did this was rather confusing and cumbersome, but that's another story. Look up '80x86 memory segmentation' if you're curious.
because each screen of the game was given a binary value in the processor so screen 1 = 00000000 screen 2 = 00000001 all the way to the 255th screen which would be 11111111. Each individual spot in the score works the same way but each one can only go up to 10 so if your score is 1,234,567 the place with the 7 has 10 possibilities (0-9 or 00000000-00001001). So when a spot reaches 9 the game is programed to add one to the next spot (the 6). The issue comes when you run out of number spots.
8 bits will go up to 255, but it can count 256 numbers including 0. What is the 0th level used for; why didn't the pacman game developers just display the binary number + 1 and have 256 levels?
Each byte is a collection of eight bits. The descriptive title is a contraction of the expression "By eight", the arrangement of pathways on an 8bit CPU. Bit is a contraction of "binary digit". So, bytes take binary digits by eights. Hence bits and bytes. And, yes, for each byte, your possibilities multiply by 256. For each bit, they double. This means if you use just one byte for your level count, it's scope is 256.
A lot of people are having revelations with binary. He kind of explains binary in a simple way, yes, but it's very tedious when you get to the higher values. Let me explain. See, if you were to try to figure out, say, 811 with that method, it'd take a little while. I can say that it's 1100101011 using a simple method. 1100101011 = (1 x 2^9) + (1 x 2^8) + (0 x 2^7) + (0 x 2^6) + (1 x 2^5) + (0 x 2^4) + (1 x 2^3) + (0 x 2^2) + (1 x 2^1) + (1 x 2^0) = 512 + 256 + 32 + 8 + 2 + 1 = 811 I explain it worse than I intend to. If there were tables, I could actually spend the time writing it all out, but I can't be flopped doing so.
Yup, It's called the 8-bit limit in my mind. I'm a programmer and while it IS the 8-bit limit (255), I can't remember if that's an official term or something I've just said to myself for all these years. Other programmers, do you say 8, 16, 32, 64-bit limit, etc? Also, for you non-programmers.. this is also why in Nintendo games like Zelda or Mario you can have a maximum of 255 coins. As a kid I saw this all the time in NES games. I always seemed so random yet so many games had it. This is why.
"... most people don't spend their time compulsively playing video games ..."
R-Right...
I-I know r-right? What kind l-losers like video g-games?
+Tomas Cooke made in 2011, not that many high gaming channels just yet
gaming was still very popular then
u-umm,r-right, g-games are for n-nerds
says a guy watching a 5 year old Numberphile video
One thing you neglect to mention is that the programmers of Pacman, made a conscious decision to use JUST ONE BYTE to count the levels in the game. If they wanted, they could have used two bytes to store the level number, thus increasing the level count to 65,535. or (1111 1111 1111 1111). So, it's not so much tied to the fact that it's an 8 bit computer, it's only "8 bit" because the accumulator registers in the CPU are 8 bit (although the program counter and indexing registers are 16 bit), and the data bus size is also 16 bit. They probably surmised that no one would ever achieve level 256 (and, for quite some time, no one did), plus, it just makes life easier to use just 1 byte to store values whenever possible.
John Laury To clarify, '8-bit' isn't simply the width of the accumulator(s). It was usually the maximum width of the data path. Most had 8-bit data busses, and 16-bit addressing, not 16-bit data busses.
muibien
+John Laury I think the game designers of pacman never tested it far enough to get to 256. They probably never thought anyone would get that far. A better solution in my opinion would be to just add a win screen at 256 (so, if the level counter is 255 and the player wins that level, show a "You Won" screen).
***** Yeah, that would have been the thing to do, or, which was more common in those days, simply "wrap" around to the first level, effectively starting the game over, but with the score left in tact, was more common in those days. You have to understand, these were arcade games, and arcade owners made money when you plopped another quarter every 5 to 10 minutes, so games came with DIP switches that could be flipped to increase difficulty, and even hacker boards were sold by 3rd parties, that would "add on" difficulty for games that didn't have harder difficulties, or the hardest difficulty had been mastered by players. It was much cheaper to invest in an add on board that cost a few hundred dollars to increase the difficulty and kept the quarters flowing rather than buying a new game. Many game hacks/alternate versions came about from these 3rd party boards. As a matter of fact, that's where Mrs Pacman came from, not from Namco. The last thing arcade owners wanted was someone dropping a quarter and owning the machine for the next 4-5 hours while they played a game to completion, thus, arcade machine makers never really programmed endings into the games. They also underestimated the skill level players would achieve. Using MAME and unlimited lives cheat codes, I played a bunch of games I used to play as a kid to the "end", either when the score turned over, it reached an ending, or when the level returned to level 1, and none of the games ever had an official "you made it" ending.... None. They all just flipped either the score, or returned to level 1, and, Pacman of course had it's famous split screen glitch. Interestingly, Pac Man 256 is now out recently for phones and tablets (I have it on my Apple TV), and it's based on that glitch, which is a really cool nod to this cool glitch.
John Laury s
Remember collecting 255 rupees in the original Zelda?
ah yes, the 8-bit unsigned upper limit
@Ismary Alonso with nbt editing you can get up to 127 and down to -128. These are the upper and lower bounds of signed 8 bit integers. As for why the soft cap of 64, I don't know.
@Ismary Alonso because why not? I mean it’s a power of eight, so it is nice and clean.
@Ismary Alonso Design choice. Not a limitation.
"rupess"???
That's Indian currency. Sorry I've never played Zelda ever, can anyone tell me what Zelda has to do with rupees?
This is also why the traditional maximum missile capacity in Metroid games is 255, and why IPv4 address values only go up to 255.
And attack, defense, speed,... max stats in old Final Fantasy games only goes to 255.
If you press 4 while the video is playing he shows how to count to 4 using binary.
There 10 kinds of people: the ones who understand binary, and the ones who don't.
There are 10 kinds of people in the world. Those who understand binary, those who don't, and those who didn't expect this joke to be ternary.
There are 10 kinds of people in the world. Those who understand hexadecimal, and F the rest.
Binary: 11111111 Hexadecimal: FFFFFFFF
Binary: 1111 1111 = FF in hex, each digit is 4 bits(0-15) in hex.
and the other ones are the guys that can't do math or grammar
It would have been useful to point out that the "bitness" of a computer isn't necessarily related to how high it can count. Most 32-bit desktop and console processors out there can handle 80 (and sometimes even 128) bit floating-point numbers, and / or are able to associate two 32-bit registers to handle 64-bit integers.
The "bitness" of a CPU / computer generally relates to three things: instruction size, integer register size and address size. "How high they can count" is a mix of hardware and software, because CPUs have more than one register, and registers of more than one type.
I realise this is just meant to be an explanation for the general public, but it's not a very good idea to mislead people into thinking they know what a term means by pretending to have given a complete explanation when you haven't.
That explains why Pokemon reset back to level 1 after 255 using the Missingno glitch
"Pac-Man is not my game, so i have only reached around level 25-30."
wtf I have a high score of 142,580 and I can't even get to the first key
Oh... So, that's it? I kind of already knew this...
I thought there would be more...
*backs into bush*
+Andrew Kovnat
same
Blows marijuana smoke into your bush
This videos are incredible, aren't they? For years I could't for the life of me understand surface tension. And one of these science channels, idk if it was minutephysics or some other, but the first time I watched it I've got it. They explain it in a easy and yet full and detailed way. Just amazing.
Simple way -
The zeros basically say this, 0000 = 8421. To get a number, you turn a 0 into a 1, so to get a two, you change the second 0 into a one. With higher bit programs you can have more options, with each zero added ass another bit, it is double the number before.
The scratchy noise of that pen just drives me crazy D:
D O N O T C R I T I S I S E T H E P E N
You can add two or more bytes together to form larger numbers, but that takes up more memory, which was precious back then. Two bytes together can make numbers up to (256*256) 0-65535, four bytes (256*256*256*256) 0-4294967295 and eight bytes 18446744073709551615.
trying to figure out binary at first was very confusing, then it just snapped and I understood it all!
Adding to what GigaBoost said about using several 8-bit numbers: In the CPU, there are things called flags. There's one flag in particular that switches on when a calculation results in an overflow (such as 255 + 1 = 0). You check the value of this flag whenever you do a calculation to know when to change the second number.
that's also the reason why you could only hold 255 rupees in the 1st zelda-game
+Ginkaze1 255 was a common limit for NES games and others of that era due to the 8-bit architecture.
I love the whole video, but for me this was the best bit: "It's taken me 15 years to get to the point where I can explain it to you." It reminded me of another quote: "So long as men cherish the dream of getting something for nothing, money without working, knowledge without study, power without knowledge, and virtue without asceticism, so long will pseudosecret and initiatory societies continue to flourish, with their imitative hierarchies and their mumbo-jumbo that imitates the real secret language, the language
of technicians." (Bergier & Pauwels)
Thanks very much for this video! As a long time player of video games, I've often encountered the 255 limit in 8-bit games (255 possible colors, 255 possible rupees, etc) and even now up to playing World of Warcraft (a 32-bit game) with its limit of 2.147 billion gold :)
I've known that it was related to to limitations of binary, but this did a wonderful job of explaining exactly why.
this MUST be the reason for 255 all stat in final fantasy. you have explained something that NO ONE ELSE could explain. i thank you with deep gratitude. =)
@Jeffrey Black: ( No reply button? )
"...effectively a 4 digit base 256 number when adding in 8bit".
I see why you think this and if you want to insist on your right to think of it this way, then I'm not about to persuade you otherwise. I don't think of this the way you do and I'll explain why.
First off, no mathematician who uses bases does this any other way: There is one symbol per digit and Not a group of symbols in one base reconceptualised as one symbol in a different one. Why add that pointless extra step?
The number of seconds in a minute ISN'T in base sixty. It's a 60 interval fraction written in base ten. If it was base sixty then this logic would continue further along the digits without limit. It doesn't. It goes for minutes and seconds and not hours or fractions of a seconds. There are not sixty hours in an 'hexacontour', there's no such thing. Therefore the time and angles analogy is certainly not an example of base 60 or 360.
Secondly, carry does Not occur on the eight bits as a whole. I can't draw a diagram in this box with ASCII but what happens at the logic level in a byte is that eight additions are performed between the two-bytes added. One for each bit. Each carry condition is only a carry on One bit. Bit zero takes it's carry condition from the carry flag and wen there is a carry condition on bit 7 ( the eighth bit ) the overflow on this one-bit addition is placed into the carry flag.
Try it with a pen and paper. Take any two eight-bit binary numbers, add them. In Every single case when a carry condition occurs that carry occurs on the addition at bit 7 of seventh but of the two values, plus the carry condition from bit.
In other words, the CPU has Not done a single addition on two digits A and B with 256 values each, as you suggest, it has performed eight one bit additions. This is why it is called an 8bit CPU in the first place: The number of data lines the CPU will operate on at a time.
You can, if you like continue to think of this otherwise, but besides not helping in any technical way, it will hinder you as it can only come from a lack of insight into what actually happens.
On say, a 6502 CPU, you can put the microprocessor into binary-coded-decimal mode with the SED instruction. An eight bit memory address can hold sixteen different values in each of its two four-bit nybbles. This mean each can be use to hold the ten values representing 0-9. Which, in Hexadecimal is exactly what you see: 10011001 in binary = 153 base 10 but 99 in base 16. Add 1 to this and, when in decimal mode, instead of going to the next hex value (9A) it resets to 0 and sets the carry flag.
This is extremely incomplete.
It's a very good explanation, but if the computer could only count to 255, then why does the score go higher?
Different elements of the game are store in different memory registers and the programmer chooses the allocation of those memory resources.
The reason the level stops the game at 255 is due to the fact that it is stored in memory as an 8 bit integer.
The score uses multiple 8 bit allocations to store its value and can count higher.
This is true for integers.... floating point operations are a completely different story altogether. In fact, floating point calculations in early computers were so complex, they sometimes utilized dedicated processors to handle the math called co-processors.
Thanks! I always wondered how the game was anything else but a 1-255 simulator, as it seems like the entire 8-bit processor is being used for counting what level you were on.
What brought this all up is the fact that the processor in a Pac-Man machine is an 8-bit processor--it can hand 2^8 (256) addresses (0-255, hence the level cap at 255). The number in "#-bit" is the power that the 2 is raised to. A 32-bit processor has address spacing for 2^32 and a 64-bit processor can handle up to 2^64 addresses.
You mentioned the address bus (/wiki/Address_bus). This is, in fact, the determining factor of how many bits a processor can be described to have.
Ah I remember when I was a lad playing WoW on a private server running on my own machine and could not set my characters level higher than 255. I remember being perplexed as to why 255 specifically was the max! Created my love of programming that did.
Just to clarify on how the carry bit is used in addition: least significant byte: clear the carry bit. Add number, add next number with carry to next significant byte, keep going until all bytes handled. Usually only a low and high byte. The carry being used as INTENDED.
Now, saying that it's IMPOSSIBLE to count any higher than 255 on pacman is wrong. They could have just used two bytes to store the levels in
if they wanted to. Then they would be able to store around 65 000 levels. They just thought: "well, we want to make the game consume the least amount of memory possible, so let's just use a 8 bit byte to store the levels. I mean, nobody will ever be able to make it to level 256 right?"
+anton adamson It's not the memory that's only using 8-bits, it's the processor.
+BrianAwesomenes you can usually combine registers. having to remember my zilog z80 microprocessing classes from 15 years ago but I am sure I combined registers to work with 16 bits at points in my project.
.. incrementing a 16-bit register called AX. In assembly, it might look like this:
INC AX
Now, let's assume that AX had a value of 65535. What happens is that it gets wrapped back to zero, and a CPU flag gets set to indicate overflow. A program can check this flag, and take appropriate action. For example, when using two adjacent 16-bit memory locations to represent a 32-bit value, the program can increment the second location when the first location wraps. Doing this allows a...
How can you get to level 255?! I can barely get past level 2.
The world record player played 4 HOURS
You reached level 2?
@@Xnoob545 😵
Going by this explanation, you would think that it would just loop back to the first level (level 0) after level 255. But it's much more complicated and much stranger than that. Retro Game Mechanics Explained has a great video on this.
1+2+4+8+16+32+64+128
or simply (2^8)-1
For people wondering why 2^8 equals 256 and not 255, think about it this way: 0 is the first number. The year 2000 is in the 21st century in the same way that 255 is the 256th number.
I'm going to go back to computerPhile O.o ( :P )
+-GD- bryan I'm guessing this video was made before there was Computerphile
Yeah
8bits are called a byte. So the biggest number being able to be stored in one byte is 255. If you want to have bigger numbers, you need to take more bytes. For 3560 you need two bytes. It would be 0000 1101 1110 1000.
2^8-1=255
Yea, But if you count in 0, it is 256 numbers :D
I had never thought of that though it was quite obvious, thanks
The level is single byte. The level can be stored as a larger number composed of several smaller numbers, effectively as a base 256 number, where each digit is a binary number between 0 and 255.
When you add 1 to 255 in 8 bit, you get a buffer overflow, which is detected and can be handled when using larger numbers.
I think this explanation is unsatisfactory. the problem isn’t the 8 bits of the CPU, but the software of the game. At that time everyone of us were playing with the 8080 and 8085 chips from Intel and we could do operations on mumbers bigger then 255, obviously. The pre- IBM computers had 8 bit processors and could do floating point math and big integer math as well. Well, as said, the problem wasn’t in the 8 bit registers, but that the variable used to store the game level was a byte variable ( wich had 8 bits) and not an integer variable which had 16 bits ( 2 bytes)
Due to the 8-bit data path and 8-bit CPU, operations on 16 bit numbers (which typically had to be loaded into two 8-bit registers emulating one 16-bit register) were much more expensive than operations on 8-bit numbers.
RonJohn63 Yes, but not impossible. A counter that consumed very tiny CPU time ( since it would be modified once every level change) could have been16 bits long. The only excuse might be the very small amount of memory of the 6507 (8KB)
FSRubyc /Yes, but not impossible./
Well sure. They even had assembler libraries to do 32-bit floating point math.
But it was *s-l-o-w*.
/The only excuse/
And a damned fine excuse it was. Do you know how expensive RAM was back then?
/the 6507/
The Pac Man arcade game ran on a Z-80. Even so, they used as little RAM as possible, and used as many tricks as possible so as to not waste any precious cycles and bytes.
FSRubyc /slowness is not an excuse/
That's why most of my reply was focused on RAM.
No. I'll explain what happens:
If a byte contains 255 and 1 is added, it 'rolls over' to 0. Unless you write the code to take this into consideration that's what happens, it's that simple :)
Now, there are different ways to add 1 to a byte. You could say, for example:
LDA level (take the number in the byte labelled 'level' and store it in accumulater A)
INCA (increase the number in A by 1)
STA level (store the number in A in the byte labelled level)
(continued)...
If the old Pacman machines can't count higher than 255, how did you ever wind up with a score of 22,323,542 or whatever?
Because the various game values were stored in different areas.
The computer had multiple registers that met together in order to have a high score. The designers likely believed that nobody would ever play up to level 256 and so they stored the level data in an 8 bit register - limiting the game to 255 levels.
the highscore is 3,333,360 by the way
This video is slightly simplistic. 8-bit computers can only count to 255 if they use a single memory location. Pacman does this for counting levels. But if the software is designed to used two memory locations for the count, then it can count to 65,535. And if it uses four locations, it can count to 4,294,967,296. And using floating point notation, taking eight memory locations, then software running on 8-bit computers can handle a wide range of numbers from the tiniest decimal fractions, up to more than the number of atoms in the universe!
in simple and graphical terms , picture it like this
Here's 1 bit
0
now you take 8 of those and put them together and you get 1 Byte
00000000
this is what is in 1 Memory register
so this number can be from a min of 00000000 - 11111111
Just like if i said to you, write down the smallest and largest 8 digit number,
you would write 00000000 - 99999999 right.
ok
so the highest number per memory register is 255
Now, Registers connect together in series, as follows...
1st register 2nd register 3rd register and so on to get
00000000 00000000 00000000
now the program could look at each digit in the score as a register
so it would only need a max number of 00001001 =9 per register
hence to make the number 22323542 8 registers are used to produce this
2 2 3 2 3 5 4
00000010 00000010 00000011 00000010 00000011 00000101 00000100
2
00000010
does that help any
We're now seriously off-topic, but you're getting close to Binary Coded Decimal (BCD). Notice that you can encode 0-9 in 4-bits, so you can fit two BCD digits in one byte. So you can hold your 8-digit decimal number in 4-bytes of BCD as follows:
0 2 2 3 2 3 5 4
00000010 00100011 00100011 01010100
:-}
You are right. For an 8 bit computer to store/access/use 16 bit numbers, it has to use two 8 bit numbers. In the CPU, there are things called flags. There's one flag in particular that switches on when a calculation results in an overflow (such as 255 + 1 = 0). You can use this flag to add one to another number.
binary... hexadecimal... so glad that we have languages now.
Yeah, asm is a bliss. I was so tired of punching in machine code...
Microprocessors have a register that has "flags" that are set or cleared depending on a few conditions for the last computation. One of them is called the "carry" flag, which is set to 1 if the the highest place had a carry. You could use it to detect that the result was too large for the register. There are usually instructions that you can use to take the carry into account, so an 8-bit computer can technically count beyond 255, but 255 is the largest result you can get with one instruction.
This was the video from where i learnt to convert decimal to binary :D
Another way is to divide the number by two unlit you reach 1 or 0. And every time you divide it, write down whats left(1 or 0). Then just flip it.
eg.
37/2 = 18 (1)
18/2 = 9 (0)
9/2 = 4 (1)
4/2 = 2 (0)
2/2 = 1 (0)
1/2 = 0 (1)
so 37 DEC = 100101 BIN
01100101 - Get it ?
Ramen King 101 ikr
197?
Even your Computer can "only" count from −9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 (0 to 18,446,744,073,709,551,615 If it is unsigned)
(If you have a 64-Bit OS & Processor)
Cool, he's counting in binar-- ERROR INTEGER OVERFLOW
Yep. You can deal with more than 8-bit numbers, but it's not automatic.
You'd have to more manually.
There might be an add instruction, which adds one byte to another. If this caused the number to wrap around, it would set the carry flag, which is a bit in a special status byte.
There might also then be a different add command that not only adds two bytes, but also adds one if the carry bit was set. So you could carry the one between adding the lower and higher bytes of a multi-byte number.
I always wondered why it was 2^n-1 instead of 2^n
There are 2^n *numbers*, but the *range* of those numbers is 0-255 (just as there are 100 numbers in two decimal columns: 00-99.)
+FlyingPies155 Because that's the maximum number you can have. There are 2^n possibilities, but we have to remember that 0 is one of those.
Exactly.
What everyone is forgetting here is the Apple II was an "8-bit computer" and it certainly could count higher than 255. Businesses used them to run their accounting on Apples, and they certainly had to deal with more than $255 at a time. It was the PacMan programmers who failed, not the 8-bit computers.
The 255 limit is good, because it is a sign to go out and get a life. No offense.
I did get a life. An extra one at 5000 points I think!
"Get a life" .... is that a early access game ?
By default it was 10,000 for a free life. Arcade operators are able to go in and change the settings.
There's several ways you can do this. A byte in the processor can only count up to 255, but in the case of the high score, you can just have four bytes which each only count up to 9. When one reaches 9, make it go to value 0000 0000 and add 1 to the next byte instead.
in the legend of zelda for nes, you can't get more than 255 rupees
To try and illustrate my point about the base of the number being represented being independent of the ability of a number of bits to represent it: In decimal (base 10), the number nine is 9 and in binary this is 1001. Now note that in base 20, the number nine is still just 9 and that this doesn't affect the binary representation which is still just 1001.
Sorry if you understood this already. If you meant coding a different base into binary, as with BCD then please refer to my previous comment.
That doesn't explain why the game glitches, shouldn't it just roll back to level 1?
There's no level 0, when the computer overflows and only reads 00000000 instead of the real value it tries to look up in a part of memory used by something else, the computer doesn't know that what is looking at is not a level so it does it best to display as graphics it but is just gibberish when is displayed on screen.
burnsy96 Also, I'm not 100% sure, but if I recall correctly the program will write that 1 it can't write in the level-amount byte somewhere else in the memory, which surely screws everything up.
burnsy96 one solution to integer overflow is to saturate at a maximum value. I'm just taking a shot in the dark, but the code could have included a conditional statement to restrict incrementing the level integer to when it's NOT 255, as a method of saturating at the ceiling of signed 8-bit integers.
Similarly, as counting down beyond 0 for a signed integer will yield the highest value for an n-bit signed integer, one might choose to saturate the value of the integer at 0, but I'm not sure if the terminology is the same(as in, "saturation").
Because it's trying to make level 0
Each bit doubles the amount of numbers it can display so that double each time (2^n)
But one value is zero so the highest it can count to is one less (2^n-1)
Dammit. I hate it when I can already answer the question in the first 5 seconds of video. :(
Binary basically works the same as base ten but you don't get to use is 0,1,2,3,4,5,6,7,8,9
you only get the first two.
Then how can your score be bigger than 255? Do they store that number differently and why can't they do that for the level number?
+rubixman7x7 There was no other reason other than to save storage space. There are 8-bits to a byte of memory. Pac-Man most certainly required more than 1 byte of memory. The 255 explanation in this video is wrong. It was quite frankly, a design decision based solely on the idea that no one could get to that level. To handle a level higher than 255, after all 8-bits are full, the game would only have to store the 255 in 1 byte than move on to the next byte, if that makes sense. In fact, in computing 0 is considered a number and thus the limit is actually 256 numbers despite capping visually at 255. Which means the computer could have considered 0(or 0 0 0 0 0 0 0 0 in binary) as level 1. So even IF the game was limited by the 8-bits/1 byte, they could have easily made a level 256. Take an IP address for example, for each number in the sequence you can put 1-255, but it can also be 0. It's understandable to be confused as the guy explaining it is only considering the processing portion of a computer, and not the storage portion. This is what RAM(Random Access Memory) is. It's a place to store information. This is why the score can get much larger than 255. And why you are absolutely right to assume that they could have gone higher in levels. It simply came down to cost to consumer and design. Pac-Man was created in a time when storage limits were much, much lower for around the same cost. So when it came down to whether or not to tip over from 1 byte to 2 bytes and so on, they really scrutinized as to whether or not it was worth it. So the designers simply said, no one will get that high so we will reserve just 1 byte for level data.
I still sob a little when I think back to 16-bit PCs. Things were so much simpler then. Windows was crap, obviously, but all the DOS/4GW games made it the happiest time of my life. :)
Am I missing something? I can only reply to RUclips content marked Google+?
I love how he explains binary or should I say 0100100100100000011011000110111101110110011001010010000001101000011011110111011100100000011010000110010100100000011001010111100001110000011011000110000101101001011011100111001100100000011000100110100101101110011000010111001001111001
I'm more concerned that it took him 15 years to understand the most basic, fundamental aspect of binary.
haha, that's what i thought... and that i was watching sesame street
Don't be concerned, Dr James is now one of the most highly educated people on our planet, top 1%.
Not only that, James has a PHD in physics, so if he doesn't screw up his life too much he is up for a pretty cosy journey to his deathbed.
You don't need to be concerned :P
The number of bits/bytes used to store a number is a programming decision. The programmer decided 1 byte was enough to store the level. It was a sensible decision, it takes hours to cause PacMAn to malfunction.
but is the first level called lvl 0? There should actually be 256 levels, as level 0 is the first level, and 8bit contains 256 numbers (including 0) Am I wrong?
If one of the other commentors was correct, they used the Level Number (starting with 1) to show how many fruits to display, and when the Level Number is 0, it never knows when to stop printing fruit.
0-255 = 256 total entries. The game starts on level 1, though.
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384.... every next number is 2^(N+1) from the previous... which N starts counting from 0 for the first bit.
Basically using 4 logical gates of on/off can process 0 -15 which is 16 states of data.
A convenient way to process large numbers by using the least possible logic gates.
I don't think this video is very good, I'm sorry to say. First, I think he could have easily gone much deeper into binary arithmetic--the places are all multiples of 2--1, 2, 4, 8, . . . 128, 256. That would have given the viewer a much more interesting understanding of binary.
But second, I don't think he actually explained WHY it ruins the game. I don't know this for sure, but normally the reason it dies is that the programmers made a mistake. They did not think anyone would ever get to 255, so they did not bother checking to make sure it did not go over 255. So when it adds 1 to 255, I will bet you it actually WRITES OVER the next byte over, destroying whatever information is in the bit one to the left of the level byte. That information was important to the program, and when it gets written over it destroys the game.
By the way, this video could have gone much deeper in a very interesting other direction. This issue is exactly how most security problems are exploited by hackers to this day. Programmers make this mistake all the time--forgetting to check "overflows." It frequently messes up the computer just like it did in pacman--when that glitch happens, the hackers then have a doorway to write over whole swaths of code with their own evil code.
This is a "magic" version of binary to explain at the beginning
+Trajan Augustus Why?
+greg55666 It's a family guy reference. Don't worry about it.
+Nota Colt oh, thank you, yes, I certainly won't worry about a Family Guy reference. That's the show written by manatees, right?
+greg55666 yes thats the show produced by politicily incorect manatees.
The glich happens when you hit 256 and is a space issue. if you you are thinking about the score, it is using a multiple of binary code and displays its answer ( dont forget you can add, subtract divide and multiply binary )if you look the score it dosn't go by ones or twos it happens in the hundreds and thousands furthering my point. the space and how much each thing takes obviously plays a role in this but is hard to explain.
It took him 15 years understanding basic binary?
hehe
I'm a computer programmer. '0' is considered whatever state the system designers wants it to be. In electronics terms, there is no Zero state, there are two voltages, and the higher of the two voltages is usually the one used for Zero. So, Zero definitely doesn't mean an 'off state'. As has been mentioned before in this thread by somebody who was correct, you can use '0' in your counter to be the internal number for level '1', and have 65536 levels.
Well, this was a very long way of saying "We get a stack overflow, and that breaks stuff"
I once failed to persuade my friends we'd be better off with binary than decimal. :) In decimal you count to 10 on your fingers, in binary you can count to 1023. :)
The equation for finding the total number of values for any binary number is take the number 2 and raise it to the power equal to the number of bits, represented by x.
For example: For a 4-bit number, let x = 4. The equation is n = 2^x, which equals 16.
A 32-bit number would be 2^32, which is approximately 4.2 billion bits, or 4.2 GB. This explains why 32-bit operating systems cannot utilize more than 4 GB of RAM at a time, and the reason for the move to 64-bit OS's.
There's a trick too: most of these game only display thousands, so they basically add dummy 0s when drawing in the screen. However, you could also have two numbers to represent the score. Supposed we have the score numbers A and B:
1. Both numbers start at 0
2. Each time score A reaches 255, add 1 to score B and reset score A
3. Smart ass converting without exceeding the 8-bit limit to display it on screen.
Well, technically, they were; just not 32-bit integers. 8-bit integers, that we now usually call "char" are just one specific type within the more general integer structure. 16-bit integers and 64-bit integers are other usual types of integers.
Back to the original question, the answer would be that a 8-bit computer's hardware can not count above 255. but using software-side computation, we can expand this limit, theoretically indefinitely; In practice, it's limited by usable memory.
The software programmer handles it. You are given instructions which respond to the carry state of an arithmetic operation. On a 6502, the one I know, you get BCS ( branch on carry set ) meaning you can easily branch out to a subroutine which handles the carry condition. On the Z80, the CPU used for Pacman, you have JP C ( Jump on carry condition ), which is functionally very similar. But both have ADC, meaning you can add, along with the carry, just like with written arithmetic, but on the CPU.
Pretty accurate, although it is 'arithmetic overflow', not 'buffer overflow'. 'Arithmetic overflow' occurs when a carry condition has been met, such as 128+128, whereas buffer overflow occurs when a buffer is asked to take more information than it has space to hold.
If you find that interesting:
Windows Server 2012 (the newest version of the Windows Server OS) is tested and certified to run 4TiB--that's Tebibytes--of RAM (don't ask me where they got 4TiB of RAM or what motherboard they used that supported that much RAM). If you recall that large number from my first comment...18 EiB...that's about 4.7 Million times larger than 4TiB (there's Pebibytes between there too)...It's 1024^2*18/4 times larger (in case you wanted to run that in a calculator).
This is a very good supposition, since you are right, what you propose here is the most likely scenario.
Nobody would program 255 similar levels
Here's what they did:
They in fact designed one level. Beating a level increments the number for the level. Other variables also get changed to ramp the difficulty up.
Because it was only allotted 1 byte of storage, the maximum level is 255 instead of 15.
They did not expect anyone to get there, so they didn't see the need to test it past level 2.
The different variables somehow cause the mapping algorithm to bug out when it returns to level 0 (256).
What actually happens is, the level number increment isn't trapped so following the overflow the software later misses a bounds check which occurs before drawing the fruit on the bottom of the screen. This check now thinks you are on a low level therefore doesn't truncate this number prior to fruit drawing. The software then proceeds directly to a routine made to draw one fruit for every level, which only works between level 1 and 7. On level 0 it wraps and draws 256 fruit overwriting the maze.
Actually the 255 limit is simply the limit of a single math operation. When the number rolls over there is a bit in the ALU of every processor typically called the carry flag. This flag can be used to string multiple math operations together to achieve any number of bits you want to use to represent a number. Additionally with the exception of some of the simplest 8 bit processors, the ALU can do 16-bit addition for computing addresses. This may be done using two 8-bit operations or may be done using dedicated 16-bit adders. Thus most 8 bit CPU can address much more than 256 words of memory. A processor than cannot use more than 256 words would be pretty limited because you need both code and data memory to do anything useful. Some CPUs don't bring all of the address bits out to pins on the chip thus creating an hardware limitation on the amount of memory it can address.
The biggest difference between a computer and a simple calculator is the ability to use logic to extended operations beyond a fixed size representation of values.
No. A variable is just an address that points directly to where that information is stored. The way you define the variable tells the computer how big it's data stack will be. Basically, the instructions for the computer are all in a stack, too, and a pointer tells the computer which instruction is next. When it gets to a variable, it hops out of it's stack of instructions and pulls that variable's stack.
1 slot in a stack = 2 bytes (8 bits). It matters on how you define the variable.
Think about it this way.. You read the number from the RIGHT instead of from the left. The first number means 1, the next number means 2, the third number means 4, the fourth number means 8, the fifth number means 16 and so on. It doubles every time. You write a 1 if you want to add the number, and you write a 0 if you want to skip it. 10010 is 18. Why? I wrote a 1 in the "2-place" and a 1 in the "16-place". I need to add those numbers together. I wrote 0 in the others, so I had to skip them.
Well, if I've understood your query correctly; usually, you have to implement a software solution to accommodate for limitations in the base hardware. Typically, an eight bit video game would reserve six bytes for score. Handling an eight byte score display requires an eight step loop to update it, e.g.:
INIT:
LDA #$30 ; ASCII: '0'.
LDX #$07
LOOP:
STA SCORE,X
DEX
BPL LOOP
RTS
Above resets score table. Then, to update score array; post following....
That actually is true; I once read a few articles on the kill screens of games such as Dig Dug, Galaga, Donkey Kong, and, of course, Pacman. After the game runs out of regular fruits to display, it displays random 2x2 tiles along the bottom of the screen, and then down the right, covering over some of the previously written sprites.
the classic one in iphone app store doesn't have it, at least. but i remember only starting it over and over again, with the same difficulty.
Any mix is possible. Programming is almost infinitely flexible. The programmer can use a mix of 8 bit, 16 bit, and 32 bit variables if they want.
It's a good question.... there's even some dispute at the higher level because whether or not your computing device is 8/16/32/64 bits, etc, can affect sales and marketing. Whereby you do strictly do get 16bits with two bytes, you don't, necessarily, end up with a 16bit number or CPU. So, a 16bit+ CPU is not one which merely combines bytes. 8bit micros can typically handle 16bit numbers using two bytes but they require more than one operation to do it.
That's a neat question. Usually, it uses a variety of Binary Coded Decimal. Often this feature is supported by the CPU, as it is on a 6502 microprocessor, but it can easily be achieved in software too. The process is in fact a little bit difficult to completely explain in one 500 character box, and, there is more than one clear way of doing it.
It doesn't explain how the code thinks and how the bug is created. It's not all about the numbers, it's the FRUIT COUNTER that glitches because of the number that "doesn't exist." It rolls to 0 but 0 rolls back to 255, creating 255 fruits shown primarily in hexadecimal code onscreen. That's basically how it happens in a nutshell.
Good video, one tiny error though - processors don't limit number widths - implementations do. For example, the latest LLVM apparently now supports arbitrary-width integers. That means you could have a uint65536 if you wanted to, even on an 8-bit processor. Performance is another question, though.
That's (probably) part of the reason why your score isn't limited to 255 in Pac-Man.
It's nice to see you agree with me that BCD isn't hard to explain and that it doesn't answer his question despite saying the exact opposite before my reply. The only confusing part is that you're telling me it's irrelevant to his question like I didn't just say that.
actually 2^16 is 65526. 15 bit lines counting up to their maximum hit 65525 and can't continue unless there is a 16th line. a 16 bit processor would actually stop at 131,171 because 2^17 is 131,172, so it can count up to 1 under this because it had 1 less lines than the 17, or the next power :p
... that could access more than 64k of memory. Of course, the way old 16-bit 80x86 processors (or 32-bit 80x86 processors in 16-bit mode) did this was rather confusing and cumbersome, but that's another story. Look up '80x86 memory segmentation' if you're curious.
because each screen of the game was given a binary value in the processor so screen 1 = 00000000 screen 2 = 00000001 all the way to the 255th screen which would be 11111111. Each individual spot in the score works the same way but each one can only go up to 10 so if your score is 1,234,567 the place with the 7 has 10 possibilities (0-9 or 00000000-00001001). So when a spot reaches 9 the game is programed to add one to the next spot (the 6). The issue comes when you run out of number spots.
8 bits will go up to 255, but it can count 256 numbers including 0. What is the 0th level used for; why didn't the pacman game developers just display the binary number + 1 and have 256 levels?
Each byte is a collection of eight bits. The descriptive title is a contraction of the expression "By eight", the arrangement of pathways on an 8bit CPU. Bit is a contraction of "binary digit". So, bytes take binary digits by eights. Hence bits and bytes. And, yes, for each byte, your possibilities multiply by 256. For each bit, they double. This means if you use just one byte for your level count, it's scope is 256.
A lot of people are having revelations with binary.
He kind of explains binary in a simple way, yes, but it's very tedious when you get to the higher values.
Let me explain.
See, if you were to try to figure out, say, 811 with that method, it'd take a little while.
I can say that it's 1100101011 using a simple method.
1100101011 = (1 x 2^9) + (1 x 2^8) + (0 x 2^7) + (0 x 2^6) + (1 x 2^5) + (0 x 2^4) + (1 x 2^3) + (0 x 2^2) + (1 x 2^1) + (1 x 2^0)
= 512 + 256 + 32 + 8 + 2 + 1 = 811
I explain it worse than I intend to. If there were tables, I could actually spend the time writing it all out, but I can't be flopped doing so.
Yup, It's called the 8-bit limit in my mind. I'm a programmer and while it IS the 8-bit limit (255), I can't remember if that's an official term or something I've just said to myself for all these years. Other programmers, do you say 8, 16, 32, 64-bit limit, etc?
Also, for you non-programmers.. this is also why in Nintendo games like Zelda or Mario you can have a maximum of 255 coins. As a kid I saw this all the time in NES games. I always seemed so random yet so many games had it. This is why.