FBD game “2048” per hour
Hello.
This post is devoted to a brief analysis of how to write the simplest toy “2048” on FBD.
Immediately put the picture with the result:
If you are interested in how this is done, welcome under 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 throw off all the tiles of the playing field to one of 4 sides. If, when dropping two tiles of one denomination, they "fly over" one on another, then they stick together into one, the nominal of which is equal to the sum of the joined tiles. After each move on the free section of the field, a new tile with a face value of "2" or "4" appears. If at the touch of a button the location of the tiles or their denomination does not change, then the move is not made.
3. The game ends in defeat, if after the next turn it is impossible to make an action.
As we can see, the rules are extremely simple. We start the implementation of the algorithm.
To solve this problem, we make the “Random” macro. Since There is no pure “random” in the controller, we are following the old and proven path:
We make a macro, the outputs of which will form random coordinates of the cell (row and column) as well as a sign that a quadruple should be placed in this cell.
So, just above, we got random coordinates of the cell, in which we have to put a new value (2 or 4). We translate this value into sixteen logical features using the “Install” macro.
As the name implies, this is the main macro that will display the state of the cell. There are 16 such macros in total. But this is the whole point, that they are all absolutely identical (this was achieved with the help of the removal of value setting algorithms and also separate processing of commands from the user). Thus, the program is quickly and easily remade. when the logic changes, it is enough to change only one macro algorithm, and everything else will change automatically.
This macro is the basis of all the logic implemented in the game.
The macro has two inputs and three outputs. The “Command” input is a logical indication that the macro needs to process 4 input elements and output the output values. The macro is universal and is used to process all four commands. It is made under the “right” command, but in order to process the “left” command, it is enough to input the elements of the string in the reverse order and in the same reverse order pick them up from the output. To process the commands "up" and "down", the corresponding values from different rows are formed at the input, forming a column.
That's all. The main elements of the program are ready. It remains only to link them together. A few words about the remaining auxiliary elements.
We reviewed 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 small 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 square fifteen times and get the finished field. We make several signatures, add the “start” and “Reset” buttons and a large inscription over the “Game over” field.
View of the window in the "drawing" mode.
That's all ready. Run and play.
While drinking coffee for lunch, I thought: “what the fuck?” And decided to redo the processing macro. Remember, I said that the processing of the line takes place in several cycles and this is the weakest point of the whole 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 the condition fulfilled. But on the other hand, this solution (albeit cumbersome 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 the whole thing. Next, under the cut a new macro processing and the general view of the program. You can pay attention to how the macro processing has been simplified (there is not a single feedback) and the mounted crutches from the elements for synchronizing the features that appear in different program execution cycles have become redundant.
Once again, we have made a toy, though useless, but very interesting from the point of view of algorithm implementation. Moreover, I deliberately did not rewrite the post and replace the old macros with new ones in order to show how quickly you can redo the program without affecting the rest. As for the simplicity of writing programs in the FBD language, I think the most eloquent here is the fact that I spent 2-3 times more time writing this post than writing a program.
What remains unrealized.
1. Scoring. I'm not special in this game. Moreover, I played it only at the time of writing this post in my program, and then it was not possible to reach a record of 256. So, making points is easy. Simply in the “Processing” macro, when summing up the values of cells with the same denomination, it is necessary to additionally issue this amount to the macro output, and outside calculate the total amount of these values. But I do not see any point in this, because the goal of the game is “to get the tile with the maximum nominal value”.
2. "Smart" algorithm for selecting a random value, to install a two or four in an empty cell. I wrote a little higher on how this can be done. But since there is nothing interesting there, then we leave it to everyone.
That's all. I hope it was interesting.
This post is devoted to a brief analysis of how to write the simplest toy “2048” on FBD.
Immediately put the picture with the result:
If you are interested in how this is done, welcome under 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 throw off all the tiles of the playing field to one of 4 sides. If, when dropping two tiles of one denomination, they "fly over" one on another, then they stick together into one, the nominal of which is equal to the sum of the joined tiles. After each move on the free section of the field, a new tile with a face value of "2" or "4" appears. If at the touch of a button the location of the tiles or their denomination does not change, then the move is not made.
3. The game ends in defeat, if after the next turn it is impossible to make an action.
As we can see, the rules are extremely simple. We start the implementation of the algorithm.
Random number generator
To solve this problem, we make the “Random” macro. Since There is no pure “random” in the controller, we are following the old and proven path:
We make a macro, the outputs of which will form random coordinates of the cell (row and column) as well as a sign that a quadruple should be placed in this cell.
Random number generator
Short description.
Algorithms 2, 3 and 4 are used to obtain the value constantly changing according to the “saw”. The “Now” algorithm outputs the current time of the controller. Next, divide these two quantities by each other. We take the remainder in the fourth decimal place. We compare with “0.1” (probability 10%) and form the corresponding sign (a sign that we have chosen the four). We take the remainder in the sixth decimal place. Multiply by 16, round down to integers and divide with the remainder by 4. Thus, we get random coordinates of the cell, where the fraction from the division is a row, and the remainder from the division is a column. The unit is 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 the value constantly changing according to the “saw”. The “Now” algorithm outputs the current time of the controller. Next, divide these two quantities by each other. We take the remainder in the fourth decimal place. We compare with “0.1” (probability 10%) and form the corresponding sign (a sign that we have chosen the four). We take the remainder in the sixth decimal place. Multiply by 16, round down to integers and divide with the remainder by 4. Thus, we get random coordinates of the cell, where the fraction from the division is a row, and the remainder from the division is a column. The unit is added so that the values are displayed “beautifully” in the range from 1 to 4. This completes our random number generator.
Macro "Installation"
So, just above, we got random coordinates of the cell, in which we have to put a new value (2 or 4). We translate this value into sixteen logical features using the “Install” macro.
Installation
Short description.
The macro itself is extremely simple and is needed only in order not to litter the main task. There are sixteen algorithms "And" on which three signs are collected according to the logical "And": the sign "work", signaling that it is possible to give a signal to set the cell, and two signs of the coordinates "row" and "column". As soon as all three signs on one of the “And” algorithms have gathered, we give a logical unit to the corresponding output, using which we make an attempt to set a new value to an empty cell.
Short description.
The macro itself is extremely simple and is needed only in order not to litter the main task. There are sixteen algorithms "And" on which three signs are collected according to the logical "And": the sign "work", signaling that it is possible to give a signal to set the cell, and two signs of the coordinates "row" and "column". As soon as all three signs on one of the “And” algorithms have gathered, we give a logical unit to the corresponding output, using which we make an attempt to set a new value to an empty cell.
Macro "Cell"
As the name implies, this is the main macro that will display the state of the cell. There are 16 such macros in total. But this is the whole point, that they are all absolutely identical (this was achieved with the help of the removal of value setting algorithms and also separate processing of commands from the user). Thus, the program is quickly and easily remade. when the logic changes, it is enough to change only one macro algorithm, and everything else will change automatically.
Cell
Short description.
The macro has six inputs and two outputs:
Inputs:
Outputs:
Macro Stuffing:
The basis of the macro is the algorithm "Memory", which stores the current value of the cell. The value written to this algorithm is selected by means of four sequential “Select” algorithms. With the first “Choice” algorithm we check which value should be written into the cell - “two” or “four”. The second “Selection” algorithm checks whether it is an empty cell. If the cell is empty, then we write there the selected deuce or four. The third “Choice” algorithm checks the start of this game or not. If this is the beginning of the game, then the value chosen earlier is written without any checks. The fourth algorithm "Choice" is the highest priority. We check if the sign “Clear” has come, and if it does, then we force the recording to zero by clearing the cell. The algorithm "Comparison" forms a sign of whether this cell is empty or not. Then, using two algorithms "AND" and "OR", we check that if we received the command to install a new random value in the cell and this cell is empty, or it is generally the beginning of the game, then we set a sign that the cell has been processed and the move is completed.
The macro has six inputs and two outputs:
Inputs:
- Established - as we said earlier, this is the input for the logical indication that a new value should be set in this cell.
- The four is a logical sign that a four, not two, must be written in this cell.
- Clear - resets all values in the program to start a new game.
- Go is a sign that the processing of all values after the command is completed and the cell can be rewritten.
- Input is the value after processing the next command to be written to the cell.
- Start is a logical sign that the game has just begun, all cells are empty and the first value can be written to any of them.
Outputs:
- The value is the current value of the cell.
- Done - a sign that the cell has been processed.
Macro Stuffing:
The basis of the macro is the algorithm "Memory", which stores the current value of the cell. The value written to this algorithm is selected by means of four sequential “Select” algorithms. With the first “Choice” algorithm we check which value should be written into the cell - “two” or “four”. The second “Selection” algorithm checks whether it is an empty cell. If the cell is empty, then we write there the selected deuce or four. The third “Choice” algorithm checks the start of this game or not. If this is the beginning of the game, then the value chosen earlier is written without any checks. The fourth algorithm "Choice" is the highest priority. We check if the sign “Clear” has come, and if it does, then we force the recording to zero by clearing the cell. The algorithm "Comparison" forms a sign of whether this cell is empty or not. Then, using two algorithms "AND" and "OR", we check that if we received the command to install a new random value in the cell and this cell is empty, or it is generally the beginning of the game, then we set a sign that the cell has been processed and the move is completed.
Macro "Processing"
This macro is the basis of all the logic implemented in the game.
The macro has two inputs and three outputs. The “Command” input is a logical indication that the macro needs to process 4 input elements and output the output values. The macro is universal and is used to process all four commands. It is made under the “right” command, but in order to process the “left” command, it is enough to input the elements of the string in the reverse order and in the same reverse order pick them up from the output. To process the commands "up" and "down", the corresponding values from different rows are formed at the input, forming a column.
General view and principle of operation
General view of the contents of the macro:
Principle of operation:
At the input are 4 elements and the command to start processing (the command works on the shift of elements from the first to the fourth, that is, the command to the right).
On the leading edge of the command, elements are stored in memory. Next, it is verified that the row of 4 elements does not contain empty cells in the direction of shift. If this check is not performed, then a cyclic shift of all elements, before which an empty cell is found, passes one cell down. The resulting sequence is checked again for the presence of empty cells in the direction of the shift and the cyclic shift of the elements continues until the check is completed.
This is the weakest point of the algorithm. To process a line, you have to run the program three times (in the limit). Due to the fact that the check can be performed during the first pass of the program, and maybe only at the third, and all 16 cells must work at the same time, it is necessary to install a large number of memory elements and triggers in the program. But for the time being, I have not thought of a simple and beautiful way to implement sorting in one pass. But it's not over yet. When there is time, I will work on it more closely and perhaps the whole program will be simplified every two times.
When the check is finally done, and all the elements are arranged in order without gaps, an impulse is formed, which starts a pairwise comparison of the elements, starting from the bottom. Compare the fourth and third elements. If they are equal, then in the fourth cell we write their sum, and all other elements are shifted down one cell. Next, we compare the second and the first elements between us and proceed in a similar way. If the fourth and third elements are not compared with each other, then we compare the third and second elements, and so on. Here the algorithm is simple due to the fact that we have already sorted out all non-zero cells and know for sure that between the filled cells we do not have empty cells. This sorting is done in one pass. At the end, the resulting element values are written to the output and the “Ready” output signal is generated.
At the same time, we need to check that when submitting a command at least one set of elements has changed. Otherwise, this command is not a move and there is nothing to do when submitting it. For this test, there are elements at the bottom of the macro, which at the source sequence check that at least one permutation is needed and at least one pair of cells “collapsed”. In this case, the output signal "worked".
Principle of operation:
At the input are 4 elements and the command to start processing (the command works on the shift of elements from the first to the fourth, that is, the command to the right).
On the leading edge of the command, elements are stored in memory. Next, it is verified that the row of 4 elements does not contain empty cells in the direction of shift. If this check is not performed, then a cyclic shift of all elements, before which an empty cell is found, passes one cell down. The resulting sequence is checked again for the presence of empty cells in the direction of the shift and the cyclic shift of the elements continues until the check is completed.
This is the weakest point of the algorithm. To process a line, you have to run the program three times (in the limit). Due to the fact that the check can be performed during the first pass of the program, and maybe only at the third, and all 16 cells must work at the same time, it is necessary to install a large number of memory elements and triggers in the program. But for the time being, I have not thought of a simple and beautiful way to implement sorting in one pass. But it's not over yet. When there is time, I will work on it more closely and perhaps the whole program will be simplified every two times.
When the check is finally done, and all the elements are arranged in order without gaps, an impulse is formed, which starts a pairwise comparison of the elements, starting from the bottom. Compare the fourth and third elements. If they are equal, then in the fourth cell we write their sum, and all other elements are shifted down one cell. Next, we compare the second and the first elements between us and proceed in a similar way. If the fourth and third elements are not compared with each other, then we compare the third and second elements, and so on. Here the algorithm is simple due to the fact that we have already sorted out all non-zero cells and know for sure that between the filled cells we do not have empty cells. This sorting is done in one pass. At the end, the resulting element values are written to the output and the “Ready” output signal is generated.
At the same time, we need to check that when submitting a command at least one set of elements has changed. Otherwise, this command is not a move and there is nothing to do when submitting it. For this test, there are elements at the bottom of the macro, which at the source sequence check that at least one permutation is needed and at least one pair of cells “collapsed”. In this case, the output signal "worked".
Common words
That's all. The main elements of the program are ready. It remains only to link them together. A few words about the remaining auxiliary elements.
Control block
These are the main controls of the game.
Manual selector, an algorithm that generates outputs according to the “one of n” scheme, serves for giving 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 the user's commands (as I said earlier, it was not possible to do the processing of the command in one cycle, which means that while the command is being processed it is necessary to block the supply of new commands). Experience has shown that the maximum processing time of a command with a cycle time of 5 ms was about 150 ms. And although all processing is carried out in a maximum of 5 cycles (there are two more cycles added “in reserve” at the expense of feedback), which is only 25 ms, the rest of the time is spent on setting a new value in the cell. Indeed, as the field is filled, the chance to get into an empty cell decreases. In the limit, the waiting time can be infinite. Mat. 80 ms wait. A recorded maximum of 150 ms. It is possible to correct a random value ejection algorithm in order to reduce the time spent on the full processing of a move. Since we have only 16 cells, then we can make 16 elements with memorized values from 1 to 16. Next, read the values from the cells of the playing field and the nonzero cells move back, and all the zero with the numbers of their elements leave 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, but I really didn’t like to complicate the already complicated program.
These are the main controls of the game.
Manual selector, an algorithm that generates outputs according to the “one of n” scheme, serves for giving 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 the user's commands (as I said earlier, it was not possible to do the processing of the command in one cycle, which means that while the command is being processed it is necessary to block the supply of new commands). Experience has shown that the maximum processing time of a command with a cycle time of 5 ms was about 150 ms. And although all processing is carried out in a maximum of 5 cycles (there are two more cycles added “in reserve” at the expense of feedback), which is only 25 ms, the rest of the time is spent on setting a new value in the cell. Indeed, as the field is filled, the chance to get into an empty cell decreases. In the limit, the waiting time can be infinite. Mat. 80 ms wait. A recorded maximum of 150 ms. It is possible to correct a random value ejection algorithm in order to reduce the time spent on the full processing of a move. Since we have only 16 cells, then we can make 16 elements with memorized values from 1 to 16. Next, read the values from the cells of the playing field and the nonzero cells move back, and all the zero with the numbers of their elements leave 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, but I really didn’t like to complicate the already complicated program.
Final program:
We reviewed all the elements of the program. Now it’s enough to combine them and everything will work.
Big picture with the final program.
General view of the program. Link to another hosting because the picture is very big.
The picture clearly shows the division of the program into 4 main blocks.
The top 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 top right is the command processing block. Consists of 4 parts Each command ("right", "left", "up" and "down") is processed separately because our macro is universal.
The bottom right is ancillary elements for transforming the order of elements and forming a sign that the game is over (provided that all the fields are occupied and there are no two adjacent cells with the same value).
The picture clearly shows the division of the program into 4 main blocks.
The top 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 top right is the command processing block. Consists of 4 parts Each command ("right", "left", "up" and "down") is processed separately because our macro is universal.
The bottom right is ancillary elements for transforming the order of elements and forming a sign that the game is over (provided that all the fields are occupied and there are no two adjacent cells with the same value).
We attach the graphic part
Well, everything is simple and done in 5 minutes.
We draw one small 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 square fifteen times and get the finished field. We make several signatures, add the “start” and “Reset” buttons and a large inscription over the “Game over” field.
View of the window in the "drawing" mode.
That's all ready. Run and play.
UPD.1
While drinking coffee for lunch, I thought: “what the fuck?” And decided to redo the processing macro. Remember, I said that the processing of the line takes place in several cycles and this is the weakest point of the whole 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 the condition fulfilled. But on the other hand, this solution (albeit cumbersome 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 the whole thing. Next, under the cut a new macro processing and the general view of the program. You can pay attention to how the macro processing has been simplified (there is not a single feedback) and the mounted crutches from the elements for synchronizing the features that appear in different program execution cycles have become redundant.
New Macro Processing
The upper half is sorting the row "in the forehead." All options are simply checked in succession and appropriate permutations are made when the conditions are met. The lower half remained unchanged. Please note that, compared with the previous version, all memory elements and feedbacks have been removed. The “Memory 54 - 57” blocks at the end are actually not needed for the program, since processing takes place in one cycle. Left them solely for the convenience of displaying the values at the output of the macro. Since the cycle time is 5 ms, then without these blocks the real values at the macro output will only skip by 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 "in the forehead." All options are simply checked in succession and appropriate permutations are made when the conditions are met. The lower half remained unchanged. Please note that, compared with the previous version, all memory elements and feedbacks have been removed. The “Memory 54 - 57” blocks at the end are actually not needed for the program, since processing takes place in one cycle. Left them solely for the convenience of displaying the values at the output of the macro. Since the cycle time is 5 ms, then without these blocks the real values at the macro output will only skip by 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 harness (or rather its absence) of the Processing macro. If you look at the previous version of the program, you can see that the output is triggered for each ready signal, the trigger for the general trigger signal, the selection of fronts and resetting these triggers by feedback. Now all this horror becomes unnecessary, and the general view of the program we have turned out clean and not littered with all sorts of crutches. All other elements of the program remained unchanged.
Here you need to pay attention to the harness (or rather its absence) of the Processing macro. If you look at the previous version of the program, you can see that the output is triggered for each ready signal, the trigger for the general trigger signal, the selection of fronts and resetting these triggers by feedback. Now all this horror becomes unnecessary, and the general view of the program we have turned out clean and not littered with all sorts of crutches. All other elements of the program remained unchanged.
Summarizing
Once again, we have made a toy, though useless, but very interesting from the point of view of algorithm implementation. Moreover, I deliberately did not rewrite the post and replace the old macros with new ones in order to show how quickly you can redo the program without affecting the rest. As for the simplicity of writing programs in the FBD language, I think the most eloquent here is the fact that I spent 2-3 times more time writing this post than writing a program.
What remains unrealized.
1. Scoring. I'm not special in this game. Moreover, I played it only at the time of writing this post in my program, and then it was not possible to reach a record of 256. So, making points is easy. Simply in the “Processing” macro, when summing up the values of cells with the same denomination, it is necessary to additionally issue this amount to the macro output, and outside calculate the total amount of these values. But I do not see any point in this, because the goal of the game is “to get the tile with the maximum nominal value”.
2. "Smart" algorithm for selecting a random value, to install a two or four in an empty cell. I wrote a little higher on how this can be done. But since there is nothing interesting there, then we leave it to everyone.
That's all. I hope it was interesting.
Source: https://habr.com/ru/post/277203/
All Articles