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
|
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <curses.h>
#include "path.h"
#include "map.h"
#include "structs.h"
#include "priority_queue.h"
#include "error.h"
int anim(Map map, size_t width, size_t height, Position start, Position end, Position *cur, char visited[height][width], PositionPQ *frontier) {
draw_map(map, width, height, 0, 0, start, end, cur, NULL, visited, frontier);
mvprintw(height+2, 0, "cur: %zu %zu", cur->x, cur->y);
/* TODO: input, automatic mode */
switch (getch()) {
case 'q':
return -1;
}
return 0;
}
/* BLOODY FUCK IT WORKS */
Path breadth_first_search_path(int dirs, Map map, size_t width, size_t height, Position start, Position end, char visited[height][width], char should_anim) {
/* The function to use to find neighbours */
unsigned int (*neighbours)(Position[], size_t[], Position, size_t, size_t, char[height][width]) = NULL;
switch (dirs) {
case 4: neighbours = &neighbours_4dir; break;
case 8: neighbours = &neighbours_8dir; break;
default: error("Tried to call breadth_first_search_path with wrong direction amount\n");
}
Path path = malloc(sizeof(PathNode)*height);
if (path == NULL) return NULL;
for (size_t row = 0; row < height; row++) {
path[row] = malloc(sizeof(PathNode) * width);
if (path[row] == NULL) return NULL;
memset(path[row], 0, width * sizeof(PathNode));
}
PositionPQ *frontier = ppq_new(start, 0);
memset(visited, 0, height * width * sizeof(char));
while (frontier != NULL) {
Position cur = ppq_pop(&frontier);
visited[cur.y][cur.x] = 1;
if (cur.x == end.x && cur.y == end.y) {
ppq_free(frontier);
return path; /* Found path */
}
Position na[dirs];
unsigned int nc = neighbours(na, NULL, cur, width, height, visited);
for (unsigned int i = 0; i < nc; i++) {
/* The Russian constitution doesn't allow walking on walls */
if (map[na[i].y][na[i].x] == WALL) continue;
if (ppq_insert(&frontier, na[i], 0) != PPQ_INSERT_ALREADY) {
path[na[i].y][na[i].x].parent = cur;
}
}
if (should_anim) {
if (anim(map, width, height, start, end, &cur, visited, frontier) == -1) return NULL;
}
}
return NULL;
}
/* FIXME: Rewrite this shit */
Path astar_path_4dir(Map map, size_t width, size_t height, Position start, Position end) {
Path path = malloc(sizeof(PathNode)*height);
if (path == NULL) return NULL;
for (size_t row = 0; row < height; row++) {
path[row] = malloc(sizeof(PathNode) * width);
if (path[row] == NULL) return NULL;
memset(path[row], 0, width * sizeof(PathNode));
}
size_t costs[height][width];
memset(costs, 0xFF, height*width*sizeof(size_t));
(void)start, (void)end, (void)map;
return NULL;
}
/* FIXME: I feel like there's a better way to do this, but not sure */
size_t manhattan_distance(Position a, Position b) {
size_t d = 0;
if (a.x > b.x) {
d += a.x - b.x;
} else {
d += b.x - a.x;
}
if (a.y > b.y) {
d += a.y - b.y;
} else {
d += b.y - a.y;
}
return d;
}
void path_free(Path path, size_t height) {
if (path == NULL) return;
for (size_t i = 0; i < height; i++) {
free(path[i]);
}
free(path);
}
|
