Помощь - Поиск - Пользователи - Календарь
Полная версия: Сапер: теория и практика
Форум «Всё о Паскале» > Pascal, Object Pascal > Написание игр
Vinchkovsky
Здравствуйте wink.gif
В общем, пишу сапер на Паскале, исключительно сам (впрочем, до этого момента), "от нечего делать", с псевдографикой и без использования приемов ООП.
Возникли два вопроса совершенно разного рода.

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

Допустим, все клетки поля не раскрыты. После нажатия клетки, которая "в фокусе" (выделенная зеленым), как должны открыться клетки? У меня варианта три:
Нажмите для просмотра прикрепленного файла
Склоняюсь в верхнему справа, а что думаете вы?

2) Как можно гибко менять размеры окна (не в полноэкранном режиме)? Как я понял, с помощью процедуры TextMode гибкости не получить, я прав?

Спасибо wink.gif
TarasBer
Цитата(Vinchkovsky @ 12.10.2008 16:09) *

Допустим, все клетки поля не раскрыты. После нажатия клетки, которая "в фокусе" (выделенная зеленым), как должны открыться клетки? У меня варианта три:
Нажмите для просмотра прикрепленного файла
Склоняюсь в верхнему справа, а что думаете вы?


Естественно левый верхний.
Гибко менять размер окна на Паскале? В чём эта гибкость должна проявляться и вообще с точки зрения кода чем отличается полный экран от неполного?
Vinchkovsky
Цитата
Естественно левый верхний.

Спасибо, действительно так, удалось подловить такой момент в Сапере стандартном wink.gif
Цитата
Гибко менять размер окна на Паскале? В чём эта гибкость должна проявляться и вообще с точки зрения кода чем отличается полный экран от неполного?

Гибкость в моем понимании - это возможность задания размеров окна более точно, чем текстмодом (хотя тут, возможно, я ошибся и недооценил текстмод, никогда его не использовал). Например, если значение ширины окна может быть задана в виде Х*а (а-некоторая константа), причем Х*а<=Xm - где Хм-максимальное значение ширины, и а значительно (на порядок, напр.) меньше Хм, то тут, по-моему, проявляется гибкость smile.gif
Если на практике - то я про подгонку размера окна под размер игрового поля wink.gif
Цитата
и вообще с точки зрения кода чем отличается полный экран от неполного?

Ничем; почитал хелп по текстмоду и использовав его на практике, понял, что немного ступил (практики маловато, извиняюсь за тавтологию).

Спасибо за подсказку wink.gif
Clerick
Здравствуйте!
У меня курсовая основывается на этой игре. Но есть ряд вопросов, например, как генерируется поле?
Lapp
Цитата(Clerick @ 8.10.2009 22:38) *
как генерируется поле?
Спасибо за вопрос, Clerick! Я как-то раньше не задумывался - плевал, пока не заплюю, с проверкой на повторы.. Но это же жутко неэффективно! Вот, задумался - результат тут:
const
n=10;

var
a: array[1..n]of integer;
i,k: integer;

begin
WriteLn('Total cells: n=',n);
Write('Type in number of cells to fill in (k<=n): k=');
ReadLn(k);
Randomize;
for i:=1 to n do if Random <= k/(n-i+1) then begin
a[i]:=1;
Dec(k)
end
else a[i]:=0;
for i:=1 to n do Write(a[i]);
ReadLn
end.

Алгоритм совсем простой - все заполняется за один проход )). И его легко распространить на двумерные массивы. Если что неясно - всегда к вашим услугам, как грится smile.gif
andriano
Цитата(Lapp @ 9.10.2009 4:16) *

Спасибо за вопрос, 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
Да, согласен. И идея обращения тоже хороша.
Но я хотел подправить свой вариант, и все же это сделаю - а то, он, ко все му прочему, еще и не надежный в таком виде). Так лучше:
const
n=10;

var
a: array[1..n]of integer;
i,k: integer;

begin
WriteLn('Total cells: n=',n);
Write('Type in number of cells to fill in (k<=n): k=');
ReadLn(k);
Randomize;
for i:=1 to n do if Random(n-i+1)<=k-1 then begin
a[i]:=1;
Dec(k)
end
else a[i]:=0;
for i:=1 to n do Write(a[i]);
ReadLn
end.


