Entry |
Year |
Total Time (s) |
Average Time (ms) (per path) |
Average Start Time (ms) (first 20 moves) |
Max Time (ms) (per segment) |
Average Path Length |
Average Suboptimality |
Problems Solved |
# Invalid |
Unsolved |
RAM Usage (MB) (before) |
RAM Usage (MB) (after) |
Storage |
Precomputation Time (total min) |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Compressed Path Databases (20 moves) | 2012 | 1190.0 | 0.704 | 0.029 | 0.683 | 2127 | 1.0000 | 1689740 | 0 | 49600 | 468.32 | 494.77 | 52GB | 81408 |
Compressed Path Databases (move by move) | 2012 | 1348.5 | 0.798 | 0.011 | 0.005 | 2127 | 1.0000 | 1689740 | 0 | 49600 | 468.32 | 571.36 | 52GB | 81408 |
Jump Point Search | 2012 | 108749.9 | 62.524 | 62.524 | 62.524 | 2095 | 1.0000 | 1739340 | 0 | 0 | 252.18 | 278.97 | 0 | 0 |
Jump Point Search (plus) | 2012 | 36307.5 | 20.874 | 20.874 | 20.874 | 2095 | 1.0000 | 1739340 | 0 | 0 | 356.28 | 383.05 | 3.0G | 74 |
Manhattan Cohesive Areas | 2012 | 130.8 | 216.235 | 216.235 | 216.235 | 5 | 1.0000 | 605 | 1619220 | 119515 | 267.01 | 483.27 | 0 | 8 |
Pseudo Priority Queues | 2012 | 28930.3 | 16.634 | 16.634 | 16.634 | 2098 | 1.0033 | 1739225 | 115 | 0 | 47.87 | 74.05 | 0 | 0 |
SubgoalGraph (variant 1) | 2012 | 2079.5 | 1.196 | 1.196 | 1.196 | 2095 | 1.0000 | 1739340 | 0 | 0 | 15.08 | 41.53 | 259MB | 1 |
SubgoalGraph (variant 2) | 2012 | 1944.0 | 1.118 | 1.118 | 1.118 | 2095 | 1.0000 | 1739340 | 0 | 0 | 17.33 | 43.78 | 554MB | 15 |
Tree Cache | 2012 | 74.7 | 0.043 | 0.043 | 0.043 | 4063 | 4.3897 | 1739340 | 0 | 0 | 13.04 | 68.58 | 96MB | 0.2 |
Bubble Dragon | 2012 | 255.7 | 0.147 | 0.008 | 0.007 | 2259 | 1.1379 | 1739340 | 0 | 0 | 20.21 | 53.53 | 649M | 13 |
Block A* | 2012 | 23104.1 | 13.283 | 13.283 | 13.283 | 2413 | 1.1557 | 1739340 | 0 | 0 | 65.75 | 103.19 | 0 | 0 |
Subgoal Graph (Improved 2012) | 2013 | 2019.0 | 1.161 | 1.161 | 1.161 | 2095 | 1.0000 | 1739340 | 0 | 0 | 15.12 | 41.57 | 259M | 1 |
Subgoal Graph (Fast) | 2013 | 1875.2 | 1.078 | 1.078 | 1.078 | 2095 | 1.0000 | 1739340 | 0 | 0 | 18.50 | 44.96 | 703MB | 3.5 |
Subgoal Graph (Low Memory) | 2013 | 2485.0 | 1.429 | 1.429 | 1.429 | 2095 | 1.0000 | 1739340 | 0 | 0 | 13.49 | 40.00 | 93MB | 1 |
Subgoal Graph (Optimal) | 2013 | 2003.3 | 1.154 | 1.154 | 1.154 | 2098 | 1.0000 | 1736645 | 2695 | 0 | 15.56 | 42.01 | 278MB | 1 |
Novella A* | 2013 | 117226.5 | 69.592 | 69.592 | 69.592 | 2190 | 1.0145 | 1684485 | 5 | 54850 | 46.92 | 79.17 | 0 | 0 |
Tree Cache | 2013 | 50.9 | 0.029 | 0.029 | 0.029 | 2564 | 2.1657 | 1739340 | 0 | 0 | 16.58 | 48.80 | 568MB | 0.5 |
DAO Engine (Limited) | 2013 | 9771.6 | 7.346 | 7.346 | 7.346 | 2130 | 1.1201 | 1330200 | 0 | 409140 | 14.54 | 36.84 | 0 | 0 |
DAO (1-level abstraction) | 2015 | 27451.9 | 15.783 | 2.660 | 2.586 | 2463 | 1.1285 | 1739340 | 0 | 0 | 14.84 | 55.24 | 3.5 MB | 0.2 |
BLJPS | 2014 | 25139.4 | 14.453 | 14.453 | 14.453 | 2095 | 1.0000 | 1739340 | 0 | 0 | 13.58 | 42.59 | 20 MB | 0.2 |
BLJPS2 | 2014 | 12947.4 | 7.444 | 7.444 | 7.444 | 2095 | 1.0000 | 1739340 | 0 | 0 | 13.96 | 42.68 | 47 MB | 0.2 |
BLJPS2_Sub | 2014 | 2731.8 | 1.571 | 1.571 | 1.571 | 2095 | 1.0000 | 1739340 | 0 | 0 | 19.82 | 48.00 | 264 MB | 0.2 |
CH | 2014 | 630.4 | 0.362 | 0.362 | 0.362 | 2095 | 1.0000 | 1739340 | 0 | 0 | 44.66 | 72.04 | 2.4 GB | 968.8 |
SRC-cut | 2014 | 276.5 | 0.160 | 0.160 | 0.160 | 2107 | 1.0000 | 1725440 | 0 | 13900 | 431.09 | 458.49 | 52 GB | 12330.8 |
SRC-cut-i | 2014 | 358.1 | 0.208 | 0.004 | 0.001 | 2107 | 1.0000 | 1725440 | 0 | 13900 | 431.09 | 540.94 | 52 GB | 12330.8 |
SRC-dfs-i | 2014 | 329.6 | 0.189 | 0.004 | 0.001 | 2095 | 1.0000 | 1739340 | 0 | 0 | 246.92 | 356.14 | 52 GB | 12330.8 |
SRC-dfs | 2014 | 251.7 | 0.145 | 0.145 | 0.145 | 2095 | 1.0000 | 1739340 | 0 | 0 | 246.92 | 274.16 | 52 GB | 12330.8 |
NSubgoal | 2014 | 1345.2 | 0.773 | 0.773 | 0.773 | 2095 | 1.0000 | 1739340 | 0 | 0 | 16.29 | 42.54 | 293MB | 2.6 |
RA | 2014 | 492223.7 | 282.995 | 282.995 | 282.995 | 2248 | 1.0580 | 1739340 | 0 | 0 | 32.05 | 58.91 | 0 | 0 |
A* bucket | 2014 | 59232.8 | 36.815 | 36.815 | 36.815 | 2206 | 1.0001 | 1608910 | 80830 | 49600 | 3577.97 | 3605.79 | 0 | 0.1 |
JPS+ | 2014 | 13449.1 | 7.732 | 7.732 | 7.732 | 2095 | 1.0000 | 1739340 | 0 | 0 | 147.03 | 175.19 | 947 MB | 1.0 |
JPS+ Bucket | 2014 | 2811.6 | 1.616 | 1.616 | 1.616 | 2095 | 1.0000 | 1739340 | 0 | 0 | 379.32 | 407.46 | 947MB | 1.0 |