XGM Forum - делаю лог. игру Lines, есть вопросы

Все, понял, это в варе. Пока обсудим общий алгоритм, независимо от платформы.
Пускай твоя игра представлена в виде матрицы 8*3(у тебя на картинке так). Обнуляем все ее ячейки в которые можно походить, во всех остальных ставим недостижимые значения(скажем, 1000), заносим в стек начальную ячейку(ЖЖ) и устанавливаем в ней число 1.

1. Перебираем ячейки в стеке и проверяем всех ее соседей в которых можно перейти - то есть в тех, у которых в ячейке матрицы стоит 0, заносим их в стек, в их ячейки заносим число 2, а ту ячейку, которую уже перебрали соседей, удаляем из стека. Таким образом в стеке на первой итерации находятся все ячейки, достижимые из ЖЖ за один шаг и в их значениях находится длинна пути + 1 - то есть число 2.
2. Повторяем итерацию 1 для ячеек которые находятся в стеке, однако в их ячейки заносим уже число 3.
И так далее, пока не выполняется одно из условий выхода:
1. В какой-то момент времени мы во время перебора напарываемся на конец пути - ячейку СС, далее даем обратный ход.
2. Стек пуст - значит конечная точка пути недостижима.

Обратный ход:
Пусть мы попали в точку окончание - СС. Теперь нам нужно быстро вернуться - алгоритм похож на подьем, но нам не нужно закидывать в стек всех соседей, а только того, у которого значение в ячейке минимально

NETRAT добавил:
Пример разметки

Код:

+--+--+--+--+--+--+--+--+
|ЖЖ|->|##|  |  |  |  |  |
+--+--+--+--+--+--+--+--+
|  | V|##|->|->|->|СС|  |
+--+--+--+--+--+--+--+--+
|  | V|->| ^|  |  |  |  |
+--+--+--+--+--+--+--+--+

итерация 1

Код:

99  0  99  0  0  0  0  0
0   0  99  0  0  0  0  0
0   0  0   0  0  0  0  0

итерация 2

Код:

99  1  99  0  0  0  0  0
1   0  99  0  0  0  0  0
0   0  0   0  0  0  0  0

итерация 3

Код:

99  1  99  0  0  0  0  0
1   2  99  0  0  0  0  0
2   0  0   0  0  0  0  0

итерация 4

Код:

99  1  99  0  0  0  0  0
1   2  99  0  0  0  0  0
2   3  0   0  0  0  0  0

итерация 5

Код:

99  1  99  0  0  0  0  0
1   2  99  0  0  0  0  0
2   3  4   0  0  0  0  0

итерация 6

Код:

99  1  99  0  0  0  0  0
1   2  99  0  0  0  0  0
2   3  4   5  0  0  0  0

итерация 7

Код:

99  1  99  0  0  0  0  0
1   2  99  6  0  0  0  0
2   3  4   5  6  0  0  0

итерация 8

Код:

99  1  99  7  0  0  0  0
1   2  99  6  7  0  0  0
2   3  4   5  6  7  0  0

итерация 9

Код:

99  1  99  7  8  0  0  0
1   2  99  6  7  8  0  0
2   3  4   5  6  7  8  0

итерация 9

Код:

99  1  99  7  8  9  0  0
1   2  99  6  7  8  9! 0
2   3  4   5  6  7  8  9

Достигли точки финала, длина пути = 9, возвращаемся чтобы найти путь:

Код:

99  H  99  7  8  9  0  0
1   G  99  6  7  8  9! 0
2   F  E   D  C  B  A  9

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

function Lab takes integer x, integer y, integer lvl, string z returns nothing if (x==GetNeededX()) and (y==GetNeededY()) then set udg_passed=true set udg_path=z return elseif udg_passed then return endif set udg_array[2Dto1D(x,y)]=lvl if udg_array[2Dto1D(x-1,y)]==0 then Lab(x-1,y,lvl+1,z+2Dto1D(x,y)) endif if udg_array[2Dto1D(x+1,y)]==0 then Lab(x+1,y,lvl+1,z+2Dto1D(x,y)) endif if udg_array[2Dto1D(x,y-1)]==0 then Lab(x,y-1,lvl+1,z+2Dto1D(x,y)) endif if udg_array[2Dto1D(x,y+1)]==0 then Lab(x,y+1,lvl+1,z+2Dto1D(x,y)) endif endfunction

Ваши права в разделе

Вы не можете создавать темы

Вы не можете отвечать на сообщения

Вы не можете прикреплять файлы

Вы можете скачивать файлы

BB-коды Вкл.

Смайлики Вкл.

[IMG] код Вкл.

HTML код Выкл.

NETRAT offline Опыт: 83,712 Активность:	bugmaker Лол, простейшая задача на построение дерева достижимости. Я такое делал для ботов пэкмена. Это ты в варе делаешь или где? NETRAT добавил: Задача - построение и обход дерева в ширину
18.02.2006, 03:07	#2 +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: Записан

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: Записан

Опции темы	Поиск в этой теме
Версия для печати	Поиск в этой теме: Расширенный поиск