<div dir="ltr"><div><div><div>I've been poking at the problem that I've talked about in the following threads.<br><br><a href="https://groups.google.com/forum/#%21searchin/haskell-cafe/michael$20litchard%7Csort:date/haskell-cafe/n0Tc29UUgoQ/iitt3z3PCwAJ" target="_blank">https://groups.google.com/forum/#!searchin/haskell-cafe/michael$20litchard|sort:date/haskell-cafe/n0Tc29UUgoQ/iitt3z3PCwAJ</a><br><br><a href="https://groups.google.com/forum/#%21searchin/haskell-cafe/michael$20litchard%7Csort:date/haskell-cafe/qD2kaZ9qpEA/jTDAp8KoCgAJ" target="_blank">https://groups.google.com/forum/#!searchin/haskell-cafe/michael$20litchard|sort:date/haskell-cafe/qD2kaZ9qpEA/jTDAp8KoCgAJ</a><br><br></div>And my misguided conclusions here<br><br><a href="https://groups.google.com/forum/#!topic/haskell-cafe/PMtYhVQ5nNQ">https://groups.google.com/forum/#!topic/haskell-cafe/PMtYhVQ5nNQ</a><br><br></div>I'm trying to write a clone in haskell of the space-system implemented in <a href="http://swmud.org">http://swmud.org</a>.<br><br></div><div>The biggest error in my thinking so far is assuming I could do without spatial extent.<br></div><div>Nope, these objects in space will have to have spatial extent. So no octree for me.<br></div><div>The advice and comments from the first two threads prompted me to investigate R-trees.<br></div><div>I could only find specifics about how to describe 2-D.<br></div><div>Until I found this paper on layered R-Trees.<br><br><a href="http://www.isprs.org/proceedings/XXXIII/congress/part4/1216_XXXIII-part4.pdf">http://www.isprs.org/proceedings/XXXIII/congress/part4/1216_XXXIII-part4.pdf</a><br><br></div><div>This looks like what I want. Here's my re-formulation of the criteria:<br><br><br>(1) Objects in space will be either 
ships that can move or stationary things like non-moving game-controlled
 ships, space-stations , moons and planets.<br><br>(2) Objects will have spatial extent. Will use bounding volumes to help determine collisions.<br><br>(3) Space is non-continuous<br> <br>(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.<br><br></div><div>(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 space.<br><br></div><div>It's the number of objects that have me wondering if layered r-tree might be too heavy-weight.<br></div><div>If so, Any links to R-tree variants that include bounding volumes? I could only find ones with bounding boxes.<br></div></div>