Сапер: теория и практика Опции

[Vinchkovsky]

Здравствуйте
В общем, пишу сапер на Паскале, исключительно сам (впрочем, до этого момента), "от нечего делать", с псевдографикой и без использования приемов ООП.
Возникли два вопроса совершенно разного рода.

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


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

Склоняюсь в верхнему справа, а что думаете вы?

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

Спасибо

Сообщение отредактировано: volvo - 19.02.2009 3:03

[TarasBer]

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

Склоняюсь в верхнему справа, а что думаете вы?

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

[Vinchkovsky]

Естественно левый верхний.

Спасибо, действительно так, удалось подловить такой момент в Сапере стандартном

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

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

и вообще с точки зрения кода чем отличается полный экран от неполного?

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

Спасибо за подсказку

[Clerick]

Здравствуйте!
У меня курсовая основывается на этой игре. Но есть ряд вопросов, например, как генерируется поле?

Сообщение отредактировано: Clerick - 9.10.2009 2:40

[Lapp]

как генерируется поле?

Спасибо за вопрос, 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.

Алгоритм совсем простой - все заполняется за один проход )). И его легко распространить на двумерные массивы. Если что неясно - всегда к вашим услугам, как грится

[andriano]

Спасибо за вопрос, 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]

Спасибо, Lapp! А существует ли какая-либо математическая модель, которая описывает генерацию поля?

Что ты имеешь в виду? Модель - это описание объектов со связями. Какие связи в случайном наборе чисел?.. Далее, математическая модель - это математическое представление чего-то реального, физического. Само по себе минное поле реально, да, отрицать не буду. Его модель в нулевом приближение есть случайный выбор координат. Вот и вся модель. Как именно осуществляется этот выбор - вопрос не модели, а техники.

[andriano]

Уточнение:
В первом приближении мродель реального минного поля - регулярная сетка.
В игре "минер", очевидно, модель иная, - как ты и сказал, случайный выбор координат (правда, опять же, в пределах регулярной сетки).
Другими словами, вопрос о математической модели отнюдь не является праздным.
Что же касается словесного описания математической модели "минного поля" для игры "сапер", то я бы ее описал как двумерное дискретное случайное равномерное распределение.

[Clerick]

И снова здравствуйте. Вопрос все по тому же саперу Разобрался, что требуется. Необходимо сформулировать правила генерации минного поля. Например,

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]

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

Череп не жмет?

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

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

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

В любом случае он отработает идеально (за исключением того, когда заданное число мин больше, чем количество ячеек в матрице). А отработает алгоритм на современной машине за 0.001 или за 0.4 секунды - это не столь принципиально. Не "Томагавк" запускаешь. Там где нужно - экономятся такты (сотруднику соседней лаборатории за то, что он сэкономил 18 тактов при выполнении подпрограммы - если что, это не Windows, это VxWorks - подняли зарплату на 20%). Там где не нужно - пишется так, как удобно.

[Lapp]

Спасибо!

Пожалуйста

[TarasBer]

> Череп не жмет?

ОЛОЛО

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

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

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

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

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

Гарантируешь? Или ты решил, что раз у тебя 1000 раз сработало, то всё нормально? Это логика игродела, а игродел здесь я, а не ты.
А ты, я так понял, пишешь на Аде промышленный софт и должен понимать, что в случае запуска какого-нибудь Тополя (чё за пиндосские Томагавки, я не понял) гарантированные 0.5 (не больше) секунд работы лучше, чем скорее всего 0.001, но может быть, 0.2, а может быть, если не повезёт, то и 10.