A* for large search spaces
You do not need to have a graph to run A*.
You only need to be able to query where you can go from a given node. So, when A* wants the lists of the neighbor nodes, you generate them. You can even lazily generate※ them along with the heuristic values.
Each node will be a position plus an orientation (and probably a speed ...
Add the speed of the vehicle (and the direction) to the search space and let it affect which the possible neighbouring nodes are.
This means that 2 nodes are the same if and only if they are in the same position, have the same direction and are for the same speed.
When generating new nodes you have the range of full left and right possible for the speed, ...