Конечно, для исследования такой задачи серьёзные математики успели применить суперкомпьютеры и все знакомые им теории, выработать критерии сложности лабиринтов, доказать встреченные на пути теоремы (теорема четырех красок). У нас же стоит задача гораздо скромнее - использовать возможности JS для демонстрации построения и заполнения замысловатых двумерных областей, чтобы научиться получать контроль над плоскостью экрана.

Определим постановку задачи - как отображать лабиринт и с какой целью. Пусть размер лабиринта и количество ячеек в нём будет переменным. Поэтому используем метод случайной генерации стенок. Так как генерация будет случайной, не получится красивого классического лабиринта с существованием решения, поэтому не будем ставить задачу посетителям ходить по нему. Первой целью будет простое разбрасывание стенок, чтобы посмотреть, что из этого получится. Затем возникают задачи по более эффективному исполнению алгоритма и ряд других сопутствующих задач. Мы их сформулируем, и в последующих подходах, может быть, разовьём в более красивые постановки. В любом случае, задача нужна для того, чтобы поупражняться в программировании и освоить приёмы. Поэтому не будем выбирать слишком сложную или слишком прагматическую (чтобы сразу быстро работало) задачу, а будем решать их по мере возможности и времени так, чтобы в первую очередь, демонстрировать коды и методы решения.

Чтобы результат выглядел содержательнее (сложнее структура на единицу площади экрана), стенки сделаем тонкими, поэтому рисуем их бордюрами вокруг квадратиков. Квадратики кодируются в матрицу (двумерный массив). Если к каждому квадратику отнести две стенки (нижнюю и правую), то 2 битами в каждом элементе масссива описывается весь лабиринт.

Далее делаем отображение в HTML. Скрипт генерирует таблицу. В ячейке таблицы создаём элемент с границами (div), которому при генерации припишем нужные цвета границ. Проще писать их не явно, а классами. Классов будет всего 4, соответственно числу комбинаций правой и нижней границ. Для проверки сделаем небольшой скрипт с матрицей, заданной вручную.

Пример 0. (без демонстрации)

<style>.l1,.l2,.l3,.l4{border:1px solid white;
  font-size:4px;width:10px;height:10px}
 .l2{border-right-color:black}
 .l3{border-bottom-color:black}
 .l4{border-bottom-color:black;border-right-color:black}
</style><script>lab=[
'133333314',
'232131322',
'213424234',
'221322134',
'222342332',
'223133314',
'221413232',
'223222122',
'233423434'];
s='<table cellspacing=0 cellpadding=0 style="border:1px solid black;'
  +'border-bottom-width:0;border-right-width:0">';
for(i=0;i<lab.length;i++){s+='<tr>';
  for(j=0;j<lab[0].length;j++){
    s+='<td><div class=l'+lab[i].charAt(j)+'> </div></td>';
  }s+='</tr>';
}s+='</table>';
document.write(s);</script>

На этой таблице видим различия в представлении в разных браузерах, чтобы в следующей версии скрипта их исправить. В частности, размер ячейки в Gecko равен размерам div плюс ширина границ. Чтобы получить одинаковые результаты, для Gecko (Mozilla, Firefox) надо задавать в стиле размеры на 2 пикселя меньше.

Надо заметить, что таблица для рисования лабиринта необязательна, если позиционировать ячейки абсолютно. (Может, это будет быстрее отрисоываться в IE? Потому что некоторая проблема в отображении возникает только в IE на больших полях лабиринтов, потому что он раза в 4 медленнеее отрисовывает код таблицы, что будет видно по результатам. В этом можно убедиться на примере 1 при открывании его в окне большой площади.)

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

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

Строим генерацию лабиринта на всём поле окна.

Лабиринт представляет собой массив ny на nx клеток, стенки в которых описываются числами от 0 до 3.

0 - нет нижней и правой стенок;

1 - есть правая стенка, нет нижней;

2 - есть нижняя, нет правой;

3 - есть нижняя и правая.

Наличие верхних и левых стенок описывается в смежных клетках. За пределами массива клеток считаем, что стенки имеются.

Пример 1.

<style>.l0,.l1,.l2,.l3 {border:1px solid white;
  font-size:10px; width:14px; height:14px;}
 .l1{border-right-color:black}    /*классы ячеек таблицы*/
 .l2{border-bottom-color:black;}
 .l3{border-bottom-color:black;border-right-color:black}
</style>
<script>d=document;
onload=genLab=function(){
  aL=[];for(i=0;i<ny;i++)aL[i]=[];  //--образ лабиринта
nx=((d.all?d.body.clientWidth:innerWidth)-30)/14;
ny=((d.all?d.body.clientHeight:innerHeight)-80)/14;
s='<table cellspacing=0 cellpadding=0'
  +'style="border:1px solid black;'
  +'border-bottom-width:0;border-right-width:0" id=t1>';
for(i=0;i<ny;i++){s+='<tr>';
  for(j=0;j<nx;j++){
    s+='<td><div class=l'+(aL[i][j]=Math.floor((Math.random()
      *1.5)+0.96))+'> </div></td>';
    //важные константы частоты встречаемости стенок
  }s+='</tr>';
}s+='</table>';
d.getElementById('d1').innerHTML=(d.all?''
  :'<style>.l0,.l1,.l2,.l3{width:12px;height:12px;}</style>')
  +s;}  //поправка размера ячейки для FF
</script><div id=d1></div> <!--место для вывода лабиринта-->

Демонстрация - в примере 1.

aL[i][j] здесь не нужно, но пригодится в следующем примере.

Классы ячеек определяются цифрами 0-3, выбор которых производится случайной функцией Math.random(). Вероятности встречаемости определяют проходимость лабиринта. Так, класс l3 делает ячейку, закрытую справа и снизу. Если допускать появление ячеек с таким классом, будет много небольших замкнутых областей. Чтобы в примере лабиринт был более "проходимым", этот класс вообще в результатах не встречается. Числа 1.5 и 0.96 определили такие вероятности появления классов ячеек: l0 (наиболее открытая):l1(c вертикальной правой границей):l2 (с горизонтальной нижней границей) встречаются в соотношении 4:100:46. Это определило то, что вертикальных стенок больше, и то, что иногда встречаются ячейки совсем без стенок. Если константы выбрать иначе, построится лабиринт с другим соотношением и густотой стенок.

Чтобы гибче управлять соотношением стенок, нужно применить более сложные алгоритмы генерации. Если в этом возникнет интерес, предлагаю писать варианты скриптов на форум по этой теме, а пока что будем разрабатывать алгоритм дальше. На очереди - заполнить связную область лабиринта одним цветом фона.

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

Выбирается точка входа - клетка, с которой начнётся обход. Создаётся стек попыток обхода области лабиринта (чтобы методом перебора путей однозначно обойти все клетки области). Создаётся образ пройденных и непройденных клеток лабиринта (чтобы знать цвета областей и выбирать непройденные области). Создаётся массив пройденных клеток области (на случай, если придётся менять их цвет).

Шаги по лабиринту будем описывать числом от 0 до 3. Шаг с параметром 0 - влево; с параметром 1 - вниз; с параметром 2 - вправо; с параметром 3 - вверх.

Тогда метод полного перебора путей заключается в том, чтобы пройти по связанной области, идя по возможности в направлении 0 (параметр 0), но не заходя на пройденные клетки. Если невозможно, выбираем направление 1 в наиболее далёкой ветви пути. Если "1" пройдено, выбираем 2, затем аналогично 3. Если все направления пройдены или не дают пройти стенки, пробуем обход более короткой ветви. Логический анализ показывает, что при таком алгоритме обход всей связанной области лабиринта закончится на невозможности пройти по направлению 3 из стартовой клетки (длина ветви - 0). Стек попыток обхода хранит направления каждого сегмента ветви, а длина определяет длину ветви - насколько далеко ушли от стартовой точки.

Описываем в функции попытки "шага" по лабиринту (hod()) случаи: попадание на стенку, на пройденный или непройденный участок. Если попадаем на стенку или пройденный участок, то шага нет и выбираем попытку шага с параметром, на 1 большим. Если он превысил 3 - все возможности исчерпаны, возвращаемся по стеку попыток назад и делаем попытку с прибавлением параметра прежнего шага. Если стек закончился - попытки исчерпаны, вся область лабиринта пройдена.

Если пройденную область закрашивать, увидим всю замкнутую пройденную область лабиринта.

Пример 2.

