Porting joegame to Hoot (I)

joegame has two high level components

• A full world tile generator and server, written in Common Lisp and only tested with sbcl.
• A javascript-based client which creates a seamless interface to explore the world.

The task we will be taking up for this series will concern mostly the first bit here. Currently, image data is generated at the server and sent over to the client as needed. While, as we will see, there has been some effort taken to optimize the relevant endpoints here, much of the current stagnation in development rests on the unsustainability of the model as a whole.

We can cache images liberally, and optimize paths at the server level, but this doesn't escape the fact that the world we are sustaining is big.

"How big is it?" First of all, as you can see above, we can distinguish a granular tilemap level from a world one. A tilemap is requested at a certain address: "/worldmap/:x/:y/:file/:rank" ; while at a world level we simply request "tiles" at x,y,z(oom) coordinates, "/worldtile/:z/:x/:y" . Tilemaps are a data structure which includes tile data and world features like trees and billboards. Tiles are images, returned from the server as 256x256 png images, and coordinated into the grid at a client level. Between these two is a relatively hard seperation, like moving from the map to the "street view." In this, and as a general note of focus for now, we can say that we are consider only the server, and only the tile images returned from the worldtile endpoint which is used at our world layer.

World tiles are at least inspired from (what we understand) other "real" tile servers do, where the z dimension scales things exponentially.

(defun world-tile (x y z)
  (declare (type integer x y z))
  (let* ((tz (expt 2 z))
         (tz-scale (* 1/256 tz)))
    (if (<= tz-scale 1)
        (worldconf:make-world-image-scaled worldconf:*worldconf* 256 256 tz-scale
                                           (* 256 (mod x tz))
                                           (* 256 (mod y tz)))
        *test-image*)))

The "natural" scale for is is 1/256, so z=8 gives us a scale of one, and z=0 is 1/256. At 0th zoom level, the entire world is represented as one 256x256 image, then 4, and so on, where zoom level 8 is a grid of 256x256 images.

In this, we can derive multiple answers to the "how big?" question. First of all, while remaining at a world tile level, a fully zoomed in picture of the world would need each dimension to be (2^8)*256, or 65536 (2¹⁶) pixels big, that is, 256 pictures at 256 size. But the total amount of pictures is a function of each zoom level's scale (256²)+(128)+…+(A/n²)

(defun bb/jgsize (n)
  (+ (expt n 2)
     (if (not (eql n 1))
         (bb/jgsize (/ n 2))
       0)))

(setq bb-jgsize
      (bb/jgsize 256))

(format  "There are %d distinct 256x256 pictures, for a total of %d pixels squared that must be calculated to generate it all" bb-jgsize (* bb-jgsize 256))

There are 87,381 distinct 256x256 pictures, for a total of 22,369,536 pixels squared (roughly 500 trillion) that must be theoretically calculated to generate it all.

It should also be noted that the amount of compute required for each tile is not the same, the empty ocean is quicker to figure our than a busy land area. But in general computation is evenly distributed across zoom levels. We said earlier that the "natural" scale for us is 8 (1/256). This means that the tiles for zoom levels above are generated by sampling the pixels returned at zoom level 8, where each pixel can be one to one:

  (defun get-top-color-sampled (conf x y n amount)
    (progn
      (let* ((resolved
               (resolve-sampled-terrains conf x y n amount))
             (c (render:parse-rgb-color
                 (if resolved
                     (color (car (last resolved)))
                     #xeeeeee))))
        (list
         (getf c :r)
         (getf c :g)
         (getf c :b)))))

  ...

(defmethod sample-val ((v value) (p point) n amount)
  (let
      ((pointmin p)
       (pointmax (++p p n)))
    (let ((vals (map 'list #'(lambda (thisp) (get-val v thisp))
                     (get-random-points pointmin pointmax amount))))
      (mean vals))))

Going back to our current project, we are aiming to reimplement everything needed to generate the world tile images. Currently they are transported as png images, but really raw pixel data is what is most important, and in fact there is only so many colors we know, so even using png data and absolute colors is currently probably a big point of inefficiency.

(setf *area-set*
       '((:deep-ocean . (:name "deep-ocean"
                         :color "#265272"
                         :animals (:|seaturtle|)
                         :objects ()
                         :image "images/terr_trench.png"
                         :wang-set :default))

         (:ocean . (:name "ocean"
                    :color "#4aa0df"
                    :animals (:|seaturtle|)
                    :image "images/terr_ocean.png"
                    :wang-set :default
                    :objects ()))


         ;;  a lot more...

         (:sand . (:name "sand"
                   :color "#ead2bd"
                   :image "images/terr_sand.png"
                   :wang-set :default)))))

