2
\$\begingroup\$

grid layout with diagonal path to goal

I can compute an A* path, but I get only cardinal directions from that. A 45˚ path would look like "up 1 left 1 up 1 left 1 up 1 left 1..."

My specific question is, given a grid with a pathing solution involving non-90˚ paths, how do you figure out those paths?

I have curves working as described here: https://gamedev.stackexchange.com/a/121016/66189

but I just don't know how to combine it with areas that block the path. I've seen a little bit about "pulling the string", but very little detail.

Another issue I have is that A* will suggest that I immediately go "backwards" for the facing of my car or take way too sharp of a turn.

edit: How do I make sure I get the blue line, not the red line, which is unusable, even though A* loves it:

enter image description here

The issue I'm seeing here is that a block that isn't usable on the red path is usable for the blue path -- but A* would mark it as unusable or as having a very bad score when checking the red path.

\$\endgroup\$
  • \$\begingroup\$ Do you need to generate the path ahead of time? Or could you use something like steering to follow the path nodes you have generated? \$\endgroup\$ – MichaelHouse Sep 13 '16 at 23:22
  • \$\begingroup\$ I'd like to have the path ahead of time, but without a path how do you know if you're heading towards a dead end -- potentially meaning a curve you can't make because of too tight a turning radius? \$\endgroup\$ – xaxxon Sep 13 '16 at 23:29
  • \$\begingroup\$ You find the "rough path" with A*, perhaps do some optimizations, then steer towards each node in the rough path with steering based on the steering capabilities of your car. \$\endgroup\$ – MichaelHouse Sep 13 '16 at 23:34
1
\$\begingroup\$

like in RTS games you Can tag some areas in your solution with a value , representing the cost of traveling that path, so that A* can find the shortest , less costly path , or take a look at this article on Gamasutra

Toward More Realistic Pathfinding: Adding Realistic Turns

which uses "postprocessing solutions for smoothing the path"

quote:

"For a better solution, the first thing we need to know is the turning radius for our unit. Turning radius is a fairly simple concept: if you're in a big parking lot in your car, and turn the wheel to the left as far as it will go and proceed to drive in a circle, the radius of that circle is your turning radius. The turning radius of a Volkswagen Beetle will be substantially smaller than that of a big SUV, and the turning radius of a person will be substantially less than that of a large, lumbering bear."

\$\endgroup\$
  • \$\begingroup\$ This link looks very good, thank you. -- upon further reading, this is everything that I've spent a long time trying to figure out all in one article. There's a lot here, but this is exactly what I want. \$\endgroup\$ – xaxxon Sep 14 '16 at 0:44
  • \$\begingroup\$ your welcome ,that took me a minute , using Google , Keyword : "A* path finding angle limiting" \$\endgroup\$ – Dr.MSM Sep 14 '16 at 1:26
0
\$\begingroup\$

Instead of having a purely 2D grid add a third wrapping dimension with the angle of the car. Then you can add the orientation of the car to the initial position and restrict the turning radius.

Selecting the next possible positions should then be restricted to straight ahead in same orientation, turn to the left with a more leftward orientation and a turn to the right with a more rightward orientation. (add reverse paths as needed)

\$\endgroup\$
  • \$\begingroup\$ Turns out that's a LOT simpler said than done, as is evidenced by the sheer amount of detail in the link from the other answer. If the moves were discrete along the grid coordinates and fixed along simple rotational boundaries, it would be simple, but realtime animation doesn't lend itself to those restrictions. \$\endgroup\$ – xaxxon Sep 14 '16 at 8:59
  • \$\begingroup\$ @xaxxon yeah at that point you will have to move away from fixed grid points and 8-way motion to full arbitrary 360° motion. \$\endgroup\$ – ratchet freak Sep 14 '16 at 9:02

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.