| | | | |
Алгоритм обхода препятствий | Полный текст материала
Цитата или краткий комментарий: «... Предлагаемый алгоритм обхода препятствий - это, так называемый, обобщенный алгоритм Дейкстры. В англоязычной литературе он называется алгоритмом A*.
...» |
Важно:- Страница предназначена для обсуждения материала, его содержания, полезности, соответствия действительности и так далее. Смысл не в разборке, а в приближении к истине :о) и пользе для всех.
- Любые другие сообщения или вопросы, а так же личные эмоции в адрес авторов и полемика, не относящаяся к теме обсуждаемого материала, будут удаляться без предупреждения авторов, дабы не мешать жителям нормально общаться.
- При голосовании учитывайте уровень, на который расчитан материал. "Интересность и полезность" имеет смысл оценивать относительно того, кому именно предназначался материал.
- Размер одного сообщений не должен превышать 5К. Если Вам нужно сказать больше, сделайте это за два раза. Или, что в данной ситуации правильнее, напишите свою статью.
Всегда легче осудить сделанное, нежели сделать самому. Поэтому, пожалуйста, соблюдайте правила Королевства и уважайте друг друга.
Добавить свое мнение.
| | Содержит полезные и(или) интересные сведения | [1] | 9 | 75% | | | | Ничего особенно нового и интересного | [2] | 3 | 25% | | | | Написано неверно (обязательно укажите почему) | [3] | 0 | 0% | | Всего проголосовали: 12 | | | Все понятно, материал читается легко | [1] | 9 | 75% | | | | Есть неясности в изложении | [2] | 2 | 16.7% | | | | Непонятно написано, трудно читается | [3] | 1 | 8.3% | | Всего проголосовали: 12 |
[Задачи оптимизации] [Программирование игр.]
Отслеживать это обсуждение
Всего сообщений: 2605-06-2009 03:35однако, сколько интересных вариантов :) |
|
02-06-2009 07:03Тогда ужу лучше if Odd(k) then... |
|
02-06-2009 04:16>>> поставить еще маленькую проверку в духе
>>> if ((k = 1) or (k = 3) or (k = 5) or (k = 7)) then Continue;
Это как-то не "по-программистски". Наверное, лучше все же как-то так:
if (k and 1) <> 0 then Continue;
;-) |
|
02-06-2009 02:59самый простой способ - это там, где
for k:=1 to 8 do
поставить еще маленькую проверку в духе
if ((k = 1) or (k = 3) or (k = 5) or (k = 7)) then Continue;
Кстати, алгоритм действительно хорош, хоть и требует небольшой доработки, но это мелочи. |
|
08-05-2009 11:42подскажите, пожалуйста, в этом алгоритме можно как-то сделать, чтобы путь не мог строиться по диагонали? Спасибо. |
|
10-09-2005 06:01--Борис Телеснин--
То есть как эта в два раза быстрее, если Вам придется обойти все точки! чтобы убедится в несуществовании пути, а мне заведомо меньше? да еще и в 2 раза? часом не бред? расшифруйте пожалста.
---
:) Ну и что? При обычном подходе - аналогично, только цикл будет крутиться в 2 раза дольше. Я же говорю не про длительность выполнения одной итерации (да, будет дольше), а расчет вообще.
--Борис Телеснин--
Кстати Волной эта всеже трудна назвать так у всех точек фаза разная, - доказать сможем? что путь будет минимальным?
---
:) :) :) Считаем, что фаза первой волны с каждой итерацией увеличивается, начиная с минимального значения (например, 0). Фаза второй волны постоянно уменьшается от какого-то заведомо большого числа. Как только волны встретятся (при анализе находим встречную волну), начинаем с финиша анализировать соседние клетки, постоянно выбирая с минимальным значением - получается минимальный путь. Что тут еще доказывать-то? |
|
05-09-2005 11:28Попдробнее пожалста , как эта ?
--------
т.е. волна будет идти максимум до какого-то среднего числа между начальным и конечным значениями. Получается, что мы в 2 раза быстрее узнаем о неаозможности прохождения
---------
То есть как эта в два раза быстрее, если Вам придется обойти все точки! чтобы убедится в несуществовании пути, а мне заведомо меньше? да еще и в 2 раза? часом не бред? расшифруйте пожалста. Кстати Волной эта всеже трудна назвать так у всех точек фаза разная, - доказать сможем? что путь будет минимальным? |
|
02-08-2005 14:362Дмитрий:
У-у-у!!!
А теперь посмотри, что будет происходить в случае одностороннего распространения волны:
Волна дошла до стены и... должна распространятся дальше - ведь путь-то мы должны найти. Т.е. количество итераций будет в 2 раза больше. |
|
02-08-2005 14:282Ins:
Внимательно прочитайте пост от 08-03-2005 11:41. |
|
21-07-2005 03:38Не лучше ли пускать волну и со старта и с финиша? |
|
20-07-2005 13:382 Leopotam
Процесс проверки с одной стороны до стены - проверили все точки по эту сторону. И процесс проверки с другой стороны - проверили все точки по ту сторону. Т.Е. проверили все точки массива. Вместо того, чтобы проверить только часть (одну сторону) :)))
Да и вообще проверка точек, как бы ни хотел происходит последовательно. Даже в тредах. Так что ускорения не получается, а замедление возможно.
Дмитрий. |
|
29-04-2005 07:072 Борис Телеснин:
прошу прощения, не подписался. |
|
29-04-2005 07:042 Борис Телеснин:
ну можно кроме укорения и тормоз получить как раз в 2 раза. Достаточно поставить одну длинную стенку между терминальными точками.
:) Тормоза не будет. Т.е. волна будет идти максимум до какого-то среднего числа между начальным и конечным значениями. Получается, что мы в 2 раза быстрее узнаем о неаозможности прохождения. А теперь посмотри на стандартный вариант - обходить эту стенку придется в любом случае...Сообщение не подписано |
|
11-03-2005 14:15A* уже вполне оптимизирован, можно добавить только следующее:
1) Не рассчитывать каждый раз весы, а использовать константы
2) Константы весов брать integer: для горизонтали и вертикали = 100, а для диагонали 141 ~ sqrt(2), такой точности будет вполне достаточно
|
|
09-03-2005 03:26>1) Использовать прямоугольный массив данных >вместо связанных списков узлов;
и где ж там связные списки нашлись?
3) Запускать "волну" не только с места старта, но >и с финиша
ну можно кроме укорения и тормоз получить как раз в 2 раза. Достаточно поставить одну длинную стенку между терминальными точками.
|
|
08-03-2005 11:46Тратится время на создание динамического массива? Так его можно создать заранее максимального размера и потом только инициализировать при начале поиска пути. |
|
08-03-2005 11:41Вот возможные варианты ускорения расчета:
1) Использовать прямоугольный массив данных (чем меньше, тем лучше) вместо связанных списков узлов;
2) Использовать только целые величины для указания стоимости прохода (см. математика с фикс. точкой);
3) Запускать "волну" не только с места старта, но и с финиша и ввести проверку на пересечение волн - фактически можно повысить быстродействие почти в 2 раза.
4) Отказаться от расчета стоимости прохода вообще (считать, что она везде одинакова) - не нужно вычислять всякие корни и т.п. Применимо только для квадратных ячеек карты. |
|
15-02-2005 13:01Тока если использовать массив с дин. размерностью - на его создание будет тратится некоторое время. Я реализовывал этот алгоритм на бейсике, тока не A*, а классический - где вместо матрицы используется граф. |
|
15-02-2005 12:57Самое простая оптимизация - это использовать integer, logint вместо real, double, extended. Оптимизация посложнее - pfvtybnm матрицу map[x,y] на массив с динамически изменяемой размерностью, типа как Node в TreeView, тогда намного уменьшится количество проматриваемых узлов. |
|
15-02-2005 07:07
1) Вот функция расстояния между двумя точками на сетке, (работает явно лучше, потому как праильная)
function HEst(A,B: TPoint; dx2,dy2:float): float;
var dx,dy : float;
begin
dx:= A.X - B.X;
dy:= A.Y - B.Y;
Result:= min(abs(dx),abs(dy))*sqrt(2) + abs(dx-dy);
end;
2) иногда маленькая точность может сыграть плохую шутку( в данном случае можна получить незабываемый эффект), посему лучше-
kk[0] := sqrt(2); кстати можно корень оформить отдельной константой - только не жалей точности
3) real не только отжил свое но и всегда медленее чем single, double и extended
4) вместо того чтоб писать map[x,y] десять раз , лучше всеже mapr^
где mapr=@map[x,y]
5) В TBoundRec лучше добавить fval - это сильно ускоряет FindMin() - теперь в ней не надо обращаться к map
Все это вместе дает эффект ускорения порядка
2 раза в худшем случае (обход всех точек)
и 10 раз в лучшем случае
максимальный выигрыш объясняется правильным вычислением расстояния на сетке и тем что 1.42<>sqrt(2)
но основная проблема канешна -
1)в алгоритме, стоит длине кратчайшего пути превысит sqrt(2)*размеркарты и вы получите обход всех точек
2)если путь не существует то опять таки полный обход( правда здесь можна боротся), алгоритм выяснения существования пути(не поиска миним-го) работает на порядок быстрее если пути нет Сообщение не подписано |
|
11-02-2005 12:04Очень полезная программа.
Я давно искал алгоритм нахождения минимального пути для создания поведения ботов в игре. Интересно, существуют ли для этого ещё более быстрые алгоритмы? |
|
25-06-2003 16:03Полезная программа. И скорость, по-моему хорошая. |
|
08-10-2002 19:33Приятная программа! (Особенно приятно, что это программа, причем с понятным результатом и входными данными)
однако странно,у меня она при некоторых условиях вообще не находит путь.(хотя он есть)
|
|
29-10-2001 16:05Приятно...
Приятно, что кто-то этим занимается, есть еще значит люди, для которых программирование - не только инструмент а исскуство... |
|
15-12-2000 18:21Почитайте учебник по дискретной математике - там все есть |
|
22-06-2000 18:25 Вы решаете такие задачи ?! Значит программирование для вас не ремесло а исскуство! |
|
|
|