3DMaze


上下左右キーで移動します。スペースキーを押下するとジャンプして俯瞰することもできます。三角関数・ベクトル・行列を使って座標計算を行い、Canvas上に描画しています。Advanced(上級)クラスでこれらの内容をカバーする予定です。以下の書籍で実装の詳細について解説しています。
ジャンプしてみると3Dのプログラムということが実感できると思います。

ソースコード


<!DOCTYPE html>
<html>
<!-- Copyright 2016 Kenichiro Tanaka -->
<head>
    <meta charset="utf-8" />
    <title>3D MAZE</title>
    <style>
        #field {touch-action:none;}
    </style>
    <script>
        "use strict";
        var ctx, maze = [], cubes = [], W = 17, H = 17;
        var xpos = 1, zpos = 1, dir = 1;
        var xposNext = 1, zposNext = 1, dirNext = 1;
        var cameraY = 50, cameraRotY = 0,
            jumpVelocity = 0, counter = 0;
        var light = new Vec3(0.5, -0.8, -0.2).normalize();

        function random(val) { return Math.floor(Math.random() * val); }

        function Vec3(x, y, z) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.normalize = function () {
                var x = this.x, y = this.y, z = this.z;
                var scale = 1 / Math.sqrt(x * x + y * y + z * z);
                this.x *= scale;
                this.y *= scale;
                this.z *= scale;
                return this;
            }
        }

        function Surface(vertices, i, type) {
            this.pos = vertices;
            this.type = type;
            var p1 = vertices[0];
            var p2 = vertices[1];
            var p3 = vertices[2];
            var p4 = vertices[3];
            var p = new Vec3(p1.x-p2.x, p1.y-p2.y, p1.z-p2.z);
            var q = new Vec3(p1.x-p3.x, p1.y-p3.y, p1.z-p3.z);
            var n = new Vec3(   // normal vector
                p.y * q.z - p.z * q.y,
                p.z * q.x - p.x * q.z,
                p.x * q.y - p.y * q.x);
            this.norm = n.normalize();  // unit normal vector
            this.cZ = (p1.z + p2.z + p3.z + p4.z) / 4;
            if (i == 0) {   // pull top surfaces a bit
                this.cZ -= 1
            }
        }

        function Cube(x, y, z, w, h, d, type) {
            this.x = x;
            this.z = z;
            this.pos = [];
            this.type = type;
            this.vertices = [
                { x: x - w, y: y - h, z: z + d },
                { x: x - w, y: y + h, z: z + d },
                { x: x + w, y: y + h, z: z + d },
                { x: x + w, y: y - h, z: z + d },
                { x: x - w, y: y - h, z: z - d },
                { x: x - w, y: y + h, z: z - d },
                { x: x + w, y: y + h, z: z - d },
                { x: x + w, y: y - h, z: z - d },
            ];

            this.polygons = [
                [2, 1, 5, 6],
                [0, 1, 2, 3],
                [4, 5, 1, 0],
                [2, 6, 7, 3],
                [7, 6, 5, 4],
                [0, 3, 7, 4]
            ];

            this.getSurfaces = function () {
                var r = []; // NOTE: floor surface is not returned
                for (var i = 0 ; i < this.polygons.length - 1 ; i++) {
                    var indices = this.polygons[i];
                    var p = [];
                    for (var j = 0 ; j < indices.length ; j++) {
                        p.push(this.pos[indices[j]]);
                    }

                    r.push(new Surface(p, i, this.type));
                }
                return r;
            };

            this.setCamera = function (cameraX, cameraZ, cameraY,
                                        mRotX, mRotY) {
                for (var i = 0 ; i < this.vertices.length ; i++) {
                    var c = this.vertices[i];
                    // move the camera
                    var x = c.x - cameraX;
                    var y = c.y - cameraY;
                    var z = c.z - cameraZ;

                    // rotate around Y axis
                    var p = mRotY[0] * x + mRotY[1] * y
                        + mRotY[2] * z;
                    var q = mRotY[3] * x + mRotY[4] * y
                        + mRotY[5] * z;
                    var r = mRotY[6] * x + mRotY[7] * y
                        + mRotY[8] * z;

                    // rotate around X axis
                    x = mRotX[0] * p + mRotX[1] * q + mRotX[2] * r;
                    y = mRotX[3] * p + mRotX[4] * q + mRotX[5] * r;
                    z = mRotX[6] * p + mRotX[7] * q + mRotX[8] * r;
                    this.pos[i] = { x: x, y: y, z: z };
                }
            }
        }

        function createMaze(w, h) {
            for (var z = 0 ; z < h ; z++) {
                maze[z] = [];
                for (var x = 0 ; x < w ; x++) {
                    maze[z][x] = (x == 0 || x == w - 1 || 
                                  z == 0 || z == h - 1)? 1 : 0;
                }
            }

            for (var z = 2 ; z < h - 2 ; z += 2) {
                for (var x = 2 ; x < w - 2 ; x += 2) {
                    maze[z][x] = 1;

                    // top row - Up,Down,Left,Right
                    // others - Down,Left,Right
                    var dir = random((z == 2) ? 4 : 3);
                    var px = x, pz = z;
                    switch (dir) {
                        case 0: pz++; break;
                        case 1: px--; break;
                        case 2: px++; break;
                        case 3: pz--; break;
                    }
                    maze[pz][px] = 1;
                }
            }
        }

        function init() {
            ctx = document.getElementById("field").getContext("2d");

            createMaze(W, H);
            
            for (var z = 0 ; z < H; z++) {
                for (var x = 0 ; x < W ; x++) {
                    if (maze[z][x]) {
                        cubes.push(new Cube(x*100-25, 0,
                            z*100-25, 25,25,25, "wall"));
                        cubes.push(new Cube(x*100+25, 0,
                            z*100-25, 25,25,25, "wall"));
                        cubes.push(new Cube(x*100-25, 0,
                            z*100+25, 25,25,25, "wall"));
                        cubes.push(new Cube(x*100+25, 0,
                            z*100+25, 25,25,25, "wall"));
                    }
                    else {
                        cubes.push(new Cube(x * 100, 0,
                            z * 100, 10, 10, 10, "dot"));
                    }
                }
            }            
          
            onkeydown = mykeydown;
            setInterval(tick, 20)
        }

        function mykeydown(e) {
            if (counter) { return; }  // do nothing while moving

            var dx = 0, dz = 0;
            switch (e.keyCode) {
                case 37:    // left
                    dirNext = dir + 1;
                    break;
                case 39:    // right
                    dirNext = dir - 1;
                    break;
                case 38:    // up -> forward
                    dx = Math.round(Math.cos(dir * Math.PI / 2));
                    dz = Math.round(Math.sin(dir * Math.PI / 2));
                    break;
                case 40:    // down -> backward
                    dx = -Math.round(Math.cos(dir * Math.PI / 2));
                    dz = -Math.round(Math.sin(dir * Math.PI / 2));
                    break;
                case 32:    // space -> jump
                    if (jumpVelocity == 0) { jumpVelocity = 150; }
                    break;
            }

            if (maze[zpos + dz][xpos + dx] == 0) {
                // remove "dot" cubes
                cubes = cubes.filter(function (d) {
                    return !(d.x / 100 == xpos + dx && 
                             d.z / 100 == zpos + dz);
                })
                cubes = cubes.filter(function (d) {
                    return !(d.x / 100 == xpos + dx * 2 &&
                             d.z / 100 == zpos + dz * 2);
                })
                xposNext = xpos + dx * 2;
                zposNext = zpos + dz * 2;
            }

            if (dirNext != dir || 
                xposNext != xpos || zposNext != zpos) {
                counter = 1;  // start moving
            }
        }

        function tick() {
            // set camera position and direction
            cameraRotY = dir * Math.PI / 2 - Math.PI / 2;
            var cameraX = xpos * 100, cameraZ = zpos * 100;

            if (counter) { // while moving or rotating
                cameraRotY += ((dirNext - dir) * counter / 10) 
                    * (Math.PI / 2);
                cameraX += ((xposNext-xpos) * counter/10) * 100;
                cameraZ += ((zposNext-zpos) * counter/10) * 100;
                if (counter++ >= 10) {
                    dir = dirNext = (dirNext + 4) % 4;
                    xpos = xposNext;
                    zpos = zposNext;
                    counter = 0;
                }
            }

            jumpVelocity -= 4;
            cameraY += jumpVelocity;
            if (cameraY < 50) {
                jumpVelocity = 0;
                cameraY = 50;
            }

            // rotate Y & X
            var c = Math.cos(cameraRotY);
            var s = Math.sin(cameraRotY);
            var MatrixRotY = [c, 0, s, 0, 1, 0, -s, 0, c];
            var MatrixRotX = [1, 0, 0, 0, 1, 0, 0, 0, 1]; 
            if (cameraY != 50) {
                var cameraRotX = Math.min(90, 
                    (cameraY - 50) / 20) * Math.PI / 180;
                var c = Math.cos(-cameraRotX);
                var s = Math.sin(-cameraRotX);
                MatrixRotX = [1, 0, 0, 0, c, -s, 0, s, c];
            }
            cubes.forEach(function (b) {
                b.setCamera(cameraX, cameraZ, cameraY,
                    MatrixRotX, MatrixRotY);
            });

            paint();
        }

        function paint() {
            // clear background
            ctx.fillStyle = "black";
            ctx.fillRect(0, 0, 600, 600);

            // get all surfaces and sort them
            var surfaces = []
            cubes.forEach(function (b) {
                surfaces = surfaces.concat(b.getSurfaces())
            });
            surfaces.sort(function (a, b) {
                return b.cZ - a.cZ;
            });

            // draw all surfaces
            surfaces.forEach(function (s) {
                var p = (s.norm.x * light.x + s.norm.y * light.y
                        + s.norm.z * light.z);
                var ratio = (p + 1) / 2; // p: -1 to 1, ratio: 0 to 1
                var R = 255, G = 255, B = 255;
                if (s.type == "dot") {
                    R = 0, G = 255, B = 128;
                }
                ctx.fillStyle = "rgba(" 
                    + Math.floor(R * ratio) + ","
                    + Math.floor(G * ratio) + ","
                    + Math.floor(B * ratio) + ",255)";

                ctx.beginPath();
                for (var i = 0 ; i < 4 ; i++) {
                    var v = s.pos[i];
                    if (v.z <= 0) continue;
                    var x = v.x / v.z * 1000 + 300;
                    var y = -v.y / v.z * 1000 + 300;
                    if (i == 0) {
                        ctx.moveTo(x, y);
                    } else {
                        ctx.lineTo(x, y);
                    }
                }
                ctx.closePath();
                ctx.fill();
            })

            // draw azimuth compass
            ctx.save();
            ctx.strokeStyle = "white";
            ctx.translate(550, 50);
            ctx.rotate(cameraRotY)
            ctx.beginPath();
            ctx.moveTo(0, 20);
            ctx.lineTo(0, -20);
            ctx.lineTo(-5, -10);
            ctx.lineTo(5, -10);
            ctx.stroke();            
            ctx.restore();
        }

        addEventListener("touchstart", mymousedown);
        addEventListener("mousedown", mymousedown);
        oncontextmenu = function(e) {e.preventDefault(); }
        function mymousedown(e){
            var mouseX = !isNaN(e.offsetX) ? e.offsetX : e.touches[0].clientX;
            var mouseY = !isNaN(e.offsetY) ? e.offsetY : e.touches[0].clientY;
            mouseX -= ctx.canvas.width / 2;
            mouseY -= ctx.canvas.height / 2;
            if (Math.abs(mouseX) > Math.abs(mouseY)){
                mykeydown({keyCode: mouseX < 0 ? 37 : 39});
            }else{
                mykeydown({keyCode: mouseY < 0 ? 38 : 40});
            }
        }
    </script>
</head>
<body onload="init()">
    <canvas id="field" width="600" height="600" 
            style="width:600px; height:600px"></canvas>
</body>
</html>

""" 3D MAZE - Copyright 2016 Kenichiro Tanaka """
import sys
import random
from math import sin, cos, pi, sqrt, floor
import pygame
from pygame.locals import QUIT, KEYDOWN, \
    K_LEFT, K_RIGHT, K_UP, K_DOWN, K_SPACE

def normalize(vec):
    """ normalize the vector (make the length 1) """
    scale = 1 / sqrt(vec[0]**2 + vec[1]**2 + vec[2]**2)
    return (vec[0]*scale, vec[1]*scale, vec[2]*scale)

def get_norm_vec(pos1, pos2, pos3):
    """ get the normal vector from 3 vertices """
    pvec = (pos1[0] - pos2[0], pos1[1] - pos2[1], pos1[2] - pos2[2])
    qvec = (pos1[0] - pos3[0], pos1[1] - pos3[1], pos1[2] - pos3[2])
    norm = (pvec[1]*qvec[2] - pvec[2]*qvec[1],
            pvec[2]*qvec[0] - pvec[0]*qvec[2],
            pvec[0]*qvec[1] - pvec[1]*qvec[0])
    return normalize(norm)

def create_maze(width, height):
    """ create maze data (0:empty 1:wall) """
    maze = [[0 for i in range(width)] for j in range(height)]
    for zpos in range(0, height):
        for xpos in range(0, width):
            if xpos in (0, width-1) or zpos in (0, height-1):
                maze[zpos][xpos] = 1
            if zpos%2 == 1 or xpos%2 == 1:
                continue
            if zpos > 1 and xpos > 1 and zpos < height-1 and \
               xpos < width-1:
                maze[zpos][xpos] = 1
                direction = random.randint(0, 3 if zpos == 2 else 2)
                (nextx, nextz) = (xpos, zpos)
                if direction == 0:
                    nextz += 1
                elif direction == 1:
                    nextx -= 1
                elif direction == 2:
                    nextx += 1
                elif direction == 3:
                    nextz -= 1
                maze[nextz][nextx] = 1
    return maze

class Surface():
    """ object for each surface """
    def __init__(self, v0, v1, v2, v3, tag, index):
        self.vert = (v0, v1, v2, v3)
        self.tag = tag
        self.index = index
        self.norm = (0, 0, 0)
        self.zpos = 0

    def update(self):
        """ update the normal vector of the surface """
        self.norm = get_norm_vec(self.vert[0],
                                 self.vert[1],
                                 self.vert[2])
        self.zpos = (self.vert[0][2] + self.vert[1][2] + \
                     self.vert[2][2] + self.vert[3][2]) / 4
        if self.index == 0:
            self.zpos -= 1

class Cube():
    """ 3D Cube model """
    polygons = (
        (2, 1, 5, 6), (0, 1, 2, 3), (4, 5, 1, 0),
        (2, 6, 7, 3), (7, 6, 5, 4), (0, 3, 7, 4)
    )

    def __init__(self, x, y, z, w, h, d, tag):
        self.xpos = x
        self.zpos = z
        self.pos = []
        self.surfaces = []
        self.vertices = (
            (x - w, y - h, z + d),
            (x - w, y + h, z + d),
            (x + w, y + h, z + d),
            (x + w, y - h, z + d),
            (x - w, y - h, z - d),
            (x - w, y + h, z - d),
            (x + w, y + h, z - d),
            (x + w, y - h, z - d),
        )

        for vert in self.vertices:
            self.pos.append([vert[0], vert[1], vert[2]])

        for i in range(5):
            indices = self.polygons[i]
            pos0 = self.pos[indices[0]]
            pos1 = self.pos[indices[1]]
            pos2 = self.pos[indices[2]]
            pos3 = self.pos[indices[3]]
            self.surfaces.append(
                Surface(pos0, pos1, pos2, pos3, tag, i))

    def set_camera(self, camera_x, camera_y, camera_z,
                   mrot_x, mrot_y):
        """ set camera location and update vertices positions """
        for i in range(len(self.vertices)):
            vert = self.vertices[i]
            xpos = vert[0] - camera_x
            ypos = vert[1] - camera_y
            zpos = vert[2] - camera_z

            # rotate around Y axis
            ppos = mrot_y[0] * xpos + mrot_y[1] * ypos \
                + mrot_y[2] * zpos
            qpos = mrot_y[3] * xpos + mrot_y[4] * ypos \
                + mrot_y[5] * zpos
            rpos = mrot_y[6] * xpos + mrot_y[7] * ypos \
                + mrot_y[8] * zpos

            # rotate around X axis
            self.pos[i][0] = mrot_x[0] * ppos \
                + mrot_x[1] * qpos + mrot_x[2] * rpos
            self.pos[i][1] = mrot_x[3] * ppos \
                + mrot_x[4] * qpos + mrot_x[5] * rpos
            self.pos[i][2] = mrot_x[6] * ppos \
                + mrot_x[7] * qpos + mrot_x[8] * rpos

        for surface in self.surfaces:
            surface.update()

