path: root/dartbot.c

#include "checkouts.h"

#include <math.h>
#include <ncurses.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

#define HORIZONTAL_STDEV 24
#define VERTICAL_STDEV 24

// board spec from WDF rules
#define WIRE_WIDTH 1.56
#define INNER_DIAMETER_BULL 12.7
#define INNER_DIAMETER_25 31.8
#define DOUBLE_OUTER_EDGE 170.0
#define TREBLE_OUTER_EDGE 107.4
#define DOUBLE_INSIDE_WIDTH 8.0
#define TREBLE_INSIDE_WIDTH 8.0

#define SEGMENT_MAX_LEN 5
// distance from centre to apex of outer wire
// must be ordered outwards from centre
#define FOREACH_RING(M) \
	M(BULL, INNER_DIAMETER_BULL/2 + WIRE_WIDTH/2) \
	M(25, INNER_DIAMETER_25/2 + WIRE_WIDTH/2) \
	M(SMALL, TREBLE_OUTER_EDGE - WIRE_WIDTH - TREBLE_INSIDE_WIDTH - \
		WIRE_WIDTH/2) \
	M(TREBLE, TREBLE_OUTER_EDGE - WIRE_WIDTH/2) \
	M(BIG, DOUBLE_OUTER_EDGE - WIRE_WIDTH - DOUBLE_INSIDE_WIDTH - \
		WIRE_WIDTH/2) \
	M(DOUBLE, DOUBLE_OUTER_EDGE - WIRE_WIDTH/2)
#define GEN_RING_ENUM(X, D) R_ ## X,
#define GEN_RING_STRING(X, D) #X,
#define GEN_RING_OUTER_DIST(X, D) D,

int SECTORS[] = { 20, 1, 18, 4, 13, 6, 10, 15, 2, 17, 3, 19, 7,
	16, 8, 11, 14, 9, 12, 5 };
#define NUM_SECTORS (sizeof(SECTORS) / sizeof(*SECTORS))
#define SECTOR_WIDTH (360.0 / NUM_SECTORS)
int SECTOR_INDS[NUM_SECTORS];
double SECTOR_ANGLES[NUM_SECTORS];
void init_sectors()
{
	for (size_t i = 0; i < NUM_SECTORS; ++i) {
		SECTOR_INDS[SECTORS[i]-1] = i;

		double angle = 90 - (i * SECTOR_WIDTH);
		if (angle < 0) angle += 360;
		SECTOR_ANGLES[i] = angle;
	}
}

enum ring {
	FOREACH_RING(GEN_RING_ENUM)
	R_OUT
};

char *RING_NAMES[] = {
	FOREACH_RING(GEN_RING_STRING)
	"OUT"
};

double OUTER_DISTS[] = {
	FOREACH_RING(GEN_RING_OUTER_DIST)
};

double CENTRE_DISTS[sizeof(OUTER_DISTS)/sizeof(*OUTER_DISTS)];
void init_centre_dists()
{
	CENTRE_DISTS[0] = 0;
	for (int i = R_25; i < R_OUT; ++i)
		CENTRE_DISTS[i] = (OUTER_DISTS[i] -
			((OUTER_DISTS[i] - OUTER_DISTS[i-1]) / 2));
}

struct ccoords {
	double x, y;
};

struct pcoords {
	double a, r;
};

struct segment {
	enum ring ring;
	int sector;
};

int get_sector(double angle)
{
	double shifted = angle - 90 - (SECTOR_WIDTH/2);
	return SECTORS[NUM_SECTORS - 1 -
		(int)((shifted - (360 * floor(shifted/360))) / SECTOR_WIDTH)];
}

enum ring get_ring(double radius)
{
	for (int i = R_BULL; i < R_OUT; ++i)
		if (radius < OUTER_DISTS[i])
			return i;

	return R_OUT;
}

double drand()
{
	return (double)rand() / RAND_MAX;
}

double gauss(double mean, double stdev)
{
	static bool have_next;
	static double next;

	double curr;

	if (have_next) {
		curr = next;
	} else {
		double theta = 2 * M_PI * drand();
		double r = sqrt(-2 * log(1 - drand()));

		curr = r * cos(theta);
		next = r * sin(theta);
	}

	have_next = !have_next;
	return mean + (curr * stdev);
}

struct ccoords get_offset()
{
	return (struct ccoords){ .x = gauss(0, HORIZONTAL_STDEV),
		.y = gauss(0, VERTICAL_STDEV) };
}

struct ccoords pol_to_cart(struct pcoords c)
{
	double t = c.a * (M_PI / 180);
	double x = c.r * cos(t);
	double y = c.r * sin(t);

	return (struct ccoords){ .x = x, .y = y };
}

struct pcoords cart_to_pol(struct ccoords c)
{
	double a = atan2(c.y, c.x) * (180 / M_PI);
	double r = sqrt(pow(c.x, 2) + pow(c.y, 2));

	return (struct pcoords){ .a = a, .r = r };
}

struct pcoords throw_dart(struct pcoords target)
{
	struct ccoords cc = pol_to_cart(target);
	struct ccoords offset = get_offset();

	return cart_to_pol((struct ccoords){ .x = cc.x + offset.x,
		.y = cc.y + offset.y });
}

struct segment get_segment(struct pcoords c)
{
	return (struct segment){ .sector = get_sector(c.a),
		.ring = get_ring(c.r) };
}

char *segment_name(struct segment seg)
{
	char *str = malloc(SEGMENT_MAX_LEN);

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wstringop-truncation"
	if (seg.ring == R_BULL || seg.ring == R_25 || seg.ring == R_OUT)
		strncpy(str, RING_NAMES[seg.ring], SEGMENT_MAX_LEN);
	else
		snprintf(str, SEGMENT_MAX_LEN,
			(seg.ring == R_TREBLE ? "T%d" :
				(seg.ring == R_DOUBLE ? "D%d" : "%d")),
			seg.sector);
#pragma GCC diagnostic pop

	return str;
}

int segment_points(struct segment seg)
{
	if (seg.ring == R_BULL)
		return 50;
	else if (seg.ring == R_25)
		return 25;
	else if (seg.ring == R_TREBLE)
		return 3 * seg.sector;
	else if (seg.ring == R_DOUBLE)
		return 2 * seg.sector;
	else if (seg.ring == R_SMALL || seg.ring == R_BIG)
		return seg.sector;
	return 0;
}

bool segment_is_double(struct segment seg)
{
	if (seg.ring == R_DOUBLE || seg.ring == R_BULL)
		return true;
	return false;
}

struct pcoords segment_centre(struct segment seg)
{
	return (struct pcoords){ .a = SECTOR_ANGLES[SECTOR_INDS[seg.sector-1]],
		.r = CENTRE_DISTS[seg.ring] };
}

struct segment segment_from_name(char *name)
{
	int s = 20;
	enum ring r;

	if (!strcmp(name, "BULL")) {
		r = R_BULL;
	} else if (!strcmp(name, "25")) {
		r = R_25;
	} else if (name[0] == 'T') {
		r = R_TREBLE;
		s = atoi(name+1);
	} else if (name[0] == 'D') {
		r = R_DOUBLE;
		s = atoi(name+1);
	} else {
		r = R_BIG;
		s = atoi(name);
	}

	return (struct segment){ .sector = s, .ring = r };
}

struct segment next_dart(int rem, int darts_in_hand)
{
	char *c = NULL;
	if (rem <= 170)
		c = CHECKOUTS[darts_in_hand-1][rem-1];
	if (!c) c = "T20";

	return segment_from_name(c);
}

struct visit {
	int points;
	int rem;
	int n_darts;
	struct segment *darts;
};

struct leg {
	int start;
	int rem;
	int n_visits;
	struct visit *visits;
};