<style>/*к стилям добавлен (остальные - из примера 1)
  класс закрашенной ячейки. Пока что он один (1 цвет)*/
 .f{background-color:#bbb; border-left-color:#bbb;
  border-top-color:#bbb;}
</style><script>d=document;
onload=genLab=function(){
 **код функции genLab копируем сюда из примера 1 !**
//  далее работаем с закраской области
  ta1=d.getElementById('t1');
  sO=[];iSO=0;  //стек обхода
  aM=[];for(i=0;i<ny;i++)aM[i]=[];//образ пройденных клеток
  i=0;j=0;  //точка входа (начало закраски)
  j2=i2=0;  m=0;k=0;  //служебные переменные
  projden(i,j);  //пометка 1-й клетки
setInterval(hod2,30); //периодически делаем группу ходов,
//  в данном случае, на 7 клеток, чтобы видеть процесс
}
hod=function(n){
  i2=i+(n==3?-1:(n==1?1:0));
  j2=j+(n==0?-1:(n==2?1:0));  //попытка хода
  if(i2<0||i2>=ny||j2<0||j2>=nx)return -1;  //край
  if(n==0&&aL[i2][j2]%2==1 || n==1&&aL[i][j]>1
    || n==2&&aL[i][j]%2==1 || n==3&&aL[i2][j2]>1)
    return -1;  //стенка
  if(aM[i2][j2]&&aM[i2][j2]==1)return -1;//пройденное поле
  return 0;  //проход разрешён
}
projden=function(i,j){  //помечаем клетку визуально и в aM
tc=ta1.firstChild.childNodes[i].childNodes[j].firstChild;
  if(tc.className=='l1'||tc.className=='l0')
    tc.style.borderBottomColor='#bbb';
  if(tc.className=='l2'||tc.className=='l0')
    tc.style.borderRightColor='#bbb';
  ta1.firstChild.childNodes[i].childNodes[j]
    .firstChild.className+=' f';  //делаем составной класс
  aM[i][j]=1;  //пометка, что поле пройдено
  m++;  // счёт до 7 для визуального эффекта
}
hod2=function(){m=0;  //для визуальности, счёт до 7
  for(k=k;k<4&&m<7;k++){  //древовидный обход области
    if(!hod(k)){i=i2;j=j2;  //ход вперёд
      projden(i,j);  //пометка клетки
      sO[iSO++]=k;  //пометка стека
      k=-1;  //(цикл сделает далее k==0)
    }else{while(iSO>0&&k==3){k=sO[--iSO];  //возврат
      i-=(k==3?-1:(k==1?1:0));
      j-=(k==0?-1:(k==2?1:0));
        //**внимание, здесь k обновляется из стека
    }}
  }
}</script><div id=d1></div>

Демонстрация - в примере 2 к статье.

В JS нет оператора или функции pause(), а действие по закрашиванию областей - очень длительное. Чтобы одновременно видеть процесс закрашивания, в программу ввели функции hod2 и hod. Первая контролирует закрашивание группы клеток, а затем делает короткую паузу, чтобы браузер хотя бы не завис на выполнении операции, а также мог бы прорисовать изменения. Особенно страдает от зависания IE6, поэтому для него надо устраивать такие порции выполнений, чтобы в случае необходимости можно было закрыть окно или уйти на другую страницу простым кликом по кнопке или ссылке. В ином случае придётся снимать задачу, что очень отрицательно скажется на репутации автора страницы :). FF, Ореra, например, сами через некоторое время сообщают о зависании скрипта и предлагают прекратить его выполнение, спасая репутацию создателя, но не все такие лояльные. Паузы между порциями выполнений создаются функцией setInterval().

Получили программу закрашивания одной области. Наметим планы (алгоритм) по закрашиванию всех замкнутых областей.

Чтобы окрасить смежные замкнутые области в разные цвета, нужно контролировать цвет клеток за стенками, чтобы суметь выбрать новую клетку в новой области для обхода. Поиск непройденных областей за стенкой выполним после обхода очередной области. Из произвольной точки пройденной области будем двигаться в произвольном направлении, невзирая на стенки, пока не встретим край лабиринта или непройденную область. Если встретили край, начинаем обход границы лабиринта в поиске непройденных областей. (Так, очевидно, можно оставить непройденные области внутри лабиринта.) Если сделан полный обход края лабиринта и все области заполнены, проверяем каждую клетку на заполненность. При нахождении незаполненной отмечаем место поиска, чтобы возвратиться к нему, и заполняем область. С этого момента по окончании заполнения области будем делать поиск непройденных областей перебором клеток. Полный перебор клеток заканчивает алгоритм.

Не описано закрашивание ровно 4 цветами, предполагаем, что число цветов не будет ограничено.

Обратимся поскорее к нематематической стороне вопроса - к скорости выполнения. Простой запуск примера 2 в разных браузерах при достаточно большой площади окна или при медленном процессоре показывает большую разницу в скорости прорисовки лабиринта. Opera (7-9) быстрее всех и имеет приемлемую скорость даже при 1600х1200, FireFox (1.07) работает чуть медленнее, на "хорошо", а IE имеет значительно меньшую скорость. Для попыток исправить немного модифицирован скрипт, чтобы он не включал в себя таблицу. Пример 3 работает корректно только в IE (строчные элементы в "правильных" браузерах не могут иметь ширины иной, чем содержащиеся в них элементы). Но зато по генерации страницы он наиболее экономичен - позволяет уменьшить время генерации на 25-30%. Что заметно в сравнении, но неудовлетворительно, если становится больше 3-4 секунд. На процессоре 2 ГГц с шиной памяти 266 МГц на полном экране в 1840 пикс IE6 над примером 1 работает 14 секунд. Это данные для конкретного процессора - большое значение имеет заполненность кеша ОЗУ и тип видеокарты. Opera 9 выполняет ту же работу за 1.5 секунды, FF - за две. Уменьшение с 14 до 10-11 - небольшое достижение. Попытка сделать скрипт с абсолютным позиционированием - пример 4 - приводит к значительно худшим результатам во всех браузерах, скорость генерации - раза в 2.5-3 меньше. Следовательно, в следующей версии скрипта надо подумать и об измерении скорости работы браузера, чтобы ограничить область, занимаемую лабиринтом. Что есть сама по себе интересная и полезная задача, результаты которой найдут примернение в других скриптах.

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

Заключение. Рисуя лабиринты, получили не только опыт работы со скриптами, но и увидели пределы мощности прорисовки таблиц и слоёв в разных браузерах. Очень большое число ячеек рано или поздно приводит к замедлению работы, что наглядно видно в нашем примере.

Ссылки к статье: