__________________________________ ASCII ART WITH QUADTREE GRAMMARS Leon Rische __________________________________ [2020-01-23 Thu 15:59] Table of Contents _________________ 1. Source Code 2. Introduction 3. Examples - [Text Version] - [HTML Version] [Text Version] [HTML Version] 1 Source Code ============= 1.1 Text Canvas ~~~~~~~~~~~~~~~ All data is stored in a long string. This string contains one character for each "pixel" of the image plus a newline after each row. ,---- | (defclass text-canvas () | ((data :initarg :data) | (width :initarg :width) | (height :initarg :height))) | | (defun make-text-canvas (width height &optional background) | "Create a text canvas of size (WIDTH, HEIGHT), optionally using | BACKGROUND as background character. If BACKGROUND is nil, spaces | are used." | (let ((data (make-string (* height (1+ width)) (or background ?\s)))) | ;; Add newlines | (dotimes (y height) | (setf (aref data (1- (* (1+ y) (1+ width)))) ?\n)) | (make-instance | 'text-canvas | :width width | :height height | :data data))) | | (defmethod set-pixel ((canvas text-canvas) x y v) | "Set the pixel at position (x, y) to value V." | (with-slots (width height data) canvas | (setf (aref data (+ x (* (1+ width) y))) v))) | | (defmethod set-rect ((canvas text-canvas) x y w h v) | "Set the rectangle at position (x, y) with size (w, h) to value | V." | (loop for x_ from x below (+ x w) do | (loop for y_ from y below (+ y h) do | (set-pixel canvas x_ y_ v)))) `---- 1.2 Quadtree Grammars ~~~~~~~~~~~~~~~~~~~~~ Now we can write a recursive function that expands a "quadtree grammar" to generate the contents of a text canvas. I'll explain how this works in the next section. ,---- | (defun cfg--expand (rules rule canvas x y size) | (if (characterp rule) | (set-rect canvas x y size size rule) | (let ((half (floor size 2))) | (destructuring-bind (rhs fallback) (alist-get rule rules) | (if (= size 1) | (set-rect | canvas | x y | size size | fallback) | (destructuring-bind (a b c d) rhs | (cfg--expand rules a canvas x y half) | (cfg--expand rules b canvas (+ x half) y half) | (cfg--expand rules c canvas x (+ y half) half) | (cfg--expand rules d canvas (+ x half) (+ y half) half))))))) | | (defun cfg-expand (size start grammar) | (let* ((canvas (make-text-canvas size size))) | (cfg--expand grammar start canvas 0 0 size) | (slot-value canvas 'data))) `---- 2 Introduction ============== A *quadtree* is a tree where each node has exactly four children. It can be interpreted / rendered e.g. as a (ASCII art) 2D image. To do so, the image is split up into four *quadrants* of equal size (top left, top right, bottom left, bottom right) either containing another quadtree or a leave node. Rules have the form `(name . (rhs fallback))'. ,---- | (cfg-expand 16 'a | '((a . ((?A ?B ?C ?D) ?A)))) `---- ,---- | AAAAAAAABBBBBBBB | AAAAAAAABBBBBBBB | AAAAAAAABBBBBBBB | AAAAAAAABBBBBBBB | AAAAAAAABBBBBBBB | AAAAAAAABBBBBBBB | AAAAAAAABBBBBBBB | AAAAAAAABBBBBBBB | CCCCCCCCDDDDDDDD | CCCCCCCCDDDDDDDD | CCCCCCCCDDDDDDDD | CCCCCCCCDDDDDDDD | CCCCCCCCDDDDDDDD | CCCCCCCCDDDDDDDD | CCCCCCCCDDDDDDDD | CCCCCCCCDDDDDDDD `---- `rhs' stands for *right hand side*. It is a list of four *terminals* or *non-terminals*, one for each quadrant of the quadtree. Terminals are characters (`?A', `?B', ... in EmacsLisp). If a terminal is encountered during expansion, the whole region of the quadtree is filled with this character. If a rule is expanded on a region of size 1, it is filled with the `fallback' character. If the RHS of the rule being expanded contains a non-terminal, this is interpreted as a reference to another rule that is used to generate the contents of the quadrant. ,---- | (cfg-expand 16 'a | '((a . ((?A ?B ?C a) ?A)))) `---- ,---- | AAAAAAAABBBBBBBB | AAAAAAAABBBBBBBB | AAAAAAAABBBBBBBB | AAAAAAAABBBBBBBB | AAAAAAAABBBBBBBB | AAAAAAAABBBBBBBB | AAAAAAAABBBBBBBB | AAAAAAAABBBBBBBB | CCCCCCCCAAAABBBB | CCCCCCCCAAAABBBB | CCCCCCCCAAAABBBB | CCCCCCCCAAAABBBB | CCCCCCCCCCCCAABB | CCCCCCCCCCCCAABB | CCCCCCCCCCCCCCAB | CCCCCCCCCCCCCCCA `---- 3 Examples ========== 3.1 Sierpinski Triangle ~~~~~~~~~~~~~~~~~~~~~~~ ,---- | (cfg-expand 64 'a | '((a . ((a a a ?\s) ?#)))) `---- ,---- | ################################################################ | # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## | # # # # # # # # # # # # # # # # | #### #### #### #### #### #### #### #### | # # # # # # # # # # # # # # # # | ## ## ## ## ## ## ## ## | # # # # # # # # | ######## ######## ######## ######## | # # # # # # # # # # # # # # # # | ## ## ## ## ## ## ## ## | # # # # # # # # | #### #### #### #### | # # # # # # # # | ## ## ## ## | # # # # | ################ ################ | # # # # # # # # # # # # # # # # | ## ## ## ## ## ## ## ## | # # # # # # # # | #### #### #### #### | # # # # # # # # | ## ## ## ## | # # # # | ######## ######## | # # # # # # # # | ## ## ## ## | # # # # | #### #### | # # # # | ## ## | # # | ################################ | # # # # # # # # # # # # # # # # | ## ## ## ## ## ## ## ## | # # # # # # # # | #### #### #### #### | # # # # # # # # | ## ## ## ## | # # # # | ######## ######## | # # # # # # # # | ## ## ## ## | # # # # | #### #### | # # # # | ## ## | # # | ################ | # # # # # # # # | ## ## ## ## | # # # # | #### #### | # # # # | ## ## | # # | ######## | # # # # | ## ## | # # | #### | # # | ## | # `---- 3.2 Example 2 ~~~~~~~~~~~~~ ,---- | (cfg-expand 64 'a | '((a . ((?\s a ?# a) ?#)))) `---- ,---- | # | ## | ## # | #### | #### # | #### ## | ###### # | ######## | ######## # | ######## ## | ######## ## # | ######## #### | ############ # | ############ ## | ############## # | ################ | ################ # | ################ ## | ################ ## # | ################ #### | ################ #### # | ################ #### ## | ################ ###### # | ################ ######## | ######################## # | ######################## ## | ######################## ## # | ######################## #### | ############################ # | ############################ ## | ############################## # | ################################ | ################################ # | ################################ ## | ################################ ## # | ################################ #### | ################################ #### # | ################################ #### ## | ################################ ###### # | ################################ ######## | ################################ ######## # | ################################ ######## ## | ################################ ######## ## # | ################################ ######## #### | ################################ ############ # | ################################ ############ ## | ################################ ############## # | ################################ ################ | ################################################ # | ################################################ ## | ################################################ ## # | ################################################ #### | ################################################ #### # | ################################################ #### ## | ################################################ ###### # | ################################################ ######## | ######################################################## # | ######################################################## ## | ######################################################## ## # | ######################################################## #### | ############################################################ # | ############################################################ ## | ############################################################## # | ################################################################ `---- 3.3 Example 3 ~~~~~~~~~~~~~ ,---- | (cfg-expand 64 'a | '((a . ((b c c a) ?.)) | (b . ((?# b b ?#) ?#)) | (c . ((?\s c c ?_) ?_)))) `---- ,---- | ################################ _ | ################################ __ | ################################ ___ | ################################ ____ | ################################ _____ | ################################ ______ | ################################ _______ | ################################ ________ | ################################ _________ | ################################ __________ | ################################ ___________ | ################################ ____________ | ################################ _____________ | ################################ ______________ | ################################ _______________ | ################################ ________________ | ################################ _________________ | ################################ __________________ | ################################ ___________________ | ################################ ____________________ | ################################ _____________________ | ################################ ______________________ | ################################ _______________________ | ################################ ________________________ | ################################ _________________________ | ################################ __________________________ | ################################ ___________________________ | ################################ ____________________________ | ################################ _____________________________ | ################################ ______________________________ | ################################ _______________________________ | ################################________________________________ | _################ _ | __################ __ | ___################ ___ | ____################ ____ | _____################ _____ | ______################ ______ | _______################ _______ | ________################ ________ | _________################ _________ | __________################ __________ | ___________################ ___________ | ____________################ ____________ | _____________################ _____________ | ______________################ ______________ | _______________################ _______________ | ________________################________________ | _________________ _######## _ | __________________ __######## __ | ___________________ ___######## ___ | ____________________ ____######## ____ | _____________________ _____######## _____ | ______________________ ______######## ______ | _______________________ _______######## _______ | ________________________ ________########________ | _________________________ _________ _#### _ | __________________________ __________ __#### __ | ___________________________ ___________ ___#### ___ | ____________________________ ____________ ____####____ | _____________________________ _____________ _____ _## _ | ______________________________ ______________ ______ __##__ | _______________________________ _______________ _______ ___ _#_ | _______________________________________________________________. `---- 3.4 Example 4 ~~~~~~~~~~~~~ ,---- | (cfg-expand 64 'a | '((a . ((?\s a c ?\s) ?\s)) | (b . ((b a ?\_ b) ?\_)) | (c . ((a b d c) ?\s)) | (d . ((d b ?# c) ?#)))) `---- ,---- | | | _ | # | _ | __ | #_ _ | # # | _ | __ | _ ___ | # ____ | #__ _ | # __ __ | ## _#_ _ | ### # # | _ | __ | _ ___ _ | # ____# | _ _____ | __ ______ | #_ _ _______ | # # ________ | #__ _ _ | # ____ __ | ## ____ _ ___ | ### ____# ____ | #### _ #__ _ | #### __# __ __ | #####_ _## _#_ _ | ##### # ### # # | _ | __ | _ ___ _ _ | # ____# # | _ _____ _ | __ ______ __ | #_ _ _______ #_ _ | # # ________# # | _ _________ | __ __________ | _ ___ ___________ _ | # ____ ____________# | #__ _ _____________ | # __ __ ______________ | ## _#_ _ _______________ | ### # # ________________ | #__ _ _ _ | # ____ __ __ | ## ____ ___ _ _ ___ _ | ### ________# # ____# | #### _ _____ _ _____ | #### ________ __ ______ | #####_ ________ #_ _ _______ | ##### # ________# # ________ | ######## _ #__ _ _ | ######## __ # ____ __ | ######## _ ___ ## ____ _ ___ | ######### ____### ____# ____ | #########__ _ #### _ #__ _ | ######### __ __#### __# __ __ | ########## _#_ _#####_ _## _#_ _ | ########### # # ##### # ### # # `---- 3.5 Example 5 ~~~~~~~~~~~~~ ,---- | (cfg-expand 64 'a | '((a . ((?_ b ?. b) ?_)) | (b . ((a ?\ a ?#) ?\ )))) `---- ,---- | ___________________________________________ | ___________________________________________# | ________________________________________.._ | ________________________________________.._# | ___________________________________________ #### | ___________________________________________##### | ________________________________________.._ #### | ________________________________________.._##### | ________________________________........___ | ________________________________........___# | ________________________________.........._ | ________________________________.........._# | ________________________________........___ #### | ________________________________........___##### | ________________________________.........._ #### | ________________________________.........._##### | ___________________________________________ ################ | ___________________________________________# ################ | ________________________________________.._ ################ | ________________________________________.._# ################ | ___________________________________________ #################### | ___________________________________________##################### | ________________________________________.._ #################### | ________________________________________.._##################### | ________________________________........___ ################ | ________________________________........___# ################ | ________________________________.........._ ################ | ________________________________.........._# ################ | ________________________________........___ #################### | ________________________________........___##################### | ________________________________.........._ #################### | ________________________________.........._##################### | ................................___________ | ................................___________# | ................................________.._ | ................................________.._# | ................................___________ #### | ................................___________##### | ................................________.._ #### | ................................________.._##### | ........................................___ | ........................................___# | .........................................._ | .........................................._# | ........................................___ #### | ........................................___##### | .........................................._ #### | .........................................._##### | ................................___________ ################ | ................................___________# ################ | ................................________.._ ################ | ................................________.._# ################ | ................................___________ #################### | ................................___________##################### | ................................________.._ #################### | ................................________.._##################### | ........................................___ ################ | ........................................___# ################ | .........................................._ ################ | .........................................._# ################ | ........................................___ #################### | ........................................___##################### | .........................................._ #################### | .........................................._##################### `---- 3.6 Example 6 ~~~~~~~~~~~~~ 0 -> 2 0 2 1 | white 1 -> black 2 2 1 | black 2 -> 2 0 0 1 | black ,---- | (cfg-expand 64 'a | '((a . ((c a c b) ?\s)) | (b . ((?# c c b) ?_)) | (c . ((c a a b) ?.)))) `---- ,---- | . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | _._ _._ _._ _._ _._ _._ _._ _._ _._ _._ _._ _._ _._ _._ _._ _._ | . #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #. | ._._ _._._._ _._._._ _._._._ _._._._ _._._._ _._._._ _._._._ _._ | . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. | _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ | . #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #. | _._ _._._._ _._ _._ _._._._ _._ _._ _._._._ _._ _._ _._._._ _._ | . . . . ####. . . . . . ####. . . . . . ####. . . . . . ####. . | _._ _._#### _._ _._ _._#### _._ _._ _._#### _._ _._ _._#### _._ | . #.. #.####. #.. #.. #.####. #.. #.. #.####. #.. #.. #.####. #. | ._._ _._####._._._._ _._####._._._._ _._####._._._._ _._####._._ | . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. | _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ | . #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #. | ._._ _._._._ _._ _._ _._._._ _._._._ _._._._ _._ _._ _._._._ _._ | . . . . . . . . ########. . . . . . . . . . . . ########. . . . | _._ _._ _._ _._######## _._ _._ _._ _._ _._ _._######## _._ _._ | . #.. #.. #.. #.########. #.. #.. #.. #.. #.. #.########. #.. #. | ._._ _._._._ _._########._._ _._._._ _._._._ _._########._._ _._ | . . ##. . . ##. ########. . ##. . . ##. . . ##. ########. . ##. | _._## _ _._## _######## _._## _ _._## _ _._## _######## _._## _ | . #.. #.. #.. #.########. #.. #.. #.. #.. #.. #.########. #.. #. | _._ _._._._ _._######## _._ _._ _._ _._._._ _._######## _._ _._ | . . . . ####. . . . . . ####. . . . . . ####. . . . . . ####. . | _._ _._#### _._ _._ _._#### _._ _._ _._#### _._ _._ _._#### _._ | . #.. #.####. #.. #.. #.####. #.. #.. #.####. #.. #.. #.####. #. | ._._ _._####._._._._ _._####._._._._ _._####._._._._ _._####._._ | . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. | _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ | . #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #. | _._ _._._._ _._ _._ _._._._ _._._._ _._._._ _._ _._ _._._._ _._ | . . . . . . . . . . . . . . . . ################. . . . . . . . | _._ _._ _._ _._ _._ _._ _._ _._################ _._ _._ _._ _._ | . #.. #.. #.. #.. #.. #.. #.. #.################. #.. #.. #.. #. | ._._ _._._._ _._._._ _._._._ _._################._._ _._._._ _._ | . . ##. . . ##. . . ##. . . ##. ################. . ##. . . ##. | _._## _ _._## _ _._## _ _._## _################ _._## _ _._## _ | . #.. #.. #.. #.. #.. #.. #.. #.################. #.. #.. #.. #. | _._ _._._._ _._ _._ _._._._ _._################ _._ _._._._ _._ | . . . . ####. . . . . . ####. . ################. . . . ####. . | _._ _._#### _._ _._ _._#### _._################ _._ _._#### _._ | . #.. #.####. #.. #.. #.####. #.################. #.. #.####. #. | ._._ _._####._._._._ _._####._._################._._ _._####._._ | . . ##. . . ##. . . ##. . . ##. ################. . ##. . . ##. | _._## _ _._## _ _._## _ _._## _################ _._## _ _._## _ | . #.. #.. #.. #.. #.. #.. #.. #.################. #.. #.. #.. #. | ._._ _._._._ _._ _._ _._._._ _._################._._ _._._._ _._ | . . . . . . . . ########. . . . . . . . . . . . ########. . . . | _._ _._ _._ _._######## _._ _._ _._ _._ _._ _._######## _._ _._ | . #.. #.. #.. #.########. #.. #.. #.. #.. #.. #.########. #.. #. | ._._ _._._._ _._########._._ _._._._ _._._._ _._########._._ _._ | . . ##. . . ##. ########. . ##. . . ##. . . ##. ########. . ##. | _._## _ _._## _######## _._## _ _._## _ _._## _######## _._## _ | . #.. #.. #.. #.########. #.. #.. #.. #.. #.. #.########. #.. #. | _._ _._._._ _._######## _._ _._ _._ _._._._ _._######## _._ _._ | . . . . ####. . . . . . ####. . . . . . ####. . . . . . ####. . | _._ _._#### _._ _._ _._#### _._ _._ _._#### _._ _._ _._#### _._ | . #.. #.####. #.. #.. #.####. #.. #.. #.####. #.. #.. #.####. #. | ._._ _._####._._._._ _._####._._._._ _._####._._._._ _._####._._ | . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. | _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ | . #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #. | _._ _._._._ _._ _._ _._._._ _._._._ _._._._ _._ _._ _._._._ _._ `---- 3.7 Example 7 ~~~~~~~~~~~~~ ,---- | (cfg-expand 64 'a | '((a . ((b a b ?\s) ?|)) | (b . ((b c ?\s a) ?=)) | (c . ((b ?_ c a) ?-)))) `---- ,---- | =-=_=-__=-=_____=-=_=-__________=-=_=-__=-=_____=-=_=-__=-=_=-=| | |-| |__ |-|____ |-| |__________ |-| |__ |-|____ |-| |__ |-| |= | =|=_=| =|____ =|=_=|________ =|=_=| =|____ =|=_=| =|=- | = -|= = ____ = -|= ________ = -|= = ____ = -|= = | | =-=|=-__=-=| =-=|________ =-=|=-__=-=| =-=|=-=_ | |= |__ |= |= ________ |= |__ |= |= |-| | =- =_=|=- =- ________ =- =_=|=- =- =| | | -|= | | ________ | -|= | | = | =-=_=-=|=-=_____=-=_=-=| =-=_=-=|=-=_=-__ | |-| |= |-|____ |-| |= |-| |= |-| |__ | =|=- =|____ =|=- =|=- =|=_=| | = | = ____ = | = | = -|= | =-=_ =-__=-=|=-=_ =-=_ =-=| | |-| |__ |= |-| |-| |= | =| =_=|=- =| =| =- | = -|= | = = | | =-=_=-__=-=_=-=|=-=_=-__=-=_____ | |-| |__ |-| |= |-| |__ |-|____ | =|=_=| =|=- =|=_=| =|____ | = -|= = | = -|= = ____ | =-=|=-=_ =-=|=-__=-=| | |= |-| |= |__ |= | =- =| =- =_=|=- | | = | -|= | | =-=_=-__ =-=_=-=| | |-| |__ |-| |= | =|=_=| =|=- | = -|= = | | =-=| =-=_ | |= |-| | =- =| | | = | =-=_=-__=-=_____=-=_=-__________ | |-| |__ |-|____ |-| |__________ | =|=_=| =|____ =|=_=|________ | = -|= = ____ = -|= ________ | =-=|=-__=-=| =-=|________ | |= |__ |= |= ________ | =- =_=|=- =- ________ | | -|= | | ________ | =-=_=-=|=-=_____=-=_=-=| | |-| |= |-|____ |-| |= | =|=- =|____ =|=- | = | = ____ = | | =-=_ =-__=-=|=-=_ | |-| |__ |= |-| | =| =_=|=- =| | = -|= | = | =-=_=-__=-=_=-=| | |-| |__ |-| |= | =|=_=| =|=- | = -|= = | | =-=|=-=_ | |= |-| | =- =| | | = | =-=_=-__ | |-| |__ | =|=_=| | = -|= | =-=| | |= | =- | | `----