Тема: Як в іграх оброблюють тисячі об'єктів без затримок?

Оце подивився відео гри "Козаки 3" і задумався. Ще якщо колись в першій версії ліміт на війська був до 8 тисяч і це все працювало на стареньких комп'ютерах (+ передача команд по мережі), то зараз до 10 тисяч юнітів + поліпшена графіка + літають різні снаряди, стріли.... Тут явно не простий цикл проходить по всіх об'єктах і щось з ними робить. Ось власне питанння - як???
Можна змоделювати на якійсь простій програмі - типу життя бактерій (будемо зображувати їх точками), вони рандомно рухаються по екрану і плодяться.

2

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

Не забувайте, що юніти досить примітивні, в них немає ні інтелекту, ні якого-небудь різноманіття того, що вони можуть робити. Снаряди з стрілами літають, але теж не по фізиці. Юніт з юнітом теж практично не взаємодіють, принаймні не кожен з великою кількістю одночасно. Може для козаків котрийсь з цих «не» і не виконується. Це, скоріше, жанрові обмеження.

Тут явно не простий цикл проходить по всіх об'єктах і щось з ними робить.

Але ж main game loop...

Подякували: Master_Sergius1

3

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

Та навіть ящо взяти і виділити кілька тисяч юнітів і просто дати команду йти туди - то цей головний цикл має пробігатися щоразу по кожному юніту і міняти йому координати чи шось таке, це дуже затратно.

4

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

По-перше, все ж головний цикл по 10000 структур, якщо треба тільки зсунути на певний крок по двох координатах, буде досить швидким. 20000 арифметичних операцій із цілими, по, скажімо, 10 тактів на операцію - це 200 тисяч тактів. Якщо це одноядерний гігагерцний процесор, це займе аж цілих 0,0002с. Ніщо не заважає крутити такий цикл 50 разів на секунду, і змінювати не 2 характеристики, а 20, це все одно навантажить наш не надто швидкий процесор аж на 1%. Якщо ж довірити таку просту обробку відеопроцесору (додавання масивів вони вміють робити), то взагалі пісня буде. Ба навіть MMX та SSE можуть в кілька разів прискорити обробку.
Проблеми починаються, коли треба обчислювати взаємодію багатьох об'єктів. Перша ідея щодо оптимізації - розбити поле, скажімо, на 64x64 квадратиків і дати юнітам обчислювати на кожному кроці, чи перейшли вони в наступний квадратик і "реєструватися" там (це можна зробити логічними операціями, а пам'яті ну якийсь мегабайт потягне на масиви "зареєстрованих"), а потім перевіряти не повну взаємодію, а тільки тих, хто в своєму та сусідніх квадратиках. Якщо в середньому навколо одного юніта опиняється 100 інших, то навантаження наш старий процесор вже не потягне, але сучасним 4-ядерним 3ГГц-овим це не має стати на заваді.

Подякували: FakiNyan, Master_Sergius, Arete, funivan, leofun015

5

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

Ну, якщо розібрати математично, то вроді як все стає на місця. Але ще ж накладні витрати на виклики функцій, а також переключення контексту на потреби самої ОС, і т.д. і т.п, то "Якщо це одноядерний гігагерцний процесор, це займе аж цілих 0,0002с." не буде відповідати дійсності, тобто якби гра не відбувається у "сферичному вакуумі".

Насправді, Я більше цікавився для свого проекту. Видно, мій нетбук геть паршивий, що погано справляється із моєю міні-грою, коли там починає плодитися велика кількість юнітів. Ну, ще плюс те, що це Python, а не С, то в принципі все логічно. Але думав, може все ж є якісь фокуси і секрети, круті алгоритми.

6

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

Функції інлайняться. ОС відбирає управління не дуже часто, інакше постійно процесор був нею зайнятий.
Ну і покажіть код, може, підкажу, як можна покращити... хоча, звісно, Python не дуже швидкий. Але там є бібліотеки для швидкої обробки масивів, скажімо, та ж numpy.

7

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

Master_Sergius
"Поділяй та владарюй!"
На сучасних компах необхідно розбивати обчислення на кілька потоків. Це може бути як горизонтальне розбиття типу поділу ігрового поля на окремі зони, які обчислюються різними потоками. Так і вертикальне розбиття, наприклад ігрова логіка в одному потоці, а фізика в іншому. Ну й відяху треба підключати по максимуму. Це в загальному.
А є ще купа конкретики, коли для якоїсь гри не обов'язково робити повноцінне обчислення зіткнень з перешкодами, чи іще щось таке. Але це зазвичай тюнять за допомогою профілювальника та демок.

8 Востаннє редагувалося Master_Sergius (29.09.2016 11:39:00)

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

Код ось тут, гра доволі примітивна, але все ж таки... https://github.com/MasterSergius/simple_shooter_2D.git

(для запуску ще потрібно встановити pygame, може потім додам requirements.txt та інструкції).

9

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

Чого все в одному файлі? Незручно ж.

Профайлером проходили?

10

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

quez написав:

Чого все в одному файлі? Незручно ж.

Профайлером проходили?

