обхождение препятствий

[Ноябрь]

волновой алгоритм и A* это одно и то же?

[Хемуль]

Вот хороший сайт:
http://www.gotoandplay.it
Там есть много полезных статей. В том числе и по алгоритмам поиска пути. Воспользуйтесь поиском.

[gl0om]

я обычно ищу кротчайший путь так:

пробегаемся по массиву карты (если у тебя канечно он есть - если нету, то ничего не машает его построить ), ищем положение движущегося предмета. ЗАписываем в эту ячейку 0. Далее вокруг этого нолика в соседлинх ячейках пишем 1 - если там есть проход.

получается типа
-1-
101
-1-

далее
--2--
-212-
21012
-212-
--2--
в итоге доходим до пунктаназначения.
Далее строим обратный путь от конечной циферки до 0, запоминаем ключи элементов пути.. и уже потом ведем объект по ключам массива до нужной точки.

единственное возможное НО.. тут удобнее всего использовать рекурсию, не знаю есть ли такая возможность в AS

алгоритм сраведлив правда для 4х угольных клеток с одинаковой значимостью прохождения.. но можно и под 6тигранники его заточить

[BigDan]

Этот вопрос я смотрю стал очень актуальным:
http://flasher.ru/forum/showthread.p...E8%F2%EC%EE%E2

[Ноябрь]

2gl0om
на предыдущей странице я писал об этом алгоритме
хороший, но все же для больших карт он не приемлим наверно.., я придумал лучше

[Ноябрь]

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

еще я подумал что вовсе не обязательно просматривать всю карту при волновом алгоритме, при первом шаге достаточно проверить 9 клеток, на втором 25 и т.д, если подумать возможно еще удасться снизить площадь проверки массива.

пс
я прямо исследование провожу)
ппс
как копировать массив?

[gl0om]

Сообщение от Ноябрь

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

еще я подумал что вовсе не обязательно просматривать всю карту при волновом алгоритме, при первом шаге достаточно проверить 9 клеток, на втором 25 и т.д, если подумать возможно еще удасться снизить площадь проверки массива.

пс
я прямо исследование провожу)
ппс
как копировать массив?

ну вообще у меня в примере путь просчитывается 1 раз, нету многократных пробегов по массиву.
Кратчайшее расстояние можно получить только просчитав полностью путь от начала до конца, проверяя вначале малое кол-во клеток можно уйти в другом направлении =). Если карта динамическая, конечно одним просчетом пути не обойтись, но каждый шаг просчитывать не надо, надо сравнивать прошлую координату объектов с текущей, если не совпадает - пересчитываем путь. К томуже если известна конечная и начальная точки - из этих координат можно построить область поиска и не пробегаться по всему массиву карты.

массив копироавть можно везде по всякому..
примитивно можно копировать во вложенном цикле

int a[MAX_ELEMENTS][MAX_ELEMENTS1];
int new_a[MAX_ELEMENTS][MAX_ELEMENTS1];
for (i=0; i<MAX_ELEMENTS; i++){
 for (j=0; j<MAX_ELEMENTS1; j++){
  new_a[i][j]=a[i][j];
 }
}

а можно и так

memcpy(new_a, a, sizeof(a));

но это не про флеш будет сказано =)

[Ноябрь]

ну как это нету..

проверяем массив(карту), если какой-нибуть его элемент равен ноль,
окружающие его элементы приравниваем к одному(если только это не препятствие)
снова проверяем массив(карту), если какой-нибуть его элемент равен один,
окружающие его элементы приравниваем к двум(если только это не препятствие)
снова проверяем массив(карту), если какой-нибуть его элемент равен два,
окружающие его элементы приравниваем к трем(если только это не препятствие)
...:)

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

[gl0om]

ну чтоб ссылку не получить думается мне надо не просто некому "а" присвоить "б". Надо сказать что "а" это новый массив a = new Array() - помоему должно помоч

[iNils]

Одномерный массив копируется с помощью метода concat

arrayA = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
arrayB = arrayA.concat ();
arrayA[0] = 100;
arrayB[0] = 500;
trace (arrayA);
trace (arrayB);