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 (tennessy@cs.ubc.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, "false" },
  51   {"-rotate", ".queens.rotate", XrmoptionNoArg, "true" },
  52   {"+flat", ".queens.flat", XrmoptionNoArg, "false" },
  53   {"-flat", ".queens.flat", XrmoptionNoArg, "true" },
  54 };
  55
  56 int rotate, wire, clearbits, flat;
  57
  58 static argtype vars[] = {
  59   {&rotate, "rotate", "Rotate", "True",  t_Bool},
  60   {&flat,   "flat",   "Flat",   "False", t_Bool},
  61 };
  62
  63 ModeSpecOpt queens_opts = {countof(opts), opts, countof(vars), vars, NULL};
  64
  65 #ifdef USE_MODULES
  66 ModStruct   queens_description =
  67 {"queens", "init_queens", "draw_queens", "release_queens",
  68  "draw_queens", "init_queens", NULL, &queens_opts,
  69  1000, 1, 2, 1, 4, 1.0, "",
  70  "Queens", 0, NULL};
  71
  72 #endif
  73
  74 typedef struct {
  75   GLXContext *glx_context;
  76   Window window;
  77   trackball_state *trackball;
  78   Bool button_down_p;
  79 } Queenscreen;
  80
  81 static Queenscreen *qs = NULL;
  82
  83 #include <math.h>
  84 #include <sys/time.h>
  85 #include <stdio.h>
  86 #include <stdlib.h>
  87
  88 #ifndef M_PI
  89 #define M_PI 3.14159265
  90 #endif
  91
  92 #define NONE 0
  93 #define QUEEN 1
  94 #define MINBOARD 5
  95 #define MAXBOARD 10
  96 #define COLORSETS 5
  97
  98 /* definition of white/black colors */
  99 GLfloat colors[COLORSETS][2][3] =
 100   {
 101     {{0.43, 0.54, 0.76}, {0.8, 0.8, 0.8}},
 102     {{0.5, 0.7, 0.9}, {0.2, 0.3, 0.6}},
 103     {{0.53725490196, 0.360784313725, 0.521568627451}, {0.6, 0.6, 0.6}},
 104     {{0.15, 0.77, 0.54}, {0.5, 0.5, 0.5}},
 105     {{0.9, 0.45, 0.0}, {0.5, 0.5, 0.5}},
 106   };
 107
 108 int board[MAXBOARD][MAXBOARD];
 109 int steps = 0, colorset = 0, BOARDSIZE = 8; /* 8 cuz its classic */
 110 double theta = 0.0;
 111
 112 Bool
 113 queens_handle_event (ModeInfo *mi, XEvent *event)
 114 {
 115   Queenscreen *c = &qs[MI_SCREEN(mi)];
 116
 117   if (event->xany.type == ButtonPress &&
 118       event->xbutton.button == Button1)
 119     {
 120       c->button_down_p = True;
 121       gltrackball_start (c->trackball,
 122                          event->xbutton.x, event->xbutton.y,
 123                          MI_WIDTH (mi), MI_HEIGHT (mi));
 124       return True;
 125     }
 126   else if (event->xany.type == ButtonRelease &&
 127            event->xbutton.button == Button1)
 128     {
 129       c->button_down_p = False;
 130       return True;
 131     }
 132   else if (event->xany.type == ButtonPress &&
 133            (event->xbutton.button == Button4 ||
 134             event->xbutton.button == Button5))
 135     {
 136       gltrackball_mousewheel (c->trackball, event->xbutton.button, 5,
 137                               !event->xbutton.state);
 138       return True;
 139     }
 140   else if (event->xany.type == MotionNotify &&
 141            c->button_down_p)
 142     {
 143       gltrackball_track (c->trackball,
 144                          event->xmotion.x, event->xmotion.y,
 145                          MI_WIDTH (mi), MI_HEIGHT (mi));
 146       return True;
 147     }
 148
 149   return False;
 150 }
 151
 152
 153
 154 /* returns true if placing a queen on column c causes a conflict */
 155 int conflictsCols(int c) {
 156   int i;
 157
 158   for(i = 0; i < BOARDSIZE; ++i)
 159     if(board[i][c])
 160       return 1;
 161
 162   return 0;
 163 }
 164
 165 /* returns true if placing a queen on (r,c) causes a diagonal conflict */
 166 int conflictsDiag(int r, int c) {
 167   int i;
 168
 169   /* positive slope */
 170   int n = r < c ? r : c;
 171   for(i = 0; i < BOARDSIZE-abs(r-c); ++i)
 172     if(board[r-n+i][c-n+i])
 173       return 1;
 174
 175   /* negative slope */
 176   n = r < BOARDSIZE - (c+1) ? r : BOARDSIZE - (c+1);
 177   for(i = 0; i < BOARDSIZE-abs(BOARDSIZE - (1+r+c)); ++i)
 178     if(board[r-n+i][c+n-i])
 179       return 1;
 180
 181   return 0;
 182 }
 183
 184 /* returns true if placing a queen at (r,c) causes a conflict */
 185 int conflicts(int r, int c) {
 186   return !conflictsCols(c) ? conflictsDiag(r, c) : 1;
 187 }
 188
 189 /* clear board */
 190 void blank(void) {
 191   int i, j;
 192
 193   for(i = 0; i < MAXBOARD; ++i)
 194     for(j = 0; j < MAXBOARD; ++j)
 195       board[i][j] = NONE;
 196 }
 197
 198 /* recursively determine solution */
 199 int findSolution(int row, int col) {
 200   if(row == BOARDSIZE)
 201     return 1;
 202
 203   while(col < BOARDSIZE) {
 204     if(!conflicts(row, col)) {
 205       board[row][col] = 1;
 206
 207       if(findSolution(row+1, 0))
 208         return 1;
 209
 210       board[row][col] = 0;
 211     }
 212
 213     ++col;
 214   }
 215
 216   return 0;
 217 }
 218
 219 /** driver for finding solution */
 220 void go(void) { while(!findSolution(0, random()%BOARDSIZE)); }
 221
 222 /* lighting variables */
 223 GLfloat front_shininess[] = {60.0};
 224 GLfloat front_specular[] = {0.4, 0.4, 0.4, 1.0};
 225 GLfloat ambient[] = {0.3, 0.3, 0.3, 1.0};
 226 GLfloat diffuse[] = {0.8, 0.8, 0.8, 1.0};
 227 GLfloat position[] = { 0.0, 5.0, 5.0, 1.0 };
 228 GLfloat lmodel_ambient[] = {0.6, 0.6, 0.6, 1.0};
 229 GLfloat lmodel_twoside[] = {GL_TRUE};
 230
 231 /* configure lighting */
 232 void setup_lights(void) {
 233
 234   /* setup twoside lighting */
 235   glLightfv(GL_LIGHT0, GL_AMBIENT, ambient);
 236   glLightfv(GL_LIGHT0, GL_DIFFUSE, diffuse);
 237   glLightfv(GL_LIGHT0, GL_POSITION, position);
 238   glEnable(GL_LIGHTING);
 239   glEnable(GL_LIGHT0);
 240
 241   /* setup material properties */
 242   glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, front_shininess);
 243   glMaterialfv(GL_FRONT_AND_BACK, GL_SPECULAR, front_specular);
 244
 245   glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
 246 }
 247
 248 #define    checkImageWidth 8
 249 #define    checkImageHeight 8
 250 GLubyte checkImage[checkImageWidth][checkImageHeight][3];
 251
 252 /* return alpha value for fading */
 253 GLfloat findAlpha(void) {
 254   return steps < 128 ? steps/128.0 : steps < 1024-128 ?1.0:(1024-steps)/128.0;
 255 }
 256
 257 /* draw pieces */
 258 void drawPieces(void) {
 259   int i, j;
 260
 261   for(i = 0; i < BOARDSIZE; ++i) {
 262     for(j = 0; j < BOARDSIZE; ++j) {
 263       if(board[i][j]) {
 264         glColor3fv(colors[colorset][i%2]);
 265         glCallList(QUEEN);
 266       }
 267
 268       glTranslatef(1.0, 0.0, 0.0);
 269     }
 270
 271     glTranslatef(-1.0*BOARDSIZE, 0.0, 1.0);
 272   }
 273 }
 274
 275 /** reflectionboard */
 276 void draw_reflections(void) {
 277   int i, j;
 278
 279   glEnable(GL_STENCIL_TEST);
 280   glStencilFunc(GL_ALWAYS, 1, 1);
 281   glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
 282   glColorMask(0,0,0,0);
 283   glDisable(GL_CULL_FACE);
 284
 285   glDisable(GL_DEPTH_TEST);
 286   glBegin(GL_QUADS);
 287
 288   /* only draw white squares */
 289   for(i = 0; i < BOARDSIZE; ++i) {
 290     for(j = (BOARDSIZE+i) % 2; j < BOARDSIZE; j += 2) {
 291       glVertex3f(i, 0.0, j + 1.0);
 292       glVertex3f(i + 1.0, 0.0, j + 1.0);
 293       glVertex3f(i + 1.0, 0.0, j);
 294       glVertex3f(i, 0.0, j);
 295     }
 296   }
 297   glEnd();
 298   glEnable(GL_DEPTH_TEST);
 299
 300   glColorMask(1, 1, 1, 1);
 301   glStencilFunc(GL_EQUAL, 1, 1);
 302   glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
 303
 304   glPushMatrix();
 305   glScalef(1.0, -1.0, 1.0);
 306   glTranslatef(0.5, 0.001, 0.5);
 307   glLightfv(GL_LIGHT0, GL_POSITION, position);
 308   drawPieces();
 309   glPopMatrix();
 310   glDisable(GL_STENCIL_TEST);
 311
 312   /* replace lights */
 313   glLightfv(GL_LIGHT0, GL_POSITION, position);
 314
 315   glEnable(GL_CULL_FACE);
 316   glCullFace(GL_BACK);
 317   glColorMask(1,1,1,1);
 318 }
 319
 320 /* draw board */
 321 void drawBoard(void) {
 322   int i, j;
 323
 324   glBegin(GL_QUADS);
 325
 326   for(i = 0; i < BOARDSIZE; ++i)
 327     for(j = 0; j < BOARDSIZE; ++j) {
 328       int par = (i-j+BOARDSIZE)%2;
 329       glColor4f(colors[colorset][par][0],
 330                 colors[colorset][par][1],
 331                 colors[colorset][par][2],
 332                 0.70);
 333       glNormal3f(0.0, 1.0, 0.0);
 334       glVertex3f(i, 0.0, j + 1.0);
 335       glVertex3f(i + 1.0, 0.0, j + 1.0);
 336       glVertex3f(i + 1.0, 0.0, j);
 337       glVertex3f(i, 0.0, j);
 338     }
 339
 340   glEnd();
 341 }
 342
 343 void display(Queenscreen *c) {
 344   glClear(clearbits);
 345
 346   glMatrixMode(GL_MODELVIEW);
 347   glLoadIdentity();
 348
 349   /* setup light attenuation */
 350   glEnable(GL_COLOR_MATERIAL);
 351   glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 0.8/(0.01+findAlpha()));
 352   glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.06);
 353
 354   /** setup perspective */
 355   glTranslatef(0.0, 0.0, -1.5*BOARDSIZE);
 356   glRotatef(30.0, 1.0, 0.0, 0.0);
 357   gltrackball_rotate (c->trackball);
 358   glRotatef(theta*100, 0.0, 1.0, 0.0);
 359   glTranslatef(-0.5*BOARDSIZE, 0.0, -0.5*BOARDSIZE);
 360
 361   /* find light positions */
 362   position[0] = BOARDSIZE/2.0 + BOARDSIZE/1.4*-sin(theta*100*M_PI/180.0);
 363   position[2] = BOARDSIZE/2.0 + BOARDSIZE/1.4*cos(theta*100*M_PI/180.0);
 364   position[1] = 6.0;
 365
 366   if(!wire) {
 367     glEnable(GL_LIGHTING);
 368     glLightfv(GL_LIGHT0, GL_POSITION, position);
 369     glEnable(GL_LIGHT0);
 370   }
 371
 372   /* draw reflections */
 373   if(!wire) {
 374     draw_reflections();
 375     glEnable(GL_BLEND);
 376   }
 377   drawBoard();
 378   if(!wire)
 379     glDisable(GL_BLEND);
 380
 381   glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.1);
 382
 383   glTranslatef(0.5, 0.0, 0.5);
 384   drawPieces();
 385
 386   /* rotate camera */
 387   if(!c->button_down_p)
 388     theta += .002;
 389
 390   /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
 391   if(++steps == 1024) {
 392     steps = 0;
 393     blank();
 394     BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
 395     colorset = (colorset+1)%COLORSETS;
 396     go();
 397   }
 398 }
 399
 400 int schunks = 15;
 401 GLfloat spidermodel[][3] =
 402   {
 403     {0.48, 0.48, 0.22},
 404     {0.48, 0.34, 0.18},
 405     {0.34, 0.34, 0.10},
 406     {0.34, 0.18, 0.30},
 407     {0.18, 0.14, 0.38},
 408     {0.14, 0.29, 0.01},
 409     {0.29, 0.18, 0.18},
 410     {0.18, 0.18, 0.16},
 411     {0.18, 0.20, 0.26},
 412     {0.20, 0.27, 0.14},
 413     {0.27, 0.24, 0.08},
 414     {0.24, 0.17, 0.00},
 415     {0.17, 0.095, 0.08},
 416     {0.095, 0.07, 0.00},
 417     {0.07, 0.00, 0.12},
 418   };
 419
 420 #define EPSILON 0.001
 421
 422 /** draws cylindermodel */
 423 void draw_model(int chunks, GLfloat model[][3], int r) {
 424   int i = 0;
 425   GLUquadricObj *quadric = gluNewQuadric();
 426   glPushMatrix();
 427   glRotatef(-90.0, 1.0, 0.0, 0.0);
 428
 429   for(i = 0; i < chunks; ++i) {
 430     if(model[i][0] > EPSILON || model[i][1] > EPSILON)
 431       gluCylinder(quadric, model[i][0], model[i][1], model[i][2], r, 1);
 432     glTranslatef(0.0, 0.0, model[i][2]);
 433   }
 434
 435   glPopMatrix();
 436 }
 437
 438 void reshape_queens(ModeInfo *mi, int width, int height) {
 439   GLfloat h = (GLfloat) height / (GLfloat) width;
 440   glViewport(0,0, width, height);
 441   glMatrixMode(GL_PROJECTION);
 442   glLoadIdentity();
 443   gluPerspective(45, 1/h, 2.0, 30.0);
 444   glMatrixMode(GL_MODELVIEW);
 445 }
 446
 447 void init_queens(ModeInfo *mi) {
 448   int screen = MI_SCREEN(mi);
 449   Queenscreen *c;
 450   wire = MI_IS_WIREFRAME(mi);
 451
 452   if(!qs &&
 453      !(qs = (Queenscreen *) calloc(MI_NUM_SCREENS(mi), sizeof(Queenscreen))))
 454     return;
 455
 456   c = &qs[screen];
 457   c->window = MI_WINDOW(mi);
 458   c->trackball = gltrackball_init ();
 459
 460   if((c->glx_context = init_GL(mi)))
 461     reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
 462   else
 463     MI_CLEARWINDOW(mi);
 464
 465   glClearColor(0.0, 0.0, 0.0, 0.0);
 466   glNewList(QUEEN, GL_COMPILE);
 467   draw_model(schunks, spidermodel, 24);
 468   glEndList();
 469
 470   if(flat)
 471     glShadeModel(GL_FLAT);
 472
 473   clearbits = GL_COLOR_BUFFER_BIT;
 474
 475   glColorMaterial(GL_FRONT, GL_DIFFUSE);
 476   glEnable(GL_COLOR_MATERIAL);
 477
 478   if(!wire) {
 479     setup_lights();
 480     glEnable(GL_DEPTH_TEST);
 481     clearbits |= GL_DEPTH_BUFFER_BIT;
 482     clearbits |= GL_STENCIL_BUFFER_BIT;
 483     glEnable(GL_CULL_FACE);
 484     glCullFace(GL_BACK);
 485   }
 486   else
 487     glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
 488
 489   /* find a solution */
 490   go();
 491 }
 492
 493 void draw_queens(ModeInfo *mi) {
 494   Queenscreen *c = &qs[MI_SCREEN(mi)];
 495   Window w = MI_WINDOW(mi);
 496   Display *disp = MI_DISPLAY(mi);
 497
 498   if(!c->glx_context)
 499     return;
 500
 501   glXMakeCurrent(disp, w, *(c->glx_context));
 502
 503   display(c);
 504
 505   if(mi->fps_p) do_fps(mi);
 506   glFinish();
 507   glXSwapBuffers(disp, w);
 508 }
 509
 510 void release_queens(ModeInfo *mi) {
 511   if(qs)
 512     free((void *) qs);
 513
 514   FreeAllGL(MI);
 515 }
 516
 517 #endif