Решил забацать сапера. Размерность, кол-во бомб и т.д. задаются в начале. Заполняется массив, перемешиваются бомбы, расставляются цифры, ставятся флажки.... Но вот беда, когда кликаем по пустой области, т.е. там где нет ни бомбы ни цифры, нужно "распахнуть" эту область во все уголки. Но так чтобы там где нет прохода граничащая область не распахивалась. Все как в обычном сапере.

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

Может кто писал сапера, дайте идею алгоритма раскрытия пустых клеток с граничащами цифрами.

И еще. Советовать может каждый. Дескать записывай новые клетки .. . проверяй их снова - на деле все гораздо сложнее - нужно проверенные идеи.

Представтьте себе лужу неправильной формы на дороге. Если я кликну на край лужи - она должна вся раскрытся, и если я кликну куда-то в центр, она тоже должна распахнуться во все уголки. Причем соседние лужи не соединяющиеся с данной должны быть закрыты.

можно посмотреть алгоритмы заливки
а вообще, если хочется чтобы именно "распахивалась", можно попробовать следующее:
1. делаем очередь
2. помещаем в нее исследуемую точку
3. берем из очереди очередную точку
4. если она пустая, добавляем в очередь всех необработанных соседей
5. показываем текущую клетку
6. если очередь пустая, заканчиваем
7. переходим на (3)
скорее всего (не пробовал), распахивание будет происходить в виде ромба, но на маленьких областях будет похоже на обычную волну...

nuclear
Я что то не понял......клетки которые не "контактируют" с минами - пустые....вот и показывай их в цикле, пока не наткнешься на границу(клутку контактирующую с миной)

Цитата

Я что то не понял......клетки которые не "контактируют" с минами - пустые....вот и показывай их в цикле, пока не наткнешься на границу(клутку контактирующую с миной)

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

Здесь одной рекурсивной функции хватит. Санируй по 4-м направлениям, при этом проверенные клетки запоминай. Тормозить не будет.

Цитата

ну нельзя же сразу показывать все пустые клетки

А почему все то?

Цитата

клетки которые не "контактируют" с минами - пустые....вот и показывай их в цикле, пока не наткнешься на границу(клутку контактирующую с миной)

Цитата

ну нельзя же сразу показывать все пустые клетки

Цитата

А почему все то?

это меня немного проглючило

Цитата(maxim1000 @ 4.3.2005, 16:09)

можно посмотреть алгоритмы заливки а вообще, если хочется чтобы именно "распахивалась", можно попробовать следующее: 1. делаем очередь 2. помещаем в нее исследуемую точку 3. берем из очереди очередную  точку 4. если она пустая, добавляем в очередь всех необработанных соседей 5. показываем текущую клетку 6. если очередь пустая, заканчиваем 7. переходим на (3) скорее всего (не пробовал), распахивание будет происходить в виде ромба, но на маленьких областях будет похоже на обычную волну

Наросал-- открывает ВСЕ пустые клетки, остаются только мины -- бери их голыми руками.
По-моему мнению сапер работает в режиме что-то похоже на
Идем от означенной точки влево и вправо, пока не встретится точка, в области которой есть 2(?), соприкасающиеся мины -> получили набор точек, от каждой точек из набора идем вверх и вниз, покуда не будет выполнено

Цитата

пока не встретится точка, в области которой есть 2(?), соприкасающиеся мины

. 1 раз. Просто и незатейливо, часть
поля открывается на другой интересно играть.

Цитата

Наросал-- открывает ВСЕ пустые клетки, остаются только мины -- бери их голыми руками

это я виноват: под пустой клеткой я имел в виду клетку, где даже цифра не пишется - т.е. вокруг мин нет

Цитата

Идем от означенной точки влево и вправо, пока не встретится точка, в области которой есть 2(?), соприкасающиеся мины -> получили набор точек, от каждой точек из набора идем вверх и вниз, покуда не будет выполнено

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

Цитата(maxim1000 @ 4.3.2005, 20:10)

не ошибаюсь

Оно самое.Посмотреть -- убрано, чтоб не тормозило вообще.

Цитата(maxim1000 @ 4.3.2005, 20:10)

для невыпуклых областей

1) Почему кольцо -- невупуклая область.
2) Для области образованнной, пространством между 4 -- кольцами(что-то похожее ты имел в виду?)--откроется квдрат, "вписанный в эту область"(Чем меньше открыто, те интереснне играть). Примерно тоже делает и сапер,может ходит туда-сюда-верх-низ ре один раз а 2,3--тоже можно.

Цитата

1) Почему кольцо -- невупуклая область

1. под кольцом я подразумевал большой круг, из которого вырезали маленький (центры общие)
2. выпуклая область - для каждой пары точек из этой области в нее входит весь отрезок между ними
для кольца это не выполняется (например, если точки симметричны относительно центра)

теперь возьмем точку внутри кольца, которая находится на одной горизонтали с центром
из нее пройдемся влево и вправо - получится отрезок, лежащий на радиусе большого круга
от каждой точки этого отрезка пройдемся вверх и вниз - получим всего лишь сегмент большого круга

Цитата

Чем меньше открыто, те интереснне играть

а вот с этим хотелось бы поспорить
данная функция используется как раз для автоматизации одной простой рутинной операции: если вокруг точки нет мин, то нужно открывать все соседние
увеличение доли этих действий в игре как раз снижает ее интерес (задалбывает, проще говоря )

Цитата(maxim1000 @ 4.3.2005, 20:41)

выпуклая область - для каждой пары точек из этой области в нее входит весь отрезок между ними

Издеваемся...

млин... знакомы вы с волновой теорией графов?
Все решается ОООООчень просто, рассказать?

Хотелось бы обратить ваше внимание еще раз на некоторые факты (не все их учитывали):
1. Всегда нужно ориенитроваться на не выпуклые области (выпуклые будут частным случаем)
2. Возможны случаи когда области соединяются не одним перешейком (циклы, кольца и т.д. о которых уже говорилось)
3. Как и в ВинМаин проходом считается случай, если клетки касаются по диагонали.
4. Открывать нужно не только пустые клетки но и цифры рядом с ними.
5. В центре области может быть кольцо из "земли", а внутри опять облатсь-анклав.

Цитата(SPrograMMer @ 6.3.2005, 11:46)

Все решается ОООООчень просто, рассказать

Спой, светик, не стыдись