Учим bash-скрипты, пишем Xonix / Habr

Прочитал я пару недель назад на хабре статью Учим bash-скрипты, пишем Sokoban и подумал, что тоже знаю bash и могу что-нибудь написать, а заодно ещё лучше узнать bash. Подумал ещё и вспомнил, что давно хотел написать Xonix, когда-то этой игрой заигрывался на своём старом 386-м. И вот, несколько бессонных ночей и скрипт готов. Если интересно как это писалось, какие проблемы возникали, то добро пожаловать под хабракат.

Правила игры 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.