I am making a 2D tile based game which involves having AI that needs to traverse the map avoiding obstacles in a natural and smooth path (NOT NECESSARY THE SHORTEST)
The orientation of the vehicle is also important in the example above the initial orientation of the vehicle is to NORTH but the orientation of the vehicle at the destination doesn't matter.
All I could do now is to compute the path using A* or a BFS fill through the center of the tiles.
This is an example of a desired path:
You can place control points in evenly spaced intervals and use this Bezier curve technique: How do I generate a smooth random horizontal 2D tunnel?
It allows you to smooth the actual path which interpolation wouldn't do.
You can control the smoothness by the step size between control points.
In order to get a more "natural" looking path, you may want to discount the cost of moving in a straight line. This technique will results in paths that have long straight stretches which you could more easily smooth with Bezier by applying the curve to the corners. Please notice that this means your graph will need edges between tiles that are far away from one another (the cost can be sqrt(distance)^1.5) and also connections between tiles that are not aligned on x or y axis. This means, you will need to make sure these edges don't overlap with obstacles, something you don't have to do with a simple graph that only allows movement between adjacent tiles.
Marco Pinter has an excellent write up on modifying the standard A* algorithm to calculate turning radius constrained path finding (also in 1 pg format & archive). Here's a summary of the portions that seem most applicable to your question.
Given starting point & heading, the shortest path to a given destination is found either by turning either as far left or right as needed until you are pointed at the destination & then moving forward in a straight line toward it as illustrated below:
Mathematically, this is solved by noting:
Thus, the starting position, heading & turning radius can be used to determine the position of the circles and basic trig (illustrated below) can then be used to find the point of exit from each circle to the destination. After finding both paths, a simple comparison given the shorter of the two.
Next, the above technique is used in the path finding by including a heading component to the search. In your case, instead of 2D grid of nodes, you need a three-dimensional space of nodes: 2 for the original XY coords & a third representing a heading (N, S, E, W, NE, NW, SE, SW).
A* pathfinding typically explores a neighborhood of 4 or 8 nodes. Unfortunately, this probably limits search in undesired ways. Consider the following:
The turning radius in the example prevents the sharp turn needed to go from a to b to c to d, but would allow a path from a to d directly. This requires expanding the search neighborhood from 8 to 24. In general, expanding the search neighborhood will allow additional solutions at the expense of additional calculation time.
Finally, because the underlying search space has changed, the search heuristic should be modified to reflect this. The typical A* heuristic measures the straight-line distance from a given position to the destination that ignores obstacles. The shortest turning path (also ignoring obstacles) provides heuristic that functions similarly, but favors positions that are oriented more directly toward the destination.
Pinter's articles covers a number of other related topics that may also be helpful to you. I found the path smoothing useful, but found the hit-check table didn't help me much. The article is was written in 2001, so not all of the optimizations presented are necessarily applicable today. When in doubt, code simply first, measure performance, 'optimize' if needed & measure again to make sure it helped.
