3 ms·
A very famous application of QuadTrees was Bill Gosper's HashLife algorithm for computing Conway's Game of Life. The Life universe is implemented as a quadtree,
by a4isms 7mo ago
A very famous application of QuadTrees was Bill Gosper's HashLife algorithm for computing Conway's Game of Life. The Life universe is implemented as a quadtree, taking advantage of precomputed smaller squares to compute larger squares.
https://en.wikipedia.org/wiki/Hashlife https://en.wikipedia.org/wiki/Hashlife
https://raganwald.com/2017/01/12/time-space-life-as-we-know-it.html https://raganwald.com/2017/01/12/time-space-life-as-we-know-...
- tetris11 7mo agoIsn't that just quadratic programming?
- a4isms 7mo agoI have nothing to say about Quadratic Programming, so you tell me. What I can say is that every reference I've found to Bill Gosper's algorithm describes the data structure as an immutable quadtree with canonicalized nodes, id est, there is extensive structure sharing in a Game of Life quadtree. That in turn facilitates heavy memoization. The wikipedia entry for Quad Trees mentions Hashlife explicitly: https://en.wikipedia.org/wiki/Quadtree https://en.wikipedia.org/wiki/Quadtree