Game Data structures in haXe (R+tree)

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Game Data structures in haXe (R+tree)

tommedema
I'm working on a 2 dimensional flash game in haXe. In order to keep track of players and their positions within the infinite universe, I have to use a node/leaf kind of data structure.

I'm thinking about using a R-tree (http://en.wikipedia.org/wiki/R-tree) or R+tree (http://en.wikipedia.org/wiki/R%2B_tree). R+ because I'm not sure how the R-tree takes care of objects overlapping outside the current node.

Before I start implementing this myself, I was wondering if anyone has ever created such a system before and if it's publicly available? Eg. somekind of haxeDataStructures library?

Regards,
Tom

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Game Data structures in haXe (R+tree)

Simon Richardson

http://code.google.com/p/polygonal/source/browse/#svn/trunk/src/lib/de/polygonal/ds



On 22 May 2010, at 11:54, Tom wrote:

I'm working on a 2 dimensional flash game in haXe. In order to keep track of players and their positions within the infinite universe, I have to use a node/leaf kind of data structure.

I'm thinking about using a R-tree (http://en.wikipedia.org/wiki/R-tree) or R+tree (http://en.wikipedia.org/wiki/R%2B_tree). R+ because I'm not sure how the R-tree takes care of objects overlapping outside the current node.

Before I start implementing this myself, I was wondering if anyone has ever created such a system before and if it's publicly available? Eg. somekind of haxeDataStructures library?

Regards,
Tom
--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Game Data structures in haXe (R+tree)

tommedema
Thanks for that link.

Unfortunately, the only game data structure he has implemented so far is a QuadTree, which does not seem to be a good solution for me because

1) a QuadTrree is based on a world with boundaries (my universe is infinite)
2) his QuadTree implementation is not yet ready for production

I think I'll make a pretty basic node/leaf kind of system myself, like the R+Tree.

If anyone has experience with a R tree, I'd like to hear from you as I have some questions. Thanks.

Regards,
Tom

2010/5/22 Simon Richardson <[hidden email]>

http://code.google.com/p/polygonal/source/browse/#svn/trunk/src/lib/de/polygonal/ds



On 22 May 2010, at 11:54, Tom wrote:

I'm working on a 2 dimensional flash game in haXe. In order to keep track of players and their positions within the infinite universe, I have to use a node/leaf kind of data structure.

I'm thinking about using a R-tree (http://en.wikipedia.org/wiki/R-tree) or R+tree (http://en.wikipedia.org/wiki/R%2B_tree). R+ because I'm not sure how the R-tree takes care of objects overlapping outside the current node.

Before I start implementing this myself, I was wondering if anyone has ever created such a system before and if it's publicly available? Eg. somekind of haxeDataStructures library?

Regards,
Tom
--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Game Data structures in haXe (R+tree)

James W. Hofmann
In reply to this post by tommedema
Tom, I would hold off on implementing an R-tree until a scalability need arises. A far simpler option is to use a hash along an "implied" grid instead. You can make it two-dimensional by composing and parsing a string key or using the full flash Dictionary capabilities to make a paired-integer key, and then generate rectangular views by making multiple queries. This will be slower than a tree implementation, and breaks down in pathological situations where a node is dense with players, but the basic query is done in constant time with light memory usage and an infinite field. If you opt for large subdivisions, you will only ever need to query at most four spaces at a time(where a query at maximum size straddles an intersection point).

This is a lesson from experience: I've started avoiding more ambitious data structures until there's a real-world test case. For gaming applications, you often don't have enough data to accurately estimate the real-world scenario until final assets (and in this case players) are running in-game, so you could easily end up in premature-optimization land; as well, creating sophisticated data structures for the first pass blurs the lines between "buggy data structure" and "buggy integration". Using the naive solution lets you focus on basic reliability and utility for the game design instead, and then when you hit the point where the optimization is needed, you'll be well-prepared to regress it against the old, working solution.
Reply | Threaded
Open this post in threaded view
|

Re: Game Data structures in haXe (R+tree)

Chris Hecker

> This is a lesson from experience: I've started avoiding more ambitious data
> structures until there's a real-world test case.

Words to live by.

Chris


James W. Hofmann wrote:

> Tom, I would hold off on implementing an R-tree until a scalability need
> arises. A far simpler option is to use a hash along an "implied" grid
> instead. You can make it two-dimensional by composing and parsing a string
> key or using the full flash Dictionary capabilities to make a paired-integer
> key, and then generate rectangular views by making multiple queries. This
> will be slower than a tree implementation, and breaks down in pathological
> situations where a node is dense with players, but the basic query is done
> in constant time with light memory usage and an infinite field. If you opt
> for large subdivisions, you will only ever need to query at most four spaces
> at a time(where a query at maximum size straddles an intersection point).
>
> This is a lesson from experience: I've started avoiding more ambitious data
> structures until there's a real-world test case. For gaming applications,
> you often don't have enough data to accurately estimate the real-world
> scenario until final assets (and in this case players) are running in-game,
> so you could easily end up in premature-optimization land; as well, creating
> sophisticated data structures for the first pass blurs the lines between
> "buggy data structure" and "buggy integration". Using the naive solution
> lets you focus on basic reliability and utility for the game design instead,
> and then when you hit the point where the optimization is needed, you'll be
> well-prepared to regress it against the old, working solution.

--
haXe - an open source web programming language
http://haxe.org