Пример метода волны приведен на Рис.1. Черными клетками обозначены препятствия. Волну запускаем из верхней левой клетки, конечная – нижняя правая. Ходить можно либо по горизонтали, либо по вертикали, по диагонали ходы запрещены. Получаем, что в конечную клетку можно попасть за 8 ходов.
Существуют различные задачи, для решения которых подходит данный алгоритм.
Задача о лабиринте. Дано: двумерный массив с препятствиями, начальная и конечная клетки. Найти путь с минимальным количеством ходов. Идея решения уже рассмотрена выше. Данный метод часто применяется в компьютерных играх, как правило, в стратегиях, т.к. на каждом шаге необходимо заново запускать волну, т.е. находить снова лучший путь после изменения положения некоторых объектов на поле, а это требует значительных временных затрат.
Для увеличения быстродействия метода волны можно применить некоторое его улучшение – двойной поиск в ширину. Его отличие в том, что запускается сразу 2 волны, одна из начальной клетки, другая из конечной. Серыми клетками обозначены начальная и конечная клетки. Слева (Рис.2а) пример с запусканием одной волны, справа (Рис.2б) – запускаются сразу две волны. Теоретически вторая волна может дать улучшение в 3-4 раза, но практике, как всегда все оказывается «немного» не так.
Задача о замке. Имеется план замка, т.е. известно, где расположены стены внутри замка (Рис.3). Необходимо определить, сколько комнат в замке, найти комнату с наибольшей площадью, и определить какую перегородку необходимо убрать, чтобы получить комнату с максимально возможной площадью.
С помощью метода волны эту задачу можно решить следующим образом. Ищем в массиве «пустую» клетку, запускаем из нее волну, и считаем сколько всего ходов сделали, т.е. сколько клеток заполнили числами, это и будет площадью комнаты. Повторяем процесс, пока есть свободные клетки. Количество комнат равно количеству запусков волны.
Еще одна модификация задачи о лабиринте – задача о пути с минимальным количеством поворотов. Дано: двумерный массив с препятствиями, начальная и конечная клетки. Из начальной клетки можно двигаться в любом направлении по горизонтали или вертикали, но затем направление можно поменять только «столкнувшись» с препятствием или границей лабиринта. Необходимо найти путь с минимальным количеством поворотов.
Эту задачу удобно решать методом волны. Единственной модификацией алгоритма здесь будет «необычный» ход. «Необычный» ход представляет собой следующее: из текущей клетки во всех направлениях ищем препятствие или границу лабиринта, как только нашли, определяем стоим на непосещенной клетке или на ней мы уже были, если клетка свободна, то заносим туда соответствующее значение – номер шага. Рис.4 демонстрирует прохождение лабиринта с применением такого «необычного» хода.
Задача о «блохах». На шахматной доске размером NxM имеется Q блох и имеется кормушка в клетке с координатами (x,y) – Рис.5а (Х-кормушка, Б-блоха). По полю блохи передвигаются ходом шахматного коня. Необходимо определить для каждой блохи, за какое минимальное количество прыжков она сможет добраться до кормушки, или определить, что этого сделать невозможно. (1
Можно брать координаты каждой блохи как начальную клетку, а координаты кормушки - как конечную, и запускать волну Q раз. Но при Q=10000, данный алгоритм не будет проходить по времени. Здесь целесообразно запустить волну из кормушки, если на очередном ходе попадаем в клетку с блохой, то мы нашли длину ее пути до кормушки. Результат виден на Рис.5б: черные клетки – первоначальные места расположения блох, клетка, в которой записан 0, представляет собой кормушку.
Можно также модифицировать метод волны на трехмерное пространство (Рис.6), для этого потребуется трехмерный массив с лабиринтом, и на каждом шаге просматривать не 4 или 8, 6 и 26, соответственно, соседних клеток. Можно модифицировать данный алгоритм для тел произвольной формы. Для этого естественно надо будет изменить логику установления факта встречи с препятствием, и при необходимости предусмотреть возможность поворота объекта для прохождения в узких местах лабиринта.
Метод волны используется также и в алгоритмах на графах – поиск в ширину, для нахождения кратчайших путей между исходной вершиной и конечной (или всеми остальными). Дано: граф (Рис.7а). Необходимо найти путь от первой вершины до девятой, содержащий минимальное количество ребер. На Рис.7б показана очередность просмотра вершин графа.
В компьютерной графике метод волны может применяться для закрашивания областей произвольной формы, или для выделения определенного цвета в заданной замкнутой области. Для этого другие цвета будут рассматриваться как препятствия, а искомый цвет с допустимыми отклонениями как свободные клетки. По сути это задача о замке, т.к. в обоих случаях имеются замкнутые области, которые надо полностью просмотреть. Дано: произвольная область (Рис.8а). Требуется закрасить серым цветом всю белую область внутри черной границы. На Рис.8б показан результат, а также ход выполнения метода волна. На каждом шаге данного алгоритма мы просматриваем клетку, если она белая, то закрашиваем, в противном случае ищем среди соседних клеток белые, куда можно сходить.
Данный метод также применяется для векторизации изображений. Допустим, у нас имеется растровое изображение (для каждой точки задан определенный цвет), мы хотим преобразовать его в векторную форму (изображение состоит из векторов, т.е. известно положение двух точек, между которыми строится прямая). Для простоты будем полагать, что фон изображения белый, а сам рисунок изображен только черным цветом.
Рис.9.Слева (Рис.9) пример растрового изображения (черным цветом) и построенного векторного (серым цветом). Векторизация заключается в построении графа, т.е. нам необходимо найти в растровом изображении «контрольные точки» (вершины в графе) и соединить их отрезками (ребра в графе). Данный метод основан на том, что мы предполагаем определенную ширину линий, и основываясь на этом пытаемся выделить ее в растровом изображении. Необходимо также учитывать, «линии» в растровом изображении могут пересекаться и соединяться (как показано на рис.9). Для определения этих линий и мест их пересечения и используется метод волны. Запускаем волну из какого-либо места растрового изображения, через 2*N шагов (N – ширина «линии» в пикселях) волна принимает устойчивых характер, на каждом шаге нам необходимо отслеживать «ширину» волны, т.е. количество точек образующих текущую генерацию волны. В местах пересечения «линий» растрового изображения, наша волна будет разделяться на две дочерние волны. Следовательно, перед разделением волны, ее «ширина будет увеличиваться», а затем произойдет разделение волны. Т.о. можно определить точку соединения или пересечения «линий» в растровом изображении. После построения такого каркаса, возможна дальнейшая оптимизация, например, уточнение места положения точек пересечения, удаление лишних точек и т.д., но это не входит в рассмотрение данной статьи. Данный метод может применяться для создания программ распознавания текста, конструкторской документации, САПР.
Применение метода волны для решения задач на графах или задач о лабиринте и близких к ним подробно описаны в работах [1, 2]. Применение волнового алгоритма и его модификации для компьютерных игр рассмотрены в статьях [3].