def eventloop():
    """ handle events in eventloop """
    global COUNTER, JUMPSPEED, CUBES
    (diffx, diffz) = (0, 0)
    for event in pygame.event.get():
        if event.type == QUIT:
            pygame.quit()
            sys.exit()
        elif event.type == KEYDOWN:
            if event.key == K_LEFT:
                TURN[1] = TURN[0] + 1
            elif event.key == K_RIGHT:
                TURN[1] = TURN[0] - 1
            elif event.key == K_UP:
                diffx = round(cos(TURN[0]*pi/2))
                diffz = round(sin(TURN[0]*pi/2))
            elif event.key == K_DOWN:
                diffx = -round(cos(TURN[0]*pi/2))
                diffz = -round(sin(TURN[0]*pi/2))
            elif event.key == K_SPACE and JUMPSPEED == 0:
                JUMPSPEED = 150

        if COUNTER != 0:
            continue

        if not (diffx == 0 and diffz == 0) and \
           (MAZE[ZPOS[0] + diffz][XPOS[0] + diffx] == 0):
            CUBES = [c for c in CUBES if not \
                (c.xpos/100 == XPOS[0]+diffx and \
                 c.zpos/100 == ZPOS[0]+diffz)]
            CUBES = [c for c in CUBES if not \
                (c.xpos/100 == XPOS[0]+diffx*2 and \
                 c.zpos/100 == ZPOS[0]+diffz*2)]
            (XPOS[1], ZPOS[1]) = (XPOS[0] + diffx*2,
                                  ZPOS[0] + diffz*2)

        if TURN[1] != TURN[0] or XPOS[1] != XPOS[0] or \
           ZPOS[1] != ZPOS[0]:
            COUNTER = 1

