3D Maze in Python

brick.jpg

maze.py

from OpenGL.GLUT import *
from OpenGL.GLU import *
from OpenGL.error import *
from OpenGL.GL import *
from PIL import Image
from operator import add, mul, div
from copy import deepcopy
from maze_gen import NORTH, WEST, SOUTH, EAST, N, towards, isCoordinateInRange

import ctypes
import sys
import math
import time
import traceback

name = 'maze'

win_width, win_height = 800, 600

heading = [0, 0, 0]
loc = [0.0, 0.0, 0.0]
map_scale = 30.

keybuffer = {}
maze = []
visited = []

shader = 0
tex_wall = 0
tex_sand = 0

timer = 0
alert = 0
done = False
fps = 0

SKYBOX_TOP      = 1
SKYBOX_BOTTOM   = 2
SKYBOX_LEFT     = 3
SKYBOX_RIGHT    = 4
SKYBOX_FRONT    = 5
SKYBOX_BACK     = 6

SKYBOX_SIZE     = 32

tex_skybox = {}
vert_skybox = {}
texc_skybox = {}

RotatingSpeed = 0.1
MovingSpeed  = 0.1

DEBUG_COLLISON = False
DEBUG_FUNCTRACE = False
DEBUG_DRAW = False
DEBUG_AUTOPILOT = False

HUD_ALWAYS_ON = True
ENABLE_AUTOPILOT = True

def main():
    global heading, loc, keybuffer, timer, alert

    glutInit(sys.argv)
    glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB | GLUT_DEPTH)
    glutInitWindowSize(1280,720)
    glutCreateWindow(name)
    glutDisplayFunc(display)
    glutReshapeFunc(resize)
    glutKeyboardFunc(keyPressed)
    glutKeyboardUpFunc(keyReleased)
    glutIdleFunc(idleFunc)

    loadShaders()
    loadTextures()
    loadSkybox()
    loadMaze()
    setupLights()
    if ENABLE_AUTOPILOT:
        autoPilotInit()

    glClearColor(0.,0.,0.,1.)
    glShadeModel(GL_SMOOTH)
    glEnable(GL_DEPTH_TEST)
    glEnable(GL_TEXTURE_CUBE_MAP)
    glDisable(GL_CULL_FACE)

    heading = [0, 0, -1]
    loc = [0.5, 0.5, -0.5]
    for i in range(256):
        keybuffer[i] = False

    timer = time.time()
    print 'timer has started.'
    glutMainLoop()
    return

def idleFunc():
    glutPostRedisplay()

def translate_maze(i):
    r = ''
    if i & NORTH:
        r += 'N'
    if i & SOUTH:
        r += 'S'
    if i & WEST:
        r += 'W'
    if i & EAST:
        r += 'E'
    return r

def loadMaze():
    global maze
    with open('maze_gen.out', 'r') as f:
        for row in f:
            maze.append(map(int, row.split(' ')))
    for i in range(N):
        visited.append([False] * N)
    for i in range(N):
        visited.append([False] * N)
    print 'first row:', map(translate_maze, maze[0])

PILOT_WALKING               = 1
PILOT_TURNLEFT              = 2
PILOT_TURNRIGHT             = 3
PILOT_REVERSE               = 4
PILOT_BACKTRACK_WALKING     = 5
PILOT_BACKTRACK_TURNLEFT    = 6
PILOT_BACKTRACK_TURNRIGHT   = 7
PILOT_COMPLETE              = 10

PILOT_ACTION_FORWARD        = 1
PILOT_ACTION_LEFT           = 2
PILOT_ACTION_RIGHT          = 4

Left = {NORTH: WEST, WEST: SOUTH, SOUTH: EAST, EAST: NORTH}
Right = {NORTH: EAST, EAST: SOUTH, SOUTH: WEST, WEST: NORTH}

pilot_heading = NORTH
pilot_status = PILOT_WALKING
pilot_walked = 0.
pilot_rotated = 0.
pilot_stack = []
pilot_hint = []
pilot_stepped = 0

def translate_status(s):
    return {
        PILOT_WALKING: 'PILOT_WALKING',
        PILOT_WALKING: 'PILOT_WALKING',
        PILOT_TURNLEFT: 'PILOT_TURNLEFT',
        PILOT_TURNRIGHT: 'PILOT_TURNRIGHT',
        PILOT_REVERSE: 'PILOT_REVERSE',
        PILOT_BACKTRACK_WALKING: 'PILOT_BACKTRACK_WALKING',
        PILOT_BACKTRACK_TURNLEFT: 'PILOT_BACKTRACK_TURNLEFT',
        PILOT_BACKTRACK_TURNRIGHT: 'PILOT_BACKTRACK_TURNRIGHT',
        PILOT_COMPLETE: 'PILOT_COMPLETE'
    }[s]

def translate_action(act):
    ret = ''
    if act & PILOT_ACTION_FORWARD:
        ret += 'FORWARD '
    if act & PILOT_ACTION_LEFT:
        ret += 'LEFT '
    if act & PILOT_ACTION_RIGHT:
        ret += 'RIGHT '
    return ret

def autoPilotInit():
    global pilot_walked, pilot_heading, pilot_status, pilot_rotated, pilot_stack, pilot_hint
    for i in range(N):
        pilot_hint.append([-1] * N)
    pilot_walked = 1.0

