6
\$\begingroup\$

Is there pathfinding algorithm which takes car steering into account?

I have large space where user can place cars (trucks actually) and other blocker objects. Objects can be placed vertically or horizontally oriented and have different sizes (may be 3x6 or 2x4 or other size). User needs to be able to select new location for any car - then I need to calculate how can that car move to selected location.

I have pathfinding working, and I can find paths with different size but only for square objects.

Update:

Pathfinding need to give only path that is possible with that type of car. For example on empty map with only one car, if user selects new location right next to its current location, car can't strafe or turn in place it has to either reverse and steer or do U turn or something. Also it must ensure that car orientation at end is what user requested.

\$\endgroup\$
  • 1
    \$\begingroup\$ just make turning more expensive than going straight ahead \$\endgroup\$ – ratchet freak Nov 5 '14 at 15:28
  • \$\begingroup\$ You could also look into steering forces \$\endgroup\$ – fastinvsqrt Nov 5 '14 at 17:00
  • \$\begingroup\$ did you ever manage to come up with a working solution? \$\endgroup\$ – xaxxon May 4 '16 at 22:37
  • \$\begingroup\$ I did not found solution. I used regular pathfinding with checking for points at which it need to change direction if it can steer (using premade bitmap patterns), and check if its ending facing is either correct or opposite (then we added small extra reversing path). There was a lot of problems with this so we removed it. \$\endgroup\$ – user3256672 May 7 '16 at 4:29
  • \$\begingroup\$ Another thing was when more cars are placed, only way to reach target is to move blocking car, and in order to move blocking car need to move another. In my case it was required to let user select location exactly as cars were used to create barricade. \$\endgroup\$ – user3256672 May 7 '16 at 4:32
2
\$\begingroup\$

There is!

You need to path find in a 3 dimensional space if the car is steering in a 2d space and use the third dimension as the cars angle. Then you could use A* or any other graph path finding algorithm and you"re good to go. The algos I go with are usually probabilistic roadmap or rapidly exploring random trees to generate the graph and A* to find a fast path.

Obviously you need to adjust the "collision space" or passable area differently for each angle of the vehicle you are moving. I usually use a low res 3d bit (2d for the plain and 1d for the angle) array to represent the passable area and then randomize vertices in the 3d-space made from the slices of adjacent 2d slices, each representing one specific angle. Since this is not 100% perfectly accurate (only 99%) I usually add a 2-3 bits thick border around obstacles to make it obvious the vehicle is not colliding with anything.

You need to know if there is a path between two vertices, for that you'll need to draw a trace line in that 3d space and check if it collides with 1 bits. This should be a question on it's own as there is a solution based on Bresenham's line algorithm.

Again to clarify, obstacles are calculated against the center of the "truck" in your case while taking the angle and shape of the track into account. Meaning that if the track is 5 units long and 2 units wide, and the center is less then two and a half units away from an obstacle, that area may be impassable depending on the angle of the track in that slice.

\$\endgroup\$
  • \$\begingroup\$ This solves non square objects problem. I updated question with more explanation. How to ensure that car will end in correct orientation at end? \$\endgroup\$ – user3256672 Nov 6 '14 at 10:24
  • \$\begingroup\$ @user3256672 Like I explained, you are traveling in a 3d space where the third dimension is an angle, you are finding the shortest path between the current position and angle to the desired position and angle. \$\endgroup\$ – wolfdawn Nov 6 '14 at 17:11
  • \$\begingroup\$ Do you have any links to any sample implementations of creating that third dimension? I'm having trouble following what you're saying on how to create it. I sort of understand the concept of what you're saying but can't figure out exactly where to start.Presumably there's some path to get to any position at any orientation, so I don't understand how to decide what to set the 3rd dimension bit to. \$\endgroup\$ – xaxxon May 4 '16 at 22:20
  • \$\begingroup\$ My specific question is here, but it's mostly a dupe (I didn't find this question/answer until after): gamedev.stackexchange.com/questions/121002/… \$\endgroup\$ – xaxxon May 4 '16 at 22:32
  • \$\begingroup\$ @xaxxon Hi. Do you have any obstacles in the route? Naive path finding in 3d (2d + angle) is very expensive computationally for a game. The 3rd dimension is the angle. Can the object (vehicle, car etc.) be placed in some specific angle in a specific position? You then create a low res 3d array of bits. (i, j) are x and y 2d positions. Then k is the angle in a discrete number. You can then connect viable positions with other viable positions (how much can the car turn while moving). \$\endgroup\$ – wolfdawn May 5 '16 at 16:03

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.