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

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.

• Do you need to generate the path ahead of time? Or could you use something like steering to follow the path nodes you have generated? Sep 13, 2016 at 23:22
• I'd like to have the path ahead of time, but without a path how do you know if you're heading towards a dead end -- potentially meaning a curve you can't make because of too tight a turning radius? Sep 13, 2016 at 23:29
• You find the "rough path" with A*, perhaps do some optimizations, then steer towards each node in the rough path with steering based on the steering capabilities of your car. Sep 13, 2016 at 23:34

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

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."

• This link looks very good, thank you. -- upon further reading, this is everything that I've spent a long time trying to figure out all in one article. There's a lot here, but this is exactly what I want. Sep 14, 2016 at 0:44
• your welcome ,that took me a minute , using Google , Keyword : "A* path finding angle limiting" Sep 14, 2016 at 1:26

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)

• Turns out that's a LOT simpler said than done, as is evidenced by the sheer amount of detail in the link from the other answer. If the moves were discrete along the grid coordinates and fixed along simple rotational boundaries, it would be simple, but realtime animation doesn't lend itself to those restrictions. Sep 14, 2016 at 8:59
• @xaxxon yeah at that point you will have to move away from fixed grid points and 8-way motion to full arbitrary 360° motion. Sep 14, 2016 at 9:02