gistfile1.txt

'''
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")