Манипуляции с изображением лабиринта, обрезка пробелов

лабиринт

Проблема, с которой я сталкиваюсь, - это пути шириной 2 пикселя (белые части).

В левом верхнем углу изображения (более темная черная часть) я вручную прошелся по белым частям, которые были 2 пикселя в ширину/высоту;

есть два решения (которые я могу придумать).

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

любые предложения, алгоритм решения лабиринта (tremaux), который я реализовал, работает для путей 1x1, но я пытаюсь адаптировать его к этому более крупному лабиринту.

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

Просто ищу подсказки/шаги в правильном направлении, так как я не уверен, правильно ли я смотрю на это или иду по правильному пути (без каламбура).

Спасибо


java algorithm image-manipulation maze
person Koborl    schedule 19.01.2015    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Таким образом, ваша сетка эффективно повторяет (1,2) = 3 пикселя, 1 стена 2 пути. Просто удалите каждую 3-ю строку. Затем удалите каждый 3-й столбец.

person RobAu    schedule 19.01.2015

arrow_upward
0
arrow_downward

Думайте о том, что изображение разделено на блоки 3x3, причем верхний левый угол всегда является стеной, верхняя строка и левый столбец — необязательными стенами, а остальные — путем, например:

W w w
w P P
w P P

W = always wall
w = possible wall
P = always path

Вам нужно преобразовать каждый из этих блоков 3x3 в блок 2x2 следующим образом:

W w
w P
person samgak    schedule 19.01.2015

arrow_upward
0
arrow_downward

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

person Matt Timmermans    schedule 28.09.2019