Быстрый алгоритм, который может найти неизвестное место назначения сетки на 2-й карте, построенной на ходу - PullRequest
Новая
       68

Быстрый алгоритм, который может найти неизвестное место назначения сетки на 2-й карте, построенной на ходу

0 голосов
/ 21 мая 2019

У меня есть ровер, который строит карту по ходу дела.Он хранит данные о каждом месте сетки в узле.Он хранит информацию о том, был ли он исследован / не исследован (то есть, если датчики сканировали это местоположение на сетке) или посещен (ровер был актуален в этом месте) или заблокирован или нет.Я использую A *, чтобы помочь найти пути.Итак, переход от исходного местоположения (местоположения роверов) к месту назначения.Эти места назначения являются неисследованными частями карты, которую он создает.

Данные хранятся в связанном массиве решеток, в основном каждый узел имеет 8 указателей на каждое окружающее местоположение сетки.каждое родительское местоположение, которое было исследовано, будет создавать / заполнять окружающие узлы неизведанными.каждый исследуемый узел помечается, если он был посещен / обнаружен или заблокирован / доступен для навигации.Неизведанное - просто ноль для всего, кроме ожидаемого исследуемого бита.

Я ищу алгоритм, помогающий найти следующее неисследованное место назначения.Скорее всего, самый близкий, но он должен быть в состоянии оставаться быстрым при увеличении размера карты.

Я попытался создать 2d массив, который примерно в 4 раза больше размера единичного узла, но проблема, которую я запустилкогда все узлы этого размера исследуются, происходит сбой.Я думал о том, чтобы попытаться проверить каждый узел, выходящий наружу от исходного узла.но это будет проверка множества узлов, которые уже были замечены и которые становятся громоздкими по мере роста карты.Дело в том, что внешний периметр всегда будет иметь неизведанные узлы.Также любые узлы внутри большого объекта.(Мне все еще нужно найти способ изменить эти узлы).

У меня еще нет кода.

Я ожидаю, что это быстрый алгоритм, который находит неисследованное местоположение, поэтому яможет использовать это, имеет мой пункт назначения в моем * A пути поиска.

1 Ответ

0 голосов
/ 21 мая 2019

У вас могут быть двухмерные массивы с указателями «связанной решетки» на окружающие одноранговые узлы, так что вы можете связываться с новыми окружающими областями без изменения размеров массивов.

struct Explored_index
{
    std::array<std::array<bool, N>, N> explored_;
    std::array<Explored_index*, 8> links_;  // say 0=North, clockwise
};

Если вы хотите, чтобы это масштабировалось произвольно, вы можете автоматизировать его так, чтобы после того, как любые 9 массивов были полностью исследованы, он добавил индекс более высокого уровня, в котором каждый бит в массиве 2d указывал, является ли массив 2d в2-й по величине индекс был полностью изучен, но если этот «ровер» каким-либо образом физический, существуют ограничения по времени, сколько он может исследовать, и вам, вероятно, не нужна такая масштабируемость.

...