Алгоритм алгоритма поиска лабиринта - программирование
Подтвердить что ты не робот

Алгоритм алгоритма поиска лабиринта

HTML

<div id="labirinth">
    <form style="text-align:center" name="forma1" autocomplete="on">
        <table style="margin:0 auto;">
            <tr>
                <td style="float:right;">Height:</td>
                <td><input type="text" id="height" name="height" autofocus="autofocus" maxlength="2" size="6" /></td>
            </tr>
            <tr>
                <td style="float:right;">Width:</td>
                <td><input type="text" id="width" name="width"  maxlength="2" size="6" /></td>
            </tr>
        </table>
    </form>
    <input type="button" alt="submit" onClick="datas();" value="New" style="margin-top:10px;" />
</div>
<pre id="out"></pre>

JavaScript

function datas() {

    var height = parseInt(document.getElementById("height").value);
    var width = parseInt(document.getElementById("width").value);

    document.getElementById('out').innerHTML = display(maze(height,width));
}

function maze(x,y) {
    var n=x*y-1;
    if (n<0) {alert("Bad numbers!");return;}
    var horiz=[]; 
        for (var j= 0; j<x+1; j++) horiz[j]= [];
    var verti=[]; 
        for (var j= 0; j<y+1; j++) verti[j]= [];

    var here= [Math.floor(Math.random()*x), Math.floor(Math.random()*y)];
    var path= [here];
    var unvisited= [];
    for (var j= 0; j<x+2; j++) {
        unvisited[j]= [];
        for (var k= 0; k<y+1; k++)
            unvisited[j].push(j>0 && j<x+1 && k>0 && (j != here[0]+1 || k != here[1]+1));
    }
    while (0<n) {
        var potential= [[here[0]+1, here[1]], [here[0],here[1]+1],
            [here[0]-1, here[1]], [here[0],here[1]-1]];
        var neighbors= [];
        for (var j= 0; j < 4; j++)
            if (unvisited[potential[j][0]+1][potential[j][1]+1])
                neighbors.push(potential[j]);
        if (neighbors.length) {
            n= n-1;
            next= neighbors[Math.floor(Math.random()*neighbors.length)];
            unvisited[next[0]+1][next[1]+1]= false;
            if (next[0] == here[0])
                horiz[next[0]][(next[1]+here[1]-1)/2]= true;
            else 
                verti[(next[0]+here[0]-1)/2][next[1]]= true;
            path.push(here= next);
        } else 
            here= path.pop();
    }
    return ({x: x, y: y, horiz: horiz, verti: verti});
}

function display(m) {
    var text= [];
    for (var j= 0; j<m.x*2+1; j++) {
        var line= [];
        if (0 == j%2)
            for (var k=0; k<m.y*4+1; k++)
                if (0 == k%4) 
                    line[k]= 'X';
                else
                    if (j>0 && m.verti[j/2-1][Math.floor(k/4)])
                        line[k]= ' ';
                    else
                        line[k]= 'X';
        else
            for (var k=0; k<m.y*4+1; k++)
                if (0 == k%4)
                    if (k>0 && m.horiz[(j-1)/2][k/4-1])
                        line[k]= ' ';
                    else
                        line[k]= 'X';
                else
                    line[k]= ' ';
        if (0 == j) line[1]=line[3]=' ',line[2]= '1';
        if (m.x*2-1 == j) line[4*m.y]= '2';
        text.push(line.join('')+'\r\n');

    }
    return text.join('');
}

Я пытаюсь создать полностью рабочий генератор лабиринтов в JavaScript без использования ячеек таблицы HTML. Теперь у меня проблемы с решателем создания для этого лабиринта.

Вопрос: Какой алгоритм решения лабиринта нужно использовать для моего кода? С чего начать? Мне не нужен весь алгоритм - мне просто нужен совет, можно ли в этом генераторе лабиринта найти лабиринт.

