13 October 2013

Minecraft4k in Lisp and C++

Abstract

Markus Persson wrote his JavaScript Minecraft4k "to test what's possible in JS and HTML5." It gives an impression of travel down a never-ending tunnel of blocks. Here I recode Minecraft4k in C++ and Lisp. There is an 80:1 performance difference between the C++ and Lisp versions. I speculate this is because I'm doing Lisp wrong.


Simplified Minecraft4k in C++

I first heard of Notch's Minecraft4k on Hacker News, where I also saw Salvatore Sanfilippo's simplified reimplementation. I thought it was cool; achieving a lot with a little code is attractive. Fun.

Compared to the original the simplified version eliminates the code that generates the texture map and the view down the tunnel of moving blocks remains straight down the Z-axis, so there is less code to write. A good place to start:

gem.h:
#ifndef GEM_H_INCLUDED
#define GEM_H_INCLUDED

// a simple wrapper around GLFW for the Minecraft4k code
// this code is public domain - use at your own risk

#include <GLFW/glfw3.h>
#include <cmath>
#include <ctime>
#include <vector>
#include <stdint.h>
#include <iostream>


class gem { // graphics environment manager
public:
    gem(int frame_width, int frame_height, int scale)
    : good_(false), width_(frame_width), height_(frame_height),
      scale_(scale), fps_counter_(0), clock_(0), window_(0)
    {
        frame_buf_.resize(width_ * height_);
        if (glfwInit()) {
            good_ = true;
            window_ = glfwCreateWindow(width_*scale_, height_*scale_,
                "mc4k - press Esc to exit", 0, 0);
            if (window_) {
                glfwSetKeyCallback(window_, key_callback);
                glfwMakeContextCurrent(window_);
                glfwSwapInterval(1);
            }
        }
    }
    
    ~gem()
    {
        if (good_)
            glfwTerminate();
    }
    
    typedef void renderer(void * private_data, uint32_t * frame_buf);

    // repeatedly display frames until user quits
    void run(renderer * render, void * private_renderer_data)
    {
        while (good_ && window_) {
            render(private_renderer_data, &frame_buf_[0]);
            glClear(GL_COLOR_BUFFER_BIT);
            glPixelZoom((float)scale_, (float)scale_);
            glDrawPixels(width_, height_, GL_RGBA, GL_UNSIGNED_BYTE, &frame_buf_[0]);
            glfwSwapBuffers(window_);
            glfwPollEvents();
            if (glfwWindowShouldClose(window_))
                break;

            // display the frames per second count every second
            ++fps_counter_;
            if (clock() - clock_ > CLOCKS_PER_SEC) {
                std::cerr << fps_counter_ << " FPS\n";
                fps_counter_ = 0;
                clock_ = clock();
            }
        }
    }
    
private:
    bool good_; // good_ <=> GLFW library initialised successfully
    int width_; // frame buffer width in pixels
    int height_; // frame buffer height in pixels
    int scale_; // each pxl in frame buf displayed as scale_ x scale_ pxls on screen
    int fps_counter_; // running count of frames this second
    clock_t clock_; // time of last FPS printout
    GLFWwindow * window_; // the GLFW window handle
    std::vector<uint32_t> frame_buf_; // width_ x height_ pixels

    static void key_callback(GLFWwindow * window, int key, int, int action, int)
    {
        if (key == GLFW_KEY_ESCAPE && action == GLFW_PRESS)
            glfwSetWindowShouldClose(window, GL_TRUE);
    }
};


#endif

mc4ka.cpp:
// mc4ka.cpp: Simplified Minecraft4k
// This version by Anthony C. Hay - http://howtowriteaprogram.blogspot.co.uk/
// Based on work by Salvatore Sanfilippo - https://gist.github.com/4195130
// Which, in turn was based on Markus Persson's Minecraft4k - http://jsdo.it/notch/dB1E
// This code is public domain - use at your own risk

#include "gem.h"
#include <cstdlib>


// the block world map is stored in a cube of side mapdim; each map entry
// determines the colour of the corresponding block
const int mappow = 6;
const int mapdim = 1 << mappow;
const int mapmask = mapdim - 1;

// these are the image dimentions used in Minecraft4k
const int width = 428;
const int height = 240;
const int scale = 2;


// return map index of block at given int co-ordinates
inline int mapindex(int x, int y, int z)
{
    return (z & mapmask) << (mappow << 1) | (y & mapmask) << mappow | (x & mapmask);
}

// return map index of block at given float co-ordinates
inline int mapindex(float x, float y, float z)
{
    return mapindex(static_cast<int>(x), static_cast<int>(y), static_cast<int>(z));
}

// return frame buffer index of pixel at given co-ordinates; (0, 0) is top left
inline int framebufindex(int x, int y)
{
    // the OpenGL frame buffer origin is at botom left
    return width * (height - y - 1) + x;
}

// return a random number between 0 and 1
inline float frand()
{
    return static_cast<float>(rand()) / RAND_MAX;
}

// return pixel of given colour
inline uint32_t rgba(uint32_t r, uint32_t g, uint32_t b)
{
    return 0xFF000000 | b << 16 | g << 8 | r;
}


