Skip to main content
GameDev.net gamedev.net
🔒 Locked

Cooperative Pathfinding with Turns

Started by lucky6969b Mar 1, 2016 at 11:50 AM 13 replies 4.5k views
Original Post
lucky6969b
lucky6969b

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

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

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.

lucky6969b
lucky6969b

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

ferrous
ferrous

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.

lucky6969b
lucky6969b
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?
ferrous
ferrous

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.

ferrous
ferrous

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

Alberth
Alberth



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

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)

lucky6969b
lucky6969b

I was having trouble in calculating the coordinates of 24-directional search.
Given 24-directional search, I need to set the gSearch flag to 3.
If I set it to 4, it is 32 directional search,
But opening surrounding 24 tiles should be the correct way.

for (int direction = 0; direction < totalDirections; direction++)
{
   int posDest = direction % gSearch;

   ptNew.x = ptCurrent.x + gDirOffset[posDest].x;
   ptNew.y = ptCurrent.y + gDirOffset[posDest].y
You can see that when gSearch is 3, it is searching the right half of the map always.
But it is set to 4, it is opening 32 nodes in one lot.
It is then a 32-directional search, but as to me, opening surrounding 24 nodes is the only correct way of doing it.
Why not writing this instead?

int dirDest = direction / gSearch;
ptNew.x = ptCurrent.x + gDirOffset[dirDest].x

lucky6969b
lucky6969b

I want to weigh abrupt turns with high h and g scores.

But in one of my test, when the agent goes from

28,39 to 6,118

when it reaches

6,61,3 (SOUTHWEST)

It refuses to turn SOUTH

6,62,2

Here are some the related results


1 X: 6 Z 61 Dir: 3 total_cost 4457.03 path_cost 2208.95 estimated_cost 2248.09 Current Depth: 22
2 X: 28 Z 59 Dir: 2 total_cost 4470.17 path_cost 1318.19 estimated_cost 3151.98 Current Depth: 20
3 X: 34 Z 45 Dir: 1 total_cost 4496.27 path_cost 879.919 estimated_cost 3616.35 Current Depth: 6
4 X: 27 Z 42 Dir: 3 total_cost 4907.14 path_cost 1633.11 estimated_cost 3274.03 Current Depth: 3
5 X: 27 Z 43 Dir: 3 total_cost 4950.15 path_cost 1697.11 estimated_cost 3253.04 Current Depth: 4
6 X: 27 Z 41 Dir: 3 total_cost 4968.23 path_cost 1569.11 estimated_cost 3399.11 Current Depth: 2
7 X: 29 Z 41 Dir: 1 total_cost 5091.93 path_cost 1569.11 estimated_cost 3522.82 Current Depth: 2
8 X: 26 Z 40 Dir: 4 total_cost 5095.29 path_cost 1696.75 estimated_cost 3398.55 Current Depth: 2
9 X: 27 Z 41 Dir: 2 total_cost 5095.86 path_cost 1696.75 estimated_cost 3399.11 Current Depth: 2
10 X: 26 Z 42 Dir: 2 total_cost 5095.98 path_cost 1787.26 estimated_cost 3308.73 Current Depth: 3
11 X: 27 Z 46 Dir: 3 total_cost 5098.27 path_cost 1889.11 estimated_cost 3209.16 Current Depth: 7
12 X: 29 Z 42 Dir: 1 total_cost 5100.24 path_cost 1633.11 estimated_cost 3467.13 Current Depth: 3
13 X: 27 Z 44 Dir: 3 total_cost 5116.34 path_cost 1761.11 estimated_cost 3355.23 Current Depth: 5
14 X: 29 Z 43 Dir: 1 total_cost 5130.11 path_cost 1697.11 estimated_cost 3433 Current Depth: 4
15 X: 27 Z 47 Dir: 3 total_cost 5141.29 path_cost 1953.11 estimated_cost 3188.18 Current Depth: 8
16 X: 25 Z 41 Dir: 4 total_cost 5151.67 path_cost 1787.26 estimated_cost 3364.42 Current Depth: 3
17 X: 24 Z 42 Dir: 4 total_cost 5151.79 path_cost 1877.76 estimated_cost 3274.03 Current Depth: 4
18 X: 25 Z 43 Dir: 2 total_cost 5152.36 path_cost 1877.76 estimated_cost 3274.6 Current Depth: 4
19 X: 23 Z 43 Dir: 4 total_cost 5154.65 path_cost 1968.27 estimated_cost 3186.38 Current Depth: 5
20 X: 27 Z 45 Dir: 3 total_cost 5159.36 path_cost 1825.11 estimated_cost 3334.25 Current Depth: 6
21 X: 22 Z 44 Dir: 4 total_cost 5234.06 path_cost 2058.78 estimated_cost 3175.28 Current Depth: 6
22 X: 23 Z 45 Dir: 2 total_cost 5234.63 path_cost 2058.78 estimated_cost 3175.85 Current Depth: 6
23 X: 22 Z 46 Dir: 2 total_cost 5234.76 path_cost 2149.29 estimated_cost 3085.46 Current Depth: 7
24 X: 29 Z 44 Dir: 1 total_cost 5253.19 path_cost 1761.11 estimated_cost 3492.08 Current Depth: 5
25 X: 29 Z 45 Dir: 1 total_cost 5283.06 path_cost 1825.11 estimated_cost 3457.95 Current Depth: 6
26 X: 27 Z 50 Dir: 3 total_cost 5289.41 path_cost 2145.11 estimated_cost 3144.3 Current Depth: 11
27 X: 21 Z 45 Dir: 4 total_cost 5290.44 path_cost 2149.29 estimated_cost 3141.15 Current Depth: 7
28 X: 20 Z 46 Dir: 4 total_cost 5290.57 path_cost 2239.8 estimated_cost 3050.76 Current Depth: 8
29 X: 21 Z 47 Dir: 2 total_cost 5291.14 path_cost 2239.8 estimated_cost 3051.33 Current Depth: 8
30 X: 29 Z 46 Dir: 1 total_cost 5291.37 path_cost 1889.11 estimated_cost 3402.26 Current Depth: 7
31 X: 19 Z 47 Dir: 4 total_cost 5293.43 path_cost 2330.31 estimated_cost 2963.11 Current Depth: 9
32 X: 27 Z 42 Dir: 4 total_cost 5296.07 path_cost 2022.04 estimated_cost 3274.03 Current Depth: 4
33 X: 27 Z 48 Dir: 3 total_cost 5307.48 path_cost 2017.11 estimated_cost 3290.37 Current Depth: 9
34 X: 27 Z 40 Dir: 4 total_cost 5314.14 path_cost 1894.04 estimated_cost 3420.1 Current Depth: 2
35 X: 29 Z 47 Dir: 1 total_cost 5321.24 path_cost 1953.11 estimated_cost 3368.13 Current Depth: 8
36 X: 24 Z 44 Dir: 2 total_cost 5323.51 path_cost 1968.27 estimated_cost 3355.23 Current Depth: 5
37 X: 27 Z 51 Dir: 3 total_cost 5332.42 path_cost 2209.11 estimated_cost 3123.31 Current Depth: 12
38 X: 29 Z 41 Dir: 2 total_cost 5338.69 path_cost 1815.87 estimated_cost 3522.82 Current Depth: 2
39 X: 27 Z 43 Dir: 4 total_cost 5339.08 path_cost 2086.04 estimated_cost 3253.04 Current Depth: 5
40 X: 27 Z 49 Dir: 3 total_cost 5350.49 path_cost 2081.11 estimated_cost 3269.38 Current Depth: 10
41 X: 27 Z 41 Dir: 4 total_cost 5357.15 path_cost 1958.04 estimated_cost 3399.11 Current Depth: 3
42 X: 30 Z 40 Dir: 0 total_cost 5372.82 path_cost 1815.87 estimated_cost 3556.95 Current Depth: 2
43 X: 18 Z 48 Dir: 4 total_cost 5372.84 path_cost 2420.82 estimated_cost 2952.01 Current Depth: 10
44 X: 19 Z 49 Dir: 2 total_cost 5373.41 path_cost 2420.82 estimated_cost 2952.58 Current Depth: 10
45 X: 30 Z 42 Dir: 2 total_cost 5373.51 path_cost 1906.38 estimated_cost 3467.13 Current Depth: 3
46 X: 18 Z 50 Dir: 2 total_cost 5373.53 path_cost 2511.33 estimated_cost 2862.2 Current Depth: 11
47 X: 31 Z 43 Dir: 2 total_cost 5408.33 path_cost 1996.89 estimated_cost 3411.44 Current Depth: 4
48 X: 30 Z 41 Dir: 0 total_cost 5429.2 path_cost 1906.38 estimated_cost 3522.82 Current Depth: 3
49 X: 17 Z 49 Dir: 4 total_cost 5429.22 path_cost 2511.33 estimated_cost 2917.88 Current Depth: 11
50 X: 16 Z 50 Dir: 4 total_cost 5429.34 path_cost 2601.84 estimated_cost 2827.5 Current Depth: 12
51 X: 17 Z 51 Dir: 2 total_cost 5429.91 path_cost 2601.84 estimated_cost 2828.07 Current Depth: 12
52 X: 15 Z 51 Dir: 4 total_cost 5432.2 path_cost 2692.35 estimated_cost 2739.85 Current Depth: 13
53 X: 29 Z 48 Dir: 1 total_cost 5444.32 path_cost 2017.11 estimated_cost 3427.21 Current Depth: 9
54 X: 28 Z 39 Dir: 0 total_cost 5449.53 path_cost 1973.22 estimated_cost 3476.31 Current Depth: 1
55 X: 29 Z 40 Dir: 0 total_cost 5450.98 path_cost 1894.04 estimated_cost 3556.95 Current Depth: 2
56 X: 28 Z 42 Dir: 0 total_cost 5454.47 path_cost 2022.04 estimated_cost 3432.43 Current Depth: 4
57 X: 20 Z 48 Dir: 2 total_cost 5462.28 path_cost 2330.31 estimated_cost 3131.97 Current Depth: 9
58 X: 31 Z 41 Dir: 0 total_cost 5463.9 path_cost 1906.38 estimated_cost 3557.51 Current Depth: 3
59 X: 29 Z 39 Dir: 0 total_cost 5471.08 path_cost 1973.22 estimated_cost 3497.87 Current Depth: 1
60 X: 28 Z 40 Dir: 0 total_cost 5472.54 path_cost 1894.04 estimated_cost 3578.5 Current Depth: 2
61 X: 29 Z 49 Dir: 1 total_cost 5474.19 path_cost 2081.11 estimated_cost 3393.08 Current Depth: 10
62 X: 27 Z 54 Dir: 3 total_cost 5480.54 path_cost 2401.11 estimated_cost 3079.43 Current Depth: 15
63 X: 29 Z 41 Dir: 0 total_cost 5480.85 path_cost 1958.04 estimated_cost 3522.82 Current Depth: 3
64 X: 29 Z 50 Dir: 1 total_cost 5482.51 path_cost 2145.11 estimated_cost 3337.4 Current Depth: 11
65 X: 27 Z 46 Dir: 4 total_cost 5487.2 path_cost 2278.04 estimated_cost 3209.16 Current Depth: 8
66 X: 29 Z 42 Dir: 0 total_cost 5489.17 path_cost 2022.04 estimated_cost 3467.13 Current Depth: 4
67 X: 28 Z 43 Dir: 0 total_cost 5497.48 path_cost 2086.04 estimated_cost 3411.44 Current Depth: 5
68 X: 27 Z 52 Dir: 3 total_cost 5498.61 path_cost 2273.11 estimated_cost 3225.5 Current Depth: 13
69 X: 27 Z 44 Dir: 4 total_cost 5505.27 path_cost 2150.04 estimated_cost 3355.23 Current Depth: 6
70 X: 14 Z 52 Dir: 4 total_cost 5511.61 path_cost 2782.86 estimated_cost 2728.75 Current Depth: 14
71 X: 15 Z 53 Dir: 2 total_cost 5512.18 path_cost 2782.86 estimated_cost 2729.32 Current Depth: 14
72 X: 14 Z 54 Dir: 2 total_cost 5512.3 path_cost 2873.37 estimated_cost 2638.93 Current Depth: 15
73 X: 29 Z 51 Dir: 1 total_cost 5512.38 path_cost 2209.11 estimated_cost 3303.27 Current Depth: 12
74 X: 28 Z 41 Dir: 0 total_cost 5515.55 path_cost 1958.04 estimated_cost 3557.52 Current Depth: 3
75 X: 29 Z 43 Dir: 0 total_cost 5519.04 path_cost 2086.04 estimated_cost 3433 Current Depth: 5
76 X: 27 Z 55 Dir: 3 total_cost 5523.56 path_cost 2465.11 estimated_cost 3058.45 Current Depth: 16
77 X: 27 Z 47 Dir: 4 total_cost 5530.22 path_cost 2342.04 estimated_cost 3188.18 Current Depth: 9
78 X: 27 Z 53 Dir: 3 total_cost 5541.63 path_cost 2337.11 estimated_cost 3204.52 Current Depth: 14
79 X: 27 Z 45 Dir: 4 total_cost 5548.29 path_cost 2214.04 estimated_cost 3334.25 Current Depth: 7
80 X: 31 Z 42 Dir: 0 total_cost 5554.41 path_cost 1996.89 estimated_cost 3557.51 Current Depth: 4
81 X: 27 Z 42 Dir: 1 total_cost 5554.9 path_cost 2280.87 estimated_cost 3274.03 Current Depth: 3
82 X: 13 Z 53 Dir: 4 total_cost 5567.99 path_cost 2873.37 estimated_cost 2694.62 Current Depth: 15
83 X: 12 Z 54 Dir: 4 total_cost 5568.11 path_cost 2963.88 estimated_cost 2604.23 Current Depth: 16
84 X: 13 Z 55 Dir: 2 total_cost 5568.68 path_cost 2963.88 estimated_cost 2604.8 Current Depth: 16
85 X: 11 Z 55 Dir: 4 total_cost 5570.97 path_cost 3054.39 estimated_cost 2516.58 Current Depth: 17
86 X: 32 Z 42 Dir: 0 total_cost 5587.72 path_cost 1996.89 estimated_cost 3590.83 Current Depth: 4
87 X: 16 Z 52 Dir: 2 total_cost 5601.05 path_cost 2692.35 estimated_cost 2908.7 Current Depth: 13
88 X: 27 Z 39 Dir: 4 total_cost 5608.13 path_cost 2198.48 estimated_cost 3409.64 Current Depth: 1
89 X: 26 Z 39 Dir: 5 total_cost 5621.56 path_cost 2190.36 estimated_cost 3431.2 Current Depth: 2
90 X: 29 Z 52 Dir: 1 total_cost 5635.46 path_cost 2273.11 estimated_cost 3362.35 Current Depth: 13
91 X: 29 Z 44 Dir: 0 total_cost 5642.12 path_cost 2150.04 estimated_cost 3492.08 Current Depth: 6
92 X: 28 Z 46 Dir: 0 total_cost 5645.6 path_cost 2278.04 estimated_cost 3367.56 Current Depth: 8
93 X: 26 Z 43 Dir: 1 total_cost 5645.98 path_cost 2371.38 estimated_cost 3274.6 Current Depth: 4
94 X: 10 Z 56 Dir: 4 total_cost 5650.38 path_cost 3144.9 estimated_cost 2505.48 Current Depth: 18
95 X: 11 Z 57 Dir: 2 total_cost 5650.95 path_cost 3144.9 estimated_cost 2506.05 Current Depth: 18
96 X: 10 Z 58 Dir: 2 total_cost 5651.08 path_cost 3235.41 estimated_cost 2415.67 Current Depth: 19
97 X: 32 Z 43 Dir: 0 total_cost 5657.24 path_cost 2087.4 estimated_cost 3569.84 Current Depth: 5
98 X: 28 Z 44 Dir: 0 total_cost 5663.67 path_cost 2150.04 estimated_cost 3513.64 Current Depth: 6
99 X: 29 Z 53 Dir: 1 total_cost 5665.33 path_cost 2337.11 estimated_cost 3328.22 Current Depth: 14
100 X: 23 Z 42 Dir: 5 total_cost 5669.25 path_cost 2461.89 estimated_cost 3207.36 Current Depth: 5
101 X: 29 Z 45 Dir: 0 total_cost 5671.99 path_cost 2214.04 estimated_cost 3457.95 Current Depth: 7
102 X: 29 Z 54 Dir: 1 total_cost 5673.64 path_cost 2401.11 estimated_cost 3272.53 Current Depth: 15
103 X: 27 Z 50 Dir: 4 total_cost 5678.34 path_cost 2534.04 estimated_cost 3144.3 Current Depth: 12
104 X: 33 Z 43 Dir: 0 total_cost 5678.8 path_cost 2087.4 estimated_cost 3591.4 Current Depth: 5
105 X: 25 Z 40 Dir: 5 total_cost 5679.41 path_cost 2280.87 estimated_cost 3398.55 Current Depth: 3
106 X: 29 Z 46 Dir: 0 total_cost 5680.3 path_cost 2278.04 estimated_cost 3402.26 Current Depth: 8
107 X: 28 Z 47 Dir: 0 total_cost 5688.62 path_cost 2342.04 estimated_cost 3346.58 Current Depth: 9
108 X: 27 Z 56 Dir: 3 total_cost 5689.75 path_cost 2529.11 estimated_cost 3160.64 Current Depth: 17
109 X: 23 Z 46 Dir: 1 total_cost 5693.67 path_cost 2642.91 estimated_cost 3050.76 Current Depth: 7
110 X: 27 Z 48 Dir: 4 total_cost 5696.41 path_cost 2406.04 estimated_cost 3290.37 Current Depth: 10
111 X: 27 Z 39 Dir: 5 total_cost 5696.98 path_cost 2287.33 estimated_cost 3409.64 Current Depth: 2
112 X: 29 Z 55 Dir: 1 total_cost 5703.51 path_cost 2465.11 estimated_cost 3238.4 Current Depth: 16
113 X: 28 Z 45 Dir: 0 total_cost 5706.69 path_cost 2214.04 estimated_cost 3492.65 Current Depth: 7
114 X: 9 Z 57 Dir: 4 total_cost 5706.76 path_cost 3235.41 estimated_cost 2471.35 Current Depth: 19
115 X: 8 Z 58 Dir: 4 total_cost 5706.89 path_cost 3325.92 estimated_cost 2380.97 Current Depth: 20
116 X: 9 Z 59 Dir: 2 total_cost 5707.45 path_cost 3325.92 estimated_cost 2381.54 Current Depth: 20
117 X: 7 Z 59 Dir: 4 total_cost 5709.74 path_cost 3416.43 estimated_cost 2293.31 Current Depth: 21
118 X: 29 Z 47 Dir: 0 total_cost 5710.17 path_cost 2342.04 estimated_cost 3368.13 Current Depth: 9
119 X: 27 Z 59 Dir: 3 total_cost 5714.69 path_cost 2721.11 estimated_cost 2993.58 Current Depth: 20
120 X: 27 Z 51 Dir: 4 total_cost 5721.35 path_cost 2598.04 estimated_cost 3123.31 Current Depth: 13
121 X: 27 Z 57 Dir: 3 total_cost 5732.76 path_cost 2593.11 estimated_cost 3139.65 Current Depth: 18
122 X: 27 Z 49 Dir: 4 total_cost 5739.42 path_cost 2470.04 estimated_cost 3269.38 Current Depth: 11
123 X: 12 Z 56 Dir: 2 total_cost 5739.83 path_cost 3054.39 estimated_cost 2685.44 Current Depth: 17
124 X: 28 Z 41 Dir: 1 total_cost 5747.87 path_cost 2190.36 estimated_cost 3557.52 Current Depth: 2
125 X: 27 Z 42 Dir: 5 total_cost 5753.36 path_cost 2479.33 estimated_cost 3274.03 Current Depth: 5
126 X: 32 Z 44 Dir: 2 total_cost 5759.43 path_cost 2087.4 estimated_cost 3672.03 Current Depth: 5
127 X: 22 Z 43 Dir: 5 total_cost 5760.33 path_cost 2552.4 estimated_cost 3207.93 Current Depth: 6
128 X: 24 Z 41 Dir: 5 total_cost 5770.49 path_cost 2371.38 estimated_cost 3399.11 Current Depth: 4
129 X: 27 Z 40 Dir: 5 total_cost 5771.44 path_cost 2351.33 estimated_cost 3420.1 Current Depth: 3
130 X: 28 Z 49 Dir: 0 total_cost 5772.74 path_cost 2470.04 estimated_cost 3302.7 Current Depth: 11
131 X: 22 Z 47 Dir: 1 total_cost 5784.75 path_cost 2733.42 estimated_cost 3051.33 Current Depth: 8
132 X: 29 Z 39 Dir: 7 total_cost 5785.2 path_cost 2287.33 estimated_cost 3497.87 Current Depth: 2
133 X: 6 Z 60 Dir: 4 total_cost 5789.15 path_cost 3506.94 estimated_cost 2282.22 Current Depth: 22
134 X: 7 Z 61 Dir: 2 total_cost 5789.72 path_cost 3506.94 estimated_cost 2282.79 Current Depth: 22
135 X: 33 Z 45 Dir: 2 total_cost 5794.26 path_cost 2177.91 estimated_cost 3616.35 Current Depth: 6
136 X: 25 Z 44 Dir: 1 total_cost 5795.57 path_cost 2461.89 estimated_cost 3333.68 Current Depth: 5
137 X: 27 Z 43 Dir: 5 total_cost 5796.38 path_cost 2543.33 estimated_cost 3253.04 Current Depth: 6
138 X: 27 Z 58 Dir: 3 total_cost 5796.76 path_cost 2657.11 estimated_cost 3139.65 Current Depth: 19
139 X: 30 Z 39 Dir: 7 total_cost 5807.35 path_cost 2309.48 estimated_cost 3497.87 Current Depth: 2
140 X: 19 Z 46 Dir: 5 total_cost 5808.02 path_cost 2823.93 estimated_cost 2984.1 Current Depth: 9
141 X: 27 Z 41 Dir: 5 total_cost 5814.45 path_cost 2415.33 estimated_cost 3399.11 Current Depth: 4
142 X: 21 Z 44 Dir: 5 total_cost 5818.19 path_cost 2642.91 estimated_cost 3175.28 Current Depth: 7
143 X: 29 Z 56 Dir: 1 total_cost 5826.59 path_cost 2529.11 estimated_cost 3297.48 Current Depth: 17
144 X: 34 Z 44 Dir: 0 total_cost 5828.39 path_cost 2177.91 estimated_cost 3650.48 Current Depth: 6
145 X: 33 Z 44 Dir: 0 total_cost 5828.39 path_cost 2177.91 estimated_cost 3650.48 Current Depth: 6
146 X: 19 Z 50 Dir: 1 total_cost 5832.44 path_cost 3004.95 estimated_cost 2827.5 Current Depth: 11
147 X: 29 Z 48 Dir: 0 total_cost 5833.25 path_cost 2406.04 estimated_cost 3427.21 Current Depth: 10
148 X: 28 Z 50 Dir: 0 total_cost 5836.74 path_cost 2534.04 estimated_cost 3302.7 Current Depth: 12
149 X: 28 Z 48 Dir: 0 total_cost 5854.81 path_cost 2406.04 estimated_cost 3448.77 Current Depth: 10
150 X: 29 Z 57 Dir: 1 total_cost 5856.46 path_cost 2593.11 estimated_cost 3263.35 Current Depth: 18
151 X: 29 Z 49 Dir: 0 total_cost 5863.12 path_cost 2470.04 estimated_cost 3393.08 Current Depth: 11
152 X: 29 Z 58 Dir: 1 total_cost 5864.78 path_cost 2657.11 estimated_cost 3207.67 Current Depth: 19
153 X: 28 Z 41 Dir: 3 total_cost 5867 path_cost 2309.48 estimated_cost 3557.52 Current Depth: 2
154 X: 29 Z 42 Dir: 3 total_cost 5867.12 path_cost 2399.99 estimated_cost 3467.13 Current Depth: 3
155 X: 27 Z 54 Dir: 4 total_cost 5869.47 path_cost 2790.04 estimated_cost 3079.43 Current Depth: 16
156 X: 29 Z 50 Dir: 0 total_cost 5871.44 path_cost 2534.04 estimated_cost 3337.4 Current Depth: 12
157 X: 8 Z 60 Dir: 2 total_cost 5878.6 path_cost 3416.43 estimated_cost 2462.17 Current Depth: 21
158 X: 28 Z 51 Dir: 0 total_cost 5879.75 path_cost 2598.04 estimated_cost 3281.71 Current Depth: 13
159 X: 24 Z 45 Dir: 1 total_cost 5886.65 path_cost 2552.4 estimated_cost 3334.25 Current Depth: 6
160 X: 27 Z 52 Dir: 4 total_cost 5887.54 path_cost 2662.04 estimated_cost 3225.5 Current Depth: 14
161 X: 29 Z 59 Dir: 1 total_cost 5894.65 path_cost 2721.11 estimated_cost 3173.54 Current Depth: 20
162 X: 18 Z 47 Dir: 5 total_cost 5899.1 path_cost 2914.44 estimated_cost 2984.67 Current Depth: 10
163 X: 29 Z 51 Dir: 0 total_cost 5901.31 path_cost 2598.04 estimated_cost 3303.27 Current Depth: 13
164 X: 29 Z 40 Dir: 7 total_cost 5908.28 path_cost 2351.33 estimated_cost 3556.95 Current Depth: 3
165 X: 20 Z 45 Dir: 5 total_cost 5909.27 path_cost 2733.42 estimated_cost 3175.85 Current Depth: 8
166 X: 27 Z 55 Dir: 4 total_cost 5912.48 path_cost 2854.04 estimated_cost 3058.45 Current Depth: 17
167 X: 30 Z 43 Dir: 3 total_cost 5923.5 path_cost 2490.5 estimated_cost 3433 Current Depth: 4
168 X: 18 Z 51 Dir: 1 total_cost 5923.52 path_cost 3095.46 estimated_cost 2828.07 Current Depth: 12
169 X: 27 Z 53 Dir: 4 total_cost 5930.56 path_cost 2726.04 estimated_cost 3204.52 Current Depth: 15
170 X: 29 Z 38 Dir: 7 total_cost 5932.94 path_cost 2400.94 estimated_cost 3532 Current Depth: 1
171 X: 21 Z 48 Dir: 1 total_cost 5934.34 path_cost 2823.93 estimated_cost 3110.41 Current Depth: 9
172 X: 29 Z 41 Dir: 7 total_cost 5938.15 path_cost 2415.33 estimated_cost 3522.82 Current Depth: 4
173 X: 27 Z 46 Dir: 5 total_cost 5944.5 path_cost 2735.33 estimated_cost 3209.16 Current Depth: 9
174 X: 29 Z 42 Dir: 7 total_cost 5946.46 path_cost 2479.33 estimated_cost 3467.13 Current Depth: 5
175 X: 15 Z 50 Dir: 5 total_cost 5946.8 path_cost 3185.96 estimated_cost 2760.83 Current Depth: 13
176 X: 17 Z 48 Dir: 5 total_cost 5956.96 path_cost 3004.95 estimated_cost 2952.01 Current Depth: 11
177 X: 27 Z 44 Dir: 5 total_cost 5962.57 path_cost 2607.33 estimated_cost 3355.23 Current Depth: 7
178 X: 28 Z 53 Dir: 0 total_cost 5963.87 path_cost 2726.04 estimated_cost 3237.83 Current Depth: 15
179 X: 15 Z 54 Dir: 1 total_cost 5971.22 path_cost 3366.98 estimated_cost 2604.23 Current Depth: 15
180 X: 29 Z 43 Dir: 7 total_cost 5976.33 path_cost 2543.33 estimated_cost 3433 Current Depth: 6
181 X: 31 Z 40 Dir: 7 total_cost 5978.5 path_cost 2399.99 estimated_cost 3578.5 Current Depth: 3
182 X: 27 Z 47 Dir: 5 total_cost 5987.51 path_cost 2799.33 estimated_cost 3188.18 Current Depth: 10
183 X: 27 Z 45 Dir: 5 total_cost 6005.58 path_cost 2671.33 estimated_cost 3334.25 Current Depth: 8
184 X: 29 Z 52 Dir: 0 total_cost 6024.39 path_cost 2662.04 estimated_cost 3362.35 Current Depth: 14
185 X: 20 Z 49 Dir: 1 total_cost 6025.42 path_cost 2914.44 estimated_cost 3110.98 Current Depth: 10
186 X: 28 Z 54 Dir: 0 total_cost 6027.87 path_cost 2790.04 estimated_cost 3237.83 Current Depth: 16
187 X: 14 Z 51 Dir: 5 total_cost 6037.88 path_cost 3276.47 estimated_cost 2761.4 Current Depth: 14
188 X: 28 Z 52 Dir: 0 total_cost 6045.94 path_cost 2662.04 estimated_cost 3383.9 Current Depth: 14
189 X: 16 Z 49 Dir: 5 total_cost 6048.04 path_cost 3095.46 estimated_cost 2952.58 Current Depth: 12
190 X: 29 Z 53 Dir: 0 total_cost 6054.26 path_cost 2726.04 estimated_cost 3328.22 Current Depth: 15
191 X: 14 Z 55 Dir: 1 total_cost 6062.29 path_cost 3457.49 estimated_cost 2604.8 Current Depth: 16
192 X: 29 Z 54 Dir: 0 total_cost 6062.57 path_cost 2790.04 estimated_cost 3272.53 Current Depth: 16
193 X: 28 Z 55 Dir: 0 total_cost 6070.88 path_cost 2854.04 estimated_cost 3216.85 Current Depth: 17
194 X: 17 Z 52 Dir: 1 total_cost 6073.11 path_cost 3185.96 estimated_cost 2887.15 Current Depth: 13
195 X: 27 Z 56 Dir: 4 total_cost 6078.68 path_cost 2918.04 estimated_cost 3160.64 Current Depth: 18
196 X: 11 Z 54 Dir: 5 total_cost 6085.57 path_cost 3548 estimated_cost 2537.57 Current Depth: 17
197 X: 29 Z 55 Dir: 0 total_cost 6092.44 path_cost 2854.04 estimated_cost 3238.4 Current Depth: 17
198 X: 31 Z 44 Dir: 3 total_cost 6094.65 path_cost 2581.01 estimated_cost 3513.64 Current Depth: 5
199 X: 13 Z 52 Dir: 5 total_cost 6095.73 path_cost 3366.98 estimated_cost 2728.75 Current Depth: 15
200 X: 29 Z 44 Dir: 7 total_cost 6099.41 path_cost 2607.33 estimated_cost 3492.08 Current Depth: 7
201 X: 11 Z 58 Dir: 1 total_cost 6109.99 path_cost 3729.02 estimated_cost 2380.97 Current Depth: 19
202 X: 27 Z 57 Dir: 4 total_cost 6121.69 path_cost 2982.04 estimated_cost 3139.65 Current Depth: 19
203 X: 29 Z 45 Dir: 7 total_cost 6129.28 path_cost 2671.33 estimated_cost 3457.95 Current Depth: 8
204 X: 27 Z 50 Dir: 5 total_cost 6135.63 path_cost 2991.33 estimated_cost 3144.3 Current Depth: 13
205 X: 29 Z 46 Dir: 7 total_cost 6137.6 path_cost 2735.33 estimated_cost 3402.26 Current Depth: 9
206 X: 27 Z 48 Dir: 5 total_cost 6153.7 path_cost 2863.33 estimated_cost 3290.37 Current Depth: 11
207 X: 28 Z 57 Dir: 0 total_cost 6155 path_cost 2982.04 estimated_cost 3172.97 Current Depth: 19
208 X: 16 Z 53 Dir: 1 total_cost 6164.19 path_cost 3276.47 estimated_cost 2887.72 Current Depth: 14
209 X: 29 Z 47 Dir: 7 total_cost 6167.47 path_cost 2799.33 estimated_cost 3368.13 Current Depth: 10
210 X: 10 Z 55 Dir: 5 total_cost 6176.65 path_cost 3638.51 estimated_cost 2538.14 Current Depth: 18
211 X: 27 Z 51 Dir: 5 total_cost 6178.65 path_cost 3055.33 estimated_cost 3123.31 Current Depth: 14
212 X: 27 Z 58 Dir: 4 total_cost 6185.69 path_cost 3046.04 estimated_cost 3139.65 Current Depth: 20
213 X: 12 Z 53 Dir: 5 total_cost 6186.81 path_cost 3457.49 estimated_cost 2729.32 Current Depth: 16
214 X: 27 Z 49 Dir: 5 total_cost 6196.72 path_cost 2927.33 estimated_cost 3269.38 Current Depth: 12
215 X: 32 Z 45 Dir: 3 total_cost 6197.49 path_cost 2671.52 estimated_cost 3525.96 Current Depth: 6
216 X: 10 Z 59 Dir: 1 total_cost 6201.07 path_cost 3819.53 estimated_cost 2381.54 Current Depth: 20
217 X: 33 Z 42 Dir: 7 total_cost 6206.54 path_cost 2581.01 estimated_cost 3625.53 Current Depth: 5
218 X: 13 Z 56 Dir: 1 total_cost 6211.89 path_cost 3548 estimated_cost 2663.88 Current Depth: 17
219 X: 29 Z 56 Dir: 0 total_cost 6215.52 path_cost 2918.04 estimated_cost 3297.48 Current Depth: 18
220 X: 28 Z 58 Dir: 0 total_cost 6219 path_cost 3046.04 estimated_cost 3172.97 Current Depth: 20
221 X: 7 Z 58 Dir: 5 total_cost 6224.34 path_cost 3910.04 estimated_cost 2314.3 Current Depth: 21
222 X: 9 Z 56 Dir: 5 total_cost 6234.5 path_cost 3729.02 estimated_cost 2505.48 Current Depth: 19
223 X: 28 Z 56 Dir: 0 total_cost 6237.08 path_cost 2918.04 estimated_cost 3319.04 Current Depth: 18
224 X: 29 Z 57 Dir: 0 total_cost 6245.39 path_cost 2982.04 estimated_cost 3263.35 Current Depth: 19
225 X: 29 Z 58 Dir: 0 total_cost 6253.7 path_cost 3046.04 estimated_cost 3207.67 Current Depth: 20
226 X: 34 Z 43 Dir: 7 total_cost 6262.92 path_cost 2671.52 estimated_cost 3591.4 Current Depth: 6
227 X: 29 Z 48 Dir: 7 total_cost 6290.55 path_cost 2863.33 estimated_cost 3427.21 Current Depth: 11
228 X: 12 Z 57 Dir: 1 total_cost 6302.96 path_cost 3638.51 estimated_cost 2664.45 Current Depth: 18
229 X: 6 Z 59 Dir: 5 total_cost 6315.42 path_cost 4000.55 estimated_cost 2314.87 Current Depth: 22
230 X: 29 Z 49 Dir: 7 total_cost 6320.42 path_cost 2927.33 estimated_cost 3393.08 Current Depth: 12
231 X: 8 Z 57 Dir: 5 total_cost 6325.58 path_cost 3819.53 estimated_cost 2506.05 Current Depth: 20
232 X: 27 Z 54 Dir: 5 total_cost 6326.77 path_cost 3247.33 estimated_cost 3079.43 Current Depth: 17
233 X: 29 Z 50 Dir: 7 total_cost 6328.73 path_cost 2991.33 estimated_cost 3337.4 Current Depth: 13
234 X: 27 Z 52 Dir: 5 total_cost 6344.84 path_cost 3119.33 estimated_cost 3225.5 Current Depth: 15
235 X: 9 Z 60 Dir: 1 total_cost 6350.66 path_cost 3910.04 estimated_cost 2440.62 Current Depth: 21
236 X: 29 Z 51 Dir: 7 total_cost 6358.6 path_cost 3055.33 estimated_cost 3303.27 Current Depth: 14
237 X: 27 Z 55 Dir: 5 total_cost 6369.78 path_cost 3311.33 estimated_cost 3058.45 Current Depth: 18
238 X: 27 Z 53 Dir: 5 total_cost 6387.85 path_cost 3183.33 estimated_cost 3204.52 Current Depth: 16
239 X: 8 Z 61 Dir: 1 total_cost 6441.74 path_cost 4000.55 estimated_cost 2441.19 Current Depth: 22
240 X: 29 Z 52 Dir: 7 total_cost 6481.68 path_cost 3119.33 estimated_cost 3362.35 Current Depth: 15
241 X: 29 Z 53 Dir: 7 total_cost 6511.55 path_cost 3183.33 estimated_cost 3328.22 Current Depth: 16
242 X: 29 Z 54 Dir: 7 total_cost 6519.87 path_cost 3247.33 estimated_cost 3272.53 Current Depth: 17
243 X: 27 Z 56 Dir: 5 total_cost 6535.97 path_cost 3375.33 estimated_cost 3160.64 Current Depth: 19
244 X: 29 Z 55 Dir: 7 total_cost 6549.74 path_cost 3311.33 estimated_cost 3238.4 Current Depth: 18
245 X: 27 Z 57 Dir: 5 total_cost 6578.99 path_cost 3439.33 estimated_cost 3139.65 Current Depth: 20
246 X: 29 Z 56 Dir: 7 total_cost 6672.82 path_cost 3375.33 estimated_cost 3297.48 Current Depth: 19
247 X: 29 Z 57 Dir: 7 total_cost 6702.69 path_cost 3439.33 estimated_cost 3263.35 Current Depth: 20
248 X: 27 Z 38 Dir: 5 total_cost 6750.05 path_cost 3319.42 estimated_cost 3430.63 Current Depth: 1
249 X: 27 Z 39 Dir: 6 total_cost 7036.75 path_cost 3627.1 estimated_cost 3409.64 Current Depth: 2
250 X: 27 Z 40 Dir: 0 total_cost 7047.2 path_cost 3627.1 estimated_cost 3420.1 Current Depth: 2
251 X: 26 Z 41 Dir: 0 total_cost 7082.03 path_cost 3717.61 estimated_cost 3364.42 Current Depth: 3
252 X: 26 Z 40 Dir: 6 total_cost 7116.16 path_cost 3717.61 estimated_cost 3398.55 Current Depth: 3
253 X: 27 Z 41 Dir: 0 total_cost 7116.73 path_cost 3717.61 estimated_cost 3399.11 Current Depth: 3
254 X: 26 Z 42 Dir: 0 total_cost 7116.85 path_cost 3808.12 estimated_cost 3308.73 Current Depth: 4
255 X: 25 Z 42 Dir: 0 total_cost 7116.85 path_cost 3808.12 estimated_cost 3308.73 Current Depth: 4
256 X: 24 Z 43 Dir: 0 total_cost 7151.68 path_cost 3898.63 estimated_cost 3253.04 Current Depth: 5
257 X: 25 Z 41 Dir: 6 total_cost 7172.54 path_cost 3808.12 estimated_cost 3364.42 Current Depth: 4
258 X: 24 Z 42 Dir: 6 total_cost 7172.66 path_cost 3898.63 estimated_cost 3274.03 Current Depth: 5
259 X: 25 Z 43 Dir: 0 total_cost 7173.23 path_cost 3898.63 estimated_cost 3274.6 Current Depth: 5
260 X: 23 Z 43 Dir: 6 total_cost 7175.52 path_cost 3989.14 estimated_cost 3186.38 Current Depth: 6
261 X: 23 Z 44 Dir: 0 total_cost 7185.98 path_cost 3989.14 estimated_cost 3196.83 Current Depth: 6
262 X: 22 Z 45 Dir: 0 total_cost 7220.8 path_cost 4079.65 estimated_cost 3141.15 Current Depth: 7
263 X: 29 Z 39 Dir: 6 total_cost 7244.09 path_cost 3746.23 estimated_cost 3497.87 Current Depth: 2
264 X: 22 Z 44 Dir: 6 total_cost 7254.93 path_cost 4079.65 estimated_cost 3175.28 Current Depth: 7
265 X: 23 Z 45 Dir: 0 total_cost 7255.5 path_cost 4079.65 estimated_cost 3175.85 Current Depth: 7
266 X: 22 Z 46 Dir: 0 total_cost 7255.63 path_cost 4170.16 estimated_cost 3085.46 Current Depth: 8
267 X: 21 Z 46 Dir: 0 total_cost 7255.63 path_cost 4170.16 estimated_cost 3085.46 Current Depth: 8
268 X: 20 Z 47 Dir: 0 total_cost 7290.45 path_cost 4260.67 estimated_cost 3029.78 Current Depth: 9
269 X: 21 Z 45 Dir: 6 total_cost 7311.31 path_cost 4170.16 estimated_cost 3141.15 Current Depth: 8
270 X: 20 Z 46 Dir: 6 total_cost 7311.43 path_cost 4260.67 estimated_cost 3050.76 Current Depth: 9
271 X: 21 Z 47 Dir: 0 total_cost 7312 path_cost 4260.67 estimated_cost 3051.33 Current Depth: 9
272 X: 19 Z 47 Dir: 6 total_cost 7314.29 path_cost 4351.18 estimated_cost 2963.11 Current Depth: 10
273 X: 28 Z 40 Dir: 4 total_cost 7324.73 path_cost 3746.23 estimated_cost 3578.5 Current Depth: 2
274 X: 19 Z 48 Dir: 0 total_cost 7324.75 path_cost 4351.18 estimated_cost 2973.57 Current Depth: 10
275 X: 24 Z 44 Dir: 0 total_cost 7344.38 path_cost 3989.14 estimated_cost 3355.23 Current Depth: 6
276 X: 29 Z 41 Dir: 4 total_cost 7359.55 path_cost 3836.74 estimated_cost 3522.82 Current Depth: 3
277 X: 18 Z 49 Dir: 0 total_cost 7359.57 path_cost 4441.69 estimated_cost 2917.88 Current Depth: 11
278 X: 30 Z 40 Dir: 6 total_cost 7393.68 path_cost 3836.74 estimated_cost 3556.95 Current Depth: 3
279 X: 18 Z 48 Dir: 6 total_cost 7393.7 path_cost 4441.69 estimated_cost 2952.01 Current Depth: 11
280 X: 19 Z 49 Dir: 0 total_cost 7394.27 path_cost 4441.69 estimated_cost 2952.58 Current Depth: 11
281 X: 30 Z 42 Dir: 4 total_cost 7394.38 path_cost 3927.25 estimated_cost 3467.13 Current Depth: 4
282 X: 18 Z 50 Dir: 0 total_cost 7394.4 path_cost 4532.2 estimated_cost 2862.2 Current Depth: 12
283 X: 17 Z 50 Dir: 0 total_cost 7394.4 path_cost 4532.2 estimated_cost 2862.2 Current Depth: 12
284 X: 31 Z 43 Dir: 4 total_cost 7429.2 path_cost 4017.76 estimated_cost 3411.44 Current Depth: 5
285 X: 16 Z 51 Dir: 0 total_cost 7429.22 path_cost 4622.71 estimated_cost 2806.51 Current Depth: 13
286 X: 17 Z 49 Dir: 6 total_cost 7450.08 path_cost 4532.2 estimated_cost 2917.88 Current Depth: 12
287 X: 16 Z 50 Dir: 6 total_cost 7450.21 path_cost 4622.71 estimated_cost 2827.5 Current Depth: 13
288 X: 17 Z 51 Dir: 0 total_cost 7450.78 path_cost 4622.71 estimated_cost 2828.07 Current Depth: 13
289 X: 15 Z 51 Dir: 6 total_cost 7453.06 path_cost 4713.22 estimated_cost 2739.85 Current Depth: 14
290 X: 15 Z 52 Dir: 0 total_cost 7463.52 path_cost 4713.22 estimated_cost 2750.3 Current Depth: 14
291 X: 20 Z 48 Dir: 0 total_cost 7483.15 path_cost 4351.18 estimated_cost 3131.97 Current Depth: 10
292 X: 31 Z 41 Dir: 6 total_cost 7484.76 path_cost 3927.25 estimated_cost 3557.51 Current Depth: 4
293 X: 14 Z 53 Dir: 0 total_cost 7498.35 path_cost 4803.73 estimated_cost 2694.62 Current Depth: 15
294 X: 14 Z 52 Dir: 6 total_cost 7532.48 path_cost 4803.73 estimated_cost 2728.75 Current Depth: 15
295 X: 15 Z 53 Dir: 0 total_cost 7533.05 path_cost 4803.73 estimated_cost 2729.32 Current Depth: 15
296 X: 14 Z 54 Dir: 0 total_cost 7533.17 path_cost 4894.24 estimated_cost 2638.93 Current Depth: 16
297 X: 13 Z 54 Dir: 0 total_cost 7533.17 path_cost 4894.24 estimated_cost 2638.93 Current Depth: 16
298 X: 12 Z 55 Dir: 0 total_cost 7567.99 path_cost 4984.75 estimated_cost 2583.25 Current Depth: 17
299 X: 13 Z 53 Dir: 6 total_cost 7588.86 path_cost 4894.24 estimated_cost 2694.62 Current Depth: 16
300 X: 12 Z 54 Dir: 6 total_cost 7588.98 path_cost 4984.75 estimated_cost 2604.23 Current Depth: 17
301 X: 13 Z 55 Dir: 0 total_cost 7589.55 path_cost 4984.75 estimated_cost 2604.8 Current Depth: 17
302 X: 11 Z 55 Dir: 6 total_cost 7591.84 path_cost 5075.26 estimated_cost 2516.58 Current Depth: 18
303 X: 11 Z 56 Dir: 0 total_cost 7602.29 path_cost 5075.26 estimated_cost 2527.04 Current Depth: 18
304 X: 32 Z 42 Dir: 6 total_cost 7608.59 path_cost 4017.76 estimated_cost 3590.83 Current Depth: 5
305 X: 16 Z 52 Dir: 0 total_cost 7621.92 path_cost 4713.22 estimated_cost 2908.7 Current Depth: 14
306 X: 10 Z 57 Dir: 0 total_cost 7637.12 path_cost 5165.77 estimated_cost 2471.35 Current Depth: 19
307 X: 10 Z 56 Dir: 6 total_cost 7671.25 path_cost 5165.77 estimated_cost 2505.48 Current Depth: 19
308 X: 11 Z 57 Dir: 0 total_cost 7671.82 path_cost 5165.77 estimated_cost 2506.05 Current Depth: 19
309 X: 10 Z 58 Dir: 0 total_cost 7671.94 path_cost 5256.28 estimated_cost 2415.67 Current Depth: 20
310 X: 9 Z 58 Dir: 0 total_cost 7671.94 path_cost 5256.28 estimated_cost 2415.67 Current Depth: 20
311 X: 33 Z 43 Dir: 6 total_cost 7699.67 path_cost 4108.27 estimated_cost 3591.4 Current Depth: 6
312 X: 8 Z 59 Dir: 0 total_cost 7706.77 path_cost 5346.79 estimated_cost 2359.98 Current Depth: 21
313 X: 28 Z 38 Dir: 6 total_cost 7715.63 path_cost 4218.34 estimated_cost 3497.3 Current Depth: 1
314 X: 9 Z 57 Dir: 6 total_cost 7727.63 path_cost 5256.28 estimated_cost 2471.35 Current Depth: 20
315 X: 8 Z 58 Dir: 6 total_cost 7727.75 path_cost 5346.79 estimated_cost 2380.97 Current Depth: 21
316 X: 9 Z 59 Dir: 0 total_cost 7728.32 path_cost 5346.79 estimated_cost 2381.54 Current Depth: 21
317 X: 7 Z 59 Dir: 6 total_cost 7730.61 path_cost 5437.3 estimated_cost 2293.31 Current Depth: 22
318 X: 7 Z 60 Dir: 0 total_cost 7741.07 path_cost 5437.3 estimated_cost 2303.77 Current Depth: 22
319 X: 12 Z 56 Dir: 0 total_cost 7760.69 path_cost 5075.26 estimated_cost 2685.44 Current Depth: 18
320 X: 32 Z 44 Dir: 4 total_cost 7780.3 path_cost 4108.27 estimated_cost 3672.03 Current Depth: 6
321 X: 8 Z 60 Dir: 0 total_cost 7899.47 path_cost 5437.3 estimated_cost 2462.17 Current Depth: 22
322 X: 28 Z 39 Dir: 6 total_cost 8056.27 path_cost 4579.96 estimated_cost 3476.31 Current Depth: 2
323 X: 28 Z 42 Dir: 6 total_cost 8204.39 path_cost 4771.96 estimated_cost 3432.43 Current Depth: 5
324 X: 28 Z 40 Dir: 6 total_cost 8222.46 path_cost 4643.96 estimated_cost 3578.5 Current Depth: 3
325 X: 28 Z 43 Dir: 6 total_cost 8247.4 path_cost 4835.96 estimated_cost 3411.44 Current Depth: 6
326 X: 28 Z 41 Dir: 6 total_cost 8265.47 path_cost 4707.96 estimated_cost 3557.52 Current Depth: 4
327 X: 28 Z 39 Dir: 7 total_cost 8344.27 path_cost 4867.96 estimated_cost 3476.31 Current Depth: 2
328 X: 27 Z 40 Dir: 7 total_cost 8378.57 path_cost 4958.47 estimated_cost 3420.1 Current Depth: 3
329 X: 28 Z 46 Dir: 6 total_cost 8395.52 path_cost 5027.96 estimated_cost 3367.56 Current Depth: 9
330 X: 26 Z 41 Dir: 7 total_cost 8413.4 path_cost 5048.98 estimated_cost 3364.42 Current Depth: 4
331 X: 28 Z 44 Dir: 6 total_cost 8413.59 path_cost 4899.96 estimated_cost 3513.64 Current Depth: 7
332 X: 28 Z 47 Dir: 6 total_cost 8438.54 path_cost 5091.96 estimated_cost 3346.58 Current Depth: 10
333 X: 25 Z 42 Dir: 7 total_cost 8448.22 path_cost 5139.49 estimated_cost 3308.73 Current Depth: 5
334 X: 28 Z 45 Dir: 6 total_cost 8456.61 path_cost 4963.96 estimated_cost 3492.65 Current Depth: 8
335 X: 28 Z 39 Dir: 5 total_cost 8463.4 path_cost 4987.09 estimated_cost 3476.31 Current Depth: 2
336 X: 24 Z 43 Dir: 7 total_cost 8483.05 path_cost 5230 estimated_cost 3253.04 Current Depth: 6
337 X: 23 Z 44 Dir: 7 total_cost 8517.35 path_cost 5320.51 estimated_cost 3196.83 Current Depth: 7
338 X: 28 Z 49 Dir: 6 total_cost 8522.66 path_cost 5219.96 estimated_cost 3302.7 Current Depth: 12
339 X: 22 Z 45 Dir: 7 total_cost 8552.17 path_cost 5411.02 estimated_cost 3141.15 Current Depth: 8
340 X: 28 Z 50 Dir: 6 total_cost 8586.66 path_cost 5283.96 estimated_cost 3302.7 Current Depth: 13
341 X: 21 Z 46 Dir: 7 total_cost 8587 path_cost 5501.53 estimated_cost 3085.46 Current Depth: 9
342 X: 28 Z 48 Dir: 6 total_cost 8604.73 path_cost 5155.96 estimated_cost 3448.77 Current Depth: 11
343 X: 20 Z 47 Dir: 7 total_cost 8621.82 path_cost 5592.04 estimated_cost 3029.78 Current Depth: 10
344 X: 28 Z 51 Dir: 6 total_cost 8629.67 path_cost 5347.96 estimated_cost 3281.71 Current Depth: 14
345 X: 29 Z 40 Dir: 5 total_cost 8634.54 path_cost 5077.6 estimated_cost 3556.95 Current Depth: 3
346 X: 19 Z 48 Dir: 7 total_cost 8656.12 path_cost 5682.55 estimated_cost 2973.57 Current Depth: 11
347 X: 30 Z 41 Dir: 5 total_cost 8690.92 path_cost 5168.11 estimated_cost 3522.82 Current Depth: 4
348 X: 18 Z 49 Dir: 7 total_cost 8690.94 path_cost 5773.06 estimated_cost 2917.88 Current Depth: 12
349 X: 28 Z 53 Dir: 6 total_cost 8713.79 path_cost 5475.96 estimated_cost 3237.83 Current Depth: 16
350 X: 17 Z 50 Dir: 7 total_cost 8725.77 path_cost 5863.57 estimated_cost 2862.2 Current Depth: 13
351 X: 16 Z 51 Dir: 7 total_cost 8760.59 path_cost 5954.08 estimated_cost 2806.51 Current Depth: 14
352 X: 28 Z 54 Dir: 6 total_cost 8777.79 path_cost 5539.96 estimated_cost 3237.83 Current Depth: 17
353 X: 15 Z 52 Dir: 7 total_cost 8794.89 path_cost 6044.59 estimated_cost 2750.3 Current Depth: 15
354 X: 28 Z 52 Dir: 6 total_cost 8795.86 path_cost 5411.96 estimated_cost 3383.9 Current Depth: 15
355 X: 31 Z 42 Dir: 5 total_cost 8816.13 path_cost 5258.62 estimated_cost 3557.51 Current Depth: 5
356 X: 28 Z 55 Dir: 6 total_cost 8820.81 path_cost 5603.96 estimated_cost 3216.85 Current Depth: 18
357 X: 14 Z 53 Dir: 7 total_cost 8829.72 path_cost 6135.1 estimated_cost 2694.62 Current Depth: 16
358 X: 13 Z 54 Dir: 7 total_cost 8864.54 path_cost 6225.61 estimated_cost 2638.93 Current Depth: 17
359 X: 12 Z 55 Dir: 7 total_cost 8899.36 path_cost 6316.12 estimated_cost 2583.25 Current Depth: 18
360 X: 28 Z 57 Dir: 6 total_cost 8904.93 path_cost 5731.96 estimated_cost 3172.97 Current Depth: 20
361 X: 32 Z 43 Dir: 5 total_cost 8918.97 path_cost 5349.13 estimated_cost 3569.84 Current Depth: 6
362 X: 11 Z 56 Dir: 7 total_cost 8933.67 path_cost 6406.63 estimated_cost 2527.04 Current Depth: 19
363 X: 10 Z 57 Dir: 7 total_cost 8968.49 path_cost 6497.14 estimated_cost 2471.35 Current Depth: 20
364 X: 28 Z 56 Dir: 6 total_cost 8987 path_cost 5667.96 estimated_cost 3319.04 Current Depth: 19
365 X: 9 Z 58 Dir: 7 total_cost 9003.31 path_cost 6587.65 estimated_cost 2415.67 Current Depth: 21
366 X: 8 Z 59 Dir: 7 total_cost 9038.14 path_cost 6678.16 estimated_cost 2359.98 Current Depth: 22
---------------
1 X: 28 Z 59 Dir: 2 total_cost 4470.17 path_cost 1318.19 estimated_cost 3151.98 Current Depth: 20
2 X: 5 Z 62 Dir: 3 total_cost 4491.86 path_cost 2299.46 estimated_cost 2192.4 Current Depth: 23
3 X: 34 Z 45 Dir: 1 total_cost 4496.27 path_cost 879.919 estimated_cost 3616.35 Current Depth: 6
4 X: 27 Z 42 Dir: 3 total_cost 4907.14 path_cost 1633.11 estimated_cost 3274.03 Current Depth: 3
5 X: 27 Z 43 Dir: 3 total_cost 4950.15 path_cost 1697.11 estimated_cost 3253.04 Current Depth: 4
6 X: 27 Z 41 Dir: 3 total_cost 4968.23 path_cost 1569.11 estimated_cost 3399.11 Current Depth: 2
7 X: 29 Z 41 Dir: 1 total_cost 5091.93 path_cost 1569.11 estimated_cost 3522.82 Current Depth: 2
8 X: 26 Z 40 Dir: 4 total_cost 5095.29 path_cost 1696.75 estimated_cost 3398.55 Current Depth: 2
9 X: 27 Z 41 Dir: 2 total_cost 5095.86 path_cost 1696.75 estimated_cost 3399.11 Current Depth: 2
10 X: 26 Z 42 Dir: 2 total_cost 5095.98 path_cost 1787.26 estimated_cost 3308.73 Current Depth: 3
11 X: 27 Z 46 Dir: 3 total_cost 5098.27 path_cost 1889.11 estimated_cost 3209.16 Current Depth: 7
12 X: 29 Z 42 Dir: 1 total_cost 5100.24 path_cost 1633.11 estimated_cost 3467.13 Current Depth: 3
13 X: 27 Z 44 Dir: 3 total_cost 5116.34 path_cost 1761.11 estimated_cost 3355.23 Current Depth: 5
14 X: 29 Z 43 Dir: 1 total_cost 5130.11 path_cost 1697.11 estimated_cost 3433 Current Depth: 4
15 X: 27 Z 47 Dir: 3 total_cost 5141.29 path_cost 1953.11 estimated_cost 3188.18 Current Depth: 8
16 X: 25 Z 41 Dir: 4 total_cost 5151.67 path_cost 1787.26 estimated_cost 3364.42 Current Depth: 3
17 X: 24 Z 42 Dir: 4 total_cost 5151.79 path_cost 1877.76 estimated_cost 3274.03 Current Depth: 4
18 X: 25 Z 43 Dir: 2 total_cost 5152.36 path_cost 1877.76 estimated_cost 3274.6 Current Depth: 4
19 X: 23 Z 43 Dir: 4 total_cost 5154.65 path_cost 1968.27 estimated_cost 3186.38 Current Depth: 5
20 X: 27 Z 45 Dir: 3 total_cost 5159.36 path_cost 1825.11 estimated_cost 3334.25 Current Depth: 6
21 X: 22 Z 44 Dir: 4 total_cost 5234.06 path_cost 2058.78 estimated_cost 3175.28 Current Depth: 6
22 X: 23 Z 45 Dir: 2 total_cost 5234.63 path_cost 2058.78 estimated_cost 3175.85 Current Depth: 6
23 X: 22 Z 46 Dir: 2 total_cost 5234.76 path_cost 2149.29 estimated_cost 3085.46 Current Depth: 7
24 X: 29 Z 44 Dir: 1 total_cost 5253.19 path_cost 1761.11 estimated_cost 3492.08 Current Depth: 5
25 X: 29 Z 45 Dir: 1 total_cost 5283.06 path_cost 1825.11 estimated_cost 3457.95 Current Depth: 6
26 X: 27 Z 50 Dir: 3 total_cost 5289.41 path_cost 2145.11 estimated_cost 3144.3 Current Depth: 11
27 X: 21 Z 45 Dir: 4 total_cost 5290.44 path_cost 2149.29 estimated_cost 3141.15 Current Depth: 7
28 X: 20 Z 46 Dir: 4 total_cost 5290.57 path_cost 2239.8 estimated_cost 3050.76 Current Depth: 8
29 X: 21 Z 47 Dir: 2 total_cost 5291.14 path_cost 2239.8 estimated_cost 3051.33 Current Depth: 8
30 X: 29 Z 46 Dir: 1 total_cost 5291.37 path_cost 1889.11 estimated_cost 3402.26 Current Depth: 7
31 X: 19 Z 47 Dir: 4 total_cost 5293.43 path_cost 2330.31 estimated_cost 2963.11 Current Depth: 9
32 X: 27 Z 42 Dir: 4 total_cost 5296.07 path_cost 2022.04 estimated_cost 3274.03 Current Depth: 4
33 X: 27 Z 48 Dir: 3 total_cost 5307.48 path_cost 2017.11 estimated_cost 3290.37 Current Depth: 9
34 X: 27 Z 40 Dir: 4 total_cost 5314.14 path_cost 1894.04 estimated_cost 3420.1 Current Depth: 2
35 X: 29 Z 47 Dir: 1 total_cost 5321.24 path_cost 1953.11 estimated_cost 3368.13 Current Depth: 8
36 X: 24 Z 44 Dir: 2 total_cost 5323.51 path_cost 1968.27 estimated_cost 3355.23 Current Depth: 5
37 X: 27 Z 51 Dir: 3 total_cost 5332.42 path_cost 2209.11 estimated_cost 3123.31 Current Depth: 12
38 X: 29 Z 41 Dir: 2 total_cost 5338.69 path_cost 1815.87 estimated_cost 3522.82 Current Depth: 2
39 X: 27 Z 43 Dir: 4 total_cost 5339.08 path_cost 2086.04 estimated_cost 3253.04 Current Depth: 5
40 X: 27 Z 49 Dir: 3 total_cost 5350.49 path_cost 2081.11 estimated_cost 3269.38 Current Depth: 10
41 X: 27 Z 41 Dir: 4 total_cost 5357.15 path_cost 1958.04 estimated_cost 3399.11 Current Depth: 3
42 X: 30 Z 40 Dir: 0 total_cost 5372.82 path_cost 1815.87 estimated_cost 3556.95 Current Depth: 2
43 X: 18 Z 48 Dir: 4 total_cost 5372.84 path_cost 2420.82 estimated_cost 2952.01 Current Depth: 10
44 X: 19 Z 49 Dir: 2 total_cost 5373.41 path_cost 2420.82 estimated_cost 2952.58 Current Depth: 10
45 X: 30 Z 42 Dir: 2 total_cost 5373.51 path_cost 1906.38 estimated_cost 3467.13 Current Depth: 3
46 X: 18 Z 50 Dir: 2 total_cost 5373.53 path_cost 2511.33 estimated_cost 2862.2 Current Depth: 11
47 X: 31 Z 43 Dir: 2 total_cost 5408.33 path_cost 1996.89 estimated_cost 3411.44 Current Depth: 4
48 X: 30 Z 41 Dir: 0 total_cost 5429.2 path_cost 1906.38 estimated_cost 3522.82 Current Depth: 3
49 X: 17 Z 49 Dir: 4 total_cost 5429.22 path_cost 2511.33 estimated_cost 2917.88 Current Depth: 11
50 X: 16 Z 50 Dir: 4 total_cost 5429.34 path_cost 2601.84 estimated_cost 2827.5 Current Depth: 12
51 X: 17 Z 51 Dir: 2 total_cost 5429.91 path_cost 2601.84 estimated_cost 2828.07 Current Depth: 12
52 X: 15 Z 51 Dir: 4 total_cost 5432.2 path_cost 2692.35 estimated_cost 2739.85 Current Depth: 13
53 X: 29 Z 48 Dir: 1 total_cost 5444.32 path_cost 2017.11 estimated_cost 3427.21 Current Depth: 9
54 X: 28 Z 39 Dir: 0 total_cost 5449.53 path_cost 1973.22 estimated_cost 3476.31 Current Depth: 1
55 X: 29 Z 40 Dir: 0 total_cost 5450.98 path_cost 1894.04 estimated_cost 3556.95 Current Depth: 2
56 X: 28 Z 42 Dir: 0 total_cost 5454.47 path_cost 2022.04 estimated_cost 3432.43 Current Depth: 4
57 X: 20 Z 48 Dir: 2 total_cost 5462.28 path_cost 2330.31 estimated_cost 3131.97 Current Depth: 9
58 X: 31 Z 41 Dir: 0 total_cost 5463.9 path_cost 1906.38 estimated_cost 3557.51 Current Depth: 3
59 X: 29 Z 39 Dir: 0 total_cost 5471.08 path_cost 1973.22 estimated_cost 3497.87 Current Depth: 1
60 X: 28 Z 40 Dir: 0 total_cost 5472.54 path_cost 1894.04 estimated_cost 3578.5 Current Depth: 2
61 X: 29 Z 49 Dir: 1 total_cost 5474.19 path_cost 2081.11 estimated_cost 3393.08 Current Depth: 10
62 X: 27 Z 54 Dir: 3 total_cost 5480.54 path_cost 2401.11 estimated_cost 3079.43 Current Depth: 15
63 X: 29 Z 41 Dir: 0 total_cost 5480.85 path_cost 1958.04 estimated_cost 3522.82 Current Depth: 3
64 X: 29 Z 50 Dir: 1 total_cost 5482.51 path_cost 2145.11 estimated_cost 3337.4 Current Depth: 11
65 X: 27 Z 46 Dir: 4 total_cost 5487.2 path_cost 2278.04 estimated_cost 3209.16 Current Depth: 8
66 X: 29 Z 42 Dir: 0 total_cost 5489.17 path_cost 2022.04 estimated_cost 3467.13 Current Depth: 4
67 X: 28 Z 43 Dir: 0 total_cost 5497.48 path_cost 2086.04 estimated_cost 3411.44 Current Depth: 5
68 X: 27 Z 52 Dir: 3 total_cost 5498.61 path_cost 2273.11 estimated_cost 3225.5 Current Depth: 13
69 X: 27 Z 44 Dir: 4 total_cost 5505.27 path_cost 2150.04 estimated_cost 3355.23 Current Depth: 6
70 X: 14 Z 52 Dir: 4 total_cost 5511.61 path_cost 2782.86 estimated_cost 2728.75 Current Depth: 14
71 X: 15 Z 53 Dir: 2 total_cost 5512.18 path_cost 2782.86 estimated_cost 2729.32 Current Depth: 14
72 X: 14 Z 54 Dir: 2 total_cost 5512.3 path_cost 2873.37 estimated_cost 2638.93 Current Depth: 15
73 X: 29 Z 51 Dir: 1 total_cost 5512.38 path_cost 2209.11 estimated_cost 3303.27 Current Depth: 12
74 X: 28 Z 41 Dir: 0 total_cost 5515.55 path_cost 1958.04 estimated_cost 3557.52 Current Depth: 3
75 X: 29 Z 43 Dir: 0 total_cost 5519.04 path_cost 2086.04 estimated_cost 3433 Current Depth: 5
76 X: 27 Z 55 Dir: 3 total_cost 5523.56 path_cost 2465.11 estimated_cost 3058.45 Current Depth: 16
77 X: 27 Z 47 Dir: 4 total_cost 5530.22 path_cost 2342.04 estimated_cost 3188.18 Current Depth: 9
78 X: 27 Z 53 Dir: 3 total_cost 5541.63 path_cost 2337.11 estimated_cost 3204.52 Current Depth: 14
79 X: 27 Z 45 Dir: 4 total_cost 5548.29 path_cost 2214.04 estimated_cost 3334.25 Current Depth: 7
80 X: 31 Z 42 Dir: 0 total_cost 5554.41 path_cost 1996.89 estimated_cost 3557.51 Current Depth: 4
81 X: 27 Z 42 Dir: 1 total_cost 5554.9 path_cost 2280.87 estimated_cost 3274.03 Current Depth: 3
82 X: 13 Z 53 Dir: 4 total_cost 5567.99 path_cost 2873.37 estimated_cost 2694.62 Current Depth: 15
83 X: 12 Z 54 Dir: 4 total_cost 5568.11 path_cost 2963.88 estimated_cost 2604.23 Current Depth: 16
84 X: 13 Z 55 Dir: 2 total_cost 5568.68 path_cost 2963.88 estimated_cost 2604.8 Current Depth: 16
85 X: 11 Z 55 Dir: 4 total_cost 5570.97 path_cost 3054.39 estimated_cost 2516.58 Current Depth: 17
86 X: 32 Z 42 Dir: 0 total_cost 5587.72 path_cost 1996.89 estimated_cost 3590.83 Current Depth: 4
87 X: 16 Z 52 Dir: 2 total_cost 5601.05 path_cost 2692.35 estimated_cost 2908.7 Current Depth: 13
88 X: 27 Z 39 Dir: 4 total_cost 5608.13 path_cost 2198.48 estimated_cost 3409.64 Current Depth: 1
89 X: 26 Z 39 Dir: 5 total_cost 5621.56 path_cost 2190.36 estimated_cost 3431.2 Current Depth: 2
90 X: 29 Z 52 Dir: 1 total_cost 5635.46 path_cost 2273.11 estimated_cost 3362.35 Current Depth: 13
91 X: 29 Z 44 Dir: 0 total_cost 5642.12 path_cost 2150.04 estimated_cost 3492.08 Current Depth: 6
92 X: 28 Z 46 Dir: 0 total_cost 5645.6 path_cost 2278.04 estimated_cost 3367.56 Current Depth: 8
93 X: 26 Z 43 Dir: 1 total_cost 5645.98 path_cost 2371.38 estimated_cost 3274.6 Current Depth: 4
94 X: 10 Z 56 Dir: 4 total_cost 5650.38 path_cost 3144.9 estimated_cost 2505.48 Current Depth: 18
95 X: 11 Z 57 Dir: 2 total_cost 5650.95 path_cost 3144.9 estimated_cost 2506.05 Current Depth: 18
96 X: 10 Z 58 Dir: 2 total_cost 5651.08 path_cost 3235.41 estimated_cost 2415.67 Current Depth: 19
97 X: 32 Z 43 Dir: 0 total_cost 5657.24 path_cost 2087.4 estimated_cost 3569.84 Current Depth: 5
98 X: 28 Z 44 Dir: 0 total_cost 5663.67 path_cost 2150.04 estimated_cost 3513.64 Current Depth: 6
99 X: 29 Z 53 Dir: 1 total_cost 5665.33 path_cost 2337.11 estimated_cost 3328.22 Current Depth: 14
100 X: 23 Z 42 Dir: 5 total_cost 5669.25 path_cost 2461.89 estimated_cost 3207.36 Current Depth: 5
101 X: 29 Z 45 Dir: 0 total_cost 5671.99 path_cost 2214.04 estimated_cost 3457.95 Current Depth: 7
102 X: 29 Z 54 Dir: 1 total_cost 5673.64 path_cost 2401.11 estimated_cost 3272.53 Current Depth: 15
103 X: 27 Z 50 Dir: 4 total_cost 5678.34 path_cost 2534.04 estimated_cost 3144.3 Current Depth: 12
104 X: 33 Z 43 Dir: 0 total_cost 5678.8 path_cost 2087.4 estimated_cost 3591.4 Current Depth: 5
105 X: 25 Z 40 Dir: 5 total_cost 5679.41 path_cost 2280.87 estimated_cost 3398.55 Current Depth: 3
106 X: 29 Z 46 Dir: 0 total_cost 5680.3 path_cost 2278.04 estimated_cost 3402.26 Current Depth: 8
107 X: 28 Z 47 Dir: 0 total_cost 5688.62 path_cost 2342.04 estimated_cost 3346.58 Current Depth: 9
108 X: 27 Z 56 Dir: 3 total_cost 5689.75 path_cost 2529.11 estimated_cost 3160.64 Current Depth: 17
109 X: 23 Z 46 Dir: 1 total_cost 5693.67 path_cost 2642.91 estimated_cost 3050.76 Current Depth: 7
110 X: 27 Z 48 Dir: 4 total_cost 5696.41 path_cost 2406.04 estimated_cost 3290.37 Current Depth: 10
111 X: 27 Z 39 Dir: 5 total_cost 5696.98 path_cost 2287.33 estimated_cost 3409.64 Current Depth: 2
112 X: 29 Z 55 Dir: 1 total_cost 5703.51 path_cost 2465.11 estimated_cost 3238.4 Current Depth: 16
113 X: 28 Z 45 Dir: 0 total_cost 5706.69 path_cost 2214.04 estimated_cost 3492.65 Current Depth: 7
114 X: 9 Z 57 Dir: 4 total_cost 5706.76 path_cost 3235.41 estimated_cost 2471.35 Current Depth: 19
115 X: 8 Z 58 Dir: 4 total_cost 5706.89 path_cost 3325.92 estimated_cost 2380.97 Current Depth: 20
116 X: 9 Z 59 Dir: 2 total_cost 5707.45 path_cost 3325.92 estimated_cost 2381.54 Current Depth: 20
117 X: 7 Z 59 Dir: 4 total_cost 5709.74 path_cost 3416.43 estimated_cost 2293.31 Current Depth: 21
118 X: 29 Z 47 Dir: 0 total_cost 5710.17 path_cost 2342.04 estimated_cost 3368.13 Current Depth: 9
119 X: 27 Z 59 Dir: 3 total_cost 5714.69 path_cost 2721.11 estimated_cost 2993.58 Current Depth: 20
120 X: 27 Z 51 Dir: 4 total_cost 5721.35 path_cost 2598.04 estimated_cost 3123.31 Current Depth: 13
121 X: 27 Z 57 Dir: 3 total_cost 5732.76 path_cost 2593.11 estimated_cost 3139.65 Current Depth: 18
122 X: 27 Z 49 Dir: 4 total_cost 5739.42 path_cost 2470.04 estimated_cost 3269.38 Current Depth: 11
123 X: 12 Z 56 Dir: 2 total_cost 5739.83 path_cost 3054.39 estimated_cost 2685.44 Current Depth: 17
124 X: 28 Z 41 Dir: 1 total_cost 5747.87 path_cost 2190.36 estimated_cost 3557.52 Current Depth: 2
125 X: 27 Z 42 Dir: 5 total_cost 5753.36 path_cost 2479.33 estimated_cost 3274.03 Current Depth: 5
126 X: 32 Z 44 Dir: 2 total_cost 5759.43 path_cost 2087.4 estimated_cost 3672.03 Current Depth: 5
127 X: 22 Z 43 Dir: 5 total_cost 5760.33 path_cost 2552.4 estimated_cost 3207.93 Current Depth: 6
128 X: 24 Z 41 Dir: 5 total_cost 5770.49 path_cost 2371.38 estimated_cost 3399.11 Current Depth: 4
129 X: 27 Z 40 Dir: 5 total_cost 5771.44 path_cost 2351.33 estimated_cost 3420.1 Current Depth: 3
130 X: 28 Z 49 Dir: 0 total_cost 5772.74 path_cost 2470.04 estimated_cost 3302.7 Current Depth: 11
131 X: 22 Z 47 Dir: 1 total_cost 5784.75 path_cost 2733.42 estimated_cost 3051.33 Current Depth: 8
132 X: 29 Z 39 Dir: 7 total_cost 5785.2 path_cost 2287.33 estimated_cost 3497.87 Current Depth: 2
133 X: 6 Z 60 Dir: 4 total_cost 5789.15 path_cost 3506.94 estimated_cost 2282.22 Current Depth: 22
134 X: 7 Z 61 Dir: 2 total_cost 5789.72 path_cost 3506.94 estimated_cost 2282.79 Current Depth: 22
135 X: 6 Z 62 Dir: 2 total_cost 5789.85 path_cost 3597.45 estimated_cost 2192.4 Current Depth: 23

Wow, rank 135, it is extremely low, how can I make it rise to the top?


int angleDiff = abs(srcDir - destDir);

   if (angleDiff > 4) {
        // 5-2
        // 6-4
        // 7-6
        switch (angleDiff)
        {
        case 5:
            angleDiff = 3;
            break;
        case 6:
            angleDiff = 2;
            break;
        case 7:
            angleDiff = 1;
            break;
        }

    }

    
    float w = 1.0f;
    switch (angleDiff) {
    case 0:
        w = 1.0f;
        break;
    case 1:
        w = 2.0f;
        break;
    case 2:
        w = 3.0f;
        break;
    case 3:
        w = 4.0f;
        break;
    case 4:
        w = 5.0f;
        break;

    }
lucky6969b
lucky6969b

In the previous post, I actually made some modifications

The angleDiff of 1 actually times 3.0, 2 times 4.0, 3 times 5.0, 4 times 6.0

I cannot edit the last post because of the annoying javascript

ferrous
ferrous

I was having trouble in calculating the coordinates of 24-directional search.
Given 24-directional search, I need to set the gSearch flag to 3.
If I set it to 4, it is 32 directional search,
But opening surrounding 24 tiles should be the correct way.


for (int direction = 0; direction < totalDirections; direction++)
{
   int posDest = direction % gSearch;

   ptNew.x = ptCurrent.x + gDirOffset[posDest].x;
   ptNew.y = ptCurrent.y + gDirOffset[posDest].y
You can see that when gSearch is 3, it is searching the right half of the map always.
But it is set to 4, it is opening 32 nodes in one lot.
It is then a 32-directional search, but as to me, opening surrounding 24 nodes is the only correct way of doing it.
Why not writing this instead?


int dirDest = direction / gSearch;
ptNew.x = ptCurrent.x + gDirOffset[dirDest].x

I generate the 24 tiles as offsets at startup like so:


dir24 = new int[24];
for(int y = -2; y <= 2; ++y)
{
  for(int x = -2; x <= 2; ++x)
  {
	if(x == 0 && y == 0)
  	   continue;
			
	dir24[dir24Length++] = x + y * this.Width;
  }
}
ferrous
ferrous

Also, for the heuristic values, I double checked my code, I guess in the end, this is what I ended up with:

nVisit.heuristicValue = endDubin.GetHValue() + kGPreference * dubinToNeighbor.GetHValue();

GetHValue() is just the total length of the dubin, the endDubin is the dubin that is from that tile to the goal, and dubinToNeighbor is the dubin to get to that tile, and kGPreference in my case is 1.5f.

So I ended up not doing any multipliers by arc.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.