Pages: 1
  Print  
Author Topic: Frustum Culling and View Hashing  (Read 2289 times)
Offline (Male) Goombert
Posted on: August 03, 2013, 12:33:39 AM

Developer
Location: Cappuccino, CA
Joined: Jan 2013
Posts: 3110

View Profile


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.
Logged
I think it was Leonardo da Vinci who once said something along the lines of "If you build the robots, they will make games." or something to that effect.

Offline (Unknown gender) TheExDeus
Reply #1 Posted on: August 03, 2013, 09:03:10 AM

Developer
Joined: Apr 2008
Posts: 1872

View Profile
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.
Logged
Offline (Male) Josh @ Dreamland
Reply #2 Posted on: August 06, 2013, 11:57:52 AM

Prince of all Goldfish
Developer
Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2959

View Profile Email
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.
Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Offline (Unknown gender) TheExDeus
Reply #3 Posted on: August 06, 2013, 02:48:54 PM

Developer
Joined: Apr 2008
Posts: 1872

View Profile
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.
Logged
Offline (Male) Josh @ Dreamland
Reply #4 Posted on: August 07, 2013, 04:20:04 PM

Prince of all Goldfish
Developer
Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2959

View Profile Email
with (obj_car closer than 300 pixels from obj_player) {} translates to with (obj_car) if (distance_to_object(obj_player) < 300) {}. 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.
Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Offline (Unknown gender) TheExDeus
Reply #5 Posted on: August 08, 2013, 01:10:39 AM

Developer
Joined: Apr 2008
Posts: 1872

View Profile
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.
« Last Edit: August 08, 2013, 01:12:44 AM by TheExDeus » Logged
Offline (Male) Goombert
Reply #6 Posted on: August 08, 2013, 09:42:58 AM

Developer
Location: Cappuccino, CA
Joined: Jan 2013
Posts: 3110

View Profile
Harri, that is exactly what I was proposing.
Logged
I think it was Leonardo da Vinci who once said something along the lines of "If you build the robots, they will make games." or something to that effect.

Offline (Unknown gender) forthevin
Reply #7 Posted on: August 08, 2013, 04:39:05 PM

Contributor
Joined: Jun 2012
Posts: 171

View Profile
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.
Logged
Offline (Male) Goombert
Reply #8 Posted on: August 08, 2013, 07:55:43 PM

Developer
Location: Cappuccino, CA
Joined: Jan 2013
Posts: 3110

View Profile
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
Logged
I think it was Leonardo da Vinci who once said something along the lines of "If you build the robots, they will make games." or something to that effect.

Pages: 1
  Print