AI и задачи

Темы, связанные с проектированием и программированием roguelike-игр

Модераторы: Максим Кич, Sanja

Аватара пользователя
Jesus05
Сообщения: 1840
Зарегистрирован: 02 дек 2009, 07:50
Откуда: Норильск, сейчас Санкт-петербург.
Контактная информация:

Re: AI и задачи

Сообщение Jesus05 » 14 ноя 2013, 08:19

Xecutor писал(а):Попробовал посчитать A* ко всем тайлам помеченным для копания в небольшой стартовой пещерке:
Screen Shot 2013-11-14 at 14.59.42.png
Считал от пикселя в центре. Но это не важно.
На моём mac mini в chrome заняло 240ms.
Что есть дохрена... Ща попробую пустить волну..

p.s. в FF на том же mac mini вообще от 500 до 1000ms скачет.
Сделай 100 итераций, и раздели время на 100, мало-ли 240 может это случайность (в большую или меньшую сторону). как и с 500-1000мс.
Волна по идеи должна быть полегче A*

Игра планируется реалтаймовская типа ДФ?
Может все эти тяжелые расчеты вынести в библиотеку С\С++\Java Asm ?

Аватара пользователя
Xecutor
Мастер
Сообщения: 758
Зарегистрирован: 25 мар 2008, 08:32

Re: AI и задачи

Сообщение Xecutor » 14 ноя 2013, 08:56

Jesus05 писал(а): Сделай 100 итераций, и раздели время на 100, мало-ли 240 может это случайность (в большую или меньшую сторону). как и с 500-1000мс.
Волна по идеи должна быть полегче A*
Есс-но я много раз тыкал.
Jesus05 писал(а): Игра планируется реалтаймовская типа ДФ?
Может все эти тяжелые расчеты вынести в библиотеку С\С++\Java Asm ?
Да, по типу DF. Realtime с активной паузой.
Ну оно как бы всё в браузере. Какой такой C++? :)


Погонял волну. В общем и целом наверное приемлимо. На огромной пещере fail происходит в пределах 100ms.
И наверное можно еще заоптимизять.

Аватара пользователя
Jesus05
Сообщения: 1840
Зарегистрирован: 02 дек 2009, 07:50
Откуда: Норильск, сейчас Санкт-петербург.
Контактная информация:

Re: AI и задачи

Сообщение Jesus05 » 14 ноя 2013, 09:18

Xecutor писал(а):Погонял волну. В общем и целом наверное приемлимо. На огромной пещере fail происходит в пределах 100ms.
И наверное можно еще заоптимизять.
Это конечно все из разряда преждевременной оптимизации, но...
Раз есть пауза и в ней наверняка будут отдаваться многие команды, может во время паузы и вести эти расчеты, при большом кол-во объектов расчеты вести в другом потоке (потоки то хоть можно использовать?) ну и не давать отпустить паузу пока ведутся расчеты :( к примеру можно какой-нить индикатор повесить "принудительная пауза" ...

Аватара пользователя
Xecutor
Мастер
Сообщения: 758
Зарегистрирован: 25 мар 2008, 08:32

Re: AI и задачи

Сообщение Xecutor » 14 ноя 2013, 09:33

Ну, тут вычисления будут в реалтайме, ибо инициировать их будут пиксели в поисках работы.

Есть такая штука как WebWorkers. Что-то типа потоков. Насколько это эффективно - ХЗ.

В общем-то волну легко ставить на паузу :)
Сделать отдельный приказ - "поиск куда идти". И выполнять его кусочками, что б не тормозить всё остальное.

Аватара пользователя
Aerton
Сообщения: 503
Зарегистрирован: 11 авг 2007, 02:58
Откуда: Новосибирск
Контактная информация:

Re: AI и задачи

Сообщение Aerton » 14 ноя 2013, 09:36

Xecutor писал(а):На моём mac mini в chrome заняло 240ms.
Что есть дохрена... Ща попробую пустить волну..
p.s. в FF на том же mac mini вообще от 500 до 1000ms скачет.
Что-то дофига - у нас дейкстрой вроде быстрее было. Но тоже не хватало, и мы размазывали поиск на несколько кадров. Можно использовать web workers. Если есть возможность использовать WebGL, то наверное можно исхитриться и написать волну на шейдере - если конечно стоимость пересылки данных не съест весь выигрыш.

При однородной карте можно попробовать jump start - должно быть намного быстрее А*.
kipar писал(а):можно пускать волну (ака карты Дийкстры, вроде бы) от заданий. Тогда любой пиксель будет сразу знать, в какую сторону идти к ближайшему заданию.
Ага, это будет по сути создание политики.
Xecutor писал(а):Мне так кажется, данные нужно обновлять не только при добавлении новых клеток для майнинга,
но и при строительстве зданий, да и вообще при любых действиях меняющих pathing, не?
В идеале да, но сильно ли критично, если в новую дырку народ ломанётся не мнгновенно? Особенно, если большая часть уже занята в этот момент чем-то другим.

Аватара пользователя
Xecutor
Мастер
Сообщения: 758
Зарегистрирован: 25 мар 2008, 08:32

Re: AI и задачи

Сообщение Xecutor » 14 ноя 2013, 10:10

Aerton писал(а): При однородной карте можно попробовать jump start - должно быть намного быстрее А*.
В смысле Jump Point Search? :)
Хм. Карта не однородная. Но для поиска принципиальной проходимости к цели наверное интересный вариант.
Впрочем, пока остановлюсь на волне и отдельном приказе поиска цели. Получилось прикольно. Пиксели, которые ближе к точке копания,
идут копать почти сразу, те которые далеко, задумываются так нехило, а потом идут копать :)
Если сильно далеко, то иногда точка к которой они идут (залочив её предварительно) к моменту прихода остаётся единственной в округе.

Аватара пользователя
Jesus05
Сообщения: 1840
Зарегистрирован: 02 дек 2009, 07:50
Откуда: Норильск, сейчас Санкт-петербург.
Контактная информация:

Re: AI и задачи

Сообщение Jesus05 » 14 ноя 2013, 10:17

Xecutor писал(а):Если сильно далеко, то иногда точка к которой они идут (залочив её предварительно) к моменту прихода остаётся единственной в округе.
В DF такой косяк тоже есть :)

Аватара пользователя
Uvadzucumi
Сообщения: 365
Зарегистрирован: 29 ноя 2011, 07:13
Откуда: Дубай, ОАЭ (Минск, Беларусь)
Контактная информация:

Re: AI и задачи

Сообщение Uvadzucumi » 14 ноя 2013, 10:31

0. Всем запустить волну.(поочередно, с интервалом в пару кадров)
1. Не считать всю волну в отрисовке одного кадра.
2. Останавливать - как нашли ближайший для копания.
2.а. ксли копать одновременно один кусок может только один, то помечаем что занят этот кусок стены (остальные в волне его как непомеченный для копания видят) - отправить копать.
2.б. если копать могут много сразу, то добавляем к колву копающих еще одного и отправляем.
3. при изменении количества нужных для копания кусков
3.а. если выкопали. и есть еще для копания - пересчитать волну освободившимся (содержатся в выкопанно только что куске)
3.б. если добавили новых кусков - посчитать волну для свободных пикселей (если такие есть)

свободные пиксели могу быть - если у нас копают одновременно 1 кусок стены только 1 пиксель, или если волна у него остановилась упершись в стену.
им ничего пересчитывать не нужно!!! ни по какому таймеру!!! только если выкопали что либо и есть еще задачи для раскопок. (ну, а при появлении нового ребенка-пикселя, то ему также сражу на шаг 0).
Меня окружали милые, добрые люди... медленно сжимая кольцо

Аватара пользователя
Shirson
Сообщения: 427
Зарегистрирован: 03 окт 2011, 13:52

Re: AI и задачи

Сообщение Shirson » 14 ноя 2013, 14:31

Xecutor писал(а):Для копания могут быть помечены сотни клеток!
От чего пускать волну?
Ты про то, что может быть отмечен, скажем, блок 10х10?
Хм... Я бы сделал так: Пускаем волну от любого из них. Помеченные на копание стены не препятствуют прохождению волны и всегда отмечаются как нулевая дистанция. Дальше всё по обычным правилам - там где есть проходы, волна пойдёт по ним, отмечая нормальную дистанцию. Любой работник, который придёт по этой волне обратно, с любой стороны, гарантировано на дистанции 1 окажется рядом с блоком, который нужно копать.
Можно еще проще - все клетки для копания сразу занести в дистанцию 0 и пустить волну.

