• Advertisement
Sign in to follow this  

Cooperative Pathfinding with Turns

This topic is 755 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement

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
Edited by lucky6969b

Share this post


Link to post
Share on other sites

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.

Edited by ferrous

Share this post


Link to post
Share on other sites

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

Edited by lucky6969b

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites

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.

Edited by ferrous

Share this post


Link to post
Share on other sites

[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. 

Edited by ferrous

Share this post


Link to post
Share on other sites

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..

Share this post


Link to post
Share on other sites

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)
 

Edited by lucky6969b

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement