Разработка программы «хождение по лабиринту», курсовая работа по системному по, страница 5

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

В качестве алгоритма генерации лабиринта будем использовать алгоритм Краскала, который позволяет генерировать довольно сложные лабиринты, с короткими коридорами, при этом лабиринт будет удовлетворять всем правилам, оговоренным ранее.

Алгоритм Краскала описывается всего семью строками на псевдокоде:

locations:= количество локаций в лабиринте

ПОКА locations > 1

Выбираем случайную стену в лабиринте

ЕСЛИ не существует пути между локациями,

разделенными этой стеной,

разбиваем стену

locations := loacations – 1;

КОНЕЦ ЦИКЛА

Для того чтобы реализовать его на практике, потребуется функция, которая определяет, существует ли путь между двумя заданными локациями или нет. Воспользуемся усовершенствованным волновым алгоритмом:

Будем идти как из начальной, так и из конечной локации. Причем на каждом шаге будем отдавать предпочтение той локации, которая ближе к конечной.

В начале генерирования в лабиринте все локации изолированы и имеют свой номер «соединенности» – если локации имеют разные номера, то еще не доказано, что они соединены.

На каждом шаге изменяется номер «соединенности» новой локации. Ей присваивается номер локации, из которой мы начали путь.