Knight's tour/C: Difference between revisions
m (→OpenGL: add {{libheader|GLUT}}) |
(→OpenGL: double buffer) |
||
Line 11: | Line 11: | ||
#include <sys/time.h> |
#include <sys/time.h> |
||
#include <string.h> |
#include <string.h> |
||
struct timeval last_update, last_move; |
struct timeval last_update, last_move; |
||
/* board width */ |
/* board width */ |
||
Line 18: | Line 18: | ||
int twid = 1; |
int twid = 1; |
||
int W = 240, H = 240, gwin; |
int W = 240, H = 240, gwin; |
||
void *board; |
void *board; |
||
typedef struct { int x, y; } cell_t; |
typedef struct { int x, y; } cell_t; |
||
Line 26: | Line 26: | ||
int n_moves, need_move = 1, stopped = 0, failed = 0, paused = 0, skip_draw = 0; |
int n_moves, need_move = 1, stopped = 0, failed = 0, paused = 0, skip_draw = 0; |
||
int delay = 1024 * 128; |
int delay = 1024 * 128; |
||
GLubyte *tex; |
GLubyte *tex; |
||
GLuint texture; |
GLuint texture; |
||
int good(int x) |
int good(int x) |
||
{ |
{ |
||
return x >= 0 && x < bw; |
return x >= 0 && x < bw; |
||
} |
} |
||
void init_board() |
void init_board() |
||
{ |
{ |
||
Line 40: | Line 40: | ||
for (int i = 0; i < bw; i++) |
for (int i = 0; i < bw; i++) |
||
memset(b[i], 0, sizeof(int) * bw); |
memset(b[i], 0, sizeof(int) * bw); |
||
n_moves = b[start.y][start.x] = 1; |
n_moves = b[start.y][start.x] = 1; |
||
moves[0] = start; |
moves[0] = start; |
||
Line 46: | Line 46: | ||
stopped = 0; |
stopped = 0; |
||
} |
} |
||
int n_vacant(int x, int y) |
int n_vacant(int x, int y) |
||
{ |
{ |
||
int (*b)[bw] = board; |
int (*b)[bw] = board; |
||
int cnt = 0; |
int cnt = 0; |
||
for (int i = 0; i < 8; i++) { |
for (int i = 0; i < 8; i++) { |
||
int nx = x + ofs[i].x; |
int nx = x + ofs[i].x; |
||
if (!good(nx)) continue; |
if (!good(nx)) continue; |
||
int ny = y + ofs[i].y; |
int ny = y + ofs[i].y; |
||
if (!good(ny)) continue; |
if (!good(ny)) continue; |
||
if (!b[ny][nx]) cnt++; |
if (!b[ny][nx]) cnt++; |
||
} |
} |
||
return cnt; |
return cnt; |
||
} |
} |
||
int restart() |
int restart() |
||
{ |
{ |
||
Line 82: | Line 82: | ||
return 0; |
return 0; |
||
} |
} |
||
int next_move() |
int next_move() |
||
{ |
{ |
||
if (!need_move || stopped || paused) |
if (!need_move || stopped || paused) |
||
return 0; |
return 0; |
||
int (*b)[bw] = board; |
int (*b)[bw] = board; |
||
cell_t cur = moves[n_moves - 1]; |
cell_t cur = moves[n_moves - 1]; |
||
cell_t dest; |
cell_t dest; |
||
int least = 9; |
int least = 9; |
||
for (int i = 0; i < 8; i++) { |
for (int i = 0; i < 8; i++) { |
||
int x = cur.x + ofs[i].x; |
int x = cur.x + ofs[i].x; |
||
if (!good(x)) continue; |
if (!good(x)) continue; |
||
int y = cur.y + ofs[i].y; |
int y = cur.y + ofs[i].y; |
||
if (!good(y)) continue; |
if (!good(y)) continue; |
||
if (b[y][x]) continue; |
if (b[y][x]) continue; |
||
int n = n_vacant(x, y); |
int n = n_vacant(x, y); |
||
if (n < least) { |
if (n < least) { |
||
Line 109: | Line 109: | ||
} |
} |
||
} |
} |
||
if (least == 9) { |
if (least == 9) { |
||
stopped = 1; |
stopped = 1; |
||
Line 120: | Line 120: | ||
return 0; |
return 0; |
||
} |
} |
||
moves[n_moves++] = dest; |
moves[n_moves++] = dest; |
||
b[dest.y][dest.x] = 1; |
b[dest.y][dest.x] = 1; |
||
need_move = 1; |
need_move = 1; |
||
return 1; |
return 1; |
||
} |
} |
||
void resize(int w, int h) |
void resize(int w, int h) |
||
{ |
{ |
||
int dx = 0, dy = 0; |
int dx = 0, dy = 0; |
||
W = w; H = h; |
W = w; H = h; |
||
if (w > h) dx = w - h; |
if (w > h) dx = w - h; |
||
else dy = h - w; |
else dy = h - w; |
||
glViewport(dx / 2, dy / 2, W - dx, H - dy); |
glViewport(dx / 2, dy / 2, W - dx, H - dy); |
||
glOrtho(0, bw, 0, bw, -1, 1); |
glOrtho(0, bw, 0, bw, -1, 1); |
||
} |
} |
||
void render() |
void render() |
||
{ |
{ |
||
double tw = (double) bw / twid; |
double tw = (double) bw / twid; |
||
struct timeval tv; |
struct timeval tv; |
||
gettimeofday(&tv, 0); |
gettimeofday(&tv, 0); |
||
Line 154: | Line 154: | ||
if (skip_draw && !stopped) return; |
if (skip_draw && !stopped) return; |
||
usec = (tv.tv_sec - last_update.tv_sec) * 1000000 |
usec = (tv.tv_sec - last_update.tv_sec) * 1000000 |
||
+ tv.tv_usec - last_update.tv_usec; |
+ tv.tv_usec - last_update.tv_usec; |
||
if (usec < 25000) return; |
if (usec < 25000) return; |
||
last_update = tv; |
last_update = tv; |
||
glClear(GL_COLOR_BUFFER_BIT); |
glClear(GL_COLOR_BUFFER_BIT); |
||
glLoadIdentity(); |
glLoadIdentity(); |
||
glBindTexture(GL_TEXTURE_2D, texture); |
glBindTexture(GL_TEXTURE_2D, texture); |
||
glColor3f(1, 1, 1); |
glColor3f(1, 1, 1); |
||
glBegin(GL_QUADS); |
glBegin(GL_QUADS); |
||
Line 171: | Line 171: | ||
glTexCoord2f(tw, 0); glVertex2i(bw, 0); |
glTexCoord2f(tw, 0); glVertex2i(bw, 0); |
||
glEnd(); |
glEnd(); |
||
glBegin(GL_QUADS); |
glBegin(GL_QUADS); |
||
glColor3f(0, .5, 1); |
glColor3f(0, .5, 1); |
||
int x = moves[0].x, y = moves[0].y; |
int x = moves[0].x, y = moves[0].y; |
||
glVertex2i(x + 0, y + 0); |
glVertex2i(x + 0, y + 0); |
||
glVertex2i(x + 0, y + 1); |
glVertex2i(x + 0, y + 1); |
||
glVertex2i(x + 1, y + 1); |
glVertex2i(x + 1, y + 1); |
||
glVertex2i(x + 1, y + 0); |
glVertex2i(x + 1, y + 0); |
||
glColor4f(.5, .7, .5, .7); |
glColor4f(.5, .7, .5, .7); |
||
for (int i = (n_moves == bw * bw) ? n_moves - 1 : 1; i < n_moves; i++) { |
for (int i = (n_moves == bw * bw) ? n_moves - 1 : 1; i < n_moves; i++) { |
||
Line 192: | Line 192: | ||
} |
} |
||
glEnd(); |
glEnd(); |
||
glBegin(GL_LINE_STRIP); |
glBegin(GL_LINE_STRIP); |
||
if (n_moves == bw * bw) |
if (n_moves == bw * bw) |
||
Line 198: | Line 198: | ||
else |
else |
||
glColor3f(0, 0, 0); |
glColor3f(0, 0, 0); |
||
for (int i = 0; i < n_moves; i++) |
for (int i = 0; i < n_moves; i++) |
||
glVertex2f(moves[i].x + .5, moves[i].y + .5); |
glVertex2f(moves[i].x + .5, moves[i].y + .5); |
||
glEnd(); |
glEnd(); |
||
glutSwapBuffers(); |
|||
glFinish(); |
|||
need_move = 1; |
need_move = 1; |
||
} |
} |
||
void init_texture() |
void init_texture() |
||
{ |
{ |
||
int i, j; |
int i, j; |
||
while (twid < bw) twid <<= 1; |
while (twid < bw) twid <<= 1; |
||
GLubyte * ptr = tex = malloc(twid * twid * 3); |
GLubyte * ptr = tex = malloc(twid * twid * 3); |
||
for (i = 0; i < twid; i++) |
for (i = 0; i < twid; i++) |
||
for (j = 0; j < twid; j++, ptr += 3) |
for (j = 0; j < twid; j++, ptr += 3) |
||
Line 221: | Line 220: | ||
else |
else |
||
ptr[0] = 120, ptr[1] = 255, ptr[2] = 200; |
ptr[0] = 120, ptr[1] = 255, ptr[2] = 200; |
||
glEnable(GL_TEXTURE_2D); |
glEnable(GL_TEXTURE_2D); |
||
glGenTextures(1, &texture); |
glGenTextures(1, &texture); |
||
Line 227: | Line 226: | ||
glTexImage2D(GL_TEXTURE_2D, 0, 3, twid, twid, |
glTexImage2D(GL_TEXTURE_2D, 0, 3, twid, twid, |
||
0, GL_RGB, GL_UNSIGNED_BYTE, tex); |
0, GL_RGB, GL_UNSIGNED_BYTE, tex); |
||
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST); |
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST); |
||
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST); |
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST); |
||
free(tex); |
free(tex); |
||
} |
} |
||
void set_delay(int inc) |
void set_delay(int inc) |
||
{ |
{ |
||
Line 242: | Line 241: | ||
delay = 1 << 20; |
delay = 1 << 20; |
||
paused = 1; |
paused = 1; |
||
printf(" |
printf("Paused\n"); |
||
return; |
return; |
||
} |
} |
||
Line 250: | Line 249: | ||
printf("Delay = %d usec\n", delay); |
printf("Delay = %d usec\n", delay); |
||
} |
} |
||
void keypress(unsigned char key, int x, int y) |
void keypress(unsigned char key, int x, int y) |
||
{ |
{ |
||
Line 275: | Line 274: | ||
} |
} |
||
} |
} |
||
void init_graphics(int c, char **v) |
void init_graphics(int c, char **v) |
||
{ |
{ |
||
glutInit(&c, v); |
glutInit(&c, v); |
||
glutInitDisplayMode(GLUT_RGBA); |
glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE); |
||
glutInitWindowSize(W, H); |
glutInitWindowSize(W, H); |
||
glutDisplayFunc(render); |
glutDisplayFunc(render); |
||
glutIdleFunc(render); |
glutIdleFunc(render); |
||
glutDisplayFunc(render); |
glutDisplayFunc(render); |
||
gwin = glutCreateWindow("Board"); |
gwin = glutCreateWindow("Board"); |
||
glutKeyboardFunc(keypress); |
glutKeyboardFunc(keypress); |
||
glutReshapeFunc(resize); |
glutReshapeFunc(resize); |
||
glClearColor(.2, .2, .2, 1); |
glClearColor(.2, .2, .2, 1); |
||
glMatrixMode(GL_PROJECTION); |
glMatrixMode(GL_PROJECTION); |
||
glLoadIdentity(); |
glLoadIdentity(); |
||
glOrtho(0, bw, 0, bw, -1, 1); |
glOrtho(0, bw, 0, bw, -1, 1); |
||
glMatrixMode(GL_MODELVIEW); |
glMatrixMode(GL_MODELVIEW); |
||
glEnable(GL_BLEND); |
glEnable(GL_BLEND); |
||
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA); |
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA); |
||
init_texture(); |
init_texture(); |
||
} |
} |
||
int main(int c, char **v) |
int main(int c, char **v) |
||
{ |
{ |
||
if (c >= 3 && !strcmp(v[1], "-s")) { |
if (c >= 3 && !strcmp(v[1], "-s")) { |
||
Line 314: | Line 313: | ||
printf("Keys:\n\tQ, Esc: exit\n\t<: slow down\n\t>: speed up\n\t" |
printf("Keys:\n\tQ, Esc: exit\n\t<: slow down\n\t>: speed up\n\t" |
||
"s: skip to finish\n<space>: try a new tour\n"); |
"s: skip to finish\n<space>: try a new tour\n"); |
||
int b[bw][bw]; |
int b[bw][bw]; |
||
cell_t g[bw * bw]; |
cell_t g[bw * bw]; |
||
Line 320: | Line 319: | ||
board = b; |
board = b; |
||
start.x = start.y = 0; |
start.x = start.y = 0; |
||
init_board(); |
init_board(); |
||
init_graphics(c, v); |
init_graphics(c, v); |
||
gettimeofday(&last_update, 0); |
gettimeofday(&last_update, 0); |
||
last_move = last_update; |
last_move = last_update; |
||
glutMainLoop(); |
glutMainLoop(); |
||
return 0; |
return 0; |
Revision as of 18:30, 16 April 2014
OpenGL
OpenGL program with glut. Compile with gcc -std=c99 -lglut -lGL -lGLU
, run with a.out -s [size]
. Program will print a help message at start.
<lang c>#include <GL/glut.h>
- include <GL/gl.h>
- include <GL/glu.h>
- include <stdio.h>
- include <time.h>
- include <unistd.h>
- include <sys/time.h>
- include <string.h>
struct timeval last_update, last_move; /* board width */ int bw = 7; /* power of 2 */ int twid = 1; int W = 240, H = 240, gwin;
void *board; typedef struct { int x, y; } cell_t; cell_t *moves; cell_t ofs[8] = {{2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}}; cell_t start; int n_moves, need_move = 1, stopped = 0, failed = 0, paused = 0, skip_draw = 0; int delay = 1024 * 128;
GLubyte *tex; GLuint texture;
int good(int x) { return x >= 0 && x < bw; }
void init_board() { int (*b)[bw] = board; for (int i = 0; i < bw; i++) memset(b[i], 0, sizeof(int) * bw);
n_moves = b[start.y][start.x] = 1; moves[0] = start; need_move = 1; stopped = 0; }
int n_vacant(int x, int y) { int (*b)[bw] = board; int cnt = 0;
for (int i = 0; i < 8; i++) { int nx = x + ofs[i].x; if (!good(nx)) continue;
int ny = y + ofs[i].y; if (!good(ny)) continue;
if (!b[ny][nx]) cnt++; }
return cnt; }
int restart() { if (++start.x < bw) { init_board(); return 1; } start.x = 0; if (++start.y < bw) { init_board(); return 1; } start.y = 0; printf("Already tried all starting positions\n"); need_move = 0; failed = 1; return 0; }
int next_move() { if (!need_move || stopped || paused) return 0;
int (*b)[bw] = board; cell_t cur = moves[n_moves - 1]; cell_t dest; int least = 9;
for (int i = 0; i < 8; i++) { int x = cur.x + ofs[i].x; if (!good(x)) continue;
int y = cur.y + ofs[i].y; if (!good(y)) continue;
if (b[y][x]) continue;
int n = n_vacant(x, y); if (n < least) { least = n; dest.x = x; dest.y = y; } }
if (least == 9) { stopped = 1; need_move = 0; if (n_moves == bw * bw) printf("Tour complete.\n"); else printf("Stuck at %d moves\n", n_moves); printf("Press SPACE to continue\n"); return 0; }
moves[n_moves++] = dest; b[dest.y][dest.x] = 1;
need_move = 1; return 1; }
void resize(int w, int h) { int dx = 0, dy = 0; W = w; H = h;
if (w > h) dx = w - h; else dy = h - w;
glViewport(dx / 2, dy / 2, W - dx, H - dy); glOrtho(0, bw, 0, bw, -1, 1); }
void render() { double tw = (double) bw / twid;
struct timeval tv; gettimeofday(&tv, 0); long usec = (tv.tv_sec - last_move.tv_sec) * 1000000 + tv.tv_usec - last_move.tv_usec; if (usec > delay || skip_draw) { next_move(); last_move = tv; }
if (skip_draw && !stopped) return;
usec = (tv.tv_sec - last_update.tv_sec) * 1000000 + tv.tv_usec - last_update.tv_usec; if (usec < 25000) return; last_update = tv;
glClear(GL_COLOR_BUFFER_BIT); glLoadIdentity(); glBindTexture(GL_TEXTURE_2D, texture);
glColor3f(1, 1, 1); glBegin(GL_QUADS); glTexCoord2f( 0, 0); glVertex2i(0, 0); glTexCoord2f( 0, tw); glVertex2i(0, bw); glTexCoord2f(tw, tw); glVertex2i(bw, bw); glTexCoord2f(tw, 0); glVertex2i(bw, 0); glEnd();
glBegin(GL_QUADS); glColor3f(0, .5, 1); int x = moves[0].x, y = moves[0].y;
glVertex2i(x + 0, y + 0); glVertex2i(x + 0, y + 1); glVertex2i(x + 1, y + 1); glVertex2i(x + 1, y + 0);
glColor4f(.5, .7, .5, .7); for (int i = (n_moves == bw * bw) ? n_moves - 1 : 1; i < n_moves; i++) { if (i == n_moves - 1) glColor3f(1, 0, 0); x = moves[i].x, y = moves[i].y; glVertex2f(x + 0, y + 0); glVertex2f(x + 0, y + 1); glVertex2f(x + 1, y + 1); glVertex2f(x + 1, y + 0); } glEnd();
glBegin(GL_LINE_STRIP); if (n_moves == bw * bw) glColor3f(0, .4, .4); else glColor3f(0, 0, 0);
for (int i = 0; i < n_moves; i++) glVertex2f(moves[i].x + .5, moves[i].y + .5); glEnd();
glutSwapBuffers(); need_move = 1; }
void init_texture() { int i, j; while (twid < bw) twid <<= 1;
GLubyte * ptr = tex = malloc(twid * twid * 3);
for (i = 0; i < twid; i++) for (j = 0; j < twid; j++, ptr += 3) if ((i & 1) != (j & 1)) ptr[0] = ptr[1] = ptr[2] = 255; else ptr[0] = 120, ptr[1] = 255, ptr[2] = 200;
glEnable(GL_TEXTURE_2D); glGenTextures(1, &texture); glBindTexture(GL_TEXTURE_2D, texture); glTexImage2D(GL_TEXTURE_2D, 0, 3, twid, twid, 0, GL_RGB, GL_UNSIGNED_BYTE, tex);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST); glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
free(tex); }
void set_delay(int inc) { if (inc) { delay *= 2; if (!delay) delay = 1; if (delay >= 1 << 20) { delay = 1 << 20; paused = 1; printf("Paused\n"); return; } } else delay /= 2; paused = 0; printf("Delay = %d usec\n", delay); }
void keypress(unsigned char key, int x, int y) { switch(key) { case ' ': if (stopped && !failed) restart(); break; case 'q': case 27: glFinish(); glutDestroyWindow(gwin); return; case ',': case '<': set_delay(1); return; case '.': case '>': set_delay(0); return; case 's': skip_draw = !skip_draw; return; } }
void init_graphics(int c, char **v) { glutInit(&c, v); glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE); glutInitWindowSize(W, H); glutDisplayFunc(render); glutIdleFunc(render); glutDisplayFunc(render);
gwin = glutCreateWindow("Board");
glutKeyboardFunc(keypress); glutReshapeFunc(resize);
glClearColor(.2, .2, .2, 1);
glMatrixMode(GL_PROJECTION); glLoadIdentity(); glOrtho(0, bw, 0, bw, -1, 1); glMatrixMode(GL_MODELVIEW);
glEnable(GL_BLEND); glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
init_texture(); }
int main(int c, char **v) { if (c >= 3 && !strcmp(v[1], "-s")) { bw = atoi(v[2]); if (bw < 3) { printf("bad argument -s %s, size set to 3\n", v[2]); bw = 3; } } printf("Keys:\n\tQ, Esc: exit\n\t<: slow down\n\t>: speed up\n\t" "s: skip to finish\n<space>: try a new tour\n");
int b[bw][bw]; cell_t g[bw * bw]; moves = g; board = b; start.x = start.y = 0;
init_board();
init_graphics(c, v); gettimeofday(&last_update, 0); last_move = last_update;
glutMainLoop(); return 0; }</lang>