имееш две очереди(мона приоритетные)
исходно рабочая пустая , новая содержит стартовую позицию

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

в оконцове лабиринт засран стоимостями прихода , по рёбрам можно востановить путь либо сразу дополнительно хранить откуда переход.

То есть в рабочую я кидаю только «лечшие позиции» а в новую все остальные?

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

в рабочую очередь только извекаеш добавляеш только в новую

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

Вот тебе самый простейший

Массив целых в размерность карты. Стартовую точку ставишь равно 1. Её соседей = 2. Вот тут нужно учитывать проходимость ячеек/стен. Соседей соседей = 3. Продолжай, пока не найдёшь конечную. Тогда иди обратно, ища у каждой текущей наименьшего соседа, и запоминай точки, пока не вернёшься в стартовую. Профит.

Это разве не BFS?

Думаю что у тебя проигрыш от реализации хипа будет больше чем выигрыш от эвристики.

Не могу понять как A* работает

Это как BFS, только из очереди выбирается не первый добавленный, а тот, для которого `пройденный путь + оценка пути до финиша` является наименьшим. Для клеточного графа будет проще чем для произвольного.

А, блин, действительно, извиняюсь. Нашёл его в статье об А* и всегда считал вариациями одного алгоритма.