#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10
#define GRAVITY_WELL_CHANCE 0.1
#define ASTEROID_CHANCE 0.3

#define START_X 0
#define START_Y 0
#define END_X 9
#define END_Y 9

#define IN_BOUNDS(x, y) ((x) >= 0 && (x) < N && (y) >= 0 && (y) < N)
#define SQ(x) ((x) * (x))

enum obstacle {
	NO_OBSTACLE,
	GRAVITY_WELL,
	ASTEROID,
};

enum path {
	NO_PATH,
	PATH,
	START,
	END,
};

/* A node during path finding. */
struct node {
	int x;
	int y;
	struct node *prev;
	struct node *parent;
};

static enum obstacle obstacle_map[N * N];
static enum path path_map[N * N];
static bool visited[N * N];

/* Places an obstacle at a random free spot. */
static void place_at_random_spot(enum obstacle obst)
{
	int x;
	int y;
	int at_start;
	int at_end;
	
	do {
		x = rand() % N;
		y = rand() % N;
		at_start = x == START_X && y == START_Y;
		at_end = y == END_X && y == END_Y;
	} while (at_start || at_end || obstacle_map[y * N + x]);

	obstacle_map[y * N + x] = obst;
}

/* Calculates distance. No need to sqrt. */
static int distance_to_end(int x, int y)
{
	return SQ(x - END_X) + SQ(y - END_Y);
}

/* Initialized the obstacle_map with random data. */
static void initialize(void)
{
	int well_count = ((int)N * N * GRAVITY_WELL_CHANCE);
	int asteroid_count = ((int)N * N * ASTEROID_CHANCE);
	unsigned int seed = time(NULL);

	srand(seed);

	while (well_count-- > 0) {
		place_at_random_spot(GRAVITY_WELL);
	}

	while (asteroid_count-- > 0) {
		place_at_random_spot(ASTEROID);
	}

	path_map[START_Y * N + START_X] = START;
	path_map[END_Y * N + END_X] = END;
}

/* Returns true if the spot is safe. A square is safe if it is inside
 * the map, isn't on an asteroid, and isn't near a gravity well.
 */
static bool is_obstructed(int x, int y)
{
	int dx;
	int dy;
	int tx;
	int ty;
	bool obst;

	if (!IN_BOUNDS(x, y)) {
		return true;
	}

	if (obstacle_map[y * N + x] == ASTEROID) {
		return true;
	}

	for (dy = -1; dy <= 1; ++dy) {
		for (dx = -1; dx <= 1; ++dx) {
			tx = x + dx;
			ty = y + dy;
			if (IN_BOUNDS(tx, ty)) {
				obst = obstacle_map[ty * N + tx] ==
					GRAVITY_WELL;
				if (obst) {
					return true;
				}
			}
		}
	}

	return false;
}

/* Pushes a node onto a stack with a given parent. */
static void
push_node(struct node **top, int x, int y, struct node *parent)
{
	struct node *p = malloc(sizeof(*p));
	assert(p && "out of memory");
	p->x = x;
	p->y = y;
	p->prev = *top;
	p->parent = parent;
	*top = p;
}

/* Pops a node from the stack. */
static struct node *pop_node(struct node **top)
{
	struct node *n = *top;
	if (*top) {
		*top = (*top)->prev;
	}
	return n;
}

/* Clears the stack, freeing all the memory. */
static void clear_stack(struct node *top)
{
	struct node *tmp;
	while (top) {
		tmp = top;
		top = top->prev;
		free(tmp);
	}
}

/* Adds all neighbors that can be checked to the stack. */
static void enumerate_neighbors(struct node **top, struct node *n)
{
	int dx;
	int dy;
	int tx;
	int ty;
	bool obst;

	for (dy = -1; dy <= 1; ++dy) {
		for (dx = -1; dx <= 1; ++dx) {
			tx = n->x + dx;
			ty = n->y + dy;
			obst = is_obstructed(tx, ty);
			if (!obst && !visited[ty * N + tx]) {
				visited[ty * N + tx] = true;
				push_node(top, tx, ty, n);
			}
		}
	}
}

/* Attempts to find a path, returns false if not found. */
static bool find_path(void)
{
	struct node *top = NULL;
	struct node *tofree = NULL;
	struct node *tmp;
	struct node *n;
	struct node *closest = NULL;
	int closest_dist = INT_MAX;
	int dist;
	bool found = false;

	push_node(&top, START_X, START_Y, NULL);
	visited[START_Y * N + START_X] = true;

	while ((tmp = pop_node(&top))) {
		n = tmp;
		/* Must save all nodes for finding our way back. We'll
		 * free them later by adding them to a stack.
		 */
		n->prev = tofree;
		tofree = n;

		dist = distance_to_end(n->x, n->y);
		if (dist < closest_dist) {
			closest = n;
			closest_dist = dist;
		}

		if (n->x == END_X && n->y == END_Y) {
			found = true;
			break;
		}

		enumerate_neighbors(&top, n);
	}

	/* Fill in path. */
	n = closest;
	while (n) {
		/* Skip start/end. */
		if (!path_map[n->y * N + n->x]) {
			path_map[n->y * N + n->x] = PATH;
		}
		n = n->parent;
	}

	clear_stack(top);
	clear_stack(tofree);
	return found;
}

/* Prints both maps, obstacle and path, to stdout. */
static void print_maps(void)
{
	int x;
	int y;
	enum obstacle obst;
	enum path path;

	for (y = 0; y < N; ++y) {
		for (x = 0; x < N; ++x) {
			obst = obstacle_map[y * N + x];
			path = path_map[y * N + x];

			if (obst == GRAVITY_WELL) {
				printf("G");
			} else if (obst == ASTEROID) {
				printf("A");
			} else if (path == PATH) {
				printf("O");
			} else if (path == START) {
				printf("S");
			} else if (path == END) {
				printf("E");
			} else {
				printf(".");
			}
		}
		printf("\n");
	}
}

int main(void)
{
	initialize();
	if (!find_path()) {
		printf("no complete path\n");
	}
    print_maps();
	return 0;
}