Системы тайминга, обсуждение

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

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

Аватара пользователя
alexbard
Сообщения: 670
Зарегистрирован: 22 апр 2011, 17:15
Откуда: Украина
Контактная информация:

Re: Системы тайминга, обсуждение

Сообщение alexbard » 19 мар 2012, 09:14

Foxman писал(а):Во вторых игрок должен эту стрелу увидеть, стрела может находиться в неосвещенном месте или за пределами радиуса видимости. Но если карта легла, то почему бы и нет, пусть увернется от стрелы. Он же герой.
подожди, как так получается, что противник имеет прямую для стрельбы по игроку (значит видит игрока, в пределах радиуса видимости), а игрок может не увидеть его ? Т.е. игрок - герой, от стрелы увернуться может, но видит хуже монстра ?
Кстати, противники тоже будут уворачиваться от стрел игрока.

Аватара пользователя
Foxman
Сообщения: 246
Зарегистрирован: 19 янв 2012, 20:30

Re: Системы тайминга, обсуждение

Сообщение Foxman » 19 мар 2012, 09:19

alexbard писал(а):подожди, как так получается, что противник имеет прямую для стрельбы по игроку (значит видит игрока, в пределах радиуса видимости), а игрок может не увидеть его ? Т.е. игрок - герой, от стрелы увернуться может, но видит хуже монстра ? Кстати, противники тоже будут уворачиваться от стрел игрока.
Не вижу противоречий. Монстр может быть в засаде, или иметь инфравидение или еще что. И да, монстр может увернуться от стрелы. И да, вополне реально попытаться убежать от летящего файрбола, а почему нет?

Аватара пользователя
alexbard
Сообщения: 670
Зарегистрирован: 22 апр 2011, 17:15
Откуда: Украина
Контактная информация:

Re: Системы тайминга, обсуждение

Сообщение alexbard » 19 мар 2012, 09:41

Foxman писал(а):Не вижу противоречий. Монстр может быть в засаде, или иметь инфравидение или еще что. И да, монстр может увернуться от стрелы. И да, вополне реально попытаться убежать от летящего файрбола, а почему нет?
Если в твоей системе сначала отсчитывается время, а потом происходят действия, то у тебя все работает отлично и можешь не читать, то что ниже написано.

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

Вот орк выпускает стрелу в игрока
....o->.................@
Для того, что бы долететь до игрока стреле нужно 100 единиц времени, но через 90 единиц к игроку переходит ход (у стрелы сейчас время t и у игрока время t):
.............->...@
и он делает ход в бок, тратя на это 1000 единиц времени:
....................@
.............->......
теперь ход снова передается стреле и она долетает до того места, где был игрок:
....................@
....................->
однако в этот момент игрока уже там нет, потому что он совершил свой ход. Теперь сравним время стрелы, которая находится в координатах x,y и игрока в координатах x,y-1:
у стрелы время t+10, а у игрока t + 1000, т.е. фактически игрок все еще находится в координатах x,y , а не x.y-1.

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

Аватара пользователя
Foxman
Сообщения: 246
Зарегистрирован: 19 янв 2012, 20:30

Re: Системы тайминга, обсуждение

Сообщение Foxman » 19 мар 2012, 10:12

alexbard писал(а): Если описывать этот процесс с помощью аппарата современной физики, то игрок своим перемещением значительно искривляет процесс хода времени вокруг себя. Причем не сам игрок, а просто факт любого действия с его стороны.
Эк вы загнули =) Я понял мысль. Но можно немножко переиграть терминологию и система станет более логичной.
Конечно, если игрок начал движение из (x,y) в (x,y-1) в момент t, то в момент t+1 его "туловко" на 99% все еще на линии удара стрелы.
Но предположим что момент t не момент начала движения, а момент смены координаты (y) на (y-1), то есть "как-будто" игрок начал движение в момент (t-999) и в момент t он полностью сменил координаты.
И я понимаю что это противоречит законам причины и следствия, но это позволяет уворачиваться от стрел и убегать от файрболлов не искривляя существенно пространство и время. Это же игра =)

Аватара пользователя
alexbard
Сообщения: 670
Зарегистрирован: 22 апр 2011, 17:15
Откуда: Украина
Контактная информация:

Re: Системы тайминга, обсуждение

Сообщение alexbard » 19 мар 2012, 10:19

Foxman писал(а): Но предположим что момент t не момент начала движения, а момент смены координаты (y) на (y-1), то есть "как-будто" игрок начал движение в момент (t-999) и в момент t он полностью сменил координаты.
Логичнее тогда просто было бы сделать систему, где ничего не подразумевается, а действительно персонаж сначала ждет сколько нужно времени, а уже только потом совершает действие.

Хотя это ваша игра и вам реализовывать, поэтому все выше написано исключительно на правах "у меня свободное время на работе" =)

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

Re: Системы тайминга, обсуждение

Сообщение Oreyn » 29 сен 2013, 19:34

Небольшой некропост.

Почитал реализации и склоняюсь сделать систему тайминга на приоритетной очереди с двоичной кучей min-heap и накидыванием кулдауна после выполнения действия.

- Берем первый элемент из очереди с наименьшим кулдауном
- Выполняем и он возвращает на сколько нужно увеличить его кулдаун до следующего действия и снова помещаем в очередь с новым приоритетом (чем значение меньше, тем быстрее дойдет очередь до элемента)

Раньше с priority queue не работал (STL C++) и вычитал в спецификации, что ему можно указывать тип контейнера в котором он будет хранить элементы vector или deque. Учитывая, что операций по вставке и удалению элементов будет много правильнее указать двусвязный список deque, так ведь?

HAHAHA DISREGARD THAT ...
Почитал на вики как работает двоичная куча с примерами реализации
http://en.wikipedia.org/wiki/Binary_heap

Там все на свапах элементов реализовано, добавляется/удаляется только последний элемент массива, а потом порядок восстанавливается специальной функцией heapify.
Да и доступ к веткам узла рассчитывается как формулы к номеру индекса в массиве (2i) и (2i +1)
Так что вектор в данном случае будет лучше двусвязного списка.

С другой стороны понял, что не нужно удалять и заново добавлять элемент с новым приоритетом в очередь. Достаточно просто изменить приоритет первого элемента и вызвать ему heapify и он сам "потонет" на нужную позицию. Но штатной возможности это сделать у priority queue нет, что ли самостоятельно ваять велосипед бинарной кучи ?

Да, второй нюанс, значение приоритета элемента, как сумма всех его использованных кулдаунов будет постоянно расти, ведь фактически это отсчет "игрового" времени. Так что или запасаться размерностью переменной, или время от времени устраивать деноминации и перебрасывать элементы во вторую приоритетную очередь и когда опустеет первая менять их местами.
Что думаете, знатоки систем тайминга?

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

Re: Системы тайминга, обсуждение

Сообщение Aerton » 30 сен 2013, 06:13

Если уж делать свой велосипед - то просто поиском минимального элемента в массиве\списке.
Ну или сортировать этот массив\список и брать первый.
Так или иначе, тратить на это больше 15 минут нецелесообразно, особенно на начальном этапе.

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

Re: Системы тайминга, обсуждение

Сообщение Shirson » 30 сен 2013, 13:00

Aerton +1

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

Re: Системы тайминга, обсуждение

Сообщение Xecutor » 30 сен 2013, 13:00

Вообще-то std::map отсортирован по ключу.
Для начала бери его и не парься.

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

Re: Системы тайминга, обсуждение

Сообщение Oreyn » 30 сен 2013, 18:31

Aerton писал(а):Если уж делать свой велосипед - то просто поиском минимального элемента в массиве\списке.
Так бинарная куча это и делает, и якобы наилучшим способом. То есть остальные элементы в массиве не будут строго по порядку уменьшения, но наименьший будет всегда первым.
И про пятнадцать минут, для меня разбор и разработка таких алгоритмов как хобби в удовольствие, а не рабочий проект бегом/бегом.
С другой стороны, конечно, чувствую что хитрости с быстрой сортировкой для 20, ну пусть 100, объектов в списке не особо нужны.
Xecutor писал(а):Вообще-то std::map отсортирован по ключу.
Для начала бери его и не парься.
Тогда уж multimap. Ключи то будут повторяться.

