Представление карты в памяти

Основные подходы к представлению карта местности в памяти робота делятся в первую очередь по типу представляемой информации - двухмерная или трехмерная, а во вторых по способу - растровая и векторная. Для подавляющего большинства любительских применений достаточно двухмерных карт или набора двухмерных карт связанных между собой точками перехода (например, планы этажей связанные лифтами и лестницами). Поэтому полноценные трехмерные карты, работа с которыми представляет значительную сложность, мы здесь пока рассматривать не будем.

Растровая двухмерная карта

Растровое представление карты.
Красным отмечены занятые препятствиями клетки.

Под растровой двухмерной картой понимают двухмерный массив в каждой ячейке которого указана информация о статусе этой ячейки для робота. Считается, что объект целиком располагается в соответствующей ячейке.

Пример растровой карты

Двухмерный массив байт 100x100, в котором значения элементов означают следующее:

• 0 - клетка не исследована;
• 255 - клетка непроходима;
• 1-9 - в клетке расположен маяк №1-9 соответственно;
• 10-19 - клетка проходима и относится к зоне 0-9 соответственно;
• 100 - в клетке расположена база подзарядки;

Векторная карта

Векторная карта пространства. Почти всегда всегда окружности запрещены к применению, их заменяют правильными многоугольниками

Под векторной картой понимают структуру данных (часто простой массив, хотя может быть и более сложная структура данных для ускорения поиска) хранящую информацию о размещенных на карты объектах. Место занимаемое объектом может определяться точкой (если не важен размер, например, маяк), окружностью, ломаной линией (если не важна ширина, например, проложенная трасса, забор, граница чего-бы то ни было) или многоугольником (указана последовательность вершин). Кроме того может иметь значение ориентация объекта (например, может быть ориентированный маяк), в этом случае, если объект является точкой, то можно доопределить вторую точку, чтобы получился вектор направления.

Пример векторной карты

Массив записей, каждая из которых состоит из следующих полей:

• Тип объекта - байт (255 - препятствие, 100 - база подзарядки, 10 - помещение);
• Идентификатор объекта - байт (может быть пустым если не важно, например, для препятствий, либо номер помещения или базы или маяка);
• Количество вершин многоугольника, представляющего границы объекта (может быть 1, например, для маяка, когда не важны его размеры);
• Массив на 20 вершин, в котором расположены координаты вершин;