3

I'm looking for simple car parking algorithm for a game.

The positions of car and garage each defined by 3 numbers (x, y, theta). Where x and y - center of the object and theta - angle between the object axis and the X axis.

enter image description here

The car movement is simplified - it's a dot (no need to calculate exact tire movement) that can drive with fixed speed back and forward or turn following a circle with the radius R (the turning radius could be fixed or flexible - doesn't matter - any option would be fine for me) and it has no inertia or acceleration.

The garage has 3 walls that shouldn't be touched by the car. It's possible to use exact dimensions for collision, but for simplicity the collision checked by measuring the angles between car and garage and the distance between car axis and the garage center. When car and garage are close enough (distance between centers is less than some constant CloseEnough) the collision checked by (alpha, d) < (maxAlpha, maxDistance)

enter image description here

The world simulated by ticks, we take the current car controls - moving direction forward or backward and the turning angle and calculate the car next position.

The algorithm should produce series of control commands, like [forward, left], [forward, left], [backward, straight], [forward, right].

It's ok if it will be iterative and produce one command at a time - then check what's going on on the next tick and produce another one. It can ask the simulation engine to simulate and produce new coordinates given the control command or use simulation engine to try multiple options and choose the best one.

Also it's ok if it does it by series of approximated movements, like it tried once - missed, tried another time - get closer, and third time - finally parked (but it should be more or less reasonable and don't do tens or hundrends of back and forth iterations).

Alex Craft
  • 13,598
  • 11
  • 69
  • 133
  • 2
    I think it would be beneficial to coördinate transform the Garage into a fixed position. – Neil Jan 12 '19 at 00:55
  • This type of robot is "non-holonomic", since its motion is constrained. The vehicle you're describing perfectly matches [Dubin's model](https://en.wikipedia.org/wiki/Dubins_path). You could likely convert the algorithm described on that page, which handles point and orientation control, into a parking algorithm simply by handling the case where the car has to go around the parking spot – c2huc2hu Jan 17 '19 at 18:57

2 Answers2

1

There are a few kinks to work out, such as how much precision is required for a successful dock, and how much precision the "ticks" allow. You'll have to experiment. But here's a general approach:

Without Loss Of Generality, assume the car moves along straight lines and minimal-radius circles. (Larger circles will give a shorter and gentler ride, but leave that for later.) In practice this will mean alternating line-circle-line-circle-line...

The ultimate goal is to drive straight into the garage.

The goal before that ("penultimate") is to get onto one of the circles tangent to that path, as close to the garage as possible. So if the garage is at (0,0,0), the circles are centered at (0, +/1r). In general, if the garage is at (x, y, θ) the circles are centered at (x-/+rsinθ, y+/-rcosθ).

The goal before that ("antepenultimate"?) is to get from one of the circles the car is already on (hard-left or hard-right) onto the line that is tangent to both that circle and the target circle.

The goal before that is to get around the garage, if need be, so that the car can perform the moves already described without hitting it. One way to approach that problem is to draw a circle centered on each corner of the garage, and go from circle to circle.

Is that enough?

Beta
  • 96,650
  • 16
  • 149
  • 150
0

You might be helped by Dubins path, as mentioned before using circles whose radius is based on the car's narrowest curvature and tangent lines linking those circles, main aim being finding where to lay those needed circles on your map and when you have it you'll be almost done, I guess!

victor fouquet
  • 1