Grids are very good for handeling objects the same size. But when size varies quadtrees can do a bit better.
Distribution is the key litmus test. Then it depends on the implementation.
Distribution is the key litmus test. Then it depends on the implementation.
What do you mean? I plan to use a quadtree (or a BSP tree) to build a network of cells and portals.
With ‘functional’ people, I mean people who write in purely functional languages.
What does purely functional mean? You can’t change anything. Imagine to only be able to create [icode]final [datatype] variable[/icode] variables.
What’s the problem?
Imagine you have a Grid. A very simple one, only an array, where each Tile for a tile-based game is stored. Whenever you want to change the tile, you need to create a new Grid and copy all the tiles into them, since you can’t change anything (a.k.a. so called side-effects (changes of state) aren’t allowed).
Now copying a grid which is big is not cheap. What they do is: Use a data structure which is basically a tree. And then whenever a tree leaf changes, they only have to change all the leaf’s ancestors. Which is only 3-10 Quadtree nodes, depending on the size of the Quadtree and implementation.
Done.
What do you mean? I plan to use a quadtree (or a BSP tree) to build a network of cells and portals.
With ‘functional’ people, I mean people who write in purely functional languages.
What does purely functional mean? You can’t change anything. Imagine to only be able to create [icode]final [datatype] variable[/icode] variables.
What’s the problem?
Imagine you have a Grid. A very simple one, only an array, where each Tile for a tile-based game is stored. Whenever you want to change the tile, you need to create a new Grid and copy all the tiles into them, since you can’t change anything (a.k.a. so called side-effects (changes of state) aren’t allowed).
Now copying a grid which is big is not cheap. What they do is: Use a data structure which is basically a tree. And then whenever a tree leaf changes, they only have to change all the leaf’s ancestors. Which is only 3-10 Quadtree nodes, depending on the size of the Quadtree and implementation.
Done.
Immutability hurts you here. In no way does it help. People with distributions which aren’t close to uniform prefer over uniform grids.
Just a side note:
You don’t copy immutable objects. As they never change (mutate) there is no point in holding more than one copy. You reference it (which is cheaper).
Try this implementation PointQuadTree.java.
It will handle Riven’s issue with infinite recursion, and it shatters/merges branches in the tree as needed.
Immutability hurts you here. In no way does it help. People with distributions which aren’t close to uniform prefer over uniform grids.
Just a side note:
You don’t copy immutable objects. As they never change (mutate) there is no point in holding more than one copy. You reference it (which is cheaper).
Try this implementation PointQuadTree.java.
It will handle Riven’s issue with infinite recursion, and it shatters/merges branches in the tree as needed.
Yes… I was talking about functional languages… :cranky:
With ‘copy’ I mean ‘create a new one with changed parameters’. Take the copy method from scala’s case classes as example…
(just so you know:)
case class Person(name: String, age: Int)
val john = Person("john", 21).copy(age = 22); // Results in "john", 22
Yes… I was talking about functional languages… :cranky:
With ‘copy’ I mean ‘create a new one with changed parameters’. Take the copy method from scala’s case classes as example…
(just so you know:)
case class Person(name: String, age: Int)
val john = Person("john", 21).copy(age = 22); // Results in "john", 22
You mean you’re talking about purely functional languages. 
You mean you’re talking about purely functional languages.
;D just because that wasn’t enough, here is a quote from my post before:
;D just because that wasn’t enough, here is a quote from my post before: