Refactor Quadtree - Githubissues

rickbatka / co-op-engine

A prototype engine for our planned co-op game. This is where we will make it work, make it network, and make it feel fun. No AI, level design, etc.

2 stars 0 forks source link

Refactor Quadtree #27

Closed reddenx closed 10 years ago

reddenx commented 10 years ago

Bugs and inefficiencies are popping up and the new bottleneck is the tree traversal during collisions and notification of movement. This is caused by the quad tree having to split and verify quite often, making it a deep tree. The remedy will be to flatten the tree to an adjustable amount.

Objectives:

[x] Each quad in tree needs to be able to hold multiple objects
[x] Max objects per quad must be adjustable
[x] Validate strategy that doesn't explode the tree.
[x] Ensure the 'we both moved to a new quad' bug doesn't transfer
[x] Ensure the infinisplit stack overflow has protection (maybe have it increase allowed count for each split making a fat bottomed structure)
[x] Uninflate when object leaves (didn't quite have time for it)

idea for validate: give quadtree an update and have it do a depth first analysis of quads removing as it traverses

EDIT: added one last little thing

reddenx commented 10 years ago

All refactored and working in a newer quad tree.... but it seems to be just as inefficient as the previous... we may actually have to go off and build some better unmanaged data structures in a library project to get more improvement out of it..... saaaaddd day

reddenx commented 10 years ago

Seems there's some bugs in it..... working on it

reddenx commented 10 years ago

I'm shelving this since the current 1 item implementation is stable and working in all cases, we'll get the better one implemented later as it's only a back end swap

rickbatka commented 10 years ago

Two things:d 1) I think your quadtree would be somewhat more efficient if the bad guys were spread out over a larger area. It would mean less deep recursive data structures. Some consolation, anyway - we're not getting any value whatsoever from the broad-phase check of the tree with everyone so tightly packed in. 2) I have an idea that I'm going to try out tomorrow. Hopefully I can figure out how to hook into that area of the code base, I haven't spent much effort trying to understand it up until this point. I have an idea for a broad-phase that would be extremely efficient, and might even be able to be combined with quad tree.

rickbatka commented 10 years ago

Got up to 1800 objects on screen when I spread out the game world (at 60fps)... I think you might be being too hard on the quad tree because we're seeing NONE of the benefits of the quad tree in that tiny space. Let's chat tomorrow.

reddenx commented 10 years ago

Yeah I did some major analysis on our project and realized the most time spent was the master insert and notify during a collision, which wont happen as often when spread out.

Also the quad tree is meant to be spread over vast areas, so you can just blanket the entire world in a single one, the depth wasn't the issue with the single element quad tree anyways.

So I'm pretty sure the refactor can get closed until we notice it becoming a problem again, at which point we should probably look to more of an unmanaged library solution cause the inefficiency is due to a lot of the CLR and .Net business type optimization that is going on.

rickbatka commented 10 years ago

Good call. Maybe get our hands dirty with a C implementation if it is still a problem later in the game :)

reddenx commented 10 years ago

alright, with children getting so close to parents it creates pockets of objects in close proximity making the single quad tree really REALLY inefficient, bringing this issue back from the dead.

reddenx commented 10 years ago

and it is done!