# A* search in hexagonal grid with minimum turn radius

I need to run an A* search through a hexagonal grid. However, I have one nasty constraint: my vehicle can only turn so sharp. It has a specified minimum turn radius. I can't quite see how to translate this constraint into something I can use with each cell expansion to determine if a neighbor is viable or not. My grid cells are significantly smaller than the minimum turn radius.

I have an initial angle and location of the vehicle; it seems I need to keep a current angle with each cell. With that in mind, I'm not quite sure when I need to reset reference point. It seems that I cannot do that every cell or I will only go in a straight line.

I can translate that turn radius into a polygon (with several hundred sides) where each side length is the distance between my grid cells. I'm not sure how to use this, though.

• I'd suggest that your A* granularity is possibly too high. As for turn radius, does it increase with velocity? You could always look at the angle between nodes and add that to your weighting, above a certain amount and it becomes un-traversable. Commented Jun 22, 2013 at 14:21
• Traditionally we've adjusted the vehicle velocity to handle the corners planned for it. We would certainly like to push that back the other way such that we can optimize for time. With your suggestion of weighting the angle, I would need a function that could guarantee that my turn radius requirement is not violated in the aggregate (but I could still expand to individual cells when necessary). Commented Jun 22, 2013 at 14:28

Let's consider a generic turn-radius constraint.
It must consist of moving 'N' hexes in a straight line before a turn of 60 degrees is allowed.

This can be incorporated by:

• Extending the definition of a path-node with a counter: StraightLineHexesRequired
• Decrementing StraightLineHexesRequired on each node expansion if EntryDirection == ExitDirection and StraightLineHexesRequired > 0
• Continuation of the present direction is 0 degrees (heading). If you are using an ordered enum for heading, then an angle left is the operation -1 mod 6, and angle right will be the operation +1 mod 6. Does that help? Commented Jun 22, 2013 at 22:01