В итоге снял чехлы с бинарного дерева и реализовал его построение на векторе. В отличии от готового std::make_heap могу изменить ключ наименьшего элемента и дать куче переместить его ниже по приоритету без удаления и добавления элемента в очередь заново. Плюс если ключи одинаковые, новоиспеченный элемент проигрывает в приоритете тем элементам, которые уже стоят в очереди.

limit_inferior
Сообщения: 2
Зарегистрирован: 11 фев 2011, 05:09

Re: Системы тайминга, обсуждение

Сообщение limit_inferior » 01 окт 2013, 13:31

Для нескольких персонажей на одном временном слое можно использовать что-то вроде std::map<Time, std::vector<Actor*>>. При переходе на новый слой легко перемешать персонажей на нем, чтобы не было ситуации, когда кто-то постоянно ходит раньше.

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

Re: Системы тайминга, обсуждение

Сообщение Oreyn » 05 ноя 2013, 12:55

Вопрос немного косвенно системы тайминга, и больше о shared/weak pointer, но всё таки.

Дано:
Абстрактный класс cAction с виртуальной функцией "сделать ход" реализует абстракцию - "объект который умеет делать ход". Производные от него классы могут быть монстрами/эффектами длительных заклинаний/пушечными ядрами, абстракцию это не волнует.
Класс cTurnEngine, который занимается определением порядка ходов очереди экземпляров cAction и собственно вызывает их функцию "сделать ход".
И может получиться так, что в процессе своего хода экземпляр cAction будет уничтожен. (Гоблин шагнул на мину, взорвал себя и весь отряд)
В итоге получается дикий вызов delete this. А ведь cTurnEngine ждет возврата из функции объекта "сделай ход", который самоуничтожился. Что собственно и является проблемой.

Хорошо, допустим объект cAction не должен так управлять своим временем жизни, он даст знать менеджеру, который владеет им, что его можно удалять. Но по хорошему тот должен сделать это после того как cTurnEngine получит возврат из функции. Пахнет все reference counting. Поэтому снял чехлы со смарт поинтеров c++11, как и советовал Czyf.

Вариант следующий:
Менеджер, который владеет экземпляром cAction имеет на него shared_ptr.
cTurnEngine, который занимается только определением очередности хода, имеет на cAction только weak_ptr.
На время хода (вызова функции "сделать ход") cTurnEngine создает временный shared_ptr из weak_ptr на cAction.
И если тот должен умереть в процессе хода, он даст знать своему менеджеру, что его можно вычеркивать, и тот сбросит свой shared_ptr. Но объект пока еще будет жив, так как есть еще одна сильная связь от shared_prt движка ходов. Тот благополучно получит код возврата от функции "сделать ход" и сбросит свой shared_ptr. Сильных ссылок на экземпляр объекта осталось ноль и он безопасно удаляется.
Взлетит?

Аватара пользователя
BreakMT
WANDER Team
Сообщения: 933
Зарегистрирован: 27 ноя 2006, 12:16

Re: Системы тайминга, обсуждение

Сообщение BreakMT » 05 ноя 2013, 13:17

Предчувствую багу "ходячих трупов" :-)

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

Re: Системы тайминга, обсуждение

Сообщение Cfyz » 05 ноя 2013, 13:43

Oeryn писал(а):Взлетит?
Вполне. Логика владения выглядит нормально, хотя я не до конца понял архитектуру по приведенному описанию. Упомянутый менеджер что-нибудь еще кроме как хранит ссылки на объекты делает? Или ты имел в виду контейнер?
Пытается раскуклиться

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

Re: Системы тайминга, обсуждение

Сообщение Aerton » 06 ноя 2013, 02:09

Oreyn писал(а):Взлетит?
Слишком перенавороченно.
Не проще ли просто возвращать true/false из "сделай ход" и в таком случае удалять монстра из списка?

Ответить

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

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