алгоритмы на Лабиринте Опции

[samec]

Дорое время суток. Есть лабиринт (замкнутых залов - нет). Два входа. Один выход. Где то в лабиринте расположена точка - до которой нужно сначала добраться от входа, потом от этой точки до выхода.
Подскажите, есть ли какой-либо алгоритм расположения точки в лабиринте так, чтобы она была равноудалена (по количеству ходов) от двух входов, но не была слишком близка (тоесть количество ходов от входа до точки было бы больше чем от точки до выхода) к входам.

Сообщение отредактировано: samec - 23.11.2008 22:25

[Lapp]

Хм.. Что-то я не совсем понимаю.. Ты же сказал, что замкнутых циклов нет - так? А значит, путь от каждого входа до выхода однозначен. И путь от входа 1 до входа 2 тоже однозначен. И где-то на этом пути есть точка ответвления на выход:

Код

1 -----
       \
       +-------------- exit
       /
      /
2 ----

(извиняюсь за кривоту)
И если этот тройник расположен на неодинаковом расстоянии от 1 и 2, то уравнять расстояния до входов можно только, если разрешить ходить назад.
Что я не так понял?

[samec]

циклы замкнутые могут присутствовать, нет изолированных комнат - я просто не так выразился, извиняюсь

[Lapp]

циклы замкнутые могут присутствовать, нет изолированных комнат - я просто не так выразился, извиняюсь

А кого вообще волнуют изолированные комнаты? Они - как в другом пространстве... Про них можно не думать.

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

А вообще я думаю, что с алгоритмами (кроме правила одной руки, и то только для плоского лабиринта) в лабиринтах туго..

[samec]

Нужно мне это вот для чего. Пишу игрушку. Два игрока - пользователь и компьютер. Цель игры: добраться до "алмаза" первым и найти с эитм "алмазом" выход из лабиринта. Игроки ходят по очерёдности (подкидывается кубик, выпадает значение - от 1 до 6 - количество ходов). Так вот, хотелось бы расположить этот самый "алмаз" равноудалённо от компьютера и пользователя, чтобы хоть как то уровнять шансы на победу того и другого игрока.
p.s.: лабиринт плоский.

Сообщение отредактировано: samec - 23.11.2008 22:06

[Lapp]

Идея хорошая, мне нравится . Покажешь, когда сделаешь?

Что касается шансов, то все просто. Мне кажется, ты зря взял установку на два входа. Пусть оба заходят с одного входа. Если подерутся - снимай с соревнований .

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

[samec]

Идея хорошая, мне нравится . Покажешь, когда сделаешь?

это обязательно

Что касается шансов, то все просто. Мне кажется, ты зря взял установку на два входа. Пусть оба заходят с одного входа. Если подерутся - снимай с соревнований .

условие задачи подразумевает именно два входа, так что хочешь не хочешь, а придётся делать именно так.

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

Лабиринт я собираюсь генерировать по алгоритму Прима или Краскала - ещё не определился по какому именно, так что самому сделать "те вилы" не получится

Чтобы не создавать новую тему, изменю название у этой и позадаю вопросы тут ещё:
Так вот, ходы пользователя - это пускай сам пользователь думает, как ему "правильнее сходить".
А вот насчет ходов компьютера, я что-то не совсем разобрался - если формировать ходы компьютера по волновому алгоритму - то он всегда, с каждым шагом, будет правильно приближаться к алмазу - ведь этот алгоритм прохода лабиринта даёт наикратчайший путь от точки А до точки B лабиринта - а это резко увеличивает шансы компьютера добраться первым до алмаза, а, соответственно у пользователя шансы на выигрыш таят на глазах... как можно этого избежать?

Добавлено через 6 мин.
про равноудаленность алмаза: можно конечно перебиать все локации лабиринта и искать от них наикратчайший путь до выхода1 и до выхода2 - и если пути по длине одинаковые - то ставить алмаз именно в этой локации... Но ведь может такое случиться - что не будет найдено таких двух наикратчайших путей, что они будут равны? Или обязательно один такой вариант должен попасться??? Только если и так - долго это всё очень...долго...

Сообщение отредактировано: samec - 23.11.2008 22:47

[Lapp]

условие задачи подразумевает именно два входа, так что хочешь не хочешь, а придётся делать именно так.

Я думал, ты сам ставишь условие. Ну, если это задача - тоды ой..

Только если и так - долго это всё очень...долго...

Главное - комп помощнее, и дело в шляпе!

[volvo]

если формировать ходы компьютера по волновому алгоритму - то он всегда, с каждым шагом, будет правильно приближаться к алмазу

Ну, и что? На то она и игра, чтоб пользователь тоже не "тормозил"... Это не поддавки, в конце концов ... Ну, а если серьезно - то можно запускать алгоритм правильного формирования хода не в 100% случаев, а только в 75%, например... А остальные 25% - пусть компьютер ходит согласно датчику случайных чисел (хотя это будет выглядеть еще более неестественно: вроде шел прямо к цели, вдруг побежал куда-то в сторону, а потом опять прямиком к алмазу)