Аватара пользователя
Aerton
Сообщения: 503
Зарегистрирован: 11 авг 2007, 02:58
Откуда: Новосибирск
Контактная информация:

Re: AI и задачи

Сообщение Aerton » 15 ноя 2013, 02:40

Xecutor писал(а):В смысле Jump Point Search? :)
Он самый. Почему-то всегда называю его неправильно.

А ещё может тормоза потому, что для карты волны используется обычный массив JS, а не typed array.

Аватара пользователя
Xecutor
Мастер
Сообщения: 758
Зарегистрирован: 25 мар 2008, 08:32

Re: AI и задачи

Сообщение Xecutor » 15 ноя 2013, 05:41

Aerton писал(а):
Xecutor писал(а):В смысле Jump Point Search? :)
Он самый. Почему-то всегда называю его неправильно.

А ещё может тормоза потому, что для карты волны используется обычный массив JS, а не typed array.
Тормозит массовый A*. Волна, особенно размазанная, вполне приемлимо.

Если волна не находит цель для задачи, я для данного юнита отключаю на несколько секунд эту задачу.
Если есть другие задачи, будет делать их. Если нет, ну потупит чуток. Это уже проблемы игрока.

Аватара пользователя
Xecutor
Мастер
Сообщения: 758
Зарегистрирован: 25 мар 2008, 08:32

Re: AI и задачи

Сообщение Xecutor » 03 дек 2013, 09:17

Такой вопрос.
Есть здание, производящее из ресурса А ресурс Б. Поставлена задача, произвести Х ресурса Б.
У здания в общем-то есть "входящая очередь". Заложили в неё Х ресурса А, здание потихоньку произведёт Х ресурса Б.

Есть рабочий. Хочет приобщиться к этой задаче. Для начала ищет ресурс А. Ок, нашел. А теперь прикол - зданий такого типа 2. Например. К какому ему идти?
Здания я ищу волной. И тут если нашел, то нашел. Если не нашел, то не нашел...
То есть если я, например, буду пытаться найти здание с минимальной очередью, а оно недоступно или очень далеко, то получится хрень, вроде...
Если просто брать ближайшее, то непонятно, как использовать здания в параллель...
Чё-то как-то не могу формальный критерий поиска сформулировать.
Что б "и вашим и нашим" :)
Начинаю думать, что возьмём рандомное, а-ля таунс, не такой уж плохой выбор :)

Аватара пользователя
Cfyz
Сообщения: 776
Зарегистрирован: 30 ноя 2006, 10:03
Откуда: Санкт-Петербург
Контактная информация:

Re: AI и задачи

Сообщение Cfyz » 03 дек 2013, 09:28

Есть неоднозначная идея вводить "административные" юниты/центры, которые будут делать свои специализированные проверки-поиски и раздавать задания простым рабочим. Потому как если все-все пытаться в рабочего положить, в потолок упрется рано или поздно. Ну и модульность, разграничение ответственности, задел на будущую симуляцию бюрократии опять же =)
Пытается раскуклиться

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Re: AI и задачи

Сообщение Максим Кич » 03 дек 2013, 09:39

Что-то мне говорит, что гуглить надо «Теорию массового обслуживания».
Dump the screen? [y/n]

Аватара пользователя
Oreyn
Сообщения: 297
Зарегистрирован: 07 авг 2013, 14:59

Re: AI и задачи

Сообщение Oreyn » 03 дек 2013, 10:15

Xecutor писал(а):Для начала ищет ресурс А. Ок, нашел. А теперь прикол - зданий такого типа 2. Например. К какому ему идти?
Идти к тому, которое и было "заказчиком" этой конкретной задачи "принести ресурс".

Если же у тебя заказ делается не от имени фабрики, а вообще, мол "создайте мне Н ресурса Б в сумме и желательно с паралельной работой всех фабрик которые умеют это делать". То тогда Н заказов распределяется поровну между фабриками и те опять становятся "заказчиками" для конкретной задачи рабочему "принести ресурс".

Xecutor, такое ощущение, что ты ДФ в глаза не видел.

Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 7 гостей