Сапер: теория и практика |
Сапер: теория и практика |
Vinchkovsky |
12.10.2008 15:09
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 98 Пол: Мужской Реальное имя: Andriy Репутация: 0 |
Здравствуйте
В общем, пишу сапер на Паскале, исключительно сам (впрочем, до этого момента), "от нечего делать", с псевдографикой и без использования приемов ООП. Возникли два вопроса совершенно разного рода. 1) На поле есть такая ситуация (создавал в Paint, правя другое расположение мин, так что если есть какие-то несоответствия - извиняйте. Отдельное извинение за качество, случайно сохранил в .джпг, что мог - то подправил. Ну и английский ): Допустим, все клетки поля не раскрыты. После нажатия клетки, которая "в фокусе" (выделенная зеленым), как должны открыться клетки? У меня варианта три: Склоняюсь в верхнему справа, а что думаете вы? 2) Как можно гибко менять размеры окна (не в полноэкранном режиме)? Как я понял, с помощью процедуры TextMode гибкости не получить, я прав? Спасибо Сообщение отредактировано: volvo - 18.02.2009 23:03 |
TarasBer |
12.10.2008 20:16
Сообщение
#2
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Допустим, все клетки поля не раскрыты. После нажатия клетки, которая "в фокусе" (выделенная зеленым), как должны открыться клетки? У меня варианта три: Склоняюсь в верхнему справа, а что думаете вы? Естественно левый верхний. Гибко менять размер окна на Паскале? В чём эта гибкость должна проявляться и вообще с точки зрения кода чем отличается полный экран от неполного? -------------------- |
Vinchkovsky |
12.10.2008 20:54
Сообщение
#3
|
Пионер Группа: Пользователи Сообщений: 98 Пол: Мужской Реальное имя: Andriy Репутация: 0 |
Цитата Естественно левый верхний. Спасибо, действительно так, удалось подловить такой момент в Сапере стандартном Цитата Гибко менять размер окна на Паскале? В чём эта гибкость должна проявляться и вообще с точки зрения кода чем отличается полный экран от неполного? Гибкость в моем понимании - это возможность задания размеров окна более точно, чем текстмодом (хотя тут, возможно, я ошибся и недооценил текстмод, никогда его не использовал). Например, если значение ширины окна может быть задана в виде Х*а (а-некоторая константа), причем Х*а<=Xm - где Хм-максимальное значение ширины, и а значительно (на порядок, напр.) меньше Хм, то тут, по-моему, проявляется гибкость Если на практике - то я про подгонку размера окна под размер игрового поля Цитата и вообще с точки зрения кода чем отличается полный экран от неполного? Ничем; почитал хелп по текстмоду и использовав его на практике, понял, что немного ступил (практики маловато, извиняюсь за тавтологию). Спасибо за подсказку |
Clerick |
8.10.2009 22:38
Сообщение
#4
|
студент.. Группа: Пользователи Сообщений: 287 Пол: Мужской Реальное имя: Дмитрий Репутация: 2 |
Здравствуйте!
У меня курсовая основывается на этой игре. Но есть ряд вопросов, например, как генерируется поле? Сообщение отредактировано: Clerick - 8.10.2009 22:40 -------------------- После дождя обязательно выглянет солнце)
|
Lapp |
9.10.2009 3:16
Сообщение
#5
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
как генерируется поле? Спасибо за вопрос, Clerick! Я как-то раньше не задумывался - плевал, пока не заплюю, с проверкой на повторы.. Но это же жутко неэффективно! Вот, задумался - результат тут:const Алгоритм совсем простой - все заполняется за один проход )). И его легко распространить на двумерные массивы. Если что неясно - всегда к вашим услугам, как грится -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
andriano |
9.10.2009 7:27
Сообщение
#6
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
Спасибо за вопрос, Clerick! Я как-то раньше не задумывался - плевал, пока не заплюю, с проверкой на повторы.. Но это же жутко неэффективно! Вот, задумался - результат тут...: Есть такая статья, "Оптимизация – ваш злейший враг" http://www.rsdn.ru/article/philosophy/Optimization.xml Там речь немного о другом, но заголовок идеально подходит к данному случаю. В любом случае, если уж мы хотим оптимизировать, то должны сперва разобраться, а где же у нас узкое место. В даном случае, очевидно, наиболее ресурсоемкой операцией является получение очередного ПСЧ. Да и весь цикл повторяется столько раз, сколько ячеек в поле. По всей видимости, данный алгоритм должен заменить тот, в котором "метки" случайно набрасываются в поле с проверкой, не занята ли она уже. Оцеки показывают, что количество проходов цикла и, соответственно, количество обращений к ДПСЧ будет меньше именно в исходном варианте при проценте заполнения не превосходящем примерно 60-67% (точно считать лень), т.е. алгоритм, предлагаемый как более эффективный, на самом деле имеет существенно меньшую эффективность. По краней мере, в большинстве случаев, когда процент заполнения менее упомянутых 60-67%. Если же процент заполнения больше, то задачу можно "перевернуть" и выбрасывать при помощи ДПСЧ "непомеченные" ячейки. Таким образом, исходный алгоритм в слегка откорректированном виде будет ВСЕГДА эфективнее предложенного. Пойдем дальше. Можно ведт придумать алгоритм, в котором вызовов ДПСЧ будет РОВНО столько, сколько нужно помеченных клеток - и ни одной больше. Навскидку могу предложить следующий (правда, не проверял его на качество распределения): Нужно пометить K клеток из N, K < N. 1. В массиве заполняем первые K клеток, а остальные N-K оставляем пустыми. 2. Проходим циклом по первым K клеткам, для каждой находим случайное число в интервале [1..N] и обмениваем содержимое текущей [i] ячейки и ячейки с номером, соответствубщим выпавшему ПСЧ (для определенности - массив нумеруется с 1). |
Lapp |
9.10.2009 8:33
Сообщение
#7
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Да, согласен. И идея обращения тоже хороша.
Но я хотел подправить свой вариант, и все же это сделаю - а то, он, ко все му прочему, еще и не надежный в таком виде). Так лучше: const -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Clerick |
10.10.2009 19:37
Сообщение
#8
|
студент.. Группа: Пользователи Сообщений: 287 Пол: Мужской Реальное имя: Дмитрий Репутация: 2 |
Спасибо, Lapp! А существует ли какая-либо математическая модель, которая описывает генерацию поля?
-------------------- После дождя обязательно выглянет солнце)
|
Lapp |
11.10.2009 5:38
Сообщение
#9
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Спасибо, Lapp! А существует ли какая-либо математическая модель, которая описывает генерацию поля? Что ты имеешь в виду? Модель - это описание объектов со связями. Какие связи в случайном наборе чисел?.. Далее, математическая модель - это математическое представление чего-то реального, физического. Само по себе минное поле реально, да, отрицать не буду. Его модель в нулевом приближение есть случайный выбор координат. Вот и вся модель. Как именно осуществляется этот выбор - вопрос не модели, а техники.-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
andriano |
11.10.2009 9:39
Сообщение
#10
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
Уточнение:
В первом приближении мродель реального минного поля - регулярная сетка. В игре "минер", очевидно, модель иная, - как ты и сказал, случайный выбор координат (правда, опять же, в пределах регулярной сетки). Другими словами, вопрос о математической модели отнюдь не является праздным. Что же касается словесного описания математической модели "минного поля" для игры "сапер", то я бы ее описал как двумерное дискретное случайное равномерное распределение. |
Clerick |
16.05.2010 20:34
Сообщение
#11
|
студент.. Группа: Пользователи Сообщений: 287 Пол: Мужской Реальное имя: Дмитрий Репутация: 2 |
И снова здравствуйте. Вопрос все по тому же саперу Разобрался, что требуется. Необходимо сформулировать правила генерации минного поля. Например,
Курсовой говорит, что их больше. Помогите найти их.. -------------------- После дождя обязательно выглянет солнце)
|
Стаян |
24.12.2010 7:40
Сообщение
#12
|
Группа: Пользователи Сообщений: 3 Пол: Мужской Репутация: 0 |
Помогите.
Я тоже делаю сапер. И столкнулся с ледующей проблемой. Надо сгенерировать мины. Генерирую рандомом кооринаты, и некоторые координаты совподают, все мои попытки сделать проверку на равность предыдущим координатам зацикливаются. Либо всеравно получается меньше мин. |
Lapp |
24.12.2010 8:04
Сообщение
#13
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Вообще, надо бы приводить хоть кусок кода. Хотя бы чтоб обозначения свои показать..
Допустим, у тебя поле - это массив f: array [1..n,1..m] of integer; Допустим, мина в нем обозначается как 1. Допустим, ты хочешь поставить z мин. k:=0; -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Стаян |
24.12.2010 8:48
Сообщение
#14
|
Группа: Пользователи Сообщений: 3 Пол: Мужской Репутация: 0 |
у мени текстовый вариант сапера. Два символьных массива, одни запоминает, где мины, другой запоминае, что выводить на экран. И вот язадаю мины. В- массив. i,j координаты.
получается меньше мин из за совпадения координат. Добавлено через 13 мин. Спасибо! |
volvo |
24.12.2010 9:07
Сообщение
#15
|
Гость |
Зациклить генерацию координат до тех пор, пока не найдено свободное от мин место - никак нельзя догадаться?
repeatИ все это в цикле столько раз, сколько нужно мин... P.S. Я надеюсь, ты понимаешь, что при таком способе генерации массив должен быть описан как var b: array[0 .. 9, 0 .. 9] of char;, а не 1 .. 10? |
Стаян |
24.12.2010 9:12
Сообщение
#16
|
Группа: Пользователи Сообщений: 3 Пол: Мужской Репутация: 0 |
да у меня там так и есть. Когда я пробывал делать так сам у меня паскаль зацикливался. Он у меня сначала генерировал, присваивалкординаты одномерным числовым массивам, и с ними сравнивал.
|
TarasBer |
24.12.2010 10:42
Сообщение
#17
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
> Генерирую рандомом кооринаты, и некоторые координаты совподают, все мои попытки сделать проверку на равность предыдущим координатам зацикливаются.
Дык тут же, в постах выше, уже описаны нужные алгоритмы. > Зациклить генерацию координат до тех пор, пока не найдено свободное от мин место - никак нельзя догадаться? Не доверяю я потенциально бесконечным алгоритмам, и всё тут. А если уж советуешь такое новичкам, то сразу раскажи про принципы работы конгруэнтного генератора, про его цикл, при каких значениях размера поля цикл может никогда не задеть нужную клетку. И вообще, что твой алгоритм будет делать в таком случае? Хороший алгоритм описан в постах 5-6 - сначала алгоритм, вызывающий ГСЧ для каждой клетки, а потом продвинутый алгоритм, вызывающий ГСЧ ровно столько раз, сколько мин на поле (или сколько свободных клеток, смотря чего меньше). А на самом деле я, когда сапёра своего писал, не заморачивался и просто ставил мины с определёнными вероятностями. Повезло - хорошее поле попалось, не повезло - плохое. -------------------- |
volvo |
24.12.2010 12:02
Сообщение
#18
|
Гость |
Цитата А если уж советуешь такое новичкам, то сразу раскажи про принципы работы конгруэнтного генератора, про его цикл, при каких значениях размера поля цикл может никогда не задеть нужную клетку. Череп не жмет? Потенциально (если бояться бесконечных алгоритмов) иди работать дворником... Цитата И вообще, что твой алгоритм будет делать в таком случае? Случай остался загадкой, т.к. картинка убитая...В любом случае он отработает идеально (за исключением того, когда заданное число мин больше, чем количество ячеек в матрице). А отработает алгоритм на современной машине за 0.001 или за 0.4 секунды - это не столь принципиально. Не "Томагавк" запускаешь. Там где нужно - экономятся такты (сотруднику соседней лаборатории за то, что он сэкономил 18 тактов при выполнении подпрограммы - если что, это не Windows, это VxWorks - подняли зарплату на 20%). Там где не нужно - пишется так, как удобно. |
Lapp |
24.12.2010 12:08
Сообщение
#19
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
TarasBer |
24.12.2010 12:14
Сообщение
#20
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
> Череп не жмет?
ОЛОЛО > Потенциально (если бояться бесконечных алгоритмов) иди работать дворником... Да ты чё, там же метлой туда сюда, тоже бесконечность. > Случай остался загадкой, т.к. картинка убитая... УМВР. Там приведён пример постого генератора (всегда возвращающего 4). > В любом случае он отработает идеально Гарантируешь? Или ты решил, что раз у тебя 1000 раз сработало, то всё нормально? Это логика игродела, а игродел здесь я, а не ты. А ты, я так понял, пишешь на Аде промышленный софт и должен понимать, что в случае запуска какого-нибудь Тополя (чё за пиндосские Томагавки, я не понял) гарантированные 0.5 (не больше) секунд работы лучше, чем скорее всего 0.001, но может быть, 0.2, а может быть, если не повезёт, то и 10. -------------------- |
Текстовая версия | 30.09.2024 20:45 |