Search very large waypoint-like system


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 :slight_smile:

Best regards,


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 :slight_smile:

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.