There is some other things here, but the important thing to remember is that each pixel of a tile corresponds to a color defined here. With this though we can't delay any longer the real meat of the thing here, which is how the world is defined such that we can place pixels where we want them.

Inspired by shader languages, the world can be considered always one pixel at a time. We implement a very simple kind of DSL in lisp macros which creates a data structure that directs what to do to get pixels.

In a word, joegame is also this big:

(let ((size (expt 2 16)))
  (setf *worldconf*
        (__ :ocean
            (<>

             (circle&
              (circle&
               (not-circle&
                (in-circle&
                 (perlin~ 0.000028 208 '())
                  )

                 (point (/ size 2) (/ size 2))
                 (* (/ size 2) 2/3) 1.2)
                (point (* size 1/3) (* size 2/3))
                (/ size 3) 0.5)
               (point (* size 1/3) (* size 3/4))
               (* size 1/5) 1.3)
              (point (* size 2/3) (* size 1/2))
              (* size 1/3) 0.6)

             0.0 (__ :deep-ocean)
             7/16 (__ :ocean)
             8/16 (0 (__ :sand)
                     1/64 ( 0.0 (__ :grass)
                                1/8 (__ :dirt
                                        (<> (lat& (perlin~ 0.000128 218 '()) size )
                                            0.0 (<> (lon& (perlin~ 0.000128 218 '()) size)
                                                    0.0 (<> (perlin~ 0.000128 108 '())
                                                            0.0 (__ :grass)
                                                            4/9 (__ :forest))

  ;; etc etc ( about 14 lines abbreviated here for space)
                                            (+ 3/5 1/32) (__ :forest)))))))))

But in order to start unpacking this, we can look at a simpler example.

(in-circle& ;; a signal filter
 (filler~ '((1/2 (__ :ocean)) ;; a "fill" (always 1) signal, with two terrain children
             (1 (__ :sand))))
 '(:x 500 :y 500) ;; the filters coordinate param
 300) ;; the filters radius param

In our little language here, there are three kinds of entities: signals (for example filler~), terrains (sand and ocean here), and filters (in-circle&). Signals and terrains can have children, filters can have its "source" which is a signal or another filter. The basic procedure is as follows:

1. Enter at the top level.
2. If the current entity is a terrain, add it to the current stack
3. If the current entity has no children, return the stack.
4. If the current entity is a terrain, add it to the stack and move to step 5. If a signal, move to step 6.
5. Iterate through each child of the terrain, making it the current entity and moving to step 2. Return the resulting stack.
6. Get the value of the signal at the current x and y coordinates and use it to pick a child. A signal's value is always between 0.0-1.0 inclusive, and the value is mapped to the child based on its offset number. Make the decided upon child the current entity and move back to step 2.

In the above example, we have only one level to consider, we query the signal and return a stack with a single :ocean or :sand back. The filler always returns 1, but then we check if the coordinate in question is in the circle with a center at 500x500 and a radius of 300. If it is, the final value is a 1 and we get the highest child (sand), if it isn't the final value is "filtered out" and we get back 0.

In practice, we want some layering of the world. Grass grows ontop of soil, the shore springs out of the depths. This explains the rule around terrains having children, because otherwise terrains would always be leafs, and stacks would always be 1. In this way, we make things like this:

(__ :deep-ocean
    (perlin~ 102 0.3
             '((0.0 nil)
               (0.2 (__ :ocean)
                (0.7 (__ :shore
                      (perlin~ 123 0.8
                       '((0.3 (__ :grass))
                         (1.0 (__ :sand)))))))))

    (resolve-terrains *world* 123 123) ;; -> (:deep-ocean :shore :grass)

There is always deep ocean, if the first signal is over 0.2 its also regular ocean, if > 0.7, we add the shore and then see if there is grass or sand on it.

Finally, because we are only considered for now with our world tiles, we are not actually concerned about the full stack, only the "last" terrain (which above would be either deep-ocean, ocean, grass, or sand).

And that is pretty much it! We should have at least everything we need to get hootin. We need to recreate

To be continued…

guix shell guile-next guile-hoot