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