ASCII Art with Quadtree Grammars

Keywords: art
Created: 2020-01-23 Thu 15:59
Table of Contents

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) ?-))))
=-=_=-__=-=_____=-=_=-__________=-=_=-__=-=_____=-=_=-__=-=_=-=|
 |-| |__ |-|____ |-| |__________ |-| |__ |-|____ |-| |__ |-| |=
  =|=_=|  =|____  =|=_=|________  =|=_=|  =|____  =|=_=|  =|=-
  = -|=   = ____  = -|= ________  = -|=   = ____  = -|=   =  |
    =-=|=-__=-=|    =-=|________    =-=|=-__=-=|    =-=|=-=_
     |=  |__ |=      |= ________     |=  |__ |=      |=  |-|
    =-  =_=|=-      =-  ________    =-  =_=|=-      =-    =|
     |  -|=  |       |  ________     |  -|=  |       |    =
        =-=_=-=|=-=_____=-=_=-=|        =-=_=-=|=-=_=-__
         |-| |=  |-|____ |-| |=          |-| |=  |-| |__
          =|=-    =|____  =|=-            =|=-    =|=_=|
          =  |    = ____  =  |            =  |    = -|=
        =-=_    =-__=-=|=-=_            =-=_        =-=|
         |-|     |__ |=  |-|             |-|         |=
          =|    =_=|=-    =|              =|        =-
          =     -|=  |    =               =          |
                =-=_=-__=-=_=-=|=-=_=-__=-=_____
                 |-| |__ |-| |=  |-| |__ |-|____
                  =|=_=|  =|=-    =|=_=|  =|____
                  = -|=   =  |    = -|=   = ____
                    =-=|=-=_        =-=|=-__=-=|
                     |=  |-|         |=  |__ |=
                    =-    =|        =-  =_=|=-
                     |    =          |  -|=  |
                =-=_=-__                =-=_=-=|
                 |-| |__                 |-| |=
                  =|=_=|                  =|=-
                  = -|=                   =  |
                    =-=|                =-=_
                     |=                  |-|
                    =-                    =|
                     |                    =
=-=_=-__=-=_____=-=_=-__________
 |-| |__ |-|____ |-| |__________
  =|=_=|  =|____  =|=_=|________
  = -|=   = ____  = -|= ________
    =-=|=-__=-=|    =-=|________
     |=  |__ |=      |= ________
    =-  =_=|=-      =-  ________
     |  -|=  |       |  ________
        =-=_=-=|=-=_____=-=_=-=|
         |-| |=  |-|____ |-| |=
          =|=-    =|____  =|=-
          =  |    = ____  =  |
        =-=_    =-__=-=|=-=_
         |-|     |__ |=  |-|
          =|    =_=|=-    =|
          =     -|=  |    =
                =-=_=-__=-=_=-=|
                 |-| |__ |-| |=
                  =|=_=|  =|=-
                  = -|=   =  |
                    =-=|=-=_
                     |=  |-|
                    =-    =|
                     |    =
                =-=_=-__
                 |-| |__
                  =|=_=|
                  = -|=
                    =-=|
                     |=
                    =-
                     |

Last export: 2020-07-12 Sun 22:29
This document is also available as plain text and pdf.

If you have an idea how this page could be improved or a comment send me a mail.