orc-smasher

orc-smasher/src/algorithm.c
algorithm.c
⎇
Raw
1#include <helper.h>
2#include <stdbool.h>
3#include <string.h>
4#include <stddef.h>
5#include <darray.h>
6
7#include <algorithm.h>
8
9#define index(x) ((x)*2+1)
10#define indexpoint(p) ((struct point){index(p.y), index(p.x)})
11#define unindex(x) (((x)-1)/2)
12#define unindexpoint(p) ((struct point){unindex(p.y), unindex(p.x)})
13
14
15#define UNVISITED '#'
16#define VISITED ' '
17
18
19typedef unsigned long size_t;
20
21static char *maze_at(char *m, size_t xs, struct point p)
22{
23 return &m[p.y*xs+p.x];
24}
25
26static bool maze_in_bounds(size_t ys, size_t xs, struct point p)
27{
28 return p.y > 0 && (size_t)p.y < ys-1 && p.x > 0 && (size_t)p.x < xs-1;
29}
30
31struct game make_maze(size_t y, size_t x)
32{
33 y += (y%2 == 0); //it must be an uneven number to look fine
34 x += (x%2 == 0);
35 assert(y >= 5);
36 assert(x >= 5);
37 struct game g = create_game(y, x);
38
39 char *maze = xmalloc(y * x + 1);
40 memset(maze, UNVISITED, y * x);
41 maze[y * x] = '\0';
42 darray(struct point) stack = darray_new();
43
44 struct point current = {0, 0};
45 *maze_at(maze, x, indexpoint(current)) = VISITED;
46
47 while(true)
48 {
49 struct point nb[4] =
50 {
51 {index(current.y), index(current.x-1)},
52 {index(current.y), index(current.x+1)},
53 {index(current.y-1), index(current.x)},
54 {index(current.y+1), index(current.x)},
55 };
56
57 if((maze_in_bounds(y,x,nb[0]) && (*maze_at(maze,x,nb[0]) == UNVISITED)) ||
58 (maze_in_bounds(y,x,nb[1]) && (*maze_at(maze,x,nb[1]) == UNVISITED)) ||
59 (maze_in_bounds(y,x,nb[2]) && (*maze_at(maze,x,nb[2]) == UNVISITED)) ||
60 (maze_in_bounds(y,x,nb[3]) && (*maze_at(maze,x,nb[3]) == UNVISITED)))
61 {
62 int c;
63 darray_append(stack, current);
64
65 while(!maze_in_bounds(y,x,nb[c=randrange(0,3)]) || *maze_at(maze, x, nb[c]) != UNVISITED);
66 *maze_at(maze, x, nb[c]) = VISITED;
67
68 struct point choice = unindexpoint(nb[c]);
69 struct point diff = {choice.y-current.y, choice.x-current.x};
70 *maze_at(maze, x, (struct point){index(current.y)+diff.y, index(current.x)+diff.x}) = VISITED;
71 current = choice;
72 } else if(!darray_empty(stack)) {
73 current = darray_pop(stack);
74 } else {
75 break;
76 }
77 }
78
79 for(size_t i = 0; i < y; i++)
80 {
81 for(size_t j = 0; j < x; j++)
82 {
83 if(*maze_at(maze, x, (struct point){i,j}) == VISITED)
84 game_at(&g, (struct point){i,j})->u->ground = EMPTYFIELD;
85 else
86 game_at(&g, (struct point){i,j})->u->ground = WALLFIELD;
87 }
88 }
89
90 game_at(&g, (struct point){y-2,x-2})->u->ground.symbol = '*';
91 game_at(&g, (struct point){y-2,x-2})->u->ground.type = TARGET;
92
93 darray_free(stack);
94 free(maze);
95 return g;
96}
97
98struct node
99{
100 struct node *parent;
101 struct point p;
102 size_t g;
103 size_t h;
104 size_t f;
105};
106
107pointarr astar(struct game *g, struct point start, struct point target, size_t maxdist)
108{
109 darray(struct node*) open = darray_new();
110 darray(struct node*) closed = darray_new();
111 pointarr result = darray_new();
112 struct node *startnode = xmalloc(sizeof(*startnode));
113 startnode->p = start;
114 startnode->parent = NULL;
115 startnode->f = 0;
116 startnode->g = 0;
117 startnode->h = 0;
118
119 darray_append(open, startnode);
120 while(!darray_empty(open))
121 {
122 size_t currenti = 0;
123 struct node *currentnode = darray_item(open, currenti);
124 for(size_t i = 0; i < open.size; i++)
125 {
126 if(darray_item(open, i)->f < currentnode->f) {
127 currenti = i;
128 currentnode = darray_item(open, i);
129 }
130 }
131
132 darray_append(closed, darray_item(open, currenti));
133 darray_remove(open, currenti);
134 if(pointeq(currentnode->p, target))
135 {
136 struct node *this = currentnode;
137 darray_append(result, this->p);
138 while((this = this->parent) != NULL)
139 {
140 darray_append(result, this->p);
141 }
142 }
143
144 darray(struct point) children = darray_new();
145 struct point up = (struct point){currentnode->p.y-1, currentnode->p.x};
146 struct point down = (struct point){currentnode->p.y+1, currentnode->p.x};
147 struct point left = (struct point){currentnode->p.y, currentnode->p.x-1};
148 struct point right = (struct point){currentnode->p.y, currentnode->p.x+1};
149
150 if(game_at(g,left)->u->ground.type == NOOBJ)
151 darray_append(children, left);
152 if(game_at(g,right)->u->ground.type == NOOBJ)
153 darray_append(children, right);
154 if(game_at(g,up)->u->ground.type == NOOBJ)
155 darray_append(children, up);
156 if(game_at(g,down)->u->ground.type == NOOBJ)
157 darray_append(children, down);
158
159
160 for(size_t i = 0; i < children.size; i++)
161 {
162 struct point child = darray_item(children, i);
163 struct node **n;
164 darray_foreach(n, closed)
165 {
166 if(pointeq((*n)->p, child))
167 goto next;
168 }
169
170 if(maxdist != 0 && currentnode->g+1 > maxdist)
171 goto next;
172
173 darray_foreach(n, open)
174 {
175 if(pointeq((*n)->p, child) && currentnode->g+1 > (*n)->g)
176 goto next;
177 }
178 darray_foreach(n, closed)
179 {
180 if(pointeq((*n)->p, child) &&currentnode->g+1 > (*n)->g)
181 goto next;
182 }
183
184 struct node *childnode = xmalloc(sizeof(*childnode));
185 childnode->p = child;
186 childnode->parent = currentnode;
187 childnode->g = currentnode->g + 1;
188 childnode->h = ipow(childnode->p.y - target.y, 2) + ipow(childnode->p.x - target.x, 2);
189 childnode->f = childnode->g + childnode->h;
190
191 darray_append(open, childnode);
192
193
194 next:;
195 }
196 darray_free(children);
197
198 }
199
200 struct node **n;
201 darray_foreach(n, closed)
202 {
203 free(*n);
204 }
205
206 darray_free(open);
207 darray_free(closed);
208
209 return result;
210}
211