   Deciding on an R-Tree... and coding it!
  Hi there. I was thinking of using some variation of R-Tree for my game to keep track of spatial relations.Situation:- I'll have lots of spells doing things like GetNearest____ and modifying it, etc. so I thought it would be a good idea. I'll also be determining visibility for AI agents based on the screen they're on, which should be trivial with a window query. - As far as the map goes, there shouldn't be any two identical rects, and there will probably be around one dozen to a few dozen rectangles on any given map.- A main point is that since the tree will contain objects which will move, I need a way to efficiently re-insert such objects without destroying and recreating the whole tree from bulk. - On a side note, it would be nice to be able to keep track of and query, say, a certain type of object. Like, GetNearestStatic.Questions: - I can't seem to find any good guide for coding the framework of any of the variations of R-Trees in C++. The only thing I found was a dead subversion link to the source of a library that looks like it was last updated in 2003. Are there any good resources for this? I'd like to code this myself instead of using a library, but I don't really understand all the terminology when they start speaking in symbols in publications...- Also, does anyone have knowledge of the different types of R-Trees in practice? I have read about the variations, and spent a good chunk of time wading through a publication on PR-Trees to no avail. I guess they all have efficiency advantages but I'm having trouble predicting which would be best for my situation.   
  I googled and found:http://www.superliminal.com/sources/sources.htm#C%20&%20C++%20Code   ;Quote:Original post by SudiI googled and found:http://www.superliminal.com/sources/sources.htm#C%20&%20C++%20CodeThanks!It seems this was written with some compiler-specific (MSVC) stuffs, though.I'm getting some pretty funky errors trying to compile it with g++, needless to say.Edit:I've tinkered with the .h and gotten it to compile with g++. However, I'd still welcome any good learning resources for R-Trees so that I might code my own implementation.[Edited by - chinchi11a on June 29, 2009 9:06:38 PM]