[Haskell-cafe] octree implementation - followup to "How to model outer space for a MUD"

Tikhon Jelvis tikhon at jelv.is
Thu Aug 20 20:41:01 UTC 2015


Are you already familiar with lenses? From a glance at the code you linked,
it will be hard to understand what's going on unless you are.

Personally, my advice is to implement a simple, limited quadtree yourself.
The first part of "Functional Programming with QuadTrees"[1] is basically a
tutorial on quadtrees with code in Miranda—eminently readable for
Haskellers. That's where I would start: write up the code from their
examples in Haskell, play around with it and add an extra function or two
to understand what's going on.

Once you have an intuition for the underlying ideas, you can expand it to
octtrees and more complex operations.

[1]:
http://conal.net/papers/warren-burton/Functional%20Programming%20and%20Quadtrees.pdf

On Thu, Aug 20, 2015 at 1:30 PM, Michael Litchard <michael at schmong.org>
wrote:

> It looks like Octree is what I want if I can solve a particular problem.
> First let me articulate what I am looking for.
>
> (1) Objects in 3-d space with no spatial extent. Collision is determined
> by two objects occupying the same point.'
>
> (2) Efficient insert-delete-update
>
> #2 seems to be the problem. I found this library, thankfully. I believe
> it's exactly what I am looking for, but for quadtrees.
>
> https://github.com/AshleyMoni/QuadTree
>
> I'm a little overwhelmed as this is a new data structure for me. I believe
> if I can grok what is going on in this library, I can take these ideas and
> extend them to the octree. I'm referring specifically to this module
>
>
> https://github.com/AshleyMoni/QuadTree/blob/master/Data/QuadTree/Internal.hs
>
> And these functions
>
> setLocation :: Eq a => Location -> a -> QuadTree a -> QuadTree a
> setLocation = set . atLocation
>
> atLocation (Having difficulty cutting and pasting this to mail.)
>
> I'd like to be able to visualize how the tree is being compressed, it may
> help to be able to see what happens to the tree when it's not compressed.
>
> Does anyone have a pointer or advice in how to break this library down in
> parts to help me grok, in a way that will help me extend to octree?
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150820/c4d4cd7f/attachment.html>


More information about the Haskell-Cafe mailing list