I have a road network and a vehicle that is current off the roads. I want to find the shortest path to any road. An obvious solution is to run a pathfinding algorithm between the current vehicle location and all the points on the road, but that's hardly scalable.

I am curious to know if there is an algorithm out there that I could use to maximize the performance of this operation.

  • 1
    \$\begingroup\$ Have you looked into point vs line segment distance calculation, and spatial partitioning? \$\endgroup\$ – DMGregory Nov 4 '18 at 23:11
  • \$\begingroup\$ I did but I felt my problem wasn't so much finding the closest (geometrically speaking) road, but rather the most accessible road. Like a road might be close, but not accessible from the current location. Though this makes me think of an optimization that might help, assuming most points are indeed accessible, I can probably sort my candidates and do path finding in that order until I run into a good one. \$\endgroup\$ – mprivat Nov 4 '18 at 23:26
  • 1
    \$\begingroup\$ Sounds like you should tell us more about your level content or setup and what constitutes "accessibility" — until now, all we know is that you have a road network, not any notion of terrain or obstacles off of the roads. \$\endgroup\$ – DMGregory Nov 4 '18 at 23:28
  • \$\begingroup\$ The only navigation contraints at the moment are the slopes of the terrain and terrain type (land vs water for example0. The vehicle cannot travel up a slope that is too steep. That would make some areas not accessible, for example islands. The root of the problem I have I guess is I'm trying to find the shortest path between my location and any one of the sampled points in my roads. \$\endgroup\$ – mprivat Nov 4 '18 at 23:32

When you don't need to arrive at a specific destination, or don't have enough guidance to estimate your distance to a destination with an admissable heuristic for A*, you can use Dijkstra's algorithm. (Effectively, A* with no heuristic)

This will enumerate shortest paths from your start position. As you explore each node in order of path distance, you check whether it's a goal (ie. whether it is a road, any road). If it is, you have found the shortest path to a road.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.