Подскажите пожалуста алгоритм =(

МИШАНЯ · 18.11.2006, 05:19

В картинке прилагается схематичное изображение.
Красный цвет место находения игрока.
Темно зеленое приграда.
Светло зеленое куда можем идти, в данном случае на 2 гекса. Может и больше.

Подписанна координатная сетка.

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

iNils · 18.11.2006, 05:46

Идти волной. Для этого надо знать каждого соседа у каждого гексагона.
У нас есть гексагон 3:3. В первый проход обходим его соседей: 3:2, 2:2, 2:3, 3:4, 4:3, 4:2. И у каждого проверяем является ли он преградой, если нет, то заносим этот гексагон в массив возможных ходов. Второй проход и опять обходим всех соседей гексагонов из массива, из заносим их туда же, исключая тех кто уже есть в массиве, преграды и начальный гексагон.

МИШАНЯ · 18.11.2006, 05:58

Чет это программно не как не получится.
Рекурсией пробывал, но флешка 255 рекурсий вложенных тока держит, когда много у игрока од, не катит(

FlexBuilder · 18.11.2006, 12:43

Рекурсия тут не обязательна достаточно гонять в цикле пока не кончатся ходы.
Алгоритм:
1. У каждой ячейки может быть состояние (пусто, преграда, заблокировано)
2. Создаем массив МКГВ (массив клеток границы волны)
3. Кладем в массив начальную клетку и блокируем ее.
4. Начинаем цикл. Выход по одному из двух условий - либо кончились ходы (счетчик цикла), либо больше нет клеток в МКГВ.
5. Начинаем цикл по всем клеткам МКГВ
6. Ищем соседей клетки, которые пустые (не заблокированные и не препятствия)
7. Добавляем все эти клетки в массив МКГВ, а саму клетку из него удаляем (делаем это естественно с умом - так чтобы новые клетки попали только в следующий проход цикла (4) - например через дополнительный массив, ограничением индексов и т.д.)
8. Блокируем вновь добавленные клетки.
9. Конец цикла 5
10. Конец цикла 4

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

МИШАНЯ · 19.11.2006, 01:41

екго сказать найди соседий, в этом вся и трудность.
Вот прикинь так выгледит в массиви карта:

iNils · 19.11.2006, 04:09

Ну и чего сложного?
У любой ячейки (i, j) соседи будут:
1. i-1, j-1
2. i-1, j
3. i-1, j+1
4. i, j-1
5. i, j+1
6. i+1, j-1
7. i+1, j
8. i+1, j+1
Естественно если индекс выходит за пределы диапазона, мы откидываем такую ячейку.

МИШАНЯ · 19.11.2006, 04:21

А если объект стоит в 4:4, то 3 и 8 не пожходят для его соседий.

iNils · 19.11.2006, 04:58

Цитата:

Сообщение от МИШАНЯ

А если объект стоит в 4:4, то 3 и 8 не пожходят для его соседий.

См. последнею строку в моем посте.

МИШАНЯ · 19.11.2006, 21:01

Так насчет определения соседий сделал, через четность не четность.
Пожалуста поясните как технически организовать обход волной (точнее кольцами), а точ е то не получается(

FlexBuilder · 20.11.2006, 01:35

я все написал выше