#include <vectrex.h>
// Suggestion from J.Riddle: lightpen support and sound effects.
// (maybe a tune that rises in tempo as more crossings are removed?)
#define int8_t int
#define uint8_t unsigned int
#define int16_t long
#define int32_t long long
#ifndef TRUE
#define TRUE (0==0)
#define FALSE (0!=0)
#endif
#define NULL 0
static unsigned int dotmask = 0xC3;
#define DRAWING_SCALE 0x80
#define CROSSHAIR_SCALE 0x40
#define set_scale(s) do { VIA_t1_cnt_lo = s; } while (0)
#define BRIGHT TRUE
#define normal FALSE
static unsigned char patList[2];
static void drawline_patterned(int y, int x, unsigned char pat)
{
patList[0]=(unsigned char)y;
patList[1]=(unsigned char)x;
*(volatile unsigned char *)0xC829 = pat;
*(volatile unsigned char *)0xC823 =0;
Draw_Pat_VL(patList);
}
static int last_intensity = -128;
static void drawline(unsigned int x1, unsigned int y1, unsigned int x2, unsigned int y2, int bright, int dashed) {
long ax1, ay1, dx, dy;
if (bright) {
if (last_intensity != BRIGHT) Intensity_7F();
} else {
if (last_intensity != normal) Intensity_3F();
}
last_intensity = bright;
Reset0Ref(); set_scale(DRAWING_SCALE);
ax1 = ((long)x1-128L); ay1 = ((long)y1-128L);
dx = ((long)x2-(long)x1); dy = ((long)y2-(long)y1);
Moveto_d((int)ay1,(int)ax1);
// id dx is 255, it splits into 127 and 128 - which causes a problem because +128 is not possible
if (dy == 255 || dx == 255) {
// 255-unit long lines are split in three, all others are split in two.
drawline_patterned((int)(dy/3L), (int)(dx/3L), (dashed ? dotmask : 0xFF));
dy -= dy/3L; dx -= dx/3L;
}
if (dy < -128L || dy > 127L || dx < -128L || dx > 127L) {
drawline_patterned((int)(dy>>1L), (int)(dx>>1L), (dashed ? dotmask : 0xFF));
// don't care which way it rounds (>>1 or /2) because this picks up the odd bit:
dy -= dy>>1L; dx -= dx>>1L;
}
drawline_patterned((int)dy, (int)dx, (dashed ? dotmask : 0xFF));
}
static char *mystrdup(const char *s) {
// to ensure writable strings in 'assign' procedure
// No heap on vectrex, so this is a little hacky.
// Fortunately I know we never have more than
// one 'heap' string at a time...
static char copy[255U], *t; // has to be large enough for biggest problem string in layouts.h
unsigned int len;
t = copy; len = 0;
do {
len += 1;
if (len == 255) {
for (;;) ; // halt.
}
*t++ = *s++;
} while (*s != '\0');
*t = '\0';
return copy;
}
static char *mystrchr(char *s, char ch) {
if (!s) return NULL;
for (;;) {
if (*s == '\0') return NULL;
if (*s == ch) return s;
s += 1;
}
}
static int atoui(const char *s) { // we know all inputs are unsigned
int i = 0, c;
if (!s) return i;
for (;;) {
if (*s == '\0') return i;
c = (int)*s++;
if (c < '0') break;
if (c > '9') break;
c = c - '0';
i = i * 10 + c;
}
return i;
}
static uint8_t _x, _a, _b, _c;
static void initRandom(unsigned int s1,unsigned int s2,unsigned int s3, unsigned int x0) {
_x = x0; _a = s1; _b = s2; _c = s3; _x++; _a = (_a^_c^_x); _b = (_b+_a); _c = ((_c+(_b>>1))^_a);
}
static uint8_t random8(void) { // assert returns unsigned value that fits in an int.
_x++; _a = (_a^_c^_x); _b = (_b+_a); _c = ((_c+(_b>>1))^_a);
return _c;
}
// mouse clicks will select a node only if they are within N units of the node.
// (comparing square of the distance to avoid sqrt() overhead)
#define SLOP_RADIUS 32
#define MAX_CLICK_DISTANCE ((long)SLOP_RADIUS*(long)SLOP_RADIUS)
// under no circumstances greater than 31.
#define MAX_NODES 11 // was (20-5+1)*100 but ran out of ram, so now (11-8+1)*64!
#include "layouts.h" // levels 8 - 11, 64 per level
typedef struct node {
unsigned int x, y; // on-screen coordinate in 0..255 range. Corrected to -128.127 only on final display.
int links; // count of links to neighbours (2,3,4)
int link[4]; // links to up to 4 neighbours
// int intersects[4];
} node;
typedef struct graph {
int nodes;
node node[MAX_NODES];
} graph;
#define FROM 0
#define TO 1
typedef struct lines { // faster to have a flat array of lines (node pairs), for checking intersections
int node[2]; // from and to
int intersects;
} lines;
static int max_line;
static lines line[MAX_NODES*4];
/* lines_intersect: AUTHOR: Mukesh Prasad, from Graphics Gems II
*
* This function computes whether two line segments,
* respectively joining the input points (x1,y1) -- (x2,y2)
* and the input points (x3,y3) -- (x4,y4) intersect.
* If the lines intersect, the output variables x, y are
* set to coordinates of the point of intersection.
*
* All values are in integers. The returned value is rounded
* to the nearest integer point.
*
* If non-integral grid points are relevant, the function
* can easily be transformed by substituting floating point
* calculations instead of integer calculations.
*
* Entry
* x1, y1, x2, y2 Coordinates of endpoints of one segment.
* x3, y3, x4, y4 Coordinates of endpoints of other segment.
*
* Exit
* x, y Coordinates of intersection point.
*
* The value returned by the function is one of:
*
* DONT_INTERSECT 0
* DO_INTERSECT 1
* COLLINEAR 2
*
* Error conditions:
*
* Depending upon the possible ranges, and particularly on 16-bit
* computers, care should be taken to protect from overflow.
*
* In the following code, 'long' values have been used for this
* purpose, instead of 'int'.
*
*/
// I (gt) believe I have modified this correctly for gcc6809's "-mint8" environment,
// but the end of the game is not being detected which would imply that this call
// is failing. Looks like a job for the debugger...
#define DONT_INTERSECT 0
#define DO_INTERSECT 1
#define COLLINEAR 2
/**************************************************************
* *
* NOTE: The following macro to determine if two numbers *
* have the same sign, is for 2's complement number *
* representation. It will need to be modified for other *
* number systems. *
* *
**************************************************************/
static int lines_intersect(int16_t x1, int16_t y1, /* First line segment */
int16_t x2, int16_t y2,
int16_t x3, int16_t y3, /* Second line segment */
int16_t x4, int16_t y4) {
int16_t b1, b2;
int32_t a1, a2, c1, c2; /* Coefficients of line eqns. */
int32_t r1, r2, r3, r4; /* 'Sign' values */
int32_t denom; /* Intermediate values */
if (
(x1 == x3 && y1 == y3) || ( x1 == x4 && y1 == y4) ||
(x2 == x3 && y2 == y3) || ( x2 == x4 && y2 == y4)
) {
//
// This isn't the whole story - the lines could be completely co-incident,
// in which case the equation of the line (ax + by + c = 0) will be the same
// for both lines, but be careful when adding that test as I think that all
// the coefficients in the equation may be scaled, for instance the second
// line might come out as 2ax + 2by + 2c = 0
//
// I'm not sure if 'COLLINEAR' above means parallel or coincident - I
// think it means parallel but if c is the same for both lines then coincident.
//
return DONT_INTERSECT; // end-points are coincident
}
// no apparent change in cycles regardless of which macro is used:
//#define SAME_SIGNS( a, b ) (((a)^(b)) >= 0)
#define SAME_SIGNS( a, b ) ((((a)<0) && ((b)<0)) || (((a)>=0) && ((b)>=0)))
/* Compute a1, b1, c1, where line joining points 1 and 2
* is "a1 x + b1 y + c1 = 0".
*/
a1 = y2 - y1; //debug_int32(120, -120, "A1", a1);
b1 = x1 - x2; //debug_int16(108, -120, "B1", b1);
c1 = (int32_t)x2 * (int32_t)y1 - (int32_t)x1 * (int32_t)y2; //debug_int32( 96, -120, "C1", c1);
/* Compute r3 and r4. */
r3 = ((int32_t)a1 * (int32_t)x3) + ((int32_t)b1 * (int32_t)y3) + (int32_t)c1; //debug_int32( 84, -120, "R3", r3);
r4 = ((int32_t)a1 * (int32_t)x4) + ((int32_t)b1 * (int32_t)y4) + (int32_t)c1; //debug_int32( 72, -120, "R4", r4);
/* Check signs of r3 and r4. If both point 3 and point 4 lie on
* same side of line 1, the line segments do not intersect.
*/
if ( r3 != 0 &&
r4 != 0 &&
SAME_SIGNS( r3, r4 ))
return ( DONT_INTERSECT );
/* Compute a2, b2, c2 */
a2 = y4 - y3; //debug_int32( 64, -120, "A2", a2);
b2 = x3 - x4; //debug_int16( 52, -120, "B2", b2);
c2 = (int32_t)x4 * (int32_t)y3 - (int32_t)x3 * (int32_t)y4; //debug_int32( 40, -120, "C2", c2);
/* Compute r1 and r2 */
r1 = (a2 * (int32_t)x1) + ((int32_t)b2 * (int32_t)y1) + (int32_t)c2; //debug_int32( 28, -120, "R1", r1);
r2 = (a2 * (int32_t)x2) + ((int32_t)b2 * (int32_t)y2) + (int32_t)c2; //debug_int32( 16, -120, "R2", r2);
/* Check signs of r1 and r2. If both point 1 and point 2 lie
* on same side of second line segment, the line segments do
* not intersect.
*/
if ( r1 != 0 &&
r2 != 0 &&
SAME_SIGNS( r1, r2 ))
return ( DONT_INTERSECT );
/* Line segments intersect: compute intersection point. */
denom = a1 * b2 - a2 * b1;
if ( denom == 0 )
return ( COLLINEAR );
return ( DO_INTERSECT ); /* lines_intersect */
#undef SAME_SIGNS
}
static void extract_lines(graph *g) {
// for graph drawing etc it is more convenient to have all the lines in one linear array
int node, link;
max_line = 0;
for (node = 0; node < g->nodes; node++) {
// each node has between 2 and 4 arcs to other nodes
for (link = 0; link < g->node[node].links; link++) {
line[max_line].node[FROM] = node;
line[max_line].node[TO] = g->node[node].link[link];
line[max_line].intersects = FALSE; // set to true by intersection scanner
max_line += 1; if (max_line == 127) { for (;;) ; }
}
}
}
static unsigned int compute_intersections(graph *g, lines *line) {
// precompute (N^2)/2 intersections - compare every line to every other.
// hopefully while dragging we can avoid N^2 comparisons and only update
// those pairs where one end of the line is our dragged node. However
// will do that later only if needed for speed. For now, brute force it...
int this_line, that_line;
unsigned int count;
count = 0;
// initialise all intersections to false
for (this_line = 0; this_line < max_line; this_line++) line[this_line].intersects = FALSE;
#ifndef NSQUARED
for (this_line = 0; this_line < max_line-1; this_line++) {
for (that_line = this_line+1; that_line < max_line; that_line++) {
if (lines_intersect(
#else
// testing a full N^2 set of comparisons to see if strange results were caused
// by mistake in optimisation, but results were the same. Just took more cycles.
for (this_line = 0; this_line < max_line; this_line++) {
for (that_line = 0; that_line < max_line; that_line++) {
if ((this_line != that_line) && lines_intersect(
#endif
g->node[line[this_line].node[FROM]].x, g->node[line[this_line].node[FROM]].y,
g->node[line[this_line].node[TO]].x, g->node[line[this_line].node[TO]].y,
g->node[line[that_line].node[FROM]].x, g->node[line[that_line].node[FROM]].y,
g->node[line[that_line].node[TO]].x, g->node[line[that_line].node[TO]].y
) == DO_INTERSECT) {
// when we find an intersection, mark *both* lines
line[this_line].intersects = TRUE;
line[that_line].intersects = TRUE;
count += 1; // used to determine end of game
}
}
}
return count; // as long as there are not 256 intersections :-)
}
static void draw_graph(graph *g, int selected_node) {
int lineno;
for (lineno = 0; lineno < max_line; lineno++) {
drawline(g->node[line[lineno].node[FROM]].x, g->node[line[lineno].node[FROM]].y,
g->node[line[lineno].node[TO]].x, g->node[line[lineno].node[TO]].y,
(line[lineno].node[FROM] == selected_node || line[lineno].node[TO] == selected_node) ? BRIGHT : normal,
line[lineno].intersects);
}
}
static void assign(graph *g, const char *init) {
// take a string generated by Simon Tatham's program, representing
// a good planar graph, and convert it to a data structure
int node, i, j, links;
char *f, *s, *p;
f = s = mystrdup(init);
p = mystrchr(s, ':'); *p = '\0';
g->nodes = atoui(s); s = p+1;
node = 0; links = 0;
for (;;) {
p = mystrchr(s, '-'); *p = '\0'; i = atoui(s); s = p+1;
if (i != node) {
links = 0;
for (node = node+1; node <= i; node++) g->node[node].links = 0;
node = i;
}
p = mystrchr(s, ',');
if (p) *p = '\0';
j = atoui(s);
g->node[i].link[links] = j;
links += 1;
g->node[i].links = links;
if (p) s = p+1; else break;
}
for (i = i+1; i <= g->nodes; i++) g->node[i].links = 0;
}
static unsigned long long dist(unsigned int x1, unsigned int y1, unsigned int x2, unsigned int y2) {
// compute and compare dist squared rather than true dist to avoid isqrt call.
// probably just adding x and y (manhattan distance) would have been good enough
unsigned int dx, dy;
unsigned long dx2, dy2;
unsigned long long result;
if (x2>x1) dx = x2 - x1; else dx = x1 - x2;
if (y2>y1) dy = y2 - y1; else dy = y1 - y2;
dx2 = (unsigned long)dx*(unsigned long)dx; dy2 = (unsigned long)dy*(unsigned long)dy; // now in range 0..65535 :-(
result = (unsigned long long)dx2+(unsigned long long)dy2;
return result;
}
static int find_nearest_node(graph *g, unsigned int x, unsigned int y) { // x,y on 0..255 space
// compare dist from cursor to every node
int node, best_node;
unsigned long long dist2, best_dist = ((unsigned long long) -1LL) >> 1ULL;
for (node = 0; node < g->nodes; node++) {
dist2 = dist(x,y, g->node[node].x, g->node[node].y);
if (dist2 < best_dist) {
best_dist = dist2; best_node = node;
}
}
return (best_dist < (unsigned long long)MAX_CLICK_DISTANCE) ? best_node : -1;
}
int main(void) {
graph g;
int node;
int dragged_node = -1;
unsigned int crossings; // how many crossings are there? We only really care if 0 or non-0...
int index;
unsigned int mouse_x, mouse_y;
int mouse_down, mouse_was_down;
volatile unsigned int *rand = (volatile unsigned int *)0xc87b;
volatile unsigned int *timer_lo = (volatile unsigned int *)0xD004;
// unfortunately, on emulator at least, very first random is always the same
// maybe ask Malban to add some randomicity to initial hardware timer?
initRandom(rand[0],rand[1],rand[2],*timer_lo);
Vec_Joy_Mux_1_X = 1; // enable analog joystick mode
Vec_Joy_Mux_1_Y = 3;
// index = (int)(random8()&3); // current levels 8 through 11 inclusive
index = 3; // for now forcing 11-node levels
// pick a random problem
assign(&g, layout[(unsigned long)index*64UL+((unsigned long)random8()&63UL)]); // 64 solutions per level
// Now lay the graph out as a tangle; later, a circular tangle:
// rather than compute the starting positions on the fly (and
// require sin and cos) we can just keep a pre-computed array
// of x,y for circles of 5..20 elements.
for (node = 0; node < g.nodes; node++) {
g.node[node].x = random8();
g.node[node].y = random8();
}
extract_lines(&g); // speeds up various things.
crossings = compute_intersections(&g, line); // initial state.
mouse_was_down = FALSE; mouse_down = FALSE;
for (;;) {
Wait_Recal();
*(volatile int *)0xC81A = 0; // maximum analog resolution
Joy_Analog();
mouse_x = (unsigned int)(((long)Vec_Joy_1_X+128L)); // -128:127 maps to 0:255
mouse_y = (unsigned int)(((long)Vec_Joy_1_Y+128L)); // but scaled down to preserve margins
Reset0Ref(); set_scale(DRAWING_SCALE); Intensity_7F();
// draw a cursor at the joystick coordinates
Moveto_d((int)((long)mouse_y-128L), (int)((long)mouse_x-128L)); // back to screen coordinates
set_scale(CROSSHAIR_SCALE);
Moveto_d(-10,-10); Draw_Line_d(20,20); Moveto_d(-10,-10);
Moveto_d(10,-10); Draw_Line_d(-20,20); Moveto_d(10,-10);
// and back to the start again
Read_Btns();
mouse_down = ((Vec_Btn_State & 8) != 0);
Reset0Ref(); set_scale(DRAWING_SCALE); Intensity_7F(); last_intensity = -128;
if (mouse_down && !mouse_was_down) {
// this was a click
dragged_node = find_nearest_node(&g, mouse_x, mouse_y);
if (dragged_node >= 0) {
g.node[dragged_node].x = mouse_x;
g.node[dragged_node].y = mouse_y;
//compute_intersections(&g, line); // too expensive while dragging although
// visual feedback would have been nice.
// Perhaps later just compute intersections
// for the arcs exiting the dragged node (max 4)
}
} else if (mouse_down) {
// this is a continuing drag
if (dragged_node >= 0) {
g.node[dragged_node].x = mouse_x;
g.node[dragged_node].y = mouse_y;
}
} else if (mouse_was_down) { // (but is no longer...)
// end of drag - drop now.
if (dragged_node >= 0) {
crossings = compute_intersections(&g, line); // and update display/detect completion
}
dragged_node = -1;
} else {
// no change, just redraw
}
mouse_was_down = mouse_down;
draw_graph(&g, dragged_node);
// if no intersections, put up a "YOU WIN!" and a time taken.
if ((crossings == 0) || ((Vec_Btn_State & 3 /* force new game? */)==3)) {
Reset0Ref(); set_scale(DRAWING_SCALE); Intensity_5F(); last_intensity = -128;
Print_Str_d(0, -20, "YOU WIN!\x80");
if (Vec_Btn_State & 1) {
// this section is cut & pasted from above. Need to make into a procedure...
// index = (int)(random()&3); // current levels 8 through 11 inclusive
index = 3; // force level 11 for now (64 variants)
assign(&g, layout[(unsigned long)index*64UL+((unsigned long)random8()&63UL)]); // 64 solutions per level
// Now lay the graph out as a tangle; later, a circular tangle:
// rather than compute the starting positions on the fly (and
// require sin and cos) we can just keep a pre-computed array
// of x,y for circles of 5..20 elements.
for (node = 0; node < g.nodes; node++) {
g.node[node].x = random8();
g.node[node].y = random8();
}
extract_lines(&g);
crossings = compute_intersections(&g, line);
mouse_was_down = FALSE; mouse_down = FALSE;
}
}
dotmask = (dotmask << 1) | (dotmask>>7);
}
return 0;
}