Tetris for DCPU-16
As already mentioned on Habré , the developer of widely known in narrow circles of Minecraft 'and Marcus “Notch” Persson is currently busy developing a new game, which will take place in space in 281,474,976,712,644.
Like Minecraft, the game will be nonstandard: the main "chip" is a fully emulated processor, under which spacecraft will surf the Bolshoi ... er, the Universe. Since the characters of the game in the year 0x10 C (the game, in fact, is called so) got straight from 1980, the DCPU-16 processor in its characteristics roughly corresponds to that era: 128 kilobytes of RAM, 100 kilohertz, a simple set of commands.
Despite the fact that the game is still in a very early stage of development, the specification of the processor is already available for review - and communities are already being formed, whose members are developing a lot of interesting pieces for a nonexistent platform. Your humble servant is among these people, and in this post I want to talk about one of these things: the implementation of Tetris for DCPU-16 .
')
(and immediately a disclaimer: the music in the video is imposed separately for artistic, so to speak, expressiveness; DCPU doesn’t allow sound output, so far)
So what does the specification say? The fact that the processor will be 16-bit (you can forget about the bytes - only double-byte words are addressed), we have 12 registers (3 of them are SP , PC and O are of the service type), exactly 65536 words of memory (that is, 128 kilobytes), 15 basic and 1 additional opcode, instructions take from 1 to 3 words, all this will be emulated with a frequency of about 100 thousand cycles per second (the number of cycles depends on the opcode and whether “big literals” are used as operands ).
Basic opcodes are simple - assignment, arithmetic (fractional numbers are represented only with fixed accuracy, 16 bits after the comma - they fall into the overflow register, O ), bit operations, condition checks. No transitions, note: they are done by directly assigning values to the PC register (as you might guess, it indicates the instruction that will be executed next). Condition checks simply skip the next instruction if the condition is not met — conditional jumps are made by combining the check and the regular jump. The only non-base opcode is to call subprocedures, puts the return address on the top of the stack and makes the transition to the specified address.
With operands it is interesting: in addition to regular registers, memory at a given address, memory at an address + register value and directly specified values, there are special values POP , PEEK and PUSH (yes - these are not operations, but operands!), Which firstly allow you to access to the top of the stack (generally speaking, it is impossible to directly access the memory pointed to by the service register), and, secondly, to reduce or increase the SP value by one. As a result, using SET PUSH, X, you can put the value in the stack, SET X, POP - pick it up from there, and SET X, PEEK - copy the value without taking it from the stack. True, strange constructions like SET X, PUSH ; SET POP, X and even SET POP, PUSH . To understand what they are doing is no longer very trivial.
Finally, about the memory. The stack mentioned above has already been mentioned - since during initialization all registers are 0, it starts with 0xFFFF (the first PUSH will first decrease SP by one, and then write down the value) and grows down. In addition, it became known that the video buffer is located at 0x8000 address - the display contains 12 lines of 32 characters each, they are stored in memory line by line, each word corresponds to one character. However, unfortunately, only 7 low bits of 16 bits went to the symbol code (it will be necessary to distort very much to provide Cyrillic support) - the 8th bit is responsible for the blinking, the next 4 - for the background color and the oldest 4 - for the color of the symbol. Colors 16, used palette CGA (RGBI) .
In addition to accessing the display, there is also the ability to read characters from the keyboard: this is the purpose of the circular buffer at 0x9000, 16 bytes in size. In order for the buffer to work, you need to store a pointer to the next character — as soon as the value in memory becomes nonzero, it must be counted, write 0 and increment the pointer to 1 (when reaching 0x9010, reset it to 0x9000). Notch gave his own example illustrating all this.
Finally, according to the latest data, you can set your own character set for display - it is located at 0x8180 (immediately after the video buffer), each word describes one letter of 4x8 pixels, each byte corresponds to one column.
The DCPU-16 device is pretty straightforward, and its performance is low - so I decided to write an online JavaScript emulator for it. Of course, in this idea I was not alone - now there is already a huge pile of such emulators, but what kind of abnormal programmer did it stop?
The result was such a thing:
http://dcpu.ru/
Actually, this is not just an emulator, but a “three in one” shampoo - an assembler, an emulator, and in the appendage a disassembler. Able to almost all of the above, except for its own table of characters. But when debugging, the current line is beautifully highlighted, and when assembling, it is able to do such a funny thing as the calculation of expressions. I think to fasten more macros, in the assembler from Notch it is.
Well, not about him. I finish the lyrical digressions, turn to the topic of the article.
As everyone knows, Tetris was invented by Alexey Pajitnov in 1984. The creator is our compatriot, the game was created practically for computers of the same level as DCPU-16 - what could be better suited for implementation?
Briefly about the code. I didn’t know about the possibility of redefining characters, so I decided to draw with ordinary characters: two filled spaces in a row - one cell. Each figure (in any of 4 turns) can be inscribed in a square of 4x4 cells, all of the figures are 7 - a total of 28 states of 16 words each (I decided to store directly the codes that will be recorded on the screen, but double them only when outputting). All this is piled up at the end of the program.
Wrote several sub-procedures. For example, to display lines on the screen (there are few of them, “Score:”, “Level:”, “GAME OVER”), to read a character from the keyboard, or here’s a pseudo-random number generator:
In general, the standard implementation of the linear congruential method (LCG) . The prime number 10061 took at random - ready to accept the amendment, if someone has the best candidate. In any case, we don’t have any cryptography here, we don’t need to take care of special “randomness”. It seems to throw out different figures, and thank God. The initial rand_seed seed is initialized as follows: when started in a loop, the value increases until the user presses a key. They say that in the old games "Press any key" was also for this purpose, by the way.
Finally, the most cunning sub-procedure that can erase a figure from the screen, and draw it, and check the possibility of its placement:
As you can see, all checks are done directly “on the spot” - in the video buffer. This, of course, has a small negative effect - when the figure is displaced, you must first erase it, then try to put it in a new place and, if it could not be done, draw it again on the old one. Due to erasing, a slight flashing occurs, but the speed of the work is sufficient to make it inconspicuous. Actually, before the figure moves one cell down, it has time to work about 2500 iterations (each one checks the presence of a key in the buffer and the figure rotates or shifts left / right) at the first level, 2000 at the second, 1500 at the third - and so on.
I mentioned the most nested cycle, but it is wrapped in two more - if the figure can no longer be moved down by gravity, a check is made for the presence of completely filled rows, they are destroyed, a new figure is selected (in fact, it is selected in advance and drawn in the “Next:” field, and here the choice is made “one step ahead”) and rushes into the glass from above. If you fail to quit, the outer loop is completed, and a beautiful flashing “Game Over” is drawn.
Verification of the filled rows comes from the bottom up, two pointers to the current “writeable” and current “readable” lines are used. First, the “readable” rises until it reaches the very top or meets the empty row. Then, from the “readable” line, the cells are copied into the “writeable” line and both go up one line higher. A pair of optimizations: copying does not occur if both pointers correspond to one line, attempts to raise the “readable” line are stopped if it is already at the very top or if the number of already deleted lines equals 4 (it is impossible to destroy at a time more). As a result, it works pretty fast, you can live.
Fully available source code here to launch it - find the button " Run in the emulator ", and already there - the button " Run ".
PS Yes, I can not help but brag - Notch himself positively assessed the result of all the above efforts :)
Like Minecraft, the game will be nonstandard: the main "chip" is a fully emulated processor, under which spacecraft will surf the Bolshoi ... er, the Universe. Since the characters of the game in the year 0x10 C (the game, in fact, is called so) got straight from 1980, the DCPU-16 processor in its characteristics roughly corresponds to that era: 128 kilobytes of RAM, 100 kilohertz, a simple set of commands.
Despite the fact that the game is still in a very early stage of development, the specification of the processor is already available for review - and communities are already being formed, whose members are developing a lot of interesting pieces for a nonexistent platform. Your humble servant is among these people, and in this post I want to talk about one of these things: the implementation of Tetris for DCPU-16 .
')
(and immediately a disclaimer: the music in the video is imposed separately for artistic, so to speak, expressiveness; DCPU doesn’t allow sound output, so far)
Details about the "internals" DCPU-16
So what does the specification say? The fact that the processor will be 16-bit (you can forget about the bytes - only double-byte words are addressed), we have 12 registers (3 of them are SP , PC and O are of the service type), exactly 65536 words of memory (that is, 128 kilobytes), 15 basic and 1 additional opcode, instructions take from 1 to 3 words, all this will be emulated with a frequency of about 100 thousand cycles per second (the number of cycles depends on the opcode and whether “big literals” are used as operands ).
Basic opcodes are simple - assignment, arithmetic (fractional numbers are represented only with fixed accuracy, 16 bits after the comma - they fall into the overflow register, O ), bit operations, condition checks. No transitions, note: they are done by directly assigning values to the PC register (as you might guess, it indicates the instruction that will be executed next). Condition checks simply skip the next instruction if the condition is not met — conditional jumps are made by combining the check and the regular jump. The only non-base opcode is to call subprocedures, puts the return address on the top of the stack and makes the transition to the specified address.
With operands it is interesting: in addition to regular registers, memory at a given address, memory at an address + register value and directly specified values, there are special values POP , PEEK and PUSH (yes - these are not operations, but operands!), Which firstly allow you to access to the top of the stack (generally speaking, it is impossible to directly access the memory pointed to by the service register), and, secondly, to reduce or increase the SP value by one. As a result, using SET PUSH, X, you can put the value in the stack, SET X, POP - pick it up from there, and SET X, PEEK - copy the value without taking it from the stack. True, strange constructions like SET X, PUSH ; SET POP, X and even SET POP, PUSH . To understand what they are doing is no longer very trivial.
Finally, about the memory. The stack mentioned above has already been mentioned - since during initialization all registers are 0, it starts with 0xFFFF (the first PUSH will first decrease SP by one, and then write down the value) and grows down. In addition, it became known that the video buffer is located at 0x8000 address - the display contains 12 lines of 32 characters each, they are stored in memory line by line, each word corresponds to one character. However, unfortunately, only 7 low bits of 16 bits went to the symbol code (it will be necessary to distort very much to provide Cyrillic support) - the 8th bit is responsible for the blinking, the next 4 - for the background color and the oldest 4 - for the color of the symbol. Colors 16, used palette CGA (RGBI) .
In addition to accessing the display, there is also the ability to read characters from the keyboard: this is the purpose of the circular buffer at 0x9000, 16 bytes in size. In order for the buffer to work, you need to store a pointer to the next character — as soon as the value in memory becomes nonzero, it must be counted, write 0 and increment the pointer to 1 (when reaching 0x9010, reset it to 0x9000). Notch gave his own example illustrating all this.
Finally, according to the latest data, you can set your own character set for display - it is located at 0x8180 (immediately after the video buffer), each word describes one letter of 4x8 pixels, each byte corresponds to one column.
Javascript emulator
The DCPU-16 device is pretty straightforward, and its performance is low - so I decided to write an online JavaScript emulator for it. Of course, in this idea I was not alone - now there is already a huge pile of such emulators, but what kind of abnormal programmer did it stop?
The result was such a thing:
http://dcpu.ru/
Actually, this is not just an emulator, but a “three in one” shampoo - an assembler, an emulator, and in the appendage a disassembler. Able to almost all of the above, except for its own table of characters. But when debugging, the current line is beautifully highlighted, and when assembling, it is able to do such a funny thing as the calculation of expressions. I think to fasten more macros, in the assembler from Notch it is.
Well, not about him. I finish the lyrical digressions, turn to the topic of the article.
Tetris
As everyone knows, Tetris was invented by Alexey Pajitnov in 1984. The creator is our compatriot, the game was created practically for computers of the same level as DCPU-16 - what could be better suited for implementation?
Briefly about the code. I didn’t know about the possibility of redefining characters, so I decided to draw with ordinary characters: two filled spaces in a row - one cell. Each figure (in any of 4 turns) can be inscribed in a square of 4x4 cells, all of the figures are 7 - a total of 28 states of 16 words each (I decided to store directly the codes that will be recorded on the screen, but double them only when outputting). All this is piled up at the end of the program.
Wrote several sub-procedures. For example, to display lines on the screen (there are few of them, “Score:”, “Level:”, “GAME OVER”), to read a character from the keyboard, or here’s a pseudo-random number generator:
:next_rand ; takes no arguments, returns random word in A MUL [rand_seed], 10061 ADD [rand_seed], 1 SET A, [rand_seed] SET PC, POP :rand_seed DAT 0xC00F In general, the standard implementation of the linear congruential method (LCG) . The prime number 10061 took at random - ready to accept the amendment, if someone has the best candidate. In any case, we don’t have any cryptography here, we don’t need to take care of special “randomness”. It seems to throw out different figures, and thank God. The initial rand_seed seed is initialized as follows: when started in a loop, the value increases until the user presses a key. They say that in the old games "Press any key" was also for this purpose, by the way.
Finally, the most cunning sub-procedure that can erase a figure from the screen, and draw it, and check the possibility of its placement:
:show_cur_piece ; display/clear/check current piece (A=0 - clear, A=1 - display, A=2 - check), if A=2 doesn't actually place anything, return B=1 is position is valid, 0 otherwise SET X, [piece_pos] ; place block at [X] (display) SET Y, [cur_piece] ; ...from [Y] (pieces array) SHL Y, 2 BOR Y, [cur_rot] SHL Y, 4 ADD Y, pieces SET I, 0 ; index :piece_cyc1 SET B, [Y] IFE B, 0 SET PC, piece_jmp1 IFG 2, A SET PC, piece_jmp2 IFG X, 0x8000 + 32*12 ADD PC, 3 IFE [X], 0 SET PC, piece_jmp1 SET B, 0 SET PC, POP :piece_jmp2 IFE A, 0 SET B, 0 SET [X], B SET [X + 1], B :piece_jmp1 ADD I, 1 ADD X, 2 ADD Y, 1 SET B, 1 IFE I, 16 SET PC, POP IFB I, 3 SET PC, piece_cyc1 ADD X, 32 - 8 SET PC, piece_cyc1 As you can see, all checks are done directly “on the spot” - in the video buffer. This, of course, has a small negative effect - when the figure is displaced, you must first erase it, then try to put it in a new place and, if it could not be done, draw it again on the old one. Due to erasing, a slight flashing occurs, but the speed of the work is sufficient to make it inconspicuous. Actually, before the figure moves one cell down, it has time to work about 2500 iterations (each one checks the presence of a key in the buffer and the figure rotates or shifts left / right) at the first level, 2000 at the second, 1500 at the third - and so on.
I mentioned the most nested cycle, but it is wrapped in two more - if the figure can no longer be moved down by gravity, a check is made for the presence of completely filled rows, they are destroyed, a new figure is selected (in fact, it is selected in advance and drawn in the “Next:” field, and here the choice is made “one step ahead”) and rushes into the glass from above. If you fail to quit, the outer loop is completed, and a beautiful flashing “Game Over” is drawn.
Verification of the filled rows comes from the bottom up, two pointers to the current “writeable” and current “readable” lines are used. First, the “readable” rises until it reaches the very top or meets the empty row. Then, from the “readable” line, the cells are copied into the “writeable” line and both go up one line higher. A pair of optimizations: copying does not occur if both pointers correspond to one line, attempts to raise the “readable” line are stopped if it is already at the very top or if the number of already deleted lines equals 4 (it is impossible to destroy at a time more). As a result, it works pretty fast, you can live.
:scan_lines ; search for complete lines, remove them and move all other down; update score & level SET A, 0x8000 + 32*11 + 11 ; start of next line to fill SET B, A ; start of next line to check SET J, 0 ; num of lines skipped :scan_cyc2 SET I, 0 ; horizontal index SET X, B :scan_cyc1 IFE [X], 0 SET PC, scan_jmp1 ADD X, 2 ADD I, 1 IFG 10, I SET PC, scan_cyc1 ADD J, 1 ; no gaps found, increase num of complete rows SUB B, 32 IFE J, 4 SET PC, scan_jmp1 IFG B, 0x8000 SET PC, scan_cyc2 :scan_jmp1 ; found a gap, or no more gaps can be found IFE A, B SET PC, scan_jmp2 ; no need to move anything, continue SET I, 0 :scan_cyc3 SET [A], [B] ADD I, 1 ADD A, 1 ADD B, 1 IFG 20, I SET PC, scan_cyc3 SUB A, 20 SUB B, 20 :scan_jmp2 SUB A, 32 IFG 0x8000, A SET PC, scan_end SUB B, 32 IFE J, 4 SET PC, scan_jmp1 IFG 0x8000, B SET PC, scan_jmp1 SET PC, scan_cyc2 :scan_end IFE J, 0 SET PC, POP ADD [lines], J SET J, [lines_score + J] MUL J, [level] ADD [score], J JSR update_score IFG 10, [lines] SET PC, POP SET [lines], 0 ADD [level], 1 JSR update_level SET PC, POP Fully available source code here to launch it - find the button " Run in the emulator ", and already there - the button " Run ".
Links
- Official game site
- Official DCPU-16 Specification
- Podreddit dedicated to the game 0x10 C , and also dedicated to the DCPU-16
- The official forum dedicated to the game
- Wiki dedicated to the game
- Catalog of assemblers, emulators, disassemblers and other tools
- Catalog of programs for DCPU-16
- My emulator / assembler / disassembler DCPU-16
- The source of my "Tetris" for DCPU-16
PS Yes, I can not help but brag - Notch himself positively assessed the result of all the above efforts :)
Source: https://habr.com/ru/post/142539/
All Articles