Clerick
Спасибо, Lapp! А существует ли какая-либо математическая модель, которая описывает генерацию поля?
Lapp
Цитата(Clerick @ 10.10.2009 20:37) *
Спасибо, Lapp! А существует ли какая-либо математическая модель, которая описывает генерацию поля?
Что ты имеешь в виду? Модель - это описание объектов со связями. Какие связи в случайном наборе чисел?.. blink.gif Далее, математическая модель - это математическое представление чего-то реального, физического. Само по себе минное поле реально, да, отрицать не буду. Его модель в нулевом приближение есть случайный выбор координат. Вот и вся модель. Как именно осуществляется этот выбор - вопрос не модели, а техники.
andriano
Уточнение:
В первом приближении мродель реального минного поля - регулярная сетка.
В игре "минер", очевидно, модель иная, - как ты и сказал, случайный выбор координат (правда, опять же, в пределах регулярной сетки).
Другими словами, вопрос о математической модели отнюдь не является праздным.
Что же касается словесного описания математической модели "минного поля" для игры "сапер", то я бы ее описал как двумерное дискретное случайное равномерное распределение.
Clerick
И снова здравствуйте. Вопрос все по тому же саперу smile.gif Разобрался, что требуется. Необходимо сформулировать правила генерации минного поля. Например,
  1. мины не образуют геометрическую фигуру
  2. мина, которая стоит в углу, не может быть окружена другими минами..
  3. не могут быть строки или столбцы состоящие из мин
  4. мина, которая стоит на краю не может быть окружена другими минами

Курсовой говорит, что их больше. Помогите найти их..
Стаян
Помогите.
Я тоже делаю сапер. И столкнулся с ледующей проблемой.
Надо сгенерировать мины.
Генерирую рандомом кооринаты, и некоторые координаты совподают, все мои попытки сделать проверку на равность предыдущим координатам зацикливаются.
Либо всеравно получается меньше мин.

Lapp
Вообще, надо бы приводить хоть кусок кода. Хотя бы чтоб обозначения свои показать..

Допустим, у тебя поле - это массив
f: array [1..n,1..m] of integer;

Допустим, мина в нем обозначается как 1.
Допустим, ты хочешь поставить z мин.
k:=0;
repeat
i:=Random(n)+1;
j:=Random(m)+1;
if f[i,j]=0 then begin
f[i,j]:=1;
Inc(k)
end
until k=z;
Стаян
у мени текстовый вариант сапера. Два символьных массива, одни запоминает, где мины, другой запоминае, что выводить на экран. И вот язадаю мины. В- массив. i,j координаты.

i:=random(10);
j:=random(10);
b[i,j]='@';


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



Добавлено через 13 мин.
Спасибо!
volvo
Зациклить генерацию координат до тех пор, пока не найдено свободное от мин место - никак нельзя догадаться?

repeat
i := random(10);
j := random(10);
until b[i, j] <> '@';
// А вот теперь - запоминаем очередную мину:
b[i, j] := '@';
И все это в цикле столько раз, сколько нужно мин...

P.S. Я надеюсь, ты понимаешь, что при таком способе генерации массив должен быть описан как
var b: array[0 .. 9, 0 .. 9] of char;
, а не 1 .. 10?
Стаян
да у меня там так и есть. Когда я пробывал делать так сам у меня паскаль зацикливался. Он у меня сначала генерировал, присваивалкординаты одномерным числовым массивам, и с ними сравнивал.
TarasBer
> Генерирую рандомом кооринаты, и некоторые координаты совподают, все мои попытки сделать проверку на равность предыдущим координатам зацикливаются.

Дык тут же, в постах выше, уже описаны нужные алгоритмы.

> Зациклить генерацию координат до тех пор, пока не найдено свободное от мин место - никак нельзя догадаться?

Не доверяю я потенциально бесконечным алгоритмам, и всё тут.
А если уж советуешь такое новичкам, то сразу раскажи про принципы работы конгруэнтного генератора, про его цикл, при каких значениях размера поля цикл может никогда не задеть нужную клетку.

