Большой массив данных. Как лучше реализовать?

← →
Whitewolf (2002-04-18 12:30) [0]

Как вообще в играх организовывается работа с большим количеством данных?

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

← →
Anatoly Podgoretsky (2002-04-18 12:40) [1]

Зачем модули хранить и в реале обрабатывать, что у тебя RealTime компилятор?

← →
Владимир Васильев (2002-04-18 14:44) [2]

Все параметры обрабатывать на каждом шаге практически никогда - кроме, быть может, инициализации - не нужно.Подумай, как можно выделить группу объектов, которые нужно обсчитать, а какие обсчитывть не надо. И как часто - что то надо считать при каждом шаге - что- то через шаг, два а то и 10.
Я,например, обсчитываю появление целей для атаки раз в секунду - т.е через 80 шагов при 80 fps

← →
Whitewolf (2002-04-18 16:28) [3]

Я именно про выделение группы объектов и говорю. Допустим у меня массив из 200 юнитов, и мне нужно по какому-нибудь критерию выбрать несколько из них. В случае с БД можно сделать простой SQL запрос и все, это и проще и быстрее, а так прийдется делать цикл по всем юнитам. А кроме простой выборки нужны еще и функции добавления/удаления юнитов, работа только с данной выборкой, без перелапачивания всей базы и т.п.
Как-то не хочется самому писать все эти функции, да и медленнее это будет, мне так кажется

← →
Владимир Васильев (2002-04-18 20:27) [4]

c bd будет только хуже - за универсальность проходится всегда платить скоростью.

Как например обсчитать столкновения - самый плохой способ напрямую перебором.

Но можно разбить карту на крупные области - напр на 20-40 равных частей и как только объект переходит из одной области в другую - отслеживать это в соответствующем списке - напр заносить в список соответствующий данной области индекс объекта. Это не сложно и не отнимет много драгоценных тиков. Зато при обсчёте столкновений нужно задействовать только ограниченный набор объектов. Объект из данной области может столкнуться только с объектами из этой же или соседних областей.

← →
Whitewolf (2002-04-19 11:47) [5]

Но по сути все равно получается простой перебор элементов массива, просто с использованием всевозможных ухищрений для оптимизации этого процесса. То есть все таки прийдется долбаться с массивами 8(

← →
Whitewolf (2002-04-19 11:50) [6]

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

← →
3d[Power] (2002-04-20 00:00) [7]

В случае с 200-ми юнитов тебе по любому придется обрабатывать весь массив. Так обычно и делается. Оптимизация заключается в том, если ты нашел не подходящий элемент, то просто пропустить его. У тебя так и получится что обрабатываются только те юниты которые нужны.

← →
Vladimir Vasilyev (2002-04-20 01:12) [8]

Прямой подход VS Метод секторов.
Мне кажется, нужны подробные объяснения, и вопрос довольно важный, чтобы его пропустить.
OK, давайте считать.
Прямой обсчёт столкновений между n объектами даёт (n^2-n)/2 проверок.
Т.е. имеет порядок O(n^2) и для n=200 потребуется 19900 проверок.

Теперь разобьём карту на сектора – лучше прямоугольные и по количеству составляющие степень двойки – 2,4,8 и т.д. – т.к. тогда операция по определению сектора в котором находится рассматриваемый объект – деление - сведётся к shr. Для получения конкретной цифры далее сделаем предположение что объекты распределены по карте равномерно и карта разбита на ixj количество секторов. Пусть i=16 j=8 , тогда имеем ixj=126 секторов и в каждом секторе m=n/(ixj) объектов : m=200/126 ~ 2 объекта в каждом секторе.

Для распределения n объектов по секторам и определение условий расположения объекта на границе придётся выполнить подготовительную работу – НО только один раз для каждого объекта. Итак – имеем n операций.
Рассмотрим наилучший случай – объект целиком принадлежит одному сектору и возможен только непосредственный контакт. Тогда нам прийдётся провести
(m^2-m)/2 *ixj – количество проверок внутри каждого сектора на кол-во секторов.
Подведём итог - всего : n+ (m^2-m)/2 = 200+1*126= 326 !

Конечно, на практике выигрыша по скорости в 60 раз вы не получите, но, как говорится, почувствуйте разницу!!!

← →
Whitewolf (2002-04-20 14:03) [9]

Одним словом нужно думать, думать и еще раз думать, как завещал ... эээ, чего это я 8)

← →
djalal (2002-10-29 20:43) [10]

как организовать в Dilphi динамический массив*?*?**

← →
Mirovodin (2002-10-29 21:27) [11]

2 djalal.

Приехали :)

Z: array of integer; // Начиная с Delphi 4 и выше если я не ошибаюсь.

Можно работать со списками (TList) или самому писать используя GetMem и FreeMem.

2 Whitewolf ©

На счет БД это ты здорово предложил :)))
Почитай как организуется работа SQL сервера на низком уровне (память, файлы), а не на уровне SQL запросов. Сразу станет ясно что лучше перебрать 100 раз список из 200 юнитов, чем использовать БД подход.

Конечно нужно оптимизировать, причем именно на уровне алгоритмов ( как предложил Vladimir Vasilyev ), а потом можно куски и на ASM-е переписать.

← →
Mirovodin (2002-10-29 21:29) [12]

2 Whitewolf ©

Забыл еще сказать - проще всего написать сразу "в лоб", посмотреть как работает, а уж потом в окончательном варианте оптимизировать работу. Так все разработчики и делают, посмотришь демку игры 20-30 fps, а в релизе уже 50-60 - оптимизация.

← →
cyborg (2002-10-30 11:02) [13]

Whitewolf © на счёт БД, ты это серьёзно?
Попробуй метод, как я его называю, PRED NEXT, ещё с Паскаля:
PData = ^TData
TData = record
Pred,Next : PData; //Указатели на предыдущую и следующую запись
DataType : Cardinal; //Тип данных
Data : Pinter; //Указатель на данные
End;

Используй
GetMem(); FreeMem();
Для поиска используешь Pred,Next

← →
pasha676 (2002-10-30 13:41) [14]

2Cyborg

Метод старый, как сам паскаль. Описан еще у Вирта в его описании языка. К слову сказать указатель на преведущий элемент редко когда бывает нужен, можно обойтись ссылкой на последующий.

← →
cyborg (2002-10-30 23:44) [15]

pasha676 видно, что ты им не пользовался, Pred нужен обязательно для вставки записей в цепочку.

Большой массив данных. Как лучше реализовать? Найти похожие ветки