I have a search problem, finding the shortest path for 3 vehicles to their parking spots, in a continuous environment (inputs are continuous for velocity, turn speed) and the location is continuous, ie. the landscape is a discrete grid but within each grid it is continuous.
There are areas where the top forward velocity and turning velocity are lower than the standard area. The vehicles cannot be within a certain distance of each other until they are both in the parking lot. Also, all 3 have to get parked within a certain time limit so the key seems to be to avoid a bottleneck at the entrance of the parking lot. Furthermore, unless the vehicles are in the parking lot, they have to stay in motion with a minimum velocity for the sticky slower area mentioned above as well as the standard speed area.
Are there any examples of using A* for such environment or do I need to discretize it as much as possible? What other algorithms are recommended for this type of problem?

  • $\begingroup$ Why does it matter that there are 3 vehicles? Can you take any solution for 1 vehicle nad use it 3 times? Or are there some requirements not mentioned here, e.g., about the interaction between the vehicles? What methods have you considered for continuous pathfinding (if you ignore the grid)? I imagine the combination of discrete + continuous pathfinding will be at least as hard as continuous pathfinding without the grid. Are you familiar with red3d.com/cwr/papers/1999/gdc99steer.html? $\endgroup$
    – D.W.
    Feb 15, 2022 at 7:19
  • $\begingroup$ @D.W. I added more info for clarification. Thanks for the link, that's very high level and useful. $\endgroup$ Feb 16, 2022 at 4:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.