И вообще, что твой алгоритм будет делать в таком случае?

Изображение

Хороший алгоритм описан в постах 5-6 - сначала алгоритм, вызывающий ГСЧ для каждой клетки, а потом продвинутый алгоритм, вызывающий ГСЧ ровно столько раз, сколько мин на поле (или сколько свободных клеток, смотря чего меньше).

А на самом деле я, когда сапёра своего писал, не заморачивался и просто ставил мины с определёнными вероятностями. Повезло - хорошее поле попалось, не повезло - плохое.
volvo
Цитата
А если уж советуешь такое новичкам, то сразу раскажи про принципы работы конгруэнтного генератора, про его цикл, при каких значениях размера поля цикл может никогда не задеть нужную клетку.
Череп не жмет? dry.gif

Потенциально (если бояться бесконечных алгоритмов) иди работать дворником...

Цитата
И вообще, что твой алгоритм будет делать в таком случае?
Случай остался загадкой, т.к. картинка убитая...

В любом случае он отработает идеально (за исключением того, когда заданное число мин больше, чем количество ячеек в матрице). А отработает алгоритм на современной машине за 0.001 или за 0.4 секунды - это не столь принципиально. Не "Томагавк" запускаешь. Там где нужно - экономятся такты (сотруднику соседней лаборатории за то, что он сэкономил 18 тактов при выполнении подпрограммы - если что, это не Windows, это VxWorks - подняли зарплату на 20%). Там где не нужно - пишется так, как удобно.
Lapp
Цитата(Стаян @ 24.12.2010 8:48) *
Спасибо!
Пожалуйста
TarasBer
> Череп не жмет?

ОЛОЛО

> Потенциально (если бояться бесконечных алгоритмов) иди работать дворником...

Да ты чё, там же метлой туда сюда, тоже бесконечность.

> Случай остался загадкой, т.к. картинка убитая...

УМВР. Там приведён пример постого генератора (всегда возвращающего 4).

> В любом случае он отработает идеально

Гарантируешь? Или ты решил, что раз у тебя 1000 раз сработало, то всё нормально? Это логика игродела, а игродел здесь я, а не ты.
А ты, я так понял, пишешь на Аде промышленный софт и должен понимать, что в случае запуска какого-нибудь Тополя (чё за пиндосские Томагавки, я не понял) гарантированные 0.5 (не больше) секунд работы лучше, чем скорее всего 0.001, но может быть, 0.2, а может быть, если не повезёт, то и 10.
andriano
Думаю самый простой и достаточно эффективный алгоритм заполнения поля:
- расставить подряд нужное количество мин,
- пробежаться по всем минам и произвести обмен со случайной клеткой поля.
Lapp
Цитата(andriano @ 24.12.2010 22:43) *
Думаю самый простой и достаточно эффективный алгоритм заполнения поля:
- расставить подряд нужное количество мин,
- пробежаться по всем минам и произвести обмен со случайной клеткой поля.

1. Первое действие абсолютно излишне; ничто не мешает ставить мины на места прямо "со склада".
2. Второе действие совершенно прекрасно приводит к исходному вопросу Стаяна в случае, когда "случайная клетка поля" уже занята.

andriano, предлагая "лучший" алгоритм, пожалуйста, указывай, чем тебе не нравятся уже приведенные алгоритмы.
-TarasBer-
Цитата(Lapp @ 25.12.2010 4:19) *

1. Первое действие абсолютно излишне; ничто не мешает ставить мины на места прямо "со склада".


Насчёт излишнести 1 действия я не понял. Приведи код.
Мне кажется, у тебя будут проблемы в случае, когда надо поменять местами 1 и 2 клетки, и на 2й со склада ещё ничего не стоит.
andriano
Цитата(Lapp @ 25.12.2010 4:19) *

1. Первое действие абсолютно излишне; ничто не мешает ставить мины на места прямо "со склада".
Отнюдь.
Разница проявляется в том случае, когда выбранная клетка уже занята. При этом мы не ставим вторую мину в уже занятую клатку, а меняем местами две мины.
Цитата

2. Второе действие совершенно прекрасно приводит к исходному вопросу Стаяна в случае, когда "случайная клетка поля" уже занята.
Второе без первого - да, приводит.
Именно поэтому я и предложил двухэтапную схему, т.к. каждый из этапов поотдельности не приводит к требуемому результату.
Цитата

andriano, предлагая "лучший" алгоритм, пожалуйста, указывай, чем тебе не нравятся уже приведенные алгоритмы.
Я ни в коей мере не утверждал, что лично мне они не нравятся. Просто они подвергались критике со стороны ДРУГИХ участников обсуждения.

В свою очередь могу посоветовать попытаться разобраться в алгоритме прежде, чем чем утверждать, что часть его лишняя, а оставшаяся часть ничем не лучше того, что уже предложено ранее.

PS. Кстати, пересмотрел тему с начала и заметил, что данный прием мною уже предлагался. Поэтому тому, кто задает вопрос посередине обсуждения, все-таки следовало бы прежде прочитать тему с начала.
Lapp
Цитата(-TarasBer- @ 25.12.2010 14:46) *
Насчёт излишнести 1 действия я не понял. Приведи код.
Вот это круто. Просить меня привести код, в то время как алгоритм приведен на уровне "поди туда, не знаю куда". norespect.gif

Цитата
Мне кажется, у тебя будут проблемы в случае, когда надо поменять местами 1 и 2 клетки, и на 2й со склада ещё ничего не стоит.
У меня не было, нет и не будет никаких проблем (по крайней мере, по таким поводам).

Цитата(andriano @ 25.12.2010 16:01) *
Отнюдь.
Разница проявляется в том случае, когда выбранная клетка уже занята. При этом мы не ставим вторую мину в уже занятую клатку, а меняем местами две мины.
Либо я персидский шах, либо - турецкий султан.. Интересно, у тебя уже и мины все разные? У каждой свой номер? или имя? и взрываются по-разному? А если нет - зачем их менять местами?.. blink.gif

Цитата
Второе без первого - да, приводит.
Второе без первого просто не будет работать совсем, если я правильно понимаю алгоритм. Я не предлагал использовать второе без первого.

Цитата
Именно поэтому я и предложил двухэтапную схему, т.к. каждый из этапов поотдельности не приводит к требуемому результату.Я ни в коей мере не утверждал, что лично мне они не нравятся. Просто они подвергались критике со стороны ДРУГИХ участников обсуждения.
Так соотнеси свои слова с этой критикой.

Цитата
В свою очередь могу посоветовать попытаться разобраться в алгоритме прежде, чем чем утверждать, что часть его лишняя, а оставшаяся часть ничем не лучше того, что уже предложено ранее.
...

Цитата
PS. Кстати, пересмотрел тему с начала и заметил, что данный прием мною уже предлагался. Поэтому тому, кто задает вопрос посередине обсуждения, все-таки следовало бы прежде прочитать тему с начала.
Вот, наконец-то, соизволили-с.. Уважаемый andriano, у нас с тобой один раз уже был разговор где ты прекрасно проявил свою профессорскую рассеянность. Рекомендую тебе на будущее ЧИТАТЬ ТЕМЫ, В КОТОРЫЕ ОТВЕЧАЕШЬ. И имей в виду, пожалуйста, что я еще пока ожидаю твоих извинений за тот прецедент.
Гость
Цитата(Lapp @ 26.12.2010 5:59) *

Вот это круто. Просить меня привести код, в то время как алгоритм приведен на уровне "поди туда, не знаю куда".



Алгоритм приведён достаточно точно, чтобы его применить.
Заполняем первые n полей минами, потом for i := 0 to n - 1 do swap(i, i + random(size-i));

> Интересно, у тебя уже и мины все разные? У каждой свой номер?

Одинаковые. Но одна из меняемых клеток может не содержать мину. А может и содержать. А как твой вариант будет это обрабатывать, есть вторая клетка заведомо без мины, и мы её переместим хз куда? Будешь запоминать все перестановки?
-TarasBer-
Забыл имя вписать.
Оказывается, отсутствие имени не вызывает ошибку отправки поста.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.