c1871f53106365cbad466350ccb96e21600bff35
[xscreensaver] / 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 #ifdef STANDALONE
21 #define DEFAULTS       "*delay:       20000 \n" \
22                        "*showFPS:     False \n" \
23                        "*wireframe:   False \n" \
24
25 # define refresh_queens 0
26 # include "xlockmore.h"
27
28 #else
29 # include "xlock.h"
30 #endif
31
32 #ifdef HAVE_COCOA
33 # include "jwxyz.h"
34 #else
35 # include <X11/Xlib.h>
36 # include <GL/gl.h>
37 # include <GL/glu.h>
38 #endif
39
40 #ifdef HAVE_JWZGLES
41 # include "jwzgles.h"
42 #endif /* HAVE_JWZGLES */
43
44 #ifdef USE_GL
45
46 #include "gltrackball.h"
47 #include "chessmodels.h"
48
49 #undef countof
50 #define countof(x) (sizeof((x))/sizeof((*x)))
51
52 static XrmOptionDescRec opts[] = {
53   {"+rotate", ".queens.rotate", XrmoptionNoArg, "false" },
54   {"-rotate", ".queens.rotate", XrmoptionNoArg, "true" },
55   {"+flat", ".queens.flat", XrmoptionNoArg, "false" },
56   {"-flat", ".queens.flat", XrmoptionNoArg, "true" },
57 };
58
59 static int rotate, wire, clearbits, flat;
60
61 static argtype vars[] = {
62   {&rotate, "rotate", "Rotate", "True",  t_Bool},
63   {&flat,   "flat",   "Flat",   "False", t_Bool},
64 };
65
66 ENTRYPOINT ModeSpecOpt queens_opts = {countof(opts), opts, countof(vars), vars, NULL};
67
68 #ifdef USE_MODULES
69 ModStruct   queens_description =
70 {"queens", "init_queens", "draw_queens", "release_queens",
71  "draw_queens", "init_queens", NULL, &queens_opts,
72  1000, 1, 2, 1, 4, 1.0, "",
73  "Queens", 0, NULL};
74
75 #endif
76
77 #define NONE 0
78 #define MINBOARD 5
79 #define MAXBOARD 10
80 #define COLORSETS 5
81
82 typedef struct {
83   GLXContext *glx_context;
84   Window window;
85   trackball_state *trackball;
86   Bool button_down_p;
87   GLfloat position[4];
88   int queen_list;
89
90   int board[MAXBOARD][MAXBOARD];
91   int steps, colorset, BOARDSIZE;
92   double theta;
93   int queen_polys;
94
95 } Queenscreen;
96
97 static Queenscreen *qss = NULL;
98
99 /* definition of white/black colors */
100 static const GLfloat colors[COLORSETS][2][3] = 
101   { 
102     {{0.43, 0.54, 0.76}, {0.8, 0.8, 0.8}},
103     {{0.5, 0.7, 0.9}, {0.2, 0.3, 0.6}},
104     {{0.53725490196, 0.360784313725, 0.521568627451}, {0.6, 0.6, 0.6}},
105     {{0.15, 0.77, 0.54}, {0.5, 0.5, 0.5}},
106     {{0.9, 0.45, 0.0}, {0.5, 0.5, 0.5}},
107   };
108
109 ENTRYPOINT Bool
110 queens_handle_event (ModeInfo *mi, XEvent *event)
111 {
112   Queenscreen *qs = &qss[MI_SCREEN(mi)];
113
114   if (event->xany.type == ButtonPress &&
115       event->xbutton.button == Button1)
116     {
117       qs->button_down_p = True;
118       gltrackball_start (qs->trackball,
119                          event->xbutton.x, event->xbutton.y,
120                          MI_WIDTH (mi), MI_HEIGHT (mi));
121       return True;
122     }
123   else if (event->xany.type == ButtonRelease &&
124            event->xbutton.button == Button1)
125     {
126       qs->button_down_p = False;
127       return True;
128     }
129   else if (event->xany.type == ButtonPress &&
130            (event->xbutton.button == Button4 ||
131             event->xbutton.button == Button5 ||
132             event->xbutton.button == Button6 ||
133             event->xbutton.button == Button7))
134     {
135       gltrackball_mousewheel (qs->trackball, event->xbutton.button, 5,
136                               !event->xbutton.state);
137       return True;
138     }
139   else if (event->xany.type == MotionNotify &&
140            qs->button_down_p)
141     {
142       gltrackball_track (qs->trackball,
143                          event->xmotion.x, event->xmotion.y,
144                          MI_WIDTH (mi), MI_HEIGHT (mi));
145       return True;
146     }
147
148   return False;
149 }
150
151
152
153 /* returns true if placing a queen on column c causes a conflict */
154 static int conflictsCols(Queenscreen *qs, int c) 
155 {
156   int i;
157
158   for(i = 0; i < qs->BOARDSIZE; ++i)
159     if(qs->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 static int conflictsDiag(Queenscreen *qs, int r, int c) 
167 {
168   int i;
169
170   /* positive slope */
171   int n = r < c ? r : c;
172   for(i = 0; i < qs->BOARDSIZE-abs(r-c); ++i)
173     if(qs->board[r-n+i][c-n+i])
174       return 1;
175
176   /* negative slope */
177   n = r < qs->BOARDSIZE - (c+1) ? r : qs->BOARDSIZE - (c+1);
178   for(i = 0; i < qs->BOARDSIZE-abs(qs->BOARDSIZE - (1+r+c)); ++i)
179     if(qs->board[r-n+i][c+n-i])
180       return 1;
181   
182   return 0;
183 }
184
185 /* returns true if placing a queen at (r,c) causes a conflict */
186 static int conflicts(Queenscreen *qs, int r, int c) 
187 {
188   return !conflictsCols(qs, c) ? conflictsDiag(qs, r, c) : 1;
189 }
190
191 /* clear board */
192 static void blank(Queenscreen *qs) 
193 {
194   int i, j;
195
196   for(i = 0; i < MAXBOARD; ++i)
197     for(j = 0; j < MAXBOARD; ++j)
198       qs->board[i][j] = NONE;
199 }
200
201 /* recursively determine solution */
202 static int findSolution(Queenscreen *qs, int row, int col) 
203 {
204   if(row == qs->BOARDSIZE)
205     return 1;
206   
207   while(col < qs->BOARDSIZE) {
208     if(!conflicts(qs, row, col)) {
209       qs->board[row][col] = 1;
210
211       if(findSolution(qs, row+1, 0))
212         return 1;
213
214       qs->board[row][col] = 0;
215     }
216
217     ++col;
218   }
219
220   return 0;
221 }
222
223 /** driver for finding solution */
224 static void go(Queenscreen *qs) { while(!findSolution(qs, 0, random()%qs->BOARDSIZE)); }
225
226 /* lighting variables */
227 static const GLfloat front_shininess[] = {60.0};
228 static const GLfloat front_specular[] = {0.4, 0.4, 0.4, 1.0};
229 static const GLfloat ambient[] = {0.3, 0.3, 0.3, 1.0};
230 static const GLfloat diffuse[] = {0.8, 0.8, 0.8, 1.0};
231
232 /* configure lighting */
233 static void setup_lights(Queenscreen *qs) 
234 {
235
236   /* setup twoside lighting */
237   glLightfv(GL_LIGHT0, GL_AMBIENT, ambient);
238   glLightfv(GL_LIGHT0, GL_DIFFUSE, diffuse);
239   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
240   glEnable(GL_LIGHTING);
241   glEnable(GL_LIGHT0);
242
243   /* setup material properties */
244   glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, front_shininess);
245   glMaterialfv(GL_FRONT_AND_BACK, GL_SPECULAR, front_specular);
246
247   glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
248 }
249
250 #define    checkImageWidth 8
251 #define    checkImageHeight 8
252 /*static GLubyte checkImage[checkImageWidth][checkImageHeight][3];*/
253
254 /* return alpha value for fading */
255 static GLfloat findAlpha(Queenscreen *qs) 
256 {
257   return qs->steps < 128 ? qs->steps/128.0 : qs->steps < 1024-128 ?1.0:(1024-qs->steps)/128.0;
258 }
259
260 /* draw pieces */
261 static int drawPieces(Queenscreen *qs) 
262 {
263   int i, j;
264   int polys = 0;
265
266   for(i = 0; i < qs->BOARDSIZE; ++i) {
267     for(j = 0; j < qs->BOARDSIZE; ++j) {
268       if(qs->board[i][j]) {
269         glColor3fv(colors[qs->colorset][i%2]);
270         glCallList(qs->queen_list);
271         polys += qs->queen_polys;
272       }
273       
274       glTranslatef(1.0, 0.0, 0.0);
275     }
276     
277     glTranslatef(-1.0*qs->BOARDSIZE, 0.0, 1.0);
278   }
279   return polys;
280 }
281
282 /** reflectionboard */
283 static int draw_reflections(Queenscreen *qs) 
284 {
285   int i, j;
286   int polys = 0;
287
288   glEnable(GL_STENCIL_TEST);
289   glStencilFunc(GL_ALWAYS, 1, 1);
290   glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
291   glColorMask(0,0,0,0);
292   glDisable(GL_CULL_FACE);
293
294   glDisable(GL_DEPTH_TEST);
295   glBegin(GL_QUADS);
296
297   /* only draw white squares */
298   for(i = 0; i < qs->BOARDSIZE; ++i) {
299     for(j = (qs->BOARDSIZE+i) % 2; j < qs->BOARDSIZE; j += 2) {
300       glVertex3f(i, 0.0, j + 1.0);
301       glVertex3f(i + 1.0, 0.0, j + 1.0);
302       glVertex3f(i + 1.0, 0.0, j);
303       glVertex3f(i, 0.0, j);
304       polys++;
305     }
306   }
307   glEnd();
308   glEnable(GL_DEPTH_TEST);
309
310   glColorMask(1, 1, 1, 1);
311   glStencilFunc(GL_EQUAL, 1, 1);
312   glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
313   
314   glPushMatrix(); 
315   glScalef(1.0, -1.0, 1.0);
316   glTranslatef(0.5, 0.001, 0.5);
317   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
318   polys += drawPieces(qs);
319   glPopMatrix();
320   glDisable(GL_STENCIL_TEST);
321
322   /* replace lights */
323   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
324
325   glEnable(GL_CULL_FACE);
326   glCullFace(GL_BACK);
327   glColorMask(1,1,1,1);
328   return polys;
329 }
330
331 /* draw board */
332 static int drawBoard(Queenscreen *qs) 
333 {
334   int i, j;
335   int polys = 0;
336
337   glBegin(GL_QUADS);
338
339   for(i = 0; i < qs->BOARDSIZE; ++i)
340     for(j = 0; j < qs->BOARDSIZE; ++j) {
341       int par = (i-j+qs->BOARDSIZE)%2;
342       glColor4f(colors[qs->colorset][par][0],
343                 colors[qs->colorset][par][1],
344                 colors[qs->colorset][par][2],
345                 0.70);
346       glNormal3f(0.0, 1.0, 0.0);
347       glVertex3f(i, 0.0, j + 1.0);
348       glVertex3f(i + 1.0, 0.0, j + 1.0);
349       glVertex3f(i + 1.0, 0.0, j);
350       glVertex3f(i, 0.0, j);
351       polys++;
352     }
353
354   glEnd();
355
356   {
357     GLfloat off = 0.01;
358     GLfloat w = qs->BOARDSIZE;
359     GLfloat h = 0.1;
360
361     /* Give the board a slight lip. */
362     /* #### oops, normals are wrong here, but you can't tell */
363
364     glColor3f(0.3, 0.3, 0.3);
365     glBegin (GL_QUADS);
366     glVertex3f (0,  0, 0);
367     glVertex3f (0, -h, 0);
368     glVertex3f (0, -h, w);
369     glVertex3f (0,  0, w);
370
371     glVertex3f (0,  0, w);
372     glVertex3f (0, -h, w);
373     glVertex3f (w, -h, w);
374     glVertex3f (w,  0, w);
375
376     glVertex3f (w,  0, w);
377     glVertex3f (w, -h, w);
378     glVertex3f (w, -h, 0);
379     glVertex3f (w,  0, 0);
380
381     glVertex3f (w,  0, 0);
382     glVertex3f (w, -h, 0);
383     glVertex3f (0, -h, 0);
384     glVertex3f (0,  0, 0);
385
386     glVertex3f (0, -h, 0);
387     glVertex3f (w, -h, 0);
388     glVertex3f (w, -h, w);
389     glVertex3f (0, -h, w);
390     glEnd();
391     polys += 4;
392
393     /* Fill in the underside of the board with an invisible black box
394        to hide the reflections that are not on tiles.  Probably there's
395        a way to do this with stencils instead.
396      */
397     w -= off*2;
398     h = 5;
399
400     glPushMatrix();
401     glTranslatef (off, 0, off);
402     glDisable(GL_LIGHTING);
403     glColor3f(0,0,0);
404     glBegin (GL_QUADS);
405     glVertex3f (0,  0, 0);
406     glVertex3f (0, -h, 0);
407     glVertex3f (0, -h, w);
408     glVertex3f (0,  0, w);
409
410     glVertex3f (0,  0, w);
411     glVertex3f (0, -h, w);
412     glVertex3f (w, -h, w);
413     glVertex3f (w,  0, w);
414
415     glVertex3f (w,  0, w);
416     glVertex3f (w, -h, w);
417     glVertex3f (w, -h, 0);
418     glVertex3f (w,  0, 0);
419
420     glVertex3f (w,  0, 0);
421     glVertex3f (w, -h, 0);
422     glVertex3f (0, -h, 0);
423     glVertex3f (0,  0, 0);
424
425     glVertex3f (0, -h, 0);
426     glVertex3f (w, -h, 0);
427     glVertex3f (w, -h, w);
428     glVertex3f (0, -h, w);
429     glEnd();
430     polys += 4;
431     glPopMatrix();
432     if (!wire)
433       glEnable(GL_LIGHTING);
434   }
435
436   return polys;
437 }
438
439 static int display(Queenscreen *qs) 
440 {
441   int max = 1024;
442   int polys = 0;
443   glClear(clearbits);
444   
445   glMatrixMode(GL_MODELVIEW);
446   glLoadIdentity();
447
448   glRotatef(current_device_rotation(), 0, 0, 1);
449
450   /* setup light attenuation */
451   /* #### apparently this does nothing */
452   glEnable(GL_COLOR_MATERIAL);
453   glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 0.8/(0.01+findAlpha(qs)));
454   glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.06);
455
456   /** setup perspective */
457   glTranslatef(0.0, 0.0, -1.5*qs->BOARDSIZE);
458   glRotatef(30.0, 1.0, 0.0, 0.0);
459   gltrackball_rotate (qs->trackball);
460   glRotatef(qs->theta*100, 0.0, 1.0, 0.0);
461   glTranslatef(-0.5*qs->BOARDSIZE, 0.0, -0.5*qs->BOARDSIZE);
462
463   /* find light positions */
464   qs->position[0] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*-sin(qs->theta*100*M_PI/180.0);
465   qs->position[2] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*cos(qs->theta*100*M_PI/180.0);
466   qs->position[1] = 6.0;
467
468   if(!wire) {
469     glEnable(GL_LIGHTING);
470     glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
471     glEnable(GL_LIGHT0);
472   }
473
474   /* Since the lighting attenuation trick up there doesn't seem to be working,
475      let's drop the old board down and drop the new board in. */
476   if (qs->steps < (max/8.0)) {
477     GLfloat y = qs->steps / (max/8.0);
478     y = sin (M_PI/2 * y);
479     glTranslatef (0, 10 - (y * 10), 0);
480   } else if (qs->steps > max-(max/8.0)) {
481     GLfloat y = (qs->steps - (max-(max/8.0))) / (GLfloat) (max/8.0);
482     y = 1 - sin (M_PI/2 * (1-y));
483     glTranslatef (0, -y * 15, 0);
484   }
485
486   /* draw reflections */
487   if(!wire) {
488     polys += draw_reflections(qs);
489     glEnable(GL_BLEND);
490   }
491   polys += drawBoard(qs);
492   if(!wire)
493     glDisable(GL_BLEND);
494
495   glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.1);
496
497   glTranslatef(0.5, 0.0, 0.5);
498   polys += drawPieces(qs);
499
500   /* rotate camera */
501   if(!qs->button_down_p)
502     qs->theta += .002;
503
504   /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
505   if(++qs->steps == max) {
506     qs->steps = 0;
507     blank(qs);
508     qs->BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
509     qs->colorset = (qs->colorset+1)%COLORSETS;
510     go(qs);
511   }
512   return polys;
513 }
514
515 static const GLfloat spidermodel[][3] =
516   {
517     {0.48, 0.48, 0.22},
518     {0.48, 0.34, 0.18},
519     {0.34, 0.34, 0.10},
520     {0.34, 0.18, 0.30},
521     {0.18, 0.14, 0.38},
522     {0.14, 0.29, 0.01},
523     {0.29, 0.18, 0.18},
524     {0.18, 0.18, 0.16},
525     {0.18, 0.20, 0.26},
526     {0.20, 0.27, 0.14},
527     {0.27, 0.24, 0.08},
528     {0.24, 0.17, 0.00},
529     {0.17, 0.095, 0.08},
530     {0.095, 0.07, 0.00},
531     {0.07, 0.00, 0.12},
532   };
533
534
535 #define EPSILON 0.001
536
537 #if 0
538 /** draws cylindermodel */
539 static int draw_model(int chunks, const GLfloat model[][3], int r) 
540 {
541   int i = 0;
542   int polys = 0;
543   glPushMatrix();
544   glRotatef(-90.0, 1.0, 0.0, 0.0);
545   
546   for(i = 0; i < chunks; ++i) {
547     if(model[i][0] > EPSILON || model[i][1] > EPSILON) {
548       polys += tube (0, 0, 0,
549                      0, 0, model[i][1],
550                      model[i][0], 0,
551                      r, False, False, False);
552 /*      gluCylinder(quadric, model[i][0], model[i][1], model[i][2], r, 1);
553       polys += r;*/
554     }
555     glTranslatef(0.0, 0.0, model[i][2]);
556   }
557   
558   glPopMatrix();
559   return polys;
560 }
561 #endif
562
563 ENTRYPOINT void reshape_queens(ModeInfo *mi, int width, int height) 
564 {
565   GLfloat h = (GLfloat) height / (GLfloat) width;
566   glViewport(0,0, width, height);
567   glMatrixMode(GL_PROJECTION);
568   glLoadIdentity();
569   gluPerspective(45, 1/h, 2.0, 30.0);
570   glMatrixMode(GL_MODELVIEW);
571 }
572
573 ENTRYPOINT void init_queens(ModeInfo *mi) 
574 {
575   int screen = MI_SCREEN(mi);
576   Queenscreen *qs;
577   int poly_counts[PIECES];
578   wire = MI_IS_WIREFRAME(mi);
579
580 # ifdef HAVE_JWZGLES /* #### glPolygonMode other than GL_FILL unimplemented */
581   wire = 0;
582 # endif
583
584   if(!qss && 
585      !(qss = (Queenscreen *) calloc(MI_NUM_SCREENS(mi), sizeof(Queenscreen))))
586     return;
587   
588   qs = &qss[screen];
589   qs->window = MI_WINDOW(mi);
590   
591   if((qs->glx_context = init_GL(mi)))
592     reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
593   else
594     MI_CLEARWINDOW(mi);
595
596   qs->trackball = gltrackball_init ();
597
598   qs->BOARDSIZE = 8; /* 8 cuz its classic */
599
600   chessmodels_gen_lists(-1, poly_counts);
601   qs->queen_list = QUEEN;
602   qs->queen_polys = poly_counts[QUEEN];
603
604   /* find a solution */
605   go(qs);
606 }
607
608 ENTRYPOINT void draw_queens(ModeInfo *mi) 
609 {
610   Queenscreen *qs = &qss[MI_SCREEN(mi)];
611   Window w = MI_WINDOW(mi);
612   Display *disp = MI_DISPLAY(mi);
613
614   if(!qs->glx_context)
615     return;
616
617   glXMakeCurrent(disp, w, *(qs->glx_context));
618
619   if(flat)
620     glShadeModel(GL_FLAT);
621   
622   clearbits = GL_COLOR_BUFFER_BIT;
623
624   glColorMaterial(GL_FRONT, GL_DIFFUSE);
625   glEnable(GL_COLOR_MATERIAL);
626
627   if(!wire) {
628     setup_lights(qs);
629     glEnable(GL_DEPTH_TEST);
630     clearbits |= GL_DEPTH_BUFFER_BIT;
631     clearbits |= GL_STENCIL_BUFFER_BIT;
632     glEnable(GL_CULL_FACE);
633     glCullFace(GL_BACK);
634   }
635   else
636     glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
637
638   mi->polygon_count = display(qs);
639   mi->recursion_depth = qs->BOARDSIZE;
640
641   if(mi->fps_p) do_fps(mi);
642   glFinish(); 
643   glXSwapBuffers(disp, w);
644 }
645
646 ENTRYPOINT void release_queens(ModeInfo *mi) 
647 {
648   if(qss)
649     free((void *) qss);
650   qss = 0;
651
652   FreeAllGL(mi);
653 }
654
655 XSCREENSAVER_MODULE ("Queens", queens)
656
657 #endif