#include <stdlib.h>

#include "line_of_sight.h"
#include "util.h"

// Bresenham's line drawing algorithm
// Based on pseudocode from Wikipedia
// https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

// Not perfect, but does a decent job of line of sight

static uint8_t plot_line_low(int x0, int y0, int x1, int y1, dungeon_t *d) {
	int dx = x1 - x0;
  int dy = y1 - y0;
  int yi = 1;
  if (dy < 0) {
    yi = -1;
    dy = -dy;
	}
  int D = 2*dy - dx;
  int y = y0;

	int x;
	for (x = x0; x != x1; x += sign(x1-x0)) {
    if (d->hardness[y][x]) return 0;
    if (D > 0) {
       y = y + yi;
       D = D - 2*dx;
		}
    D = D + 2*dy;
	}
	return 1;
}

static uint8_t plot_line_high(int x0, int y0, int x1, int y1, dungeon_t *d) {
  int dx = x1 - x0;
  int dy = y1 - y0;
  int xi = 1;
  if (dx < 0) {
    xi = -1;
    dx = -dx;
	}
	
  int D = 2*dx - dy;
  int x = x0;

	int y;
	for (y = y0; y != y1; y += sign(y1-y0)) {
    if (d->hardness[y][x]) return 0;
    if (D > 0) {
       x = x + xi;
       D = D - 2*dy;
		}
    D = D + 2*dx;
	}
	return 1;
}

static uint8_t test_line(int x0, int y0, int x1, int y1, dungeon_t *d) {
	int i;
	
	// Vertical line
	if (x0 == x1) {
		for (i = y0; i != y1; i += sign(y1-y0)) {
			if (d->hardness[i][x1]) return 0;
		}
		return 1;
	}

  if (abs(y1 - y0) < abs(x1 - x0)) {
    if (x0 > x1) {
      return plot_line_low(x1, y1, x0, y0, d);
		} else {
      return plot_line_low(x0, y0, x1, y1, d);
		}
	} else {
    if (y0 > y1) {
      return plot_line_high(x1, y1, x0, y0, d);
		} else {
      return plot_line_high(x0, y0, x1, y1, d);
		}
	}
	return 1;
}

void calc_line_of_sight(dungeon_t *d, uint8_t result[MAP_HEIGHT][MAP_WIDTH], int x, int y) {
	int i, j;
	for (i = 0; i < MAP_HEIGHT; i++) {
		for (j = 0; j < MAP_WIDTH; j++) {
			result[i][j] = 0;
		}
	}

	for (i = max(0, y-VIEW_DIST); i < min(MAP_HEIGHT, y+VIEW_DIST+1); i++) {
		for (j = max(0, x-VIEW_DIST); j <  min(MAP_WIDTH, x+VIEW_DIST+1); j++) {
			result[i][j] = test_line(j, i, x, y, d);
		}
	}
}