def heading_vector(d):
    return {
        NORTH: [0, 0, -1],
        SOUTH: [0, 0, 1],
        WEST: [-1, 0, 0],
        EAST: [1, 0, 0]
    }[d]

def autoPilotWalking():
    global pilot_walked, pilot_heading, pilot_status, pilot_rotated, pilot_stack, loc, heading, pilot_hint
    if pilot_walked < 1.0:
        keybuffer[ord('w')] = True
        pilot_walked += MovingSpeed
        nextAnimation()
        keybuffer[ord('w')] = False
    else:
        rx, ry, vx, vy = getRVcoordinates(loc)
        if DEBUG_AUTOPILOT:
            print 'walked to (%d, %d)' % (vx, vy)
        heading = heading_vector(pilot_heading)
        setCamera()
        if vx == N - 1 and vy == N - 1:
            if DEBUG_AUTOPILOT:
                print 'reached destination'
            pilot_status = PILOT_COMPLETE
            return

        if pilot_hint[vx][vy] >= 0:
            print 'maze has loop!'
            loc[0], loc[2] = vx + 0.5, -vy - 0.5
            pilot_hint[vx][vy] = 0
            pilot_status = PILOT_REVERSE
            pilot_rotated = 0.
            return
        choice = 0
        if not maze[vx][vy] & pilot_heading:
            choice |= PILOT_ACTION_FORWARD
        if not maze[vx][vy] & Left[pilot_heading]:
            choice |= PILOT_ACTION_LEFT
        if not maze[vx][vy] & Right[pilot_heading]:
            choice |= PILOT_ACTION_RIGHT
        if DEBUG_AUTOPILOT:
            print 'available choices are:', 'forward' if choice & PILOT_ACTION_FORWARD else '', 'left' if choice & PILOT_ACTION_LEFT else '', 'right' if choice & PILOT_ACTION_RIGHT else ''

        if choice == 0:
            if DEBUG_AUTOPILOT:
                print 'decision: reverse'
            loc[0], loc[2] = vx + 0.5, -vy - 0.5
            pilot_hint[vx][vy] = 0
            pilot_status = PILOT_REVERSE
            pilot_rotated = 0.
        else:
            if choice & PILOT_ACTION_RIGHT:
                if DEBUG_AUTOPILOT:
                    print 'decision: turn right'
                loc[0], loc[2] = vx + 0.5, -vy - 0.5
                pilot_hint[vx][vy] = choice & ~PILOT_ACTION_RIGHT
                pilot_status = PILOT_TURNRIGHT
                pilot_rotated = 0.
                pilot_stack.append(PILOT_ACTION_RIGHT)
                #if DEBUG_AUTOPILOT:
                #    print 'control stack ', map(translate_action, pilot_stack)
            elif choice & PILOT_ACTION_FORWARD:
                if DEBUG_AUTOPILOT:
                    print 'decision: continue walking'
                pilot_hint[vx][vy] = choice & ~PILOT_ACTION_FORWARD
                pilot_stack.append(PILOT_ACTION_FORWARD)
                pilot_walked = 0.
                #if DEBUG_AUTOPILOT:
                #    print 'control stack ', map(translate_action, pilot_stack)
            else:
                if DEBUG_AUTOPILOT:
                    print 'decision: turn left'
                loc[0], loc[2] = vx + 0.5, -vy - 0.5
                pilot_hint[vx][vy] = choice & ~PILOT_ACTION_LEFT
                pilot_status = PILOT_TURNLEFT
                pilot_rotated = 0.
                pilot_stack.append(PILOT_ACTION_LEFT)
                #if DEBUG_AUTOPILOT:
                #    print 'control stack ', map(translate_action, pilot_stack)

