-- title:  Raycast Unlocked
-- author: Nalquas
-- desc:   An FPS-independent Raycaster with sprites
-- script: lua
-- input:  gamepad

-- ===================================================================================================================================
-- INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO INFO
-- ===================================================================================================================================
-- Controls:
--	Up    Forward
--	Down  Backward
--	Left  TurnLeft
--	Right TurnRight
--	A (Z) SwitchMap
--	B (X) ToggleFOV (Press Up or Down while holding to change FOV)
--	X (A) StrafeLeft
--	Y (S) StrafeRight

-- Sides:
-- +1+
-- 4+2
-- +3+

-- Corners:
-- 1-2
-- |-|
-- 4-3

-- 1UPS=0.016666s

-- ===================================================================================================================================
-- VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES VARIABLES
-- ===================================================================================================================================
--Options (Should be available in a menu in a proper game):
fov=70 --Field of view
heightFactor=20 --Factor that influences the size of everything
distance=500 --View distance
overhead=false --Bird's-eye view?
musicTest=false --Test whether or not sound is stable (No, that's not music, that's beeping.)
fisheyeCompensation=1.16 --Originally 1.4, but people say that's still fisheye. 1.16 seems to be stable.
initialHitStepSize=8 --Size of the steps used to detect blocks during raycasting. Low values lead to very accurate projection at low performance, high values lead to very unconsistent projection at excellent performance.
betterSky=true --Apply sky gradient?
gifRecorderMode=false
doCorrectFPS=true
classicRender=false --Render every pixel in a texture as a seperate line or every line in a texture as a textri?

fpsFactor=1

-- Memory of last actions performed, and when (For making gameplay fps-independent)
last={t=time(),btn={}}
for i=0,7 do last.btn[i]=false end
now=last

t=0
player={x=96,y=24,rot=90,stepDistance=1,rotationSpeed=2}
spriteList={}
spriteList[1]={created=false,index=1,ck=0,w3D=0.45,h3D=0.75,x=120,y=90,sizeX=1,sizeY=1,firstScreenX=0,lastScreenX=0,firstScreenHeight=0,lastScreenHeight=0,distance=0}
spriteList[2]={created=false,index=32,ck=0,w3D=0.75,h3D=2.2,x=264,y=48,sizeX=2,sizeY=3,firstScreenX=0,lastScreenX=0,firstScreenHeight=0,lastScreenHeight=0,distance=0}
spriteList[3]={created=false,index=2,ck=0,w3D=0.9,h3D=0.75,x=304,y=56,sizeX=2,sizeY=1,firstScreenX=0,lastScreenX=0,firstScreenHeight=0,lastScreenHeight=0,distance=0}
spriteList[4]={created=false,index=2,ck=0,w3D=0.45,h3D=0.375,x=296,y=40,sizeX=2,sizeY=1,firstScreenX=0,lastScreenX=0,firstScreenHeight=0,lastScreenHeight=0,distance=0}
spriteList[5]={created=false,index=2,ck=0,w3D=0.275,h3D=0.1875,x=288,y=48,sizeX=2,sizeY=1,firstScreenX=0,lastScreenX=0,firstScreenHeight=0,lastScreenHeight=0,distance=0}
spriteList[6]={created=false,index=32,ck=0,w3D=0.75,h3D=2.2,x=328,y=48,sizeX=2,sizeY=3,firstScreenX=0,lastScreenX=0,firstScreenHeight=0,lastScreenHeight=0,distance=0}

-- ===================================================================================================================================
-- FUNCTIONS FUNCTIONS FUNCTIONS FUNCTIONS FUNCTIONS FUNCTIONS FUNCTIONS FUNCTIONS FUNCTIONS FUNCTIONS FUNCTIONS FUNCTIONS FUNCTIONS
-- ===================================================================================================================================
-- FPS function:
local FPS={value =0,frames =0,lastTime=-1000}
function FPS:getValue()
  if (time()-self.lastTime <= 1000) then
    self.frames=self.frames+1
  else 
    self.value=self.frames
    self.frames=0
    self.lastTime=time()
  end
  return self.value
