Instantly share code, notes, and snippets.

# NashS/gist:6233283 Last active Dec 21, 2015

 ''' Created on Aug 11, 2013 @author: BEEFCAKE ''' import math spaceArray = [] rayEquation = [] rayDir = 0 rayCollision = [-1,-1] def checkIntersection(tileX,tileY,faceToCheck): global rayEquation A = 0 B = 0 C = 0 x1 = 0 x2 = 0 y1 = 0 y2 = 0 #Check for right-face tile intersection if faceToCheck == "right": A = 1 B = 0 x1 = tileX + 1 y1 = tileY elif faceToCheck == "top": A = 0 B = -1 x1 = tileX y1 = tileY elif faceToCheck == "left": A = 1 B = 0 x1 = tileX y1 = tileY elif faceToCheck == "bottom": A = 0 B = -1 x1 = tileX y1 = tileY+1 else: return [-1,-1] x2 = x1 - B y2 = y1 + A C = A*x1 + B*y1 det = rayEquation[0]*B - A*rayEquation[1] X = round((B*rayEquation[2] - rayEquation[1]*C)/det,15) Y = round((rayEquation[0]*C - A*rayEquation[2])/det,15) if x1 <= X <= x2 - B and y1 <= Y <= y2: return [X,Y] else: return [-1,-1] def isRayInTile(tileX, tileY, faceToCheck): global spaceArray global rayEquation global rayDir global rayCollision #no need to further explore space if collision already found if rayCollision[0] >= 0 and rayCollision[1] >= 0: return #make sure current tile is within the domain of the space if 0 > tileX or tileX >= len(spaceArray) or 0 > tileY or tileY >= len(spaceArray[0]): return tileIntersection = [-1,-1] if faceToCheck != "none": tileIntersection = checkIntersection(tileX, tileY,faceToCheck) else: tileIntersection = [0,0] if tileIntersection[0] >= 0 and tileIntersection[1] >= 0: if spaceArray[tileY][tileX] == 0: if rayDir < math.pi/2: isRayInTile(tileX+1,tileY,faceToCheck="left") isRayInTile(tileX,tileY+1,faceToCheck="top") elif math.pi/2 <= rayDir < math.pi: isRayInTile(tileX-1,tileY,faceToCheck="right") isRayInTile(tileX,tileY+1,faceToCheck="top") elif math.pi <= rayDir < 3*math.pi/2: isRayInTile(tileX-1,tileY,faceToCheck="right") isRayInTile(tileX,tileY-1,faceToCheck="bottom") elif 3*math.pi/2 <= rayDir < 2*math.pi: isRayInTile(tileX+1,tileY,faceToCheck="left") isRayInTile(tileX,tileY-1,faceToCheck="bottom") else: rayCollision = [round(tileIntersection[0],3),round(tileIntersection[1],3)] return return def rayCast(input): global spaceArray global rayEquation global rayDir global rayCollision rayCollision = [-1,-1] lines = input.splitlines() spaceWidth = float(lines[0].split()[0]) spaceHeight = float(lines[0].split()[1]) spaceArray = [[1 if c=="x" else 0 for c in lines[x]] for x in range(1, len(lines)-1)] rayOrigX = float(lines[len(lines)-1].split()[0]) rayOrigY = float(lines[len(lines)-1].split()[1]) rayDir = float(lines[len(lines)-1].split()[2]) % (2*math.pi) #Vertically flipping ray Direction because going up means going in the negative y direction rayDir += 2*(math.pi - rayDir) #ensures the ray length will pass the boundaries of the space to make sure it checks for every possible wall along the ray path rayLength= float(math.sqrt(spaceWidth**2 + spaceHeight**2)) #Ax+By=C where A=y2-y1, B=x1-x2, C=A*x1+B*y1 A = rayLength*math.sin(rayDir) B = -1*rayLength*math.cos(rayDir) C = A*rayOrigX + B*rayOrigY rayEquation =[A,B,C] isRayInTile( int(math.floor(rayOrigX)), int(math.floor(rayOrigY)), faceToCheck="none") return rayCollision if __name__ == '__main__': print rayCast( "10 10\n"+ "xxxxxxxxxx\n"+ "x x x x\n"+ "x x x x\n"+ "x x xxx\n"+ "xxxx x\n"+ "x x x\n"+ "x x\n"+ "x x x\n"+ "x x xx\n"+ "xxxxxxxxxx\n"+ "6.5 6.5 3") print rayCast( "4 4\n"+ "xxxx\n"+ "xx x\n"+ "x x\n"+ "xxxx\n"+ "1.5 2.5 0.7853981") print rayCast( "4 4\n"+ "xxxx\n"+ "xx x\n"+ "x x\n"+ "xxxx\n"+ "1.5 2.5 0.7853982") print rayCast( "4 4\n"+ "xxxx\n"+ "x x\n"+ "x xx\n"+ "xxxx\n"+ "2.5 1.5 3.92699082") print rayCast( "4 4\n"+ "xxxx\n"+ "x x\n"+ "x xx\n"+ "xxxx\n"+ "2.5 1.5 3.92699081")