Не в одному, там ще константи є :)
А взагалі, із самого початку воно трохи все не так задумувалося, а потім пішло-поїхало.
А профайлом не впевнений шо дуже добре допоможе, бо тут не зовсім детермінована поведінка. А треба зачекати поки назбереться монстрів... Але результати ось такі (це я повирізав трохи шматків):

Прихований текст
ncalls  tottime  percall  cumtime  percall filename:lineno(function)
97809   10.768    0.000   10.768    0.000 :0(blit)
1    0.024    0.024    0.024    0.024 :0(init)
        7    0.004    0.001    0.004    0.001 :0(insert)
     5214    0.008    0.000    0.008    0.000 :0(isalnum)
       43    0.000    0.000    0.000    0.000 :0(isdigit)
        1    0.000    0.000    0.000    0.000 :0(isenabled)
     6222    0.008    0.000    0.012    0.000 :0(isinstance)
   100/69    0.000    0.000    0.004    0.000 :0(issubclass)
      111    0.000    0.000    0.000    0.000 :0(items)
       74    0.000    0.000    0.000    0.000 :0(iter)
  720/711    0.020    0.000    0.084    0.000 :0(join)
       17    0.000    0.000    0.000    0.000 :0(keys)
31674/31232    0.036    0.000    0.036    0.000 :0(len)
       20    0.000    0.000    0.000    0.000 :0(listdir)
        3    0.012    0.004    0.012    0.004 :0(load_extended)
        1    0.000    0.000    0.000    0.000 :0(locals)
        2    0.000    0.000    0.000    0.000 :0(log)
     6424    0.024    0.000    0.024    0.000 :0(lower)
       38    0.000    0.000    0.000    0.000 :0(lstat)
       12    0.000    0.000    0.000    0.000 :0(lstrip)

Схоже що найбільше навантаження йде саме на відображення (blit), а не на обчислення.

11

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

Тоді треба не перемальовувати фон кожен кадр. Все інше досить маленьке, тому у вас скоріше всього не буде стільки ворогів, щоб навантаження при їх малюванні зрівнялось з навантаженням при малюванні фону. Більше того, фон постійно на одному місці, тому немає сенсу постійно перемальовувати його. Гугл говорить, що http://www.pygame.org/docs/ref/sprite.html#pygame.sprite.DirtySprite може допомогти.

Подякували: Master_Sergius1

12

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

Спробую. Я йшов спочатку по звичайному тутору, а далі стало влом читати/розбирати, почав кодити. Якось так.

13

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

Ну, ще плюс те, що це Python, а не С, то в принципі все логічно. Але думав, може все ж є якісь фокуси і секрети, круті алгоритми.

На dou один з розробників писав, що вони писали треті козаки на Delphi)

А заголом насправді, якщо всі задачі розбити на прості (окремо обчислення ШІ, окремо рухи, окремо дії, окремо бій) то все не так складно. І якщо це мережева гра то обчислювати нічого не треба, просто заархівований пакет даних передити

14

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

додам свої 5 копійок. Як було вище вказано - очікувати зміни і тільки тоді щось робити.
Тобто не треба кожен раз перевіряти де є та 1000 юнітів чи перетинаються вони з іншими, достатньо перевірити ті що змінили позиції у певних точках. Або наприклад ви знаєте що обєкти зустрінуться з іншою армією через 100 кроків. Ви можете чекати виконання умов. Такі собі Event

Розкажіть про свою логіку ігри, можливо щось підскажемо ;) Або станемо бета тестерами))

Подякували: koala1

15

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

funivan написав:

додам свої 5 копійок. Як було вище вказано - очікувати зміни і тільки тоді щось робити.
Тобто не треба кожен раз перевіряти де є та 1000 юнітів чи перетинаються вони з іншими, достатньо перевірити ті що змінили позиції у певних точках. Або наприклад ви знаєте що обєкти зустрінуться з іншою армією через 100 кроків. Ви можете чекати виконання умов. Такі собі Event

Розкажіть про свою логіку ігри, можливо щось підскажемо ;) Або станемо бета тестерами))

Ні, рендер має обробити всі обєкти сцени, щоб їх можно було побачити.

16

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

Ні, рендер має обробити всі обєкти сцени, щоб їх можно було побачити.

Дуже часто народ робить таку штуку:
Якщо перетинаються юніти - тоді знищуємо тих, у кого менше здоровя.
Якщо є армія 1000*1000 Народ перевіряє чи кожен юніт перетинаться з іншим юнітом.
Я мав на увазі що можна по іншому робити таку логіку ;) І не потрібно буде перевіряти чи кожен юніт не перетинається з юнітом суперника.

17

Re: Як в іграх оброблюють тисячі об'єктів без затримок?

Тут ще важливо, що коли юніти рухаються полем, то не треба для кожного з них прораховуати шлях. Спочатку знаходимо шлях для головного юніта, а потім інші йдуть за ним, якщо кількість юнітів велика, тобто вони займають багато місця на екрані. то для кращого вигляду сцени можна обрати декілька головних юнітів, а інші щоб рухались за ними використовуючи певну систему ваг.

Подякували: koala1