I agree with Tikhon But a sparse matrix might be conceptually simpler to start with But are sparse matrices easy to implement in Haskell and then is it easy to change the data structure layer on? -- -- Sent from an expensive device which will be obsolete in a few months! :D Casey On Aug 14, 2015 1:50 PM, "Tikhon Jelvis" wrote:

It depends on exactly what you want to represent and how you want to do it.

The first thing that comes to mind for me would be using an octtree[1], which is the three-dimensional analog of a quadtree[2]. Conal Elliott has an interesting point about using quadtrees to represent images in Haskell[3], and you should be able to adapt the idea to indexing into a three dimensional world with an octtree.

[1]: https://en.wikipedia.org/wiki/Octree

[2]: https://en.wikipedia.org/wiki/Quadtree

[3]: http://conal.net/blog/posts/topless-data

On Fri, Aug 14, 2015 at 1:44 PM, David McBride wrote:

...

If you are thinking of it as a 3d grid, you might just have a (Map (Integer, Integer, Integer) Contents, where every room in this 3d grid that has something in it is in the map and every room that is empty space has no corresponding entry in the map.

Then when you enter a room you can quickly look up what is in that room, then reasonably quickly check the neighbors in every direction to see what the ship might be able to sense were it to travel in that direction.

In this case, space is infinite, but the datastructure is only as big as the amount of content you have.

On Fri, Aug 14, 2015 at 4:34 PM, Michael Litchard wrote:

...

Star Wars MUD has a 3-D coordinate system such that (0,0,0) is some planet. I'm curious as to how one might model this system that could simulate a ship's movement through a 3-D grid. Matrix, 3-D array, graph. None of these? Ideas?

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

I would not model space -- there's too much of it -- rather Things in space. Each Thing has a 3d coordinate (plus more geometric information, plus more information). Things can be rooms, and things can have position defined in terms of other things. On Fri, Aug 14, 2015 at 3:23 PM, Michael Litchard wrote:

Well, thinking more about it, I think I want an 8-regular complete graph. I've been doodling and came to the conclusion pretty quickly that thinking of this space in terms of a grid wasn't quite right. I *would* like to only hold data of populated nodes if possible, to model an infinite space as David mentioned. I've been looking at fgl to help me think about this problem in terms of a graph. I'll think and tinker over the weekend and see if I can come up with something more articulate. Not committed to a graph, but I want a discrete structure and this looks like it fits the bill at the moment.

On Fri, Aug 14, 2015 at 2:00 PM, KC wrote:

...

I agree with Tikhon

But a sparse matrix might be conceptually simpler to start with But are sparse matrices easy to implement in Haskell and then is it easy to change the data structure layer on?

-- --

Sent from an expensive device which will be obsolete in a few months! :D

Casey

On Aug 14, 2015 1:50 PM, "Tikhon Jelvis" wrote:

...

It depends on exactly what you want to represent and how you want to do it.

The first thing that comes to mind for me would be using an octtree[1], which is the three-dimensional analog of a quadtree[2]. Conal Elliott has an interesting point about using quadtrees to represent images in Haskell[3], and you should be able to adapt the idea to indexing into a three dimensional world with an octtree.

[1]: https://en.wikipedia.org/wiki/Octree

[2]: https://en.wikipedia.org/wiki/Quadtree

[3]: http://conal.net/blog/posts/topless-data

On Fri, Aug 14, 2015 at 1:44 PM, David McBride wrote:

...

If you are thinking of it as a 3d grid, you might just have a (Map (Integer, Integer, Integer) Contents, where every room in this 3d grid that has something in it is in the map and every room that is empty space has no corresponding entry in the map.

Then when you enter a room you can quickly look up what is in that room, then reasonably quickly check the neighbors in every direction to see what the ship might be able to sense were it to travel in that direction.

In this case, space is infinite, but the datastructure is only as big as the amount of content you have.

On Fri, Aug 14, 2015 at 4:34 PM, Michael Litchard wrote:

...

Star Wars MUD has a 3-D coordinate system such that (0,0,0) is some planet. I'm curious as to how one might model this system that could simulate a ship's movement through a 3-D grid. Matrix, 3-D array, graph. None of these? Ideas?

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

I'm looking for unbounded but discrete, but I think conal's blog post can help me work this out. On Fri, Aug 14, 2015 at 3:36 PM, Tikhon Jelvis wrote:

The problem with just modeling things is that certain questions become difficult. For example, it's often useful to know what thing is closest to some given thing, or what a thing's closest neighbor is.

Moreover, while there is certainly a lot of space out there, this is Haskell so we can model all of it lazily. That's what Conal's blog post is about: a practical way to lazily model images with no bounds and no resolution limit. On Aug 14, 2015 3:31 PM, "Jeffrey Brown" wrote:

...

I would not model space -- there's too much of it -- rather Things in space. Each Thing has a 3d coordinate (plus more geometric information, plus more information). Things can be rooms, and things can have position defined in terms of other things.

On Fri, Aug 14, 2015 at 3:23 PM, Michael Litchard wrote:

...

Well, thinking more about it, I think I want an 8-regular complete graph. I've been doodling and came to the conclusion pretty quickly that thinking of this space in terms of a grid wasn't quite right. I *would* like to only hold data of populated nodes if possible, to model an infinite space as David mentioned. I've been looking at fgl to help me think about this problem in terms of a graph. I'll think and tinker over the weekend and see if I can come up with something more articulate. Not committed to a graph, but I want a discrete structure and this looks like it fits the bill at the moment.

On Fri, Aug 14, 2015 at 2:00 PM, KC wrote:

...

I agree with Tikhon

But a sparse matrix might be conceptually simpler to start with But are sparse matrices easy to implement in Haskell and then is it easy to change the data structure layer on?

-- --

Sent from an expensive device which will be obsolete in a few months! :D

Casey

On Aug 14, 2015 1:50 PM, "Tikhon Jelvis" wrote:

...

It depends on exactly what you want to represent and how you want to do it.

The first thing that comes to mind for me would be using an octtree[1], which is the three-dimensional analog of a quadtree[2]. Conal Elliott has an interesting point about using quadtrees to represent images in Haskell[3], and you should be able to adapt the idea to indexing into a three dimensional world with an octtree.

[1]: https://en.wikipedia.org/wiki/Octree

[2]: https://en.wikipedia.org/wiki/Quadtree

[3]: http://conal.net/blog/posts/topless-data

On Fri, Aug 14, 2015 at 1:44 PM, David McBride wrote:

...

If you are thinking of it as a 3d grid, you might just have a (Map (Integer, Integer, Integer) Contents, where every room in this 3d grid that has something in it is in the map and every room that is empty space has no corresponding entry in the map.

Then when you enter a room you can quickly look up what is in that room, then reasonably quickly check the neighbors in every direction to see what the ship might be able to sense were it to travel in that direction.

In this case, space is infinite, but the datastructure is only as big as the amount of content you have.

On Fri, Aug 14, 2015 at 4:34 PM, Michael Litchard < michael@schmong.org> wrote:

> Star Wars MUD has a 3-D coordinate system such that (0,0,0) is some > planet. I'm curious as to how one might model this system that could > simulate a ship's movement through a 3-D grid. Matrix, 3-D array, graph. > None of these? Ideas? > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > >

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

There are two other tree-like structures that may contain interesting ideas for you: https://en.wikipedia.org/wiki/K-d_tree https://en.wikipedia.org/wiki/R-tree A straight octree has a couple of issues: it can become badly unbalanced, and if your objects have spatial extent then some of them will intersect more than one child region. The K-d tree fixes the balance problem, and the R-tree fixes both. The difficulty with the R-tree is that there are lots of different ways you might divide your things into regions, each with different balance properties. Furthermore if things are moving around then you will have to worry about rebalancing or else all your leaf regions will end up covering all of space! HTH, David On 14 August 2015 at 23:44, Michael Litchard wrote:

The octree looks promising.

On Fri, Aug 14, 2015 at 3:41 PM, Michael Litchard wrote:

...

I'm looking for unbounded but discrete, but I think conal's blog post can help me work this out.

On Fri, Aug 14, 2015 at 3:36 PM, Tikhon Jelvis wrote:

...

The problem with just modeling things is that certain questions become difficult. For example, it's often useful to know what thing is closest to some given thing, or what a thing's closest neighbor is.

Moreover, while there is certainly a lot of space out there, this is Haskell so we can model all of it lazily. That's what Conal's blog post is about: a practical way to lazily model images with no bounds and no resolution limit. On Aug 14, 2015 3:31 PM, "Jeffrey Brown" wrote:

...

I would not model space -- there's too much of it -- rather Things in space. Each Thing has a 3d coordinate (plus more geometric information, plus more information). Things can be rooms, and things can have position defined in terms of other things.

On Fri, Aug 14, 2015 at 3:23 PM, Michael Litchard wrote:

...

Well, thinking more about it, I think I want an 8-regular complete graph. I've been doodling and came to the conclusion pretty quickly that thinking of this space in terms of a grid wasn't quite right. I *would* like to only hold data of populated nodes if possible, to model an infinite space as David mentioned. I've been looking at fgl to help me think about this problem in terms of a graph. I'll think and tinker over the weekend and see if I can come up with something more articulate. Not committed to a graph, but I want a discrete structure and this looks like it fits the bill at the moment.

On Fri, Aug 14, 2015 at 2:00 PM, KC wrote:

...

I agree with Tikhon

But a sparse matrix might be conceptually simpler to start with But are sparse matrices easy to implement in Haskell and then is it easy to change the data structure layer on?

-- --

Sent from an expensive device which will be obsolete in a few months! :D

Casey

On Aug 14, 2015 1:50 PM, "Tikhon Jelvis" wrote:

> It depends on exactly what you want to represent and how you want to > do it. > > The first thing that comes to mind for me would be using an > octtree[1], which is the three-dimensional analog of a quadtree[2]. Conal > Elliott has an interesting point about using quadtrees to represent images > in Haskell[3], and you should be able to adapt the idea to indexing into a > three dimensional world with an octtree. > > [1]: https://en.wikipedia.org/wiki/Octree > > [2]: https://en.wikipedia.org/wiki/Quadtree > > [3]: http://conal.net/blog/posts/topless-data > > On Fri, Aug 14, 2015 at 1:44 PM, David McBride > wrote: > >> If you are thinking of it as a 3d grid, you might just have a (Map >> (Integer, Integer, Integer) Contents, where every room in this 3d grid that >> has something in it is in the map and every room that is empty space has no >> corresponding entry in the map. >> >> Then when you enter a room you can quickly look up what is in that >> room, then reasonably quickly check the neighbors in every direction to see >> what the ship might be able to sense were it to travel in that direction. >> >> In this case, space is infinite, but the datastructure is only as >> big as the amount of content you have. >> >> On Fri, Aug 14, 2015 at 4:34 PM, Michael Litchard < >> michael@schmong.org> wrote: >> >>> Star Wars MUD has a 3-D coordinate system such that (0,0,0) is >>> some planet. I'm curious as to how one might model this system that could >>> simulate a ship's movement through a 3-D grid. Matrix, 3-D array, graph. >>> None of these? Ideas? >>> >>> _______________________________________________ >>> Haskell-Cafe mailing list >>> Haskell-Cafe@haskell.org >>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe >>> >>> >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe@haskell.org >> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe >> >> > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe