Look at these 2 outcomes
The source is 6,6 and destination is 10,10

       F    G    H
7 7 1 1735 1420 315 << H should be higher
6 5 7 1907 708 1199

The G cost is okay, the one that taking turns (direction 7) should cost less than
a closer node with wrong direction.
But when you look at the H cost, as the opened node is 7,7, the true heuristic will be less
than 6,5 because it will take an easier path no matter what the direction is.
But I still prefer 6,5 to 7,7... how do I increase the true distance of 7,7.
So that 6,5 should be chosen instead?
Thanks
Jack

I am using Marco Pinter's article, sorry, I can't find it on the net anymore.
But when I run the program,
For the following parameters
start: 6,6
end: 30,30
startdirection(radian): 4.7
I've got the following results back

Notice I am running the original program from the author.
The agent turning radius is 1.2 meters and agent size 1.3 meters.
You see that in the first step, the agent takes abrupt turn from 6 to 1
which is extremely sharp. I test for many many times, even with startdirection of 1.57
that is actually facing towards the destination, the results are the same

I then adjust the tunring radius to 2.0, 4.0, 6.0, nothing changes
Why?

0 X:6 Z:6 Dir:6

1 X:7.5 Z:7.5 Dir:1

2 X:8.5 Z:8.5 Dir:1

3 X:9.5 Z:9.5 Dir:1

4 X:10.5 Z:10.5 Dir:1

You can use a web archive to find it and the source code. What parameters are you using for the search? Are you doing a 24 tile search, a 48 tile search? I also believe there are some bugs in the sample.

I've implemented a version of this in the past, though I moved portions of it over to vectors. I recall that a lot of it is playing with how you determine your costs, for example, I changed the distance heuristic of the Dubin's curves, and counted the turning portion of the distance to be more expensive than the straight line portion.

Hi

Got a new problem.

The search is very slow when the source and dest are very far apart.

I am doing a 48 tile search (which sometimes accumulating to thousands of nodes in the opened list)

I am doing some relaxation too, like giving a preferred direction to the heuristic score to reduce the number of opened nodes.

and doing some f and g score first testing... to no avail

But just still too slow.

But I'll look into what you suggested.

Jack

The algorithm is slow, and I wouldn't use it for really long path searches. At that point I'd break up the search into a hierarchical one. There are some minor speed-ups you can do by profiling and seeing where you're spending the most time, and by pre-calculating some things. For example, if you know your objects width and turn radius, you can tell which tiles it will cover when doing any of the moves to the 48 tiles, so you're not doing any angle / dubin calculations at that point, just checking for blocked tiles. (Ex: moving to a tile one north, and one east when the object is facing north, the object will go through tiles {+1,0}, {+2,0}, {+2,+1}, which you can then use to map those offsets to the actual tiles, check if the path is blocked, etc.

If you're map is mostly open, you can also shortcut by seeing if you can do a dubin directly to the goal, and if so, not doing any 48 tile searches. This I imagine would also help a lot if your hierarchical paths tended to use roads.

In other words, I just do a regular astar, and expand out according to agent width, turn radius etc from the astar center and check if they are blocked, and do a smooth out pass later on?

Not exactly. Hierarchical means that you basically have two (or more) levels of search. It's like when you're plotting how to get from your house to a place in the city. The search is broken up by, "How do I get to the nearest freeway", "What freeway exit do I take", and "How do I get from this freeway exit to the destination". Similarly if you break up your incredibly large area into multiple regions, you could then break up the pathfinding. For example, your regions could have nodes for the entrances/exits to other regions. Then, for example, if you have regions A,B,C,D like so:

            ============= ===========
============|            |           |
     A      *     B      *           |
            |            |           |
            |======*=====      D     |
            |            |           |
            *      C     *           |
============|            |           |
            =========================

If the object is in A, and needs to get to some point in D, it can pathfind to one of it's two exits, then pathfind to the exits, etc.

As for the other optimization, let me see if I can draw something in MS Paint real quick.

[attachment=31167:HorribleArt.png]

What I'm trying to get at, is that you can precalculate all the dubin's curves for the 48/24 neighbor tiles, and from there, you know which tiles they cover. (ie, like that shot above, with a starting facing of North, going to the tile that is +2, +2 from the starting position will go through the tiles {0,+1}, {0,+2}, {+1,+2}, and finally {+2,+2}. Note those are all offsets, and remain true wherever you do the search, so if your object is actually at the tile -3, 5, you can just apply the offsets to find the true tiles and check if they are blocked.

EDIT: To be more specific, you end up with a huge set of data, a it's 48 dubins for each direction, that each come with a list of tiles they could cover. But like I said, at least it's all precalculated. Or lazy-calculated and then re-used. If you have constantly changing Radii or Width, this isn't a good option though.

If the object is in A, and needs to get to some point in D, it can pathfind to one of it's two exits, then pathfind to the exits, etc.

This may not be optimal. The optimal path may visit both B and C several times, for example..

Funny thing going on, when the timeastar is working.
Is it working on both sides of the source (the opened list)...
If the destination is on the east side of the src, both E, S, W, N nodes are opened,
just like the greedy algorithm....
Why on earth the astar would consider the side that is opposite to the destination...
funny enough....

(Only 24-directional now)