We learn bash-scripts, we write Xonix
I read a couple of weeks ago on the Habré article. Learn to bash-scripts, write Sokoban and thought that I also know bash and can write something, and at the same time learn even better bash. I also thought about it and remembered that I had long wanted to write Xonix, once I played on this game on my old 386th. And so, a few sleepless nights and the script is ready. If you are interested in how it was written, what problems arose, then welcome to habrakat.
The rules of the game Xonix can be found in Wikipedia . But since in the implementation I once played, there were no land opponents, they will not be in my implementation.
When writing, I used many different features of bash and the environment, I’ll focus on the most interesting ones, in my opinion.
')
Since it is immediately clear that the script will turn out great, it is reasonable to use functions. There is nothing difficult about functions in bash. The function is defined as follows.
And it is called like this:
Parameters in the function body are accessed using
will display 5 and 10.
Similar javascript code
habitually displays two times 3.
The second feature is that the function body cannot be empty (as well as any block in bash). This is resolved with a colon. So the stub function will look like this:
Also, when you need to comment out the function body for any reason, instead of
How to display colored characters in the console is well known, it uses the escape sequence
We also need to know the dimensions of the console, they are stored in the variables
Next, you need to suppress the echo output from the user, for this we write
When you need it, we write
Since we need to redraw the field at fixed intervals, and still determine which keys the user pressed, the main loop looks like this:
Here the following points are of interest. The
For realization, we obviously need a two-dimensional array to store the field, as well as arrays of structures, to store, for example, the coordinates and directions of movement of opponents. Unfortunately, in bash, arrays can only be one-dimensional, but that will be enough for us: we just pull out two-dimensional arrays line by line. We do the same with arrays of structures. Also, to avoid tedious checks of the array boundaries, we will add boundary elements along the perimeter of the field. Thus, the field initialization function will look something like this:
I note that there are holes in the array. And also in bash there are associative arrays.
To organize a table of records, you must write an array to a file and read an array from a file. For convenience, we will write each element of the array on a separate line. Then reading the array with the results from the file will look like this:
Short explanation:
The array is also read simply:
Obviously, programs written in bash are slow. At the same time, similar code written in Java or C would be executed instantly. You start to notice time. And there is no optimization. Therefore, it is realistic to feel all the optimization methods that I once studied, but now I’m used to, that the compiler performs them. As: removal of a repeating code from the loop body, rewriting the if-elif-elif-else-fi construct in decreasing order of the probability of fulfilling the condition, etc.
It turned out that the subtask of removing the conquered pieces of the sea is an interesting subtask. First, a simple algorithm was implemented based on the area fill algorithm:
But it was very, very, very slow. After spending two or three hours on optimization, I rewrote it this way and that, I accelerated it two times, I realized that I needed a different approach, and went to sleep. And in the morning on Habré saw the article Counting Objects in a binary image. Part 1 This was what we needed. Immediately implemented the algorithm given there, the time of which was completely satisfactory:
Another interesting subtask was writing a code to reflect enemies from borders. At first I tried to write code with a bunch of checks of various options, but it turned out to be cumbersome and clumsy working. I had to think again.
It is easy to understand that to determine the next position of the enemy, it is necessary to know a piece of the 3x3 field, and that only 2 ^ 8 = 256 options of obstacles around the enemy are possible.
But I don’t want to encode all 256 variants either, so we’ll remember about pattern matching. Note that in some cases the direction of further movement depends only on the key pieces of the border and does not depend on what is in other places, for example:
We introduce the following notation: X - land, _ - sea,? - anything.
Then the configurations above and some others are given by the following pattern:
And that's all, it remains only to write the pattern matching function and come up with a set of templates that completely cover all possible wall variants.
And finally, two funny mistakes that I made while writing the script.
And how many missed dollar icons, spaces - do not count.
The script can be found at http://codepad.org/UfTfcMxj . It is recommended to run in console size 80x25. If you expand to full screen, then on weak computers brakes are possible.
UPD1. If the script is downloaded from codepad.org as raw code, the end of line characters are saved as CRLF. And the script starts to crash at startup. You must either manually insert the text into the file, or set on a dos2unix file.
UPD2. It dawned that the rules in the case of pressing the reverse movement of the key differ. If someone wants to avoid taking life in this case, he can use the tzlom http://codepad.org/slUUrueq habrayuzer patch.
The rules of the game Xonix can be found in Wikipedia . But since in the implementation I once played, there were no land opponents, they will not be in my implementation.
When writing, I used many different features of bash and the environment, I’ll focus on the most interesting ones, in my opinion.
')
Functions
Since it is immediately clear that the script will turn out great, it is reasonable to use functions. There is nothing difficult about functions in bash. The function is defined as follows.
function func() { cmd1 cmd2 ... cmdn } And it is called like this:
func param1 param2 ... paramn Parameters in the function body are accessed using
$1 , $2 , ... You can also declare local variables with local . But there are two features. The first is that the variables have a dynamic scope, rather than the usual static one, that is, the following code i=3 function f() { echo $i } function g() { local i=5 f } function h() { local i=10 f } g h will display 5 and 10.
Similar javascript code
var i = 3; function f() { alert(i); } function g() { var i = 5; f(); } function h() { var i = 10; f(); } g(); h(); habitually displays two times 3.
The second feature is that the function body cannot be empty (as well as any block in bash). This is resolved with a colon. So the stub function will look like this:
function f() { : } Also, when you need to comment out the function body for any reason, instead of
# you can simply write : function f() { : cmd1 : cmd2 : cmd3 } User interaction
How to display colored characters in the console is well known, it uses the escape sequence
"\e[ ; ; m" . The cursor is positioned using the "\e[ ; f" escape sequence. In this case, the count comes from the unit. Two more escape sequences are convenient: "\e[2K" to clear the entire current line, "\e[2J" to clear the entire screen. More details can be found in man console_codes .We also need to know the dimensions of the console, they are stored in the variables
COLUMNS and LINES . But they are only available online, so the first line is to write #!/bin/bash -i Next, you need to suppress the echo output from the user, for this we write
stty -echo When you need it, we write
stty echo Since we need to redraw the field at fixed intervals, and still determine which keys the user pressed, the main loop looks like this:
function runLevel() { local -l key local -i time=0 local -i newTime ... while true; do key="" read -t $TIMEOUT -n 1 key newTime=$((`date +%s` * 100 + (10#`date +%N` / 10000000))) case "$key" in $UP_KEY) playerDY=-1 playerDX=0;; $DOWN_KEY) playerDY=1 playerDX=0;; $LEFT_KEY) playerDX=-1 playerDY=0;; $RIGHT_KEY) playerDX=1 playerDY=0;; $EXIT_KEY) break 3;; "") ;; esac if [[ $((newTime - time)) -ge DELAY ]]; then movePlayer moveOpponents time=newTime fi ... done } Here the following points are of interest. The
-l attribute of the key variable allows you to forget about the fact that the CAPS LOCK key can be pressed, since the value of the variable will always be in lower case. And the expression whose value is assigned to newTime calculates the time with an accuracy of millisecond.Arrays
For realization, we obviously need a two-dimensional array to store the field, as well as arrays of structures, to store, for example, the coordinates and directions of movement of opponents. Unfortunately, in bash, arrays can only be one-dimensional, but that will be enough for us: we just pull out two-dimensional arrays line by line. We do the same with arrays of structures. Also, to avoid tedious checks of the array boundaries, we will add boundary elements along the perimeter of the field. Thus, the field initialization function will look something like this:
function initMap() { local -ii local -ij for ((i = 1; i < MAP_HEIGHT - 1; ++i)); do for ((j = 1; j < MAP_WIDTH - 1; ++j)); do map[i * MAP_WIDTH + j]=$SEA done done for ((i = 0; i < MAP_HEIGHT; ++i)); do map[i * MAP_WIDTH]=$LAND map[i * MAP_WIDTH + MAP_WIDTH - 1]=$LAND done for ((j = 0; j < MAP_WIDTH; ++j)); do map[j]=$LAND map[(MAP_HEIGHT - 1) * MAP_WIDTH + j]=$LAND done } I note that there are holes in the array. And also in bash there are associative arrays.
To organize a table of records, you must write an array to a file and read an array from a file. For convenience, we will write each element of the array on a separate line. Then reading the array with the results from the file will look like this:
function writeTopScores() { (IFS=$'\n'; echo "${topScores[*]}" > "$TOP_SCORES_FILE_NAME") } Short explanation:
${a[*]} means the substitution of all elements of an array. Moreover, if this expression is found in double quotes, then the first character from the IFS variable will be taken as the delimiter.The array is also read simply:
function readTopScores() { topScores=() if [[ -r "$TOP_SCORES_FILE_NAME" ]]; then readarray -t topScores < "$TOP_SCORES_FILE_NAME" fi } Removing reclaimed pieces of the sea
Obviously, programs written in bash are slow. At the same time, similar code written in Java or C would be executed instantly. You start to notice time. And there is no optimization. Therefore, it is realistic to feel all the optimization methods that I once studied, but now I’m used to, that the compiler performs them. As: removal of a repeating code from the loop body, rewriting the if-elif-elif-else-fi construct in decreasing order of the probability of fulfilling the condition, etc.
It turned out that the subtask of removing the conquered pieces of the sea is an interesting subtask. First, a simple algorithm was implemented based on the area fill algorithm:
function deleteFreeAreas() { local -a points local -ii for ((i = 0; i < countOpponents; ++i)); do points[i]=$((opponents[4 * i] * mapWidth + opponents[4 * i + 1])) done local -i countPoints=$countOpponents local -i index while [[ countPoints -ne 0 ]]; do index=$((points[--countPoints])) map[index]=$opponentArea if [[ ${map[index + 1]} == $sea ]]; then points[countPoints++]=$((index + 1)) fi if [[ ${map[index - 1]} == $sea ]]; then points[countPoints++]=$((index - 1)) fi if [[ ${map[index + mapWidth]} == $sea ]]; then points[countPoints++]=$((index + mapWidth)) fi if [[ ${map[index - mapWidth]} == $sea ]]; then points[countPoints++]=$((index - mapWidth)) fi done ... } But it was very, very, very slow. After spending two or three hours on optimization, I rewrote it this way and that, I accelerated it two times, I realized that I needed a different approach, and went to sleep. And in the morning on Habré saw the article Counting Objects in a binary image. Part 1 This was what we needed. Immediately implemented the algorithm given there, the time of which was completely satisfactory:
function deleteFreeAreas() { local -a marks=() local -i mark=MARK_0 ... for ((i = 1; i < MAP_HEIGHT - 1; ++i)); do for ((j = 1; j < MAP_WIDTH - 1; ++j)); do index=$((i * MAP_WIDTH + j)) if [[ ${tracks[index]} ]]; then map[index]=$LAND fi a=${map[index]} b=${map[(i - 1) * MAP_WIDTH + j]} c=${map[i * MAP_WIDTH + j - 1]} if [[ a -eq SEA ]]; then if [[ b -ne LAND && c -ne LAND ]]; then if [[ ${marks[b]} -eq ${marks[c]} ]]; then map[index]=${marks[b]} else d=$(((b < c) ? b : c)) e=$(((b < c) ? c : b)) map[index]=${marks[d]} m=${marks[e]} for ((k = MARK_0; k < mark; ++k)); do if [[ ${marks[k]} -eq m ]]; then marks[k]=${marks[d]} fi done fi elif [[ b -eq LAND && c -eq LAND ]]; then map[index]=$mark marks[mark]=$mark ((++mark)) elif [[ b -ne LAND && c -eq LAND ]]; then map[index]=${marks[b]} elif [[ b -eq LAND && c -ne LAND ]]; then map[index]=${marks[c]} fi fi done done for ((i = 0; i < countOpponents; ++i)); do m=${marks[${map[$(( ${opponents[4 * i]} * MAP_WIDTH + ${opponents[4 * i + 1]}))]}]} for ((j = 0; j < mark; ++j)); do if [[ ${marks[j]} -eq m ]]; then marks[j]=$OPPONENT_AREA fi done done ... } Moving opponents
Another interesting subtask was writing a code to reflect enemies from borders. At first I tried to write code with a bunch of checks of various options, but it turned out to be cumbersome and clumsy working. I had to think again.
It is easy to understand that to determine the next position of the enemy, it is necessary to know a piece of the 3x3 field, and that only 2 ^ 8 = 256 options of obstacles around the enemy are possible.
But I don’t want to encode all 256 variants either, so we’ll remember about pattern matching. Note that in some cases the direction of further movement depends only on the key pieces of the border and does not depend on what is in other places, for example:
_ X _ XXXXX _ _ XX _ 1 _ _ 1 _ _ 1 _ _ 1 _ _ _ 2 _ _ 2 _ _ 2 _ _ 2 We introduce the following notation: X - land, _ - sea,? - anything.
Then the configurations above and some others are given by the following pattern:
? X ? ? o _ ? _ _ And that's all, it remains only to write the pattern matching function and come up with a set of templates that completely cover all possible wall variants.
function compare() { local -r -a pattern=($1) local -r -ax=($2) local -ii for ((i = 0; i < 8; ++i)); do if [[ ${pattern[i]} -ne ANY && ${pattern[i]} -ne ${x[i]} ]]; then return 1 fi done return 0 } rules=( # pattern dy dx "$ANY $SEA $SEA $ANY $SEA $ANY $ANY $ANY" 1 1 "$ANY $LAND $ANY $ANY $SEA $ANY $SEA $SEA" -1 1 "$SEA $SEA $ANY $SEA $LAND $ANY $ANY $ANY" 1 -1 "$ANY $ANY $LAND $ANY $ANY $LAND $ANY $ANY" 0 0 "$ANY $LAND $ANY $ANY $ANY $ANY $LAND $ANY" 0 0 "$ANY $ANY $ANY $LAND $LAND $ANY $ANY $ANY" 0 0 ... "$ANY $LAND $ANY $ANY $ANY $LAND $ANY $LAND" 0 0 ) declare -r -i COUNT_RULES=$((${#rules[*]} / 3)) function findRule() { local -rx=$1 for ((i = 0; i < COUNT_RULES; ++i)); do if compare "${rules[i * 3]}" "$x"; then echo ${rules[i * 3 + 1]} ${rules[i * 3 + 2]} break fi done } function moveOpponents() { local -ii local -iy local -ix local -i dx local -i dy local -a cells local -a rule for ((i = 0; i < countOpponents; ++i)); do y=${opponents[4 * i]} dy=${opponents[4 * i + 2]} x=${opponents[4 * i + 1]} dx=${opponents[4 * i + 3]} clearOpponent $y $x cells[0]=${map[(y + dy) * MAP_WIDTH + x - dx]} cells[1]=${map[(y + dy) * MAP_WIDTH + x]} cells[2]=${map[(y + dy) * MAP_WIDTH + x + dx]} cells[3]=${map[y * MAP_WIDTH + x - dx]} cells[4]=${map[y * MAP_WIDTH + x + dx]} cells[5]=${map[(y - dy) * MAP_WIDTH + x - dx]} cells[6]=${map[(y - dy) * MAP_WIDTH + x]} cells[7]=${map[(y - dy) * MAP_WIDTH + x + dx]} rule=(`findRule "${cells[*]}"`) ((dy *= rule[0])) ((dx *= rule[1])) ((y += dy)) ((x += dx)) opponents[4 * i]=$y opponents[4 * i + 2]=$dy opponents[4 * i + 1]=$x opponents[4 * i + 3]=$dx drawOpponent $y $x done ... } And finally, two funny mistakes that I made while writing the script.
- The variable, which is now called tracks, I first called the PATH. And then I could not understand why the script falls with incomprehensible errors.
- Line
readarray -t topScores < "$TOP_SCORES_FILE_NAME"
I first wrote ascat "$TOP_SCORES_FILE_NAME" | readarray -t topScores
Although I knew, I knew that the pipeline was being executed in a separate process with all the consequences.
And how many missed dollar icons, spaces - do not count.
The script can be found at http://codepad.org/UfTfcMxj . It is recommended to run in console size 80x25. If you expand to full screen, then on weak computers brakes are possible.
UPD1. If the script is downloaded from codepad.org as raw code, the end of line characters are saved as CRLF. And the script starts to crash at startup. You must either manually insert the text into the file, or set on a dos2unix file.
UPD2. It dawned that the rules in the case of pressing the reverse movement of the key differ. If someone wants to avoid taking life in this case, he can use the tzlom http://codepad.org/slUUrueq habrayuzer patch.
Source: https://habr.com/ru/post/122029/
All Articles