-
Notifications
You must be signed in to change notification settings - Fork 77
/
AStarTestCases.ts
125 lines (100 loc) · 12 KB
/
AStarTestCases.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
import {Coordinate} from "./GridGraph";
/********************************************************************************
** AStarTestCases
This file contains several test cases.
You are free to add new ones.
********************************************************************************/
export interface TestCase {
xsize : number;
ysize : number;
cost : number;
path : Coordinate[];
walls : Coordinate[];
}
export var testCases : TestCase[] = [];
testCases.push({
xsize: 5, ysize: 5, cost: 8,
path: [[0,1], [0,2], [0,3], [1,3], [2,3], [3,3], [3,4], [4,4]],
walls: [[1,4], [3,2], [0,4], [4,0], [2,2], [2,1], [2,2], [1,2]]
});
testCases.push({
xsize: 10, ysize: 10, cost: 18,
path: [[0,1], [0,2], [0,3], [1,3], [2,3], [3,3], [3,4], [4,4], [5,4], [5,5], [5,6], [6,6], [6,7], [7,7], [8,7], [8,8], [9,8], [9,9]],
walls: [[7,5], [7,0], [4,2], [7,5], [3,2], [8,0], [1,5], [8,0], [5,8], [5,8], [0,6], [7,2], [0,4], [6,8], [5,7], [4,0], [3,5], [3,8], [8,6], [5,3], [0,6], [4,5], [2,2], [6,4], [2,7], [2,1], [6,8], [6,5], [2,5], [2,2], [4,2], [4,2], [1,2], [8,0]]
});
testCases.push({
xsize: 10, ysize: 10, cost: 24,
path: [[0,1], [1,1], [1,2], [1,3], [2,3], [3,3], [4,3], [5,3], [5,2], [5,1], [6,1], [7,1], [7,0], [8,0], [9,0], [9,1], [9,2], [9,3], [9,4], [9,5], [9,6], [9,7], [9,8], [9,9]],
walls: [[3,6], [2,8], [8,3], [7,6], [6,2], [2,2], [4,5], [3,0], [3,0], [4,4], [4,0], [0,2], [5,7], [8,3], [4,0], [3,5], [4,5], [0,4], [6,8], [4,5], [3,2], [3,0], [6,8], [7,7], [3,4], [1,7], [2,2], [4,6], [7,2], [6,0], [7,4], [0,6], [4,2], [5,4], [7,7], [4,2], [8,2], [8,1], [3,0], [1,8], [3,2], [6,5], [2,1], [7,7], [1,6], [8,2], [3,0], [7,4], [3,7], [5,8], [8,2], [4,5], [4,6], [4,5]]
});
testCases.push({
xsize: 11, ysize: 11, cost: 24,
path: [[1,0], [1,1], [2,1], [2,2], [2,3], [2,4], [1,4], [0,4], [0,5], [0,6], [0,7], [1,7], [1,8], [2,8], [3,8], [4,8], [4,9], [4,10], [5,10], [6,10], [7,10], [8,10], [9,10], [10,10]],
walls: [[5,1], [4,7], [8,2], [4,5], [2,9], [6,9], [7,1], [7,6], [1,6], [4,2], [1,3], [4,2], [3,6], [5,0], [9,8], [0,2], [8,8], [0,1], [8,2], [8,6], [1,5], [2,5], [8,4], [9,1], [5,4], [9,7], [9,1], [5,5], [5,7], [2,7], [7,0], [9,0], [7,8], [8,5], [0,8], [5,3]]
});
testCases.push({
xsize: 12, ysize: 12, cost: 26,
path: [[0,1], [0,2], [1,2], [2,2], [2,3], [2,4], [2,5], [1,5], [1,6], [1,7], [1,8], [0,8], [0,9], [0,10], [0,11], [1,11], [2,11], [3,11], [4,11], [5,11], [6,11], [7,11], [8,11], [9,11], [10,11], [11,11]],
walls: [[6,0], [8,0], [1,0], [5,1], [0,6], [1,9], [8,7], [7,5], [6,9], [2,9], [9,3], [5,0], [3,0], [1,4], [9,2], [8,2], [6,2], [8,1], [9,0], [7,5], [3,7], [1,10], [7,0], [3,8], [7,6], [4,5], [8,4], [6,3], [6,8], [4,0], [10,8], [3,4], [10,4], [7,6], [5,3], [5,1], [3,3], [5,7], [7,5], [5,9], [3,1], [10,5], [8,10], [7,0], [6,8], [4,2], [9,10], [9,3], [5,0], [7,6], [8,0], [5,8], [2,1], [5,5], [7,8], [9,10], [0,5], [6,6], [1,10], [4,2], [4,10], [8,9], [2,0], [3,6], [6,6], [2,9], [7,8]]
});
testCases.push({
xsize: 13, ysize: 13, cost: 24,
path: [[1,0], [2,0], [2,1], [2,2], [3,2], [4,2], [5,2], [5,3], [5,4], [5,5], [5,6], [5,7], [6,7], [7,7], [7,8], [8,8], [9,8], [10,8], [10,9], [11,9], [12,9], [12,10], [12,11], [12,12]],
walls: [[7,5], [2,8], [8,4], [1,7], [10,1], [8,7], [3,9], [0,11], [7,2], [0,7], [6,11], [9,11], [9,9], [5,10], [1,3], [8,9], [3,4], [11,1], [2,4], [3,3], [9,9], [8,11], [11,10], [1,2], [0,8], [9,1], [4,3], [7,11], [10,6], [6,4], [0,4], [4,10], [0,7], [1,1], [0,7], [6,6], [5,1], [4,7], [11,8], [10,1], [0,4], [3,6], [0,5], [10,2], [9,5], [7,4], [9,3], [4,4], [7,10], [11,6], [8,0], [3,4]]
});
testCases.push({
xsize: 14, ysize: 14, cost: 26,
path: [[0,1], [0,2], [0,3], [0,4], [0,5], [1,5], [1,6], [1,7], [2,7], [3,7], [4,7], [4,8], [4,9], [5,9], [5,10], [5,11], [5,12], [5,13], [6,13], [7,13], [8,13], [9,13], [10,13], [11,13], [12,13], [13,13]],
walls: [[10,8], [6,7], [4,12], [6,12], [12,6], [8,5], [7,12], [9,10], [2,6], [7,8], [1,4], [8,0], [11,4], [3,3], [3,1], [9,0], [11,0], [8,4], [8,12], [3,2], [10,1], [2,12], [3,4], [10,9], [10,6], [8,9], [7,2], [9,10], [4,11], [7,11], [2,5], [10,2], [10,7], [10,11], [5,4], [6,3], [0,12], [1,10], [1,2], [6,3], [6,1], [7,1], [6,6], [8,11], [11,9], [2,2], [10,3], [7,5], [12,11], [2,0], [8,12], [0,11], [6,3], [8,1], [3,11]]
});
testCases.push({
xsize: 18, ysize: 18, cost: 36,
path: [[0,1], [0,2], [1,2], [2,2], [2,3], [3,3], [4,3], [4,4], [4,5], [4,6], [4,7], [5,7], [5,8], [5,9], [6,9], [7,9], [7,10], [7,11], [7,12], [8,12], [8,13], [9,13], [10,13], [10,12], [11,12], [12,12], [12,13], [12,14], [12,15], [12,16], [13,16], [13,17], [14,17], [15,17], [16,17], [17,17]],
walls: [[4,11], [5,16], [12,6], [11,4], [17,8], [14,14], [6,5], [6,8], [6,16], [8,16], [17,10], [10,7], [3,9], [11,14], [12,9], [11,6], [9,12], [14,16], [4,10], [13,4], [9,11], [15,9], [3,4], [11,10], [12,8], [11,4], [10,11], [4,17], [17,14], [0,8], [4,1], [1,5], [16,14], [6,0], [1,10], [14,13], [6,1], [9,5], [3,4], [14,2], [14,10], [14,2], [0,9], [17,8], [3,17], [9,17], [3,5], [10,8], [14,2], [0,13], [8,0], [4,12], [3,0], [0,17], [2,1], [13,3], [5,15], [7,0], [11,7], [16,16], [1,0], [4,1], [11,3], [17,8], [10,15], [6,13], [5,13], [6,8], [14,11], [14,4], [11,5], [14,7], [15,6], [15,13], [16,15], [0,9], [7,0], [1,13], [7,16], [8,11], [15,7], [6,6], [14,2], [2,16], [12,6], [14,11], [15,11], [12,1], [5,10], [3,7], [4,8], [15,12], [17,11], [6,2], [0,6], [13,7], [0,13], [2,0], [2,9], [0,11], [7,14], [2,15], [3,16], [5,16], [7,7], [1,14], [8,4], [14,16], [7,14], [8,15], [1,3], [15,8], [2,0], [7,3], [10,0], [15,14], [15,7], [8,16], [8,2], [6,15], [5,13], [12,11], [11,16], [10,0], [7,0], [9,5], [3,13], [13,9], [14,13], [3,12], [6,6], [7,13], [4,2], [6,10], [14,9], [17,0], [8,3], [2,17], [17,15], [13,15], [12,10], [11,9], [15,10], [4,8], [10,9], [14,15], [9,14], [10,2], [17,13], [0,3], [11,11], [3,0], [11,4], [11,8], [8,7], [11,16], [0,15], [8,14], [4,13], [12,7], [0,12], [0,17], [11,13], [0,16]]
});
testCases.push({
xsize: 19, ysize: 19, cost: 48,
path: [[0,1], [0,2], [0,3], [1,3], [2,3], [2,4], [2,5], [2,6], [2,7], [3,7], [4,7], [5,7], [5,6], [6,6], [7,6], [7,5], [7,4], [6,4], [6,3], [6,2], [7,2], [8,2], [9,2], [9,3], [9,4], [10,4], [10,5], [11,5], [12,5], [13,5], [13,6], [13,7], [14,7], [14,8], [15,8], [16,8], [17,8], [17,9], [18,9], [18,10], [18,11], [18,12], [18,13], [18,14], [18,15], [18,16], [18,17], [18,18]],
walls: [[4,5], [3,10], [3,17], [2,8], [5,13], [14,0], [8,8], [12,7], [1,16], [2,17], [4,1], [17,15], [12,6], [4,2], [10,8], [12,2], [4,12], [4,11], [4,1], [1,11], [0,8], [15,9], [8,17], [14,16], [0,12], [7,7], [11,6], [6,0], [2,11], [5,1], [12,14], [6,5], [1,17], [7,8], [8,7], [2,12], [13,16], [16,11], [8,8], [12,11], [1,8], [0,8], [5,10], [15,1], [3,5], [16,13], [8,1], [4,0], [12,6], [15,6], [12,3], [8,3], [10,16], [11,2], [7,12], [5,3], [1,13], [1,15], [3,9], [13,12], [17,10], [11,15], [16,16], [5,4], [3,8], [0,7], [2,2], [16,2], [6,7], [8,1], [16,17], [17,12], [5,17], [12,15], [1,4], [11,9], [6,0], [8,8], [15,17], [3,10], [9,12], [1,2], [8,12], [17,10], [5,2], [6,10], [6,9], [9,5], [8,9], [16,7], [9,14], [17,12], [14,2], [4,6], [2,10], [0,11], [10,12], [16,16], [16,5], [0,16], [10,7], [1,4], [4,12], [8,8], [10,15], [1,16], [4,1], [12,4], [1,4], [16,13], [17,17], [8,12], [14,4], [2,10], [5,12], [16,11], [14,6], [11,8], [13,1], [8,6], [17,3], [15,11], [0,7], [9,17], [1,8], [10,6], [7,3], [2,14], [8,11], [9,15], [3,3], [6,10], [8,4], [6,13], [0,11], [9,11], [17,0], [16,2]]
});
testCases.push({
xsize: 24, ysize: 24, cost: 48,
path: [[0,1], [1,1], [2,1], [2,2], [2,3], [2,4], [2,5], [2,6], [2,7], [2,8], [2,9], [3,9], [4,9], [5,9], [6,9], [7,9], [7,10], [8,10], [9,10], [9,9], [10,9], [11,9], [12,9], [13,9], [14,9], [14,10], [14,11], [14,12], [14,13], [14,14], [14,15], [14,16], [14,17], [15,17], [16,17], [16,18], [17,18], [18,18], [19,18], [19,19], [19,20], [20,20], [20,21], [21,21], [22,21], [23,21], [23,22], [23,23]],
walls: [[18,21], [5,11], [2,17], [13,17], [12,6], [4,12], [0,4], [9,5], [17,8], [19,14], [2,11], [15,9], [8,20], [10,4], [11,22], [11,11], [15,16], [7,6], [21,5], [4,8], [9,0], [10,22], [18,20], [16,4], [13,13], [8,9], [21,20], [9,18], [20,4], [2,15], [19,7], [13,20], [5,3], [16,3], [13,11], [2,17], [20,19], [21,15], [16,9], [7,7], [1,16], [0,22], [20,8], [2,21], [11,18], [22,0], [11,10], [12,16], [5,11], [8,6], [6,11], [18,17], [12,4], [7,7], [0,22], [22,19], [16,11], [22,14], [21,4], [21,17], [3,1], [9,19], [6,8], [21,10], [21,17], [6,21], [17,8], [18,5], [3,5], [2,21], [6,10], [0,3], [0,17], [10,10], [10,11], [19,16], [4,19], [11,2], [11,4], [9,4], [20,4], [7,1], [4,3], [13,3], [10,8], [9,8], [2,11], [15,15], [22,17], [16,8], [2,15], [13,6], [1,10], [9,12], [1,0], [12,15], [19,2], [1,16], [15,14], [1,3], [1,16], [18,15], [9,2], [5,1], [6,21], [10,21], [1,2], [3,13], [21,18], [1,9], [20,0], [20,1], [4,7], [7,0], [5,0], [19,21], [21,9], [17,6], [2,16], [19,16], [13,2], [0,13], [7,22], [3,7], [12,4], [12,5], [20,11], [18,7], [5,11], [22,15], [13,10], [21,4], [1,7], [14,4], [1,4], [12,10], [12,12], [20,8], [7,17], [10,6], [19,2], [1,10], [7,16], [8,14], [16,10], [1,19], [5,17], [16,8], [11,20], [11,15], [3,15], [11,0], [18,21], [6,14], [11,20], [3,17], [6,7], [8,13], [16,14], [21,1], [5,18], [0,11], [8,15], [4,20], [0,5], [21,13], [19,2], [21,13], [16,11]]
});
testCases.push({
xsize: 22, ysize: 22, cost: 42,
path: [[1,0], [2,0], [2,1], [3,1], [4,1], [4,2], [4,3], [4,4], [5,4], [5,5], [6,5], [7,5], [8,5], [8,6], [8,7], [9,7], [10,7], [11,7], [12,7], [13,7], [14,7], [15,7], [16,7], [16,8], [16,9], [16,10], [16,11], [16,12], [16,13], [17,13], [17,14], [17,15], [17,16], [17,17], [18,17], [19,17], [20,17], [20,18], [20,19], [20,20], [21,20], [21,21]],
walls: [[6,0], [15,5], [13,3], [4,16], [16,6], [9,14], [11,9], [3,20], [11,6], [10,9], [0,12], [5,14], [4,9], [5,16], [10,8], [8,18], [9,13], [18,2], [15,9], [6,16], [5,18], [4,5], [11,18], [9,6], [3,12], [15,11], [19,1], [6,9], [15,9], [7,9], [9,18], [7,13], [7,20], [9,10], [17,10], [18,5], [4,17], [2,10], [8,10], [19,18], [1,12], [12,4], [17,10], [11,12], [18,16], [15,20], [8,11], [1,19], [7,13], [15,8], [0,1], [9,10], [7,13], [2,3], [7,8], [0,18], [4,5], [13,19], [10,5], [17,11], [6,16], [15,18], [0,2], [17,0], [19,12], [6,0], [7,3], [3,19], [1,1], [11,4], [10,3], [19,6], [3,16], [14,6], [19,11], [20,1], [17,0], [18,0], [5,8], [7,7], [4,11], [6,3], [0,15], [15,4], [13,10], [18,15], [7,1], [0,4], [20,3], [6,7], [15,1], [1,15], [18,19], [9,0], [0,13], [7,6], [1,17], [9,13], [14,2], [11,3], [11,3], [9,10], [12,20], [9,19], [16,1], [20,16], [10,3], [13,17], [8,15], [5,12], [14,20], [6,15], [9,17], [18,0], [2,6], [4,16], [7,8], [14,8], [20,6], [20,8], [13,10], [6,4], [9,0], [0,4], [19,9], [5,3], [15,5], [18,11], [4,5], [4,16], [19,6], [10,18], [14,4], [18,20], [16,14], [1,13], [7,8], [15,2], [18,11], [3,10]]
});
// Make a test case twice as large. The optimal path will not always be correct.
function doubleTest(test : TestCase) : TestCase {
var doubleWalls : Coordinate[] = test.walls.slice();
for (var i = 0; i < test.walls.length; i++) {
var [x, y] = test.walls[i];
doubleWalls.push([x + test.xsize, y], [x, y + test.ysize], [x + test.xsize, y + test.ysize]);
}
var doublePath : Coordinate[] = test.path.slice();
doublePath.push([test.xsize-1, test.ysize], [test.xsize, test.ysize]);
for (var i = 0; i < test.path.length; i++) {
var [x, y] = test.path[i];
doublePath.push([x + test.xsize, y + test.ysize]);
}
return {xsize: 2*test.xsize, ysize: 2*test.ysize,
cost: 2*test.cost + 2,
path: doublePath, walls: doubleWalls};
}
// size: 44 x 44
testCases.push(doubleTest(testCases[testCases.length-1]));
// size: 88 x 88
testCases.push(doubleTest(testCases[testCases.length-1]));
// size: 176 x 176
testCases.push(doubleTest(testCases[testCases.length-1]));
// size: 352 x 352
testCases.push(doubleTest(testCases[testCases.length-1]));
// size: 704 x 704
testCases.push(doubleTest(testCases[testCases.length-1]));
// size: 1408 x 1408
// testCases.push(doubleTest(testCases[testCases.length-1]));
// size: 2816 x 2816
// testCases.push(doubleTest(testCases[testCases.length-1]));