Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование в широком смысле слова > Алгоритмика

Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения

Ответ
 
Опции темы
Старый 22.01.2011, 13:21   #16
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений
(для 5,323 пользователей)
Ответ: A* и способы его оптимизации

Что значит?
Сообщение от Evgen Посмотреть сообщение
что волновой поиск "включается"
A* это и есть алгоритм Дейкстры с добавленной эвристикой. Чем лучше функция эвристики выбрана для поставленной задачи - тем эффективнее алгоритм.
(Offline)
 
Ответить с цитированием
Старый 22.01.2011, 13:44   #17
Evgen
Разработчик
 
Аватар для Evgen
 
Регистрация: 12.01.2011
Адрес: Moscow
Сообщений: 419
Написано 68 полезных сообщений
(для 100 пользователей)
Ответ: A* и способы его оптимизации

Да добавлена функция эвристики. Подход может быть разным, а название будет одно и то же.
(Offline)
 
Ответить с цитированием
Старый 22.01.2011, 13:54   #18
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений
(для 5,323 пользователей)
Ответ: A* и способы его оптимизации

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

Вообще харвестер должен запоминать место своего сбора (зона), если например игрок указал сам где собирать, и возвращаться туда, если в зоне остался спайс.
(Offline)
 
Ответить с цитированием
Старый 22.01.2011, 15:26   #19
moka
.
 
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений
(для 6,863 пользователей)
Ответ: A* и способы его оптимизации

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


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

ЗЫ, крашь тесты делал, без оптимизаций, около кучи 500 отрезков. Поиск не занимал более 5мс (не оптимизированный)!
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Reizel (22.01.2011)
Старый 22.01.2011, 15:30   #20
Knightmare
Дэвелопер
 
Регистрация: 14.02.2007
Сообщений: 1,471
Написано 824 полезных сообщений
(для 2,920 пользователей)
Ответ: A* и способы его оптимизации

Чувак, ты изобрел графы и обход их, с чем я тебя и поздравляю.
(Offline)
 
Ответить с цитированием
Старый 22.01.2011, 15:51   #21
moka
.
 
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений
(для 6,863 пользователей)
Ответ: A* и способы его оптимизации

Я и не претендовал на то что этого не существует..
(Offline)
 
Ответить с цитированием
Старый 22.01.2011, 16:58   #22
Reizel
Задрот
 
Аватар для Reizel
 
Регистрация: 24.07.2009
Адрес: Ивановская область, г. Кинешма
Сообщений: 1,574
Написано 407 полезных сообщений
(для 863 пользователей)
Ответ: A* и способы его оптимизации

Мока, я тож об таком думал. Подтолкнул идею, буду юзать в своем проекте
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
moka (22.01.2011)
Старый 22.01.2011, 23:48   #23
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Ответ: A* и способы его оптимизации

Сообщение от MoKa Посмотреть сообщение
Я и не претендовал на то что этого не существует..
в правом нижнему гулу написано обратное... или нет?
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Старый 23.01.2011, 01:21   #24
wolfhound512
Знающий
 
Аватар для wolfhound512
 
Регистрация: 18.02.2008
Сообщений: 276
Написано 121 полезных сообщений
(для 299 пользователей)
Ответ: A* и способы его оптимизации

Я тоже 5 лет назад пытался изобрести велосипед - векторный поиск по дискретной карте (не знаю как правильно называется). Если кому надо, могу выложить исходники
Миниатюры
Нажмите на изображение для увеличения
Название: PF.jpg
Просмотров: 822
Размер:	482.4 Кб
ID:	12454  
Вложения
Тип файла: zip GrupsBuild.zip (616.1 Кб, 430 просмотров)
__________________
GUI, GUIw512, AlbaLynx, Форум
(Offline)
 
Ответить с цитированием
Эти 4 пользователя(ей) сказали Спасибо wolfhound512 за это полезное сообщение:
BlackOut (28.01.2011), den (23.01.2011), h1dd3n (23.01.2011), Randomize (23.01.2011)
Старый 23.01.2011, 02:53   #25
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Ответ: A* и способы его оптимизации

2wolfhound512
это полезно. тем более - сделаны выводы.
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
wolfhound512 (23.01.2011)
Старый 23.01.2011, 16:21   #26
Evgen
Разработчик
 
Аватар для Evgen
 
Регистрация: 12.01.2011
Адрес: Moscow
Сообщений: 419
Написано 68 полезных сообщений
(для 100 пользователей)
Ответ: A* и способы его оптимизации

Сообщение от wolfhound512 Посмотреть сообщение
Я тоже 5 лет назад пытался изобрести велосипед - векторный поиск по дискретной карте (не знаю как правильно называется). Если кому надо, могу выложить исходники
Не думаю, что на дискретной карте, векторный поиск будет работать быстрее чем алгоритм волновой заливки.
(Offline)
 
Ответить с цитированием
Старый 23.01.2011, 17:02   #27
wolfhound512
Знающий
 
Аватар для wolfhound512
 
Регистрация: 18.02.2008
Сообщений: 276
Написано 121 полезных сообщений
(для 299 пользователей)
Ответ: A* и способы его оптимизации

На самом деле поиск производится по векторной карте, которая строится на основе дискретной (запусти прикрепленный экзешник). Это делалось под конкретный проект с большими расстояниями, так что прирост должен был быть существенный. Но к сожалению до испытаний на практике дело не дошло.
__________________
GUI, GUIw512, AlbaLynx, Форум
(Offline)
 
Ответить с цитированием
Старый 23.01.2011, 21:39   #28
den
Дэвелопер
 
Аватар для den
 
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений
(для 2,419 пользователей)
Ответ: A* и способы его оптимизации

wolfhound512, это мне как раз нужно сейчас!!!!1 Именно это!!
Исходники не надо, лучше скажи как это правильно называется!
(Offline)
 
Ответить с цитированием
Старый 24.01.2011, 00:50   #29
moka
.
 
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений
(для 6,863 пользователей)
Ответ: A* и способы его оптимизации

Сообщение от impersonalis Посмотреть сообщение
в правом нижнему гулу написано обратное... или нет?
Скорее относилось к выражению концепции и идеи реализации, а не самого метода поиска пути (плюс к картинке).
(Offline)
 
Ответить с цитированием
Старый 24.01.2011, 12:10   #30
Evgen
Разработчик
 
Аватар для Evgen
 
Регистрация: 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)
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Способы уменьшить вес PNG-картинок Sanya MidletPascal 13 09.05.2009 14:25
Способы сжатия графики Phantom FAQ 26 12.10.2008 20:24
Достижения Оптимизации johnk 3D-программирование 42 19.08.2007 13:46
Способы отметить новый год jimon Юмор 1 23.11.2006 23:53
Методы оптимизации MiXaeL FAQ 21 04.10.2006 08:44


Часовой пояс GMT +4, время: 13:40.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com