handling very many objects (Large Array)

Share your ZGE-development tips and techniques here!

Moderator: Moderators

Post Reply
User avatar
diki
Posts: 140
Joined: Thu Sep 11, 2008 7:53 pm
Location: GMT+1
Contact:

handling very many objects (Large Array)

Post by diki »

hi,
i was recently having a little idea about handling large arrays of objects in such a way that all the objects are present & accessible, but without requiring the entire array to be involved in calculations every frame. that sounds abstract, but i wanted to improve on my my cityscape generator, which uses many objects (buildings); even with kjells excellent culling example, a large array that is checked entirely every frame requires a lot of processor attention. i also required a method for intelligent collision detection, which is also (probably) performance heavy when running on the entire set of buildings.

i thought about checking only a small portion of the large array each frame (in this case for proximity to the mouse cursor) and transfering all elements in range to a smaller array, which is then updated & rendered every frame at a much lower processing cost. this is a simple idea, but i failed a few times at implementing it in ZGE (and still find it a bit complicated); assuming that my approach is probably not the best, i'd like to hear your opinions about it :)

i also made an obnoxiously large infographic which, in hindsight, makes it look a lot less impressive than i thought it would be ;) i attached two similar versions of the project, one which demos the principle and another that uses more elements and is the performance test (they differ only in a few changed variables).
Attachments
idea v02.GIF
idea v02.GIF (12.82 KiB) Viewed 15891 times
20090925 array transfer test v15 demo.zgeproj
this setup demos the principle.
(8.29 KiB) Downloaded 734 times
20090925 array transfer test v15 perf.zgeproj
this setup is the performance test, running quite smooth.
(8.29 KiB) Downloaded 754 times
User avatar
Kjell
Posts: 1876
Joined: Sat Feb 23, 2008 11:15 pm

Post by Kjell »

Hi diki,

You definitely don't want to loop through a list containing all of your objects indeed :) But instead of copying them over to a separate array, just limit the range of data that you're using / reading using smart spacial indexing instead.

For your situation a simple 2D Grid should be sufficient. Use a 3D Array of which the first two dimensions represent the X & Y coordinates of the Grid, while the third lists all the object ID's that are positioned within the bounds of that Cell. Optionally you can use a additional 3D Array which contains the number of objects listed in your data structure per Cell to speed up the loops.

Personally I'm a big fan of Octrees ( Quadtrees are the 2D equivalent ), but they are a little more complicated to implement & manage ( and not really necessary unless you're dealing with complex environments ).

K
kattle87
Posts: 402
Joined: Wed Sep 26, 2007 9:06 am
Location: Italy

Post by kattle87 »

I second this idea of scanning little portions of the array every frame, so you end up removing ad creating models once every 2 or 3 seconds MAX... and this is not that bad, if you ask me!After that, we can use several "indexes arrays" like kjell suggested, maybe one for creation of models you will use for collision and for "high detail" graphics, the other one for rendering with low level of detail the other buildings.

EDIT: now I see you don't copy anything but just store indexes, this makes sense...
Kjell... the problem with indexing here is that the cityscape generator does not create an uniform grid of object, thus the way you proposed could be difficult to achieve.
In the fall of 1972 President Nixon announced that the rate of increase of inflation was decreasing. This was the first time a sitting president used the third derivative to advance his case for reelection.
-=Hugo Rossi=-
User avatar
Kjell
Posts: 1876
Joined: Sat Feb 23, 2008 11:15 pm

Post by Kjell »

:)

@kattle87: One thing at the time ~ Using LOD's / specific collision models is something different from spacial indexing.

You don't need objects to fit inside a Grid Cell to index them. Just use their position coordinates and set a rule that for example a object can never be bigger then 1 cell, in which case they overlap 4 cells maximum ( find a balance that works for your environment ).

K
kattle87
Posts: 402
Joined: Wed Sep 26, 2007 9:06 am
Location: Italy

Post by kattle87 »

