0
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Have you looked into point vs line segment distance calculation, and spatial partitioning? \$\endgroup\$
    – DMGregory
    Nov 4, 2018 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, 2018 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, 2018 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, 2018 at 23:32

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .