forum.boolean.name
Страница 2 из 2 < 1 2
Показывать 64 сообщений этой темы на одной странице

forum.boolean.name (http://forum.boolean.name/index.php)
-   Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)
-   -   A* и способы его оптимизации (http://forum.boolean.name/showthread.php?t=1603)

pax 22.01.2011 13:21
Ответ: A* и способы его оптимизации
 
Что значит?
Цитата:
Сообщение от Evgen (Сообщение 176471)
что волновой поиск "включается"
A* это и есть алгоритм Дейкстры с добавленной эвристикой. Чем лучше функция эвристики выбрана для поставленной задачи - тем эффективнее алгоритм.

Evgen 22.01.2011 13:44
Ответ: A* и способы его оптимизации
 
Да добавлена функция эвристики. Подход может быть разным, а название будет одно и то же.

pax 22.01.2011 13:54
Ответ: A* и способы его оптимизации
 
Кстати зачем такие сложности в вычислениях?
Цитата:
Пример Dune2 спайса много, харвестер один, пускаем волновую заливку во все стороны пока не наткнемся на спайс.
Я бы сделал так:
1. Пробежался бы по всей карте и разделил спайс на зоны.
2. Посчитал расстояние до каждой зоны от каждого сборочного пункта.
3. При отправке харвестера собирать спайс нашел бы ближайшую зону и проложил путь.

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

moka 22.01.2011 15:26
Ответ: A* и способы его оптимизации
 
В наше время уже давно используют более эффективные поиски пути.
Давно делал концепт, и где-то были наработки:
Скрытый текст (вы должны войти под своим логином или зарегистрироваться и иметь 10 сообщение(ий)):
У вас нет прав, чтобы видеть скрытый текст, содержащийся здесь.


ЗЫ, алгоритм ещё упростить можно (2ой пункт, можно почти сразу "соединять" с 3им.).
При этом скорость вычисления отличная, плюс нету ограничений в пространстве (размер) и детали не сильно влияют на производительность. Нужно только разбиение списка на сектора и кластеризация их, для оптимизации количества просчётов.

ЗЫ, крашь тесты делал, без оптимизаций, около кучи 500 отрезков. Поиск не занимал более 5мс (не оптимизированный)!

Knightmare 22.01.2011 15:30
Ответ: A* и способы его оптимизации
 
Чувак, ты изобрел графы и обход их, с чем я тебя и поздравляю.

moka 22.01.2011 15:51
Ответ: A* и способы его оптимизации
 
Я и не претендовал на то что этого не существует..

Reizel 22.01.2011 16:58
Ответ: A* и способы его оптимизации
 
Мока, я тож об таком думал. Подтолкнул идею, буду юзать в своем проекте :)

impersonalis 22.01.2011 23:48
Ответ: A* и способы его оптимизации
 
Цитата:
Сообщение от MoKa (Сообщение 176520)
Я и не претендовал на то что этого не существует..
в правом нижнему гулу написано обратное... или нет?

wolfhound512 23.01.2011 01:21
Ответ: A* и способы его оптимизации
 
Вложений: 2
Я тоже 5 лет назад пытался изобрести велосипед - векторный поиск по дискретной карте (не знаю как правильно называется). Если кому надо, могу выложить исходники

impersonalis 23.01.2011 02:53
Ответ: A* и способы его оптимизации
 
2wolfhound512
это полезно. тем более - сделаны выводы.

Evgen 23.01.2011 16:21
Ответ: A* и способы его оптимизации
 
Цитата:
Сообщение от wolfhound512 (Сообщение 176606)
Я тоже 5 лет назад пытался изобрести велосипед - векторный поиск по дискретной карте (не знаю как правильно называется). Если кому надо, могу выложить исходники
Не думаю, что на дискретной карте, векторный поиск будет работать быстрее чем алгоритм волновой заливки.

wolfhound512 23.01.2011 17:02
Ответ: A* и способы его оптимизации
 
На самом деле поиск производится по векторной карте, которая строится на основе дискретной (запусти прикрепленный экзешник). Это делалось под конкретный проект с большими расстояниями, так что прирост должен был быть существенный. Но к сожалению до испытаний на практике дело не дошло.

den 23.01.2011 21:39
Ответ: A* и способы его оптимизации
 
wolfhound512, это мне как раз нужно сейчас!!!!1 Именно это!!:)
Исходники не надо, лучше скажи как это правильно называется!

moka 24.01.2011 00:50
Ответ: A* и способы его оптимизации
 
Цитата:
Сообщение от impersonalis (Сообщение 176594)
в правом нижнему гулу написано обратное... или нет?
Скорее относилось к выражению концепции и идеи реализации, а не самого метода поиска пути (плюс к картинке).

Evgen 24.01.2011 12:10
Ответ: A* и способы его оптимизации
 
Цитата:
Сообщение от Den (Сообщение 176657)
wolfhound512, это мне как раз нужно сейчас!!!!1 Именно это!!:)
Исходники не надо, лучше скажи как это правильно называется!
Очень похоже на это
http://www.dtf.ru/articles/read.php?id=46788
если, что wolfhound512 поправит.


Часовой пояс GMT +4, время: 07:34.
Страница 2 из 2 < 1 2
Показывать 64 сообщений этой темы на одной странице

vBulletin® Version 3.6.5.
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
Перевод: zCarot