If you're reading this you probably know what The Game of Life is. If not, visit the Wikipedia for more information:
https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
You may want to just recall the rules governing those aggregates of live cells called polyominos. They are very simple:
a live cell with more than 3 live neighbors (where neighbors of a cell are those cells adjacent to it in every direction) dies (over-population).
a live cell with less than 2 live neighbors dies (under-population).
a dead cell with exactly 3 live neighbors becomes live.
The following diagrams clarify the rules and serve as the preliminary analysis of the problem domain.
And now the code. It is written in a language based on Racket called "Intermediate Student Language with lambda". It can be run on DrRacket (https://download.racket-lang.org/) by setting "Language" to that. ISL+ is a purely functional language that, additionally, allows the use of anonymous functions via lambda expressions. I have also included the Racket module for working with sets (require racket/set). You can, of course, define your own implementation of the set functions applied, instead. They are easy to define. For supporting graphics and interactivity two more modules are required: 2htdp/image and 2htdp/universe.
Regarding the kind of data to represent the domain information I have chosen complex numbers, which are well supported by Racket, to represent a cell. The advantage of using complex numbers instead of, say, a structure of x and y coordinates is mainly performance. A functional implementation without any kind of mutation will be typically slow. At least resorting to a plain data type should improve things in that regard. That choice doesn't compromise readability, though, I think. Besides, the implementation of functions, in particular neighbors, is really neat with such a data type.
On the other hand, I have represented polyominos as sets of cells. Actually lists of cells but treated as immutable sets. That, I hope, produces an elegant and pretty understandable implementation. It also allows an arbitrary number of cells in the grid. I'm aware that clever algorithms could improve efficiency, but I preferred to write first the most natural and readable version.
One last thing, the animation tends to be sluggish after certain point, depending on the clock rate specified and the number of cells involved in that moment. To avoid that annoyance from the very beginning, freezeing the image of the grid is absolutely indispensable.
If you want to change the number of rows and columns of the grid, modify COLS# and ROWS# as you wish.
To play the game, run the program with (main START) from the Interactions Window within DrRacket. Select cells to construct a polyomino by clicking on them on the initial grid. To clear the grid, press 'Escape', to (re)start the animation press 'Enter', to stop the animation, press any key except 'Enter' or 'Escape'.
;; ===============================================
;; CONSTANTS
;; -----------------------------------------------
;; Game rules
(define OVER-POPULATION-THRESHOLD 3)
(define UNDER-POPULATION-THRESHOLD 2)
(define PROCREATION-FACTOR 3)
;; -----------------------------------------------
;; Graphics - Dimensions
; number of rows and columns in the grid
(define ROWS# 81)
(define COLS# 81)
; length of each cell side (in pixels)
(define SIDE 10)
; x and y positions of the middle of, roughly, the grid's center tile
(define CTR-X
(if (odd? COLS#)
(quotient (* COLS# SIDE) 2)
(- (quotient (* COLS# SIDE) 2) (quotient SIDE 2))))
(define CTR-Y
(if (odd? ROWS#)
(quotient (* ROWS# SIDE) 2)
(- (quotient (* ROWS# SIDE) 2) (quotient SIDE 2))))
;; -----------------------------------------------
;; Graphics - Images
(define LIVE-CELL (color-frame "transparent"
(square (sub1 SIDE) "solid" "red")))
(define DEAD-CELL (square SIDE "outline" "black"))
(define GRID
(local [(define col-img
(foldr above
empty-image
(build-list ROWS# (lambda (_) DEAD-CELL))))]
(freeze
(foldr beside
empty-image
(build-list COLS# (lambda (_) col-img))))))
;; ===============================================
;; DATA DEFINITIONS
;; -----------------------------------------------
;; Cell is Complex
;; interp. a cell in a game of life, where its real and imaginary
;; parts represent, respectively, its positions on the x and
;; y axis of the complex plane of the game.
;; remark: actual values for those parts are chosen in such a way
;; that the 0+0i cell in cell patterns is, roughly, at the
;; center of the pattern, which makes easier to design
;; drawing functions
(define C0 (make-rectangular 0 0)) ;0+0i
;; -----------------------------------------------
;; Life is (listof Cell)
;; interp. a set of living cells in a game of life
(define I-TROMINO
(list (make-rectangular 0 1)
(make-rectangular 0 0)
(make-rectangular 0 -1)))
(define P-PENTOMINO
(list (make-rectangular 0 1)
(make-rectangular 1 1)
(make-rectangular 0 0)
(make-rectangular 1 0)
(make-rectangular 0 -1)))
(define R-PENTOMINO
(list (make-rectangular 0 1)
(make-rectangular 1 1)
(make-rectangular -1 0)
(make-rectangular 0 0)
(make-rectangular 0 -1)))
;; -----------------------------------------------
;; Direction is one of:
(define E (make-rectangular 1 0))
(define NE (make-rectangular 1 1))
(define N (make-rectangular 0 1))
(define NW (make-rectangular -1 1))
(define W (make-rectangular -1 0))
(define SW (make-rectangular -1 -1))
(define S (make-rectangular 0 -1))
(define SE (make-rectangular 1 -1))
;; interp. the eight cardinal points
(define DIRECTIONS (list E NE N NW W SW S SE))
;; -----------------------------------------------
(define-struct gol (life running?))
;; GoL is (make-gol Life Boolean)
;; interp. a game of life with its life and a
;; state, running or stopped
(define STOPPED #f)
(define RUNNING #t)
(define START (make-gol '() STOPPED))
;; ===============================================
;; FUNCTIONS
;; -----------------------------------------------
;; GoL -> GoL
;; start main with (main START)
(define (main gol)
(big-bang gol
(on-tick next .5)
(to-draw render)
(on-mouse add-cell)
(on-key handle-key)))
;; -----------------------------------------------
;; GoL -> GoL
;; produce the next gol from the given one
(define (next gol)
(cond [(gol-running? gol)
(make-gol (evolve (gol-life gol)) RUNNING)]
[else gol]))
;; -----------------------------------------------
;; Life -> Life
;; produce the next evolutive step of the given life
(define (evolve l)
(local [;; Cell -> (listof Cell)
;; produce the neighbors of the given cell
(define (neighbors c)
(map (lambda (d) (+ c d)) DIRECTIONS))
;; Cell -> Natural
;; produce the number of the living neighbors of given cell
(define (alive-neighbors# c)
(set-count (set-intersect (neighbors c) l)))
;; Cell -> Boolean
;; determine whether the given cell is going to survive
(define (survive? c)
(<= UNDER-POPULATION-THRESHOLD
(alive-neighbors# c)
OVER-POPULATION-THRESHOLD))
;; Cell -> Boolean
;; determine whether the given cell is going to rise
(define (rise? c)
(= (alive-neighbors# c) PROCREATION-FACTOR))
;; surviving cells in the given life
(define surviving
(filter survive? l))
;; surrounding cells around the given life
(define environ
(set-subtract (foldr set-union '() (map neighbors l)) l))
;; cells going to live in the environment of the given life
(define rising
(filter rise? environ))]
(set-union surviving rising)))
;; -----------------------------------------------
;; GoL -> Image
;; render the given gol life on the grid
(define (render gol)
(local [;; Cell -> Posn
;; produce the position on the grid corresponding
;; to the given cell
(define (cell->pos c)
(make-posn (+ CTR-X (* (real-part c) SIDE))
(- CTR-Y (* (imag-part c) SIDE))))
;; Cell Image -> Image
;; draw the given the cell onto the given image
(define (draw-cell c img)
(local [(define p (cell->pos c))]
(place-image LIVE-CELL (posn-x p) (posn-y p) img)))]
(foldr draw-cell GRID (gol-life gol))))
;; -----------------------------------------------
;; GoL Integer Integer MouseEvent -> GoL
;; add the cell clicked on to the given gol's life
(define (add-cell gol x y me)
(local [(define (xy->cell x y)
(local [(define ctr-delta
(make-posn (ceiling (sub1 (/ COLS# 2)))
(ceiling (sub1 (/ ROWS# 2)))))]
(make-rectangular (- (quotient x SIDE)
(posn-x ctr-delta))
(+ (- (quotient y SIDE))
(posn-y ctr-delta)))))]
(cond [(mouse=? me "button-down")
(make-gol (cons (xy->cell x y) (gol-life gol))
(gol-running? gol))]
[else gol])))
;; -----------------------------------------------
;; GoL KeyEvent -> GoL
;; handle keys as follows
;; - 'Enter' - starts the animation
;; - 'Escape' - clear all cells and stops the animation
;; - any other key - stops the animation
(define (handle-key l ke)
(cond [(key=? ke "\r")
(make-gol (gol-life l) RUNNING)]
[(key=? ke "escape")
(make-gol '() STOPPED)]
[else
(make-gol (gol-life l) STOPPED)]))
No hay comentarios:
Publicar un comentario