def tick():
    """ called periodically from the main loop """
    global COUNTER, CAMERAY, JUMPSPEED
    eventloop()

    camera_rot_y = TURN[0] * pi / 2 - pi / 2
    (camera_x, camera_z) = (XPOS[0] * 100, ZPOS[0] * 100)
    if COUNTER > 0:
        camera_rot_y += ((TURN[1] - TURN[0]) * COUNTER / 10) \
            * (pi / 2)
        camera_x += ((XPOS[1] - XPOS[0]) * COUNTER / 10) * 100
        camera_z += ((ZPOS[1] - ZPOS[0]) * COUNTER / 10) * 100
        COUNTER += 1
        if COUNTER >= 10:
            TURN[0] = TURN[1] = (TURN[1] + 4) % 4
            (XPOS[0], ZPOS[0]) = (XPOS[1], ZPOS[1])
            COUNTER = 0

    JUMPSPEED -= 4
    CAMERAY += JUMPSPEED
    if CAMERAY < 50:
        JUMPSPEED = 0
        CAMERAY = 50

    (cval, sval) = (cos(camera_rot_y), sin(camera_rot_y))
    mrot_y = [cval, 0, sval, 0, 1, 0, -sval, 0, cval]
    mrot_x = [1, 0, 0, 0, 1, 0, 0, 0, 1]
    if CAMERAY != 50:
        camera_rot_x = min(90, (CAMERAY - 50) / 20) * pi / 180
        (cval, sval) = (cos(-camera_rot_x), sin(-camera_rot_x))
        mrot_x = [1, 0, 0, 0, cval, -sval, 0, sval, cval]
    for cube in CUBES:
        cube.set_camera(camera_x, CAMERAY, camera_z,
                        mrot_x, mrot_y)

