IPB
ЛогинПароль:

> алгоритмы на Лабиринте
сообщение
Сообщение #1


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской
Реальное имя: Юра

Репутация: -  1  +


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

Сообщение отредактировано: samec -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской
Реальное имя: Юра

Репутация: -  1  +


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

Сообщение отредактировано: samec -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской
Реальное имя: Юра

Репутация: -  1  +


Цитата(Lapp @ 23.11.2008 21:06) *

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

это обязательно smile.gif
Цитата(Lapp @ 23.11.2008 21:06) *

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

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

Цитата(Lapp @ 23.11.2008 21:06) *

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

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

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

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

Сообщение отредактировано: samec -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 18.05.2024 13:59
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name