def autoPilotBacktrackWalking():
    global pilot_walked, pilot_heading, pilot_status, pilot_rotated, pilot_stack, loc, heading, pilot_hint
    if pilot_walked < 1.0:
        keybuffer[ord('w')] = True
        pilot_walked += MovingSpeed
        nextAnimation()
        keybuffer[ord('w')] = False
    else:
        rx, ry, vx, vy = getRVcoordinates(loc)
        if DEBUG_AUTOPILOT:
            print 'backtrack walked to (%d, %d)' % (vx, vy)
        heading = heading_vector(pilot_heading)
        setCamera()
        old_choice = pilot_stack[-1]
        pilot_stack = pilot_stack[:-1]
        if DEBUG_AUTOPILOT:
            print 'available choices are:', 'forward' if pilot_hint[vx][vy] & PILOT_ACTION_FORWARD else '', 'left' if pilot_hint[vx][vy] & PILOT_ACTION_LEFT else '', 'right' if pilot_hint[vx][vy] & PILOT_ACTION_RIGHT else ''
        if pilot_hint[vx][vy] == 0:
            if pilot_stack[-1] == PILOT_ACTION_LEFT:
                pilot_status = PILOT_BACKTRACK_TURNRIGHT
                pilot_rotated = 0.
                loc[0], loc[2] = vx + 0.5, -vy - 0.5
                if DEBUG_AUTOPILOT:
                #    print 'control stack ', map(translate_action, pilot_stack)
                    print 'decision: backtrack a left turn'
            elif pilot_stack[-1] == PILOT_ACTION_RIGHT:
                pilot_status = PILOT_BACKTRACK_TURNLEFT
                pilot_rotated = 0.
                loc[0], loc[2] = vx + 0.5, -vy - 0.5
                if DEBUG_AUTOPILOT:
                #    print 'control stack ', map(translate_action, pilot_stack)
                    print 'decision: backtrack a right turn'
            else:
                if DEBUG_AUTOPILOT:
                #    print 'control stack ', map(translate_action, pilot_stack)
                    print 'decision: backtrack a forward'
                pilot_walked = 0.
        else:
            if pilot_hint[vx][vy] & PILOT_ACTION_FORWARD:
                pilot_hint[vx][vy] = pilot_hint[vx][vy] & ~PILOT_ACTION_FORWARD
                pilot_status = PILOT_TURNRIGHT
                pilot_rotated = 0.
                loc[0], loc[2] = vx + 0.5, -vy - 0.5
                pilot_stack = pilot_stack[:-1]
                if DEBUG_AUTOPILOT:
                    print 'decision: turn right, substitute a right turn with a forward'
                #    print 'control stack ', map(translate_action, pilot_stack)
            elif pilot_hint[vx][vy] & PILOT_ACTION_LEFT:
                pilot_hint[vx][vy] = pilot_hint[vx][vy] & ~PILOT_ACTION_LEFT
                if pilot_stack[-1] == PILOT_ACTION_RIGHT:
                    pilot_status = PILOT_WALKING
                    pilot_walked = 0.
                    if DEBUG_AUTOPILOT:
                        print 'decision: go straight, substitute a right turn with a left turn'
                    pilot_stack[-1] = PILOT_ACTION_LEFT
                    pilot_stack.append(PILOT_ACTION_FORWARD)
                else:
                    pilot_status = PILOT_TURNRIGHT
                    pilot_rotated = 0.
                    loc[0], loc[2] = vx + 0.5, -vy - 0.5
                    if DEBUG_AUTOPILOT:
                        print 'decision: turn right, substitute a forward with a left turn'
                    pilot_stack.append(PILOT_ACTION_LEFT)
                #if DEBUG_AUTOPILOT:
                #    print 'control stack ', map(translate_action, pilot_stack)

def autoPilotTurnLeft():
    global pilot_walked, pilot_heading, pilot_status, pilot_rotated, pilot_stack, heading
    if 1. - math.fabs(reduce(add, map(mul, heading_vector(Left[pilot_heading]), heading))) > 0.01:
        keybuffer[ord('a')] = True
        pilot_rotated += RotatingSpeed
        nextAnimation()
        keybuffer[ord('a')] = False
    else:
        if DEBUG_AUTOPILOT:
            print 'turning left...'
        pilot_heading = Left[pilot_heading]
        heading = heading_vector(pilot_heading)
        pilot_stack.append(PILOT_ACTION_FORWARD)
        pilot_status = PILOT_WALKING
        pilot_walked = 0.

def autoPilotTurnRight():
    global pilot_walked, pilot_heading, pilot_status, pilot_rotated, pilot_stack, heading
    if 1. - math.fabs(reduce(add, map(mul, heading_vector(Right[pilot_heading]), heading))) > 0.01:
        keybuffer[ord('d')] = True
        pilot_rotated += RotatingSpeed
        nextAnimation()
        keybuffer[ord('d')] = False
    else:
        if DEBUG_AUTOPILOT:
            print 'turning right...'
        pilot_heading = Right[pilot_heading]
        heading = heading_vector(pilot_heading)
        pilot_stack.append(PILOT_ACTION_FORWARD)
        pilot_status = PILOT_WALKING
        pilot_walked = 0.

def autoPilotBacktrackTurnLeft():
    global pilot_walked, pilot_heading, pilot_status, pilot_rotated, pilot_stack, heading
    if 1. - math.fabs(reduce(add, map(mul, heading_vector(Left[pilot_heading]), heading))) > 0.01:
        keybuffer[ord('a')] = True
        pilot_rotated += RotatingSpeed
        nextAnimation()
        keybuffer[ord('a')] = False
    else:
        if DEBUG_AUTOPILOT:
            print 'backtrack turning left...'
        pilot_heading = Left[pilot_heading]
        heading = heading_vector(pilot_heading)
        pilot_stack = pilot_stack[:-1]
        pilot_status = PILOT_BACKTRACK_WALKING
        pilot_walked = 0.

def autoPilotBacktrackTurnRight():
    global pilot_walked, pilot_heading, pilot_status, pilot_rotated, pilot_stack, heading
    if 1. - math.fabs(reduce(add, map(mul, heading_vector(Right[pilot_heading]), heading))) > 0.01:
        keybuffer[ord('d')] = True
        pilot_rotated += RotatingSpeed
        nextAnimation()
        keybuffer[ord('d')] = False
    else:
        if DEBUG_AUTOPILOT:
            print 'backtrack turning right...'
        pilot_heading = Right[pilot_heading]
        heading = heading_vector(pilot_heading)
        pilot_stack = pilot_stack[:-1]
        pilot_status = PILOT_BACKTRACK_WALKING
        pilot_walked = 0.