JSbin - http://jsbin.com/uwoyon/1

4b9b3361

Ответ 1

Моя рекомендация для решателя, который должен работать для лабиринтов, которые вы генерируете, будет алгоритмом Дейкстры. Хотя я не уверен, как параметры horiz и verti определяют структуру лабиринта, алгоритм Дейкстры будет работать в вашей ситуации, начиная с ячейки рядом с "1" и строя оттуда.

Способ, которым он работает, - обозначить каждую ячейку количеством ячеек между ней и начальной ячейкой. Для лабиринта 3x3 первая ячейка будет:

x 1 xxxxxxxxx
x 1         x
x   xxxxxxxxx
x           x
x   xxxxxxxxx
x           2
xxxxxxxxxxxxx

Работа с помеченной ячейкой проверяет, есть ли пустая соседняя ячейка (одна не заблокирована стеной), увеличивайте значение ячейки на 1. Повторите этот процесс для всех пустых ячеек:

x 1 xxxxxxxxx
x 1   2   3 x
x   xxxxxxxxx
x 2   3   4 x
x   xxxxxxxxx
x 3   4   5 2
xxxxxxxxxxxxx

Теперь откидывайтесь назад от ячейки, прилегающей к концу '2'. Это показывает, что решение имеет путь длиной 5 шагов, поэтому начинайте с 5, найдите соседние 4, затем 3 и т.д. Назад к 1.

Примечание. Я рекомендую рекурсивное решение, использующее очереди для маркировки ячеек:

1- Наклейте первую ячейку на "1" и поместите ее в очередь.

2- Возьмите ячейку из очереди: - проверить, не закончен ли соседи по закону (те, которые не заблокированы стеной). - Если соседняя ячейка не маркирована, затем назовите ее текущей ячейкой + 1. - Добавить соседнюю ячейку в очередь. - Повторите для всех 4 потенциальных соседей

3 Повторите шаги 1 и 2, пока не будет больше немаркированных ячеек.

EDIT: здесь fiddle для решателя, используя то, что я предложил, это не относится к генератор лабиринта в вопросе, поэтому, если не спросить, я не буду вдаваться в подробности о том, как он работает (это немного грубо, но его реализация должна быть достаточно простой, чтобы следовать).

Ответ 2

Если это идеальный лабиринт (только один путь между любыми двумя ячейками), вам просто нужен рекурсивный последователь стены. Начните с первой ячейки и проверьте все окружающие ячейки в заданном порядке, обычно по часовой стрелке или против часовой стрелки. Если ячейку можно ввести, введите ее. Если это конец, все готово. Если нет, повторите. Когда вы проверили все 3 других пути, и никто не закончил, просто вернитесь. Когда вы дойдете до конца, у вашего стека вызовов есть решение:) То, что я обычно делаю, это вернуть "false" для "Я не нашел решение здесь" или "true" для "это решение".

Вы можете видеть, как я решаю в своих алгоритмах лабиринта на github:

https://github.com/mdchaney/jsmaze

Если вы посмотрите на jsmaze2.html, функция "find_depth" на самом деле является решателем.

jsmaze4.html намного сложнее, но на самом деле он создает решение при построении лабиринтов с помощью рекурсивного алгоритма. Он делает это, отслеживая, какая стена была сбита, когда ячейка "введена" во время строительства. Поскольку есть другие алгоритмы, я также включил "find_depth", который устанавливает входную стену для любого лабиринта.

Это достаточно, чтобы вы начали.

Ответ 3

Нерекурсивный способ разрешит вам лабиринт. С рекурсией (backtracking algo) вы можете испытать удачу.

Обратитесь к этому документу: - http://cs.stanford.edu/people/eroberts/courses/cs106b/chapters/07-backtracking-algorithms.pdf

Если этот вопрос будет открыт до уик-энда. Я бы опубликовал закодированный ответ.

Спасибо