// create the world map
std::vector<uint32_t> generate_map()
{
    std::vector<uint32_t> map(mapdim * mapdim * mapdim);
    
    for (int x = 0; x < mapdim; x++) {
        for (int y = 0; y < mapdim; y++) {
            for (int z = 0; z < mapdim; z++) {
                float yd = (y - 32.5f) * 0.4f;
                float zd = (z - 32.5f) * 0.4f;
                if (frand() > sqrt(sqrt(yd * yd + zd * zd)) - 0.8 || frand() < 0.6)
                    map[mapindex(x,y,z)] = 0; // there won't be a block here
                else
                    map[mapindex(x,y,z)] = 0x00FFFFFF & (rand() * rand()); // block colour
            }
        }
    }
    
    return map;
}


// render the next frame into the given 'frame_buf'
void render_blocks(void * private_renderer_data, uint32_t * frame_buf)
{
    // the given void * is our world map
    const uint32_t * map = reinterpret_cast<uint32_t *>(private_renderer_data);
    
    float dx = static_cast<float>(clock() % (CLOCKS_PER_SEC * 10)) / (CLOCKS_PER_SEC * 10);
    float ox = 32.5f + dx * mapdim;
    float oy = 32.5;
    float oz = 32.5;
    
    for (int x = 0; x < width; ++x) {
        const float rotzd = static_cast<float>(x - width / 2) / height;

        for (int y = 0; y < height; ++y) {
            const float rotyd = static_cast<float>(y - height / 2) / height;
            const float rotxd = 1;
            uint32_t col = 0;
            uint32_t br = 255;
            float ddist = 0;
            float closest = 32;

            for (int d = 0; d < 3; d++) {
                const float dimLength = d == 0 ? rotxd : d == 1 ? rotyd : rotzd;
                const float ll = 1 / fabs(dimLength);
                const float xd = rotxd * ll;
                const float yd = rotyd * ll;
                const float zd = rotzd * ll;
                float initial;
                switch (d) {
                    case 0: initial = ox - static_cast<int>(ox); break;
                    case 1: initial = oy - static_cast<int>(oy); break;
                    default: initial = oz - static_cast<int>(oz); break;
                }
                if (dimLength > 0)
                    initial = 1 - initial;
                float dist = ll * initial;
                float xp = ox + xd * initial;
                float yp = oy + yd * initial;
                float zp = oz + zd * initial;
                if (dimLength < 0)
                    --(d == 0 ? xp : d == 1 ? yp : zp);
                
                while (dist < closest) {
                    uint32_t tex = map[mapindex(xp, yp, zp)];
                    if (tex > 0) {
                        col = tex;
                        ddist = static_cast<float>(255 - static_cast<int>(dist / 32 * 255));
                        br = 255 * (255 - ((d + 2) % 3) * 50) / 255;
                        closest = dist;
                    }
                    xp += xd;
                    yp += yd;
                    zp += zd;
                    dist += ll;
                }
            }
            
            const uint32_t r = static_cast<uint32_t>(((col >> 16) & 0xff) * br * ddist / (255 * 255));
            const uint32_t g = static_cast<uint32_t>(((col >> 8) & 0xff) * br * ddist / (255 * 255));
            const uint32_t b = static_cast<uint32_t>(((col) & 0xff) * br * ddist / (255 * 255));
            
            frame_buf[framebufindex(x, y)] = rgba(r, g, b);
        }
    }
}


int main()
{
    std::vector<uint32_t> map(generate_map());
    gem graphics(width, height, scale);
    graphics.run(render_blocks, &map[0]);
}

Note: this is my first OpenGL project and my first GLFW project, so it may well not be "best practice." However, I've compiled and run this on Windows 7 and OS X and it works. There are some notes on how to compile this code in the Appendix below.


Minecraft4k in C++

Having got Sanfilippo's simplified variant working in C++ I went back to Notch's original JavaScript version and ported that to C++:

mc4kb.cpp:
// mc4kb.cpp: Minecraft4k
// This version by Anthony C. Hay - http://howtowriteaprogram.blogspot.co.uk/
// Based on Markus Persson's Minecraft4k - http://jsdo.it/notch/dB1E
// This code is public domain - use at your own risk

#include "gem.h"
#include <cstdlib>


// the block world map is stored in a cube of side mapdim; each map entry
// determines the colour of the corresponding block
const int mappow = 6;
const int mapdim = 1 << mappow;
const int mapmask = mapdim - 1;

// these are the image dimentions used in Minecraft4k
const int width = 428;
const int height = 240;
const int scale = 2;


// return map index of block at given int co-ordinates
inline int mapindex(int x, int y, int z)
{
    return (z & mapmask) << (mappow << 1) | (y & mapmask) << mappow | (x & mapmask);
}

// return map index of block at given float co-ordinates
inline int mapindex(float x, float y, float z)
{
    return mapindex(static_cast<int>(x), static_cast<int>(y), static_cast<int>(z));
}

// return frame buffer index of pixel at given co-ordinates; (0, 0) is top left
inline int framebufindex(int x, int y)
{
    // the OpenGL frame buffer origin is at botom left
    return width * (height - y - 1) + x;
}

// return a random number between 0 and 1
inline float frand()
{
    return static_cast<float>(rand()) / RAND_MAX;
}

// return pixel of given colour
inline uint32_t rgba(uint32_t r, uint32_t g, uint32_t b)
{
    return 0xFF000000 | b << 16 | g << 8 | r;
}


// algorithmicly generate bricks and wood and water and ground and ...
std::vector<uint32_t> generate_textures()
{
    std::vector<uint32_t> texmap(16 * 16 * 3 * 16);
    
    for (int i = 1; i < 16; ++i) {
        float br = 255.0f - rand() % 96;
        for (int y = 0; y < 16 * 3; ++y) {
            for (int x = 0; x < 16; ++x) {
                uint32_t color = 0x966C4A; // ground
                
                if (i == 4) // stone
                    color = 0x7F7F7F;
                
                if (i != 4 || rand() % 3 == 0)
                    br = 255.0f - rand() % 96;
                
                if ((i == 1 && y < (((x * x * 3 + x * 81) >> 2) & 3) + 18))
                    color = 0x6AAA40; // grass
                else if ((i == 1 && y < (((x * x * 3 + x * 81) >> 2) & 3) + 19))
                    br = br * 2 / 3;
                
                if (i == 7) { // wood
                    color = 0x675231;
                    if (x > 0 && x < 15 && ((y > 0 && y < 15) || (y > 32 && y < 47))) {
                        color = 0xBC9862;
                        float xd = x - 7.0f;
                        float yd = (y & 15) - 7.0f;
                        if (xd < 0)
                            xd = 1 - xd;
                        if (yd < 0)
                            yd = 1 - yd;
                        if (yd > xd)
                            xd = yd;
                        
                        br = 196.0f - rand() % 32 + static_cast<int>(xd) % 3 * 32;
                    }
                    else if (rand() % 2 == 0)
                        br = br * (150 - (x & 1) * 100) / 100;
                }
                
                if (i == 5) { // brick
                    color = 0xB53A15;
                    if ((x + (y >> 2) * 4) % 8 == 0 || y % 4 == 0)
                        color = 0xBCAFA5;
                }
                
                if (i == 9) // water
                    color = 0x4040ff;
                
                uint32_t brr = static_cast<uint32_t>(br);
                if (y >= 32)
                    brr /= 2;
                
                if (i == 8) { // leaves
                    color = 0x50D937;
                    if (rand() % 2 == 0) {
                        color = 0;
                        brr = 255;
                    }
                }
                
                uint32_t col = (((color >> 16) & 0xff) * brr / 255) << 16
                             | (((color >> 8) & 0xff) * brr / 255) << 8
                             | (((color) & 0xff) * brr / 255);
                texmap[x + y * 16 + i * 256 * 3] = col;
            }
        }
    }
    
    return texmap;
}


// create the world map
std::vector<uint32_t> generate_map()
{
    std::vector<uint32_t> map(mapdim * mapdim * mapdim);
    
    for (int x = 0; x < mapdim; x++) {
        for (int y = 0; y < mapdim; y++) {
            for (int z = 0; z < mapdim; z++) {
                float yd = (y - 32.5f) * 0.4f;
                float zd = (z - 32.5f) * 0.4f;
                if (frand() > sqrt(sqrt(yd * yd + zd * zd)) - 0.8 || frand() < 0.6)
                    map[mapindex(x,y,z)] = 0; // there won't be a block here
                else
                    map[mapindex(x,y,z)] = rand() % 16; // assign a block type (or none)
            }
        }
    }
    
    return map;
}


struct render_info { // bundle of data used in render_minecraft()
    std::vector<uint32_t> map;
    std::vector<uint32_t> texmap;
    
    render_info()
    : map(generate_map()), texmap(generate_textures())
    {
    }
};


