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 release_queens 0
26 # include "xlockmore.h"
27
28 #else
29 # include "xlock.h"
30 #endif
31
32 #ifdef HAVE_JWXYZ
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", NULL,
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
queens_handle_event(ModeInfo * mi,XEvent * event)110 queens_handle_event (ModeInfo *mi, XEvent *event)
111 {
112 Queenscreen *qs = &qss[MI_SCREEN(mi)];
113
114 if (gltrackball_event_handler (event, qs->trackball,
115 MI_WIDTH (mi), MI_HEIGHT (mi),
116 &qs->button_down_p))
117 return True;
118 else if (screenhack_event_helper (MI_DISPLAY(mi), MI_WINDOW(mi), event))
119 {
120 qs->steps = 1024 - 1;
121 return True;
122 }
123
124 return False;
125 }
126
127
128
129 /* returns true if placing a queen on column c causes a conflict */
conflictsCols(Queenscreen * qs,int c)130 static int conflictsCols(Queenscreen *qs, int c)
131 {
132 int i;
133
134 for(i = 0; i < qs->BOARDSIZE; ++i)
135 if(qs->board[i][c])
136 return 1;
137
138 return 0;
139 }
140
141 /* returns true if placing a queen on (r,c) causes a diagonal conflict */
conflictsDiag(Queenscreen * qs,int r,int c)142 static int conflictsDiag(Queenscreen *qs, int r, int c)
143 {
144 int i;
145
146 /* positive slope */
147 int n = r < c ? r : c;
148 for(i = 0; i < qs->BOARDSIZE-abs(r-c); ++i)
149 if(qs->board[r-n+i][c-n+i])
150 return 1;
151
152 /* negative slope */
153 n = r < qs->BOARDSIZE - (c+1) ? r : qs->BOARDSIZE - (c+1);
154 for(i = 0; i < qs->BOARDSIZE-abs(qs->BOARDSIZE - (1+r+c)); ++i)
155 if(qs->board[r-n+i][c+n-i])
156 return 1;
157
158 return 0;
159 }
160
161 /* returns true if placing a queen at (r,c) causes a conflict */
conflicts(Queenscreen * qs,int r,int c)162 static int conflicts(Queenscreen *qs, int r, int c)
163 {
164 return !conflictsCols(qs, c) ? conflictsDiag(qs, r, c) : 1;
165 }
166
167 /* clear board */
blank(Queenscreen * qs)168 static void blank(Queenscreen *qs)
169 {
170 int i, j;
171
172 for(i = 0; i < MAXBOARD; ++i)
173 for(j = 0; j < MAXBOARD; ++j)
174 qs->board[i][j] = NONE;
175 }
176
177 /* recursively determine solution */
findSolution(Queenscreen * qs,int row,int col)178 static int findSolution(Queenscreen *qs, int row, int col)
179 {
180 if(row == qs->BOARDSIZE)
181 return 1;
182
183 while(col < qs->BOARDSIZE) {
184 if(!conflicts(qs, row, col)) {
185 qs->board[row][col] = 1;
186
187 if(findSolution(qs, row+1, 0))
188 return 1;
189
190 qs->board[row][col] = 0;
191 }
192
193 ++col;
194 }
195
196 return 0;
197 }
198
199 /** driver for finding solution */
go(Queenscreen * qs)200 static void go(Queenscreen *qs) { while(!findSolution(qs, 0, random()%qs->BOARDSIZE)); }
201
202 /* lighting variables */
203 static const GLfloat front_shininess[] = {60.0};
204 static const GLfloat front_specular[] = {0.4, 0.4, 0.4, 1.0};
205 static const GLfloat ambient[] = {0.3, 0.3, 0.3, 1.0};
206 static const GLfloat diffuse[] = {0.8, 0.8, 0.8, 1.0};
207
208 /* configure lighting */
setup_lights(Queenscreen * qs)209 static void setup_lights(Queenscreen *qs)
210 {
211
212 /* setup twoside lighting */
213 glLightfv(GL_LIGHT0, GL_AMBIENT, ambient);
214 glLightfv(GL_LIGHT0, GL_DIFFUSE, diffuse);
215 glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
216 glEnable(GL_LIGHTING);
217 glEnable(GL_LIGHT0);
218
219 /* setup material properties */
220 glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, front_shininess);
221 glMaterialfv(GL_FRONT_AND_BACK, GL_SPECULAR, front_specular);
222
223 glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
224 }
225
226 #define checkImageWidth 8
227 #define checkImageHeight 8
228 /*static GLubyte checkImage[checkImageWidth][checkImageHeight][3];*/
229
230 /* return alpha value for fading */
findAlpha(Queenscreen * qs)231 static GLfloat findAlpha(Queenscreen *qs)
232 {
233 return qs->steps < 128 ? qs->steps/128.0 : qs->steps < 1024-128 ?1.0:(1024-qs->steps)/128.0;
234 }
235
236 /* draw pieces */
drawPieces(Queenscreen * qs)237 static int drawPieces(Queenscreen *qs)
238 {
239 int i, j;
240 int polys = 0;
241
242 for(i = 0; i < qs->BOARDSIZE; ++i) {
243 for(j = 0; j < qs->BOARDSIZE; ++j) {
244 if(qs->board[i][j]) {
245 glColor3fv(colors[qs->colorset][i%2]);
246 glCallList(qs->queen_list);
247 polys += qs->queen_polys;
248 }
249
250 glTranslatef(1.0, 0.0, 0.0);
251 }
252
253 glTranslatef(-1.0*qs->BOARDSIZE, 0.0, 1.0);
254 }
255 return polys;
256 }
257
258 /** reflectionboard */
draw_reflections(Queenscreen * qs)259 static int draw_reflections(Queenscreen *qs)
260 {
261 int i, j;
262 int polys = 0;
263
264 glEnable(GL_STENCIL_TEST);
265 glStencilFunc(GL_ALWAYS, 1, 1);
266 glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
267 glColorMask(0,0,0,0);
268 glDisable(GL_CULL_FACE);
269
270 glDisable(GL_DEPTH_TEST);
271 glBegin(GL_QUADS);
272
273 /* only draw white squares */
274 for(i = 0; i < qs->BOARDSIZE; ++i) {
275 for(j = (qs->BOARDSIZE+i) % 2; j < qs->BOARDSIZE; j += 2) {
276 glVertex3f(i, 0.0, j + 1.0);
277 glVertex3f(i + 1.0, 0.0, j + 1.0);
278 glVertex3f(i + 1.0, 0.0, j);
279 glVertex3f(i, 0.0, j);
280 polys++;
281 }
282 }
283 glEnd();
284 glEnable(GL_DEPTH_TEST);
285
286 glColorMask(1, 1, 1, 1);
287 glStencilFunc(GL_EQUAL, 1, 1);
288 glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
289
290 glPushMatrix();
291 glScalef(1.0, -1.0, 1.0);
292 glTranslatef(0.5, 0.001, 0.5);
293 glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
294 polys += drawPieces(qs);
295 glPopMatrix();
296 glDisable(GL_STENCIL_TEST);
297
298 /* replace lights */
299 glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
300
301 glEnable(GL_CULL_FACE);
302 glCullFace(GL_BACK);
303 glColorMask(1,1,1,1);
304 return polys;
305 }
306
307 /* draw board */
drawBoard(Queenscreen * qs)308 static int drawBoard(Queenscreen *qs)
309 {
310 int i, j;
311 int polys = 0;
312
313 glBegin(GL_QUADS);
314
315 for(i = 0; i < qs->BOARDSIZE; ++i)
316 for(j = 0; j < qs->BOARDSIZE; ++j) {
317 int par = (i-j+qs->BOARDSIZE)%2;
318 glColor4f(colors[qs->colorset][par][0],
319 colors[qs->colorset][par][1],
320 colors[qs->colorset][par][2],
321 0.70);
322 glNormal3f(0.0, 1.0, 0.0);
323 glVertex3f(i, 0.0, j + 1.0);
324 glVertex3f(i + 1.0, 0.0, j + 1.0);
325 glVertex3f(i + 1.0, 0.0, j);
326 glVertex3f(i, 0.0, j);
327 polys++;
328 }
329
330 glEnd();
331
332 {
333 GLfloat off = 0.01;
334 GLfloat w = qs->BOARDSIZE;
335 GLfloat h = 0.1;
336
337 /* Give the board a slight lip. */
338 /* #### oops, normals are wrong here, but you can't tell */
339
340 glColor3f(0.3, 0.3, 0.3);
341 glBegin (GL_QUADS);
342 glVertex3f (0, 0, 0);
343 glVertex3f (0, -h, 0);
344 glVertex3f (0, -h, w);
345 glVertex3f (0, 0, w);
346
347 glVertex3f (0, 0, w);
348 glVertex3f (0, -h, w);
349 glVertex3f (w, -h, w);
350 glVertex3f (w, 0, w);
351
352 glVertex3f (w, 0, w);
353 glVertex3f (w, -h, w);
354 glVertex3f (w, -h, 0);
355 glVertex3f (w, 0, 0);
356
357 glVertex3f (w, 0, 0);
358 glVertex3f (w, -h, 0);
359 glVertex3f (0, -h, 0);
360 glVertex3f (0, 0, 0);
361
362 glVertex3f (0, -h, 0);
363 glVertex3f (w, -h, 0);
364 glVertex3f (w, -h, w);
365 glVertex3f (0, -h, w);
366 glEnd();
367 polys += 4;
368
369 /* Fill in the underside of the board with an invisible black box
370 to hide the reflections that are not on tiles. Probably there's
371 a way to do this with stencils instead.
372 */
373 w -= off*2;
374 h = 5;
375
376 glPushMatrix();
377 glTranslatef (off, 0, off);
378 glDisable(GL_LIGHTING);
379 glColor3f(0,0,0);
380 glBegin (GL_QUADS);
381 glVertex3f (0, 0, 0);
382 glVertex3f (0, -h, 0);
383 glVertex3f (0, -h, w);
384 glVertex3f (0, 0, w);
385
386 glVertex3f (0, 0, w);
387 glVertex3f (0, -h, w);
388 glVertex3f (w, -h, w);
389 glVertex3f (w, 0, w);
390
391 glVertex3f (w, 0, w);
392 glVertex3f (w, -h, w);
393 glVertex3f (w, -h, 0);
394 glVertex3f (w, 0, 0);
395
396 glVertex3f (w, 0, 0);
397 glVertex3f (w, -h, 0);
398 glVertex3f (0, -h, 0);
399 glVertex3f (0, 0, 0);
400
401 glVertex3f (0, -h, 0);
402 glVertex3f (w, -h, 0);
403 glVertex3f (w, -h, w);
404 glVertex3f (0, -h, w);
405 glEnd();
406 polys += 4;
407 glPopMatrix();
408 if (!wire)
409 glEnable(GL_LIGHTING);
410 }
411
412 return polys;
413 }
414
display(ModeInfo * mi,Queenscreen * qs)415 static int display(ModeInfo *mi, Queenscreen *qs)
416 {
417 int max = 1024;
418 int polys = 0;
419 glClear(clearbits);
420
421 glMatrixMode(GL_MODELVIEW);
422 glLoadIdentity();
423
424 glRotatef(current_device_rotation(), 0, 0, 1);
425
426 /* setup light attenuation */
427 /* #### apparently this does nothing */
428 glEnable(GL_COLOR_MATERIAL);
429 glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 0.8/(0.01+findAlpha(qs)));
430 glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.06);
431
432 /** setup perspective */
433 glTranslatef(0.0, 0.0, -1.5*qs->BOARDSIZE);
434 glRotatef(30.0, 1.0, 0.0, 0.0);
435 gltrackball_rotate (qs->trackball);
436 glRotatef(qs->theta*100, 0.0, 1.0, 0.0);
437 glTranslatef(-0.5*qs->BOARDSIZE, 0.0, -0.5*qs->BOARDSIZE);
438
439 /* find light positions */
440 qs->position[0] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*-sin(qs->theta*100*M_PI/180.0);
441 qs->position[2] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*cos(qs->theta*100*M_PI/180.0);
442 qs->position[1] = 6.0;
443
444 if(!wire) {
445 glEnable(GL_LIGHTING);
446 glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
447 glEnable(GL_LIGHT0);
448 }
449
450 /* Since the lighting attenuation trick up there doesn't seem to be working,
451 let's drop the old board down and drop the new board in. */
452 if (qs->steps < (max/8.0)) {
453 GLfloat y = qs->steps / (max/8.0);
454 y = sin (M_PI/2 * y);
455 glTranslatef (0, 10 - (y * 10), 0);
456 } else if (qs->steps > max-(max/8.0)) {
457 GLfloat y = (qs->steps - (max-(max/8.0))) / (GLfloat) (max/8.0);
458 y = 1 - sin (M_PI/2 * (1-y));
459 glTranslatef (0, -y * 15, 0);
460 }
461
462 /* draw reflections */
463 if(!wire) {
464 polys += draw_reflections(qs);
465 glEnable(GL_BLEND);
466 }
467 polys += drawBoard(qs);
468 if(!wire)
469 glDisable(GL_BLEND);
470
471 glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.1);
472
473 glTranslatef(0.5, 0.0, 0.5);
474 polys += drawPieces(qs);
475
476 /* rotate camera */
477 if(!qs->button_down_p)
478 qs->theta += .002;
479
480 /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
481 if(++qs->steps == max) {
482 qs->steps = 0;
483 blank(qs);
484 qs->BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
485 qs->colorset = (qs->colorset+1)%COLORSETS;
486 go(qs);
487 }
488 return polys;
489 }
490
491 #define EPSILON 0.001
492
493 #if 0
494 /** draws cylindermodel */
495 static int draw_model(int chunks, const GLfloat model[][3], int r)
496 {
497 int i = 0;
498 int polys = 0;
499 glPushMatrix();
500 glRotatef(-90.0, 1.0, 0.0, 0.0);
501
502 for(i = 0; i < chunks; ++i) {
503 if(model[i][0] > EPSILON || model[i][1] > EPSILON) {
504 polys += tube (0, 0, 0,
505 0, 0, model[i][1],
506 model[i][0], 0,
507 r, False, False, False);
508 /* gluCylinder(quadric, model[i][0], model[i][1], model[i][2], r, 1);
509 polys += r;*/
510 }
511 glTranslatef(0.0, 0.0, model[i][2]);
512 }
513
514 glPopMatrix();
515 return polys;
516 }
517 #endif
518
reshape_queens(ModeInfo * mi,int width,int height)519 ENTRYPOINT void reshape_queens(ModeInfo *mi, int width, int height)
520 {
521 GLfloat h = (GLfloat) height / (GLfloat) width;
522 int y = 0;
523
524 if (width > height * 5) { /* tiny window: show middle */
525 height = width;
526 y = -height/2;
527 h = height / (GLfloat) width;
528 }
529 glViewport(0,y, width, height);
530 glMatrixMode(GL_PROJECTION);
531 glLoadIdentity();
532 gluPerspective(45, 1/h, 2.0, 30.0);
533 glMatrixMode(GL_MODELVIEW);
534 }
535
init_queens(ModeInfo * mi)536 ENTRYPOINT void init_queens(ModeInfo *mi)
537 {
538 int screen = MI_SCREEN(mi);
539 Queenscreen *qs;
540 int poly_counts[PIECES];
541 wire = MI_IS_WIREFRAME(mi);
542
543 # ifdef HAVE_JWZGLES /* #### glPolygonMode other than GL_FILL unimplemented */
544 wire = 0;
545 # endif
546
547 MI_INIT (mi, qss);
548
549 qs = &qss[screen];
550 qs->window = MI_WINDOW(mi);
551
552 if((qs->glx_context = init_GL(mi)))
553 reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
554 else
555 MI_CLEARWINDOW(mi);
556
557 qs->trackball = gltrackball_init (False);
558
559 qs->BOARDSIZE = 8; /* 8 cuz its classic */
560
561 chessmodels_gen_lists(-1, poly_counts);
562 qs->queen_list = QUEEN;
563 qs->queen_polys = poly_counts[QUEEN];
564
565 /* find a solution */
566 go(qs);
567 }
568
draw_queens(ModeInfo * mi)569 ENTRYPOINT void draw_queens(ModeInfo *mi)
570 {
571 Queenscreen *qs = &qss[MI_SCREEN(mi)];
572 Window w = MI_WINDOW(mi);
573 Display *disp = MI_DISPLAY(mi);
574
575 if(!qs->glx_context)
576 return;
577
578 glXMakeCurrent(disp, w, *qs->glx_context);
579
580 if(flat)
581 glShadeModel(GL_FLAT);
582
583 clearbits = GL_COLOR_BUFFER_BIT;
584
585 glColorMaterial(GL_FRONT, GL_DIFFUSE);
586 glEnable(GL_COLOR_MATERIAL);
587
588 if(!wire) {
589 setup_lights(qs);
590 glEnable(GL_DEPTH_TEST);
591 clearbits |= GL_DEPTH_BUFFER_BIT;
592 clearbits |= GL_STENCIL_BUFFER_BIT;
593 glEnable(GL_CULL_FACE);
594 glCullFace(GL_BACK);
595 }
596 else
597 glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
598
599 mi->polygon_count = display(mi, qs);
600 mi->recursion_depth = qs->BOARDSIZE;
601
602 if(mi->fps_p) do_fps(mi);
603 glFinish();
604 glXSwapBuffers(disp, w);
605 }
606
607
free_queens(ModeInfo * mi)608 ENTRYPOINT void free_queens(ModeInfo *mi)
609 {
610 Queenscreen *qs = &qss[MI_SCREEN(mi)];
611 int i;
612 if (!qs->glx_context) return;
613 glXMakeCurrent (MI_DISPLAY(mi), MI_WINDOW(mi), *qs->glx_context);
614 gltrackball_free (qs->trackball);
615
616 /* this is horrible! List numbers are hardcoded! */
617 for (i = 1; i <= 20; i++)
618 if (glIsList(i)) glDeleteLists(i, 1);
619 }
620
621 XSCREENSAVER_MODULE ("Queens", queens)
622
623 #endif
624