Conway Game of Life and the QuadTree

[EricLang]

I would like to make a Life game, using a quadtree, which I heard is the best method processing all that cells. Now I have the problem: I don't understand the QuadTree. Does anyone have a (simple) source example of the use of a quadtree?

[paul_nicholls]

I'm not sure why a quadtree would be the best way to process the cells in the game of life?

All you do is check neighbouring cells in a simple 2d array - no need to use quadtrees for this AFAIK...

cheers,
Paul

[chronozphere]

A quad tree is a space partitioning datastructure that is used to perform high-speed spatial operations like searching or collision detection. I think you need to have a very special game-of-life in mind, to be in need of such a solution. :)

[EricLang]

Well the problem is not the 2d grid (which could be bits). But when the grid is 1000x1000 we need to do 1.000.000 x 8 checks for each cell for each "generation".
And even then I'm limited to this 1000x1000.
Could we think of an expandable datastructure, storing these cells, while maintaing the speed of the 8 "neighbour" checks?
A sorted list of coordinates is far to slow of course.

[phibermon]

Have you concidered using a shader? I'm sure I've seen the game of life operating on a texture in a GLSL shader before now.

Also if you've got a multi-core CPU, break up the arena into seperate threads, they only have to lock when checking those border cells that are allocated to another thread.

for more learned information check here : http://dotat.at/prog/life/life.html