Creating a random lat/long coordinate that is positioned in a physically reachable location

Issue

I have an application that generates some number of tokens around the current location of the user using a certain distance radius. The user will then have to run to some of those locations. The problem is that some tokens can be created in a lake,forest,ocean, or some other physically unreachable location. As a quick fix I just generate extra tokens and increase the proximity distance that determines if a user reached a certain location. I now want to improve this so that each token is located at a reachable location.

The only solution I have been able to come up with is using the Google Directions API to determine a path from the user to the token and use the last coordinate in the polyline as the new reachable location of the token. My problem with this is that I potentially have to post up to 30 requests to the Directions service simultaneously and I am worried that I might hit the query rate limit. I have not found anything definite about query rate limit.

So my question is whether anyone knows of a better solution or can give any input on the Directions query rate limit? Waiting 1 second between each request and forcing the user to wait up to 30 seconds is not a reasonable solution. Thanks.

UPDATE Using the solution that I described in the question does produces an OVER_QUERY_LIMIT, even if I wait 1 second between each request. Other then that the logic was sound and tokens that got a request thru were appearing in walk reachable locations.

Solution

After some 8 hours I finally got something working. So using the fact that each request can have up to 8 waypoints I can technically ask directions to 9 locations in one request. Here's what I am doing now:

Generate 9 random locations at a time. Pass the locations to my DirectionsComputer which returns the polyline path that goes through all 9 coordinates as a list of coordinates. Then I pick 9 location from the path and set them as the locations of my tokens. Now all my tokens are semi-randomly generated, always appear on a road, and I only need to do 4 consecutive requests to generate 36 tokens.

There are some cases where a few tokens are bunched together. For example, the coordinates which are originally located in the ocean get moved to the same beach. But for the most part, all my tests showed the tokens spread apart and I could tweak the rest.

Answered By - Alex