git.hungrycats.org Git - xscreensaver/blob - hacks/glx/queens.c

   1 /*
   2  * queens - solves n queens problem, displays
   3  * i make no claims that this is an optimal solution to the problem,
   4  * good enough for xss
   5  * hacked from glchess
   6  *
   7  * version 1.0 - May 10, 2002
   8  *
   9  * Copyright (C) 2002 Blair Tennessy (tennessb@unbc.ca)
  10  *
  11  * Permission to use, copy, modify, distribute, and sell this software and its
  12  * documentation for any purpose is hereby granted without fee, provided that
  13  * the above copyright notice appear in all copies and that both that
  14  * copyright notice and this permission notice appear in supporting
  15  * documentation.  No representations are made about the suitability of this
  16  * software for any purpose.  It is provided "as is" without express or
  17  * implied warranty.
  18  */
  19
  20 #include <X11/Intrinsic.h>
  21
  22 #ifdef STANDALONE
  23 # define PROGCLASS        "Queens"
  24 # define HACK_INIT        init_queens
  25 # define HACK_DRAW        draw_queens
  26 # define HACK_RESHAPE     reshape_queens
  27 # define HACK_HANDLE_EVENT queens_handle_event
  28 # define EVENT_MASK       PointerMotionMask
  29 # define queens_opts  xlockmore_opts
  30
  31 #define DEFAULTS       "*delay:       20000       \n" \
  32                        "*showFPS:       False       \n" \
  33                        "*wireframe:     False     \n"   \
  34
  35 # include "xlockmore.h"
  36
  37 #else
  38 # include "xlock.h"
  39 #endif
  40
  41 #ifdef USE_GL
  42
  43 #include <GL/glu.h>
  44 #include "gltrackball.h"
  45
  46 #undef countof
  47 #define countof(x) (sizeof((x))/sizeof((*x)))
  48
  49 static XrmOptionDescRec opts[] = {
  50   {"+rotate", ".queens.rotate", XrmoptionNoArg, (caddr_t) "false" },
  51   {"-rotate", ".queens.rotate", XrmoptionNoArg, (caddr_t) "true" },
  52 };
  53
  54 int rotate;
  55
  56 static argtype vars[] = {
  57   {(caddr_t *) &rotate, "rotate", "Rotate", "True", t_Bool},
  58 };
  59
  60 ModeSpecOpt queens_opts = {countof(opts), opts, countof(vars), vars, NULL};
  61
  62 #ifdef USE_MODULES
  63 ModStruct   queens_description =
  64 {"queens", "init_queens", "draw_queens", "release_queens",
  65  "draw_queens", "init_queens", NULL, &queens_opts,
  66  1000, 1, 2, 1, 4, 1.0, "",
  67  "Queens", 0, NULL};
  68
  69 #endif
  70
  71 typedef struct {
  72   GLXContext *glx_context;
  73   Window window;
  74   trackball_state *trackball;
  75   Bool button_down_p;
  76 } Queenscreen;
  77
  78 static Queenscreen *qs = NULL;
  79
  80 #include <math.h>
  81 #include <sys/time.h>
  82 #include <stdio.h>
  83 #include <stdlib.h>
  84
  85 #ifndef M_PI
  86 #define M_PI 3.14159265
  87 #endif
  88
  89 #define NONE 0
  90 #define QUEEN 1
  91 #define MINBOARD 5
  92 #define MAXBOARD 10
  93
  94 /* definition of white/black colors */
  95 GLfloat colors[2][3] = { {0.5, 0.7, 0.9},
  96                          {0.2, 0.3, 0.6} };
  97
  98 int board[MAXBOARD][MAXBOARD];
  99 int work = 0, vb = 0, steps = 0, BOARDSIZE = 8; /* 8 cuz its classic */
 100
 101 Bool
 102 queens_handle_event (ModeInfo *mi, XEvent *event)
 103 {
 104   Queenscreen *c = &qs[MI_SCREEN(mi)];
 105
 106   if (event->xany.type == ButtonPress &&
 107       event->xbutton.button & Button1)
 108     {
 109       c->button_down_p = True;
 110       gltrackball_start (c->trackball,
 111                          event->xbutton.x, event->xbutton.y,
 112                          MI_WIDTH (mi), MI_HEIGHT (mi));
 113       return True;
 114     }
 115   else if (event->xany.type == ButtonRelease &&
 116            event->xbutton.button & Button1)
 117     {
 118       c->button_down_p = False;
 119       return True;
 120     }
 121   else if (event->xany.type == MotionNotify &&
 122            c->button_down_p)
 123     {
 124       gltrackball_track (c->trackball,
 125                          event->xmotion.x, event->xmotion.y,
 126                          MI_WIDTH (mi), MI_HEIGHT (mi));
 127       return True;
 128     }
 129
 130   return False;
 131 }
 132
 133
 134
 135 /* returns true if placing a queen on column c causes a conflict */
 136 int conflictsCols(int c) {
 137   int i;
 138
 139   for(i = 0; i < BOARDSIZE; ++i)
 140     if(board[i][c])
 141       return 1;
 142
 143   return 0;
 144 }
 145
 146 /* returns true if placing a queen on (r,c) causes a diagonal conflict */
 147 int conflictsDiag(int r, int c) {
 148   int i;
 149
 150   /* positive slope */
 151   int n = r < c ? r : c;
 152   for(i = 0; i < BOARDSIZE-abs(r-c); ++i)
 153     if(board[r-n+i][c-n+i])
 154       return 1;
 155
 156   /* negative slope */
 157   n = r < BOARDSIZE - (c+1) ? r : BOARDSIZE - (c+1);
 158   for(i = 0; i < BOARDSIZE-abs(BOARDSIZE - (1+r+c)); ++i)
 159     if(board[r-n+i][c+n-i])
 160       return 1;
 161
 162   return 0;
 163 }
 164
 165 /* returns true if placing a queen at (r,c) causes a conflict */
 166 int conflicts(int r, int c) {
 167   return !conflictsCols(c) ? conflictsDiag(r, c) : 1;
 168 }
 169
 170 /* clear board */
 171 void blank(void) {
 172   int i, j;
 173
 174   for(i = 0; i < MAXBOARD; ++i)
 175     for(j = 0; j < MAXBOARD; ++j)
 176       board[i][j] = NONE;
 177 }
 178
 179 /* recursively determine solution */
 180 int findSolution(int row) {
 181   int col = 0;
 182
 183   if(row == BOARDSIZE)
 184     return 1;
 185
 186   while(col < BOARDSIZE) {
 187     if(!conflicts(row, col)) {
 188       board[row][col] = QUEEN;
 189
 190       if(findSolution(row+1))
 191         return 1;
 192
 193       board[row][col] = NONE;
 194     }
 195
 196     ++col;
 197   }
 198
 199   return 0;
 200 }
 201
 202 /* driver for finding solution */
 203 void go(void) { findSolution(0); }
 204
 205 /* configure lighting */
 206 void setup_lights(void) {
 207   GLfloat position[] = { 4.0, 8.0, 4.0, 1.0 };
 208
 209   glEnable(GL_LIGHTING);
 210   glLightfv(GL_LIGHT0, GL_POSITION, position);
 211   glEnable(GL_LIGHT0);
 212 }
 213
 214 /* return alpha value for fading */
 215 GLfloat findAlpha(void) {
 216   return steps < 128 ? steps/128.0 : steps < 512-128 ? 1.0 : (512-steps)/128.0;
 217 }
 218
 219 /* draw pieces */
 220 void drawPieces(void) {
 221   int i, j;
 222
 223   for(i = 0; i < BOARDSIZE; ++i) {
 224     for(j = 0; j < BOARDSIZE; ++j) {
 225       if(board[i][j]) {
 226         glColor4f(colors[i%2][0], colors[i%2][1], colors[i%2][2], findAlpha());
 227         glCallList(QUEEN);
 228       }
 229
 230       glTranslatef(1.0, 0.0, 0.0);
 231     }
 232
 233     glTranslatef(-1.0*BOARDSIZE, 0.0, 1.0);
 234   }
 235 }
 236
 237 /* draw board */
 238 void drawBoard(int wire) {
 239   int i, j;
 240
 241   if (!wire) glBegin(GL_QUADS);
 242
 243   for(i = 0; i < BOARDSIZE; ++i)
 244     for(j = 0; j < BOARDSIZE; ++j) {
 245       int par = (i-j+BOARDSIZE)%2;
 246       glColor4f(colors[par][0], colors[par][1], colors[par][2], findAlpha());
 247       glNormal3f(0.0, 1.0, 0.0);
 248       if (wire) glBegin(GL_LINE_LOOP);
 249       glVertex3f(j - 0.5, -0.01, i - 0.5);
 250       glVertex3f(j + 0.5, -0.01, i - 0.5);
 251       glVertex3f(j + 0.5, -0.01, i + 0.5);
 252       glVertex3f(j - 0.5, -0.01, i + 0.5);
 253       if (wire) glEnd();
 254     }
 255
 256   if (!wire) glEnd();
 257 }
 258
 259 double theta = 0.0;
 260
 261 void display(Queenscreen *c, int wire) {
 262   glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
 263
 264   glMatrixMode(GL_MODELVIEW);
 265   glLoadIdentity();
 266   gluLookAt(0.0, 1.0+(0.8*fabs(sin(theta)))*10.0, -1.2*BOARDSIZE,
 267             0.0, 1.0, 0.0,
 268             0.0, 0.0, 1.0);
 269
 270   glScalef(1, -1, 1);
 271   gltrackball_rotate (c->trackball);    /* Apply mouse-based camera position */
 272   glScalef(1, -1, 1);
 273
 274   glRotatef(theta*100, 0.0, 1.0, 0.0);
 275   glTranslatef(-0.5 * (BOARDSIZE-1), 0.0, -0.5 * (BOARDSIZE-1));
 276
 277   if (!wire) {
 278     glEnable(GL_LIGHTING);
 279     glEnable(GL_COLOR_MATERIAL);
 280     glEnable(GL_BLEND);
 281   }
 282
 283   drawBoard(wire);
 284   glTranslatef(0.0, 0.01, 0.0);
 285   drawPieces();
 286
 287   glDisable(GL_COLOR_MATERIAL);
 288   glDisable(GL_BLEND);
 289   glDisable(GL_LIGHTING);
 290
 291   theta += .002;
 292
 293   /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
 294   if(++steps == 512) {
 295     steps = 0;
 296     blank();
 297     BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
 298     go();
 299   }
 300 }
 301
 302 #define piece_size 0.1
 303 #define EPSILON 0.001
 304
 305 /* Make a revolved piece */
 306 void revolve_line(double *trace_r, double *trace_h, double max_iheight,
 307                   int rot, int wire) {
 308   double theta, norm_theta, sin_theta, cos_theta;
 309   double norm_ptheta = 0.0, sin_ptheta = 0.0, cos_ptheta = 1.0;
 310   double radius, pradius;
 311   double max_height = max_iheight, height, pheight;
 312   double dx, dy, len;
 313   int npoints, p;
 314   double dtheta = (2.0*M_PI) / rot;
 315
 316   /* Get the number of points */
 317   for(npoints = 0;
 318       fabs(trace_r[npoints]) > EPSILON || fabs(trace_h[npoints]) > EPSILON;
 319       ++npoints);
 320
 321   /* If less than two points, can not revolve */
 322   if(npoints < 2)
 323     return;
 324
 325   /* If the max_height hasn't been defined, find it */
 326   if(max_height < EPSILON)
 327     for(p = 0; p < npoints; ++p)
 328       if(max_height < trace_h[p])
 329         max_height = trace_h[p];
 330
 331   /* Draw the revolution */
 332   for(theta = dtheta; rot > 0; --rot) {
 333     sin_theta = sin(theta);
 334     cos_theta = cos(theta);
 335     norm_theta = theta / (2.0 * M_PI);
 336     pradius = trace_r[0] * piece_size;
 337     pheight = trace_h[0] * piece_size;
 338
 339     for(p = 0; p < npoints; ++p) {
 340       radius = trace_r[p] * piece_size;
 341       height = trace_h[p] * piece_size;
 342
 343       /* Get the normalized lengths of the normal vector */
 344       dx = radius - pradius;
 345       dy = height - pheight;
 346       len = sqrt(dx*dx + dy*dy);
 347       dx /= len;
 348       dy /= len;
 349
 350       /* If only triangles required */
 351       if (fabs(radius) < EPSILON) {
 352         glBegin(wire ? GL_LINE_LOOP : GL_TRIANGLES);
 353
 354         glNormal3f(dy * sin_ptheta, -dx, dy * cos_ptheta);
 355         glTexCoord2f(norm_ptheta, pheight / max_height);
 356         glVertex3f(pradius * sin_ptheta, pheight, pradius * cos_ptheta);
 357
 358         glNormal3f(dy * sin_theta, -dx, dy * cos_theta);
 359         glTexCoord2f(norm_theta, pheight / max_height);
 360         glVertex3f(pradius * sin_theta, pheight, pradius * cos_theta);
 361
 362         glTexCoord2f(0.5 * (norm_theta + norm_ptheta),
 363                      height / max_height);
 364         glVertex3f(0.0, height, 0.0);
 365
 366         glEnd();
 367       }
 368
 369       else {
 370         glBegin(wire ? GL_LINE_LOOP : GL_QUADS);
 371
 372         glNormal3f(dy * sin_ptheta, -dx, dy * cos_ptheta);
 373         glTexCoord2f(norm_ptheta, pheight / max_height);
 374         glVertex3f(pradius * sin_ptheta, pheight, pradius * cos_ptheta);
 375
 376         glNormal3f(dy * sin_theta, -dx, dy * cos_theta);
 377         glTexCoord2f(norm_theta, pheight / max_height);
 378         glVertex3f(pradius * sin_theta, pheight, pradius * cos_theta);
 379
 380         glTexCoord2f(norm_theta, height / max_height);
 381         glVertex3f(radius * sin_theta, height, radius * cos_theta);
 382
 383         glNormal3f(dy * sin_ptheta, -dx, dy * cos_ptheta);
 384         glTexCoord2f(norm_ptheta, height / max_height);
 385         glVertex3f(radius * sin_ptheta, height, radius * cos_ptheta);
 386
 387         glEnd();
 388       }
 389
 390       pradius = radius;
 391       pheight = height;
 392     }
 393
 394     sin_ptheta = sin_theta;
 395     cos_ptheta = cos_theta;
 396     norm_ptheta = norm_theta;
 397     theta += dtheta;
 398   }
 399 }
 400
 401 void draw_queen(int wire) {
 402   double trace_r[] =
 403       { 4.8, 4.8, 3.4, 3.4, 1.8, 1.4, 2.9, 1.8, 1.8, 2.0,
 404         2.7, 2.4, 1.7, 0.95, 0.7, 0.0, 0.0 }; /*, 0.9, 0.7, 0.0, 0.0};*/
 405   double trace_h[] =
 406       { 0.0, 2.2, 4.0, 5.0, 8.0, 11.8, 11.8, 13.6, 15.2, 17.8,
 407         19.2, 20.0, 20.0, 20.8, 20.8, 22.0, 0.0 };/*,21.4, 22.0, 22.0, 0.0 };*/
 408
 409   revolve_line(trace_r, trace_h, 0.0, 8, wire);
 410 }
 411
 412 void reshape_queens(ModeInfo *mi, int width, int height) {
 413   GLfloat h = (GLfloat) height / (GLfloat) width;
 414   glViewport(0,0, width, height);
 415   glMatrixMode(GL_PROJECTION);
 416   glLoadIdentity();
 417   gluPerspective(45, 1/h, 2.0, 30.0);
 418   glMatrixMode(GL_MODELVIEW);
 419 }
 420
 421 void init_queens(ModeInfo *mi) {
 422   GLfloat mat_shininess[] = { 90.0 };
 423   GLfloat mat_specular[] = { 1.0, 1.0, 1.0, 1.0 };
 424
 425   int screen = MI_SCREEN(mi);
 426   int wire = MI_IS_WIREFRAME(mi);
 427   Queenscreen *c;
 428
 429   if(!qs &&
 430      !(qs = (Queenscreen *) calloc(MI_NUM_SCREENS(mi), sizeof(Queenscreen))))
 431     return;
 432
 433   c = &qs[screen];
 434   c->window = MI_WINDOW(mi);
 435   c->trackball = gltrackball_init ();
 436
 437   if((c->glx_context = init_GL(mi)))
 438     reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
 439   else
 440     MI_CLEARWINDOW(mi);
 441
 442   glClearColor(0.0, 0.0, 0.0, 0.0);
 443
 444   setup_lights();
 445   glNewList(1, GL_COMPILE);
 446   draw_queen(wire);
 447   glEndList();
 448
 449   if (!wire) {
 450     glColorMaterial(GL_FRONT, GL_DIFFUSE);
 451
 452     glMaterialfv(GL_FRONT_AND_BACK, GL_SPECULAR, mat_specular);
 453     glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, mat_shininess);
 454
 455     glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
 456     glShadeModel(GL_SMOOTH);
 457     glEnable(GL_DEPTH_TEST);
 458   }
 459
 460   /* find a solution */
 461   go();
 462 }
 463
 464 void draw_queens(ModeInfo *mi) {
 465   Queenscreen *c = &qs[MI_SCREEN(mi)];
 466   Window w = MI_WINDOW(mi);
 467   Display *disp = MI_DISPLAY(mi);
 468
 469   if(!c->glx_context)
 470     return;
 471
 472   glXMakeCurrent(disp, w, *(c->glx_context));
 473
 474   display(c, MI_IS_WIREFRAME(mi));
 475
 476   if(mi->fps_p) do_fps(mi);
 477   glFinish();
 478   glXSwapBuffers(disp, w);
 479 }
 480
 481 void release_queens(ModeInfo *mi) {
 482   if(qs)
 483     free((void *) qs);
 484
 485   FreeAllGL(MI);
 486 }
 487
 488 #endif