def autoPilotReverse():
    global pilot_walked, pilot_heading, pilot_status, pilot_rotated, pilot_stack, heading
    if pilot_rotated < 3.04159:
        keybuffer[ord('d')] = True
        pilot_rotated += RotatingSpeed
        nextAnimation()
        keybuffer[ord('d')] = False
    else:
        if DEBUG_AUTOPILOT:
            print 'reverse...'
        pilot_heading = Right[Right[pilot_heading]]
        heading = heading_vector(pilot_heading)
        pilot_status = PILOT_BACKTRACK_WALKING
        pilot_walked = 0.

def autoPilotStepping():
    global pilot_stepped
    pilot_stepped += 1
    {
        PILOT_WALKING: autoPilotWalking,
        PILOT_TURNLEFT: autoPilotTurnLeft,
        PILOT_TURNRIGHT: autoPilotTurnRight,
        PILOT_REVERSE: autoPilotReverse,
        PILOT_BACKTRACK_WALKING: autoPilotBacktrackWalking,
        PILOT_BACKTRACK_TURNLEFT: autoPilotBacktrackTurnLeft,
        PILOT_BACKTRACK_TURNRIGHT: autoPilotBacktrackTurnRight,
        PILOT_COMPLETE: lambda: 0
    }[pilot_status]()

def loadTextureFromRawData(img_w, img_h, data):
    tex = glGenTextures(1)
    glBindTexture(GL_TEXTURE_2D, tex)
    glPixelStorei(GL_UNPACK_ALIGNMENT,1)
    glTexImage2D(GL_TEXTURE_2D, 0, 3, img_w, img_h, 0, GL_RGBA, GL_UNSIGNED_BYTE, data)
    glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT)
    glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT)
    glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST)
    glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST)
    return tex

def loadTextureFromFile(fname):
    with Image.open(fname) as img:
        w, h = img.size
        dat = img.tostring('raw', 'RGBX', 0, -1)
        return loadTextureFromRawData(w, h, dat)
    return 0

def loadSkybox():
    global tex_skybox, vert_skybox, texc_skybox

    fname = {
        SKYBOX_RIGHT: 'skybox_right.jpg',
        SKYBOX_TOP: 'skybox_top.jpg',
        SKYBOX_FRONT: 'skybox_front.jpg',
        SKYBOX_LEFT: 'skybox_left.jpg',
        SKYBOX_BOTTOM: 'skybox_bottom.jpg',
        SKYBOX_BACK: 'skybox_back.jpg'
    }

    for f,n in fname.iteritems():
        tex_skybox[f] = loadTextureFromFile(n)

    vert_skybox[SKYBOX_BACK] = [
        [SKYBOX_SIZE, SKYBOX_SIZE, SKYBOX_SIZE],
        [SKYBOX_SIZE, -SKYBOX_SIZE, SKYBOX_SIZE],
        [-SKYBOX_SIZE, SKYBOX_SIZE, SKYBOX_SIZE],
        [-SKYBOX_SIZE, -SKYBOX_SIZE, SKYBOX_SIZE]]
    texc_skybox[SKYBOX_BACK] = [[0,1], [0,0], [1,1], [1,0]]

    vert_skybox[SKYBOX_LEFT] = [
        [-SKYBOX_SIZE, SKYBOX_SIZE, SKYBOX_SIZE],
        [-SKYBOX_SIZE, -SKYBOX_SIZE, SKYBOX_SIZE],
        [-SKYBOX_SIZE, SKYBOX_SIZE, -SKYBOX_SIZE],
        [-SKYBOX_SIZE, -SKYBOX_SIZE, -SKYBOX_SIZE]]
    texc_skybox[SKYBOX_LEFT] = [[0,1], [0,0], [1,1], [1,0]]

    vert_skybox[SKYBOX_FRONT] = [
        [-SKYBOX_SIZE, SKYBOX_SIZE, -SKYBOX_SIZE],
        [-SKYBOX_SIZE, -SKYBOX_SIZE, -SKYBOX_SIZE],
        [SKYBOX_SIZE, SKYBOX_SIZE, -SKYBOX_SIZE],
        [SKYBOX_SIZE, -SKYBOX_SIZE, -SKYBOX_SIZE]]
    texc_skybox[SKYBOX_FRONT] = [[0,1], [0,0], [1,1], [1,0]]

    vert_skybox[SKYBOX_RIGHT] = [
        [SKYBOX_SIZE, SKYBOX_SIZE, -SKYBOX_SIZE],
        [SKYBOX_SIZE, -SKYBOX_SIZE, -SKYBOX_SIZE],
        [SKYBOX_SIZE, SKYBOX_SIZE, SKYBOX_SIZE],
        [SKYBOX_SIZE, -SKYBOX_SIZE, SKYBOX_SIZE]]
    texc_skybox[SKYBOX_RIGHT] = [[0,1], [0,0], [1,1], [1,0]]

    vert_skybox[SKYBOX_TOP] = [
        [SKYBOX_SIZE, SKYBOX_SIZE, SKYBOX_SIZE],
        [-SKYBOX_SIZE, SKYBOX_SIZE, SKYBOX_SIZE],
        [SKYBOX_SIZE, SKYBOX_SIZE, -SKYBOX_SIZE],
        [-SKYBOX_SIZE, SKYBOX_SIZE, -SKYBOX_SIZE]]
    texc_skybox[SKYBOX_TOP] = [[0,1], [0,0], [1,1], [1,0]]

