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

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

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

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

Ответ
 
Опции темы
Старый 09.05.2015, 16:16   #1
Igor
Мастер
 
Аватар для Igor
 
Регистрация: 03.05.2010
Адрес: Подмосковье
Сообщений: 1,218
Написано 438 полезных сообщений
(для 790 пользователей)
RTS game loop

Пытаюсь понять, как сделать игровой цикл в стретегии с огромным количеством юнитов на карте (как минимум 1к не должно тормозить на телефоне, а лучше 8к и больше). Есть следующие ограничения:
  1. течение игрового времени не зависит от fps и прочих сюрпризов типа сборщика мусора на 30мс
  2. повторяемость. В идеале - разбить игру на "тики", и получить возможность при тех же входных данных получить ровно те же результаты.
  3. длинный тик: есть опасения, что каждый кадр или чаще обновлять состояние каждого юнита не получится - их много, да и аккумулятор экономить надо.
В итоге у меня сформировалась следующая идея:
мир обновляется около пяти раз в секунду, следующее состояние мира детерминировано вычисляется на основе предыдущего состояния и пользовательских действий:
state(x+1) = f(state(x), input)
Поскольку время вычисления следующего состояния может оказаться больше, чем время обновления экрана, я разбиваю карту на куски и первым делом рассчитываю тот кусок, который видит пользователь, и на основе старой и новой позиции юнитов p0 и p1 интерполирую промежуточную как p0 + (p1-p0)*t

Кто пробовал писать rts, поделитесь опытом: как бы вы это сделали?
Какая задержка при отдаче команд юнитам заметна? Тут не старкрафт, несколько сотен раз в минуту в экран тыкать осмысленно вряд ли можно.
__________________
О¯О ¡¡¡ʁɔvʎнdǝʚǝdǝu dиW

Последний раз редактировалось Igor, 09.05.2015 в 17:25.
(Offline)
 
Ответить с цитированием
Старый 09.05.2015, 17:00   #2
Samodelkin
Мастер
 
Регистрация: 12.01.2009
Сообщений: 979
Написано 388 полезных сообщений
(для 631 пользователей)
Ответ: RTS game loop

Опыта разработки RTS нет, но первое что приходит в голову это разделить юнитов стоящих и идущих/сражающихся. Я думаю что вторых в разы меньше, а первых обновлять не надо или очень редко. Предложение с кусками карты, которые видит пользователь, тоже дельное, но я думаю сложнее и его реализовывать надо после выше предложенного. Ещё вроде как в Total War обрабатываются отряды целиком, какими то общими формулами, а если на него смотрит пользователь, то исходя из состояния отряда генерируются отдельные юниты и их действия. По этой причине движок Total War не может симулировать современные сражения, где нет отрядов.
(Offline)
 
Ответить с цитированием
Старый 09.05.2015, 17:37   #3
Nex
Гигант индустрии
 
Аватар для Nex
 
Регистрация: 13.09.2008
Сообщений: 2,893
Написано 1,185 полезных сообщений
(для 3,298 пользователей)
Ответ: RTS game loop

Спустя 4 года отвечаю еще раз.

Сообщение от Igor Посмотреть сообщение
В этой игре как-то очень хитро сделали туман, так как игра не тормозила при 500 и больше юнитов на компах тех времён.
Как они это сделали? Только сейчас задумался...
Сообщение от Nex Посмотреть сообщение
(Offline)
 
Ответить с цитированием
Старый 09.05.2015, 19:23   #4
Igor
Мастер
 
Аватар для Igor
 
Регистрация: 03.05.2010
Адрес: Подмосковье
Сообщений: 1,218
Написано 438 полезных сообщений
(для 790 пользователей)
Ответ: RTS game loop

И так мы получаем, что любой юнит проверяет всего 9 больших ячеек вокруг себя (девятая, это та в которой он сам находится) раз в полторы секунды и если обнаруживается,
Я тоже реализовал карту на основе ячеек. Но даже по твоей ссылке пишут про то, что некоторые действия делаются раз в полторы секунды - т.е., некоторые штуки у них тоже работают небыстро и как-то надо их растягивать на несколько кадров.
__________________
О¯О ¡¡¡ʁɔvʎнdǝʚǝdǝu dиW
(Offline)
 
Ответить с цитированием
Старый 12.01.2017, 22:12   #5
Evgen
Разработчик
 
Аватар для Evgen
 
Регистрация: 12.01.2011
Адрес: Moscow
Сообщений: 419
Написано 68 полезных сообщений
(для 100 пользователей)
Ответ: RTS game loop

Сообщение от Nex Посмотреть сообщение
Спустя 4 года отвечаю еще раз.
Алгоритм похож на тот же что и в земле онимодов

https://astralax.ru/articles/pathway

Чтобы подобный алгоритм повторить, нужно быть крайне продвинутым.
Я бы советовал начать с простого приближения без применения поиска пути, а потом уже пробовать поиск пути.

Пример алгоритма приближения:

if(xtarget>xpos)xpos++;
if(xtarget<xpos)xpos--;
if(ytarget>ypos)ypos++;
if(ytarget<ypos)ypos--;
Алгоритмы приближения разные бывают. Есть улучшенные, которые могут небольшие препятствия обходить. Но против "карманов" из препятствий они бессильны.

А вообще тема разработки RTS очень объемная, там очень много всяких алгоритмов.

Последний раз редактировалось Evgen, 13.01.2017 в 13:58.
(Offline)
 
Ответить с цитированием
Ответ


Опции темы

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

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


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


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