bots are driving cars - how should they?

[MalteNuhn]

Hi there,

I am currently working on a traffic simulation software using java and delphi, but the language isn't that important right now.

My question is, if you have any good idea for an algorithm, so that a car can drive from one point to another. The important fact is, that there may also be obstacles in the "direct connection" between those two points. But how should a car / bot behave, in order to avoid crashing into that obstacle(s !!)? Important is, that the car should not have all information about traffic around itself, just the things, a real driver could see, if he looks out of his window.
Of course, the bot has to steer around that obstacle, but how "hard", and why?

Any ideas and suggestions?

Thanks a lot - Malte Nuhn

[galathaea]

This is not an easy problem, so be prepared to spend alot (if not most) of your coding time working on this problem. There is no really generic solution, as it really depends on the type of simulation you desire, but I will assume you have a 2d simulation with obstacles that never completely block a path. If you have streets with dead ends or other such, this will not work. Also, if you have an intended endpoint that is not accessible down all paths (a maze) this will not work. But here's the starter for one street with obstacles where there are no narrowness conditions:

In the program construct lines parallel to the direction of the street that in some sense fill the granularity of possible object blocking locations and that start at the current start location and end on an obstacle or the end of the street.
Now, if the line (or lines) emanating from the vehicle are blocked, scan the perpendicular to the blocking point to find the nearest parallel line that is unblocked.
Repeat and store the list of lines needed (and the points to move to and block points).
When you reach the end, you have constructed your first test path.
Now form the connected segment path of unblocked points and perform checks to see whether this path has blocks along it. If not, you are done with your path calculation.
If you found blocks, you need to check sliding the connection points along unblocked segements of the parallel lines for an unblocked path. If you find one, again you are done constructing your path. Otherwise you must start again, choosing new collections of parallel lines to connect.
Now that you have your connected, unblocked path, it is a simple calculation to figure out the steering of this path. It is more difficult if you need to allow for smooth turns.

This is the skeleton under the simple conditions I have given. Every extra option you add will require a complete overhaul of the algorithm, and as the obstacle conditions get more complex and street way get more maze-like, you will need to implement learning algorithms or more complex, homotopic-theoretic methodologies. I hope this helps!

[MalteNuhn]

wow! thanks a lot!!!

that was kindof the smartest answer I ever got in the Internet. Thanx man!

Very great, and somehow quite simple :)

VERY GREAT! ... i'm repeating it, but who cares ;)