def loadTextures():
    global tex_wall, tex_sand

    tex_wall = loadTextureFromFile('brick.jpg')
    tex_sand = loadTextureFromFile('sand.jpg')

def setupLights():
    lightZeroPosition = [10., 10., 10., 1.]
    lightZeroColor = [1.0, 1.0, 1.0, 1.0]
    glLightfv(GL_LIGHT0, GL_POSITION, lightZeroPosition)
    glLightfv(GL_LIGHT0, GL_DIFFUSE, lightZeroColor)
    glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 0.1)
    glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.05)

def setCamera():
    global heading, loc

    if DEBUG_FUNCTRACE:
        print 'functrace: setCamera'
    glMatrixMode(GL_MODELVIEW)
    glLoadIdentity()
    at = map(add, loc, heading)
    params = deepcopy(loc)
    params.extend(at)
    params.extend([0., 1., 0.])
    gluLookAt(*params)
    glutPostRedisplay()

def getRVcoordinates(loc):
    rel_x, rel_y = math.floor(loc[0]), math.floor(-loc[2])
    vrt_x, vrt_y = int(rel_x), int(rel_y)
    return rel_x, rel_y, vrt_x, vrt_y

def checkXBlocked(old_loc, new_loc, rx, ry, vx, vy):
    if new_loc[0] - rx < 0.2 and new_loc[0] - old_loc[0] < 0:
        if DEBUG_COLLISON:
            print 'trying reach west:',
        if maze[vx][vy] & WEST:
            if DEBUG_COLLISON:
                print 'rejected'
            new_loc[0] = rx + 0.21
        else:
            if DEBUG_COLLISON:
                print 'accepted'
        return maze[vx][vy] & WEST
    if new_loc[0] - rx > 0.8 and new_loc[0] - old_loc[0] > 0:
        if DEBUG_COLLISON:
            print 'trying reach east:',
        if maze[vx][vy] & EAST:
            if DEBUG_COLLISON:
                print 'rejected'
            new_loc[0] = rx + 0.79
        else:
            if DEBUG_COLLISON:
                print 'accepted'
        return maze[vx][vy] & EAST
    return False

def checkYBlocked(old_loc, new_loc, rx, ry, vx, vy):
    if -new_loc[2] - ry < 0.2 and -new_loc[2] - -old_loc[2] < 0:
        if DEBUG_COLLISON:
            print 'trying reach south:',
        if maze[vx][vy] & SOUTH:
            if DEBUG_COLLISON:
                print 'rejected'
            new_loc[2] = -(ry + 0.21)
        else:
            if DEBUG_COLLISON:
                print 'accepted'
        return maze[vx][vy] & SOUTH
    if -new_loc[2] - ry > 0.8 and -new_loc[2] - -old_loc[2] > 0:
        if DEBUG_COLLISON:
            print 'trying reach north:',
        if maze[vx][vy] & NORTH:
            if DEBUG_COLLISON:
                print 'rejected'
            new_loc[2] = -(ry + 0.79)
        else:
            if DEBUG_COLLISON:
                print 'accepted'
        return maze[vx][vy] & NORTH
    return False

def checkBlocked(old_loc, new_loc):
    if DEBUG_COLLISON:
        print 'testing',old_loc,'against',new_loc
    rx, ry, vx, vy = getRVcoordinates(old_loc)
    if DEBUG_COLLISON:
        print 'R', rx, ry, 'V', vx, vy
    checkXBlocked(loc, new_loc, rx, ry, vx, vy)
    checkYBlocked(loc, new_loc, rx, ry, vx, vy)

def extendsSight(i, j, d, n):
    visited[i][j] = True
    if n == 0:
        return
    if not maze[i][j] & d:
        extendsSight(*map(add, [i,j], towards[d]), d = d, n = n - 1)

def nextAnimation():
    global heading, loc, done, timer
    if DEBUG_FUNCTRACE:
        print 'functrace: nextAnimation'
    refresh = False
    if keybuffer[ord('a')] and not keybuffer[ord('d')]:
        cos = math.cos(RotatingSpeed)
        sin = math.sin(RotatingSpeed)
        heading = [cos * heading[0] + sin * heading[2], heading[1], -sin * heading[0] + cos * heading[2]]
        refresh = True
    elif keybuffer[ord('d')] and not keybuffer[ord('a')]:
        cos = math.cos(-RotatingSpeed)
        sin = math.sin(-RotatingSpeed)
        heading = [cos * heading[0] + sin * heading[2], heading[1], -sin * heading[0] + cos * heading[2]]
        refresh = True
    if keybuffer[ord('w')] and not keybuffer[ord('s')]:
        new_loc = map(add, loc, map(lambda x: x * MovingSpeed, heading))
        checkBlocked(loc, new_loc)
        loc = new_loc
        refresh = True
    elif keybuffer[ord('s')] and not keybuffer[ord('w')]:
        new_loc = map(add, loc, map(lambda x: x * -MovingSpeed, heading))
        checkBlocked(loc, new_loc)
        loc = new_loc
        refresh = True
    if refresh:
        rx, ry, vx, vy = getRVcoordinates(loc)
        for d in towards.iterkeys():
            extendsSight(vx,vy,d,3)
        if rx == N - 1 and ry == N - 1 and not done:
            timer = time.time() - timer
            done = True
            print 'COMPLETE, TIME ELAPSED %.2fs' % timer
        l = math.sqrt(reduce(add, map(mul, heading, heading)))
        heading = map(div, heading, [l] * 3)
        setCamera()

