A* uses exponential in memory. There are two common improvements for A* to deal with that:

Please remember that you are feeding notes to A*. A* is still in charge of picking the best path.

A* memory use is exponential. There are two common improvements for A* to deal with that:

Please remember that you are feeding nodes to A*. A* is still in charge of picking the best path.

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.

You, of course, need your heuristic. And whatever heuristic you have for position only would remain admissible for these nodes.

For tweaks, consider making the time interval and the angle step smaller as a function of nearby obstacle or the distance to the goal. That should give the car more maneuverability where needed.

Alright, the drawback is that we are increasing the search space for A*, and this is likely going to result in a higher execution time.

Breaking A* so that it conforms to a time budget is harder, yet possible. Turn the A* algorithm into a state machine. To do that, you write it as continuations. Then represent the continuations as data. Immutable data structures are great for this. with that, you can store the current state of the algorithm when the time budget for it is up and extract partial results.

The partial results of A* up to where it could run in the time budget have some known cost for some nodes, pick among the nodes with known costs the node that would bring the car closer to the goal as per the heuristic, so the car can start driving, even though the search didn't have time to figure out the path to the goal.

However, you can improve upon this.

If you create a nav-mesh, with large convex areas. The connectivity of the areas is valid, regardless of the speed of the car. You can path find in this coarse nav-mesh, so you can figure out the general path before you worry about car speed and orientation.

Then you can path find with more complex rules from one areas of the nav-mesh to the next. I know that A* says that you compare the node to the goal. Don't do that, instead you are going to implement the goal as a predicate, which says "it is in the next nav-mesh".

This also ensures that the partial results I was talking about earlier will not result in the car going the wrong direction and having to backtrack. Thus you can have some confidence to resume the algorithm. You would have to check if the algorithm has gone a different path than the one the car went, and if so, start searching again from the current position of the car.

If all goes well, a single execution of this modified A* can be used to find a path that passes the nav-mesh areas in order and then reaches the goal. How? Well, you satisfy the predicate, you have partial results, then you use them to resume with a new predicate for the next step.

A* for large search spaces

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.

You, of course, need your heuristic. And whatever heuristic you have for position only would remain admissible for these nodes.

※: In general, you want a method that gives you the next neighbor. And you call it to iterate. That is, you do not generate all the neighbors before iterating over them.

Memory problems

A* uses exponential in memory. There are two common improvements for A* to deal with that:

• Iterative Deepening A*: You use the heuristic of the distance from the start node to the goal to set a limit of how long a path should be. If the cost is greater than this limit, you consider the node closed.

  If you did not find a solution, you increase the limit, you move all the closed nodes to open, and explore them again.

• Memory bounded A*: There are nodes in the open set that are unlikely to lead to a better solution. So, you are going to get rid of them.

  The idea is that you have a maximum number of items in your open set. If you reach that capacity, you remove the worst. So you never have more than your maximum, and thus your open set does not run out of memory.

Exploring a car driving space

For tweaks, consider that making the angle step smaller will result in more nodes. You may, for example, make it a function of nearby obstacle or the distance to the goal. You can do something similar to time steps. That should give the car more maneuverability where needed.

Two level search

If you create a nav-mesh, with large convex areas. The connectivity of the areas is valid, regardless of the speed of the car. You can path find in this coarse nav-mesh, so you can figure out the general path before you worry about car speed and orientation.

Then you can path find with more complex rules from one areas of the nav-mesh to the next. I know that A* says that you compare the node to the goal. Don't do that, instead you are going to implement the goal as a predicate, which says "it is in the next nav-mesh".

Once you have found a solution that moves the car to the next area of the nav-mesh, you can reconstruct the path, clear memory, and continue the search to the next area of the nav-mesh, which will give you another section to add to the path. You continue like that until you are at the last area where you search for the goal position.

Time budget

Breaking the search algorithm so that it conforms to a time budget is harder, yet possible. Turn the search algorithm into a state machine. To do that, you write it as continuations. Then represent the continuations as data (see "defunctionalization"). Immutable data structures are good for this. With that, you can store the current state of the algorithm when the time budget for it is up and extract partial results.

The partial results of the search algorithm up to where it could run in the time budget have some known cost for some nodes, pick among the nodes with known costs the node that would bring the car closer to the goal as per the heuristic, so the car can start driving, even though the search didn't have time to figure out the path to the goal.

If you use the two level search as described above, you can have some confidence that the path is going in the correct general path, and that it will not have to do a U-turn. For the small chance of that happening, you would have to check if the algorithm has gone a different path than the one the car went, and if so, start searching again from the current position of the car.