Table of Contents
An ASCII version of Quadtree Grammars .
Source Code
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))))
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)))
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
Examples
Sierpinski Triangle
(cfg-expand 64 'a '((a . ((a a a ?\s) ?#))))
################################################################ # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## # # # # # # # # # # # # # # # # #### #### #### #### #### #### #### #### # # # # # # # # # # # # # # # # ## ## ## ## ## ## ## ## # # # # # # # # ######## ######## ######## ######## # # # # # # # # # # # # # # # # ## ## ## ## ## ## ## ## # # # # # # # # #### #### #### #### # # # # # # # # ## ## ## ## # # # # ################ ################ # # # # # # # # # # # # # # # # ## ## ## ## ## ## ## ## # # # # # # # # #### #### #### #### # # # # # # # # ## ## ## ## # # # # ######## ######## # # # # # # # # ## ## ## ## # # # # #### #### # # # # ## ## # # ################################ # # # # # # # # # # # # # # # # ## ## ## ## ## ## ## ## # # # # # # # # #### #### #### #### # # # # # # # # ## ## ## ## # # # # ######## ######## # # # # # # # # ## ## ## ## # # # # #### #### # # # # ## ## # # ################ # # # # # # # # ## ## ## ## # # # # #### #### # # # # ## ## # # ######## # # # # ## ## # # #### # # ## #
Example 2
(cfg-expand 64 'a '((a . ((?\s a ?# a) ?#))))
#
##
## #
####
#### #
#### ##
###### #
########
######## #
######## ##
######## ## #
######## ####
############ #
############ ##
############## #
################
################ #
################ ##
################ ## #
################ ####
################ #### #
################ #### ##
################ ###### #
################ ########
######################## #
######################## ##
######################## ## #
######################## ####
############################ #
############################ ##
############################## #
################################
################################ #
################################ ##
################################ ## #
################################ ####
################################ #### #
################################ #### ##
################################ ###### #
################################ ########
################################ ######## #
################################ ######## ##
################################ ######## ## #
################################ ######## ####
################################ ############ #
################################ ############ ##
################################ ############## #
################################ ################
################################################ #
################################################ ##
################################################ ## #
################################################ ####
################################################ #### #
################################################ #### ##
################################################ ###### #
################################################ ########
######################################################## #
######################################################## ##
######################################################## ## #
######################################################## ####
############################################################ #
############################################################ ##
############################################################## #
################################################################
Example 3
(cfg-expand 64 'a '((a . ((b c c a) ?.)) (b . ((?# b b ?#) ?#)) (c . ((?\s c c ?_) ?_))))
################################ _
################################ __
################################ ___
################################ ____
################################ _____
################################ ______
################################ _______
################################ ________
################################ _________
################################ __________
################################ ___________
################################ ____________
################################ _____________
################################ ______________
################################ _______________
################################ ________________
################################ _________________
################################ __________________
################################ ___________________
################################ ____________________
################################ _____________________
################################ ______________________
################################ _______________________
################################ ________________________
################################ _________________________
################################ __________________________
################################ ___________________________
################################ ____________________________
################################ _____________________________
################################ ______________________________
################################ _______________________________
################################________________________________
_################ _
__################ __
___################ ___
____################ ____
_____################ _____
______################ ______
_______################ _______
________################ ________
_________################ _________
__________################ __________
___________################ ___________
____________################ ____________
_____________################ _____________
______________################ ______________
_______________################ _______________
________________################________________
_________________ _######## _
__________________ __######## __
___________________ ___######## ___
____________________ ____######## ____
_____________________ _____######## _____
______________________ ______######## ______
_______________________ _______######## _______
________________________ ________########________
_________________________ _________ _#### _
__________________________ __________ __#### __
___________________________ ___________ ___#### ___
____________________________ ____________ ____####____
_____________________________ _____________ _____ _## _
______________________________ ______________ ______ __##__
_______________________________ _______________ _______ ___ _#_
_______________________________________________________________.
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) ?#))))
_
#
_
__
#_ _
# #
_
__
_ ___
# ____
#__ _
# __ __
## _#_ _
### # #
_
__
_ ___ _
# ____#
_ _____
__ ______
#_ _ _______
# # ________
#__ _ _
# ____ __
## ____ _ ___
### ____# ____
#### _ #__ _
#### __# __ __
#####_ _## _#_ _
##### # ### # #
_
__
_ ___ _ _
# ____# #
_ _____ _
__ ______ __
#_ _ _______ #_ _
# # ________# #
_ _________
__ __________
_ ___ ___________ _
# ____ ____________#
#__ _ _____________
# __ __ ______________
## _#_ _ _______________
### # # ________________
#__ _ _ _
# ____ __ __
## ____ ___ _ _ ___ _
### ________# # ____#
#### _ _____ _ _____
#### ________ __ ______
#####_ ________ #_ _ _______
##### # ________# # ________
######## _ #__ _ _
######## __ # ____ __
######## _ ___ ## ____ _ ___
######### ____### ____# ____
#########__ _ #### _ #__ _
######### __ __#### __# __ __
########## _#_ _#####_ _## _#_ _
########### # # ##### # ### # #
Example 5
(cfg-expand 64 'a '((a . ((?_ b ?. b) ?_)) (b . ((a ?\ a ?#) ?\ ))))
___________________________________________ ___________________________________________# ________________________________________.._ ________________________________________.._# ___________________________________________ #### ___________________________________________##### ________________________________________.._ #### ________________________________________.._##### ________________________________........___ ________________________________........___# ________________________________.........._ ________________________________.........._# ________________________________........___ #### ________________________________........___##### ________________________________.........._ #### ________________________________.........._##### ___________________________________________ ################ ___________________________________________# ################ ________________________________________.._ ################ ________________________________________.._# ################ ___________________________________________ #################### ___________________________________________##################### ________________________________________.._ #################### ________________________________________.._##################### ________________________________........___ ################ ________________________________........___# ################ ________________________________.........._ ################ ________________________________.........._# ################ ________________________________........___ #################### ________________________________........___##################### ________________________________.........._ #################### ________________________________.........._##################### ................................___________ ................................___________# ................................________.._ ................................________.._# ................................___________ #### ................................___________##### ................................________.._ #### ................................________.._##### ........................................___ ........................................___# .........................................._ .........................................._# ........................................___ #### ........................................___##### .........................................._ #### .........................................._##### ................................___________ ################ ................................___________# ################ ................................________.._ ################ ................................________.._# ################ ................................___________ #################### ................................___________##################### ................................________.._ #################### ................................________.._##################### ........................................___ ################ ........................................___# ################ .........................................._ ################ .........................................._# ################ ........................................___ #################### ........................................___##################### .........................................._ #################### .........................................._#####################
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) ?.))))
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . _._ _._ _._ _._ _._ _._ _._ _._ _._ _._ _._ _._ _._ _._ _._ _._ . #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #. ._._ _._._._ _._._._ _._._._ _._._._ _._._._ _._._._ _._._._ _._ . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ . #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #. _._ _._._._ _._ _._ _._._._ _._ _._ _._._._ _._ _._ _._._._ _._ . . . . ####. . . . . . ####. . . . . . ####. . . . . . ####. . _._ _._#### _._ _._ _._#### _._ _._ _._#### _._ _._ _._#### _._ . #.. #.####. #.. #.. #.####. #.. #.. #.####. #.. #.. #.####. #. ._._ _._####._._._._ _._####._._._._ _._####._._._._ _._####._._ . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ . #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #. ._._ _._._._ _._ _._ _._._._ _._._._ _._._._ _._ _._ _._._._ _._ . . . . . . . . ########. . . . . . . . . . . . ########. . . . _._ _._ _._ _._######## _._ _._ _._ _._ _._ _._######## _._ _._ . #.. #.. #.. #.########. #.. #.. #.. #.. #.. #.########. #.. #. ._._ _._._._ _._########._._ _._._._ _._._._ _._########._._ _._ . . ##. . . ##. ########. . ##. . . ##. . . ##. ########. . ##. _._## _ _._## _######## _._## _ _._## _ _._## _######## _._## _ . #.. #.. #.. #.########. #.. #.. #.. #.. #.. #.########. #.. #. _._ _._._._ _._######## _._ _._ _._ _._._._ _._######## _._ _._ . . . . ####. . . . . . ####. . . . . . ####. . . . . . ####. . _._ _._#### _._ _._ _._#### _._ _._ _._#### _._ _._ _._#### _._ . #.. #.####. #.. #.. #.####. #.. #.. #.####. #.. #.. #.####. #. ._._ _._####._._._._ _._####._._._._ _._####._._._._ _._####._._ . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ . #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #. _._ _._._._ _._ _._ _._._._ _._._._ _._._._ _._ _._ _._._._ _._ . . . . . . . . . . . . . . . . ################. . . . . . . . _._ _._ _._ _._ _._ _._ _._ _._################ _._ _._ _._ _._ . #.. #.. #.. #.. #.. #.. #.. #.################. #.. #.. #.. #. ._._ _._._._ _._._._ _._._._ _._################._._ _._._._ _._ . . ##. . . ##. . . ##. . . ##. ################. . ##. . . ##. _._## _ _._## _ _._## _ _._## _################ _._## _ _._## _ . #.. #.. #.. #.. #.. #.. #.. #.################. #.. #.. #.. #. _._ _._._._ _._ _._ _._._._ _._################ _._ _._._._ _._ . . . . ####. . . . . . ####. . ################. . . . ####. . _._ _._#### _._ _._ _._#### _._################ _._ _._#### _._ . #.. #.####. #.. #.. #.####. #.################. #.. #.####. #. ._._ _._####._._._._ _._####._._################._._ _._####._._ . . ##. . . ##. . . ##. . . ##. ################. . ##. . . ##. _._## _ _._## _ _._## _ _._## _################ _._## _ _._## _ . #.. #.. #.. #.. #.. #.. #.. #.################. #.. #.. #.. #. ._._ _._._._ _._ _._ _._._._ _._################._._ _._._._ _._ . . . . . . . . ########. . . . . . . . . . . . ########. . . . _._ _._ _._ _._######## _._ _._ _._ _._ _._ _._######## _._ _._ . #.. #.. #.. #.########. #.. #.. #.. #.. #.. #.########. #.. #. ._._ _._._._ _._########._._ _._._._ _._._._ _._########._._ _._ . . ##. . . ##. ########. . ##. . . ##. . . ##. ########. . ##. _._## _ _._## _######## _._## _ _._## _ _._## _######## _._## _ . #.. #.. #.. #.########. #.. #.. #.. #.. #.. #.########. #.. #. _._ _._._._ _._######## _._ _._ _._ _._._._ _._######## _._ _._ . . . . ####. . . . . . ####. . . . . . ####. . . . . . ####. . _._ _._#### _._ _._ _._#### _._ _._ _._#### _._ _._ _._#### _._ . #.. #.####. #.. #.. #.####. #.. #.. #.####. #.. #.. #.####. #. ._._ _._####._._._._ _._####._._._._ _._####._._._._ _._####._._ . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. . . ##. _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ _._## _ . #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #.. #. _._ _._._._ _._ _._ _._._._ _._._._ _._._._ _._ _._ _._._._ _._
Example 7
(cfg-expand 64 'a '((a . ((b a b ?\s) ?|)) (b . ((b c ?\s a) ?=)) (c . ((b ?_ c a) ?-))))
=-=_=-__=-=_____=-=_=-__________=-=_=-__=-=_____=-=_=-__=-=_=-=|
|-| |__ |-|____ |-| |__________ |-| |__ |-|____ |-| |__ |-| |=
=|=_=| =|____ =|=_=|________ =|=_=| =|____ =|=_=| =|=-
= -|= = ____ = -|= ________ = -|= = ____ = -|= = |
=-=|=-__=-=| =-=|________ =-=|=-__=-=| =-=|=-=_
|= |__ |= |= ________ |= |__ |= |= |-|
=- =_=|=- =- ________ =- =_=|=- =- =|
| -|= | | ________ | -|= | | =
=-=_=-=|=-=_____=-=_=-=| =-=_=-=|=-=_=-__
|-| |= |-|____ |-| |= |-| |= |-| |__
=|=- =|____ =|=- =|=- =|=_=|
= | = ____ = | = | = -|=
=-=_ =-__=-=|=-=_ =-=_ =-=|
|-| |__ |= |-| |-| |=
=| =_=|=- =| =| =-
= -|= | = = |
=-=_=-__=-=_=-=|=-=_=-__=-=_____
|-| |__ |-| |= |-| |__ |-|____
=|=_=| =|=- =|=_=| =|____
= -|= = | = -|= = ____
=-=|=-=_ =-=|=-__=-=|
|= |-| |= |__ |=
=- =| =- =_=|=-
| = | -|= |
=-=_=-__ =-=_=-=|
|-| |__ |-| |=
=|=_=| =|=-
= -|= = |
=-=| =-=_
|= |-|
=- =|
| =
=-=_=-__=-=_____=-=_=-__________
|-| |__ |-|____ |-| |__________
=|=_=| =|____ =|=_=|________
= -|= = ____ = -|= ________
=-=|=-__=-=| =-=|________
|= |__ |= |= ________
=- =_=|=- =- ________
| -|= | | ________
=-=_=-=|=-=_____=-=_=-=|
|-| |= |-|____ |-| |=
=|=- =|____ =|=-
= | = ____ = |
=-=_ =-__=-=|=-=_
|-| |__ |= |-|
=| =_=|=- =|
= -|= | =
=-=_=-__=-=_=-=|
|-| |__ |-| |=
=|=_=| =|=-
= -|= = |
=-=|=-=_
|= |-|
=- =|
| =
=-=_=-__
|-| |__
=|=_=|
= -|=
=-=|
|=
=-
|