// render the next frame into the given 'frame_buf'
void render_minecraft(void * private_renderer_data, uint32_t * frame_buf)
{
    const render_info * info = reinterpret_cast<render_info *>(private_renderer_data);
    const uint32_t * map = &info->map[0];
    const uint32_t * texmap = &info->texmap[0];
    const float pi = 3.14159265f;
    
    const float dx = static_cast<float>(clock() % (CLOCKS_PER_SEC * 10)) / (CLOCKS_PER_SEC * 10);
    const float xRot = sin(dx * pi * 2) * 0.4f + pi / 2;
    const float yRot = cos(dx * pi * 2) * 0.4f;
    const float yCos = cos(yRot);
    const float ySin = sin(yRot);
    const float xCos = cos(xRot);
    const float xSin = sin(xRot);
    const float ox = 32.5f + dx * 64;
    const float oy = 32.5f;
    const float oz = 32.5f;
    
    for (int x = 0; x < width; ++x) {
        float ___xd = (x - width / 2.0f) / height;

        for (int y = 0; y < height; ++y) {
            const float __yd = (y - height / 2.0f) / height;
            const float __zd = 1;
            
            const float ___zd = __zd * yCos + __yd * ySin;
            const float _yd = __yd * yCos - __zd * ySin;
            
            const float _xd = ___xd * xCos + ___zd * xSin;
            const float _zd = ___zd * xCos - ___xd * xSin;
            
            uint32_t col = 0;
            uint32_t br = 255;
            float ddist = 0;
            float closest = 32;
            
            for (int d = 0; d < 3; ++d) {
                const float dimLength = d == 0 ? _xd : d == 1 ? _yd : _zd;
                float ll = 1 / (dimLength < 0 ? -dimLength : dimLength);
                float xd = (_xd) * ll;
                float yd = (_yd) * ll;
                float zd = (_zd) * ll;
                float initial;
                switch (d) {
                    case 0: initial = ox - static_cast<int>(ox); break;
                    case 1: initial = oy - static_cast<int>(oy); break;
                    default: initial = oz - static_cast<int>(oz); break;
                }
                if (dimLength > 0)
                    initial = 1 - initial;
                float dist = ll * initial;
                float xp = ox + xd * initial;
                float yp = oy + yd * initial;
                float zp = oz + zd * initial;
                if (dimLength < 0)
                    --(d == 0 ? xp : d == 1 ? yp : zp);
                
                while (dist < closest) {
                    uint32_t tex = map[mapindex(xp, yp, zp)];
                    
                    if (tex > 0) {
                        uint32_t u = (uint32_t)((xp + zp) * 16) & 15;
                        uint32_t v = ((uint32_t)(yp * 16) & 15) + 16;
                        if (d == 1) {
                            u = (uint32_t)(xp * 16) & 15;
                            v = ((uint32_t)(zp * 16) & 15);
                            if (yd < 0)
                                v += 32;
                        }
                        
                        uint32_t cc = texmap[u + v * 16 + tex * 256 * 3];
                        if (cc > 0) {
                            col = cc;
                            ddist = static_cast<float>(255 - static_cast<int>(dist / 32 * 255));
                            br = 255 * (255 - ((d + 2) % 3) * 50) / 255;
                            closest = dist;
                        }
                    }
                    xp += xd;
                    yp += yd;
                    zp += zd;
                    dist += ll;
                }
            }
            
            const uint32_t r = static_cast<uint32_t>(((col >> 16) & 0xff) * br * ddist / (255 * 255));
            const uint32_t g = static_cast<uint32_t>(((col >> 8) & 0xff) * br * ddist / (255 * 255));
            const uint32_t b = static_cast<uint32_t>(((col) & 0xff) * br * ddist / (255 * 255));
            
            frame_buf[framebufindex(x, y)] = rgba(r, g, b);
        }
    }
}


int main()
{
    render_info info;
    gem graphics(width, height, scale);
    graphics.run(render_minecraft, &info);
}


Simplified Minecraft4k in Lisp

Lisp appeals to me for many reasons, probably mostly the same reasons it appeals to many other people. I think it's fair to say Lisp isn't a mainstream, corporate language. And that's one reason.

This is what I wrote:

mc4ka.scm:
#lang racket/gui
; mc4ka.scm: Simplified Minecraft4k
; This version by Anthony C. Hay - http://howtowriteaprogram.blogspot.co.uk/
; Based on work by Salvatore Sanfilippo - https://gist.github.com/4195130
; Which, in turn was based on Markus Persson's Minecraft4k - http://jsdo.it/notch/dB1E
; This code is public domain - use at your own risk


(require (lib "gl.ss" "sgl")
         (lib "gl-vectors.ss" "sgl"))