end

-- Load palette string
function loadPalette(pal)
	for i=0,15 do
	 r=tonumber(string.sub(pal,i*6+1,i*6+2),16)
	 g=tonumber(string.sub(pal,i*6+3,i*6+4),16)
	 b=tonumber(string.sub(pal,i*6+5,i*6+6),16)
	 poke(0x3FC0+(i*3)+0,r)
	 poke(0x3FC0+(i*3)+1,g)
	 poke(0x3FC0+(i*3)+2,b)
	end
end

-- set spritesheet pixel
function sset(x,y,c)
    local addr=0x4000+(x//8+y//8*16)*32 -- get sprite address
    poke4(addr*2+x%8+y%8*8,c) -- set sprite pixel
end

-- get spritesheet pixel
function sget(x,y)
    local addr=0x4000+(x//8+y//8*16)*32 -- get sprite address
    return peek4(addr*2+x%8+y%8*8) -- get sprite pixel
end

-- Set background color
function background(bgrValue)
	poke(0x03FF8, bgrValue) -- Set Background
end

-- Round stuff
function round(x)
	if x<0 then return math.ceil(x-0.5) end
	return math.floor(x+0.5)
end

-- Generates all the parameters used in lineMemory
function generateLine(x1,y1,x2,y2,c,distance)
	return {x1=x1,y1=y1,x2=x2,y2=y2,c=c,distance=distance}
end

function scaledSpr(id,x,y,x2,y2,colorKey,width,height)
	-- A B
	--
	-- D C
    -- ax ay bx by cx cy au av bu bv cu cv
	
    ax=x
    ay=y
    
    bx=x2
    by=y
    
    cx=x2
    cy=y2
    
    dx=x
    dy=y2
    
    uFactor=((id%16)*8)
    vFactor=math.floor(id/16)*8
    
    au=uFactor
    av=vFactor
    
    bu=uFactor+width
    bv=vFactor
    
    cu=uFactor+width
    cv=vFactor+height
    
    du=uFactor
    dv=vFactor+height
    
    textri(ax,ay,bx,by,cx,cy,au,av,bu,bv,cu,cv,false,colorKey)
    textri(ax,ay,dx,dy,cx,cy,au,av,du,dv,cu,cv,false,colorKey)
end

-- ===================================================================================================================================
-- INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT INIT
-- ===================================================================================================================================
if musicTest then music(7,-1,-1,true) end

-- Change palette entry 14 each line to have a good sky gradient
function scanline(row)
	if betterSky then
		
		--Possible colors: (B is always X-row*3)
		--  R   G   B
		-- 000-000-255 Pure blue (looks artificial)
		-- 096-064-255 Sundown, early
		-- 128-064-255 Sundown, mid
		-- 128-096-255 Morning
		
		-- skygradient (palette position 14)
		poke(0x3fea,128) --r
		poke(0x3feb,64) --g
		poke(0x3fec,255-row*3) --b
	end
end

function TIC()
-- ===================================================================================================================================
-- SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC SYNC
-- ===================================================================================================================================
	currUPS=FPS:getValue()
	if (gifRecorderMode) then
		tDiff=0.01666
	else
		tDiff=(time()-now.t)/1000.0
	end
	tDiffUPS=tDiff/0.016666 --1UPS~0.016666s
	last=now
	now.t=time()
	for i=0,7 do now.btn[i]=btn(i) end
	
	--Decide amount of frames to be rendered based on tDiffUPS (Buggy?...)
	if (doCorrectFPS) then
		if (tDiffUPS>=2 and fpsFactor==1) then fpsFactor=2 elseif (tDiffUPS<=1.0 and fpsFactor==2) then fpsFactor=1 end
	end

-- ===================================================================================================================================
-- INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT INPUT
-- ===================================================================================================================================
	if now.btn[0] and last.btn[0] then
		if now.btn[5] then
			fov=fov+0.5
			--specialFactor=specialFactor+0.005
		else
			player.x=(player.stepDistance*math.cos(math.rad(player.rot))*tDiffUPS)+player.x
			player.y=(player.stepDistance*math.sin(math.rad(player.rot))*tDiffUPS)+player.y
		end
	end
	if now.btn[1] and last.btn[1] then
		if now.btn[5] then
			fov=fov-0.5
			--specialFactor=specialFactor-0.005
		else
			player.x=(player.stepDistance*math.cos(math.rad(player.rot-180))*tDiffUPS)+player.x
			player.y=(player.stepDistance*math.sin(math.rad(player.rot-180))*tDiffUPS)+player.y	 
		end
	end
	if now.btn[2] then player.rot=player.rot-(player.rotationSpeed*tDiffUPS) end
	if now.btn[3] then player.rot=player.rot+(player.rotationSpeed*tDiffUPS) end
	if now.btn[4] and t%10==0 then overhead=not overhead end
	if now.btn[6] and last.btn[6] then 
		player.x=(player.stepDistance*math.cos(math.rad(player.rot-90))*tDiffUPS)+player.x
		player.y=(player.stepDistance*math.sin(math.rad(player.rot-90))*tDiffUPS)+player.y
	end
	if now.btn[7] and last.btn[7] then
		player.x=(player.stepDistance*math.cos(math.rad(player.rot+90))*tDiffUPS)+player.x
		player.y=(player.stepDistance*math.sin(math.rad(player.rot+90))*tDiffUPS)+player.y	 
	end
	
-- ===================================================================================================================================
-- LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC LOGIC
-- ===================================================================================================================================
	--Limit Player rotation to avoid unlikely overflows
	if player.rot>=360 then player.rot=player.rot-360 end
	if player.rot<0 then player.rot=player.rot+360 end
 
-- ===================================================================================================================================
-- RENDER RENDER RENDER RENDER RENDER RENDER RENDER RENDER RENDER RENDER RENDER RENDER RENDER RENDER RENDER RENDER RENDER RENDER
-- ===================================================================================================================================
	--Only render if supposed to:
	if (t%fpsFactor==0) then
		--background(14)
		
		--Initialization
		if (betterSky) then
			cls(14) --Sky with gradient
		else
			cls(2) --Sky/Ceiling/Background
		end
		
		if overhead then 
			map(0,0,240,136,-player.x+120,-player.y+68,-1,1) --Map
			circ(120,68,2,6) --Player Marker
			
			--Sprites:
			for i=1,#spriteList do
				spr(spriteList[i].index,spriteList[i].x-((spriteList[i].sizeX*8)/2)-player.x+120,spriteList[i].y-((spriteList[i].sizeX*8)/2)-player.y+68,0,1,0,0,spriteList[i].sizeX,spriteList[i].sizeY)
			end
		else
			rect(0,66,240,70,4) --Ground
		end
		
		--RAYCASTING! THIS IS HOW YOU DO IT!
		--0.3125 degrees per pixel->75 degrees
		--0.375 degrees per pixel ->90 degrees
		--rot=-37.5
		--rot=-45
		rot=-(fov/2)
		--lastLine={mapX=-1,mapY=-1,sRight=0}
		renderQueue={[1]=1}
		for i=0,239 do
			--if (i==120) then trace(player.rot+rot) end
			continue=true
			jk=0 --Distance (radius of a circle)
			j=0 --Distance (The one actually used to render stuff)
			side=0 --Side we hit a block on
			initHit=false --Has the first hit of something been done for this iteration?
			initIndex=-1 --Index of the first block we hit
			finalHit=false --Has backwards raycasting been finished to get a precise distance?
			lastX2=-1
			lastY2=-1
			lastMapX=-1
			lastMapY=-1
			isCorner=false --Is what we ended up with a corner?
			cornerNr=1 --What rotation does the corner have?
			--lineMemory={} --List of line command parameters for rendering sprites etc. in the 3D-world, pixel by pixel
			
			while jk<=distance and continue do
				if jk<0 then break end
				
				--Oh, and iterate j, of cause.
				if not initHit then
					jk=jk+initialHitStepSize
				end
				
				-- Perspective correction (Not perfect, but reduces fisheye!)
				j=jk/math.cos(math.rad(rot/fisheyeCompensation))
				
				--Calculate point to check:
				x2=((j/2.0)*math.cos(math.rad(player.rot+rot)))+player.x
				y2=((j/2.0)*math.sin(math.rad(player.rot+rot)))+player.y
				
				--Check point on map for wall:
				mapX=math.floor(x2/8)
				mapY=math.floor(y2/8)
				index=mget(mapX,mapY)
				
				spriteWeGot=0
				--Have we hit a sprite? If yes, which one?
				for i=1,#spriteList do
					if ((x2>=spriteList[i].x-4) and (x2<=spriteList[i].x+4) and (y2>=spriteList[i].y-4) and (y2<=spriteList[i].y+4)) then
						spriteWeGot=i
						break;
					end
				end
				
				--And go on to render...
				if index>0 or initIndex>0 then
					
					-- Go back a few steps in distance to find the precise wall position and side
					if not initHit then
						initHit=true
						lastX2=x2
						lastY2=y2
						lastMapX=mapX
						lastMapY=mapY
						initIndex=index
						
						if cornersOn then
							--Is it a corner?
							if not ((index%8)==0 or (index%8)==5) then
								isCorner=true
								cornerNr=index%8
							end
						end
					elseif not finalHit then
						if not (mapX==lastMapX) or not (mapY==lastMapY) then--or (isCorner and not (checkCorner(cornerNr,x2,y2))) then
							if index>0 then
								lastX2=x2
								lastY2=y2
								lastMapX=mapX
								lastMapY=mapY
								initIndex=index
								if overhead then pix(x2-player.x+120,y2-player.y+68,14) end
							else
								x2=lastX2
								y2=lastY2
								mapX=lastMapX
								mapY=lastMapY
								jk=jk+1
								index=initIndex
								finalHit=true
								if overhead then pix(x2-player.x+120,y2-player.y+68,6) end
							end
						else
							lastX2=x2
							lastY2=y2
							lastMapX=mapX
							lastMapY=mapY
							if overhead then pix(x2-player.x+120,y2-player.y+68,13) end
						end
						jk=jk-1
					end
					
					if finalHit then --Render the line once we know the precise distance
						if overhead then
							continue=false
						else
							--Find out which side we hit the wall on
							jkR=jk
							jR=j
							xR=0
							yR=0
							continueBack=true
							while continueBack do
								jkR=jkR-0.5
								
								-- Perspective correction (to avoid fisheye!)
								jR=jk/math.cos(math.rad(rot/fisheyeCompensation))
								
								--Calculate point to check:
								xR=((jR/2.0)*math.cos(math.rad(player.rot+rot)))+player.x
								yR=((jR/2.0)*math.sin(math.rad(player.rot+rot)))+player.y
								--Check point on map for wall:
								mapXR=math.floor(xR/8)
								mapYR=math.floor(yR/8)
								
								if mapXR<mapX then
									side=4
									continueBack=false
								elseif mapXR>mapX then
									side=2
									continueBack=false
								elseif mapYR<mapY then
									side=1
									continueBack=false
								elseif mapYR>mapY then
									side=3
									continueBack=false
								elseif jR<0 then
									continueBack=false
								end
							end
							
							--Render wall
							height=136/jkR*heightFactor --Total height of a line
							step=(height*1.5)/8 -- using *1.5 instead of /2*3 increases performance by 3fps --Height of one pixel of a texture on the line
							heightDiff=height/2
							yNow=66-(height/2)
							if not (side==0) then
								indexChange=0
								posInTexture=0
								if side%2==1 then
									indexChange=1
									posInTexture=math.floor(xR%8)
								else
									posInTexture=math.floor(yR%8)
								end
								
								if classicRender then
									-- Render lines with textures based on known side and position
									for k=0,7 do --Increasing k to 15 results in a kind of reflection; Maybe useful later on?
										--lineMemory[#lineMemory+1]=generateLine(i,yNow,i,yNow+step,sget(((index+indexChange)*8)+posInTexture,k),j)
										line(i,yNow,i,yNow+step,sget(((index+indexChange)*8)+posInTexture,k)) --Putting all the wall data into lineMemory induces a significant performance drop
										yNow=yNow+step
									end
								else
									texX=(((index+indexChange)%16)*8)+posInTexture
									texY=(math.floor((index+indexChange)/16)*8)
									textri(i,yNow,i+1,yNow,i+1,yNow+(7*step),texX,texY,texX,texY,texX,texY+8,false,-1);
								end
							end
							continue=false
						end
					end
				elseif overhead then
					pix(x2-player.x+120,y2-player.y+68,15)
				elseif spriteWeGot>0 then
					--Refresh information on spriteList
					--Raycasten, ersten x merken, zweiten y merken, Differenz->XScale, height=yScale
					heightN=136/jk*heightFactor
					if (spriteList[spriteWeGot].created) then
						spriteList[spriteWeGot].lastScreenX=i
						spriteList[spriteWeGot].lastScreenHeight=heightN
						
						--Handle renderQueue sorting here?
						if (spriteList[renderQueue[spriteList[spriteWeGot].renderN-1]].distance>spriteList[spriteWeGot].distance) then --If this distance is bigger than on the last sprite...
							renderQueue[spriteList[spriteWeGot].renderN]=renderQueue[spriteList[spriteWeGot].renderN-1]
							renderQueue[spriteList[spriteWeGot].renderN-1]=spriteWeGot
						end
						
						--for down=1,#renderQueue-2 do
							--if (spriteList[renderQueue[spriteList[spriteWeGot].renderN-down]].distance>spriteList[spriteWeGot].distance) then --If this distance is bigger than on the last sprite...
								--renderQueue[spriteList[spriteWeGot].renderN]=renderQueue[spriteList[spriteWeGot].renderN-down]
								--renderQueue[spriteList[spriteWeGot].renderN-down]=spriteWeGot
							--end
						--end
					else
						spriteList[spriteWeGot].firstScreenX=i
						spriteList[spriteWeGot].firstScreenHeight=heightN
						spriteList[spriteWeGot].lastScreenX=i
						spriteList[spriteWeGot].lastScreenHeight=heightN
						renderQueue[#renderQueue+1]=spriteWeGot
						spriteList[spriteWeGot].renderN=#renderQueue
						spriteList[spriteWeGot].distance=jk
						spriteList[spriteWeGot].created=true
					end
				end
			end
			
			--Iterate rotation
			rot=rot+(fov/240)
		end
		
		for j=#renderQueue,1,-1 do
			i=renderQueue[j]
			if (spriteList[i].created) then
				hNow=(spriteList[i].firstScreenHeight+spriteList[i].lastScreenHeight)/2
				xDiff=(spriteList[i].lastScreenX-spriteList[i].firstScreenX)*spriteList[i].w3D
				xMed=(spriteList[i].lastScreenX+spriteList[i].firstScreenX)/2
				yGround=65+hNow
				
				scaledSpr(spriteList[i].index,xMed-xDiff,yGround-(hNow*spriteList[i].h3D),xMed+xDiff,yGround,spriteList[i].ck,spriteList[i].sizeX*8,spriteList[i].sizeY*8)
				
				--Reset every sprite here!
				spriteList[i].created=false
				spriteList[i].firstScreenX=0
				spriteList[i].firstScreenHeight=0
			end
		end
		
	-- ===================================================================================================================================
	-- DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG
	-- ===================================================================================================================================
		-- FPS Display:
		print("FPS: " .. currUPS,2,2,15,true,1,true)
		
		-- time() display
		print("\n\n\nnow.t="..now.t.."\nlast.t="..last.t.."\ntDiff="..tDiff.."\nUPS/FPS="..tDiffUPS.."\nfpsFactor="..fpsFactor,2,2,15,true,1,true)
		
		-- FOV Display:
		print("FOV: "..fov.."'",2,126,15,true,1,true)
	else
		--FPS:getValue()
	end
	
	-- ===================================================================================================================================
	-- ITERATION ITERATION ITERATION ITERATION ITERATION ITERATION ITERATION ITERATION ITERATION ITERATION ITERATION ITERATION ITERATION
	-- ===================================================================================================================================
	t=t+1
end