Цветные линии

← →
OSokin © (2004-04-30 18:59) [0]

Я пишу игру типа цветных линий, и у меня затык. Как проверить, может ли выбранный шар переместиться в заданную точку, или нет. Поле - 10х10, можно менять. Пять цветов. Алгоритмы типа A* просьба не предлагать. Мне надо что-то компактное и действенное на 100%.

← →
cyborg © (2004-05-01 10:52) [1]

Волновой алгоритм самый простой и гарантированный на 100%.
Смысл такой:
Очищаешь массив, значение непроходимых ячеек устанавливаешь в 255 помечаешь старт, например значением 1, а финиш значением 254, затем проходишься в цикле от 254 до 1 по массиву. Если значение ячейки равное значению прохода цикла, т.е. напр. 254, то вокруг неё, если ячейка ноль, помечаешь на единицу меньше, т.е. вокруг ячейки со значением 254 помечаешь верх, низ, лево и право, если они равны нулю значением 253. и так, пока не дойдёшь до ячейки со значением 1 или пока не закончится цикл. Если дошёл до значения 1, то путь найден, если нет, то пути нет. Далее со старта смотришь, если значение соседней ячейки больше теекущей, то туда двигаешь шарик и так, пока не придёшь в ячейку со значением 254.

Вот, если понятно чего я тут написал ;).

← →
cyborg © (2004-05-01 10:54) [2]

Исправление:

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

← →
MeF88 © (2004-05-02 05:38) [3]

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

А ты уверен, что так ты до финиша дойдешь?

P.S. Классическая задача о поиске пути, решается от перебора с возратом и динамического программирования до алгоритмов поиска во взвешенном графе и алгоритма А*, хотя конечно писать А* для Lines - по-моему изврат.

← →
cyborg © (2004-05-02 09:37) [4]

> А ты уверен, что так ты до финиша дойдешь?

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

← →
Kobik © (2004-05-02 19:15) [5]

>>Алгоритмы типа A* просьба не предлагать
А чем он плох? Если хочешь покомпактнее - то использей простой поиск в ширину. Хотя на самом деле А* - это улучшение того же поиска в ширину - работает он вернее и не намного дольше.

(или под компактностью ты подразумеваешь компактность исходного кода?).

← →
Stalker_23b (2004-05-03 02:15) [6]

Волновой алгоритм должен работать на 100%. Мне кажется, в данной ситуации он оптимален.

← →
OSokin © (2004-05-03 13:22) [7]

Я посмотрел демку с A*, так там процедурка очень большая... И, если можно, дайте небольшой исходничек.

← →
Kobik © (2004-05-03 18:48) [8]

Я когда первый раз пару лет назад посмотрел алгоритм A*, то тоже ничего не понял, но после того, как прослушал в универе курс "Теория графов" все стало предельно ясно.

Достань любую книжку по теории графоф или дискретной оптимизации и не парься.

← →
MeF88 © (2004-05-04 01:10) [9]

> У тебя что, жизнь не удалась или просто делать нечего такие
> вопросы задавать?

=) Алгоритм испортил?

← →
OSokin © (2004-06-08 17:01) [10]

Kobik, плиз подскажи лучше так, чтобы восьмиклассник понял.

← →
Servelat (2004-06-08 18:30) [11]

2 OSokin
Скинул на мыло тебе примерчик, волновой алгоритм, реализация почти дословно того, что сказал cyborg. Вроде все понятно.

← →
kas-t (2004-06-09 03:11) [12]

Я тут тоже решил 3д освоить с Lines, дошел до момента поиска пути, начитался статей, нефига не понял. Распечатал исходники примеров, тоже ничего не мог понять. Наверное дня 3 ходил время от времени пытался придумать не сложный алгоритм поиска пути, пытался сделать методом правой-левой руки, но надоело возиться с условиями, условия еще часто противоречили друг другу, шарик частенько метался вдоль препятствия. Долго вчитывался внимательно в статьи, и в итоге написал поиск пути. Только не знаю, как он называется правильно.

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

Функция поиска получилась всего в 80-90 строк без вычисления кротчайшего пути. Зато 100% работает :)

← →
Evgeniy_K (2004-06-10 16:59) [13]

ВОлновой алгоритм (рекурсивно):
из конечной точки смещаешься по полю и ставишь в поле текущий турн, если поле чистое;
потом просто шагаешь из начала в конец...

Спасибо!

Цветные линии Найти похожие ветки