ENIGMA Forums

General fluff => General ENIGMA => Topic started by: Goombert on August 03, 2013, 12:33:39 am

Title: Frustum Culling and View Hashing
Post by: Goombert on August 03, 2013, 12:33:39 am
(https://geodata.ethz.ch/geovite/tutorials/L2GeodataStructuresAndDataModels/en/images/quadtree.gif)

Well this is obviously an easy way we can get games speeded up. I am talking of course of adding a quadtree for culling 2D objects outside the view. I don't intend or am I even suggesting to implement this for the draw_sprite commands or anything, just simply for objects who are set a sprite and do not have a draw event and by default simply draw their sprite.

The reason is because sometimes people implement their own view bounds checking, for instance, cheeseboy does in his Raptor Blasters game. Also programmers may have their own methods of making their game faster that our method might impede. Therefore I am only suggesting this for objects that do not have draw events.

The idea is simple, we divide all the objects update into a quadtree based on their local x and y and mask, then simply draw only the ones in view by default.
Title: Re: Frustum Culling and View Hashing
Post by: TheExDeus on August 03, 2013, 09:03:10 am
Is a quad-tree really nessesary for a 2d game? Can't you just do simple bounds checking like x-sprite_offsetx()+sprite_width()>0 or something? Previously this was done for all the tiles. When they were turned into lists then it was just easier to draw everything.
Title: Re: Frustum Culling and View Hashing
Post by: Josh @ Dreamland on August 06, 2013, 11:57:52 am
I am adding getters and setters to EDL for this very purpose.

They will replace multifuntion_variant for some objects, and will be used to update the space map when objects move.
Title: Re: Frustum Culling and View Hashing
Post by: TheExDeus on August 06, 2013, 02:48:54 pm
And that will do what exactly? Like you could do with (obj_car closer than 300 pixels from obj_player) {} and then iterate only trough cars closer than 300 pixels to the player? Because I think a mechanism to iterate only instances you need is a good one and maybe quad tree would work in that case. But I don't see why it would be used for 2D drawing.
Title: Re: Frustum Culling and View Hashing
Post by: Josh @ Dreamland on August 07, 2013, 04:20:04 pm
with (obj_car closer than 300 pixels from obj_player) {} translates to [snip=EDL]with (obj_car) if (distance_to_object(obj_player) < 300) {}[/snip]. The space map (most likely quad tree, in 2D) would not really help with that at all, unless you narrowed down only quadrants which contained pixels closer than 300 pixels. This is feasible, but would have to be specialized to make any real use of it. Otherwise, iterating quadrants would waste more time than it's worth.

Maybe a lambda expression could enable doing that in a general way... I'd have to give it some thought.
Title: Re: Frustum Culling and View Hashing
Post by: TheExDeus on August 08, 2013, 01:10:39 am
Well I thought a quad tree in any size will give an advantage in that situation. Like if I have quads of 800x600 (view size) and my room is 20000x20000, then just by with (obj_car closer than 300 pixels from player) would iterate at most 4 quads. And why would you even iterate quads? You should be able to get them just from position. Like get quad the player is in (O(1)) and then get any other quad that is closer than 300 pixels (O(1), because you always check at most 8 quads if the request size is smaller than quad size, otherwise it might get a little more complicated). Then do with (obj_car) if (distance_to_object(obj_player) < 300) {}, but make "with (obj_car)" return only cars in those selected quadrants. That means if there are 2000 cars all over the map, it would still return like 150 for example and the "if" check would reduce that to 10 for example.
Title: Re: Frustum Culling and View Hashing
Post by: Goombert on August 08, 2013, 09:42:58 am
Harri, that is exactly what I was proposing.
Title: Re: Frustum Culling and View Hashing
Post by: forthevin on August 08, 2013, 04:39:05 pm
I investigated similar data structures some time ago when I looked into broad-phase collision detection. A variation of k-d trees (http://en.wikipedia.org/wiki/Kd-tree) could be a possibility for tiles. k-d trees are normally just for points, but it is possible to modify them to support bounding boxes, meaning that you could skip the distance check that you would need for the quad tree. While I recall they are relatively expensive to create and modify, meaning quad trees would likely be a better solution for moving objects, you rarely need to modify tiles, and they should have decent performance for querying areas of tiles (especially tiles that have regular sizes and are spread out in somewhat uniform density). That said, I don't know how much of a speed up it would provide, unless the room with tiles is very, very large relative to the view, in which case I think it could be well worth it.

As for collision detection, I think they can easily be worth it, given that the number of collision can be quadratic in the number of instances (if you have two about equally large groups of instances where the groups collide with each other), and a k-d tree should in most cases reduce the number of collision from O(N^2) to O(N*log(N)) or something similar.
Title: Re: Frustum Culling and View Hashing
Post by: Goombert on August 08, 2013, 07:55:43 pm
Project Mario used a slightly broader approach to a quadtree for collision hashing, that is how I optimized Project K as much as I did :P