Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Программирование игр, графики и искусственного интеллекта > Пишем сапера

Автор: nuclear 4.3.2005, 15:56

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

Автор: maxim1000 4.3.2005, 16:09

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

Автор: ~FoX~ 4.3.2005, 17:08

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

Автор: maxim1000 4.3.2005, 18:31

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

Автор: S.A.P. 4.3.2005, 18:59

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

Автор: ~FoX~ 4.3.2005, 19:37

Цитата ну нельзя же сразу показывать все пустые клетки А почему все то?

Автор: maxim1000 4.3.2005, 19:50

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

Автор: De Gray 4.3.2005, 20:05

Цитата(maxim1000 @ 4.3.2005, 16:09) можно посмотреть алгоритмы заливки а вообще, если хочется чтобы именно "распахивалась", можно попробовать следующее: 1. делаем очередь 2. помещаем в нее исследуемую точку 3. берем из очереди очередную  точку 4. если она пустая, добавляем в очередь всех необработанных соседей 5. показываем текущую клетку 6. если очередь пустая, заканчиваем 7. переходим на (3) скорее всего (не пробовал), распахивание будет происходить в виде ромба, но на маленьких областях будет похоже на обычную волну Наросал-- открывает ВСЕ пустые клетки, остаются только мины -- бери их голыми руками. По-моему мнению сапер работает в режиме что-то похоже на Идем от означенной точки влево и вправо, пока не встретится точка, в области которой есть 2(?), соприкасающиеся мины -> получили набор точек, от каждой точек из набора идем вверх и вниз, покуда не будет выполнено Цитата пока не встретится точка, в области которой есть 2(?), соприкасающиеся мины . 1 раз. Просто и незатейливо, часть поля открывается на другой интересно играть.

Автор: maxim1000 4.3.2005, 20:10

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

Автор: De Gray 4.3.2005, 20:18

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

Автор: maxim1000 4.3.2005, 20:41

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

Автор: De Gray 5.3.2005, 10:34

Цитата(maxim1000 @ 4.3.2005, 20:41) выпуклая область - для каждой пары точек из этой области в нее входит весь отрезок между ними Издеваемся...

Автор: SPrograMMer 6.3.2005, 11:46

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

Автор: nuclear 6.3.2005, 13:36

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

Автор: De Gray 6.3.2005, 17:41

Цитата(SPrograMMer @ 6.3.2005, 11:46) Все решается ОООООчень просто, рассказать Спой, светик, не стыдись

Автор: SPrograMMer 6.3.2005, 19:09

Цитата(De @ 6.3.2005, 17:41) Спой, светик, не стыдись С удовольствием: пью-пью-пью-пью... Значит, представляем наше поле в виде невзвешенного графа. (что такое граф я думаю понятно) Если взять некую вершину этого графа за корень, то можно пустить волну от этого корня к другим узлам, таким образом, самые ближайшие узлы будут иметь индекс 1, следующие, от 1-ых (да чуть не забыл корень - это 0) но еще не помеченные - 2, и так далее, так можно пройти до любой вершины и решить большое количество задач. Применительно к саперу (поле необязательно представлять в виде графа): при щелчке на ячейку, где нет цифры, мы должны открыть всю область, где этих чифр нет, но смежных с текущей. Делаем так: наша ячейка - корень, помечаем её 0 (да кстати, лучше что быбыло два массива - первый непосредственно поле, в котором в ячейке может быть число от 1-8 - число, 0 - пусто, -1 - мина; и второй - массив, изначально заполненный -1, в котором и будем пускат волну) запоминаем эту ячейку (пара чисел X и Y). Пускаем волну в 4 стороны - влево, вправо, вверх и вниз, если в достугнутой волной полем стоит 0, то есть пусто (это из первого массива), значит во вотором массиве помечаем эту клетку как 0, и теперь данная клетка у нас - вершина, проделываем с ней то ж самое. Когда клетки возле текущей вершины заканчиваются - возвращаемся на уровень ниже - к предыдущей вершине. Как только усе закончится - можно отображать пустые клетки, смотря на второй массив, где ячейки равны 0-ям. Усе!

Автор: maxim1000 7.3.2005, 12:59

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

Автор: nuclear 7.3.2005, 20:43

А не проще ли так. Берем пустую клетку. Осматриваемся вокруг нее. Если в округе есть пустые - добавляем их в массив. Осматриваем первый элемент массива - если есть ИНЫЕ пустые, добавляем их в конец нашего же массива. Осматриваем второй элемент массива - если есть ИНЫЕ пустые, опять добавляем их в конец нашего же массива. И так до тех пор пока не дойдем до конца.

Автор: De Gray 8.3.2005, 12:18

Цитата(nuclear @ 7.3.2005, 20:43) А не проще ли так. Берем пустую клетку. Осматриваемся вокруг нее. Если в округе есть пустые - добавляем их в массив. Осматриваем первый элемент массива - если есть ИНЫЕ пустые, добавляем их в конец нашего же массива. Осматриваем второй элемент массива - если есть ИНЫЕ пустые, опять добавляем их в конец нашего же массива. И так до тех пор пока не дойдем до конца. Цитата maxim1000, только очередь заменена массивом

Автор: @!!ex 8.3.2005, 12:36

Как то вы все не так делаете, только в конце начали нормальные алгоритмы предлагать. ИМХО алгоритм заливки уже лет 15(Со времен появления графики) не меняется.

Автор: De Gray 8.3.2005, 18:09

Цитата Как то вы все не так делаете, только в конце начали нормальные алгоритмы предлагать. ИМХО алгоритм заливки уже лет 15(Со времен появления графики) не меняется. Очень остроумно... учитывая, что в начале и в конце были предложены ОДИНАКОВЫЕ алгоритмы.

Автор: nuclear 10.3.2005, 13:12

Самое печальное, что все свелось примерно к тому что собственно я и реализовал изначально в своей проге. У меня проблема была (и есть) в том, что подобный алгоритм написан на AS, и естесно интерпретирующих скоростей языка явно не хватает. Конечно, все это можно без проблем закодить и на си и на обджект паскале в Делфе - не вопрос. Просто я где-то видел сапера написанного во флеше, где также имеется притормаживание, но оно заметно меньше чем у меня. Возможно я испольжовал ту же идею, но не совсем оптимизировал свой код. Этим собственно и была вынесена тема на обсуждение.

Автор: maxim1000 10.3.2005, 13:22

в том-то и дело, что алгоритм, который я предложил, приводит к тому, что область как бы "распахивается" если надо быстро, то тут есть другие алгоритмы: нечто похожее было предоржено: Цитата(De @ 4.3.2005, 18:05) Идем от означенной точки влево и вправо, пока не встретится точка, в области которой есть 2(?), соприкасающиеся мины -> получили набор точек, от каждой точек из набора идем вверх и вниз, покуда не будет выполнено только надо учесть, что область может быть довольно сложной, а потому придется алгоритм подправить...

Автор: binisio 11.3.2005, 11:11

nuclear у меня тоже была подобная проблема: писал игру на as, думал, что так будет шустрее. тормозило сильно. тот же код на си работал намного быстрее. хороший эффект получается при их совместном использовании: все что касается логики - на с++, а вывод на экран, прорисовку - на as.

Автор: nuclear 11.3.2005, 14:27

binisio можешь объяснить как ты слепил в одно код на си и ас?

Автор: @!!ex 12.3.2005, 19:14

Видимо, я не совсем въезжаю в тему..... Что есть as?

Автор: nuclear 12.3.2005, 20:21

@!!ex ActionScript

Автор: binisio 14.3.2005, 12:28

nuclear сори, я думал речь идет о аssembler

Автор: @!!ex 14.3.2005, 12:39

Цитата(binisio @ 14.3.2005, 12:28) nuclear сори, я думал речь идет о аssembler Я тоже подумал о не допиманном слове asm. Только в контексте с остальным текстом оно ну никак не увязывалось..... поэтому и спросил......... 1) Можно поподробнее об as? 2) Не имеет смысла совмещать ассемблер и С. Дело в том, что в этом случае компилятор не может нормально оптимизировать код. Поэтому нужно либо писать куски на чистом С, либо на чистом асм.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)