Commit | Line | Data |
---|---|---|
116f0564 KH |
1 | ;;; 5x5.el -- Simple little puzzle game. |
2 | ||
08f87e3c | 3 | ;; Copyright (C) 1999 Free Software Foundation, Inc. |
116f0564 KH |
4 | |
5 | ;; Author: Dave Pearson <davep@hagbard.demon.co.uk> | |
6 | ;; Maintainer: Dave Pearson <davep@hagbard.demon.co.uk> | |
7 | ;; Created: 1998-10-03 | |
08f87e3c | 8 | ;; Version: $Revision: 1.2 $ |
116f0564 KH |
9 | ;; Keywords: games puzzles |
10 | ||
11 | ;; This file is part of GNU Emacs. | |
12 | ||
13 | ;; GNU Emacs is free software; you can redistribute it and/or modify | |
14 | ;; it under the terms of the GNU General Public License as published by | |
15 | ;; the Free Software Foundation; either version 2, or (at your option) | |
16 | ;; any later version. | |
17 | ||
18 | ;; GNU Emacs is distributed in the hope that it will be useful, | |
19 | ;; but WITHOUT ANY WARRANTY; without even the implied warranty of | |
20 | ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
21 | ;; GNU General Public License for more details. | |
22 | ||
23 | ;; You should have received a copy of the GNU General Public License | |
24 | ;; along with GNU Emacs; see the file COPYING. If not, write to the | |
25 | ;; Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
26 | ;; Boston, MA 02111-1307, USA. | |
27 | ||
28 | ;;; Commentary: | |
29 | ||
30 | ;; The aim of 5x5 is to fill in all the squares. If you need any more of an | |
31 | ;; explanation you probably shouldn't play the game. | |
32 | ||
33 | ;;; TODO: | |
34 | ||
35 | ;; o The code for updating the grid needs to be re-done. At the moment it | |
36 | ;; simply re-draws the grid every time a move is made. | |
37 | ;; | |
36dfd590 | 38 | ;; o Look into tarting up the display with colour. gamegrid.el looks |
116f0564 KH |
39 | ;; interesting, perhaps that is the way to go? |
40 | ||
41 | ;;; Thanks: | |
42 | ||
43 | ;; Ralf Fassel <ralf@akutech.de> for his help and introduction to writing an | |
44 | ;; emacs mode. | |
45 | ;; | |
46 | ;; Pascal Q. Porcupine <joshagam@cs.nmsu.edu> for inspiring the animated | |
47 | ;; solver. | |
48 | ||
49 | ;; Things we need. | |
50 | ||
51 | (eval-when-compile | |
52 | (require 'cl)) | |
53 | ||
54 | ;; If customize isn't available just use defvar instead. | |
55 | (eval-and-compile | |
56 | (unless (fboundp 'defgroup) | |
57 | (defmacro defgroup (&rest rest) nil) | |
58 | (defmacro defcustom (symbol init docstring &rest rest) | |
59 | `(defvar ,symbol ,init ,docstring)))) | |
60 | ||
61 | ;; Customize options. | |
62 | ||
63 | (defgroup 5x5 nil | |
64 | "5x5 - Silly little puzzle game." | |
65 | :group 'games | |
66 | :prefix "5x5-") | |
67 | ||
68 | (defcustom 5x5-grid-size 5 | |
69 | "*Size of the playing area." | |
70 | :type 'integer | |
71 | :group '5x5) | |
72 | ||
73 | (defcustom 5x5-x-scale 4 | |
74 | "*X scaling factor for drawing the grid." | |
75 | :type 'integer | |
76 | :group '5x5) | |
77 | ||
78 | (defcustom 5x5-y-scale 3 | |
79 | "*Y scaling factor for drawing the grid." | |
80 | :type 'integer | |
81 | :group '5x5) | |
82 | ||
83 | (defcustom 5x5-animate-delay .01 | |
84 | "*Delay in seconds when animating a solution crack." | |
85 | :type 'number | |
86 | :group '5x5) | |
87 | ||
88 | (defcustom 5x5-hassle-me t | |
89 | "*Should 5x5 ask you when you want to do a destructive operation?" | |
90 | :type 'boolean | |
91 | :group '5x5) | |
92 | ||
93 | (defcustom 5x5-mode-hook nil | |
94 | "*Hook run on starting 5x5." | |
95 | :type 'hook | |
96 | :group '5x5) | |
97 | ||
98 | ;; Non-customize variables. | |
99 | ||
100 | (defvar 5x5-grid nil | |
101 | "5x5 grid contents.") | |
102 | ||
103 | (defvar 5x5-x-pos 2 | |
104 | "X position of cursor.") | |
105 | ||
106 | (defvar 5x5-y-pos 2 | |
107 | "Y position of cursor.") | |
108 | ||
109 | (defvar 5x5-moves 0 | |
110 | "Moves made.") | |
111 | ||
112 | (defvar 5x5-cracking nil | |
113 | "Are we in cracking mode?") | |
114 | ||
115 | (defvar 5x5-buffer-name "*5x5*" | |
116 | "Name of the 5x5 play buffer.") | |
117 | ||
118 | (defvar 5x5-mode-map nil | |
119 | "Local keymap for the 5x5 game.") | |
120 | ||
121 | ;; Keymap. | |
122 | ||
123 | (unless 5x5-mode-map | |
124 | (let ((map (make-sparse-keymap))) | |
125 | (suppress-keymap map t) | |
126 | (define-key map "?" #'describe-mode) | |
127 | (define-key map "\r" #'5x5-flip-current) | |
128 | (define-key map " " #'5x5-flip-current) | |
129 | (define-key map [up] #'5x5-up) | |
130 | (define-key map [down] #'5x5-down) | |
131 | (define-key map [left] #'5x5-left) | |
132 | (define-key map [tab] #'5x5-right) | |
133 | (define-key map [right] #'5x5-right) | |
134 | (define-key map [(control a)] #'5x5-bol) | |
135 | (define-key map [(control e)] #'5x5-eol) | |
08f87e3c KH |
136 | (define-key map [(control p)] #'5x5-up) |
137 | (define-key map [(control n)] #'5x5-down) | |
138 | (define-key map [(control b)] #'5x5-left) | |
139 | (define-key map [(control f)] #'5x5-right) | |
116f0564 KH |
140 | (define-key map [home] #'5x5-bol) |
141 | (define-key map [end] #'5x5-eol) | |
142 | (define-key map [prior] #'5x5-first) | |
143 | (define-key map [next] #'5x5-last) | |
144 | (define-key map "r" #'5x5-randomize) | |
145 | (define-key map [(control c) (control r)] #'5x5-crack-randomly) | |
146 | (define-key map [(control c) (control c)] #'5x5-crack-mutating-current) | |
147 | (define-key map [(control c) (control b)] #'5x5-crack-mutating-best) | |
148 | (define-key map [(control c) (control x)] #'5x5-crack-xor-mutate) | |
149 | (define-key map "n" #'5x5-new-game) | |
150 | (define-key map "q" #'5x5-quit-game) | |
151 | (setq 5x5-mode-map map))) | |
152 | ||
153 | ;; Menu definition. | |
154 | ||
155 | (easy-menu-define 5x5-mode-menu 5x5-mode-map "5x5 menu." | |
156 | '("5x5" | |
157 | ["New game" 5x5-new-game t] | |
158 | ["Random game" 5x5-randomize t] | |
159 | ["Quit game" 5x5-quit-game t] | |
160 | "---" | |
161 | ["Crack randomly" 5x5-crack-randomly t] | |
162 | ["Crack mutating current" 5x5-crack-mutating-current t] | |
163 | ["Crack mutating best" 5x5-crack-mutating-best t] | |
164 | ["Crack with xor mutate" 5x5-crack-xor-mutate t])) | |
165 | ||
166 | ;; Gameplay functions. | |
167 | ||
168 | (put '5x5-mode 'mode-class 'special) | |
169 | ||
170 | (defun 5x5-mode () | |
171 | "A mode for playing `5x5' | |
172 | ||
173 | The key bindings for 5x5-mode are: | |
174 | ||
175 | \\{5x5-mode-map}" | |
176 | (kill-all-local-variables) | |
177 | (use-local-map 5x5-mode-map) | |
178 | (setq major-mode '5x5-mode | |
179 | mode-name "5x5") | |
180 | (run-hooks '5x5-mode-hook) | |
181 | (setq buffer-read-only t | |
182 | truncate-lines t) | |
183 | (buffer-disable-undo (current-buffer))) | |
184 | ||
185 | ;;;###autoload | |
186 | (defun 5x5 (&optional size) | |
187 | "Play 5x5. | |
188 | ||
189 | The object of 5x5 is very simple, by moving around the grid and flipping | |
190 | squares you must fill the grid. | |
191 | ||
192 | 5x5 keyboard bindings are: | |
193 | \\<5x5-mode-map> | |
194 | Flip \\[5x5-flip-current] | |
195 | Move up \\[5x5-up] | |
196 | Move down \\[5x5-down] | |
197 | Move left \\[5x5-left] | |
198 | Move right \\[5x5-right] | |
199 | Start new game \\[5x5-new-game] | |
200 | New game with random grid \\[5x5-randomize] | |
201 | Random cracker \\[5x5-crack-randomly] | |
202 | Mutate current cracker \\[5x5-crack-mutating-current] | |
08f87e3c | 203 | Mutate best cracker \\[5x5-crack-mutating-best] |
116f0564 KH |
204 | Mutate xor cracker \\[5x5-crack-xor-mutate] |
205 | Quit current game \\[5x5-quit-game]" | |
206 | ||
207 | (interactive "P") | |
208 | (setq 5x5-cracking nil) | |
209 | (when size | |
210 | (setq 5x5-grid-size size)) | |
211 | (switch-to-buffer 5x5-buffer-name) | |
212 | (if (or (not 5x5-grid) (not (= 5x5-grid-size (length (aref 5x5-grid 0))))) | |
213 | (5x5-new-game)) | |
214 | (5x5-draw-grid (list 5x5-grid)) | |
215 | (5x5-position-cursor) | |
216 | (5x5-mode)) | |
217 | ||
218 | (defun 5x5-new-game () | |
219 | "Start a new game of `5x5'." | |
220 | (interactive) | |
221 | (when (if (interactive-p) (5x5-y-or-n-p "Start a new game? ") t) | |
222 | (setq 5x5-x-pos (/ 5x5-grid-size 2) | |
223 | 5x5-y-pos (/ 5x5-grid-size 2) | |
224 | 5x5-moves 0 | |
225 | 5x5-grid (5x5-make-move (5x5-make-new-grid) 5x5-y-pos 5x5-x-pos)) | |
226 | (when (interactive-p) | |
227 | (5x5-draw-grid (list 5x5-grid)) | |
228 | (5x5-position-cursor)))) | |
229 | ||
230 | (defun 5x5-quit-game () | |
231 | "Quit the current game of `5x5'." | |
232 | (interactive) | |
233 | (kill-buffer 5x5-buffer-name)) | |
234 | ||
235 | (defun 5x5-make-new-grid () | |
236 | "Create and return a new `5x5' grid structure." | |
237 | (let ((grid (make-vector 5x5-grid-size nil))) | |
238 | (loop for y from 0 to (1- 5x5-grid-size) do | |
239 | (aset grid y (make-vector 5x5-grid-size nil))) | |
240 | grid)) | |
241 | ||
242 | (defun 5x5-cell (grid y x) | |
243 | "Return the value of the cell in GRID at location X,Y." | |
244 | (aref (aref grid y) x)) | |
245 | ||
246 | (defun 5x5-set-cell (grid y x value) | |
247 | "Set the value of cell X,Y in GRID to VALUE." | |
248 | (aset (aref grid y) x value)) | |
249 | ||
250 | (defun 5x5-flip-cell (grid y x) | |
251 | "Flip the value of cell X,Y in GRID." | |
252 | (5x5-set-cell grid y x (not (5x5-cell grid y x)))) | |
253 | ||
254 | (defun 5x5-copy-grid (grid) | |
255 | "Make a new copy of GRID." | |
256 | (let ((copy (5x5-make-new-grid))) | |
257 | (loop for y from 0 to (1- 5x5-grid-size) do | |
258 | (loop for x from 0 to (1- 5x5-grid-size) do | |
259 | (5x5-set-cell copy y x (5x5-cell grid y x)))) | |
260 | copy)) | |
261 | ||
262 | (defun 5x5-make-move (grid row col) | |
263 | "Make a move on GRID at row ROW and column COL." | |
264 | (5x5-flip-cell grid row col) | |
265 | (if (> row 0) | |
266 | (5x5-flip-cell grid (1- row) col)) | |
267 | (if (< row (- 5x5-grid-size 1)) | |
268 | (5x5-flip-cell grid (1+ row) col)) | |
269 | (if (> col 0) | |
270 | (5x5-flip-cell grid row (1- col))) | |
271 | (if (< col (- 5x5-grid-size 1)) | |
272 | (5x5-flip-cell grid row (1+ col))) | |
273 | grid) | |
274 | ||
275 | (defun 5x5-row-value (row) | |
276 | "Get the \"on-value\" for grid row ROW." | |
277 | (loop for y from 0 to (1- 5x5-grid-size) sum (if (aref row y) 1 0))) | |
278 | ||
279 | (defun 5x5-grid-value (grid) | |
280 | "Get the \"on-value\" for grid GRID." | |
281 | (loop for y from 0 to (1- 5x5-grid-size) sum (5x5-row-value (aref grid y)))) | |
282 | ||
283 | (defun 5x5-draw-grid-end () | |
284 | "Draw the top/bottom of the grid" | |
285 | (insert "+") | |
286 | (loop for x from 0 to (1- 5x5-grid-size) do | |
287 | (insert "-" (make-string 5x5-x-scale ?-))) | |
288 | (insert "-+ ")) | |
289 | ||
290 | (defun 5x5-draw-grid (grids) | |
291 | "Draw the grids GRIDS into the current buffer." | |
292 | (let ((buffer-read-only nil)) | |
293 | (erase-buffer) | |
294 | (loop for grid in grids do (5x5-draw-grid-end)) | |
295 | (insert "\n") | |
296 | (loop for y from 0 to (1- 5x5-grid-size) do | |
297 | (loop for lines from 0 to (1- 5x5-y-scale) do | |
298 | (loop for grid in grids do | |
299 | (loop for x from 0 to (1- 5x5-grid-size) do | |
300 | (insert (if (zerop x) "| " " ") | |
301 | (make-string 5x5-x-scale | |
302 | (if (5x5-cell grid y x) ?# ?.)))) | |
303 | (insert " | ")) | |
304 | (insert "\n"))) | |
305 | (loop for grid in grids do (5x5-draw-grid-end)) | |
306 | (insert "\n") | |
307 | (insert (format "On: %d Moves: %d" (5x5-grid-value (car grids)) 5x5-moves)))) | |
308 | ||
309 | (defun 5x5-position-cursor () | |
310 | "Position the cursor on the grid." | |
311 | (goto-line (+ (* 5x5-y-pos 5x5-y-scale) 2)) | |
312 | (goto-char (+ (point) (* 5x5-x-pos 5x5-x-scale) (+ 5x5-x-pos 1) 1))) | |
313 | ||
314 | (defun 5x5-made-move () | |
315 | "Keep track of how many moves have been made." | |
316 | (incf 5x5-moves)) | |
317 | ||
318 | (defun 5x5-make-random-grid () | |
319 | "Make a random grid." | |
320 | (let ((grid (5x5-make-new-grid))) | |
321 | (loop for y from 0 to (1- 5x5-grid-size) do | |
322 | (loop for x from 0 to (1- 5x5-grid-size) do | |
323 | (if (zerop (random 2)) | |
324 | (5x5-flip-cell grid y x)))) | |
325 | grid)) | |
326 | ||
327 | ;; Cracker functions. | |
328 | ||
329 | ;;;###autoload | |
330 | (defun 5x5-crack-randomly () | |
331 | "Attempt to crack 5x5 using random solutions." | |
332 | (interactive) | |
333 | (5x5-crack #'5x5-make-random-solution)) | |
334 | ||
335 | ;;;###autoload | |
336 | (defun 5x5-crack-mutating-current () | |
337 | "Attempt to crack 5x5 by mutating the current solution." | |
338 | (interactive) | |
339 | (5x5-crack #'5x5-make-mutate-current)) | |
340 | ||
341 | ;;;###autoload | |
342 | (defun 5x5-crack-mutating-best () | |
343 | "Attempt to crack 5x5 by mutating the best solution." | |
344 | (interactive) | |
345 | (5x5-crack #'5x5-make-mutate-best)) | |
346 | ||
347 | ;;;###autoload | |
348 | (defun 5x5-crack-xor-mutate () | |
349 | "Attempt to crack 5x5 by xor the current and best solution and then | |
350 | mutating the result." | |
351 | (interactive) | |
352 | (5x5-crack #'5x5-make-xor-with-mutation)) | |
353 | ||
354 | ;;;###autoload | |
355 | (defun 5x5-crack (breeder) | |
356 | "Attempt to find a solution for 5x5. | |
357 | ||
358 | 5x5-crack takes the argument BREEDER which should be a function that takes | |
359 | two parameters, the first will be a grid vector array that is the current | |
360 | solution and the second will be the best solution so far. The function | |
361 | should return a grid vector array that is the new solution." | |
362 | ||
363 | (interactive "aBreeder function: ") | |
364 | (5x5) | |
365 | (setq 5x5-cracking t) | |
366 | (let* ((best-solution (5x5-make-random-grid)) | |
367 | (current-solution best-solution) | |
368 | (best-result (5x5-make-new-grid)) | |
369 | (current-result (5x5-make-new-grid)) | |
370 | (target (* 5x5-grid-size 5x5-grid-size))) | |
371 | (while (and (< (5x5-grid-value best-result) target) | |
372 | (not (input-pending-p))) | |
373 | (setq current-result (5x5-play-solution current-solution best-solution)) | |
374 | (if (> (5x5-grid-value current-result) (5x5-grid-value best-result)) | |
375 | (setq best-solution current-solution | |
376 | best-result current-result)) | |
377 | (setq current-solution (funcall breeder | |
378 | (5x5-copy-grid current-solution) | |
379 | (5x5-copy-grid best-solution))))) | |
380 | (setq 5x5-cracking nil)) | |
381 | ||
382 | (defun 5x5-make-random-solution (&rest ignore) | |
383 | "Make a random solution." | |
384 | (5x5-make-random-grid)) | |
385 | ||
386 | (defun 5x5-make-mutate-current (current best) | |
387 | "Mutate the current solution." | |
388 | (5x5-mutate-solution current)) | |
389 | ||
390 | (defun 5x5-make-mutate-best (current best) | |
391 | "Mutate the best solution." | |
392 | (5x5-mutate-solution best)) | |
393 | ||
394 | (defun 5x5-make-xor-with-mutation (current best) | |
395 | "xor current and best solution then mutate the result." | |
396 | (let ((xored (5x5-make-new-grid))) | |
397 | (loop for y from 0 to (1- 5x5-grid-size) do | |
398 | (loop for x from 0 to (1- 5x5-grid-size) do | |
399 | (5x5-set-cell xored y x | |
400 | (5x5-xor (5x5-cell current y x) | |
401 | (5x5-cell best y x))))) | |
402 | (5x5-mutate-solution xored))) | |
403 | ||
404 | (defun 5x5-mutate-solution (solution) | |
405 | "Randomly flip bits in the solution." | |
406 | (loop for y from 0 to (1- 5x5-grid-size) do | |
407 | (loop for x from 0 to (1- 5x5-grid-size) do | |
408 | (if (= (random (/ (* 5x5-grid-size 5x5-grid-size) 2)) | |
409 | (/ (/ (* 5x5-grid-size 5x5-grid-size) 2) 2)) | |
410 | (5x5-flip-cell solution y x)))) | |
411 | solution) | |
412 | ||
413 | (defun 5x5-play-solution (solution best) | |
414 | "Play a solution on an empty grid. This destroys the current game in | |
415 | progress because it is an animated attempt." | |
416 | (5x5-new-game) | |
417 | (loop for y from 0 to (1- 5x5-grid-size) do | |
418 | (loop for x from 0 to (1- 5x5-grid-size) do | |
419 | (setq 5x5-y-pos y | |
420 | 5x5-x-pos x) | |
421 | (if (5x5-cell solution y x) | |
422 | (5x5-flip-current)) | |
423 | (5x5-draw-grid (list 5x5-grid solution best)) | |
424 | (5x5-position-cursor) | |
425 | (sit-for 5x5-animate-delay))) | |
426 | 5x5-grid) | |
427 | ||
428 | ;; Keyboard response functions. | |
429 | ||
430 | (defun 5x5-flip-current () | |
431 | "Make a move on the current cursor location." | |
432 | (interactive) | |
433 | (setq 5x5-grid (5x5-make-move 5x5-grid 5x5-y-pos 5x5-x-pos)) | |
434 | (5x5-made-move) | |
435 | (unless 5x5-cracking | |
436 | (5x5-draw-grid (list 5x5-grid))) | |
437 | (5x5-position-cursor) | |
438 | (when (= (5x5-grid-value 5x5-grid) (* 5x5-grid-size 5x5-grid-size)) | |
439 | (beep) | |
440 | (message "You win!"))) | |
441 | ||
442 | (defun 5x5-up () | |
443 | "Move up." | |
444 | (interactive) | |
445 | (unless (zerop 5x5-y-pos) | |
446 | (decf 5x5-y-pos) | |
447 | (5x5-position-cursor))) | |
448 | ||
449 | (defun 5x5-down () | |
450 | "Move down." | |
451 | (interactive) | |
452 | (unless (= 5x5-y-pos (1- 5x5-grid-size)) | |
453 | (incf 5x5-y-pos) | |
454 | (5x5-position-cursor))) | |
455 | ||
456 | (defun 5x5-left () | |
457 | "Move left." | |
458 | (interactive) | |
459 | (unless (zerop 5x5-x-pos) | |
460 | (decf 5x5-x-pos) | |
461 | (5x5-position-cursor))) | |
462 | ||
463 | (defun 5x5-right () | |
464 | "Move right." | |
465 | (interactive) | |
466 | (unless (= 5x5-x-pos (1- 5x5-grid-size)) | |
467 | (incf 5x5-x-pos) | |
468 | (5x5-position-cursor))) | |
469 | ||
470 | (defun 5x5-bol () | |
471 | "Move to beginning of line." | |
472 | (interactive) | |
473 | (setq 5x5-x-pos 0) | |
474 | (5x5-position-cursor)) | |
475 | ||
476 | (defun 5x5-eol () | |
477 | "Move to end of line." | |
478 | (interactive) | |
479 | (setq 5x5-x-pos (1- 5x5-grid-size)) | |
480 | (5x5-position-cursor)) | |
481 | ||
482 | (defun 5x5-first () | |
483 | "Move to the first cell." | |
484 | (interactive) | |
485 | (setq 5x5-x-pos 0 | |
486 | 5x5-y-pos 0) | |
487 | (5x5-position-cursor)) | |
488 | ||
489 | (defun 5x5-last () | |
490 | "Move to the last cell." | |
491 | (interactive) | |
492 | (setq 5x5-x-pos (1- 5x5-grid-size) | |
493 | 5x5-y-pos (1- 5x5-grid-size)) | |
494 | (5x5-position-cursor)) | |
495 | ||
496 | (defun 5x5-randomize () | |
497 | "Randomize the grid." | |
498 | (interactive) | |
499 | (when (5x5-y-or-n-p "Start a new game with a random grid? ") | |
500 | (setq 5x5-x-pos (/ 5x5-grid-size 2) | |
501 | 5x5-y-pos (/ 5x5-grid-size 2) | |
502 | 5x5-moves 0 | |
503 | 5x5-grid (5x5-make-random-grid)) | |
504 | (unless 5x5-cracking | |
505 | (5x5-draw-grid (list 5x5-grid))) | |
506 | (5x5-position-cursor))) | |
507 | ||
508 | ;; Support functions | |
509 | ||
510 | (defun 5x5-xor (x y) | |
511 | "Boolean exclusive-or of X and Y." | |
512 | (and (or x y) (not (and x y)))) | |
513 | ||
514 | (defun 5x5-y-or-n-p (prompt) | |
515 | "5x5 wrapper for y-or-n-p which respects the 5x5-hassle-me setting." | |
516 | (if 5x5-hassle-me | |
517 | (y-or-n-p prompt) | |
518 | t)) | |
519 | ||
520 | (provide '5x5) | |
521 | ||
522 | ;;; 5x5.el ends here |