def paint():
    """ update the surface """
    # Paint polygons
    SURFACE.fill((0, 0, 0))
    surfaces = []
    for cube in CUBES:
        surfaces.extend(cube.surfaces)
    surfaces = sorted(surfaces, key=lambda x: x.zpos, reverse=True)

    for surf in surfaces:
        dot = surf.norm[0]*LIGHT[0] + surf.norm[1]*LIGHT[1] \
            + surf.norm[2]*LIGHT[2]
        ratio = (dot + 1) / 2
        (rval, gval, bval) = (0, 255, 128) \
            if surf.tag == "dot" else (255, 255, 255)
        (rval, gval, bval) = (floor(rval*ratio),
                              floor(gval*ratio), floor(bval*ratio))

        pts = []
        for i in range(4):
            (xpos, ypos, zpos) = (surf.vert[i][0],
                                  surf.vert[i][1], surf.vert[i][2])
            if zpos <= 10:
                continue
            xpos = int(xpos * 1000 / zpos + 300)
            ypos = int(-ypos * 1000 / zpos + 300)
            pts.append((xpos, ypos))

        if len(pts) > 3:
            pygame.draw.polygon(SURFACE, (rval, gval, bval), pts)

    pygame.display.update()

def main():
    """ main routine """
    for zpos in range(0, H):
        for xpos in range(0, W):
            if MAZE[zpos][xpos] == 1:
                CUBES.append(Cube(xpos*100-25, 0, zpos*100-25,
                                  25, 25, 25, "wall"))
                CUBES.append(Cube(xpos*100+25, 0, zpos*100-25,
                                  25, 25, 25, "wall"))
                CUBES.append(Cube(xpos*100-25, 0, zpos*100+25,
                                  25, 25, 25, "wall"))
                CUBES.append(Cube(xpos*100+25, 0, zpos*100+25,
                                  25, 25, 25, "wall"))
            else:
                CUBES.append(Cube(xpos*100, 0, zpos*100,
                                  10, 10, 10, "dot"))

    while True:
        tick()
        paint()
        FPSCLOCK.tick(FPS)

pygame.init()
SURFACE = pygame.display.set_mode([600, 600])
SURFACE.convert()
FPSCLOCK = pygame.time.Clock()
(W, H) = (13, 13)
XPOS = [1, 1]
ZPOS = [1, 1]
TURN = [1, 1]
COUNTER = 0
CAMERAY = 50
JUMPSPEED = 0
LIGHT = normalize([0.5, -0.8, -0.2])
FPS = 30
CUBES = []
MAZE = create_maze(W, H)

if __name__ == '__main__':
    main()