struct leg *leg_init(int points)
{
	struct leg *l = calloc(1, sizeof(*l));
	l->start = l->rem = points;
	l->visits = calloc(1000, sizeof(*(l->visits))); // FIXME

	return l;
}

void leg_free(struct leg *l)
{
	for (int i = 0; i < l->n_visits; ++i)
		free(l->visits[i].darts);
	free(l->visits);
	free(l);
}

void test_visit(struct leg *l)
{
	struct visit *v = l->visits + l->n_visits++;
	v->darts = calloc(3, sizeof(*(v->darts)));

	for (int i = 0; i < 3; ++i) {
		struct segment ts = next_dart(l->rem - v->points, 3 - i);
		struct pcoords tc = segment_centre(ts);
		struct pcoords dc = throw_dart(tc);
		struct segment ds = get_segment(dc);

		v->darts[v->n_darts++] = ds;
		v->points += segment_points(ds);

		if (l->rem - v->points == 0 && segment_is_double(ds))
			break;

		if (l->rem - v->points <= 1) {
			v->points = 0;
			break;
		}
	}

	l->rem -= v->points;
	v->rem = l->rem;
}

void test_match(int start_points)
{
	struct leg *l = leg_init(start_points);

	while(l->rem > 0)
		test_visit(l);

	printf("(%2d)       %3d\n", l->n_visits, l->start);
	for(int i = 0; i < l->n_visits; ++i) {
		struct visit *v = l->visits + i;
		printf("(%2d)  %3d  %3d", i+1, v->points, v->rem);

		for (int j = 0; j < v->n_darts; ++j) {
			char *n = segment_name(v->darts[j]);
			printf(j == 0 ? "  %4s" :" %4s", n);
			free(n);
		}
		printf("\n");
	}

	leg_free(l);
}

void draw(WINDOW *w, struct leg *l)
{
	werase(w);
	box(w, 0, 0);
	wmove(w, 0, 2);
	waddstr(w, "dartbot");

	char buf[100];
	int buflen = 0;

	int offset = 2;
	int start_visit = (LINES - 3 > l->n_visits) ? 0 : (l->n_visits - (LINES - 3));
	if (start_visit == 0 && LINES - 3 > l->n_visits) {
		wmove(w, (offset++)-start_visit, 2);
		sprintf(buf, "(%2d)       %3d", 0, l->start);
		waddstr(w, buf);
	}

	for (int i = start_visit; i < l->n_visits; ++i) {
		wmove(w, offset+i-start_visit, 2);
		struct visit *v = l->visits + i;

		buflen += sprintf(buf, "(%2d)  %3d  %3d", i+1, v->points, v->rem);

		for (int j = 0; j < v->n_darts; ++j) {
			char *n = segment_name(v->darts[j]);
			buflen += sprintf(buf + buflen, j == 0 ? "  %4s" :" %4s", n);
			free(n);
		}

		buflen = 0;
		waddstr(w, buf);
	}

	wrefresh(w);
}

void test_curses_match(int start_points)
{
	initscr();
	curs_set(0);
	noecho();

	WINDOW *w = newwin(LINES, COLS, 0, 0);

	struct leg *l = leg_init(start_points);

	draw(w, l);

	while (l->rem > 0) {
		test_visit(l);

		usleep(250000);
		draw(w, l);
	}

	leg_free(l);
	wgetch(w);
	delwin(w);
	endwin();
}

void init_colours()
{
	init_pair(1, 82, 0); // 140
	init_pair(2, 154, 0); // 100
	init_pair(3, 226, 0); // 60
	init_pair(4, 214, 0); // 40
	init_pair(5, 202, 0); // 20
	init_pair(6, 196, 0); // 0
	init_pair(7, 235, 0); // darts
	init_pair(8, 244, 0); // visit
}

int points_colour(int points)
{
	if (points >= 180)
		return COLOR_PAIR(1) | A_BOLD;
	else if (points >= 140)
		return COLOR_PAIR(1);
	else if (points >= 100)
		return COLOR_PAIR(2);
	else if (points >= 60)
		return COLOR_PAIR(3);
	else if (points >= 40)
		return COLOR_PAIR(4);
	else if (points >= 20)
		return COLOR_PAIR(5);
	else if (points > 0)
		return COLOR_PAIR(6);
	else
		return COLOR_PAIR(6) | A_BOLD;
}

void flushbuf(WINDOW *w, char *buf, int *buflen, int col)
{
	if (!(*buflen)) return;

	if (col) wattron(w, col);
	waddstr(w, buf);
	if (col) wattroff(w, col);

	*buflen = 0;
}

void draw2(WINDOW *w, struct leg *l1, struct leg *l2)
{
	werase(w);
	box(w, 0, 0);
	wmove(w, 0, 2);
	waddstr(w, "dartbot");

	char buf[100];
	int buflen = 0;

	int n_visits = l1->n_visits > l2->n_visits ? l1->n_visits : l2->n_visits;

	int offset = 2;
	int start_visit = (LINES - 3 > n_visits) ? 0 : (n_visits - (LINES - 3));
	if (start_visit == 0 && LINES - 3 > n_visits) {
		wmove(w, (offset++)-start_visit, 2);
		buflen = sprintf(buf, "(%2d)", 0);
		flushbuf(w, buf, &buflen, COLOR_PAIR(8));
		buflen = sprintf(buf, "       %3d  %3d", l1->start, l2->start);
		flushbuf(w, buf, &buflen, 0);
	}

	for (int i = start_visit; i < n_visits; ++i) {
		wmove(w, offset+i-start_visit, 2);
		buflen += sprintf(buf + buflen, "(%2d)", i+1);
		flushbuf(w, buf, &buflen, COLOR_PAIR(8));
		buflen += sprintf(buf + buflen, "  ");
		flushbuf(w, buf, &buflen, 0);

		struct visit *v = l1->visits + i;

		flushbuf(w, buf, &buflen, 0);
		buflen += sprintf(buf + buflen, "%3d", v->points);
		flushbuf(w, buf, &buflen, points_colour(v->points));

		buflen += sprintf(buf + buflen, "  %3d", v->rem);

		if (i < l2->n_visits) {
			v = l2->visits + i;

			buflen += sprintf(buf + buflen, "  %3d  ", v->rem);

			flushbuf(w, buf, &buflen, 0);
			buflen += sprintf(buf + buflen, "%3d", v->points);
			flushbuf(w, buf, &buflen, points_colour(v->points));

			for (int j = 0; j < v->n_darts; ++j) {
				char *n = segment_name(v->darts[j]);
				buflen += sprintf(buf + buflen, j == 0 ? "  %4s" :" %4s", n);
				free(n);
			}
			flushbuf(w, buf, &buflen, COLOR_PAIR(7));
		}

		flushbuf(w, buf, &buflen, 0);
	}

	wrefresh(w);
}

void test_curses_match2(int start_points)
{
	initscr();
	start_color();
	init_colours();
	curs_set(0);
	noecho();

	WINDOW *w = newwin(LINES, COLS, 0, 0);

	struct leg *l1 = leg_init(start_points);
	struct leg *l2 = leg_init(start_points);

	draw2(w, l1, l2);

	while (l1->rem > 0 && l2->rem > 0) {
		test_visit(l1);
		if (l1->rem > 0)
			test_visit(l2);

		usleep(250000);
		draw2(w, l1, l2);
	}

	leg_free(l1);
	leg_free(l2);
	wgetch(w);
	delwin(w);
	endwin();
}

int main()
{
	srand(time(NULL));
	init_sectors();
	init_centre_dists();

	//test_curses_match(501);
	test_curses_match2(501);
	test_match(501);

	return 0;
}