def resize(w, h):
    global win_width, win_height
    win_width, win_height = w, h
    glViewport(0, 0, w, h)
    glMatrixMode(GL_PROJECTION)
    glLoadIdentity()
    gluPerspective(60, float(w) / float(h) if h != 0 else float(w), 0.1, 10000)
    glMatrixMode(GL_MODELVIEW)
    setCamera()

def keyPressed(key, x, y):
    global keybuffer
    keybuffer[ord(key)] = True
    glutPostRedisplay()

def keyReleased(key, x, y):
    global keybuffer
    keybuffer[ord(key)] = False

def loadShaders():
    global shader
    vs = glCreateShader(GL_VERTEX_SHADER)
    fs = glCreateShader(GL_FRAGMENT_SHADER)

    with open('maze_pp.vs','r') as f:
        vv = f.read()
    with open('maze_pp.fs','r') as f:
        ff = f.read()
    glShaderSource(vs, vv)
    glShaderSource(fs, ff)

    glCompileShader(vs)
    if glGetShaderiv(vs, GL_COMPILE_STATUS) != GL_TRUE:
        raise RuntimeError(glGetShaderInfoLog(vs))
    glCompileShader(fs)
    if glGetShaderiv(fs, GL_COMPILE_STATUS) != GL_TRUE:
        raise RuntimeError(glGetShaderInfoLog(fs))

    shader = glCreateProgram()
    glAttachShader(shader, vs)
    glAttachShader(shader, fs)
    glLinkProgram(shader)
    glUseProgram(shader)

def drawSkyBox(x, y, w, height):
    for i in vert_skybox.iterkeys():
        glBindTexture(GL_TEXTURE_2D, tex_skybox[i])
        glBegin(GL_TRIANGLE_STRIP)
        for t, v in zip(texc_skybox[i], vert_skybox[i]):
            glTexCoord2f(*t)
            glVertex3f(*map(add, loc, v))
        glEnd()

def drawPlane(w, h):
    glBindTexture(GL_TEXTURE_2D, tex_sand)
    vert = [[w, 0, -h], [0, 0, -h], [w, 0, 0], [0, 0, 0]]
    texc = [[w, h], [0, h], [w, 0], [0, 0]]
    glBegin(GL_TRIANGLE_STRIP)
    for t, v in zip(texc, vert):
        glTexCoord2f(*t)
        #glNormal3f(0., 1., 0.)
        glVertex3f(*v)
    glEnd()

def drawWallQuad(dx, dz, is_ns, negative_norm):
    vert_ns = [[1, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0]]
    vert_we = [[0, 1, 0], [0, 1, -1], [0, 0, 0], [0, 0, -1]]
    texc = [[1, 1], [0, 1], [1, 0], [0, 0]]
    glBegin(GL_TRIANGLE_STRIP)
    for t, v in zip(texc, vert_ns if is_ns else vert_we):
        glTexCoord2f(*t)
        if is_ns:
            glNormal3f(0, 0, -1 if negative_norm else 1)
        else:
            glNormal3f(-1 if negative_norm else 1, 0, 0)
        v[0] += dx
        v[2] += dz
        glVertex3f(*v)
    glEnd()

def drawBoxWall(x, y, w):
    glBindTexture(GL_TEXTURE_2D, tex_wall)
    if w & NORTH:
        drawWallQuad(x, -y - 1, True, False)
    if w & SOUTH:
        drawWallQuad(x, -y, True, True)
    if w & WEST:
        drawWallQuad(x, -y, False, False)
    if w & EAST:
        drawWallQuad(x + 1, -y, False, True)

def drawWalls():
    pos_x, pos_y = loc[0], loc[2]
    vrt_x, vrt_y = round(pos_x), -round(pos_y)
    range_xlow, range_xhigh = vrt_x - 10, vrt_x + 10
    range_ylow, range_yhigh = vrt_y - 10, vrt_y + 10
    if DEBUG_DRAW:
        print 'redraw limited to x(%d, %d), y(%d, %d)' % (range_xlow, range_xhigh, range_ylow, range_yhigh)
    for i, row in enumerate(maze):
        if i > range_xlow and i < range_xhigh:
            for j, elem in enumerate(row):
                if j > range_ylow and j < range_yhigh:
                    drawBoxWall(i, j, elem & ~(WEST & SOUTH) if i != 0 and j != 0 else elem)

def beginHUD():
    glUseProgram(0)
    glMatrixMode(GL_PROJECTION)
    glPushMatrix()
    glLoadIdentity()
    glOrtho(-win_width / 2., win_width / 2., -win_height / 2., win_height / 2., -1., 1.)
    glMatrixMode(GL_MODELVIEW)
    glPushMatrix()
    glLoadIdentity()

def endHUD():
    glMatrixMode(GL_PROJECTION)
    glPopMatrix()
    glMatrixMode(GL_MODELVIEW)
    glPopMatrix()
    glUseProgram(shader)

def isMapBlockDrawable(i, j, w):
    ni, nj = map(add, [i,j], towards[w])
    return ((isCoordinateInRange(ni, nj) and visited[ni][nj]) or visited[i][j]) and maze[i][j] & w

