public
Last active

  • Download Gist
gistfile1.txt
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183
'''
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")

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.