koobas.hobune.stream
Search very large waypoint-like system
Hi,
I am looking for a way to approximately find the closest waypoint to my player without having to check all the waypoints (as it would take too long).
Our system has half-million waypoints and relates to a traffic system
I have the waypoints stored as a list of Vector3 and I would prefer not to loop through those until I find one that is inside a close distance.
So I thought I could maybe lay some kind of Grid System over the scene to structure it into small pieces, but I hope someone might have a smarter solution to it :)
Best regards,
Fred
One of the standard grid systems used to organize 3D points is a OctTree. That should take you to other similar solutions (I believe an OctTree is for 3D -- probably a similar thing for 2D.)
quite - an OctTree or some sort of spatial hashing. (i wouldn't even know how to begin with 1/2 million points.)
my guess is, it could be OP is making some basic flaw in approach; for example it could be OP is charting out "every few inches" of even straight roads, or something like that, rather than (say) using some sort of higher-level representation (indeed, as is done in GPS/mapping software - one way or another).
Thanks Owen. A OctTree was what I had in $$anonymous$$d (just did't remember the name).
The following answer only relates to typical games with typical waypoint systems per your earlier question edit.
With "half a million" waypoints, you are talking about perhaps a GPS-like system or some sort of other novel structure, which is not really a ordinary game-like "waypoint" system, which I assumed you meant - sorry about that
It wouldn't really work like an everyday "waypoint" system in a game
It sounds like a fascinating project and you'll have to totally get in to spatial hashing
I don't think it would be possible to "just give" a solution as it would be novel custom engineering based on your overall concept. Cheers
First, note that it will not take too long :)
Computers are incredibly fast - how many waypoints do you have? If less than a few thousand you won't even notice it. Unless something is screwed-up.
Secondly this is an incredibly well-explored area in computer engineering. And it would be ridiculous in most situations to write spatial hashing (what you hint at in the "many squares" comment) yourself from scratch.
You can't really use unity or any game engine without a spline package,
so get something like SuperSplinesPro and the function you need ("get closest waypoint") is completely built-in, you know?
Footnote - - I mention SuperSplinesPro particularly; that traditionally was the very best spline package. Sadly it is now unsupported (no updates for 2 yrs) so, one can't realistically buy it -- but anyway find the spline package (free or paid) you like and use that for the issue at hand.
Thanks for your answer, but I ask because it takes too long :). I am making a game for mobile devices and have around 500.000 waypoints for my traffic system. So looping through them kind of affects my framerate as I have a lot of other stuff going on at the same time and I don't want to break my physics model (as I decreased the maximum overhead I allow for those calculations).
O$$anonymous$$ I have edited the question for you. Hope you find a good engineering approach. You must surely have some structures associated with the data (roads, suburbs, type of surface or whatever) so your solution would relate to that, and some sort of spatial hashing technique. Enjoy!
Yeah the data is attache to a road based environment. Thanks for the idea of spatial hashing. I'll definitely take a look at that :)
