|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
22.01.2011, 13:21
|
#16
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: A* и способы его оптимизации
Что значит?
Сообщение от Evgen
что волновой поиск "включается"
|
A* это и есть алгоритм Дейкстры с добавленной эвристикой. Чем лучше функция эвристики выбрана для поставленной задачи - тем эффективнее алгоритм.
|
(Offline)
|
|
22.01.2011, 13:44
|
#17
|
Разработчик
Регистрация: 12.01.2011
Адрес: Moscow
Сообщений: 419
Написано 68 полезных сообщений (для 100 пользователей)
|
Ответ: A* и способы его оптимизации
Да добавлена функция эвристики. Подход может быть разным, а название будет одно и то же.
|
(Offline)
|
|
22.01.2011, 13:54
|
#18
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: A* и способы его оптимизации
Кстати зачем такие сложности в вычислениях?
Пример Dune2 спайса много, харвестер один, пускаем волновую заливку во все стороны пока не наткнемся на спайс.
|
Я бы сделал так:
1. Пробежался бы по всей карте и разделил спайс на зоны.
2. Посчитал расстояние до каждой зоны от каждого сборочного пункта.
3. При отправке харвестера собирать спайс нашел бы ближайшую зону и проложил путь.
Вообще харвестер должен запоминать место своего сбора (зона), если например игрок указал сам где собирать, и возвращаться туда, если в зоне остался спайс.
|
(Offline)
|
|
22.01.2011, 15:26
|
#19
|
.
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений (для 6,863 пользователей)
|
Ответ: A* и способы его оптимизации
В наше время уже давно используют более эффективные поиски пути.
Давно делал концепт, и где-то были наработки:
Скрытый текст (вы должны войти под своим логином или зарегистрироваться и иметь 10 сообщение(ий)):
У вас нет прав, чтобы видеть скрытый текст, содержащийся здесь.
|
ЗЫ, алгоритм ещё упростить можно (2ой пункт, можно почти сразу "соединять" с 3им.).
При этом скорость вычисления отличная, плюс нету ограничений в пространстве (размер) и детали не сильно влияют на производительность. Нужно только разбиение списка на сектора и кластеризация их, для оптимизации количества просчётов.
ЗЫ, крашь тесты делал, без оптимизаций, около кучи 500 отрезков. Поиск не занимал более 5мс (не оптимизированный)!
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
22.01.2011, 15:30
|
#20
|
Дэвелопер
Регистрация: 14.02.2007
Сообщений: 1,471
Написано 824 полезных сообщений (для 2,920 пользователей)
|
Ответ: A* и способы его оптимизации
Чувак, ты изобрел графы и обход их, с чем я тебя и поздравляю.
|
(Offline)
|
|
22.01.2011, 15:51
|
#21
|
.
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений (для 6,863 пользователей)
|
Ответ: A* и способы его оптимизации
Я и не претендовал на то что этого не существует..
|
(Offline)
|
|
22.01.2011, 16:58
|
#22
|
Задрот
Регистрация: 24.07.2009
Адрес: Ивановская область, г. Кинешма
Сообщений: 1,574
Написано 407 полезных сообщений (для 863 пользователей)
|
Ответ: A* и способы его оптимизации
Мока, я тож об таком думал. Подтолкнул идею, буду юзать в своем проекте
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
22.01.2011, 23:48
|
#23
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: A* и способы его оптимизации
Сообщение от MoKa
Я и не претендовал на то что этого не существует..
|
в правом нижнему гулу написано обратное... или нет?
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
23.01.2011, 01:21
|
#24
|
Знающий
Регистрация: 18.02.2008
Сообщений: 276
Написано 121 полезных сообщений (для 299 пользователей)
|
Ответ: A* и способы его оптимизации
Я тоже 5 лет назад пытался изобрести велосипед - векторный поиск по дискретной карте (не знаю как правильно называется). Если кому надо, могу выложить исходники
|
(Offline)
|
|
Эти 4 пользователя(ей) сказали Спасибо wolfhound512 за это полезное сообщение:
|
|
23.01.2011, 02:53
|
#25
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: A* и способы его оптимизации
2wolfhound512
это полезно. тем более - сделаны выводы.
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
23.01.2011, 16:21
|
#26
|
Разработчик
Регистрация: 12.01.2011
Адрес: Moscow
Сообщений: 419
Написано 68 полезных сообщений (для 100 пользователей)
|
Ответ: A* и способы его оптимизации
Сообщение от wolfhound512
Я тоже 5 лет назад пытался изобрести велосипед - векторный поиск по дискретной карте (не знаю как правильно называется). Если кому надо, могу выложить исходники
|
Не думаю, что на дискретной карте, векторный поиск будет работать быстрее чем алгоритм волновой заливки.
|
(Offline)
|
|
23.01.2011, 17:02
|
#27
|
Знающий
Регистрация: 18.02.2008
Сообщений: 276
Написано 121 полезных сообщений (для 299 пользователей)
|
Ответ: A* и способы его оптимизации
На самом деле поиск производится по векторной карте, которая строится на основе дискретной (запусти прикрепленный экзешник). Это делалось под конкретный проект с большими расстояниями, так что прирост должен был быть существенный. Но к сожалению до испытаний на практике дело не дошло.
|
(Offline)
|
|
23.01.2011, 21:39
|
#28
|
Дэвелопер
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений (для 2,419 пользователей)
|
Ответ: A* и способы его оптимизации
wolfhound512, это мне как раз нужно сейчас!!!!1 Именно это!!
Исходники не надо, лучше скажи как это правильно называется!
|
(Offline)
|
|
24.01.2011, 00:50
|
#29
|
.
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений (для 6,863 пользователей)
|
Ответ: A* и способы его оптимизации
Сообщение от impersonalis
в правом нижнему гулу написано обратное... или нет?
|
Скорее относилось к выражению концепции и идеи реализации, а не самого метода поиска пути (плюс к картинке).
|
(Offline)
|
|
24.01.2011, 12:10
|
#30
|
Разработчик
Регистрация: 12.01.2011
Адрес: Moscow
Сообщений: 419
Написано 68 полезных сообщений (для 100 пользователей)
|
Ответ: A* и способы его оптимизации
Сообщение от Den
wolfhound512, это мне как раз нужно сейчас!!!!1 Именно это!!
Исходники не надо, лучше скажи как это правильно называется!
|
Очень похоже на это
http://www.dtf.ru/articles/read.php?id=46788
если, что wolfhound512 поправит.
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо Evgen за это полезное сообщение:
|
den (24.01.2011), pax (24.01.2011)
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 12:08.
|