; graphics environment manager canvas class
(define gem-canvas%
  (class* canvas% ()
    (inherit with-gl-context swap-gl-buffers)
    (init-field frame-buf width height scale)

   (define/override (on-paint)
      (with-gl-context
        (lambda ()
          (glClearColor 0.0 0.0 0.0 0.0)
          (glClear GL_COLOR_BUFFER_BIT)
          (glPixelZoom scale scale)
          (glDrawPixels width height GL_RGBA GL_UNSIGNED_BYTE frame-buf)
          (swap-gl-buffers))))

    (define/override (on-size width height)
      (with-gl-context
        (lambda ()
          (glViewport 0 0 width height))))

    (define/override (on-char key)
      (when (equal? (send key get-key-code) #\q)
        (exit)))

    (super-instantiate () (style '(gl)))
  )
)


; graphics environment manager class
(define gem%
  (class object%
    (super-new)
    (init-field width height scale title)
    (field
     ; frame-buf is width by height pixels, with 4 bytes per pixel
     (frame-buf (make-gl-ubyte-vector (* width height 4)))
     (win (new frame% (label title) (min-width (* width scale)) (min-height (* height scale))))
     (gl (new gem-canvas% (parent win) (frame-buf frame-buf) (width width) (height height) (scale scale))))

    ; repeatedly display frames until user quits
    (define/public (run renderer private-renderer-data)
      (define (run-loop)
        (renderer private-renderer-data frame-buf)
        (send gl on-paint)
        (queue-callback run-loop #f))
      (send win show #t)
      (run-loop))
  )
)


; the block world map is stored in a cube of side mapdim; each map entry
; determines the colour of the corresponding block
(define MAPPOW 6)
(define MAPDIM (expt 2 MAPPOW))
(define MAPMASK (- MAPDIM 1))

; these are the image dimentions used in Minecraft4k
(define WIDTH 428)
(define HEIGHT 240)
(define SCALE 2)


; return map index of block at given (integer) co-ordinates
(define (mapindex x y z)
  (bitwise-ior
   (arithmetic-shift (bitwise-and z MAPMASK) (* MAPPOW 2))
   (arithmetic-shift (bitwise-and y MAPMASK) MAPPOW)
   (bitwise-and x MAPMASK)))

; return map index of block at given (real) co-ordinates
(define (mapindexf x y z)
  (mapindex (inexact->exact (floor x)) (inexact->exact (floor y)) (inexact->exact (floor z))))


; return frame buffer index of pixel at given co-ordinates; (0, 0) is top left
(define (framebufindex x y)
  ; the OpenGL frame buffer origin is at botom left
  (* (+ (* WIDTH (- HEIGHT y 1)) x) 4))

; return a random number between 0 and 1
(define (frand)
  (random))

; set pixel at (x,y) in given gl-ubyte-vector 'buf' to given colour
(define (set-pixel-rgb buf x y r g b)
  (let
      ((index (framebufindex x y)))
    (gl-vector-set! buf index r)
    (gl-vector-set! buf (+ index 1) g)
    (gl-vector-set! buf (+ index 2) b)
    (gl-vector-set! buf (+ index 3) #xFF)))

(define (set-pixel-col buf x y col)
  (let
      ((index (framebufindex x y)))
    (gl-vector-set! buf index (arithmetic-shift col -16))
    (gl-vector-set! buf (+ index 1) (arithmetic-shift col -8))
    (gl-vector-set! buf (+ index 2) col)
    (gl-vector-set! buf (+ index 3) #xFF)))

; create the world map
(define (generate-map)
  (define blkmap (make-gl-uint-vector (* MAPDIM MAPDIM MAPDIM)))
  (for ((x MAPDIM))
    (for ((y MAPDIM))
      (for ((z MAPDIM))
        (let
            ((yd (* (- y 32.5) 0.4))
             (zd (* (- z 32.5) 0.4)))
          (if (or
               (> (frand) (- (sqrt (sqrt (+ (* yd yd) (* zd zd)))) 0.8))
               (< (frand) 0.6))
              (gl-vector-set! blkmap (mapindex x y z) 0) ; there won't be a block here
              (gl-vector-set! blkmap (mapindex x y z) (inexact->exact (floor (* (frand) #x00FFFFFF)))) ; block colour
          )
        )
      )
    )
  )
  blkmap)

(define cl 0.0) ; use instead of a clock for now

; render the next frame of the 'blkmap' world into the given 'frame-buf'
(define (render-blocks blkmap frame-buf)
  (define dx cl)
  (define ox (+ 32.5 (* dx MAPDIM)))
  (define oy 32.5)
  (define oz 32.5)
  (set! cl (+ cl 0.01))
  
  (for ((x WIDTH))
    (define rotzd (/ (- (exact->inexact x) (/ WIDTH 2)) HEIGHT))
    (for ((y HEIGHT))
      (define rotyd (/ (- (exact->inexact y) (/ HEIGHT 2)) HEIGHT))
      (define rotxd 1.0)
      (define col 0)
      (define br 255)
      (define ddist 0.0)
      (define closest 32.0)
      (for ((d 3))
        (define dimLength 0.0)

        (cond
          ((= d 0) (set! dimLength rotxd))
          ((= d 1) (set! dimLength rotyd))
          ((= d 2) (set! dimLength rotzd)))

        (define ll (/ 1.0 (abs dimLength)))
        (define xd (* rotxd ll))
        (define yd (* rotyd ll))
        (define zd (* rotzd ll))
        (define initial 0.0)

        (cond
          ((= d 0) (set! initial (- ox (floor ox))))
          ((= d 1) (set! initial (- oy (floor oy))))
          ((= d 2) (set! initial (- oz (floor oz)))))
        
        (when (> dimLength 0)
          (set! initial (- 1 initial)))
                  
        (define dist (* ll initial))
        (define xp (+ ox (* xd initial)))
        (define yp (+ oy (* yd initial)))
        (define zp (+ oz (* zd initial)))
                  
        (when (< dimLength 0)
          (cond
            ((= d 0) (set! xp (- xp 1)))
            ((= d 1) (set! yp (- yp 1)))
            ((= d 2) (set! zp (- zp 1)))))
        
        (let loop ()
          (when (< dist closest)
            (define tex (gl-vector-ref blkmap (mapindexf xp yp zp)))
            (when (> tex 0)
              (set! col tex)
              (set! ddist (- 255.0 (floor (* (/ dist 32.0) 255.0))))
              (set! br (/ (* 255 (- 255 (* 50 (modulo (+ d 2) 3)))) 255))
              (set! closest dist))
            (set! xp (+ xp xd))
            (set! yp (+ yp yd))
            (set! zp (+ zp zd))
            (set! dist (+ dist ll))
            (loop)))
        
        (define r (inexact->exact (floor (/ (* (bitwise-and (arithmetic-shift col -16) #xFF) br ddist) (* 255.0 255)))))
        (define g (inexact->exact (floor (/ (* (bitwise-and (arithmetic-shift col  -8) #xFF) br ddist) (* 255.0 255))))) 
        (define b (inexact->exact (floor (/ (* (bitwise-and col                        #xFF) br ddist) (* 255.0 255))))) 
        (set-pixel-rgb frame-buf x y r g b))))
)


(define (main)
  (let ((blkmap (generate-map))
        (graphics (new gem% (width WIDTH) (height HEIGHT) (scale SCALE) (title "mc4k - press q to exit"))))
    (send graphics run render-blocks blkmap)))

(main)

Note: not only is this my first OpenGL project this is also the biggest program I've ever written in a Lisp-family language, so it's almost certainly "wrong." However, it works on my DrRacket 5.2.1, producing the same moving tunnel of blocks as the C++ version, but not at the same frame-rate, as discussed below.


C++ vs. Lisp

“The code is nevertheless much more compact, because (no surprise) Racket is better than C++.”
- Matthew Flatt, currently associate professor of computer science at the University of Utah

I assume the people behind Racket have a deep understanding of computer programming languages. But can these things be so black and white?

For the case in hand, the C++ version displays 80 frames per second on my 2008 iMac, and the Racket version displays one frame per second on the same machine. Surprise?

Why is the Lisp version so much slower than the C++ version? I assume I've made some kind of dumb beginner's mistakes in the way I've written the code. (If you can see what they are, would you tell me?) I used Racket's Create Executable... command to create a compiled application; if I just hit the run button in the DrRacket IDE the code runs at a quarter the speed: I get one frame every 4 seconds.

Maybe I'm trying to write C++ in Racket - a classic beginners mistake? - but while writing the code one big C++ feature I missed was the deterministic destructor. I wanted to call glfwTerminate when my gem object went out of scope. Uh-oh! "How do you get anything done in Lisp? It doesn't even have destructors." I am not saying this. In fact I'm pretty sure that there is either already a mechanism that would automatically call a "destructor" method and I just couldn't find it, or there will be a way to build such a mechanism when I've learned a bit more. I know that the Racket with-output-to-file function automatically closes the file "whenever control escapes the dynamic extent" of the with-output-to-file call, which is the sort of thing I'm looking for, I think.

“By induction, the only programmers in a position to see all the differences in power between the various languages are those who understand the most powerful one. (This is probably what Eric Raymond meant about Lisp making you a better programmer.) You can't trust the opinions of the others, because of the Blub paradox: they're satisfied with whatever language they happen to use, because it dictates the way they think about programs.”
- Paul Graham

I understand what Paul is saying, but am I really too stupid to see further than my own nose? (Don't answer that!)

“The same is true of Byrne's account of how music has not "progressed" from a "primitive" state -- rather, it adapted itself to different technological realities. Big cathedrals demand music that accommodates a lot of reverb; village campfire music has completely different needs. Reading this, I was excited by the parallels to discussions of whether we live in an era of technological "progress" or merely technological "change" -- is there a pinnacle we're climbing, or simply a bunch of stuff followed by a bunch of other stuff? Our overwhelming narrative of progress feels like hubris to me, at least a lot of the time. Some things are "better" (more energy efficient, more space-efficient, faster, more effective), but there are plenty of things that are held up as "better" that, to me, are simply different. Often very good, but in no way a higher rung on some notional ladder toward perfection.”
- Cory Doctorow

This quote is from Cory Doctorow's review of a book about music by David Byrne. I have no idea where Doctorow stands with regard to discussions about C++ vs. Lisp. But what he says here resonates with my own views about these languages, which is that they are, like men and women, equal but different. It's obvious. I think people often look at a poorly written piece of code and blame the language it's written in. Clearly, some languages are more expressive or abstract than others. But there is more to it than that. As I've written before, I don't care how super-duper your language is, I bet I can write some pretty dumb, incorrect, slow, brittle, half-assed code in it. And conversely it isn't necessarily true that something written in a language lower down the abstraction scale couldn't be good, by any of the usual measures of good, principally by being useful and/or beautiful.

I value the diversity of programming languages. I'm dabbling in Lisp because it interests me. I plan to update this post in ten years' time, when I hope I'll be more of a Lisp programmer than I am now. Maybe my opinion on C++ vs. Lisp will have changed by then.

“Today I committed the first 5112 lines of D code to Facebook's repository. The project is in heavy daily use at Facebook. Compared to the original version (written in C++) we've measured massive wins in all of source code size, build speed, and running speed.”
- Andrei Alexandrescu

My contention is that someone of Alexandrescu's ability, coming to a piece of code with fresh eyes and a certain determination to prove a point, could rewrite the code in C++ and achieve similar "massive wins."

Human beings are so tribal. Don't you think? We seem to need to identify strongly with one group (for protection? from what?) and jeer at the other lot for being different.

A friend with a long-time interest in D has done a port of mc4ka/b. You can see it here. (Yes, but the question is what are we going to do?)


Appendix - Notes on compiling the code

Windows and OS X ship with OpenGL support, but you need something to create a window and handle keyboard input and so on. There are several libraries to choose from, such as SDL, GLUT and GLFW. I used GLFW because it seemed to be actively maintained. I really didn't know much about it, but it all worked out OK.

This article is more fun with programming languages than it is graphics programming tutorial. None of it should be taken as The Right Way to do it. These are notes I took about what I did to just get a bitmap out of a vector and onto the screen.

Building mc4ka.cpp and mc4kb.cpp under Windows

The current GLFW release is 3.0.3:

- download the source archive (glfw-3.0.3.zip) from http://www.glfw.org/download.html and unzip it
- build GLFW as described in README.md
  - download cmake installer from http://www.cmake.org/cmake/resources/software.html and install it
    (I used the Windows (Win32 Installer) version 2.8.11.2)
  - I used the cmake GUI to build the GLFW.sln file to build the GLFW static library
  - then open the GLFW.sln in Visual Studio 10 and build the whole GLFW solution in both Release and Debug
- build and link mc4ka: I borrowed one of the GLFW example solutions, but then I made a batch file:

mkawin.bat:
cl /nologo /MD /EHs /O2 /W4 /I C:\Projects\glfw-3.0.3\include mc4ka.cpp ^
   /Fmc4ka /link C:\Projects\glfw-3.0.3\src\Release\glfw3.lib ^
   user32.lib gdi32.lib glu32.lib opengl32.lib 

- ditto for mc4kb


Building mc4ka.cpp and mc4kb.cpp under OS X

- download the source archive (glfw-3.0.3.zip) from http://www.glfw.org/download.html and unzip it
- build GLFW as described in README.md
  - download cmake installer from http://www.cmake.org/cmake/resources/software.html and install it
  - I used the cmake GUI to build the makefiles to build the GLFW static library
  - then run make in the build directory to build GLFW
  - then sudo make install
- to compile and link mc4ka.cpp I used this Shell script:

mkaosx:
#!/bin/bash 
# build mc4ka.cpp with i686-apple-darwin11-llvm-g++-4.2 under OS X
g++ -O3 -ffast-math -g -o mc4ka mc4ka.cpp -lglfw3 -framework Cocoa -framework OpenGL -framework IOKit

- ditto for mc4kb


Building mc4ka.scm with Racket under Windows and OS X

Racket comes with OpenGL support, so once you've installed Racket you're ready to go.

To install Racket you do pretty much the same thing under both Windows and OS X:

- download Racket from http://racket-lang.org/download/
- I installed Racket v5.3.6 (x86_64) on my Windows 7 box and Mac. I also ran the code under DrRacket v5.2.1 on the Mac.
  (They have binaries for 32- and 64-bit Windows, OS X and Linux. Or download the source and build it yourself.)
- start DrRacket and File|Open... mc4ka.scm
- to run it click the green Run button
- to compile it goto Racket|Create Executable... and choose Type: Stand-alone, Base: GRacket


Appendix - Notch's original code

Notch's original Mincraft4k is here. It's in Java and is even more awesome than the first version I saw, which is the one I based the above code on. That version is here and is reproduced below.

“A quick port of Minecraft4k to test what's possible in JS and HTML5.

Because of the nature of this project (it was originally meant as an entry for the Java4k competition, which focuses on executable size), the code is HORRIBLE, but fairly small.

You may use the code in here for any purpose in any way you want, at your own risk.”

- Marcus Persson

var ctx;
var pixels;

var w = 212 * 2;
var h = 120 * 2;

var map = new Array(64 * 64 * 64);
var texmap = new Array(16 * 16 * 3 * 16);

function init() {
    for ( var i = 1; i < 16; i++) {
        var br = 255 - ((Math.random() * 96) | 0);
        for ( var y = 0; y < 16 * 3; y++) {
            for ( var x = 0; x < 16; x++) {
                var color = 0x966C4A;
                if (i == 4)
                    color = 0x7F7F7F;
                if (i != 4 || ((Math.random() * 3) | 0) == 0) {
                    br = 255 - ((Math.random() * 96) | 0);
                }
                if ((i == 1 && y < (((x * x * 3 + x * 81) >> 2) & 3) + 18)) {
                    color = 0x6AAA40;
                } else if ((i == 1 && y < (((x * x * 3 + x * 81) >> 2) & 3) + 19)) {
                    br = br * 2 / 3;
                }
                if (i == 7) {
                    color = 0x675231;
                    if (x > 0 && x < 15
                            && ((y > 0 && y < 15) || (y > 32 && y < 47))) {
                        color = 0xBC9862;
                        var xd = (x - 7);
                        var yd = ((y & 15) - 7);
                        if (xd < 0)
                            xd = 1 - xd;
                        if (yd < 0)
                            yd = 1 - yd;
                        if (yd > xd)
                            xd = yd;

                        br = 196 - ((Math.random() * 32) | 0) + xd % 3 * 32;
                    } else if (((Math.random() * 2) | 0) == 0) {
                        br = br * (150 - (x & 1) * 100) / 100;
                    }
                }

                if (i == 5) {
                    color = 0xB53A15;
                    if ((x + (y >> 2) * 4) % 8 == 0 || y % 4 == 0) {
                        color = 0xBCAFA5;
                    }
                }
                if (i == 9) {
                    color = 0x4040ff;
                }
                var brr = br;
                if (y >= 32)
                    brr /= 2;

                if (i == 8) {
                    color = 0x50D937;
                    if (((Math.random() * 2) | 0) == 0) {
                        color = 0;
                        brr = 255;
                    }
                }

                var col = (((color >> 16) & 0xff) * brr / 255) << 16
                        | (((color >> 8) & 0xff) * brr / 255) << 8
                        | (((color) & 0xff) * brr / 255);
                texmap[x + y * 16 + i * 256 * 3] = col;
            }
        }
    }

    ctx = document.getElementById('game').getContext('2d');

    for ( var x = 0; x < 64; x++) {
        for ( var y = 0; y < 64; y++) {
            for ( var z = 0; z < 64; z++) {
                var i = z << 12 | y << 6 | x;
                var yd = (y - 32.5) * 0.4;
                var zd = (z - 32.5) * 0.4;
                map[i] = (Math.random() * 16) | 0;
                if (Math.random() > Math.sqrt(Math.sqrt(yd * yd + zd * zd)) - 0.8)
                    map[i] = 0;
            }
        }
    }

    pixels = ctx.createImageData(w, h);

    for ( var i = 0; i < w * h; i++) {
        pixels.data[i * 4 + 3] = 255;
    }

    setInterval(clock, 1000 / 100);
};

function clock() {
    renderMinecraft();
    ctx.putImageData(pixels, 0, 0);
};

var f = 0;
function renderMinecraft() {
    var xRot = Math.sin(Date.now() % 10000 / 10000 * Math.PI * 2) * 0.4
            + Math.PI / 2;
    var yRot = Math.cos(Date.now() % 10000 / 10000 * Math.PI * 2) * 0.4;
    var yCos = Math.cos(yRot);
    var ySin = Math.sin(yRot);
    var xCos = Math.cos(xRot);
    var xSin = Math.sin(xRot);

    var ox = 32.5 + Date.now() % 10000 / 10000 * 64;
    var oy = 32.5;
    var oz = 32.5;

    f++;
    for ( var x = 0; x < w; x++) {
        var ___xd = (x - w / 2) / h;
        for ( var y = 0; y < h; y++) {
            var __yd = (y - h / 2) / h;
            var __zd = 1;

            var ___zd = __zd * yCos + __yd * ySin;
            var _yd = __yd * yCos - __zd * ySin;

            var _xd = ___xd * xCos + ___zd * xSin;
            var _zd = ___zd * xCos - ___xd * xSin;

            var col = 0;
            var br = 255;
            var ddist = 0;

            var closest = 32;
            for ( var d = 0; d < 3; d++) {
                var dimLength = _xd;
                if (d == 1)
                    dimLength = _yd;
                if (d == 2)
                    dimLength = _zd;

                var ll = 1 / (dimLength < 0 ? -dimLength : dimLength);
                var xd = (_xd) * ll;
                var yd = (_yd) * ll;
                var zd = (_zd) * ll;

                var initial = ox - (ox | 0);
                if (d == 1)
                    initial = oy - (oy | 0);
                if (d == 2)
                    initial = oz - (oz | 0);
                if (dimLength > 0)
                    initial = 1 - initial;

                var dist = ll * initial;

                var xp = ox + xd * initial;
                var yp = oy + yd * initial;
                var zp = oz + zd * initial;

                if (dimLength < 0) {
                    if (d == 0)
                        xp--;
                    if (d == 1)
                        yp--;
                    if (d == 2)
                        zp--;
                }

                while (dist < closest) {
                    var tex = map[(zp & 63) << 12 | (yp & 63) << 6 | (xp & 63)];

                    if (tex > 0) {
                        var u = ((xp + zp) * 16) & 15;
                        var v = ((yp * 16) & 15) + 16;
                        if (d == 1) {
                            u = (xp * 16) & 15;
                            v = ((zp * 16) & 15);
                            if (yd < 0)
                                v += 32;
                        }

                        var cc = texmap[u + v * 16 + tex * 256 * 3];
                        if (cc > 0) {
                            col = cc;
                            ddist = 255 - ((dist / 32 * 255) | 0);
                            br = 255 * (255 - ((d + 2) % 3) * 50) / 255;
                            closest = dist;
                        }
                    }
                    xp += xd;
                    yp += yd;
                    zp += zd;
                    dist += ll;
                }
            }

            var r = ((col >> 16) & 0xff) * br * ddist / (255 * 255);
            var g = ((col >> 8) & 0xff) * br * ddist / (255 * 255);
            var b = ((col) & 0xff) * br * ddist / (255 * 255);// + (255 -

            pixels.data[(x + y * w) * 4 + 0] = r;
            pixels.data[(x + y * w) * 4 + 1] = g;
            pixels.data[(x + y * w) * 4 + 2] = b;
        }
    }
}

init();

index of blog posts

No comments:

Post a Comment