Rambler's Top100
"Knowledge itself is power"
F.Bacon
Поиск | Карта сайта | Помощь | О проекте | ТТХ  
 Сокровищница
  
 

Фильтр по датам

 
 К н и г и
 
Книжная полка
 
 
Библиотека
 
  
  
 


Поиск
 
Поиск по КС
Поиск в статьях
Яndex© + Google©
Поиск книг

 
  
Тематический каталог
Все манускрипты

 
  
Карта VCL
ОШИБКИ
Сообщения системы

 
Форумы
 
Круглый стол
Новые вопросы

 
  
Базарная площадь
Городская площадь

 
   
С Л С

 
Летопись
 
Королевские Хроники
Рыцарский Зал
Глас народа!

 
  
ТТХ
Конкурсы
Королевская клюква

 
Разделы
 
Hello, World!
Лицей

Квинтана

 
  
Сокровищница
Подземелье Магов
Подводные камни
Свитки

 
  
Школа ОБЕРОНА

 
  
Арсенальная башня
Фолианты
Полигон

 
  
Книга Песка
Дальние земли

 
  
АРХИВЫ

 
 

Сейчас на сайте присутствуют:
 
  
 
Во Флориде и в Королевстве сейчас  04:41[Войти] | [Зарегистрироваться]

Обсуждение материала
Алгоритм обхода препятствий
Полный текст материала


Цитата или краткий комментарий:

«... Предлагаемый алгоритм обхода препятствий - это, так называемый, обобщенный алгоритм Дейкстры. В англоязычной литературе он называется алгоритмом A*. ...»


Важно:
  • Страница предназначена для обсуждения материала, его содержания, полезности, соответствия действительности и так далее. Смысл не в разборке, а в приближении к истине :о) и пользе для всех.
  • Любые другие сообщения или вопросы, а так же личные эмоции в адрес авторов и полемика, не относящаяся к теме обсуждаемого материала, будут удаляться без предупреждения авторов, дабы не мешать жителям нормально общаться.
  • При голосовании учитывайте уровень, на который расчитан материал. "Интересность и полезность" имеет смысл оценивать относительно того, кому именно предназначался материал.
  • Размер одного сообщений не должен превышать 5К. Если Вам нужно сказать больше, сделайте это за два раза. Или, что в данной ситуации правильнее, напишите свою статью.
Всегда легче осудить сделанное, нежели сделать самому. Поэтому, пожалуйста, соблюдайте правила Королевства и уважайте друг друга.



Добавить свое мнение.

Результаты голосования
Оценка содержания

  Содержит полезные и(или) интересные сведения
[1]975%
 
  Ничего особенно нового и интересного
[2]325%
 
  Написано неверно (обязательно укажите почему)
[3]00%
 
Всего проголосовали: 12

Оценка стиля изложения

  Все понятно, материал читается легко
[1]975%
 
  Есть неясности в изложении
[2]216.7%
 
  Непонятно написано, трудно читается
[3]18.3%
 
Всего проголосовали: 12




Смотрите также материалы по темам:
[Задачи оптимизации] [Программирование игр.]

Комментарии жителей
Отслеживать это обсуждение

Всего сообщений: 26

05-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;


;-)
 Geo


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:36
2Дмитрий:
У-у-у!!!
А теперь посмотри, что будет происходить в случае одностороннего распространения волны:
Волна дошла до стены и... должна распространятся дальше - ведь путь-то мы должны найти. Т.е. количество итераций будет в 2 раза больше.


02-08-2005 14:28
2Ins:
Внимательно прочитайте пост от 08-03-2005 11:41.


21-07-2005 03:38
Не лучше ли пускать волну и со старта и с финиша?
 Ins


20-07-2005 13:38
2 Leopotam

Процесс проверки с одной стороны до стены - проверили все точки по эту сторону. И процесс проверки с другой стороны - проверили все точки по ту сторону. Т.Е. проверили все точки массива. Вместо того, чтобы проверить только часть (одну сторону) :)))
Да и вообще проверка точек, как бы ни хотел происходит последовательно. Даже в тредах. Так что ускорения не получается, а замедление возможно.

Дмитрий.


29-04-2005 07:07
2 Борис Телеснин:
прошу прощения, не подписался.


29-04-2005 07:04
2 Борис Телеснин:
ну можно кроме укорения и тормоз получить как раз в 2 раза. Достаточно поставить одну длинную стенку между терминальными точками.

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


11-03-2005 14:15
A* уже вполне оптимизирован, можно добавить только следующее:

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
Полезная программа. И скорость, по-моему хорошая.
 vadi


08-10-2002 19:33
Приятная программа! (Особенно приятно, что это программа, причем с понятным результатом и входными данными)
однако странно,у меня она при некоторых условиях вообще не находит путь.(хотя он есть)



29-10-2001 16:05
Приятно...
Приятно, что кто-то этим занимается, есть еще значит люди, для которых программирование - не только инструмент а исскуство...


15-12-2000 18:21
Почитайте учебник по дискретной математике - там все есть


22-06-2000 18:25
   Вы решаете такие задачи ?! Значит программирование для вас не ремесло а исскуство!


Добавьте свое cообщение

Вашe имя:  [Войти]
Ваш адрес (e-mail):На Королевстве все адреса защищаются от спам-роботов
контрольный вопрос:
Раз дощечка, два дощечка будет лесенка. Раз словечко, два словечко, будет ЧТО?
в качестве ответа на вопрос или загадку следует давать только одно слово в именительном падеже и именно в такой форме, как оно используется в оригинале.
Надоело отвечать на странные вопросы? Зарегистрируйтесь на сайте.

Оценка содержания
 
Содержит полезные и(или) интересные сведения
 
Ничего особенно нового и интересного
 
Написано неверно (обязательно укажите почему)


Оценка стиля изложения
 
Все понятно, материал читается легко
 
Есть неясности в изложении
 
Непонятно написано, трудно читается

Текст:
Жирный шрифт  Наклонный шрифт  Подчеркнутый шрифт  Выравнивание по центру  Список  Заголовок  Разделительная линия  Код  Маленький шрифт  Крупный шрифт  Цитирование блока текста  Строчное цитирование
  • вопрос Круглого стола № XXX

  • вопрос № YYY в тесте № XXX Рыцарской Квинтаны

  • сообщение № YYY в теме № XXX Базарной площади
  • обсуждение темы № YYY Базарной площади
  •  
     Правила оформления сообщений на Королевстве
      
    Время на сайте: GMT минус 5 часов

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

    Web hosting for this web site provided by DotNetPark (ASP.NET, SharePoint, MS SQL hosting)  
    Software for IIS, Hyper-V, MS SQL. Tools for Windows server administrators. Server migration utilities  

     
    © При использовании любых материалов «Королевства Delphi» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
    Все используемые на сайте торговые марки являются собственностью их производителей.

    Яндекс цитирования