Прочитал я пару недель назад на хабре статью Учим bash-скрипты, пишем Sokoban и подумал, что тоже знаю bash и могу что-нибудь написать, а заодно ещё лучше узнать bash. Подумал ещё и вспомнил, что давно хотел написать Xonix, когда-то этой игрой заигрывался на своём старом 386-м. И вот, несколько бессонных ночей и скрипт готов. Если интересно как это писалось, какие проблемы возникали, то добро пожаловать под хабракат.
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/ad6/a4f/463/ad6a4f4638347221ffd403097694fc90.png)
Правила игры Xonix можно прочитать в Википедии. Но так как в реализации, в которую я когда-то играл, не было сухопутных противников, то и в моей реализации их не будет.
При написании использовалось много различных возможностей bash и окружения, остановлюсь на наиболее интересных, на мой взгляд.
Так как сразу понятно что скрипт получится большим, то разумно использовать функции. Ничего сложного в функциях в bash нет. Определяется функция следующим образом.
А вызывается так:
Доступ к параметрам в теле функции осуществляется с помощью
выведет 5 и 10.
Аналогичный же код на JavaScript
привычно выведет два раза 3.
Вторая особенность заключается в том, что тело функции не может быть пустым (впрочем как и любой блок в bash). Это решается с помощью двоеточия. Так что функция-заглушка будет выглядеть так:
Также когда нужно по каким-либо причинам закомментировать тело функции, можно вместо
О том как выводить цветные символы в консоль хорошо известно, для этого используется escape-последовательность
Также нам нужно знать размеры консоли, они хранятся в переменных
Далее, нужно подавить эхо-вывод от пользователя, для этого пишем
Когда он понадобится, пишем
Так как нам нужно через фиксированные промежутки времени перерисовывать поле, и при этом ещё определять, какие клавиши нажал пользователь, то основной цикл выглядит примерно так:
Тут интерес представляют следующие моменты. Атрибут
Для реализации нам, очевидно, нужен двухмерный массив, чтобы хранить поле, а также массивы структур, чтобы хранить, например, координаты и направления движения противников. К сожалению, в bash массивы могут быть только одномерными, но нам этого будет достаточно: просто вытягиваем двухмерные массивы построчно. Аналогично поступаем с массивами структур. Также чтобы избежать утомительных проверок границ массивов, по периметру поля добавим граничные элементы. Таким образом, функция инициализации поля будет выглядеть примерно так:
Отмечу, что в массиве возможны дырки. А также в bash существуют ассоциативные массивы.
Для организации таблицы рекордов необходимо записывать массив в файл и читать массив из файла. Для удобства будем записывать каждый элемент массива в отдельной строке. Тогда чтение массива с результатами из файла будет выглядеть так:
Короткое пояснение:
Читается же массив также просто:
Очевидно, что программы, написанные на bash, работают медленно. При этом аналогичный код, написанный на Java или на C, выполнялся бы мгновенно. Начинаешь замечать время. А ещё нет оптимизации. Поэтому реально пощупать всякие методы оптимизации, которые когда-то изучал, а сейчас привык, что их выполняет компилятор. Как то: вынос повторяющегося кода из тела цикла, переписывание конструкции if-elif-elif-else-fi в порядке убывания вероятности выполнения условия и т. д.
Оказалось, что подзадача удаления отвоёванных кусков моря, является интересной подзадачей. Сначала, был реализован простой алгоритм на основе алгоритма заполнения области:
Но это было очень-очень-очень медленно. Потратив два или три часа на оптимизацию, переписывал и так и этак, ускорил раза в два, понял, что нужен другой подход, и лёг спать. А на утро на хабре увидел статью Подсчет объектов на бинарном изображении. Часть 1 Это было то, что надо. Сразу же реализовал приведённый там алгоритм, время которого вполне устроило:
Ещё одной интересной подзадачей, было написание кода отражения врагов от границ. Сначала я попытался написать код с кучей проверок различных вариантов, но он получился громоздким и коряво работающим. Пришлось снова задуматься.
Несложно понять, что для определения следующего положения противника необходимо знать кусочек поля размером 3x3, и что возможно всего 2^8 = 256 вариантов препятствий вокруг противника.
Но кодировать все 256 вариантов тоже не хочется, поэтому вспоминаем про сопоставление с шаблоном. Заметим, что в некоторых случаях направление дальнейшего движения зависит только от ключевых кусков границы и не зависит от того, что находится в остальных местах, например:
Введём обозначения: X — суша, _ — море,? — всё что угодно.
Тогда приведённые выше конфигурации и некоторые другие задаются следующим шаблоном:
И всё, осталось только написать функцию сопоставления с шаблоном и придумать набор шаблонов, полностью покрывающих все возможные варианты стен.
Ну и напоследок две забавные ошибки, которые я допустил пока писал скрипт.
А сколько было пропущенных значков доллара, пробелов — не счесть.
Скрипт можно найти по ссылке http://codepad.org/UfTfcMxj. Рекомендуется запускать в консоли размером 80x25. Если развернуть на весь экран, то на слабых компах возможны тормоза.
UPD1. Если скрипт скачивать с codepad.org как raw code, то символы конца строки сохраняются как CRLF. И скрипт при запуске начинает сыпаться ошибками. Следует либо вручную вставить текст в файл, либо натравить на файл dos2unix.
UPD2. Выснилось, что правила в случае нажатия на клавишу обратную движению разнятся. Если кто-то хочет, чтобы отнимания жизни в этом случае не было, то может воспользоваться патчем хабраюзера tzlom http://codepad.org/slUUrueq.
![](https://habrastorage.org/getpro/habr/post_images/ad6/a4f/463/ad6a4f4638347221ffd403097694fc90.png)
Правила игры Xonix можно прочитать в Википедии. Но так как в реализации, в которую я когда-то играл, не было сухопутных противников, то и в моей реализации их не будет.
При написании использовалось много различных возможностей bash и окружения, остановлюсь на наиболее интересных, на мой взгляд.
Функции
Так как сразу понятно что скрипт получится большим, то разумно использовать функции. Ничего сложного в функциях в bash нет. Определяется функция следующим образом.
function func() {
cmd1
cmd2
...
cmdn
}
А вызывается так:
func param1 param2 ... paramn
Доступ к параметрам в теле функции осуществляется с помощью
$1
, $2
,… Также можно объявлять локальные переменные с помощью local
. Но есть две особенности. Первая заключается в том, что у переменных динамическая область видимости, а не привычная статическая, то есть следующий кодi=3
function f() {
echo $i
}
function g() {
local i=5
f
}
function h() {
local i=10
f
}
g
h
выведет 5 и 10.
Аналогичный же код на JavaScript
var i = 3;
function f() {
alert(i);
}
function g() {
var i = 5;
f();
}
function h() {
var i = 10;
f();
}
g();
h();
привычно выведет два раза 3.
Вторая особенность заключается в том, что тело функции не может быть пустым (впрочем как и любой блок в bash). Это решается с помощью двоеточия. Так что функция-заглушка будет выглядеть так:
function f() {
:
}
Также когда нужно по каким-либо причинам закомментировать тело функции, можно вместо
#
просто написать :
.function f() {
: cmd1
: cmd2
: cmd3
}
Взаимодействие с пользователем
О том как выводить цветные символы в консоль хорошо известно, для этого используется escape-последовательность
"\e[число;число;числоm"
. Курсор позиционируется с помощью escape-последовательности "\e[строка;столбецf"
. При этом отсчёт идёт с единицы. Удобны ещё две escape-последовательности: "\e[2K"
— очистить всю текущую строку, "\e[2J"
— очистить весь экран. Более подробно можно прочитать в man console_codes
.Также нам нужно знать размеры консоли, они хранятся в переменных
COLUMNS
и LINES
. Но они доступны только в интерактивном режиме, поэтому в первой строке стоит написать#!/bin/bash -i
Далее, нужно подавить эхо-вывод от пользователя, для этого пишем
stty -echo
Когда он понадобится, пишем
stty echo
Так как нам нужно через фиксированные промежутки времени перерисовывать поле, и при этом ещё определять, какие клавиши нажал пользователь, то основной цикл выглядит примерно так:
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
}
Тут интерес представляют следующие моменты. Атрибут
-l
у переменной key
позволяет забыть про то, что может быть нажата клавиша CAPS LOCK, так как значение переменной всегда будет в нижнем регистре. А выражение, значение которого присваивается newTime, вычисляет время с точностью до миллисекунды.Массивы
Для реализации нам, очевидно, нужен двухмерный массив, чтобы хранить поле, а также массивы структур, чтобы хранить, например, координаты и направления движения противников. К сожалению, в bash массивы могут быть только одномерными, но нам этого будет достаточно: просто вытягиваем двухмерные массивы построчно. Аналогично поступаем с массивами структур. Также чтобы избежать утомительных проверок границ массивов, по периметру поля добавим граничные элементы. Таким образом, функция инициализации поля будет выглядеть примерно так:
function initMap() {
local -i i
local -i j
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
}
Отмечу, что в массиве возможны дырки. А также в bash существуют ассоциативные массивы.
Для организации таблицы рекордов необходимо записывать массив в файл и читать массив из файла. Для удобства будем записывать каждый элемент массива в отдельной строке. Тогда чтение массива с результатами из файла будет выглядеть так:
function writeTopScores() {
(IFS=$'\n'; echo "${topScores[*]}" > "$TOP_SCORES_FILE_NAME")
}
Короткое пояснение:
${a[*]}
означает подстановку всех элементов массива. При этом если это выражение встречается в двойных кавычках, то в качестве разделителя будет взят первый символ из переменной IFS
.Читается же массив также просто:
function readTopScores() {
topScores=()
if [[ -r "$TOP_SCORES_FILE_NAME" ]]; then
readarray -t topScores < "$TOP_SCORES_FILE_NAME"
fi
}
Удаление отвоёванных кусков моря
Очевидно, что программы, написанные на bash, работают медленно. При этом аналогичный код, написанный на Java или на C, выполнялся бы мгновенно. Начинаешь замечать время. А ещё нет оптимизации. Поэтому реально пощупать всякие методы оптимизации, которые когда-то изучал, а сейчас привык, что их выполняет компилятор. Как то: вынос повторяющегося кода из тела цикла, переписывание конструкции if-elif-elif-else-fi в порядке убывания вероятности выполнения условия и т. д.
Оказалось, что подзадача удаления отвоёванных кусков моря, является интересной подзадачей. Сначала, был реализован простой алгоритм на основе алгоритма заполнения области:
function deleteFreeAreas() {
local -a points
local -i i
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
...
}
Но это было очень-очень-очень медленно. Потратив два или три часа на оптимизацию, переписывал и так и этак, ускорил раза в два, понял, что нужен другой подход, и лёг спать. А на утро на хабре увидел статью Подсчет объектов на бинарном изображении. Часть 1 Это было то, что надо. Сразу же реализовал приведённый там алгоритм, время которого вполне устроило:
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
...
}
Перемещение противников
Ещё одной интересной подзадачей, было написание кода отражения врагов от границ. Сначала я попытался написать код с кучей проверок различных вариантов, но он получился громоздким и коряво работающим. Пришлось снова задуматься.
Несложно понять, что для определения следующего положения противника необходимо знать кусочек поля размером 3x3, и что возможно всего 2^8 = 256 вариантов препятствий вокруг противника.
Но кодировать все 256 вариантов тоже не хочется, поэтому вспоминаем про сопоставление с шаблоном. Заметим, что в некоторых случаях направление дальнейшего движения зависит только от ключевых кусков границы и не зависит от того, что находится в остальных местах, например:
_ X _ X X X X X _ _ X X
_ 1 _ _ 1 _ _ 1 _ _ 1 _
_ _ 2 _ _ 2 _ _ 2 _ _ 2
Введём обозначения: X — суша, _ — море,? — всё что угодно.
Тогда приведённые выше конфигурации и некоторые другие задаются следующим шаблоном:
? X ?
? o _
? _ _
И всё, осталось только написать функцию сопоставления с шаблоном и придумать набор шаблонов, полностью покрывающих все возможные варианты стен.
function compare() {
local -r -a pattern=($1)
local -r -a x=($2)
local -i i
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 -r x=$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 -i i
local -i y
local -i x
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
...
}
Ну и напоследок две забавные ошибки, которые я допустил пока писал скрипт.
- Переменную, которая сейчас называется tracks, я сначала назвал PATH. А потом не мог понять, почему скрипт падает с непонятными ошибками.
- Строчку
readarray -t topScores < "$TOP_SCORES_FILE_NAME"
я сначала написал как
cat "$TOP_SCORES_FILE_NAME" | readarray -t topScores
Хотя ведь знал, знал, что конвейер исполняется в отдельном процессе со всеми вытекающими.
А сколько было пропущенных значков доллара, пробелов — не счесть.
Скрипт можно найти по ссылке http://codepad.org/UfTfcMxj. Рекомендуется запускать в консоли размером 80x25. Если развернуть на весь экран, то на слабых компах возможны тормоза.
UPD1. Если скрипт скачивать с codepad.org как raw code, то символы конца строки сохраняются как CRLF. И скрипт при запуске начинает сыпаться ошибками. Следует либо вручную вставить текст в файл, либо натравить на файл dos2unix.
UPD2. Выснилось, что правила в случае нажатия на клавишу обратную движению разнятся. Если кто-то хочет, чтобы отнимания жизни в этом случае не было, то может воспользоваться патчем хабраюзера tzlom http://codepad.org/slUUrueq.