[Haskell-cafe] Representation of 3-D objects in non-continuous space

Michael Litchard michael at schmong.org
Sun May 22 17:57:51 UTC 2016

I've been poking at the problem that I've talked about in the following



And my misguided conclusions here


I'm trying to write a clone in haskell of the space-system implemented in

The biggest error in my thinking so far is assuming I could do without
spatial extent.
Nope, these objects in space will have to have spatial extent. So no octree
for me.
The advice and comments from the first two threads prompted me to
investigate R-trees.
I could only find specifics about how to describe 2-D.
Until I found this paper on layered R-Trees.


This looks like what I want. Here's my re-formulation of the criteria:

(1) Objects in space will be either ships that can move or stationary
things like non-moving game-controlled ships, space-stations , moons and

(2) Objects will have spatial extent. Will use bounding volumes to help
determine collisions.

(3) Space is non-continuous

(4) Movement happens by setting a destination vector and a speed. There's
no steering exactly, but you can change destination while moving, slow down
or stop suddenly.

(5) Represent this space with a layered R-tree, This tree will at most have
say, 200-300 objects in it, most of which could be moving around in this

It's the number of objects that have me wondering if layered r-tree might
be too heavy-weight.
If so, Any links to R-tree variants that include bounding volumes? I could
only find ones with bounding boxes.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20160522/972c708d/attachment.html>

More information about the Haskell-Cafe mailing list