bugmaker
invulnerable
offline
Опыт:
2,282Активность: |
делаю лог. игру Lines, есть вопросы
Решил забацать логическую игру Lines, столкнулся с проблемкой...
короче если кто знает, чтобы передвинуть шарик из точки A в точку B, он должен пройти по самому кротчайшему пути (т.е. по такому пути, которое занимает минимальное количество ходов). Вот например точка ЖЖ и точка СС, шарику нада сделать 6 ходов чтоб добратся туда, т.к. это прямая линия- это есть кротчайший путь Код:
тут тоже нетрудно, 8 ходов, хотя можно и подругому V Код:
вот так например, хотя ходов все равно 8 Код:
а вот трудности начинаются, когда на пути шарика встают другие, т.е. необходимо обходить их: Код:
инлгда до точки СС добратся не удается т.к. все перекрыто Код:
ну тык вот, я думал-думал, даже пробовал, но либо бажанно, либо никак ни получается огибание других препятствий, если ктонить знает как, то помажите плиз. если че непонятно написал-пишите-спрашивайте... bugmaker добавил: кста, если кто не знает что такое лайнс, выкладываю оригинальную игру скаченную хз откуда... |
18.02.2006, 02:58 | #1
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
NETRAT
offline
Опыт:
83,712Активность: |
bugmaker Лол, простейшая задача на построение дерева достижимости. Я такое делал для ботов пэкмена. Это ты в варе делаешь или где?
NETRAT добавил: Задача - построение и обход дерева в ширину |
18.02.2006, 03:07 | #2
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
bugmaker
invulnerable
offline
Опыт:
2,282Активность: |
в варе.
Цитата:
ну для тя мож и простейшая, мож поконкрентей опишишь плыз... |
|
18.02.2006, 03:10 | #3
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
NETRAT
offline
Опыт:
83,712Активность: |
Все, понял, это в варе. Пока обсудим общий алгоритм, независимо от платформы.
Пускай твоя игра представлена в виде матрицы 8*3(у тебя на картинке так). Обнуляем все ее ячейки в которые можно походить, во всех остальных ставим недостижимые значения(скажем, 1000), заносим в стек начальную ячейку(ЖЖ) и устанавливаем в ней число 1. 1. Перебираем ячейки в стеке и проверяем всех ее соседей в которых можно перейти - то есть в тех, у которых в ячейке матрицы стоит 0, заносим их в стек, в их ячейки заносим число 2, а ту ячейку, которую уже перебрали соседей, удаляем из стека. Таким образом в стеке на первой итерации находятся все ячейки, достижимые из ЖЖ за один шаг и в их значениях находится длинна пути + 1 - то есть число 2. 2. Повторяем итерацию 1 для ячеек которые находятся в стеке, однако в их ячейки заносим уже число 3. И так далее, пока не выполняется одно из условий выхода: 1. В какой-то момент времени мы во время перебора напарываемся на конец пути - ячейку СС, далее даем обратный ход. 2. Стек пуст - значит конечная точка пути недостижима. Обратный ход: Пусть мы попали в точку окончание - СС. Теперь нам нужно быстро вернуться - алгоритм похож на подьем, но нам не нужно закидывать в стек всех соседей, а только того, у которого значение в ячейке минимально NETRAT добавил: Пример разметки Код:
итерация 1 Код:
итерация 2 Код:
итерация 3 Код:
итерация 4 Код:
итерация 5 Код:
итерация 6 Код:
итерация 7 Код:
итерация 8 Код:
итерация 9 Код:
итерация 9 Код:
Достигли точки финала, длина пути = 9, возвращаемся чтобы найти путь: Код:
NETRAT добавил: Надеюсь, суть понятна. Вся сложность сводится к реализации в Варкрафте матрицы и стека, для тебя это не должно составить труда. Алгоритм трудоемкий так как он находит все пути от одной точки до любой другой. Для оптимизации можно использовать встречные движения, но это сложнее... Для крутых лабиринтов размером больше 10*10 может и тормозить... |
18.02.2006, 03:34 | #4
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
bugmaker
invulnerable
offline
Опыт:
2,282Активность: |
Суть ясна. Сетку, матрицу и прочий гемор я уже заготовил ;) как раз 10x10 ( Щаз буду прикидовать как будет выглядеть код. думаю я догнал ), а лаги это не так уж и страшно. биг респект заранее! |
18.02.2006, 03:41 | #5
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
NETRAT
offline
Опыт:
83,712Активность: |
Если что не пойдет, могу своего пекмена поискать на С... Ну тут все просто если представляешь себе что такое дерево и как его обходить =) |
18.02.2006, 12:05 | #6
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Markiz
offline
Опыт:
11,432Активность: |
Алгоритм wave.
В общем-то все как и описал нетрат, только в принципе можно попробовать обход в глубину (читай рекурсия) для лабиринта 10х10 проблем со стеком не должно быть в принципе. функция типа такой: Код:
Нужны функции преобразования индексов есессно. |
19.02.2006, 15:52 | #7
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
NETRAT
offline
Опыт:
83,712Активность: |
Markiz в глубину обход - это полный ацтой - ты найдешь не кратчайший путь, а первый попавшийся
|
19.02.2006, 17:05 | #8
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Markiz
offline
Опыт:
11,432Активность: |
NETRAT
все сообразил. ступил мальца. |
19.02.2006, 20:31 | #9
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
THeBloodiest
offline
Опыт:
20,881Активность: |
Чем вам Астар не нравится? оО |
20.02.2006, 00:34 | #10
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|