Как создать двухметную "карту" пространства.

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

P.s. Пока ничего кроме как боооооооооольшой массив в голову не приходит.

 

В простейшем случае двумерный массив, элементы которого показывают, "свободна" ли данная "клетка" карты или нет.

 

Есть второй метод, более медленный (в проекции на возможности МК), но менее требовательный к ресурсам - изучать пространство по мере продвижения к цели (прохождение лабиринта). Достаточно будет запомнить маршрут из точки отправления и последний неудачный маршрут.

 

А где будет храниться карта того пространства, которое будет изучаться по ходу движения? Считываться с GPIO ?

 

Например, в GPS-навигаторе трек можно записывать несколькими способами:
- каждую секунду текущую координату (для Ардуино это 8 байт в секунду)
- текущую координату при абсолютной величине ее изменения больше чем минимальная ошибка GPS (8 байт на координаты плюс 4 байта время прибытия в новую точку пространства)
- то же самое, что п.2 но только изменение координаты и времени относительно предыдущей позиции (от 2 до 12 байт в зависимости от скорости движения и метода "упаковки" приращений координат
- и т.д.

Третий способ в одном конкретном случае пешеходного GPS позволяет упаковать 20 тысяч точек пути в 64 кБ ПЗУ за счет того, что приращение координат в пешем режиме умещается в несколько битов. Если уменьшить точность, можно сохранять треки в широком диапазоне скоростей изменения координат

Я к тому, что в зависимости от используемой платформы можно использовать разные методы и вполне реально хранить очень много информации в стандартном 8+4кБ ЗУ МК.

 

А хватит ли точности GPS?

Карту можно хранить как множество полигонов...

 

Возможно, придется сделать выбор, какую модель пространства использовать: дискретную или непрерывную. В первом случае, карта в первом приближении будет представлять собой битовую карту пространства, во втором - множество контуров (полигонов) на плоскости, определенных через упорядоченное множество вершин.

 

А как вы будете решать проблему позиционирования? Для маленькой платформы точности GPS, как сказал Mitrandir, скорее всего, не хватит. Только что IMU использовать...

 

Я привел GPS только в качестве примера.
Ибо Цели определяют Средства
Прежде надо ответить на вопросы:
- каковы характеристики пространства в котором предполагается ориентирование
- каковы требования к точности и скорости позиционирования

Отсюда выбор исполнительных механизмов и сенсоров и платформы для их обслуживания.
Ориентирование двухколесного бота на столе 1х1 метр - один выбор средств, ориентирование боеголовки в пределах системы Альфа Центавра - другие средства.

 

Субъективный опыт использования IMU: накопление существенной ошибки с течением времени. То есть использовать IMU как систему инерциальной навигации вряд ли получится. Пожалуй, только для определения ориентации прибора относительно положения, достигнутого в процессе начальной стабилизации.

 

Естественно и вполне ожидаемо. Но что остается делать, использовать libastral.a ?

 

в начале 80-х мне подарили модель танка Т54. Когда мне надоело управлять им с помощью пульта, я поставил на него систему из двух программных дисков из фольгированного гетинакса. Диск вращался постоянно, по нему ползали токосъемники. Конфигурация дорожек и коммутация токосъемников была подобрана таким образом, что танк ездил в ту сторону, где находился наиболее мощный источник света.
Фактически на диски была нанесена "программа" действия. 0 байт ОЗУ, 0 байт ПЗУ, нет микроконтроллера, быстродействие сопоставимое с неповоротливостью управляемой модели советского времени. Но работало

Опять же я к тому, что если у вас нет даже Ардуино, можно что-нибудь всегда придумать

 

BTW, была такая идея - сделать платформу с IR/Sonic радаром (постоянное вращение на 360 и скан местности), которая бы ездила по помещению, а свое положение в пространстве вычисляла исходя из корреляции текущего снимка с радара с кумулятивным образом всего пространства.

 

о, нашел про диск

http://www.radioradar.net/articles/scientific_technical/encoder.html

 

Имхо, неподъемная для Ардуино задача. Но как один из вариантов

 

Ардуиновские сенсоры довольно грубо видят пространство, так что, может быть, объем информации и не так велик, но все-таки да, ее много. Может быть, Arduino Due потянет...

 

Due потянет!

 

Для своей телеги, планирую связку дальномер+компас+ ИМУ под управлением связки ардуино+расбери

 

местность можно представить в виде связанного графа, где вершины - решетка из точек с заданной дискретностью, а ребра - возможные маршруты движения из этой точки до соседних.
Получаем 2х мерный байтовый массив, где каждый бит будет указывать на возможность движения в конкретном направлении. Например, если последовательность курсов С-СВ-В-ЮВ-Ю-ЮЗ-З-СЗ, то запись в массиве для конкретной точки вида 11101101 скажет роботу, что двигаться с текущей позиции он может только на север, северо-восток, восток, юг, юго-запад и северо-запад.
А хранить можно на SD-карточке в файле.

 

думаю, что сообщество будет вам благодарно, если вы примените Due в этом проекте
пока мало проектов на этой платформе
P.S. Субъективное мнение