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\$ Commented 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\$ Commented 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\$ Commented 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\$ Commented Nov 4, 2018 at 23:32

1 Answer 1

Reset to default
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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.