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