Given a grid system where some coordinates are marked as impassable, how to find natural-looking car driving path between two locations?

Question

I can compute an A* path, but I get only cardinal directions from that. A 45˚ path would look like "up 1 left 1 up 1 left 1 up 1 left 1..."

My specific question is, given a grid with a pathing solution involving non-90˚ paths, how do you figure out those paths?

I have curves working as described here: https://gamedev.stackexchange.com/a/121016/66189

but I just don't know how to combine it with areas that block the path. I've seen a little bit about "pulling the string", but very little detail.

Another issue I have is that A* will suggest that I immediately go "backwards" for the facing of my car or take way too sharp of a turn.

edit: How do I make sure I get the blue line, not the red line, which is unusable, even though A* loves it:

The issue I'm seeing here is that a block that isn't usable on the red path is usable for the blue path -- but A* would mark it as unusable or as having a very bad score when checking the red path.

Answer 1

like in RTS games you Can tag some areas in your solution with a value , representing the cost of traveling that path, so that A* can find the shortest , less costly path , or take a look at this article on Gamasutra

Toward More Realistic Pathfinding: Adding Realistic Turns

which uses "postprocessing solutions for smoothing the path"

quote:

"For a better solution, the first thing we need to know is the turning radius for our unit. Turning radius is a fairly simple concept: if you're in a big parking lot in your car, and turn the wheel to the left as far as it will go and proceed to drive in a circle, the radius of that circle is your turning radius. The turning radius of a Volkswagen Beetle will be substantially smaller than that of a big SUV, and the turning radius of a person will be substantially less than that of a large, lumbering bear."

Answer 2

Instead of having a purely 2D grid add a third wrapping dimension with the angle of the car. Then you can add the orientation of the car to the initial position and restrict the turning radius.

Selecting the next possible positions should then be restricted to straight ahead in same orientation, turn to the left with a more leftward orientation and a turn to the right with a more rightward orientation. (add reverse paths as needed)