API tools faq
paste
Advertisement
here2share

# 3D_maze.py

here2share
Feb 25th, 2021
897
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 68.41 KB | None | 0 0
raw download clone embed print report
  1. # 3D_maze.py
  2.  
  3. # Copyright 2014, Jackson Bahr
  4.  
  5. # This program is free software: you can redistribute it and/or modify
  6. # it under the terms of the GNU General Public License as published by
  7. # the Free Software Foundation, either version 3 of the License, or
  8. # (at your option) any later version.
  9. #
  10. # This program is distributed in the hope that it will be useful,
  11. # but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13. # GNU General Public License for more details.
  14. #
  15. # You should have received a copy of the GNU General Public License
  16. # along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17.  
  18.  
  19. import copy
  20. import math
  21. from Tkinter import *
  22. import random
  23. import time
  24.  
  25. CYCLE_AMOUNT = 5 # higher number -> fewer cycles
  26.  
  27. # if you change the resolution,
  28. # you may need to slightly alter the following two:
  29. CAM_HEIGHT = 0.125
  30. CAM_WIDTH = 0.015
  31.  
  32. # do not edit these:
  33. CAM_LENGTH = 0.1
  34. CAM_SEP = 0.04
  35. WALL_H = 0.5
  36. CELL_SIZE = 40 # pixels
  37. DEBUG = False
  38. FOV = math.pi/2
  39.  
  40. ################################################################################
  41. ##### Point & Seg Helper Functions #############################################
  42. ################################################################################
  43.  
  44. def flipCoin():
  45.     # taken from:
  46.     # kosbie.net/cmu/fall-12/15-112/handouts/notes-recursion/mazeSolver.py
  47.     return random.choice([True, False])
  48.  
  49. def smallChance():
  50.     choices = [True]
  51.     choices.extend([False]*CYCLE_AMOUNT)
  52.     return random.choice(choices)
  53.  
  54. def withinEp(x, y):
  55.     """Returns True if x and y are within some predefined epsilon: 0.0001"""
  56.     epsilon = 0.0001
  57.     return abs(x-y) < epsilon
  58.  
  59. def chopDomain(x):
  60.     """Chops number to fit within [1,1] for use with arccos"""
  61.     if (x > 1):
  62.         return 1
  63.     elif (x < -1):
  64.         return -1
  65.     else:
  66.         return x
  67.  
  68. def sec(x):
  69.     return 1 / math.cos(x)
  70.  
  71. def csc(x):
  72.     return 1 / math.sin(x)
  73.  
  74. def isNumber(x):
  75.     """Returns True if x in an int, long, or float; False otherwise"""
  76.     return type(x) in (int, long, float)
  77.  
  78. def sign(x):
  79.     """Returns "+" for non-negative numbers; "-" otherwise"""
  80.  
  81. def mathSign(x):
  82.     if (x == 0):
  83.         return 0
  84.     else:
  85.         return (x/abs(x))
  86.  
  87.  
  88. def xKey(point):
  89.     return point.x
  90.  
  91. def yKey(point):
  92.     return point.y
  93.  
  94. def getElementFromSet(s):
  95.     """Non-destructively returns an arbitrary element from a set"""
  96.     for val in s:
  97.         return val # breaks
  98.  
  99. def extremeX(pointSet):
  100.     minPoint = min(pointSet, key=xKey)
  101.     maxPoint = max(pointSet, key=xKey)
  102.     return (minPoint, maxPoint)
  103.  
  104. def extremeY(pointSet):
  105.     minPoint = min(pointSet, key=yKey)
  106.     maxPoint = max(pointSet, key=yKey)
  107.     return (minPoint, maxPoint)
  108.  
  109. # from http://www.kosbie.net/cmu/spring-14/15-112/handouts/grayScale.py
  110. def hexColor(red, green, blue):
  111.     return ("#%02x%02x%02x" % (red, green, blue))
  112.  
  113. # color gradient idea from Delancey Wu
  114. def makeColor(row, col, rows, cols):
  115.     if (((row == rows-1) and (col == cols-2)) or
  116.           ((row == rows-2) and (col == cols-1))):
  117.         color = hexColor(255,255,255)
  118.     else:
  119.         green = 255*(row+col)/float(rows+cols)
  120.         blue = 255*(rows+cols-row-col)/float(rows+cols)
  121.         red = 40
  122.         color = hexColor(red, green, blue)
  123.     return color
  124.  
  125. def rgbFromHex(color):
  126.     # get RGB color from hex
  127.     red = int(color[1:3], 16)
  128.     green = int(color[3:5], 16)
  129.     blue = int(color[5:], 16)
  130.     return (red, green, blue)
  131.  
  132. def rightChannelColor(color):
  133.     # red-tint color for left channel of
  134.     # red-cyan anaglyph
  135. #    (red, green, blue) = rgbFromHex(color)
  136. #    gray = (red+green+blue)/3
  137. #    newGray = min(255, gray*2)
  138.     # I could not get this to work, so I resorted
  139.     # to black/white (rather, red/cyan) for 3DG:
  140.     return hexColor(255, 0, 0)
  141.  
  142. def leftChannelColor(color):
  143.     # cyan-tint color for right channel of
  144.     # red-cyan anaglyph
  145. #    (red, green, blue) = rgbFromHex(color)
  146. #    gray = (red+green+blue)/2
  147. #    newGray = min(255, gray*2)
  148.     # I could not get this to work, so I resorted
  149.     # to black/white (rather, red/cyan) for 3DG:
  150.     return hexColor(0, 255, 255)
  151.  
  152. def shrinkScreenSeg(x, h, otherX, otherH):
  153.     if (abs(x) > abs(h)):
  154.         newX = 1.0*mathSign(x)
  155.         a = newX / x
  156.         newH = a*h + (1-a)*otherH
  157.     else:
  158.         newH = 1.0*mathSign(h)
  159.         a = newH / h
  160.         newX = a*x + (1-a)*otherX
  161.     return (newX, newH)
  162.  
  163.  
  164.  
  165. ################################################################################
  166. ##### Point, Seg, Ray Classes ##################################################
  167. ################################################################################
  168.  
  169. class Point(object):
  170.     def __init__(self, x, y):
  171.         if (not isNumber(x) or not isNumber(y)):
  172.             assert(False), "cannot make a point from non-numbers"
  173.         self.x = x
  174.         self.y = y
  175.  
  176.     def __eq__(self, other):
  177.         return (withinEp(self.x, other.x) and withinEp(self.y, other.y))
  178.  
  179.     def __ne__(self, other):
  180.         return not self.__eq__(other)
  181.  
  182.     def __str__(self):
  183.         return "(%f,%f)" % (self.x, self.y)
  184.  
  185.     def __repr__(self):
  186.         return "Point(%f,%f)" % (self.x, self.y)
  187.  
  188.     def __hash__(self):
  189.         hashables = (self.x, self.y)
  190.         return hash(hashables)
  191.  
  192.     def dist(self, other):
  193.         dx = self.x - other.x
  194.         dy = self.y - other.y
  195.         return math.sqrt(dx**2 + dy**2)
  196.  
  197. class Seg(object):
  198.     def __init__(self, p1, p2, color=hexColor(0,0,0)):
  199.         # sanity check
  200.         if not (type(p1) == type(p2) == Point):
  201.             assert(False), "cannot make a seg from nonpoints"
  202.         self.p1 = p1
  203.         self.p2 = p2
  204.         self.color = color
  205.         self.isVert = (self.kind() == "vert")
  206.         self.isHoriz = (self.kind() == "horiz")
  207.  
  208.     def __eq__(self, other):
  209.         if ((self.p1 == other.p1) and (self.p2 == other.p2)):
  210.             return True
  211.         elif ((self.p1 == other.p2) and (self.p2 == other.p1)):
  212.             return True
  213.         else:
  214.             return False
  215.  
  216.     def __str__(self):
  217.         return "(%f,%f)-(%f,%f)" % (self.p1.x, self.p1.y,
  218.                                    self.p2.x, self.p2.y)
  219.  
  220.     def __repr__(self):
  221.         return "Seg("+repr(self.p1)+","+repr(self.p2)+")"
  222.  
  223.     def __hash__(self):
  224.         hashables = (self.p1.x, self.p1.y, self.p2.x, self.p2.y)
  225.         return hash(hashables)
  226.  
  227.     def kind(self):
  228.         if (self.p1.x == self.p2.x):
  229.             return "vert"
  230.         elif (self.p1.y == self.p2.y):
  231.             return "horiz"
  232.         else:
  233.             return "other"
  234.  
  235.     def withinDist(self, eye, dist):
  236.         """Returns True if eye is within a certain distance of
  237.        the segment (in a rectangular sense around the edges)"""
  238.         minX = min(self.p1.x, self.p2.x)
  239.         maxX = max(self.p1.x, self.p2.x)
  240.         minY = min(self.p1.y, self.p2.y)
  241.         maxY = max(self.p1.y, self.p2.y)
  242.         return ((minX - dist < eye.x < maxX + dist) and
  243.                 (minY - dist < eye.y < maxY + dist))
  244.  
  245.  
  246. class Ray(object):
  247.     def __init__(self, eye, target):
  248.         self.eye = eye
  249.         self.dx = target.x - eye.x
  250.         self.dy = target.y - eye.y
  251.         self.target = target
  252.  
  253.     def __eq__(self, other):
  254.         return ((self.eye == other.eye) and (self.dx == other.dx)
  255.             and (self.dy == other.dy))
  256.  
  257.     def __str__(self):
  258.         return str(self.eye) + " -> " + str(self.target)
  259.  
  260.     def __repr__(self):
  261.         return "Ray("+repr(self.eye)+","+repr(self.target)+")"
  262.  
  263.     def __sub__(self, other):
  264.         if (self.eye != other.eye):
  265.             assert(False), "cannot subtract"
  266.         return Ray(other.target, self.target)
  267.  
  268.     def __mul__(self, scale):
  269.         newTargetX = self.eye.x + scale*self.dx
  270.         newTargetY = self.eye.y + scale*self.dy
  271.         return Ray(self.eye, Point(newTargetX, newTargetY))
  272.  
  273.     def __rmul__(self, scale):
  274.         return self.__mul__(scale)
  275.  
  276.  
  277.     def dot(self, other):
  278.         if (type(other) != Ray):
  279.             assert(False), "cannot dot non-rays"
  280.         if (self.eye != other.eye):
  281.             assert(False), "rays have different starting points"
  282.         return self.dx * other.dx + self.dy * other.dy
  283.  
  284.     def norm(self):
  285.         return math.sqrt(self.dot(self))
  286.  
  287.     def angle(self, other):
  288.         if (type(other) != Ray):
  289.             assert(False), "angle not defined for non-rays"
  290.         if (self.eye != other.eye):
  291.             assert(False), "rays have different starting points"
  292.         value = chopDomain(self.dot(other) /float(self.norm() * other.norm()))
  293.         angle = math.acos(value)
  294.         return angle # radians
  295.  
  296.     def rotate(self, angle):
  297.         # angle in radians
  298.         # taken from jbahr-hw8.py
  299.         rotationMatrix = Matrix([[math.cos(angle), -math.sin(angle)],
  300.                                  [math.sin(angle), math.cos(angle)]])
  301.         oldNorm = self.norm()
  302.         dir = Vector([self.dx, self.dy])
  303.         newDir = rotationMatrix.mult(dir)
  304.         newPoint = Point(newDir.elements[0], newDir.elements[1])
  305.         newTarget = Point(newPoint.x + self.eye.x, newPoint.y + self.eye.y)
  306.         newRay = Ray(self.eye, newTarget)
  307.         return newRay
  308.  
  309.     def angleWithX(self):
  310.         xAxis = Ray(self.eye, Point(self.eye.x + 1, self.eye.y))
  311.         return self.angle(xAxis)
  312.        
  313.  
  314. class Matrix(object):
  315.     def __init__(self, elements):
  316.         self.elements = elements
  317.         self.rows = len(elements)
  318.         if (type(elements[0]) == list):
  319.             self.cols = len(elements[0])
  320.         else:
  321.             # handle vectors too
  322.             self.cols = 1
  323.  
  324.     def mult(self, other):
  325.         if (type(other) != Vector):
  326.             assert(False), "cannot be multiplied"
  327.         # other must be a vector
  328.         def dotprod(row):
  329.             return Vector(row).dot(other)
  330.         # using map was the idea of James Wu
  331.         return Vector(map(dotprod, self.elements))
  332.  
  333.     def transpose(self):
  334.         # this implementation was taken from recitation
  335.         return Matrix(zip(*self.elements))
  336.  
  337.     def __str__(self):
  338.         output = ""
  339.         for i in xrange(self.rows):
  340.             for j in xrange(self.cols):
  341.                 output += str(self.elements[i][j])
  342.             output += "\n"
  343.         return output
  344.  
  345.     def __repr__(self):
  346.         return "Matrix("+str(self.elements)+")"
  347.  
  348. class Vector(Matrix):
  349.     def __init__(self, elements):
  350.         # column vector
  351.         self.elements = elements
  352.         self.rows = len(elements)
  353.  
  354.     def dot(self, other):
  355.         if (type(other) != Vector):
  356.             assert(False), "cannot dot non-vectors"
  357.         def prod(a):
  358.             return a[0] * a[1]
  359.         return sum(map(prod,zip(self.elements,other.elements)))
  360.  
  361.     def norm(self):
  362.         return math.sqrt(self.dot(self))
  363.  
  364.     def __mul__(self, other):
  365.         if (not isNumber(other)):
  366.             assert(False), "cannot multiply"
  367.         return Vector(map(lambda x : other*x, self.elements))
  368.  
  369.     def __rmul__(self, other):
  370.         return self.__mul__(other)
  371.  
  372.     def __add__(self, other):
  373.         newElements = map(sum, zip(self.elements, other.elements))
  374.         return Vector(newElements)
  375.  
  376.     def __neg__(self):
  377.         return Vector(map(lambda x: -x, self.elements))
  378.  
  379.     def __str__(self):
  380.         return str(self.elements)
  381.  
  382. class ScreenSeg(object):
  383.     # keeps track of distance from center of screen and height
  384.     def __init__(self, cam, seg):
  385.         self.color = seg.color
  386.         # MUST be given a seg that is visible in the direction of the cam
  387.         # Seg pruning must be done beforehand!
  388.         # following is some linear algebra
  389.         v1 = Ray(cam.viewRay.eye, seg.p1)
  390.         v2 = Ray(cam.viewRay.eye, seg.p2)
  391.  
  392.         screenV1 = v1 * (cam.viewRay.norm()**2 / cam.viewRay.dot(v1))
  393.         screenV2 = v2 * (cam.viewRay.norm()**2 / cam.viewRay.dot(v2))
  394.  
  395.         self.x1 = screenV1.dot(cam.rightRay)
  396.         self.x2 = screenV2.dot(cam.rightRay)
  397.  
  398.         self.h1 = WALL_H * screenV1.norm() / v1.norm()
  399.         self.h2 = WALL_H * screenV2.norm() / v2.norm()
  400.  
  401.         self.shrink()
  402.  
  403.     def __str__(self):
  404.         (x1,h1,x2,h2) = (self.x1,self.h1,self.x2,self.h2)
  405.         return str((x1,h1,x2,h2))
  406.  
  407.     def shrink(self):
  408.         # required because tkinter cannot draw points too far from
  409.         # the visible portion of the canvas
  410.         # if abs(x),abs(h) < 1, it can be drawn
  411.         (x1, x2, h1, h2) = (self.x1, self.x2, self.h1, self.h2)
  412.         if ((abs(x1) > 1) or (abs(h1) > 1)):
  413.             (self.x1, self.h1) = shrinkScreenSeg(x1, h1, x2, h2)
  414.         if ((x2 > 1) or (h2 > 1)):
  415.             (self.x2, self.h2) = shrinkScreenSeg(x2, h2, x1, h1)
  416.  
  417.  
  418.        
  419.  
  420. class Intersection(object):
  421.     # represents an intersection of a ray and a wall, which can be either
  422.     # "normal" - ray.eye --- ray.target --- wall
  423.     #   this should usually obscure the wall
  424.     # "behind" - ray.eye --- wall --- ray.target
  425.     #   the wall is generally in front of the obstruction
  426.     # "backwards" - wall --- ray.eye --- ray.target
  427.     #   this generally does not obscure the wall
  428.     # "infinity"
  429.     #   the ray and wall are parallel
  430.     def __init__(self, point, kind):
  431.         self.point = point
  432.         self.kind = kind # str
  433.  
  434.     def __eq__(self, other):
  435.         return ((self.kind == other.kind) and (self.point == other.point))
  436.  
  437.     def __str__(self):
  438.         if (self.kind == "infinity"):
  439.             if (self.point.x == 0):
  440.                 return "(0,"+str(sign(self.point.y))+"inf)"
  441.             elif (self.point.y == 0):
  442.                 return "("+str(sign(self.point.x))+"inf,0)"
  443.         else:
  444.             return "(%f,%f)" % (self.point.x, self.point.y)
  445.  
  446.     def __repr__(self):
  447.         return "Intersection(%s,%s)" % (str(repr(self.point)), self.kind)
  448.  
  449.        
  450.  
  451.  
  452. ################################################################################
  453. ##### Line Intersection Functions ##############################################
  454. ################################################################################
  455.  
  456.  
  457.  
  458. def intersectRayAndRookSeg(ray, segment):
  459.     """Given a ray and a rook segment, returns their intersection.  The point
  460.    of intersection is not guaranteed to lie on the segment."""
  461.     if (segment.isHoriz):
  462.         return intersectRayAndHorizSegment(ray, segment)
  463.     elif (segment.isVert):
  464.         return intersectRayAndVertSegment(ray, segment)
  465.     else:
  466.         assert(False), "not a rook segment"
  467.  
  468. def intersectRayAndVertSegment(ray, segment):
  469.     """Given a ray and a "vert" segment, return an intersection, unless
  470.    the ray and segment are collinear, at which point this will return
  471.    the entire segment"""
  472.     ### NOTE:  The "eye" is forbidden from lying on a segment ###
  473.     # sanity check
  474.     if (not segment.isVert):
  475.         assert(False), "not a vertical segment"
  476.     if (ray.dx != 0):
  477.         # Note that segment.p1.x == segment.p2.x since it is vertical
  478.         # pointOnLine = k*(dx,dy) + eye.  This solves for k:
  479.         k = (segment.p1.x - ray.eye.x) / float(ray.dx)
  480.         yIntercept = k*ray.dy + ray.eye.y
  481.         intPoint = Point(segment.p1.x, yIntercept)
  482.         if (k < 0):
  483.             return Intersection(intPoint, "backwards")
  484.         elif (k < 1):
  485.             return Intersection(intPoint, "behind")
  486.         else:
  487.             return Intersection(intPoint, "normal")
  488.     else:
  489.         if (segment.p1.x == ray.eye.x):
  490.             # collinear!
  491.             return segment
  492.         else:
  493.             yIntercept = 1 if (ray.dy > 0) else -1
  494.             return Intersection(Point(0,yIntercept), "infinity")
  495.  
  496.  
  497.  
  498. def intersectRayAndHorizSegment(ray, segment):
  499.     """Given a ray and a "horiz" segment, return an intersection, unless
  500.    the ray and segment are collinear, at which point this will return
  501.    the entire segment"""
  502.     # sanity check
  503.     if (not segment.isHoriz):
  504.         assert(False), "not a horizontal segment"
  505.     if (ray.dy != 0):
  506.         # Note that segment.p1.y == segment.p2.y since it is horizontal
  507.         # pointOnLine = k*(dx,dy) + eye.  This solves for k:
  508.         k = (segment.p1.y - ray.eye.y) / float(ray.dy)
  509.         xIntercept = k*ray.dx + ray.eye.x
  510.         intPoint = Point(xIntercept, segment.p1.y)
  511.         if (k < 0):
  512.             return Intersection(intPoint, "backwards")
  513.         elif (k < 1):
  514.             return Intersection(intPoint, "behind")
  515.         else:
  516.             return Intersection(intPoint, "normal")
  517.     else:
  518.         if (segment.p1.y == ray.eye.y):
  519.             # collinear!
  520.             return segment
  521.         else:
  522.             xIntercept = 1 if (ray.dx > 0) else -1
  523.             return Intersection(Point(xIntercept,0), "infinity")
  524.  
  525. def intersectWalls(seg1, seg2):
  526.     """Given two orthogonal rook segs, returns the predicted
  527.    intersection (if they were to stretch into lines)"""
  528.     if (seg1.kind() == seg2.kind()):
  529.         assert(False), "segs not perpendicular"
  530.     if ((seg1.kind() == "other") or (seg2.kind() == "other")):
  531.         assert(False), "not rook segments"
  532.     elif (seg1.isHoriz):
  533.         return Point(seg2.p1.x, seg1.p1.y)
  534.     elif (seg1.isVert):
  535.         return Point(seg1.p1.x, seg2.p1.y)
  536.     else:
  537.         # should never happen
  538.         assert(False), "ERROR!"
  539.  
  540.  
  541. ################################################################################
  542. ##### Line Intersection Functions ##############################################
  543. ################################################################################
  544.  
  545.  
  546. def obstructViaIntersections(cross1, cross2, wall, seg):
  547.     """Given two intersections, a wall, and a segment, return a set containing the
  548.    portions on the segment.  The wall is what obscured the segment to produce
  549.    the two intersections (which are collinear with the seg)."""
  550.     # sanity check
  551.     if ((type(cross1) != Intersection) or (type(cross2) != Intersection)):
  552.         assert(False), "received non-intersections"
  553.     elif (type(seg) != Seg):
  554.         assert(False), "received non-segment"
  555.     # I recognize this is AWFUL style, but I can't think of another
  556.     #  way to handle these cases
  557.     # Most of these cases are really distinct
  558.     if (cross1.kind == "normal"):
  559.         if (cross2.kind == "normal"):
  560.             return normNormIntersect(cross1,cross2,wall,seg)
  561.         elif (cross2.kind == "behind"):
  562.             return normBehindIntersect(cross1,cross2,wall,seg)
  563.         elif (cross2.kind == "backwards"):
  564.             return normBackIntersect(cross1,cross2,wall,seg)
  565.         elif (cross2.kind == "infinity"):
  566.             return normInfIntersect(cross1,cross2,wall,seg)
  567.     elif (cross1.kind == "behind"):
  568.         if (cross2.kind == "normal"):
  569.             return normBehindIntersect(cross2,cross1,wall,seg)
  570.         elif (cross2.kind == "behind"):
  571.             return behindBehindIntersect(cross1,cross2,wall,seg)
  572.         elif (cross2.kind == "backwards"):
  573.             return behindBackIntersect(cross1,cross2,wall,seg)
  574.         elif (cross2.kind == "infinity"):
  575.             return behindInfIntersect(cross1,cross2,wall,seg)
  576.     elif (cross1.kind == "backwards"):
  577.         if (cross2.kind == "normal"):
  578.             return normBackIntersect(cross2,cross1,wall,seg)
  579.         elif (cross2.kind == "behind"):
  580.             return behindBackIntersect(cross2,cross1,wall,seg)
  581.         elif (cross2.kind == "backwards"):
  582.             return backBackIntersect(cross1,cross2,wall,seg)
  583.         elif (cross2.kind == "infinity"):
  584.             return backInfIntersect(cross1,cross2,wall,seg)
  585.     elif (cross1.kind == "infinity"):
  586.         if (cross2.kind == "normal"):
  587.             return normInfIntersect(cross2,cross1,wall,seg)
  588.         elif (cross2.kind == "behind"):
  589.             return behindInfIntersect(cross2,cross1,wall,seg)
  590.         elif (cross2.kind == "backwards"):
  591.             return backInfIntersect(cross2,cross1,wall,seg)
  592.         elif (cross2.kind == "infinity"):
  593.             return infInfIntersect(cross1,cross2,wall,seg)
  594.  
  595. def normNormIntersect(cross1,cross2,wall,seg):
  596.     # sanity check
  597.     if ((type(cross1) != Intersection) or (type(cross2) != Intersection)):
  598.         assert(False), "received non-intersections"
  599.     if (type(seg) != Seg):
  600.         assert(False), "received non-seg"
  601.     if (seg.isVert):
  602.         return normNormVertIntersect(cross1,cross2,seg)
  603.     elif (seg.isHoriz):
  604.         return normNormHorizIntersect(cross1,cross2,seg)
  605.  
  606. def normNormHorizIntersect(cross1,cross2,seg):
  607.     crossPoint1 = cross1.point
  608.     crossPoint2 = cross2.point
  609.     segSet = set([seg.p1, seg.p2])
  610.     crossSet = set([crossPoint1, crossPoint2])
  611.     (minSegPoint, maxSegPoint) = extremeX(segSet)
  612.     (minCrossPoint, maxCrossPoint) = extremeX(crossSet)
  613.     if (minCrossPoint.x <= minSegPoint.x):
  614.         if (maxCrossPoint.x < minSegPoint.x):
  615.             # nothing obscured
  616.             return set([seg])
  617.         elif (maxCrossPoint.x < maxSegPoint.x):
  618.             # obscured on left
  619.             return set([Seg(maxCrossPoint, maxSegPoint, seg.color)])
  620.         else:
  621.             # entirely obscured
  622.             return set()
  623.     elif (minCrossPoint.x < maxSegPoint.x):
  624.         if (maxCrossPoint.x < maxSegPoint.x):
  625.             # centrally obscured
  626.             return set([Seg(minSegPoint,minCrossPoint, seg.color),
  627.                         Seg(maxCrossPoint,maxSegPoint, seg.color)])
  628.         else:
  629.             # obscured on right
  630.             return set([Seg(minSegPoint,minCrossPoint, seg.color)])
  631.     else:
  632.         return set([seg])
  633.  
  634. def normNormVertIntersect(cross1,cross2,seg):
  635.     crossPoint1 = cross1.point
  636.     crossPoint2 = cross2.point
  637.     segSet = set([seg.p1, seg.p2])
  638.     crossSet = set([crossPoint1, crossPoint2])
  639.     (minSegPoint, maxSegPoint) = extremeY(segSet)
  640.     (minCrossPoint, maxCrossPoint) = extremeY(crossSet)
  641.     if (minCrossPoint.y <= minSegPoint.y):
  642.         if (maxCrossPoint.y < minSegPoint.y):
  643.             # nothing obscured
  644.             return set([seg])
  645.         elif (maxCrossPoint.y < maxSegPoint.y):
  646.             # obscured on top
  647.             return set([Seg(maxCrossPoint, maxSegPoint, seg.color)])
  648.         else:
  649.             # entirely obscured
  650.             return set()
  651.     elif (minCrossPoint.y < maxSegPoint.y):
  652.         if (maxCrossPoint.y < maxSegPoint.y):
  653.             # centrally obscured
  654.             return set([Seg(minSegPoint,minCrossPoint, seg.color),
  655.                         Seg(maxCrossPoint,maxSegPoint, seg.color)])
  656.         else:
  657.             # obscured on bottom
  658.             return set([Seg(minSegPoint,minCrossPoint, seg.color)])
  659.     else:
  660.         return set([seg])
  661.  
  662. def normBehindIntersect(cross,behindCross,wall,seg):
  663.     newCross = intersectWalls(wall,seg)
  664.     newIntersection = Intersection(newCross, "normal")
  665.     return normNormIntersect(cross, newIntersection, wall, seg)
  666.  
  667. def normBackIntersect(cross,backCross,wall,seg):
  668.     # we want to find the remaining portion of the seg
  669.     #  on the opposite side of the backCross
  670.     if (seg.isVert):
  671.         return normBackVertIntersect(cross,backCross,wall,seg)
  672.     elif (seg.isHoriz):
  673.         return normBackHorizIntersect(cross,backCross,wall,seg)
  674.     else:
  675.         assert(False), "seg should be vert or horiz"
  676.  
  677. def normBackVertIntersect(normCross, backCross, wall, seg):
  678.     cross = intersectWalls(wall, seg)
  679.     segSet = set([seg.p1, seg.p2])
  680.     (minSegPoint, maxSegPoint) = extremeY(segSet)
  681.     if (backCross.point.y < cross.y):
  682.         # want bottom half of line
  683.         botPoint = extremeY(set([minSegPoint, normCross.point]))[0] # min
  684.         topPoint = extremeY(set([maxSegPoint, normCross.point]))[0] # min
  685.         if (topPoint.y < botPoint.y):
  686.             return set()
  687.         else:
  688.             return set([Seg(botPoint, topPoint, seg.color)])
  689.     else:
  690.         # want top half of line
  691.         botPoint = extremeY(set([minSegPoint, normCross.point]))[1] # max
  692.         topPoint = extremeY(set([maxSegPoint, normCross.point]))[1] # max
  693.         if (topPoint.y < botPoint.y):
  694.             return set()
  695.         else:
  696.             return set([Seg(botPoint, topPoint, seg.color)])
  697.  
  698. def normBackHorizIntersect(normCross, backCross, wall, seg):
  699.     cross = intersectWalls(wall, seg)
  700.     segSet = set([seg.p1, seg.p2])
  701.     (minSegPoint, maxSegPoint) = extremeX(segSet)
  702.     if (backCross.point.x < cross.x):
  703.         # want left half of line
  704.         leftPoint = extremeX(set([minSegPoint, normCross.point]))[0] # min
  705.         rightPoint = extremeX(set([maxSegPoint, normCross.point]))[0] # min
  706.         if (rightPoint.x <= leftPoint.x):
  707.             return set()
  708.         else:
  709.             return set([Seg(leftPoint, rightPoint, seg.color)])
  710.     else:
  711.         # want right half of line
  712.         leftPoint = extremeX(set([minSegPoint, normCross.point]))[1] # max
  713.         rightPoint = extremeX(set([maxSegPoint, normCross.point]))[1] # max
  714.         if (rightPoint.x <= leftPoint.x):
  715.             return set()
  716.         else:
  717.             return set([Seg(leftPoint, rightPoint, seg.color)])
  718.    
  719.  
  720. def normInfIntersect(cross,infCross,wall,seg):
  721.     # we want to find the remaining portion of the seg
  722.     #  on the opposite side of the infCross
  723.     if (seg.isVert):
  724.         return normInfVertIntersect(cross,infCross,wall,seg)
  725.     elif (seg.isHoriz):
  726.         return normInfHorizIntersect(cross,infCross,wall,seg)
  727.     else:
  728.         assert(False), "seg should be vert or horiz"
  729.  
  730. def normInfVertIntersect(cross, infCross, wall, seg):
  731.     segSet = set([seg.p1, seg.p2])
  732.     (minSegPoint, maxSegPoint) = extremeY(segSet)
  733.     if (infCross.point.y > 0):
  734.         # obscured above cross
  735.         topPoint = extremeY(set([maxSegPoint, cross.point]))[0] # min
  736.         botPoint = extremeY(set([minSegPoint, cross.point]))[0] # min
  737.         if (topPoint.y < botPoint.y):
  738.             return set()
  739.         else:
  740.             return set([Seg(botPoint, topPoint, seg.color)])
  741.     elif (infCross.point.y < 0):
  742.         # obscured below cross
  743.         topPoint = extremeY(set([maxSegPoint, cross.point]))[1] # max
  744.         botPoint = extremeY(set([minSegPoint, cross.point]))[1] # max
  745.         if (topPoint.y < botPoint.y):
  746.             return set()
  747.         else:
  748.             return set([Seg(botPoint, topPoint, seg.color)])
  749.     else:
  750.         assert(False), "infCross should be vertical"
  751.  
  752.  
  753. def normInfHorizIntersect(cross, infCross, wall, seg):
  754.     segSet = set([seg.p1, seg.p2])
  755.     (minSegPoint, maxSegPoint) = extremeX(segSet)
  756.     if (infCross.point.x > 0):
  757.         # obscured to right of cross
  758.         rightPoint = extremeX(set([maxSegPoint, cross.point]))[0] # min
  759.         leftPoint = extremeX(set([minSegPoint, cross.point]))[0] # min
  760.         if (rightPoint.x < leftPoint.x):
  761.             return set()
  762.         else:
  763.             return set([Seg(leftPoint, rightPoint, seg.color)])
  764.     elif (infCross.point.x < 0):
  765.         # obscured to left of cross
  766.         rightPoint = extremeX(set([maxSegPoint, cross.point]))[1] # max
  767.         leftPoint = extremeX(set([minSegPoint, cross.point]))[1] # max
  768.         if (rightPoint.x < leftPoint.x):
  769.             return set()
  770.         else:
  771.             return set([Seg(leftPoint, rightPoint, seg.color)])
  772.     else:
  773.         assert(False), "infCross should be horizontal"
  774.  
  775. def behindBehindIntersect(behindCross1,behindCross2,wall,seg):
  776.     # the (obstructing) wall is behind the seg
  777.     # so nothing is obstructed
  778.     return set([seg])
  779.  
  780. def behindBackIntersect(behindCross,backCross,wall,seg):
  781.     # requires a picture to understand:
  782.     #  *** ###|
  783.     #  ***.###|
  784.     #  *** ###|
  785.     # if . is the eye and | represents the obstructing wall:
  786.     #  backCross must be in the * section
  787.     #  behindCross must be in the # section
  788.     # (The eye may not be in a seg)
  789.     # We must remove the part of the seg that extends beyond the wall
  790.     if (seg.isVert):
  791.         return behindBackVertIntersect(behindCross,backCross,wall,seg)
  792.     elif (seg.isHoriz):
  793.         return behindBackHorizIntersect(behindCross,backCross,wall,seg)
  794.     else:
  795.         assert(False), "seg should be vert or horiz"
  796.  
  797. def behindBackVertIntersect(behindCross, backCross, wall, seg):
  798.     newCross = intersectWalls(wall, seg)
  799.     crossSet = set([newCross, behindCross.point, backCross.point])
  800.     (minCrossPoint, maxCrossPoint) = extremeY(crossSet)
  801.     if (wall.p1.y > behindCross.point.y):
  802.         # wall crosses above
  803.         # (could choose backCross, also)
  804.         # quick check
  805.         (botSegPoint,topSegPoint) = extremeY(set([seg.p1,seg.p2]))
  806.         topPoint = extremeY(set([topSegPoint, newCross]))[0] # min
  807.         if (botSegPoint.y >= topPoint.y):
  808.             return set()
  809.         else:
  810.             return set([Seg(botSegPoint, topPoint, seg.color)])
  811.     else:
  812.         (botSegPoint,topSegPoint) = extremeY(set([seg.p1,seg.p2]))
  813.         botPoint = extremeY(set([botSegPoint, newCross]))[1] # max
  814.         if (topSegPoint.y <= botPoint.y):
  815.             return set()
  816.         else:
  817.             return set([Seg(botPoint, topSegPoint, seg.color)])
  818.  
  819.  
  820. def behindBackHorizIntersect(behindCross, backCross, wall, seg):
  821.     newCross = intersectWalls(wall, seg)
  822.     crossSet = set([newCross, behindCross.point, backCross.point])
  823.     (minCrossPoint, maxCrossPoint) = extremeX(crossSet)
  824.     if (wall.p1.x > behindCross.point.x):
  825.         # wall crosses to right
  826.         # (could choose backCross, also)
  827.         # quick check
  828.         (botSegPoint,topSegPoint) = extremeX(set([seg.p1,seg.p2]))
  829.         topPoint = extremeX(set([topSegPoint, newCross]))[0] # min
  830.         if (botSegPoint.x >= topPoint.x):
  831.             return set()
  832.         else:
  833.             return set([Seg(botSegPoint, topPoint, seg.color)])
  834.     else:
  835.         (botSegPoint,topSegPoint) = extremeX(set([seg.p1,seg.p2]))
  836.         botPoint = extremeX(set([botSegPoint, newCross]))[1] # max
  837.         if (topSegPoint.x <= botPoint.x):
  838.             return set()
  839.         else:
  840.             return set([Seg(botPoint, topSegPoint, seg.color)])
  841.  
  842.  
  843.  
  844. def behindInfIntersect(behindCross,infCross,wall,seg):
  845.     # requires a picture:
  846.     #  .###|
  847.     #  *###|
  848.     #  *###|
  849.     # the infCross must be in the * section
  850.     # the behindCross must be in the * section
  851.     # any portion of the segment that extends beyond the wall is obscured
  852.     #  just like with the behindBackIntersect
  853.     if (seg.isVert):
  854.         return behindInfVertIntersect(behindCross,infCross,wall,seg)
  855.     elif (seg.isHoriz):
  856.         return behindInfHorizIntersect(behindCross,infCross,wall,seg)
  857.     else:
  858.         assert(False), "seg should be vert or horiz"
  859.  
  860.  
  861. def behindInfVertIntersect(behindCross,infCross,wall,seg):
  862.     segPointSet = set([seg.p1, seg.p2])
  863.     (minSegPoint, maxSegPoint) = extremeY(segPointSet)
  864.     cross = intersectWalls(wall,seg)
  865.     if (infCross.point.y > 0):
  866.         # wall above eye
  867.         topPoint = extremeY(set([maxSegPoint, cross]))[0] # min
  868.         botPoint = extremeY(set([minSegPoint, cross]))[0] # min
  869.         if (topPoint.y < botPoint.y):
  870.             return set()
  871.         else:
  872.             return set([Seg(botPoint, topPoint, seg.color)])
  873.     elif (infCross.point.y < 0):
  874.         # wall below eye
  875.         topPoint = extremeY(set([maxSegPoint, cross]))[1] # max
  876.         botPoint = extremeY(set([minSegPoint, cross]))[1] # max
  877.         if (topPoint.y < botPoint.y):
  878.             return set()
  879.         else:
  880.             return set([Seg(botPoint, topPoint, seg.color)])
  881.     else:
  882.         assert(False), "infCross should be vertical"
  883.        
  884.  
  885. def behindInfHorizIntersect(behindCross,infCross,wall,seg):
  886.     segPointSet = set([seg.p1, seg.p2])
  887.     (minSegPoint, maxSegPoint) = extremeX(segPointSet)
  888.     cross = intersectWalls(wall,seg)
  889.     if (infCross.point.x > 0):
  890.         # wall to right of eye
  891.         leftPoint = extremeX(set([minSegPoint, cross]))[0] # min
  892.         rightPoint = extremeX(set([maxSegPoint, cross]))[0] # min
  893.         if (rightPoint.x < leftPoint.x):
  894.             return set()
  895.         else:
  896.             return set([Seg(leftPoint, rightPoint, seg.color)])
  897.     elif (infCross.point.x < 0):
  898.         # wall to left of eye
  899.         leftPoint = extremeX(set([minSegPoint, cross]))[1] # max
  900.         rightPoint = extremeX(set([maxSegPoint, cross]))[1] # max
  901.         if (rightPoint.x < leftPoint.x):
  902.             return set()
  903.         else:
  904.             return set([Seg(leftPoint, rightPoint, seg.color)])
  905.     else:
  906.         assert(False), "infCross should be horizontal"
  907.  
  908. def backBackIntersect(backCross1,backCross2,wall,seg):
  909.     return set([seg])
  910.            
  911. def backInfIntersect(backCross,infCross,wall,seg):
  912.     return set([seg])
  913.  
  914. def infInfIntersect(infCross1,infCross2,wall,seg):
  915.     # eye is collinear with wall, which is parallel to seg
  916.     return set([seg])
  917.  
  918.  
  919. ################################################################################
  920. ##### Total Visibility of a Segment ############################################
  921. ################################################################################
  922.  
  923. def obstructSeg(eye, wall, seg):
  924.     """Given an eye, a certain seg, and an (obstructing) wall, this returns
  925.    the remaining visible portion of the seg as a set of segments (or an empty
  926.    set)."""
  927.     ray1 = Ray(eye, wall.p1)
  928.     ray2 = Ray(eye, wall.p2)
  929.     cross1 = intersectRayAndRookSeg(ray1, seg)
  930.     cross2 = intersectRayAndRookSeg(ray2, seg)
  931.     if ((type(cross1) == Seg) or (type(cross2) == Seg)):
  932.         # something obscured entire segment
  933.         # NOTE: There is a small side effect, since
  934.         # the entire seg is returned even if the obstruction lies behind
  935.         # however, the seg must be viewed straight on for this to happen
  936.         #, so in the 3D case, it doesn't matter
  937.         return set()
  938.     return obstructViaIntersections(cross1, cross2, wall, seg)
  939.  
  940. def obstructSegViaSegSet(eye, segSet, seg):
  941.     """Given an eye, a certain seg, and a set of other segs, this returns the
  942.    remaining visible portion of the specific seg when obstructed by the whole
  943.    set."""
  944.     # sanity check
  945.     if (type(seg) != Seg): assert(False), "seg not of type Seg"
  946.     if (type(segSet) != set): assert(False), "segSet not of type set"
  947.     if (type(eye) != Point): assert(False), "eye not a Point"
  948.     remainingPieces = set([seg])
  949.     newPieces = set()
  950.     for wall in segSet:
  951.         for piece in remainingPieces:
  952.             newPieces = newPieces | obstructSeg(eye, wall, piece) # union
  953.         remainingPieces = newPieces
  954.         newPieces = set()
  955.     return remainingPieces
  956.  
  957.  
  958. def obstructSegs(eye, segSet):
  959.     """Given an eye and a set of segments, this returns the visible portions
  960.    (as a set) of each segment."""
  961.     visible = set()
  962.     for seg in segSet:
  963.         otherSegs = segSet - set([seg])
  964.         visible = visible.union(obstructSegViaSegSet(eye, otherSegs, seg))
  965.     return visible
  966.  
  967.  
  968. ################################################################################
  969. ##### Camera Class #############################################################
  970. ################################################################################
  971.  
  972. class Camera(object):
  973.     def __init__(self, viewRay):
  974.         if (type(viewRay) != Ray):
  975.             assert(False), "Camera requires Ray"
  976.         self.viewRay = viewRay
  977.         self.rightRay = viewRay.rotate(-math.pi/2)
  978.         self.height = CAM_HEIGHT
  979.  
  980.     def rotate(self, angle):
  981.         # angle in radians
  982.         viewRay = self.viewRay
  983.         self.viewRay = self.viewRay.rotate(angle)
  984.         self.rightRay = self.rightRay.rotate(angle)
  985.  
  986.     def translate(self, vector):
  987.         newX = self.viewRay.eye.x + vector.elements[0]
  988.         newY = self.viewRay.eye.y + vector.elements[1]
  989.         newEye = Point(newX, newY)
  990.         newTargetX = self.viewRay.target.x + vector.elements[0]
  991.         newTargetY = self.viewRay.target.y + vector.elements[1]
  992.         newTarget = Point(newTargetX, newTargetY)
  993.         newRightX = self.rightRay.target.x + vector.elements[0]
  994.         newRightY = self.rightRay.target.y + vector.elements[1]
  995.         newRightTarget = Point(newRightX, newRightY)
  996.         self.viewRay = Ray(newEye, newTarget)
  997.         self.rightRay = Ray(newEye, newRightTarget)
  998.        
  999.  
  1000. ################################################################################
  1001. ##### Maze Class ###############################################################
  1002. ################################################################################
  1003.  
  1004. class Maze(object):
  1005.     def __init__(self, rows, cols):
  1006.         (self.rows, self.cols) = (rows, cols)
  1007.         self.initCells()
  1008.         self.initPoints()
  1009.         self.initSegs()
  1010.         self.makeMaze()
  1011.  
  1012.     def initCells(self):
  1013.         (rows, cols) = (self.rows, self.cols)
  1014.         # more points than cells
  1015.         cRows = rows - 1
  1016.         cCols = cols - 1
  1017.         self.cells = [[i+cCols*j for i in xrange(cCols)] for j in xrange(cRows)]
  1018.  
  1019.     def initCellsAsOne(self):
  1020.         (rows, cols) = (self.rows, self.cols)
  1021.         # more points than cells
  1022.         cRows = rows - 1
  1023.         cCols = cols - 1
  1024.         self.cells = [[1]*cCols for i in xrange(cRows)]
  1025.  
  1026.     def initPoints(self):
  1027.         (rows, cols) = (self.rows, self.cols)
  1028.         self.points = [[0]*cols for i in xrange(rows)]
  1029.         for row in xrange(rows):
  1030.             for col in xrange(cols):
  1031.                 self.points[row][col] = Point(row, col)
  1032.  
  1033.     def initSegs(self):
  1034.         # we start with all possible segments
  1035.         (rows, cols) = (self.rows, self.cols)
  1036.         self.segs = list()
  1037.         for row in xrange(rows):
  1038.             for col in xrange(cols):
  1039.                 curPoint = Point(row,col)
  1040.                 color = makeColor(row, col, rows, cols)
  1041.                 if (row + 1 < rows):
  1042.                     nextPoint = Point(row+1,col)
  1043.                     self.segs.append(Seg(curPoint, nextPoint, color))
  1044.                 if (col + 1 < cols):
  1045.                     nextPoint = Point(row,col+1)
  1046.                     self.segs.append(Seg(curPoint, nextPoint, color))
  1047.  
  1048.     def removeSeg(self, seg, cellVal1, cellVal2):
  1049.         if (seg in self.segs):
  1050.             self.segs.remove(seg)
  1051.         self.renameCells(cellVal1, cellVal2)
  1052.  
  1053.     def renameCells(self, cellVal1, cellVal2):
  1054.         (cRows, cCols) = (self.rows - 1, self.cols - 1)
  1055.         (fromVal, toVal) = (max(cellVal1, cellVal2), min(cellVal1, cellVal2))
  1056.         for row in xrange(cRows):
  1057.             for col in xrange(cCols):
  1058.                 if (self.cells[row][col] == fromVal):
  1059.                     self.cells[row][col] = toVal
  1060.  
  1061.     def isFinishedMaze(self):
  1062.         (cRows, cCols) = (self.rows - 1, self.cols - 1)
  1063.         for row in xrange(cRows):
  1064.             for col in xrange(cCols):
  1065.                 if (self.cells[row][col] != 0):
  1066.                     return False
  1067.         return True
  1068.            
  1069.  
  1070.     def makeMaze(self):
  1071.         # I am borrowing heavily from the algorithm used here:
  1072.         # kosbie.net/cmu/fall-12/15-112/handouts/notes-recursion/mazeSolver.py
  1073.         (rows, cols) = (self.rows, self.cols)
  1074.         (cRows, cCols) = (rows-1, cols-1)
  1075.         while (not self.isFinishedMaze()):
  1076.             cRow = random.randint(0, cRows-1)
  1077.             cCol = random.randint(0, cCols-1)
  1078.             curCell = self.cells[cRow][cCol]
  1079.             if flipCoin(): # try to go east
  1080.                 if (cCol == cCols - 1): continue # at edge
  1081.                 targetCell = self.cells[cRow][cCol + 1]
  1082.                 dividingSeg = Seg(Point(cRow,cCol+1),
  1083.                                   Point(cRow+1,cCol+1))
  1084.                 if (curCell == targetCell):
  1085.                     if (dividingSeg in self.segs):
  1086.                         if (smallChance()):
  1087.                             self.removeSeg(dividingSeg, curCell, targetCell)
  1088.                 else:
  1089.                     self.removeSeg(dividingSeg, curCell, targetCell)
  1090.             else: # try to go north
  1091.                 if (cRow == cRows - 1): continue # at edge
  1092.                 targetCell = self.cells[cRow+1][cCol]
  1093.                 dividingSeg = Seg(Point(cRow+1,cCol),
  1094.                                   Point(cRow+1,cCol+1))
  1095.                 if (curCell == targetCell):
  1096.                     continue
  1097.                 else:
  1098.                     self.removeSeg(dividingSeg, curCell, targetCell)
  1099.  
  1100.     def deadCornerCell(self, row, col, dir):
  1101.         (rows, cols) = (self.rows, self.cols)
  1102.         (cRows, cCols) = (rows - 1, cols - 1)
  1103.         if (dir == "UL"):
  1104.             # checking to the upper left
  1105.             # if shielded by dead cells to the bottom right, this is dead
  1106.             rightCell = self.cells[row][col+1]
  1107.             downCell = self.cells[row-1][col]
  1108.             return (((self.hasSeg(row, col, "right")) or (rightCell == 0)) and
  1109.                     ((self.hasSeg(row, col, "down")) or (downCell == 0)))
  1110.         elif (dir == "UR"):
  1111.             leftCell = self.cells[row][col-1]
  1112.             downCell = self.cells[row-1][col]
  1113.             return (((self.hasSeg(row, col, "left")) or (leftCell == 0)) and
  1114.                     ((self.hasSeg(row, col, "down")) or (downCell == 0)))
  1115.         elif (dir == "DL"):
  1116.             rightCell = self.cells[row][col+1]
  1117.             upCell = self.cells[row+1][col]
  1118.             return (((self.hasSeg(row, col, "right")) or (rightCell == 0)) and
  1119.                     ((self.hasSeg(row, col, "up")) or (upCell == 0)))
  1120.         elif (dir == "DR"):
  1121.             leftCell = self.cells[row][col-1]
  1122.             upCell = self.cells[row+1][col]
  1123.             return (((self.hasSeg(row, col, "left")) or (leftCell == 0)) and
  1124.                     ((self.hasSeg(row, col, "up")) or (upCell == 0)))
  1125.         else:
  1126.             assert(False), "not a direction"
  1127.  
  1128.  
  1129.  
  1130.         return False
  1131.  
  1132.     def cullCorners(self, eye):
  1133.         eyeRow = int(math.floor(eye.y))
  1134.         eyeCol = int(math.floor(eye.x))
  1135.         (rows, cols) = (self.rows, self.cols)
  1136.         (cRows, cCols) = (rows - 1, cols - 1)
  1137.         # xranges are reversed so that we check progressively
  1138.         # further from the eye (since this process "cascades")
  1139.         culledFlag = False
  1140.         # bottom left
  1141.         if ((eyeRow != 0) and (eyeCol != 0)):
  1142.             for row in xrange(eyeRow-1, -1, -1):
  1143.                 for col in xrange(eyeCol-1, -1, -1):
  1144.                     if (self.deadCornerCell(row, col, "DL")):
  1145.                         if (self.cells[row][col] != 0):
  1146.                             self.cells[row][col] = 0 # dead
  1147.                             culledFlag = True
  1148.         # bottom right
  1149.         if ((eyeRow != 0) and (eyeCol != cCols)):
  1150.             for row in xrange(eyeRow-1, -1, -1):
  1151.                 for col in xrange(eyeCol+1, cCols):
  1152.                     if (self.deadCornerCell(row, col, "DR")):
  1153.                         if (self.cells[row][col] != 0):
  1154.                             self.cells[row][col] = 0 # dead
  1155.                             culledFlag = True
  1156.         # top left
  1157.         if ((eyeRow != cRows) and (eyeCol != 0)):
  1158.             for row in xrange(eyeRow+1, cRows):
  1159.                 for col in xrange(eyeCol-1, -1, -1):
  1160.                     if (self.deadCornerCell(row, col, "UL")):
  1161.                         if (self.cells[row][col] != 0):
  1162.                             self.cells[row][col] = 0 # dead
  1163.                             culledFlag = True
  1164.         # top right
  1165.         if ((eyeRow != cRows) and (eyeCol != cCols)):
  1166.             for row in xrange(eyeRow+1, cRows):
  1167.                 for col in xrange(eyeCol+1, cCols):
  1168.                     if (self.deadCornerCell(row, col, "UR")):
  1169.                         if (self.cells[row][col] != 0):
  1170.                             self.cells[row][col] = 0 # dead
  1171.                             culledFlag = True
  1172.         return culledFlag # something was deleted
  1173.                
  1174.  
  1175.        
  1176.     def removeDeadSandwichedSegs(self):
  1177.         (rows, cols) = (self.rows, self.cols)
  1178.         (cRows, cCols) = (rows - 1, cols - 1)
  1179.         # check right
  1180.         for row in xrange(cRows):
  1181.             for col in xrange(cCols - 1):
  1182.                 if (self.cells[row][col] == self.cells[row][col+1] == 0):
  1183.                     deadSeg = Seg(Point(col+1, row), Point(col+1, row+1))
  1184.                     if (deadSeg in self.checkSegs):
  1185.                         self.checkSegs.remove(deadSeg)
  1186.         # check far right
  1187.         for row in xrange(cRows):
  1188.             if (self.cells[row][cCols-1] == 0):
  1189.                 deadSeg = Seg(Point(cCols+1, row), Point(cCols+1, row+1))
  1190.                 if (deadSeg in self.checkSegs):
  1191.                     self.checkSegs.remove(deadSeg)
  1192.         # check up
  1193.         for row in xrange(cRows - 1):
  1194.             for col in xrange(cCols):
  1195.                 if (self.cells[row][col] == self.cells[row+1][col] == 0):
  1196.                     deadSeg = Seg(Point(col, row+1), Point(col+1, row+1))
  1197.                     if (deadSeg in self.checkSegs):
  1198.                         self.checkSegs.remove(deadSeg)
  1199.         # check far top
  1200.         for col in xrange(cCols):
  1201.             if (self.cells[cRows-1][col] == 0):
  1202.                 deadSeg = Seg(Point(col, cRows+1), Point(col+1, cRows+1))
  1203.                 if (deadSeg in self.checkSegs):
  1204.                     self.checkSegs.remove(deadSeg)
  1205.         return None
  1206.                        
  1207.                    
  1208.  
  1209.     def hasSeg(self, row, col, dir):
  1210.         y = row
  1211.         x = col
  1212.         if (dir == "left"):
  1213.             return (Seg(Point(x, y), Point(x, y+1)) in self.checkSegs)
  1214.         elif (dir == "right"):
  1215.             return (Seg(Point(x+1,y), Point(x+1,y+1)) in self.checkSegs)
  1216.         elif (dir == "up"):
  1217.             return (Seg(Point(x, y+1), Point(x+1, y+1)) in self.checkSegs)
  1218.         elif (dir == "down"):
  1219.             return (Seg(Point(x, y), Point(x+1, y)) in self.checkSegs)
  1220.         else:
  1221.             assert(False), "not a direction"
  1222.  
  1223.     def deleteCellsInDir(self, delRow, delCol, dir):
  1224.         # destructive function
  1225.         (rows, cols) = (self.rows, self.cols)
  1226.         (cRows, cCols) = (rows - 1, cols - 1)
  1227.         if ((delRow == cRows) or (delRow < 0) or
  1228.             (delCol == cCols) or (delCol < 0)):
  1229.             # out of bounds
  1230.             return None
  1231.         if (dir == "left"):
  1232.             for col in xrange(0, delCol+1):
  1233.                 self.cells[delRow][col] = 0
  1234.         elif (dir == "right"):
  1235.             for col in xrange(delCol, cCols):
  1236.                 self.cells[delRow][col] = 0
  1237.         elif (dir == "down"):
  1238.             for row in xrange(0, delRow+1):
  1239.                 self.cells[row][delCol] = 0
  1240.         elif (dir == "up"):
  1241.             for row in xrange(delRow, cRows):
  1242.                 self.cells[row][delCol] = 0
  1243.         else:
  1244.             assert(False), "not a direction"
  1245.  
  1246.  
  1247.     def cullSegs(self, eye):
  1248.         # only return segs which could possibly be visible to reduce
  1249.         # render time
  1250.         # mark all cells as 1 (alive)
  1251.         # we will mark cells as 0 (dead) if they cannot possible be seen
  1252.         # walls sandwiched between dead cells are invisible and will be culled
  1253.         eyeRow = int(math.floor(eye.y))
  1254.         eyeCol = int(math.floor(eye.x))
  1255.         (rows, cols) = (self.rows, self.cols)
  1256.         (cRows, cCols) = (rows - 1, cols - 1)
  1257.         self.initCellsAsOne()
  1258.         self.checkSegs = copy.copy(self.segs)
  1259.         for col in xrange(eyeCol, cCols):
  1260.             if self.hasSeg(eyeRow, col, "right"):
  1261.                 self.deleteCellsInDir(eyeRow, col+1, "right")
  1262.                 break
  1263.         for col in xrange(eyeCol, -1, -1):
  1264.             if self.hasSeg(eyeRow, col, "left"):
  1265.                 self.deleteCellsInDir(eyeRow, col-1, "left")
  1266.                 break
  1267.         for row in xrange(eyeRow, cRows):
  1268.             if self.hasSeg(row, eyeCol, "up"):
  1269.                 self.deleteCellsInDir(row+1, eyeCol, "up")
  1270.                 break
  1271.         for row in xrange(eyeRow, -1, -1):
  1272.             if self.hasSeg(row, eyeCol, "down"):
  1273.                 self.deleteCellsInDir(row-1, eyeCol, "down")
  1274.                 break
  1275.         while(self.cullCorners(eye)):
  1276.             # cullCorners will remove cells invisible by a corner
  1277.             # it will return true if something was removed
  1278.             pass
  1279.         self.removeDeadSandwichedSegs()
  1280.         # will remove segs sandwiched between dead cells
  1281.         return set(self.checkSegs)
  1282.  
  1283.  
  1284.        
  1285.  
  1286.  
  1287.  
  1288.  
  1289.  
  1290.  
  1291.  
  1292. ################################################################################
  1293. ##### Animation Class ##########################################################
  1294. ################################################################################
  1295.  
  1296.  
  1297. # taken from jbahr-hw9.py
  1298. class Animation(object):
  1299.     def __init__(self, width=500, height=300):
  1300.         self.root = Tk()
  1301.         self.width = width
  1302.         self.height = height
  1303.         self.canvas = Canvas(self.root, width=self.width, height=self.height)
  1304.         self.canvas.pack()
  1305.         self.init()
  1306.         self.root.bind("<KeyPress>", self.keyPressed)
  1307.         self.root.bind("<KeyRelease>", self.keyReleased)
  1308.         self.root.bind("<Button-1>", self.mousePressed)
  1309.  
  1310.     def run(self):
  1311.         self.timerFired()
  1312.         self.root.mainloop()
  1313.  
  1314.     def init(self):
  1315.         pass
  1316.  
  1317.     def redrawAll(self):
  1318.         pass
  1319.  
  1320.     def keyPressed(self, event):
  1321.         pass
  1322.  
  1323.     def keyReleased(self, event):
  1324.         pass
  1325.  
  1326.     def mousePressed(self, event):
  1327.         pass
  1328.  
  1329.     def timerFired(self):
  1330.         self.redrawAll()
  1331.         delay = 100 # ms
  1332.         self.canvas.after(delay, self.timerFired)
  1333.  
  1334.  
  1335. ################################################################################
  1336. ##### MazeGame Animation Class #################################################
  1337. ################################################################################
  1338.  
  1339.  
  1340. class MazeGame(Animation):
  1341.     def __init__(self, mazeSize, width=700, height=500):
  1342.         self.mazeRows = mazeSize
  1343.         self.mazeCols = mazeSize
  1344.         self.mode = "3D"
  1345.         super(MazeGame, self).__init__(width, height)
  1346.         self.root.resizable(width=0, height=0) # non-resizable
  1347.  
  1348. ######################
  1349. ####### Model ########
  1350. ######################
  1351.  
  1352.     def init(self):
  1353.         self.isGameOver = False
  1354.         self.isHelp = True
  1355.         self.initMaze()
  1356.         self.initCamera()
  1357.  
  1358.     def initCamera(self):
  1359.         self.speed = 0.08
  1360.         self.rotateSpeed = math.pi/32
  1361.         self.cameraLength = CAM_LENGTH
  1362.         self.cameraSep = CAM_SEP
  1363.         # we start closest to (0,0)
  1364.         # facing in the x direction
  1365.         # check if facing wall
  1366.         startPoint = Point(0.5, 0.5)
  1367.         if (Seg(Point(0,1),Point(1,1)) in self.maze.segs):
  1368.             secondCamStart = Point(0.5, 0.5 - self.cameraSep)
  1369.             secondCamView = Point(0.5 + self.cameraLength, 0.5 - self.cameraSep)
  1370.             viewPoint = Point(0.5 + self.cameraLength, 0.5)
  1371.         else:
  1372.             secondCamStart = Point(0.5 + self.cameraSep, 0.5)
  1373.             secondCamView = Point(0.5 + self.cameraSep, 0.5 + self.cameraLength)
  1374.             viewPoint = Point(0.5, 0.5 + self.cameraLength)
  1375.         self.camera = Camera(Ray(startPoint, viewPoint))
  1376.         self.secondCamera = Camera(Ray(secondCamStart, secondCamView))
  1377.         self.cameraVel = 0
  1378.         self.sideCameraVel = 0
  1379.         self.cameraRotVel = 0
  1380.  
  1381.     def initMaze(self):
  1382.         print "Generating random maze..."
  1383.         self.maze = Maze(self.mazeRows, self.mazeCols)
  1384.         print "Finished generating maze!"
  1385.  
  1386.  
  1387. ######################
  1388. ##### Controller #####
  1389. ######################
  1390.  
  1391.     def timerFired(self):
  1392.         if (self.mode == "3D"):
  1393.             self.screenSegs = set()
  1394.             self.visibleSegs = set()
  1395.             self.circularVisibleSegs = set()
  1396.             (self.visibleSegs,
  1397.              self.circularVisibleSegs) = self.firstPersonVisibleSegs(self.camera)
  1398.             self.projectVisibleSegsToScreen(self.camera,
  1399.                                             self.screenSegs,
  1400.                                             self.visibleSegs)
  1401.         elif (self.mode == "3DG"):
  1402.             self.screenSegs = set()
  1403.             self.secScreenSegs = set()
  1404.             self.visibleSegs = set()
  1405.             self.secVisibleSegs = set()
  1406.             self.circularVisibleSegs = set()
  1407.             self.secCircularVisibleSegs = set()
  1408.             (self.visibleSegs, self.circularVisibleSegs) = \
  1409.                                         self.firstPersonVisibleSegs(self.camera)
  1410.             (self.secVisibleSegs, self.secCircularVisibleSegs) = \
  1411.                     self.firstPersonVisibleSegs(self.secondCamera)
  1412.             self.projectVisibleSegsToScreen(self.camera,
  1413.                                             self.screenSegs,
  1414.                                             self.visibleSegs)
  1415.             self.projectVisibleSegsToScreen(self.secondCamera,
  1416.                                             self.secScreenSegs,
  1417.                                             self.secVisibleSegs)
  1418.         elif (self.mode == "2D"):
  1419.             self.topDownVisibleSegs()
  1420.         self.updateCamera()
  1421.         self.isWin()
  1422.         self.redrawAll()
  1423.         delay = 40 # ms
  1424.         self.canvas.after(delay, self.timerFired)
  1425.  
  1426.     def topDownVisibleSegs(self):
  1427.         eye = self.camera.viewRay.eye
  1428.         possibleSegs = self.maze.cullSegs(eye)
  1429.         self.circularVisibleSegs = obstructSegs(eye, possibleSegs)
  1430.  
  1431.     def firstPersonVisibleSegs(self, cam):
  1432.         # check if each seg in visibleSegs is within 90 degrees of cam.viewRay
  1433.         # given visSegs to store visibleSegs and circSegs to store
  1434.         # circularly visible segs
  1435.         visSegs = set()
  1436.         circSegs = set()
  1437.         eye = cam.viewRay.eye
  1438.         possibleSegs = self.maze.cullSegs(eye)
  1439.         circSegs = obstructSegs(eye, possibleSegs) # visible in 360
  1440.         visSegs = set()
  1441.         for seg in circSegs:
  1442.             ray1 = Ray(eye, seg.p1)
  1443.             ray2 = Ray(eye, seg.p2)
  1444.             angle1 = abs(ray1.angle(cam.viewRay))
  1445.             angle2 = abs(ray2.angle(cam.viewRay))
  1446.             screenEye = cam.viewRay.target
  1447.             screenDir = (cam.rightRay.dx, cam.rightRay.dy)
  1448.             rightPoint = Point(screenEye.x+screenDir[0], screenEye.y+screenDir[1])
  1449.             screenRay = Ray(screenEye, rightPoint)
  1450.             viewRay = cam.viewRay
  1451.             if ((angle1 < FOV) and (angle2 < FOV)):
  1452.                 visSegs.add(seg)
  1453.             elif ((angle1 >= FOV) and (angle2 < FOV)):
  1454.                 newIntersect = intersectRayAndRookSeg(screenRay, seg)
  1455.                 newPoint = newIntersect.point
  1456.                 # check for special case
  1457.                 if (0 < ray2.dot(viewRay)/viewRay.norm() < viewRay.norm()):
  1458.                     continue
  1459.                 else:
  1460.                     visSegs.add(Seg(newPoint, seg.p2, seg.color))
  1461.             elif ((angle1 < FOV) and (angle2 >= FOV)):
  1462.                 newIntersect = intersectRayAndRookSeg(screenRay, seg)
  1463.                 newPoint = newIntersect.point
  1464.                 # check for special case
  1465.                 if (0 < ray1.dot(viewRay)/viewRay.norm() < viewRay.norm()):
  1466.                     continue
  1467.                 else:
  1468.                     visSegs.add(Seg(seg.p1, newPoint, seg.color))
  1469.             else:
  1470.                 # seg is completely behind
  1471.                 continue
  1472.         return (visSegs, circSegs)
  1473.                
  1474.     def projectVisibleSegsToScreen(self, cam, screenSegs, visSegs):
  1475.         for seg in visSegs:
  1476.             screenSegs.add(ScreenSeg(cam, seg))
  1477.  
  1478.     def updateCamera(self):
  1479.         topDownModes = ["2D"]
  1480.         firstPersonModes = ["3D", "3DG"]
  1481.         if (self.mode in topDownModes):
  1482.             self.topDownUpdateCamera()
  1483.         elif (self.mode in firstPersonModes):
  1484.             self.firstPersonUpdateCamera()
  1485.         else:
  1486.             assert(False), "Not a valid mode"
  1487.  
  1488.  
  1489.     def topDownUpdateCamera(self):
  1490.         self.camera.rotate(self.cameraRotVel)
  1491.         self.secondCamera.rotate(self.cameraRotVel)
  1492.         self.camera.translate(self.cameraVel)
  1493.         self.secondCamera.translate(self.cameraVel)
  1494.         if not self.cameraIsLegal():
  1495.             # move back!
  1496.             self.camera.translate(- self.cameraVel)
  1497.             self.secondCamera.translate(- self.cameraVel)
  1498.  
  1499.  
  1500.     def firstPersonUpdateCamera(self):
  1501.         viewDir = Vector([self.camera.viewRay.dx, self.camera.viewRay.dy])
  1502.         rightDir = Vector([self.camera.rightRay.dx, self.camera.rightRay.dy])
  1503.         velocity = (self.cameraVel/viewDir.norm()) * viewDir
  1504.         sideVel = (self.sideCameraVel/rightDir.norm()) * rightDir
  1505.         newVel = (velocity + sideVel)
  1506.         if (newVel.norm() != 0):
  1507.             oldNorm = max(velocity.norm(), sideVel.norm())
  1508.             newVel = newVel * (oldNorm/newVel.norm())
  1509.         self.camera.rotate(self.cameraRotVel)
  1510.         self.secondCamera.rotate(self.cameraRotVel)
  1511.         self.camera.translate(newVel)
  1512.         self.secondCamera.translate(newVel)
  1513.         if not self.cameraIsLegal():
  1514.             # move back!
  1515.             self.camera.translate(- newVel)
  1516.             self.secondCamera.translate(- newVel)
  1517.  
  1518.  
  1519.     def cameraIsLegal(self):
  1520.         # check that camera is no more than 1.5*self.cameraLength
  1521.         # from any wall
  1522.         cam1 = self.camera
  1523.         cam2 = self.secondCamera
  1524.         for seg in self.circularVisibleSegs:
  1525.             if (seg.withinDist(cam1.viewRay.eye,1.2*self.cameraLength) or
  1526.                 (seg.withinDist(cam2.viewRay.eye, 1.2*self.cameraLength))):
  1527.                 return False
  1528.         return True
  1529.  
  1530.     def isWin(self):
  1531.         # if in last cell, game is won
  1532.         lastX = self.maze.cols - 1
  1533.         lastY = self.maze.rows - 1
  1534.         if ((abs(self.camera.viewRay.eye.x - lastX) < 1) and
  1535.             (abs(self.camera.viewRay.eye.y - lastY) < 1)):
  1536.             self.isGameOver = True
  1537.  
  1538.     def mousePressed(self, event):
  1539.         pass
  1540.  
  1541.     def keyPressed(self, event):
  1542.         firstPersonModes = ["3D", "3DG"]
  1543.         topDownModes = ["2D"]
  1544.         if (self.mode in firstPersonModes):
  1545.             self.firstPersonKeyPressed(event)
  1546.         elif (self.mode in topDownModes):
  1547.             self.topDownKeyPressed(event)
  1548.         else:
  1549.             assert(False), "not a valid mode"
  1550.         if (event.keysym == "h"):
  1551.             # toggle help screen
  1552.             self.isHelp = not self.isHelp
  1553.         else:
  1554.             self.isHelp = False
  1555.         if (event.keysym == "r"):
  1556.             self.mode = "3D"
  1557.             self.init()
  1558.             self.isHelp = False
  1559.             # restart
  1560.         if (event.keysym == "1"):
  1561.             self.mode = "2D"
  1562.             self.cameraVel = Vector([0,0])
  1563.         elif (event.keysym == "2"):
  1564.             self.mode = "3D"
  1565.             self.cameraVel = 0
  1566.             self.sideCameraVel = 0
  1567.         elif (event.keysym == "3"):
  1568.             self.mode = "3DG"
  1569.             self.cameraVel = 0
  1570.             self.sideCameraVel = 0
  1571.  
  1572.  
  1573.     def firstPersonKeyPressed(self, event):
  1574.         viewDir = Vector([self.camera.viewRay.dx, self.camera.viewRay.dy])
  1575.         if ((event.keysym == "w") or (event.keysym=="Up")):
  1576.             self.cameraVel = self.speed
  1577.         elif ((event.keysym == "s") or (event.keysym=="Down")):
  1578.             self.cameraVel = -self.speed
  1579.         elif ((event.keysym == "d") or (event.keysym=="Right")):
  1580.             # clockwise
  1581.             self.cameraRotVel = self.rotateSpeed
  1582.         elif ((event.keysym == "a") or (event.keysym=="Left")):
  1583.             # counter-clockwise
  1584.             self.cameraRotVel = - self.rotateSpeed
  1585.         elif ((event.keysym == "comma") or (event.keysym=="Prior")):
  1586.             # Prior is page up
  1587.             # sidestep left
  1588.             self.sideCameraVel = self.speed
  1589.         elif ((event.keysym == "period") or (event.keysym=="Next")):
  1590.             # Next is page down
  1591.             self.sideCameraVel = - self.speed
  1592.  
  1593.     def topDownKeyPressed(self, event):
  1594.         up = ["Up", "w"]
  1595.         down = ["Down", "s"]
  1596.         left = ["Left", "a"]
  1597.         right = ["Right", "d"]
  1598.         if (event.keysym in up):
  1599.             # up is down in TkInter
  1600.             self.cameraVel = self.speed * Vector([0,-1])
  1601.         elif (event.keysym in down):
  1602.             # up is down in TkInter
  1603.             self.cameraVel = self.speed * Vector([0,1])
  1604.         elif (event.keysym in right):
  1605.             self.cameraVel = self.speed * Vector([1,0])
  1606.         elif (event.keysym in left):
  1607.             self.cameraVel = self.speed * Vector([-1,0])
  1608.         # ensure no more rotation
  1609.         self.cameraRotVel = 0
  1610.  
  1611.     def keyReleased(self, event):
  1612.         firstPersonModes = ["3D", "3DG"]
  1613.         topDownModes = ["2D"]
  1614.         if (self.mode in firstPersonModes):
  1615.             return self.firstPersonKeyReleased(event)
  1616.         elif (self.mode in topDownModes):
  1617.             return self.topDownKeyReleased(event)
  1618.         else:
  1619.             assert(False), "not a valid mode"
  1620.  
  1621.     def firstPersonKeyReleased(self, event):
  1622.         translations = ["w", "s", "Up", "Down"]
  1623.         sideSteps = ["comma","period","Prior","Next"]
  1624.         rotations = ["a", "d", "Left", "Right"]
  1625.         if (event.keysym in translations):
  1626.             self.cameraVel = 0
  1627.         elif (event.keysym in sideSteps):
  1628.             self.sideCameraVel = 0
  1629.         elif (event.keysym in rotations):
  1630.             self.cameraRotVel = 0
  1631.  
  1632.     def topDownKeyReleased(self, event):
  1633.         translations = ["Up", "Down", "Left", "Right",
  1634.                         "w", "a", "s", "d"]
  1635.         if (event.keysym in translations):
  1636.             self.cameraVel = Vector([0,0])
  1637.  
  1638.  
  1639. ######################
  1640. ######## View ########
  1641. ######################
  1642.  
  1643.     def drawGameOver(self):
  1644.         cx = self.width/2
  1645.         cy = self.height/2
  1646.         self.canvas.create_text(cx, cy, text="You Won!",
  1647.                                 font="Helvetica 36 bold")
  1648.  
  1649.     def draw3DGGameOver(self):
  1650.         # If you find yourself on a system where Tkinter text
  1651.         # stippling works, then comment out:
  1652.         self.drawGameOver()
  1653.         # and uncomment the remainder of this function
  1654.         # (and install the dejavu font)
  1655. #        cxLeft = self.width * (49.5/100)
  1656. #        cxRight = self.width * (50.5/100)
  1657. #        cy = self.height/2
  1658. #        self.canvas.create_text(cxLeft, cy, text="You Win!",
  1659. #                                font=("dejavu sans light", 36),
  1660. #                                stipple="gray50",
  1661. #                                fill=None,
  1662. #                                offset="0,0")
  1663. #        self.canvas.create_text(cxRight, cy, text="You Win!",
  1664. #                                font=("dejavu sans light", 36),
  1665. #                                stipple="gray50",
  1666. #                                fill=hexColor(0,255,255),
  1667. #                                offset="0,1")
  1668.  
  1669.     def drawHelp(self):
  1670.         cx = self.width/2
  1671.         leftcx = self.width/3
  1672.         rightcx = (2*self.width)/3
  1673.         cy = self.height/2
  1674.         self.canvas.create_text(cx,cy*(2./9.),text="3D Maze!",
  1675.                                 font="Helvetica 28",fill="white")
  1676.         self.canvas.create_text(cx,cy/2,
  1677.                                 text="""Find the far corner (the white cell)
  1678. The maze will get greener""",
  1679.                                 font="Helvetica 24",fill="white",
  1680.                                 justify=CENTER)
  1681.         self.canvas.create_text(leftcx, cy, text="""
  1682.        To move
  1683.        To sidestep
  1684.        To switch to 2D mode
  1685.                           3D mode
  1686.                           3D with glasses
  1687.        To toggle help
  1688.        To restart""", font="Helvetica 18",fill="white")
  1689.         self.canvas.create_text(rightcx, cy, text="""
  1690.        WASD or arrow keys
  1691.        ,/. or PgUp/PgDown
  1692.        1
  1693.        2
  1694.        3
  1695.        h
  1696.        r""", font="Helvetica 18",fill="white")
  1697.  
  1698.        
  1699.  
  1700.  
  1701.     def redrawAll(self):
  1702.         self.canvas.delete(ALL)
  1703.         if (self.mode == "2D"):
  1704.             self.redraw2D()
  1705.         elif (self.mode == "3D"):
  1706.             self.redraw3D()
  1707.         elif (self.mode == "3DG"):
  1708.             self.redraw3DG()
  1709.         else:
  1710.             assert(False), "no valid mode"
  1711.         if (self.isHelp):
  1712.             self.drawHelp()
  1713.         elif (self.isGameOver):
  1714.             if (self.mode == "3DG"):
  1715.                 self.draw3DGGameOver()
  1716.             else:
  1717.                 self.drawGameOver()
  1718.  
  1719.     def redraw2D(self):
  1720.         eye = self.camera.viewRay.eye
  1721.         segs = self.circularVisibleSegs
  1722.         cx = self.width/2
  1723.         cy = self.height/2
  1724.         left = cx - (CELL_SIZE*(self.mazeCols - 1))/2
  1725.         top = cy - (CELL_SIZE*(self.mazeRows - 1))/2
  1726.         self.draw2DEye(left, top)
  1727.         for s in segs:
  1728.             self.canvas.create_line(left + CELL_SIZE*s.p1.x,
  1729.                                     top + CELL_SIZE*s.p1.y,
  1730.                                     left + CELL_SIZE*s.p2.x,
  1731.                                     top + CELL_SIZE*s.p2.y,
  1732.                                     fill=s.color, width=2)
  1733.         if (DEBUG):
  1734.             for s in self.maze.segs:
  1735.                 self.canvas.create_line(left + CELL_SIZE*s.p1.x,
  1736.                                         top + CELL_SIZE*s.p1.y,
  1737.                                         left + CELL_SIZE*s.p2.x,
  1738.                                         top + CELL_SIZE*s.p2.y,
  1739.                                         fill="black", width=1)
  1740.  
  1741.     def draw2DEye(self, left, top):
  1742.         eye = self.camera.viewRay.eye
  1743.         target = self.camera.viewRay.target
  1744.         x1 = left + CELL_SIZE*eye.x
  1745.         y1 = top + CELL_SIZE*eye.y
  1746.         x2 = left + CELL_SIZE*target.x
  1747.         y2 = top + CELL_SIZE*target.y
  1748.         self.canvas.create_line(x1, y1, x2, y2, arrow="last", fill="blue")
  1749.  
  1750.     def drawBackground(self):
  1751.         background = hexColor(255,255,255) # better for red/cyan anaglyph
  1752.         self.canvas.create_rectangle(0, 0, self.width, self.height,
  1753.                                      fill=background, width=0)
  1754.  
  1755.     def drawGround(self):
  1756.         brown = hexColor(123, 112, 0)
  1757.         #brown = hexColor(163, 130, 41) # alternative
  1758.         cy = self.height/2
  1759.         self.canvas.create_rectangle(0, cy, self.width, self.height,
  1760.                                      fill=brown, width=0)
  1761.  
  1762.  
  1763.     def drawSky(self):
  1764.         #blue = hexColor(130,202,250) # light sky blue
  1765.         blue = hexColor(112,172,255) # sky blue
  1766.         #blue = hexColor(160,191,235) # alternative
  1767.         cy = self.height/2
  1768.         self.canvas.create_rectangle(0, 0, self.width, cy,
  1769.                                      fill=blue, width=0)
  1770.  
  1771.     def redraw3D(self):
  1772.         cx = self.width/2
  1773.         cy = self.height/2
  1774.         scaleX = (self.width / CAM_WIDTH)
  1775.         scaleY = (self.height / CAM_HEIGHT)
  1776.         self.drawGround()
  1777.         self.drawSky()
  1778.         for s in self.screenSegs:
  1779.             left = cx - s.x1*scaleX
  1780.             right = cx - s.x2*scaleX
  1781.             leftTop = cy + s.h1*scaleY
  1782.             leftBot = cy - s.h1*scaleY
  1783.             rightTop = cy + s.h2*scaleY
  1784.             rightBot = cy - s.h2*scaleY
  1785.             self.canvas.create_polygon(left, leftTop, right, rightTop,
  1786.                                        right, rightBot, left, leftBot,
  1787.                                        fill=s.color,
  1788.                                        outline="black")
  1789.  
  1790.     def draw3DGChannel(self, channel):
  1791.         # the wireframe 3DG idea was Nick Goman's
  1792.         cx = self.width/2
  1793.         cy = self.height/2
  1794.         scaleX = (self.width / CAM_WIDTH)
  1795.         scaleY = (self.height / CAM_HEIGHT)
  1796.         if (channel == "right"):
  1797.             screenSegs = self.screenSegs
  1798.             shift = "0,0"
  1799.         else:
  1800.             screenSegs = self.secScreenSegs
  1801.             shift = "0,1"
  1802.         for s in screenSegs:
  1803.             left = cx - s.x1*scaleX
  1804.             right = cx - s.x2*scaleX
  1805.             leftTop = cy + s.h1*scaleY
  1806.             leftBot = cy - s.h1*scaleY
  1807.             rightTop = cy + s.h2*scaleY
  1808.             rightBot = cy - s.h2*scaleY
  1809.             if (channel == "right"):
  1810.                 outlineColor = hexColor(255,0,0)
  1811.             else:
  1812.                 outlineColor = hexColor(0,255,255)
  1813.             if (s.color == "#ffffff"):
  1814.                 endColor = "#bbffbb"
  1815.                 self.canvas.create_polygon(left, leftTop, right, rightTop,
  1816.                                            right, rightBot, left, leftBot,
  1817.                                            width=0, fill=endColor)
  1818.             self.canvas.create_line(left, leftTop, right, rightTop,
  1819.                                     stipple="gray50", offset=shift,
  1820.                                     fill=outlineColor,width=3)
  1821.             self.canvas.create_line(right, rightTop, right, rightBot,
  1822.                                     stipple="gray50", offset=shift,
  1823.                                     fill=outlineColor,width=3)
  1824.             self.canvas.create_line(right, rightBot, left, leftBot,
  1825.                                     stipple="gray50", offset=shift,
  1826.                                     fill=outlineColor,width=3)
  1827.             self.canvas.create_line(left, leftBot, left, leftTop,
  1828.                                     stipple="gray50", offset=shift,
  1829.                                     fill=outlineColor,width=3)
  1830.  
  1831.  
  1832.     def redraw3DG(self):
  1833.         self.drawBackground() # white
  1834.         self.draw3DGChannel("left")
  1835.         self.draw3DGChannel("right")
  1836.  
  1837. game = MazeGame(10, 1366, 768)
  1838. game.run()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!