Как сгенерировать маршрут в массиве координат?

Question

[6ondawave9]

Есть массив элементов по типу

S O O O O
O O O O O
O O O O O
O O O O O
O O O O E

Надо сгенерировать случайный маршрут ведущий из точки S в точку E и соответственно поменять элементы О на, пусть будет, Х.
Типо такого

S O O O O
Х O O O O
Х O O O O
Х O O O O
Х Х Х Х E

Знаем, что элементов всегда 25, в строке всегда 5 элементов и старт и финиш всегда в одном положении. Массив одномерный, но если необходим двумерный, то некритично.
Если будет решение сразу с кодом буду тысячу раз признателен.

И важное уточнение забыл, маршрут может быть диагональным
А-ля
S O O O O
O Х O O O
O O Х O O
O O O Х O
O O O O E

Comments

[Wataru]

Путь нужен кратчайший или зигзаг допустим? Без самопересечений зотя бы (типа буква Р)? Путь может сам себя касаться? Типа, всю матрицу X заполнить подойдет?

[6ondawave9]

Wataru, не кратчайший, главное чтобы вел от старта до финиша и при каждом запуске функции маршрут был новый

[Wataru]

6ondawave9, а остальные вопросы?

[Stalker_RED]

6ondawave9, не может он быть каждый раз новым, там не так много комбинаций. Случайным - может.

[6ondawave9]

Wataru, пардон, без пересечений

[Wataru]

6ondawave9, А самокасание? Всю матрицу заполнить иксами можно - и это весьма вероятный ответ, потому что его можно кучей способов получить. В итоге алгоритм может выдавать одно и то же, хотя это как бы разные пути.

[6ondawave9]

Stalker_RED, понимаю, это и имел ввиду)

[6ondawave9]

Wataru, а если ввести ограничение от 3 до 9 Х? И важное уточнение забыл, маршрут может быть диагональным
А-ля
S O O O O
O Х O O O
O O Х O O
O O O Х O
O O O O E

[Alexandroppolus]

6ondawave9, если ограничиться только шагами "вниз", "вправо" и "вправо-вниз" (каждый раз выбирая случайно из доступных вариантов), то сделать очень просто. Тебе такое норм? Или хочется, чтобы мог и вверх, и влево?

[Wataru]

6ondawave9, Ну и для 9 я бы мог сделать вот так:

S 0 0 0 0
0 X X X 0
0 X X X 0
0 X X X 0
0 0 0 0 S

Эти 9 иксов можно обходить сотней способов.

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

[mayton2019]

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

Вобщем постанока плохая. Надо ее прорабатывать исключая такие вот кейсы. Они не нарушают условий
но и пользы от них нету.

S O O O O
X X O O O
O X X X X 
O X X X X
O O O X E

[6ondawave9]

Alexandroppolus, да, подойдёт, буду очень благодарен

[6ondawave9]

mayton2019, абсолютно верно, задача сгенерировать случайный лабиринт для дальнейшей отрисовки. Структуру данных можно поменять, тк потом развернуть результат в одномерный массив не будет проблемой, я думаю. Подобными задачами ранее никогда не занимался, поэтому могу быть некорректен в формулировках и пояснениях, извиняюсь)

[6ondawave9]

Wataru, задача сгенерировать случайный лабиринт для дальнейшей отрисовки. Структуру данных можно поменять, тк потом развернуть результат в одномерный массив не будет проблемой, я думаю. Подобными задачами ранее никогда не занимался, поэтому могу быть некорректен в формулировках и пояснениях, извиняюсь)

[Модератор]

Не надо ставить как можно больше тэгов. Лучше оставить один, но конкретный, с которым проблема.
См.п.3.1 Регламента.

[Wataru]

6ondawave9, так, уже интереснее. Вам нужен не путь, а лабиринт. С тупиками, возможно, но чтобы был выход. Стены в лабиринте какие: непроходимые клетки или тонкие стены между клетками?

Answer 1

[Alexandroppolus]

function run() {
    const arr = Array.from({length: 5}, () => Array(5).fill('0'));
    
    const pos = [0, 0];
    while(pos[0] !== 4 || pos[1] !== 4) {
        if (pos[0] === 4) {
            pos[1]++;
        } else if (pos[1] === 4) {
            pos[0]++;
        } else {
            const r = Math.floor(Math.random() * 3) + 1;
            if (r & 1) {
                pos[0]++;
            }
            if (r & 2) {
                pos[1]++;
            }
        }
        arr[pos[0]][pos[1]] = 'X';
    }
    arr[0][0] = 'S';
    arr[4][4] = 'E';
    return arr;
}

run()

можешь выполнить в консоли браузера и сразу увидеть результат

Comments

[6ondawave9]

Получается, моя теория верна.
Спасибо большое! То что я себе и представлял)

[Alexandroppolus]

ну да, вместо pos тут можно две отдельные переменные x и y )

[mayton2019]

6ondawave9, капец у тебя память короткая. Мы только что говорили о том что матрица символов не может предтавлять маршрут с заворотами.

Ты хоть протестировал?

[6ondawave9]

mayton2019, наверное не совсем правильно понял, что значит "с заворотами". Протестировал и вроде то, что надо

Answer 2

[6ondawave9]

Полагаю, можно случайно выбирать (с помощью простого рандома) идти вниз или вправо или вправо и вниз одновременно и заполнять таким образом X пока не окажемся у E, проверяя попутно не дошли ли мы до правого или нижнего края. Такой способ должен же работать, верно?