Hey guys, I am working on the AI for a game where cars are driving around (3D). To get them from point A to B I implemented some pathfinding. Here's how I am doing it currently. First I set up some "important" points, see here: The connections don't mean anything, only the points are important. The shot shows my test city from above. The first thing I do is to calculate the visibility from one point to all others. If it's not visible, then the way is considered to be blocked. The next thing is to test which of the remaining routes do work. For this I run the full physics simulation and create a sphere (represents the car) at the starting point and set its velocity so that it points towards the next point. If the sphere can reach the target point within some time limit then the path is considered viable. The time and length it to took to get from A to B is written down. Example: From point 1 you can see points 2 and 4 (also 5 and some others). The connection between 1 and 3 is discarded because there is no line of sight. Then the physics sphere tries to get from 1 to 2 and from 1 to 4 and succeeds. Some steps later the connections for points 2 are evaluated. There are line of sights between 2-1, 2-3, 2-47 (amongst some others). There's a clear line of sight between 2-3, so the physics sphere is run. It is stuck in the water and does not reach point 3 within the time limit. So this way is also considered to be blocked. This goes on with all the points I have and I get a nice edge-weighted graph with all possible connections between the points. The cost function is just the time it took the sphere to get from X to Y for now. Then I perform a search with Dijkstra's algorithm on it and it returns the "shortest pathes". Now my problem is that these pathes are not really optimal. For example it tends to return the path regardless of the number of turns. Often it would be easier to drive along some straight route - even if it is longer - than to drive the shortest path with lots and lots of turns. In reality the car has to break for these turns and this will make these parts much slower than the straight ones. Finally, my question. How do I get the "best pathes"? I tried to think about integrating the turning around corners thing into the cost function somehow, but this can't really work. The cost function would depend on two connections and the angle between them (the angle of a corner). I have no idea how to integrate this concept into the normal pathfinding. Any ideas how to approach this? Are there known solutions for this? Thanks for looking into this, -Matthias [Edited by - Nitrogenyx on August 22, 2007 8:06:40 AM]

Split each node in the graph into N nodes, one for each edge connected to that node. Each of these nodes now has a single edge. These edges represent moving straight from one place to another. Now add edges to connect each of these new nodes with all the other new nodes that were split from the same original node. These edges represent transfering from one path to another, so their cost depends on things like how long it takes to make a turn. You might also want to create separate nodes for each direction a car can drive at a particular place, since right turns might be faster than left turns, for example. At a 4 way intersection, there would be 8 nodes, two for each direction in which the car can pass through the intersection, and those two would correspond to opposite directions. Some of these nodes might not be connected, depending on which turns are allowed.

Thanks a lot for this answer. I was thinking to split the nodes somehow, but I didn't have the idea to connect the new nodes with themselves (to represent a path change). This is a very sound concept.
I will try to implement this over the next day and let you know whether it worked :)

Thanks again.

-Matthias

Hello,

I have been working more on this today. Although I haven't done the actual implementation in code yet, I worked out your comment with pen and paper. Below are my results. The first picture shows the basic network. The second image depicts the network with the changes applied. Red lines show connection within a "single node" (spatially), black lines represent the original connections. I didn't add the connections for different directions for the sake of simplicity.




This is already an improvement over the last solution. Now I have another question. Let's take the "sharp turn" connection for example. Which cost do I have to assign to it? The cost is really dynamic, because it depends on the car's speed which again depends on the history of the nodes visited so far. If the car is very fast the cost would be very high, because it has to break a lot and then turn. If the car arrives already very slow at the node the cost would be very low, because it does not have to break.
For example the cost would probably be higher if the car had started at the lower left node compared to the upper left node.

How do I incorporate these kinds of dynamic costs?

Thanks,
-Matthias

Add an additonal cost based on the angle between the nodes perhaps?

Something like K * sin(theta) maybe, this will equal K for theta = 90 degrees and 0 for 0 degrees? You could probably give a different value K for each car based on its turn rate too.

This won't work with angles > 90 degrees though so you probably want to rule those out by applying a very large cost.

Thanks for your answer.

The angle will surely be part of the calculation, but it's not enough to determine the cost. Depending on the vehicle speed the angle could be up to, say 90°, without having to break. If the vehicle is very fast and encounters the very same 90° corner it will have to break a good deal before it is able to pass it. In the later situation the cost has to be higher. My problem is how to find the shortest path if the cost of an edge depends on the travelled path.

-Matthias

It might be time to consider not explicitly representing the search space. By this I mean that nodes of the search graph could be generated as it is searched. The graph representing the roads would still be used, but the actual nodes searched would include not only position but also direction and speed.

Another solution is to use the node splitting idea and just generate the edge costs as the graph is searched. That's probably simpler.