6
\$\begingroup\$

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.

|improve this question
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Matt D Jun 22 '13 at 14:21
  • \$\begingroup\$ 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). \$\endgroup\$ – Brannon Jun 22 '13 at 14:28
3
\$\begingroup\$

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
  • If StraightLineHexesRequired != 0 then only expanding the hex dead-ahead
  • If StraightLineHexesRequired == 0 then expanding only the nodes dead-ahead, and the two hexes 60 degrees off of dead-ahead.
  • Setting StraightLineHexesRequired to N on every turn of 60 degrees.

This nicely generalizes to the case where N might be 0.

Update:
In the case where one is optimizing for time, and speed is a mutable parameter, and N depends on speed, one would add nodes to the open set with current speed as well as plus-one and minus-one on the speed scale, with appropriate new values of StraightLineHexesRequired

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ I'm trying to understand what you're saying here. It seems you have an assumption that my initial angle is 0 deg? And once I make the 60 deg turn, I'm now facing that direction or I'm somewhere between my previous angle and the additional 60? \$\endgroup\$ – Brannon Jun 22 '13 at 21:39
  • \$\begingroup\$ 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? \$\endgroup\$ – Pieter Geerkens Jun 22 '13 at 22:01
  • \$\begingroup\$ I ended up using a discrete line algorithm for determining "dead ahead". \$\endgroup\$ – Brannon Jul 11 '13 at 3:14
  • 1
    \$\begingroup\$ OK. I have just converted my Pathfinding algorithm to a Bidirectional ALT implementation, which now runs 240 * faster on my 760 x 420 test map. The pre-processing takes about 4 seconds running in parallel on i7 cpu, and consumes about 6MB of additional storage for the map. Longest test path is now calculated in < 5 ms: hexgridutilities.codeplex.com \$\endgroup\$ – Pieter Geerkens Jul 11 '13 at 3:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.