fork(9) download
copy 
  1.  
  2. #include <assert.h>
  3. #include <limits.h>
  4. #include <math.h>
  5. #include <stdbool.h>
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <time.h>
  9.  
  10. #define N 10
  11. #define GRAVITY_WELL_CHANCE 0.1
  12. #define ASTEROID_CHANCE 0.3
  13.  
  14. #define START_X 0
  15. #define START_Y 0
  16. #define END_X 9
  17. #define END_Y 9
  18.  
  19. #define IN_BOUNDS(x, y) ((x) >= 0 && (x) < N && (y) >= 0 && (y) < N)
  20. #define SQ(x) ((x) * (x))
  21.  
  22. enum obstacle {
  23. 	NO_OBSTACLE,
  24. 	GRAVITY_WELL,
  25. 	ASTEROID,
  26. };
  27.  
  28. enum path {
  29. 	NO_PATH,
  30. 	PATH,
  31. 	START,
  32. 	END,
  33. };
  34.  
  35. /* A node during path finding. */
  36. struct node {
  37. 	int x;
  38. 	int y;
  39. 	struct node *prev;
  40. 	struct node *parent;
  41. };
  42.  
  43. static enum obstacle obstacle_map[N * N];
  44. static enum path path_map[N * N];
  45. static bool visited[N * N];
  46.  
  47. /* Places an obstacle at a random free spot. */
  48. static void place_at_random_spot(enum obstacle obst)
  49. {
  50. 	int x;
  51. 	int y;
  52. 	int at_start;
  53. 	int at_end;
  54.  
  55. 	do {
  56. 		x = rand() % N;
  57. 		y = rand() % N;
  58. 		at_start = x == START_X && y == START_Y;
  59. 		at_end = y == END_X && y == END_Y;
  60. 	} while (at_start || at_end || obstacle_map[y * N + x]);
  61.  
  62. 	obstacle_map[y * N + x] = obst;
  63. }
  64.  
  65. /* Calculates distance. No need to sqrt. */
  66. static int distance_to_end(int x, int y)
  67. {
  68. 	return SQ(x - END_X) + SQ(y - END_Y);
  69. }
  70.  
  71. /* Initialized the obstacle_map with random data. */
  72. static void initialize(void)
  73. {
  74. 	int well_count = ((int)N * N * GRAVITY_WELL_CHANCE);
  75. 	int asteroid_count = ((int)N * N * ASTEROID_CHANCE);
  76. 	unsigned int seed = time(NULL);
  77.  
  78. 	srand(seed);
  79.  
  80. 	while (well_count-- > 0) {
  81. 		place_at_random_spot(GRAVITY_WELL);
  82. 	}
  83.  
  84. 	while (asteroid_count-- > 0) {
  85. 		place_at_random_spot(ASTEROID);
  86. 	}
  87.  
  88. 	path_map[START_Y * N + START_X] = START;
  89. 	path_map[END_Y * N + END_X] = END;
  90. }
  91.  
  92. /* Returns true if the spot is safe. A square is safe if it is inside
  93.  * the map, isn't on an asteroid, and isn't near a gravity well.
  94.  */
  95. static bool is_obstructed(int x, int y)
  96. {
  97. 	int dx;
  98. 	int dy;
  99. 	int tx;
  100. 	int ty;
  101. 	bool obst;
  102.  
  103. 	if (!IN_BOUNDS(x, y)) {
  104. 		return true;
  105. 	}
  106.  
  107. 	if (obstacle_map[y * N + x] == ASTEROID) {
  108. 		return true;
  109. 	}
  110.  
  111. 	for (dy = -1; dy <= 1; ++dy) {
  112. 		for (dx = -1; dx <= 1; ++dx) {
  113. 			tx = x + dx;
  114. 			ty = y + dy;
  115. 			if (IN_BOUNDS(tx, ty)) {
  116. 				obst = obstacle_map[ty * N + tx] ==
  117. 					GRAVITY_WELL;
  118. 				if (obst) {
  119. 					return true;
  120. 				}
  121. 			}
  122. 		}
  123. 	}
  124.  
  125. 	return false;
  126. }
  127.  
  128. /* Pushes a node onto a stack with a given parent. */
  129. static void
  130. push_node(struct node **top, int x, int y, struct node *parent)
  131. {
  132. 	struct node *p = malloc(sizeof(*p));
  133. 	assert(p && "out of memory");
  134. 	p->x = x;
  135. 	p->y = y;
  136. 	p->prev = *top;
  137. 	p->parent = parent;
  138. 	*top = p;
  139. }
  140.  
  141. /* Pops a node from the stack. */
  142. static struct node *pop_node(struct node **top)
  143. {
  144. 	struct node *n = *top;
  145. 	if (*top) {
  146. 		*top = (*top)->prev;
  147. 	}
  148. 	return n;
  149. }
  150.  
  151. /* Clears the stack, freeing all the memory. */
  152. static void clear_stack(struct node *top)
  153. {
  154. 	struct node *tmp;
  155. 	while (top) {
  156. 		tmp = top;
  157. 		top = top->prev;
  158. 		free(tmp);
  159. 	}
  160. }
  161.  
  162. /* Adds all neighbors that can be checked to the stack. */
  163. static void enumerate_neighbors(struct node **top, struct node *n)
  164. {
  165. 	int dx;
  166. 	int dy;
  167. 	int tx;
  168. 	int ty;
  169. 	bool obst;
  170.  
  171. 	for (dy = -1; dy <= 1; ++dy) {
  172. 		for (dx = -1; dx <= 1; ++dx) {
  173. 			tx = n->x + dx;
  174. 			ty = n->y + dy;
  175. 			obst = is_obstructed(tx, ty);
  176. 			if (!obst && !visited[ty * N + tx]) {
  177. 				visited[ty * N + tx] = true;
  178. 				push_node(top, tx, ty, n);
  179. 			}
  180. 		}
  181. 	}
  182. }
  183.  
  184. /* Attempts to find a path, returns false if not found. */
  185. static bool find_path(void)
  186. {
  187. 	struct node *top = NULL;
  188. 	struct node *tofree = NULL;
  189. 	struct node *tmp;
  190. 	struct node *n;
  191. 	struct node *closest = NULL;
  192. 	int closest_dist = INT_MAX;
  193. 	int dist;
  194. 	bool found = false;
  195.  
  196. 	push_node(&top, START_X, START_Y, NULL);
  197. 	visited[START_Y * N + START_X] = true;
  198.  
  199. 	while ((tmp = pop_node(&top))) {
  200. 		n = tmp;
  201. 		/* Must save all nodes for finding our way back. We'll
  202. 		 * free them later by adding them to a stack.
  203. 		 */
  204. 		n->prev = tofree;
  205. 		tofree = n;
  206.  
  207. 		dist = distance_to_end(n->x, n->y);
  208. 		if (dist < closest_dist) {
  209. 			closest = n;
  210. 			closest_dist = dist;
  211. 		}
  212.  
  213. 		if (n->x == END_X && n->y == END_Y) {
  214. 			found = true;
  215. 			break;
  216. 		}
  217.  
  218. 		enumerate_neighbors(&top, n);
  219. 	}
  220.  
  221. 	/* Fill in path. */
  222. 	n = closest;
  223. 	while (n) {
  224. 		/* Skip start/end. */
  225. 		if (!path_map[n->y * N + n->x]) {
  226. 			path_map[n->y * N + n->x] = PATH;
  227. 		}
  228. 		n = n->parent;
  229. 	}
  230.  
  231. 	clear_stack(top);
  232. 	clear_stack(tofree);
  233. 	return found;
  234. }
  235.  
  236. /* Prints both maps, obstacle and path, to stdout. */
  237. static void print_maps(void)
  238. {
  239. 	int x;
  240. 	int y;
  241. 	enum obstacle obst;
  242. 	enum path path;
  243.  
  244. 	for (y = 0; y < N; ++y) {
  245. 		for (x = 0; x < N; ++x) {
  246. 			obst = obstacle_map[y * N + x];
  247. 			path = path_map[y * N + x];
  248.  
  249. 			if (obst == GRAVITY_WELL) {
  250. 				printf("G");
  251. 			} else if (obst == ASTEROID) {
  252. 				printf("A");
  253. 			} else if (path == PATH) {
  254. 				printf("O");
  255. 			} else if (path == START) {
  256. 				printf("S");
  257. 			} else if (path == END) {
  258. 				printf("E");
  259. 			} else {
  260. 				printf(".");
  261. 			}
  262. 		}
  263. 		printf("\n");
  264. 	}
  265. }
  266.  
  267. int main(void)
  268. {
  269. 	initialize();
  270. 	if (!find_path()) {
  271. 		printf("no complete path\n");
  272. 	}
  273.     print_maps();
  274. 	return 0;
  275. }
  276.  
  277.  
Success #stdin #stdout 0s 2380KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
no complete path
SA.AA..G..
.O..GAAGA.
..OA....AA
.OA.A..AA.
AOA.GAG.A.
.AO....AAA
.A...A..AA
A.GA...G..
GA.AG..GA.
.........E
https://ideone.com/1oPyzb
language:
C99 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!