# Copyright 2013 Jonatan Bijl # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 3 of the License, or # (at your option) any later version. # # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # For the GNU General Public License, see . # 3D maze drawing program # steps: # 0) useful data structures and constants # 1) defining - define where walls are # 2) clipping - hide (parts of) walls that are behind other walls # 3) drawing - let turtle draw the remaining walls. import turtle # 0) useful data structures and constants HALF_WIDTH, HALF_HEIGHT = 300, 600 #half pillar width HPW = 0.2 class Point: def __init__(self, x, y): #world-space x,y coords self.x, self.y = x,y #screen-space x,y after perspective transform. self.tx, self.ty = HALF_WIDTH*x/y, HALF_HEIGHT/y #angle of line from 0,0 through x,y self.direction = y/x class Wall: def __init__(self, p1, p2): self.left, self.right = (p1, p2) if p1.tx < p2.tx else (p2, p1) dx, dy = self.right.x - self.left.x, self.right.y - self.left.y if dx == 0: #wall along Y axis self.a = float('inf') else: #store wall line as formula f(x) = a*x + b self.a = dy/dx self.b = self.left.y - self.a * self.left.x def raycast(self, c): if self.a == float('inf') : #wall along Y axis if c != 0: return Point(self.left.x, c * self.left.x) else: #intersection of the line y=ax+b and the line y=cx if c != self.a: x = self.b / (c - self.a) return Point(x, self.a * x + self.b) return None #some utils to help define walls def make_walls(*coords): return [Wall(Point(*p1), Point(*p2)) for p1, p2 in zip(coords,coords[1:])] def make_pillar(x, y): return make_walls((x-HPW,y-HPW),(x+HPW,y-HPW),(x+HPW,y+HPW),(x-HPW,y+HPW), (x-HPW,y-HPW)) # 1) defining - define where walls are (and add some pillars) walls = make_walls((-6.5,2), (-6.5,8), (-3.5,8), (-3.5,12), (-0.5,12), (-0.5,8), (6.5,8), (6.5,5), (7,5), (7,12), (15,12), (15,6), (9,6), (9,3.5), (6.5,3.5), (6.5,2)) for y in [3.5, 4.5, 5.5, 6.5]: walls.extend(make_pillar(-5.5,y) + make_pillar(3.5,y)) for y in [3.5, 6.5]: walls.extend(make_pillar(-2.5,y) + make_pillar(.5,y)) # 2) clipping - hide (parts of) walls that are behind other walls. # In this process, a wall might get cut up into several wall-segments. # # Removes the part of wall that is hidden behind occluder (another wall), returning the visible part(s) # Only call this if you are sure occluder is not wall, or it might hide itself ;) # Everything is based on comparing tx values (perspective-projected x coords) and y values (for depth checking) def clip(wall, occluder): #easy cases: no hiding at all if wall.right.tx <= occluder.left.tx or wall.left.tx >= occluder.right.tx or occluder.right.tx == occluder.left.tx: return [wall] #complicated cases: walls partially or totally overlapping, not sure which is in front #find the left and right side of the area where the two are overlapping, and analyze those points if wall.left.tx < occluder.left.tx: l_w_point, l_o_point = wall.raycast(occluder.left.direction), occluder.left else: l_w_point, l_o_point = wall.left, occluder.raycast(wall.left.direction) if wall.right.tx > occluder.right.tx: r_w_point, r_o_point = wall.raycast(occluder.right.direction), occluder.right else: r_w_point, r_o_point = wall.right, occluder.raycast(wall.right.direction) #check if occluder is in front of wall by the total who-is-in-front-of-who score if ((l_o_point.y - l_w_point.y) + (r_o_point.y - r_w_point.y)) < 0: clipped_walls = [] if wall.left.tx < occluder.left.tx: clipped_walls.append(Wall(wall.left, l_w_point)) if wall.right.tx > occluder.right.tx: clipped_walls.append(Wall(r_w_point, wall.right)) return clipped_walls #may be empty if totally occluded else: return [wall] #clipping stage: make a new list of all the wall-segments that are not hidden behind other walls clipped_walls = [] for wall in walls: #start with the wall as only segment wall_segments = [wall] #then clip it with all the walls there are. for occluder in walls: if occluder != wall: wall_segments = [out_segment for in_segment in wall_segments for out_segment in clip(in_segment, occluder)] #the remaining bits are what is actually visible clipped_walls.extend(wall_segments) #draw from left to right. Speeds up drawing a lot clipped_walls.sort(key=lambda x: x.left.tx) #now that we've determined what exactly we want to draw, let Turtle do his work. t = turtle.Turtle() #draw the given wall in perspective def draw_poly(wall): points = [(wall.right.tx, -wall.right.ty), (wall.right.tx, wall.right.ty), (wall.left.tx, wall.left.ty), (wall.left.tx, -wall.left.ty)] t.penup() t.goto(*points[-1]) t.pendown() for x, y in points: t.goto(x,y) #draw every wall-segment like that for wall in clipped_walls: draw_poly(wall) turtle.exitonclick()