def drawMap():
    beginHUD()
    glColor4f(1, 0, 0, 1)
    glLineWidth(3)
    glBegin(GL_LINES)
    glVertex3f(-5, 5, 0)
    glVertex3f(5, -5, 0)
    glVertex3f(5, 5, 0)
    glVertex3f(-5, -5, 0)
    glEnd()
    glColor4f(0, 0, 1, 1)
    theta = math.acos(reduce(add, map(mul, heading_vector(NORTH), heading))) / 3.141592654 * 180
    if heading[0] > 0:
        theta = -theta
    glRotatef(-theta, 0, 0, 1)
    glTranslatef(-loc[0] * map_scale, loc[2] * map_scale, 0)
    glBegin(GL_LINES)
    for i in xrange(N):
        hstart, hend = 0, 0
        vstart, vend = 0, 0
        for j in xrange(N):
            if isMapBlockDrawable(j, i, SOUTH):
                if hstart == hend:
                    hstart = j * map_scale
                    hend = hstart
                hend += map_scale
            else:
                if hstart != hend:
                    glVertex3f(hstart, i * map_scale, 0)
                    glVertex3f(hend, i * map_scale, 0)
                hstart = hend
            if isMapBlockDrawable(i, j, WEST):
                if vstart == vend:
                    vstart = j * map_scale
                    vend = vstart
                vend += map_scale
            else:
                if vstart != vend:
                    glVertex3f(i * map_scale, vstart, 0)
                    glVertex3f(i * map_scale, vend, 0)
                vstart = vend
        if hstart != hend:
            glVertex3f(hstart, i * map_scale, 0)
            glVertex3f(hend, i * map_scale, 0)
        if vstart != vend:
            glVertex3f(i * map_scale, vstart, 0)
            glVertex3f(i * map_scale, vend, 0)

    hstart, hend = 0, 0
    vstart, vend = 0, 0
    for j in xrange(N):
        if isMapBlockDrawable(j, i, NORTH):
            if hstart == hend:
                hstart = j * map_scale
                hend = hstart
            hend += map_scale
        else:
            if hstart != hend:
                glVertex3f(hstart, N * map_scale, 0)
                glVertex3f(hend, N * map_scale, 0)
            hstart = hend
        if isMapBlockDrawable(i, j, EAST):
            if vstart == vend:
                vstart = j * map_scale
                vend = vstart
            vend += map_scale
        else:
            if vstart != vend:
                glVertex3f(N * map_scale, vstart, 0)
                glVertex3f(N * map_scale, vend, 0)
            vstart = vend
    if hstart != hend:
        glVertex3f(hstart, N * map_scale, 0)
        glVertex3f(hend, N * map_scale, 0)
    if vstart != vend:
        glVertex3f(N * map_scale, vstart, 0)
        glVertex3f(N * map_scale, vend, 0)

    glColor4f(0, 1, 0, 1)
    glVertex3f(-5 + N * map_scale - (map_scale / 2), 5 + N * map_scale - (map_scale / 2), 0)
    glVertex3f(5 + N * map_scale - (map_scale / 2), -5 + N * map_scale - (map_scale / 2), 0)
    glVertex3f(5 + N * map_scale - (map_scale / 2), 5 + N * map_scale - (map_scale / 2), 0)
    glVertex3f(-5 + N * map_scale - (map_scale / 2), -5 + N * map_scale - (map_scale / 2), 0)
    glEnd()

    glprint(30, 30, 'TIME ELAPSED: %.2fs' % ((time.time() - timer) if not done else timer))
    glprint(30, 45, 'FRAME RATE: %.2f' % fps)

    glprint(30, 65, 'AUTO PILOT %s' % ('ENABLED' if ENABLE_AUTOPILOT else 'DISABLED'))
    glprint(30, 80, 'HUD %s' % ('ALWAYS ON' if HUD_ALWAYS_ON else 'MANUAL'))


    glprint(30, 100, 'MAZE SIZE %d' % N)
    glprint(30, 115, 'SKYBOX SIZE %d' % SKYBOX_SIZE)
    glprint(30, 130, 'MOVING SPEED %.2f' % MovingSpeed)
    glprint(30, 145, 'ROTATING SPEED %.2f' % RotatingSpeed)

    if ENABLE_AUTOPILOT:
        glprint(30, 160, 'AUTO PILOT DEBUG:')
        glprint(60, 175, 'STATUS %s' % translate_status(pilot_status))
        glprint(60, 190, 'CONTROL STACK DEPTH %d' % len(pilot_stack))
        glprint(60, 205, 'STEPPED %d' % pilot_stepped)
        glprint(60, 220, 'LAST ACTION %s' % translate_action(pilot_stack[-1]) if len(pilot_stack) > 0 else 'N/A')

    endHUD()

def glprint(x, y, str):
    glLoadIdentity()
    glColor4f(1, 0, 0, 1)
    glTranslatef(-win_width / 2, win_height / 2, 0)
    glRasterPos2f(x,-y)
    glScalef(2,2,2)
    for ch in str:
        glutBitmapCharacter(GLUT_BITMAP_9_BY_15, ctypes.c_int(ord(ch)))

def display():
    global timer, alert, fps
    try:
        glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT)
        begin = time.time()
        #glUseProgram(shader)
        if ENABLE_AUTOPILOT:
            autoPilotStepping()
        nextAnimation()
        red = [1.0, 0., 0., 1.]
        green = [0., 1.0, 0., 1.]
        blue = [0., 0., 1.0, 1.]

        glMaterialfv(GL_FRONT_AND_BACK,GL_DIFFUSE,blue)
        drawSkyBox((N - 32) / 2, (32 - N) / 2, 32, 16)
        glMaterialfv(GL_FRONT_AND_BACK,GL_DIFFUSE,red)
        drawPlane(64, 64)
        glMaterialfv(GL_FRONT_AND_BACK,GL_DIFFUSE,green)
        drawWalls()

        if keybuffer[ord('m')] or HUD_ALWAYS_ON:
            drawMap()

        glutSwapBuffers()
        elapsed = time.time() - begin
        fps = 1. / elapsed
        if DEBUG_DRAW:
            print 'redraw costs %.2fs' % elapsed,'estimated fps %.1f' % fps
    except Exception as e:
        print 'error occurs:', e
        print traceback.format_exc()
        glutLeaveMainLoop()
    return

if __name__ == '__main__':
    main()

maze_gen.py

import random
from operator import add
from copy import deepcopy
import sys

NORTH  = 1
WEST   = 2
SOUTH  = 4
EAST   = 8

towards = {
    EAST: [1, 0],
    NORTH: [0, 1],
    WEST: [-1, 0],
    SOUTH: [0, -1]
}

reverse = {0: 0, EAST: WEST, WEST: EAST, NORTH: SOUTH, SOUTH: NORTH}
N = 16
visited = []
maze = []

def isCoordinateInRange(x, y):
    return x >= 0 and x < N and y >= 0 and y < N

def validate(x, y):
    return isCoordinateInRange(x,y) and not visited[x][y]

def depth_first_search(x, y, src):
    global visited
    visited[x][y] = True
    maze[x][y] = (NORTH | WEST | SOUTH | EAST) & ~reverse[src]
    dirs = towards.items()
    random.shuffle(dirs)
    for d in dirs:
        candidate = map(add, [x, y], d[1])
        if validate(*candidate):
            maze[x][y] = maze[x][y] & ~d[0]
            print candidate
            depth_first_search(candidate[0], candidate[1], d[0])

def main():
    sys.setrecursionlimit(N * N + 10)
    for i in range(N):
        visited.append([False] * N)
        maze.append([0] * N)
    depth_first_search(0, 0, 0)
    with open('maze_gen.out', 'w') as f:
        for row in maze:
            f.write(' '.join(map(str, row)))
            f.write('\n')

if __name__ == '__main__':
    main()

maze_pp.fs

varying vec4 diffuse,ambientGlobal, ambient, ecPos;
varying vec3 normal,halfVector;
uniform sampler2D tex;
void main()
{
    vec3 n,halfV,viewV,lightDir;
    float NdotL,NdotHV;
    vec4 color = ambientGlobal;
    float att, dist;

    /* a fragment shader can't write a verying variable, hence we need
    a new variable to store the normalized interpolated normal */
    n = normalize(normal);

    // Compute the ligt direction
    lightDir = vec3(gl_LightSource[0].position-ecPos);

    /* compute the distance to the light source to a varying variable*/
    dist = length(lightDir);


    /* compute the dot product between normal and ldir */
    NdotL = max(dot(n,normalize(lightDir)),0.0);

    if (NdotL > 0.0) {

        att = 1.0 / (gl_LightSource[0].constantAttenuation +
                gl_LightSource[0].linearAttenuation * dist +
                gl_LightSource[0].quadraticAttenuation * dist * dist);
        color += att * (diffuse * NdotL + ambient);
        //color += att * (diffuse * NdotL + ambient);


        halfV = normalize(halfVector);
        NdotHV = max(dot(n,halfV),0.0);
        color += att * gl_FrontMaterial.specular * gl_LightSource[0].specular * pow(NdotHV,gl_FrontMaterial.shininess);
    }

    //gl_FragColor = diffuse;
    gl_FragColor = texture2D(tex,gl_TexCoord[0].st);
}

maze_pp.vs

varying vec4 diffuse,ambientGlobal,ambient, ecPos;
varying vec3 normal,halfVector;

void main()
{
    vec3 aux;

    /* first transform the normal into eye space and normalize the result */
    normal = normalize(gl_NormalMatrix * gl_Normal);

    /* compute the vertex position  in camera space. */
    ecPos = gl_ModelViewMatrix * gl_Vertex;

    /* Normalize the halfVector to pass it to the fragment shader */
    halfVector = gl_LightSource[0].halfVector.xyz;

    /* Compute the diffuse, ambient and globalAmbient terms */
    diffuse = gl_FrontMaterial.diffuse * gl_LightSource[0].diffuse;
    ambient = gl_FrontMaterial.ambient * gl_LightSource[0].ambient;
    ambientGlobal = gl_LightModel.ambient * gl_FrontMaterial.ambient;

    gl_TexCoord[0] = gl_TextureMatrix[0] * gl_MultiTexCoord0;
    gl_Position = ftransform();
}

sand.jpg

skybox_back.jpg

skybox_bottom.jpg

skybox_front.jpg

skybox_left.jpg

skybox_right.jpg

skybox_top.jpg