summaryrefslogtreecommitdiffstats
path: root/hacks/glx/queens.c
diff options
context:
space:
mode:
Diffstat (limited to 'hacks/glx/queens.c')
-rw-r--r--hacks/glx/queens.c610
1 files changed, 610 insertions, 0 deletions
diff --git a/hacks/glx/queens.c b/hacks/glx/queens.c
new file mode 100644
index 0000000..bc9b202
--- /dev/null
+++ b/hacks/glx/queens.c
@@ -0,0 +1,610 @@
+/*
+ * queens - solves n queens problem, displays
+ * i make no claims that this is an optimal solution to the problem,
+ * good enough for xss
+ * hacked from glchess
+ *
+ * version 1.0 - May 10, 2002
+ *
+ * Copyright (C) 2002 Blair Tennessy (tennessy@cs.ubc.ca)
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation. No representations are made about the suitability of this
+ * software for any purpose. It is provided "as is" without express or
+ * implied warranty.
+ */
+
+#ifdef STANDALONE
+#define DEFAULTS "*delay: 20000 \n" \
+ "*showFPS: False \n" \
+ "*wireframe: False \n" \
+
+# define free_queens 0
+# define release_queens 0
+# include "xlockmore.h"
+
+#else
+# include "xlock.h"
+#endif
+
+#ifdef HAVE_JWXYZ
+# include "jwxyz.h"
+#else
+# include <X11/Xlib.h>
+# include <GL/gl.h>
+# include <GL/glu.h>
+#endif
+
+#ifdef HAVE_JWZGLES
+# include "jwzgles.h"
+#endif /* HAVE_JWZGLES */
+
+#ifdef USE_GL
+
+#include "gltrackball.h"
+#include "chessmodels.h"
+
+#undef countof
+#define countof(x) (sizeof((x))/sizeof((*x)))
+
+static XrmOptionDescRec opts[] = {
+ {"+rotate", ".queens.rotate", XrmoptionNoArg, "false" },
+ {"-rotate", ".queens.rotate", XrmoptionNoArg, "true" },
+ {"+flat", ".queens.flat", XrmoptionNoArg, "false" },
+ {"-flat", ".queens.flat", XrmoptionNoArg, "true" },
+};
+
+static int rotate, wire, clearbits, flat;
+
+static argtype vars[] = {
+ {&rotate, "rotate", "Rotate", "True", t_Bool},
+ {&flat, "flat", "Flat", "False", t_Bool},
+};
+
+ENTRYPOINT ModeSpecOpt queens_opts = {countof(opts), opts, countof(vars), vars, NULL};
+
+#ifdef USE_MODULES
+ModStruct queens_description =
+{"queens", "init_queens", "draw_queens", NULL,
+ "draw_queens", "init_queens", NULL, &queens_opts,
+ 1000, 1, 2, 1, 4, 1.0, "",
+ "Queens", 0, NULL};
+
+#endif
+
+#define NONE 0
+#define MINBOARD 5
+#define MAXBOARD 10
+#define COLORSETS 5
+
+typedef struct {
+ GLXContext *glx_context;
+ Window window;
+ trackball_state *trackball;
+ Bool button_down_p;
+ GLfloat position[4];
+ int queen_list;
+
+ int board[MAXBOARD][MAXBOARD];
+ int steps, colorset, BOARDSIZE;
+ double theta;
+ int queen_polys;
+
+} Queenscreen;
+
+static Queenscreen *qss = NULL;
+
+/* definition of white/black colors */
+static const GLfloat colors[COLORSETS][2][3] =
+ {
+ {{0.43, 0.54, 0.76}, {0.8, 0.8, 0.8}},
+ {{0.5, 0.7, 0.9}, {0.2, 0.3, 0.6}},
+ {{0.53725490196, 0.360784313725, 0.521568627451}, {0.6, 0.6, 0.6}},
+ {{0.15, 0.77, 0.54}, {0.5, 0.5, 0.5}},
+ {{0.9, 0.45, 0.0}, {0.5, 0.5, 0.5}},
+ };
+
+ENTRYPOINT Bool
+queens_handle_event (ModeInfo *mi, XEvent *event)
+{
+ Queenscreen *qs = &qss[MI_SCREEN(mi)];
+
+ if (gltrackball_event_handler (event, qs->trackball,
+ MI_WIDTH (mi), MI_HEIGHT (mi),
+ &qs->button_down_p))
+ return True;
+ else if (screenhack_event_helper (MI_DISPLAY(mi), MI_WINDOW(mi), event))
+ {
+ qs->steps = 1024 - 1;
+ return True;
+ }
+
+ return False;
+}
+
+
+
+/* returns true if placing a queen on column c causes a conflict */
+static int conflictsCols(Queenscreen *qs, int c)
+{
+ int i;
+
+ for(i = 0; i < qs->BOARDSIZE; ++i)
+ if(qs->board[i][c])
+ return 1;
+
+ return 0;
+}
+
+/* returns true if placing a queen on (r,c) causes a diagonal conflict */
+static int conflictsDiag(Queenscreen *qs, int r, int c)
+{
+ int i;
+
+ /* positive slope */
+ int n = r < c ? r : c;
+ for(i = 0; i < qs->BOARDSIZE-abs(r-c); ++i)
+ if(qs->board[r-n+i][c-n+i])
+ return 1;
+
+ /* negative slope */
+ n = r < qs->BOARDSIZE - (c+1) ? r : qs->BOARDSIZE - (c+1);
+ for(i = 0; i < qs->BOARDSIZE-abs(qs->BOARDSIZE - (1+r+c)); ++i)
+ if(qs->board[r-n+i][c+n-i])
+ return 1;
+
+ return 0;
+}
+
+/* returns true if placing a queen at (r,c) causes a conflict */
+static int conflicts(Queenscreen *qs, int r, int c)
+{
+ return !conflictsCols(qs, c) ? conflictsDiag(qs, r, c) : 1;
+}
+
+/* clear board */
+static void blank(Queenscreen *qs)
+{
+ int i, j;
+
+ for(i = 0; i < MAXBOARD; ++i)
+ for(j = 0; j < MAXBOARD; ++j)
+ qs->board[i][j] = NONE;
+}
+
+/* recursively determine solution */
+static int findSolution(Queenscreen *qs, int row, int col)
+{
+ if(row == qs->BOARDSIZE)
+ return 1;
+
+ while(col < qs->BOARDSIZE) {
+ if(!conflicts(qs, row, col)) {
+ qs->board[row][col] = 1;
+
+ if(findSolution(qs, row+1, 0))
+ return 1;
+
+ qs->board[row][col] = 0;
+ }
+
+ ++col;
+ }
+
+ return 0;
+}
+
+/** driver for finding solution */
+static void go(Queenscreen *qs) { while(!findSolution(qs, 0, random()%qs->BOARDSIZE)); }
+
+/* lighting variables */
+static const GLfloat front_shininess[] = {60.0};
+static const GLfloat front_specular[] = {0.4, 0.4, 0.4, 1.0};
+static const GLfloat ambient[] = {0.3, 0.3, 0.3, 1.0};
+static const GLfloat diffuse[] = {0.8, 0.8, 0.8, 1.0};
+
+/* configure lighting */
+static void setup_lights(Queenscreen *qs)
+{
+
+ /* setup twoside lighting */
+ glLightfv(GL_LIGHT0, GL_AMBIENT, ambient);
+ glLightfv(GL_LIGHT0, GL_DIFFUSE, diffuse);
+ glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
+ glEnable(GL_LIGHTING);
+ glEnable(GL_LIGHT0);
+
+ /* setup material properties */
+ glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, front_shininess);
+ glMaterialfv(GL_FRONT_AND_BACK, GL_SPECULAR, front_specular);
+
+ glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
+}
+
+#define checkImageWidth 8
+#define checkImageHeight 8
+/*static GLubyte checkImage[checkImageWidth][checkImageHeight][3];*/
+
+/* return alpha value for fading */
+static GLfloat findAlpha(Queenscreen *qs)
+{
+ return qs->steps < 128 ? qs->steps/128.0 : qs->steps < 1024-128 ?1.0:(1024-qs->steps)/128.0;
+}
+
+/* draw pieces */
+static int drawPieces(Queenscreen *qs)
+{
+ int i, j;
+ int polys = 0;
+
+ for(i = 0; i < qs->BOARDSIZE; ++i) {
+ for(j = 0; j < qs->BOARDSIZE; ++j) {
+ if(qs->board[i][j]) {
+ glColor3fv(colors[qs->colorset][i%2]);
+ glCallList(qs->queen_list);
+ polys += qs->queen_polys;
+ }
+
+ glTranslatef(1.0, 0.0, 0.0);
+ }
+
+ glTranslatef(-1.0*qs->BOARDSIZE, 0.0, 1.0);
+ }
+ return polys;
+}
+
+/** reflectionboard */
+static int draw_reflections(Queenscreen *qs)
+{
+ int i, j;
+ int polys = 0;
+
+ glEnable(GL_STENCIL_TEST);
+ glStencilFunc(GL_ALWAYS, 1, 1);
+ glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
+ glColorMask(0,0,0,0);
+ glDisable(GL_CULL_FACE);
+
+ glDisable(GL_DEPTH_TEST);
+ glBegin(GL_QUADS);
+
+ /* only draw white squares */
+ for(i = 0; i < qs->BOARDSIZE; ++i) {
+ for(j = (qs->BOARDSIZE+i) % 2; j < qs->BOARDSIZE; j += 2) {
+ glVertex3f(i, 0.0, j + 1.0);
+ glVertex3f(i + 1.0, 0.0, j + 1.0);
+ glVertex3f(i + 1.0, 0.0, j);
+ glVertex3f(i, 0.0, j);
+ polys++;
+ }
+ }
+ glEnd();
+ glEnable(GL_DEPTH_TEST);
+
+ glColorMask(1, 1, 1, 1);
+ glStencilFunc(GL_EQUAL, 1, 1);
+ glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
+
+ glPushMatrix();
+ glScalef(1.0, -1.0, 1.0);
+ glTranslatef(0.5, 0.001, 0.5);
+ glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
+ polys += drawPieces(qs);
+ glPopMatrix();
+ glDisable(GL_STENCIL_TEST);
+
+ /* replace lights */
+ glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
+
+ glEnable(GL_CULL_FACE);
+ glCullFace(GL_BACK);
+ glColorMask(1,1,1,1);
+ return polys;
+}
+
+/* draw board */
+static int drawBoard(Queenscreen *qs)
+{
+ int i, j;
+ int polys = 0;
+
+ glBegin(GL_QUADS);
+
+ for(i = 0; i < qs->BOARDSIZE; ++i)
+ for(j = 0; j < qs->BOARDSIZE; ++j) {
+ int par = (i-j+qs->BOARDSIZE)%2;
+ glColor4f(colors[qs->colorset][par][0],
+ colors[qs->colorset][par][1],
+ colors[qs->colorset][par][2],
+ 0.70);
+ glNormal3f(0.0, 1.0, 0.0);
+ glVertex3f(i, 0.0, j + 1.0);
+ glVertex3f(i + 1.0, 0.0, j + 1.0);
+ glVertex3f(i + 1.0, 0.0, j);
+ glVertex3f(i, 0.0, j);
+ polys++;
+ }
+
+ glEnd();
+
+ {
+ GLfloat off = 0.01;
+ GLfloat w = qs->BOARDSIZE;
+ GLfloat h = 0.1;
+
+ /* Give the board a slight lip. */
+ /* #### oops, normals are wrong here, but you can't tell */
+
+ glColor3f(0.3, 0.3, 0.3);
+ glBegin (GL_QUADS);
+ glVertex3f (0, 0, 0);
+ glVertex3f (0, -h, 0);
+ glVertex3f (0, -h, w);
+ glVertex3f (0, 0, w);
+
+ glVertex3f (0, 0, w);
+ glVertex3f (0, -h, w);
+ glVertex3f (w, -h, w);
+ glVertex3f (w, 0, w);
+
+ glVertex3f (w, 0, w);
+ glVertex3f (w, -h, w);
+ glVertex3f (w, -h, 0);
+ glVertex3f (w, 0, 0);
+
+ glVertex3f (w, 0, 0);
+ glVertex3f (w, -h, 0);
+ glVertex3f (0, -h, 0);
+ glVertex3f (0, 0, 0);
+
+ glVertex3f (0, -h, 0);
+ glVertex3f (w, -h, 0);
+ glVertex3f (w, -h, w);
+ glVertex3f (0, -h, w);
+ glEnd();
+ polys += 4;
+
+ /* Fill in the underside of the board with an invisible black box
+ to hide the reflections that are not on tiles. Probably there's
+ a way to do this with stencils instead.
+ */
+ w -= off*2;
+ h = 5;
+
+ glPushMatrix();
+ glTranslatef (off, 0, off);
+ glDisable(GL_LIGHTING);
+ glColor3f(0,0,0);
+ glBegin (GL_QUADS);
+ glVertex3f (0, 0, 0);
+ glVertex3f (0, -h, 0);
+ glVertex3f (0, -h, w);
+ glVertex3f (0, 0, w);
+
+ glVertex3f (0, 0, w);
+ glVertex3f (0, -h, w);
+ glVertex3f (w, -h, w);
+ glVertex3f (w, 0, w);
+
+ glVertex3f (w, 0, w);
+ glVertex3f (w, -h, w);
+ glVertex3f (w, -h, 0);
+ glVertex3f (w, 0, 0);
+
+ glVertex3f (w, 0, 0);
+ glVertex3f (w, -h, 0);
+ glVertex3f (0, -h, 0);
+ glVertex3f (0, 0, 0);
+
+ glVertex3f (0, -h, 0);
+ glVertex3f (w, -h, 0);
+ glVertex3f (w, -h, w);
+ glVertex3f (0, -h, w);
+ glEnd();
+ polys += 4;
+ glPopMatrix();
+ if (!wire)
+ glEnable(GL_LIGHTING);
+ }
+
+ return polys;
+}
+
+static int display(ModeInfo *mi, Queenscreen *qs)
+{
+ int max = 1024;
+ int polys = 0;
+ glClear(clearbits);
+
+ glMatrixMode(GL_MODELVIEW);
+ glLoadIdentity();
+
+ glRotatef(current_device_rotation(), 0, 0, 1);
+
+ /* setup light attenuation */
+ /* #### apparently this does nothing */
+ glEnable(GL_COLOR_MATERIAL);
+ glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 0.8/(0.01+findAlpha(qs)));
+ glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.06);
+
+ /** setup perspective */
+ glTranslatef(0.0, 0.0, -1.5*qs->BOARDSIZE);
+ glRotatef(30.0, 1.0, 0.0, 0.0);
+ gltrackball_rotate (qs->trackball);
+ glRotatef(qs->theta*100, 0.0, 1.0, 0.0);
+ glTranslatef(-0.5*qs->BOARDSIZE, 0.0, -0.5*qs->BOARDSIZE);
+
+ /* find light positions */
+ qs->position[0] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*-sin(qs->theta*100*M_PI/180.0);
+ qs->position[2] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*cos(qs->theta*100*M_PI/180.0);
+ qs->position[1] = 6.0;
+
+ if(!wire) {
+ glEnable(GL_LIGHTING);
+ glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
+ glEnable(GL_LIGHT0);
+ }
+
+ /* Since the lighting attenuation trick up there doesn't seem to be working,
+ let's drop the old board down and drop the new board in. */
+ if (qs->steps < (max/8.0)) {
+ GLfloat y = qs->steps / (max/8.0);
+ y = sin (M_PI/2 * y);
+ glTranslatef (0, 10 - (y * 10), 0);
+ } else if (qs->steps > max-(max/8.0)) {
+ GLfloat y = (qs->steps - (max-(max/8.0))) / (GLfloat) (max/8.0);
+ y = 1 - sin (M_PI/2 * (1-y));
+ glTranslatef (0, -y * 15, 0);
+ }
+
+ /* draw reflections */
+ if(!wire) {
+ polys += draw_reflections(qs);
+ glEnable(GL_BLEND);
+ }
+ polys += drawBoard(qs);
+ if(!wire)
+ glDisable(GL_BLEND);
+
+ glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.1);
+
+ glTranslatef(0.5, 0.0, 0.5);
+ polys += drawPieces(qs);
+
+ /* rotate camera */
+ if(!qs->button_down_p)
+ qs->theta += .002;
+
+ /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
+ if(++qs->steps == max) {
+ qs->steps = 0;
+ blank(qs);
+ qs->BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
+ qs->colorset = (qs->colorset+1)%COLORSETS;
+ go(qs);
+ }
+ return polys;
+}
+
+#define EPSILON 0.001
+
+#if 0
+/** draws cylindermodel */
+static int draw_model(int chunks, const GLfloat model[][3], int r)
+{
+ int i = 0;
+ int polys = 0;
+ glPushMatrix();
+ glRotatef(-90.0, 1.0, 0.0, 0.0);
+
+ for(i = 0; i < chunks; ++i) {
+ if(model[i][0] > EPSILON || model[i][1] > EPSILON) {
+ polys += tube (0, 0, 0,
+ 0, 0, model[i][1],
+ model[i][0], 0,
+ r, False, False, False);
+/* gluCylinder(quadric, model[i][0], model[i][1], model[i][2], r, 1);
+ polys += r;*/
+ }
+ glTranslatef(0.0, 0.0, model[i][2]);
+ }
+
+ glPopMatrix();
+ return polys;
+}
+#endif
+
+ENTRYPOINT void reshape_queens(ModeInfo *mi, int width, int height)
+{
+ GLfloat h = (GLfloat) height / (GLfloat) width;
+ int y = 0;
+
+ if (width > height * 5) { /* tiny window: show middle */
+ height = width;
+ y = -height/2;
+ h = height / (GLfloat) width;
+ }
+ glViewport(0,y, width, height);
+ glMatrixMode(GL_PROJECTION);
+ glLoadIdentity();
+ gluPerspective(45, 1/h, 2.0, 30.0);
+ glMatrixMode(GL_MODELVIEW);
+}
+
+ENTRYPOINT void init_queens(ModeInfo *mi)
+{
+ int screen = MI_SCREEN(mi);
+ Queenscreen *qs;
+ int poly_counts[PIECES];
+ wire = MI_IS_WIREFRAME(mi);
+
+# ifdef HAVE_JWZGLES /* #### glPolygonMode other than GL_FILL unimplemented */
+ wire = 0;
+# endif
+
+ MI_INIT (mi, qss);
+
+ qs = &qss[screen];
+ qs->window = MI_WINDOW(mi);
+
+ if((qs->glx_context = init_GL(mi)))
+ reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
+ else
+ MI_CLEARWINDOW(mi);
+
+ qs->trackball = gltrackball_init (False);
+
+ qs->BOARDSIZE = 8; /* 8 cuz its classic */
+
+ chessmodels_gen_lists(-1, poly_counts);
+ qs->queen_list = QUEEN;
+ qs->queen_polys = poly_counts[QUEEN];
+
+ /* find a solution */
+ go(qs);
+}
+
+ENTRYPOINT void draw_queens(ModeInfo *mi)
+{
+ Queenscreen *qs = &qss[MI_SCREEN(mi)];
+ Window w = MI_WINDOW(mi);
+ Display *disp = MI_DISPLAY(mi);
+
+ if(!qs->glx_context)
+ return;
+
+ glXMakeCurrent(disp, w, *(qs->glx_context));
+
+ if(flat)
+ glShadeModel(GL_FLAT);
+
+ clearbits = GL_COLOR_BUFFER_BIT;
+
+ glColorMaterial(GL_FRONT, GL_DIFFUSE);
+ glEnable(GL_COLOR_MATERIAL);
+
+ if(!wire) {
+ setup_lights(qs);
+ glEnable(GL_DEPTH_TEST);
+ clearbits |= GL_DEPTH_BUFFER_BIT;
+ clearbits |= GL_STENCIL_BUFFER_BIT;
+ glEnable(GL_CULL_FACE);
+ glCullFace(GL_BACK);
+ }
+ else
+ glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
+
+ mi->polygon_count = display(mi, qs);
+ mi->recursion_depth = qs->BOARDSIZE;
+
+ if(mi->fps_p) do_fps(mi);
+ glFinish();
+ glXSwapBuffers(disp, w);
+}
+
+XSCREENSAVER_MODULE ("Queens", queens)
+
+#endif
generated by cgit v1.2.3-55-g7522 (git 2.39.0) at 2024-05-18 02:37:51 +0200