Одной из главных подзадач при разработке системы управления микромышью является запоминание лабиринта и его обработка. При исследовании лабиринта требуется запоминать расположение стенок в каждой клетке, а при построении маршрута требуется “вспоминать” какие стенки и где были обнаружены.
Для этой задачи имеет смысл разработать модуль хранения информации о лабиринте, предоставляющий удобный интерфейс взаимодействия с ним.
Для начала: какие задачи модуль хранения информации о лабиринте должен решать?
Каждая стенка может находится в одном из трех состояний:
Обозначим каждое из этих состояний как перечисление:
enum Wall
{
UNKNOWN,
WALL,
OPEN
};
Тогда для хранения информации о стенках внутри одной клетки можно использовать следующую структуру:
struct Cell
{
Wall left;
Wall down;
Wall up;
Wall right;
};
Порядок стенок в структуре в конечном итоге не имеет значения, т.к. к полям мы все равно будем обращатся по имени. Именно такой порядок я выбрал исходя из порядка расположения горячих клавиш движения в Vim на клавиатуре:
hjkl, что транслируется ввлево,вниз,вверх,вправо.
Эта структура определяет интерфейс взаимодействия с нашим классом. С помощью нее мы сможем передавать информацию о стенках и также ее получать обратно.
Для начала мы определим интерфейс взаимодействия с классом следующим образом:
class Maze
{
// ....... //
public:
/**
* @brief Установить стенку в клетке с данными координатами
*/
void setWall(Vec2 coord, Cell cell_walls);
/**
* @brief Получить информацию о стенках в клетке с данными координатами
*/
Cell getWalls(Vec2 coord);
// ....... //
};
Эти два метода будут нашим основным способом общения с классом.
#include "Maze.h"
int main()
{
Maze maze;
// Сохранение стенок
Vec2 coord = {2, 3};
Maze::Cell cell_walls = {
.left = Maze::OPEN,
.down = Maze::OPEN,
.up = Maze::OPEN,
.right = Maze::OPEN
};
maze.setWall(coord, cell_walls);
// Чтение стенок
coord = {4, 3};
Maze::Cell cell_walls_read = maze.getWalls(coord);
}
Теперь, после того как мы определились с интерфейсом, поговорим о том, как мы можем хранить лабиринт в памяти. Есть несколько способов подойти к решению этой задачи. Подробный разбор всех вариантов пока проводить не будем, сфокусируемся на том, который мне показался самым эффективным по памяти:
Для каждой ячейки лабиринта будем хранить информацию правой и нижней стенках. Таким образом информация о каждой стенке будет хранится в единственном экзепляре и на ячейку будет отводится 4 бита.
Один байт:
ячейка A | ячейка B
[ssee|ssee]
| | | ` восточная (правая) стенка ячейки B
| | ` южная (нижняя) стенка ячейки B
| ` восточная (правая) стенка ячейки A
` нижняя (южная) стенка ячейки A
При таком способе хранения информация о всем лабиринте Micromouse поместится в: 16x16x0.5 = 128Байт.
Как же реализовать такое хранение данных?
#define MAZE_WIDTH 8
#define MAZE_HEIGHT 4
#define MAZE_MEM_SIZE (MAZE_WIDTH * MAZE_HEIGHT / 2)
class Maze{
// ............ //
private:
struct CellStoreRaw
{
Wall hidown : 2;
Wall hiright : 2;
Wall lodown : 2;
Wall loright : 2;
};
enum LoHi
{
LO = 1,
HI = 0
};
CellStoreRaw map[MAZE_MEM_SIZE];
// ............ //
};
Вся информация хранится в массиве структур CellStoreRaw, хранящих информацию о двух соседних клетках.
Для записи информации о стенках реализуем следующий метод:
class Maze{
// .......... //
public:
/**
* @brief Установить стенку в клетке с данными координатами
*/
void setWall(Vec2 coord, Cell cell_walls)
{
// Определение индекса ячейки в массиве и ее относительного положения (LO - правая, HI - левая клетка из пары)
int cell_id = coord.y * MAZE_WIDTH / 2 + coord.x / 2;
int cell_offset = coord.x % 2;
if(cell_offset == LO)
{
SET_WALL(map[cell_id].lodown, cell_walls.down);
SET_WALL(map[cell_id].loright, cell_walls.right);
SET_WALL(map[cell_id].hiright, cell_walls.left);
// Краевой случай - если над клеткой ничего нет, то ничего не сохраняем
if(cell_id >= MAZE_WIDTH / 2)
{
SET_WALL(map[cell_id - MAZE_WIDTH / 2].lodown, cell_walls.up);
}
}
else
{
SET_WALL(map[cell_id].hidown, cell_walls.down);
SET_WALL(map[cell_id].hiright, cell_walls.right);
// Аналогично с самой левой клеткой. Слева нет ячейки, поэтмоу просто ничего не делаем
if(cell_id % (MAZE_WIDTH / 2) != 0)
{
SET_WALL(map[cell_id - 1].loright, cell_walls.left);
}
if(cell_id >= MAZE_WIDTH / 2)
{
SET_WALL(map[cell_id - MAZE_WIDTH / 2].hidown, cell_walls.up);
}
}
}
// ......... //
};
Здесь можно заметить макрос SET_WALL, который проверяет, нужно ли сохранять информацию о стенке в ячейке. Если была передана конкретная информация о стенке (не UNKNOWN), то сохраняем ее, иначе ничего не делаем.
#define SET_WALL(stored_wall, wall) stored_wall = (wall == Maze::UNKNOWN ? stored_wall : wall)
Для получения информации о стенках реализуем следующий метод:
class Maze{
// .......... //
public:
/**
* @brief Получить информацию о стенках в клетке с данными координатами
*/
Cell getWalls(Vec2 coord)
{
int cell_id = coord.y * MAZE_WIDTH / 2 + coord.x / 2;
int cell_offset = coord.x % 2;
Cell cell =
{
.left = getLeftWall(cell_id, cell_offset),
.down = getDownWall(cell_id, cell_offset),
.up = getUpWall(cell_id, cell_offset),
.right = getRightWall(cell_id, cell_offset)
};
return cell;
}
// ......... //
};
В этом методе мы получаем индекс ячейки в массиве и ее относительного положения. Для упрощения работы со стенками были реализованы функции, которые позволяют найти соответствующую стенку в ячейке:
class Maze{
// .......... //
public:
Wall getUpWall(int cell_id, int cell_offset)
{
if(cell_id >= MAZE_WIDTH / 2)
{
if(cell_offset == LO)
{
return map[cell_id - MAZE_WIDTH / 2].lodown;
}
return map[cell_id - MAZE_WIDTH / 2].hidown;
}
return WALL;
}
Wall getLeftWall(int cell_id, int cell_offset)
{
if(cell_offset == LO)
{
return map[cell_id].hiright;
}
if(cell_id % (MAZE_WIDTH / 2) == 0)
{
return WALL;
}
return map[cell_id - 1].loright;
}
Wall getDownWall(int cell_id, int cell_offset)
{
if(cell_offset == LO)
{
return map[cell_id].lodown;
}
return map[cell_id].hidown;
}
Wall getRightWall(int cell_id, int cell_offset)
{
if(cell_offset == LO)
{
return map[cell_id].loright;
}
return map[cell_id].hiright;
}
// ......... //
};
Эти функции проверяют, находится ли соответствующая стенка в ячейке и возвращают соответствующий тип стенки.
Таким образом, мы получили способ хранения информации о лабиринте в памяти Arduino. Полный код можно найти в репозитории tauriel-asmr.