Now I got what you meant... well, it's a nice way for doing it I must say! And yes it would be easier to cope with. Nice one Kjell ;)
In the fall of 1972 President Nixon announced that the rate of increase of inflation was decreasing. This was the first time a sitting president used the third derivative to advance his case for reelection.
-=Hugo Rossi=-
User avatar
diki
Posts: 140
Joined: Thu Sep 11, 2008 7:53 pm
Location: GMT+1
Contact:

Post by diki »

yes, spatial indexing sounds really good - and is probably a lot faster than having to care for a transfer-array (checking for presence when inserting & keeping track of entries to delete)... back to the editor, i guess :)
User avatar
diki
Posts: 140
Joined: Thu Sep 11, 2008 7:53 pm
Location: GMT+1
Contact:

Post by diki »

thanks for the idea, kjell!
now i can put this to use with some collision detection ... :D
Attachments
cells2.gif
cells2.gif (7.94 KiB) Viewed 15840 times
20090912 cityscape testcase v86.zgeproj
(56.71 KiB) Downloaded 806 times
User avatar
Kjell
Posts: 1876
Joined: Sat Feb 23, 2008 11:15 pm

Post by Kjell »

Hmm,

Judging from the Grid lines in your screenshot your cell size is way too big. This way you'll end up having to check culling / clipping / collision for ~100 buildings that exist within the cell your "character" is located ( while the whole purpose of spatial indexing is to end up with a handful of objects ).

For your situation I think it's best that a cell has the same size as your largest building. Although you haven't clearly stated what you're aiming for still. When you want to do a Rampage / Godzilla type of game, or SimCity perhaps .. you're going to need completely different systems.

K
User avatar
diki
Posts: 140
Joined: Thu Sep 11, 2008 7:53 pm
Location: GMT+1
Contact:

Post by diki »

hi kjell,
sure, the cell size still needs to be adjusted. the purpose i want to use this for is to a) speed up rendering (simply by only culling a reduced number of objects - e.g. the 9 cells surrounding the player, with ~40 buildings in each cell) and b) do custom collision testing (this should of course operate on much smaller cells of 3-5 buildings). the gameplay is, in a nutshell, the player jumping around on top of buildings.

just out of curiosity, for which reasons would one need a different system (and what kind) with rampage/sim city?
User avatar
Kjell
Posts: 1876
Joined: Sat Feb 23, 2008 11:15 pm

Post by Kjell »

Hi diki,

Let's not get into other games such as SimCity ( constant grid-based ) or Godzilla ( dynamic environment ) right now .. more important is that you seem to have missed my "as long as you won't be able to stand on top of buildings" comment. When you're standing on top of a building while looking down the culling method I proposed won't work properly.

Also keep in mind that a game like Mirror's Edge closes off the playfield with a row of high rising buildings .. which are purely used as background art, and aren't indexed / nor have collision.

Image

K
User avatar
diki
Posts: 140
Joined: Thu Sep 11, 2008 7:53 pm
Location: GMT+1
Contact:

Post by diki »

hi kjell,
of course i didn't miss your comment; the scenario of standing on a building & looking down just wasn't part of the general idea back then - sorry :)
User avatar
Kjell
Posts: 1876
Joined: Sat Feb 23, 2008 11:15 pm

Post by Kjell »

Hi diki,

No worries, sometimes running into something you hadn't foreseen can be a good learning experience :) I've mentioned this before, but it's worth mentioning again .. subtle choices can have huge impact on your code. Take "Dawn of Mana" and "Final Fantasy XII" for example. Both 3rd person action-RPG's developed for the PS2 by Square-Enix .. but because characters can jump in the first and can't in the latter, the required collision / spatial indexing methods are completely different.

K
User avatar
jph_wacheski
Posts: 1005
Joined: Sat Feb 16, 2008 8:10 pm
Location: Canada
Contact:

Post by jph_wacheski »

Noticed an article on this subject here;

http://www.gamedev.net/reference/snippe ... atialHash/
iterationGAMES.com
User avatar
Kjell
Posts: 1876
Joined: Sat Feb 23, 2008 11:15 pm

Post by Kjell »

No offence,

But that implementation heavily relies on the fact that Python supports append-able dynamic arrays .. it might / will just confuse people using ZGE.

K
Post Reply