The game "2048" on the FBD in an hour
Hello.
This post is devoted to a brief discussion of how to write the simplest toy “2048” on FBD.
Immediately put a picture with the result:
If you are interested in how this is done, welcome to cat.
The game "2048". Rules.
1. In each round, a tile of face value “2” (with a probability of 90%) or “4” (with a probability of 10%) appears.
2. By pressing the arrow, the player can discard all tiles of the playing field in one of 4 sides. If, when dropping, two tiles of the same denomination “fly” one onto the other, then they stick together into one, the denomination of which is equal to the sum of the connected tiles. After each move, a new tile with a face value of “2” or “4” appears on the free section of the field. If, when the button is pressed, the location of the tiles or their denomination does not change, then the move does not occur.
3. The game ends in defeat if, after the next move, it is impossible to complete an action.
As we can see, the rules are extremely simple. We begin the implementation of the algorithm.
To solve this problem, we make the macro "Random". Because there is no pure “random” in the controller, we go the old and tested way:
We make a macro, at the outputs of which random coordinates of the cell (row and column) will be formed, as well as a sign that a four should be placed in this cell.
So, a little higher we got the random coordinates of the cell in which we should put the new value (2 or 4). We convert this value to sixteen logical signs using the "Installation" macro.
As the name implies, this is the main macro that will display us the state of the cell. There are 16 such macros in total. But this is the whole point that they are all exactly the same (this was achieved by removing the algorithms for setting values and also separately processing commands from the user). Thus, the program quickly and easily redone because when changing the logic, it is enough to change only one macro algorithm, and everything else will be changed automatically.
This macro is the basis of all the logic implemented in the game.
A macro has two inputs and three outputs. The “Command” input is a logical sign that the macro needs to process 4 input elements and produce output values. The macro is universal and is used to process all four commands. It is made under the command “to the right,” but to process the command “to the left,” it’s enough to input the line elements in the reverse order and in the same reverse order pick them up from the output. To process the “up” and “down” commands, the corresponding values from different rows, forming a column, are input.
That, in fact, is all. The main elements of the program are ready. It remains only to connect them together. A few words about the rest of the auxiliary elements.
We examined all the elements of the program. Now it’s enough to combine them and everything will work.
Well, everything is simple and done in 5 minutes.
We draw one square. We give it a value equal to the value of the corresponding cell. Change the background color depending on the value of the cell. Next, copy the box fifteen times and get the finished field. We make several signatures, add the “Start” and “Reset” buttons and a large inscription on top of the “Game over” field.
View of the window in the "drawing" mode.
That’s all done. We start and you can play.
While drinking coffee at lunch, I thought: “what the hell?” And decided to redo the processing macro. Remember, I said that line processing takes place in several cycles and this is the weakest point of the entire program. I decided to get rid of this and put all the checks in one sequence. On the one hand, we get extra checks if even at the start we have fulfilled the condition. But on the other hand, this solution (albeit bulky and ugly looking) allows us to get rid of pornography with a bunch of triggers, a bunch of memory cells and the need to synchronize this whole thing. Next, under the cat, a new processing macro and a general view of the program. You can pay attention to how the processing macro has been simplified (there is not a single feedback) and the hinged crutches from the elements have become redundant to synchronize the signs that occur in different cycles of the program.
Once again, we made a toy, even useless, but very interesting from the point of view of the implementation of algorithms. Moreover, I deliberately did not rewrite the post and replace the old macros with new ones to show how you can quickly radically alter the program without affecting the rest of it. As for the simplicity of writing programs in the FBD language, I think the most eloquent here will be the fact that I spent 2-3 times more time writing this post than writing a program.
What remains unrealized.
1. Scoring. I am not special in this game. Moreover, he played it only at the time of writing this post in his program, and so far he did not succeed in reaching a record of 256. So, making scoring is easy. It’s just that in the “Processing” macro, when summing the values of cells with the same nominal value, you need to additionally give this amount to the macro output, and from the outside, calculate the total amount of these values. But I do not see any sense in this, because the goal of the game is to get tiles with the maximum face value.
2. The "smart" algorithm for choosing a random value to set a two or four into an empty cell. I wrote just above how this can be done. But since there is nothing interesting there, then leave it to everyone.
That's all. I hope it was interesting.
This post is devoted to a brief discussion of how to write the simplest toy “2048” on FBD.
Immediately put a picture with the result:
If you are interested in how this is done, welcome to cat.
Initial data
The game "2048". Rules.
1. In each round, a tile of face value “2” (with a probability of 90%) or “4” (with a probability of 10%) appears.
2. By pressing the arrow, the player can discard all tiles of the playing field in one of 4 sides. If, when dropping, two tiles of the same denomination “fly” one onto the other, then they stick together into one, the denomination of which is equal to the sum of the connected tiles. After each move, a new tile with a face value of “2” or “4” appears on the free section of the field. If, when the button is pressed, the location of the tiles or their denomination does not change, then the move does not occur.
3. The game ends in defeat if, after the next move, it is impossible to complete an action.
As we can see, the rules are extremely simple. We begin the implementation of the algorithm.
Random number generator
To solve this problem, we make the macro "Random". Because there is no pure “random” in the controller, we go the old and tested way:
We make a macro, at the outputs of which random coordinates of the cell (row and column) will be formed, as well as a sign that a four should be placed in this cell.
Random number generator
Short description.
Algorithms 2,3 and 4 are used to obtain values that are constantly changing in terms of “saw”. The “Now” algorithm outputs the current controller time. Next, we divide these two quantities into each other. We take the remainder in the fourth decimal place. Compare with "0.1" (10% probability) and form the corresponding sign (sign that the four were chosen). We take the remainder in the sixth decimal place. We multiply by 16, round down to the nearest integer, and divide with the remainder by 4. Thus we get random coordinates of the cell, where the quotient of division is the row and the remainder of division is the column. A unit has been added so that the values are displayed “beautifully” in the range from 1 to 4. This completes our random number generator.
Short description.
Algorithms 2,3 and 4 are used to obtain values that are constantly changing in terms of “saw”. The “Now” algorithm outputs the current controller time. Next, we divide these two quantities into each other. We take the remainder in the fourth decimal place. Compare with "0.1" (10% probability) and form the corresponding sign (sign that the four were chosen). We take the remainder in the sixth decimal place. We multiply by 16, round down to the nearest integer, and divide with the remainder by 4. Thus we get random coordinates of the cell, where the quotient of division is the row and the remainder of division is the column. A unit has been added so that the values are displayed “beautifully” in the range from 1 to 4. This completes our random number generator.
Installation Macro
So, a little higher we got the random coordinates of the cell in which we should put the new value (2 or 4). We convert this value to sixteen logical signs using the "Installation" macro.
Installation
Short description.
The macro itself is extremely simple and is needed only in order not to clutter up the main task. There are sixteen “And” algorithms on which, according to the logical “And”, three signs are collected: the “work” sign, signaling that a signal can be set to set the cell, and two signs of the “row” and “column” coordinates. As soon as all three signs on one of the “I” algorithms are assembled, we issue a logical unit to the corresponding output, by which we try to set a new value in an empty cell.
Short description.
The macro itself is extremely simple and is needed only in order not to clutter up the main task. There are sixteen “And” algorithms on which, according to the logical “And”, three signs are collected: the “work” sign, signaling that a signal can be set to set the cell, and two signs of the “row” and “column” coordinates. As soon as all three signs on one of the “I” algorithms are assembled, we issue a logical unit to the corresponding output, by which we try to set a new value in an empty cell.
Macro "Cell"
As the name implies, this is the main macro that will display us the state of the cell. There are 16 such macros in total. But this is the whole point that they are all exactly the same (this was achieved by removing the algorithms for setting values and also separately processing commands from the user). Thus, the program quickly and easily redone because when changing the logic, it is enough to change only one macro algorithm, and everything else will be changed automatically.
Cell
Short description.
The macro has six inputs and two outputs:
Inputs:
Outputs:
Macro filling:
The macro is based on the “Memory” algorithm, which stores the current value of the cell. The value recorded in this algorithm is selected by means of four consecutive "Selection" algorithms. The first algorithm, “Choice”, we check which value should be written to the cell - “two” or “four”. The secondf Choosing algorithm checks if this is an empty cell. If the cell is empty, then we write there the selected two or four. The third algorithm, "Choice," checks whether this is the beginning of the game or not. If this is the beginning of the game, then without any checks, the previously selected value is written. The fourth algorithm "Choice" is the highest priority. We check if the sign “Clear” has come, and if it has, then forcibly write to memory zero clearing the cell. The “Comparison” algorithm forms a sign whether this cell is empty or not. Next, using the two algorithms “AND” and “OR”, we check
The macro has six inputs and two outputs:
Inputs:
- Set - as we said earlier, this is an input for a logical sign that a new value should be set in this cell.
- Four is a logical sign that a quad should be written in this cell, not a two.
- Clear - resets all values in the program to start a new game.
- Go - a sign that the processing of all values after the command is completed and the cell can be overwritten.
- Input - the value after processing the next command, which must be written to the cell.
- Start - a logical sign that the game has just begun, all cells are empty and you can write the first value to any of them.
Outputs:
- Value is the current value of the cell.
- Done - a sign that cell processing is complete.
Macro filling:
The macro is based on the “Memory” algorithm, which stores the current value of the cell. The value recorded in this algorithm is selected by means of four consecutive "Selection" algorithms. The first algorithm, “Choice”, we check which value should be written to the cell - “two” or “four”. The secondf Choosing algorithm checks if this is an empty cell. If the cell is empty, then we write there the selected two or four. The third algorithm, "Choice," checks whether this is the beginning of the game or not. If this is the beginning of the game, then without any checks, the previously selected value is written. The fourth algorithm "Choice" is the highest priority. We check if the sign “Clear” has come, and if it has, then forcibly write to memory zero clearing the cell. The “Comparison” algorithm forms a sign whether this cell is empty or not. Next, using the two algorithms “AND” and “OR”, we check
Macro Processing
This macro is the basis of all the logic implemented in the game.
A macro has two inputs and three outputs. The “Command” input is a logical sign that the macro needs to process 4 input elements and produce output values. The macro is universal and is used to process all four commands. It is made under the command “to the right,” but to process the command “to the left,” it’s enough to input the line elements in the reverse order and in the same reverse order pick them up from the output. To process the “up” and “down” commands, the corresponding values from different rows, forming a column, are input.
General view and principle of operation
General view of the contents of the macro:
How it works:
4 elements and a command to start processing are fed to the input (the command works to shift elements from the first to the fourth, i.e. the command to the right).
On the leading edge of the command, elements are written into memory. Further, it is checked that the row of 4 elements does not contain empty cells in the direction of shift. If this check is not performed, then there is a cyclic shift of all elements in front of which an empty cell is detected, one cell down. The resulting sequence is again checked for empty cells in the shift direction and the cyclic shift of the elements continues until the check is completed.
This is the weakest point of the algorithm. To process the string, you have to run the program three times (in the limit). Due to the fact that the check can be performed on the first pass of the program, or maybe only on the third, and all 16 cells must work at the same time, you have to put a large number of memory elements and triggers in the program. But so far I haven’t come up with a simple and beautiful way to implement one-pass sorting. But not yet evening. When there is time, I’ll do it more tightly and maybe the whole program will be simplified every two times.
When the verification is finally completed, and all the elements are arranged in order without gaps, an impulse is formed by which a pairwise comparison of the elements is started, starting from the bottom. Compare the fourth and third elements. If they are equal, then in the fourth cell we write down their sum, and we shift all other elements down one cell. Next, we compare the second and first elements with each other and do the same. If the fourth and third elements are not compared with each other, then we compare the third and second elements, etc. Here the algorithm is simple due to the fact that we have already sorted all non-zero cells and know for sure that between the filled cells we do not have empty cells. This sorting is performed in one pass. At the end, the resulting element values are written to the output and the “Finish” output signal is generated.
At the same time, we need to verify that at least one set of elements has changed when giving the command. Otherwise, this command is not a move and you do not need to do anything when submitting it. For this check, there are the elements at the bottom of the macro, which at the original sequence check that at least one permutation is needed and at least one pair of cells is “collapsed”. In this case, the output signal “worked” is formed.
How it works:
4 elements and a command to start processing are fed to the input (the command works to shift elements from the first to the fourth, i.e. the command to the right).
On the leading edge of the command, elements are written into memory. Further, it is checked that the row of 4 elements does not contain empty cells in the direction of shift. If this check is not performed, then there is a cyclic shift of all elements in front of which an empty cell is detected, one cell down. The resulting sequence is again checked for empty cells in the shift direction and the cyclic shift of the elements continues until the check is completed.
This is the weakest point of the algorithm. To process the string, you have to run the program three times (in the limit). Due to the fact that the check can be performed on the first pass of the program, or maybe only on the third, and all 16 cells must work at the same time, you have to put a large number of memory elements and triggers in the program. But so far I haven’t come up with a simple and beautiful way to implement one-pass sorting. But not yet evening. When there is time, I’ll do it more tightly and maybe the whole program will be simplified every two times.
When the verification is finally completed, and all the elements are arranged in order without gaps, an impulse is formed by which a pairwise comparison of the elements is started, starting from the bottom. Compare the fourth and third elements. If they are equal, then in the fourth cell we write down their sum, and we shift all other elements down one cell. Next, we compare the second and first elements with each other and do the same. If the fourth and third elements are not compared with each other, then we compare the third and second elements, etc. Here the algorithm is simple due to the fact that we have already sorted all non-zero cells and know for sure that between the filled cells we do not have empty cells. This sorting is performed in one pass. At the end, the resulting element values are written to the output and the “Finish” output signal is generated.
At the same time, we need to verify that at least one set of elements has changed when giving the command. Otherwise, this command is not a move and you do not need to do anything when submitting it. For this check, there are the elements at the bottom of the macro, which at the original sequence check that at least one permutation is needed and at least one pair of cells is “collapsed”. In this case, the output signal “worked” is formed.
Common words
That, in fact, is all. The main elements of the program are ready. It remains only to connect them together. A few words about the rest of the auxiliary elements.
Control block
These are the main game controls.
The manual selector, an algorithm that generates outputs according to the “one of n” scheme, serves to supply all 6 commands. 1 - “move up” command, 2 - “to the right”, 3 - “down”, 4 - “to the left”, 5 - “start of a new game”, 6 - “reset”.
The block serves to block user commands (as I said earlier, it was not possible to process the command in one cycle, which means that while the command is being processed, it is necessary to block the flow of new commands). Experience has shown that the maximum processing time for a command with a cycle time of 5 ms was about 150 ms. And although all the processing is carried out in a maximum of 5 cycles (there are two more cycles added “in reserve” due to feedbacks), which is only 25 ms, the rest of the time is spent setting a new value in the cell. After all, as the field is filled, the chance to get into an empty cell decreases. In the limit, the waiting time can be infinite. Mat. wait 80 ms. Fixed maximum 150 ms. You can tweak the algorithm for ejecting a random value in order to reduce the time spent on complete processing of the move. Because we have only 16 cells, then you can make 16 elements with stored values from 1 to 16. Next, read the values from the cells of the playing field and move non-zero cells back, and leave all zero with the numbers of their elements at the beginning of the row. Count the number of zero cells and throw out a random number in this range. But this adds a bunch of algorithms, and I really did not want to complicate an already complex program.
These are the main game controls.
The manual selector, an algorithm that generates outputs according to the “one of n” scheme, serves to supply all 6 commands. 1 - “move up” command, 2 - “to the right”, 3 - “down”, 4 - “to the left”, 5 - “start of a new game”, 6 - “reset”.
The block serves to block user commands (as I said earlier, it was not possible to process the command in one cycle, which means that while the command is being processed, it is necessary to block the flow of new commands). Experience has shown that the maximum processing time for a command with a cycle time of 5 ms was about 150 ms. And although all the processing is carried out in a maximum of 5 cycles (there are two more cycles added “in reserve” due to feedbacks), which is only 25 ms, the rest of the time is spent setting a new value in the cell. After all, as the field is filled, the chance to get into an empty cell decreases. In the limit, the waiting time can be infinite. Mat. wait 80 ms. Fixed maximum 150 ms. You can tweak the algorithm for ejecting a random value in order to reduce the time spent on complete processing of the move. Because we have only 16 cells, then you can make 16 elements with stored values from 1 to 16. Next, read the values from the cells of the playing field and move non-zero cells back, and leave all zero with the numbers of their elements at the beginning of the row. Count the number of zero cells and throw out a random number in this range. But this adds a bunch of algorithms, and I really did not want to complicate an already complex program.
The final program:
We examined all the elements of the program. Now it’s enough to combine them and everything will work.
Large drawing with the final program
General view of the program. Link to another hosting because the picture is very large.
The picture clearly shows the division of the program into 4 main blocks.
The upper left is the control unit. There is a selector that forms commands, a random number generator, locks, etc.
The bottom left is a block of cells. There are 16 cells, the value of which is displayed in the graphic part.
The upper right part is a command processing block. Consists of 4 parts since each command ("right", "left", "up" and "down") is processed separately since our macro is universal.
The lower right part is auxiliary elements for transforming the order of elements and forming a sign that the game is over (provided that all fields are occupied and there are no two neighboring cells with the same value).
The lower right part is auxiliary elements for transforming the order of elements and forming a sign that the game is over (provided that all fields are occupied and there are no two neighboring cells with the same value).
We attach the graphic part
Well, everything is simple and done in 5 minutes.
We draw one square. We give it a value equal to the value of the corresponding cell. Change the background color depending on the value of the cell. Next, copy the box fifteen times and get the finished field. We make several signatures, add the “Start” and “Reset” buttons and a large inscription on top of the “Game over” field.
View of the window in the "drawing" mode.
That’s all done. We start and you can play.
UPD.1
While drinking coffee at lunch, I thought: “what the hell?” And decided to redo the processing macro. Remember, I said that line processing takes place in several cycles and this is the weakest point of the entire program. I decided to get rid of this and put all the checks in one sequence. On the one hand, we get extra checks if even at the start we have fulfilled the condition. But on the other hand, this solution (albeit bulky and ugly looking) allows us to get rid of pornography with a bunch of triggers, a bunch of memory cells and the need to synchronize this whole thing. Next, under the cat, a new processing macro and a general view of the program. You can pay attention to how the processing macro has been simplified (there is not a single feedback) and the hinged crutches from the elements have become redundant to synchronize the signs that occur in different cycles of the program.
New Macro Processing
The upper half is sorting the row “on the forehead”. All options are simply checked in a row and, when the conditions are met, appropriate permutations are made. The lower half remained unchanged. Please note that compared to the previous version, all memory elements and feedbacks are removed. The blocks “Memory 54 - 57” at the end are not really needed for the program, because processing takes place in one cycle. I left them solely for the convenience of displaying the values at the macro output. Because Since we have a cycle time of 5 ms, without these blocks the real values at the macro output will skip only for 1 cycle (5 ms, it is almost impossible to notice), and the rest of the time at the outputs will hang "-1".
The upper half is sorting the row “on the forehead”. All options are simply checked in a row and, when the conditions are met, appropriate permutations are made. The lower half remained unchanged. Please note that compared to the previous version, all memory elements and feedbacks are removed. The blocks “Memory 54 - 57” at the end are not really needed for the program, because processing takes place in one cycle. I left them solely for the convenience of displaying the values at the macro output. Because Since we have a cycle time of 5 ms, without these blocks the real values at the macro output will skip only for 1 cycle (5 ms, it is almost impossible to notice), and the rest of the time at the outputs will hang "-1".
New general view of the program
Link to another hosting because the picture is very large.
Here you need to pay attention to the binding (or rather its absence) of the "Processing" macros. If you look at the previous version of the program, you will notice that there is a trigger for each ready signal, a trigger for a common trigger signal, edge detection and feedback reset of these triggers. Now all this horror becomes unnecessary, and the general view of the program turned out to be clean and not littered with all kinds of crutches. All other elements of the program remained unchanged.
Summarizing
Once again, we made a toy, even useless, but very interesting from the point of view of the implementation of algorithms. Moreover, I deliberately did not rewrite the post and replace the old macros with new ones to show how you can quickly radically alter the program without affecting the rest of it. As for the simplicity of writing programs in the FBD language, I think the most eloquent here will be the fact that I spent 2-3 times more time writing this post than writing a program.
What remains unrealized.
1. Scoring. I am not special in this game. Moreover, he played it only at the time of writing this post in his program, and so far he did not succeed in reaching a record of 256. So, making scoring is easy. It’s just that in the “Processing” macro, when summing the values of cells with the same nominal value, you need to additionally give this amount to the macro output, and from the outside, calculate the total amount of these values. But I do not see any sense in this, because the goal of the game is to get tiles with the maximum face value.
2. The "smart" algorithm for choosing a random value to set a two or four into an empty cell. I wrote just above how this can be done. But since there is nothing interesting there, then leave it to everyone.
That's all. I hope it was interesting.