PICO-8 ray caster demo with loads of flip() calls

rayzzz-2.p8

pico-8 cartridge // http://www.pico-8.com
version 16
__lua__
-- raycaster demo
-- by @powersaurus
-- based heavily on http://lodev.org/cgtutor/raycasting.html
-- and http://lodev.org/cgtutor/raycasting2.html
-- and inspired by the work of @matthughson
-- thanks for advice from @kometbomb and @doyousketch2

debug=true
frames=0
function calculate_fps(now)
 frames+=1
 local newnow=flr(now)
 if (newnow!=lastclock) then
  fps=frames
  frames=0
  lastclock=newnow
 end
end

function clamp(val,mi,ma)
 return max(mi,min(ma,val))
end

function make_door(x,y,a)
 local d=make_sprite(x,y,a,true)
 d.update=function(s)
  local diff = abs(s.target_r-s.a)
		if diff>1 then
			local rot = (s.target_r-s.a)/diff*2
			turn_player(s,rot)
		end
		
		if abs(player.pos.x-s.pos.x)<=1.5 and 
	 abs(player.pos.y-s.pos.y)<=1.5 then
	  rotate_to(s,90)
 	else
   rotate_to(s,0)		
 	end
 end
 return d
end

function make_cat(x,y,a)
 local c=make_sprite(x,y,a,false)
 
 c.think_timer=1
 c.do_plan=function()
  local diff = abs(c.target_r-c.a)
 	if diff>1 then
 		local rot = 10
 		if c.target_r<c.a then
 		 rot=-10
 		end
 		turn_player(c,rot)
 	end

  move_in_current_dir(c,0.10)  
 end
  
 c.update=function(c)
  c.do_plan()
   
  c.think_timer-=1
  if c.think_timer==0 then
   c.think_timer=30
   --plan
   rotate_to(c,rnd(360))
   --end plan
  end
 end
end

function make_sprite(x,y,a,flat)
 local s={
  a=0,
  target_r=0,
  dr={x=1,y=0},
  pos={x=x,y=y},
  flat=flat
 }
 return s
end
		
function rotate_to(s,targetrotation)
	s.target_r = targetrotation
end

function make_world()
 return {
  {5,6,5,6,2,2,2,5,5,5,5,0,0,0,0,0,0,0},
  {5,-1,-1,-1,-1,-1,2,-4,-4,-4,2,0,0,0,0,0,0,0},
  {5,-1,-1,-1,-1,-1,2,-4,-4,-4,6,6,6,6,6,6,6,6},
  {6,-1,-1,-1,-1,-1,2,-4,-4, -4,-4,-3,-3,-3,-3,-3,-3,6},
  {6,-1,-1,-1,-1,2,2,-4,-4,-4,-3,-3,-3,-3,-3,-3,-3,6},
  {6,-1,-1,-1,-1,2,2,-4,-4,-4,6,6,6,6,6,6,6,6},
  {6,-1,-1,-1,-1,-4,-4,-4,-4,-4,5,0,0,0,0,0,0,0},
  {5,-1,-1,-1,-1,2,-4,-4,-4,-4,5,0,0,0,0,0,0,0},
  {5,-1,-1,-1,-1,2,-4,-4,-4,-4,5,0,0,0,0,0,0,0},
  {5,5,5,5,5,5,5,5,5,5,5,0,0,0,0,0,0,0}
 }
end

function _init()
 timer=0
 dist_table={}
 detail_limit_table={}
 create_palettes()
 
 msg=""
 player={
  a=0,
  pos={x=2.5,y=2.5},
--  pos={x=5.704,y=4.116},
  dr={x=1,y=0}, -- looking west
  cam={x=0,y=0.66}
 }
 turn_player(player,55)
-- turn_player(player,7)

 world=make_world() 
 sprites={}
-- add(sprites,make_sprite(5,5,0,true))
-- add(sprites,make_sprite(3,8,rnd(360),true))
-- add(sprites,make_sprite(8.75,8,rnd(360),true))
-- add(sprites,make_sprite(9,9,rnd(360),true))
-- add(sprites,make_sprite(8,3,rnd(360),true))
 add(sprites,make_door(6.5,7,0))
 add(sprites,make_sprite(7,3.5,0,false))

 add(sprites,make_sprite(8,5,rnd(360)))
 add(sprites,make_sprite(9,5,rnd(360)))
 add(sprites,make_sprite(9,9,rnd(360)))
 add(sprites,make_sprite(7,9,rnd(360)))
 add(sprites,make_sprite(5,8,rnd(360)))
 add(sprites,make_sprite(4,7,rnd(360)))
 add(sprites,make_sprite(3,6,rnd(360)))
 add(sprites,make_sprite(8,5,rnd(360)))
 add(sprites,make_sprite(8,4,rnd(360)))--]]
 add(sprites,make_sprite(4,3,rnd(360)))
 add(sprites,make_sprite(8,2,rnd(360)))
 add(sprites,make_sprite(8,1,rnd(360)))
 add(sprites,make_sprite(8,3,rnd(360)))--]]
 
 for y=0,128 do
  dist_table[y]=128/(2*y-128)
  detail_limit_table[y]=flr(98+7*sin(y/256))
 end

--[[ world={}
 for y=1,32 do
  world[y]={}
  for x=1,32 do
   world[y][x]=sget(95+x,95+y)
  end
 end]]
 
 for y=1,#world do
--  print("y="..y.." "..#world[y])
  for x=1,#world[y] do

   poke(0x4300+y*#world[y]+x,abs(world[y][x]))
--   poke(0x4300+y*#world[y]+x,y)
  end
 end

 stars={}
 for s=0,50 do
  local x=rnd(20)-10
  local y=rnd(20)-10
  local z=rnd(96)
  local star={
   x=x,
   y=y,
   z=z
  }
  
  add(stars,star)
 end
 
 particles={}
-- add(particles,{x=2,y=2,z=1})
-- add(particles,{x=3,y=3,z=1})
-- add(particles,{x=3,y=2,z=1})
-- add(particles,{x=2,y=3,z=1})
--[[ for i=1,128 do
  local d=rnd(2)
  local r=rnd(1)
  add(particles,{
   x=4+d*-sin(r),
   y=4+d*cos(r),
   z=rnd(50)-30,
   life=100})
 end]]
 


 _draw=draw
 _update=update

end

function turn_player(player,ar)
 player.a+=ar
 if player.a>359 then
  player.a-=359
 end
 player.a=flr(player.a)
 local r=player.a/360
 local olddrx=player.dr.x
  
 player.dr.x=cos(r)
 player.dr.y=-sin(r)

 if player.cam then
  local r2=ar/360
  local oldplanex=player.cam.x
  player.cam.x=oldplanex*cos(r2)+
   player.cam.y*sin(r2)
  player.cam.y=-oldplanex*sin(r2)+
   player.cam.y*cos(r2)
 end
end

strafe=false
draw_map=false
function update()
 timer+=1

 if btnp(5) then
  draw_map=not draw_map
 end
 local sp=0.16 
 if btn(4) then
  strafe=true
 else
  strafe=false
 end
 if btn(0) then
  if strafe then
   local movex=flr(player.pos.x-player.cam.x*sp)
   local movey=flr(player.pos.y-player.cam.y*sp)
  
   if (world[flr(player.pos.y)][movex]<=0) player.pos.x-=player.cam.x*sp
   if (world[movey][flr(player.pos.x)]<=0) player.pos.y-=player.cam.y*sp
  else
   turn_player(player,-3)
  end
 end
 if btn(1) then
  if strafe then
   local movex=flr(player.pos.x+player.cam.x*sp)
   local movey=flr(player.pos.y+player.cam.y*sp)
  
   if (world[flr(player.pos.y)][movex]<=0) player.pos.x+=player.cam.x*sp
   if (world[movey][flr(player.pos.x)]<=0) player.pos.y+=player.cam.y*sp
  else
   turn_player(player,3)   
  end
 end

 if btn(2) then
  move_in_current_dir(player,sp)
 end
 if btn(3) then
  move_in_current_dir(player,-sp)
 end
 
 for _,s in pairs(sprites) do
  if (s.update) s:update()
 end
end

function move_in_current_dir(s,amount)
 local movex=s.pos.x+s.dr.x*amount
 local movey=s.pos.y+s.dr.y*amount
  
 if world[flr(s.pos.y)][flr(movex)]<=0 
-- and abs(flr(movex)-movex)>0.1
 then
  s.pos.x+=s.dr.x*amount
 end
 if world[flr(movey)][flr(s.pos.x)]<=0 
-- and abs(flr(movey)-movey)>0.1
 then
  s.pos.y+=s.dr.y*amount
 end
end

function draw()
 reset_palette()

 calculate_fps(time())
 timer+=1
 
 if draw_map then
  draw_map_view(world,player)
 else
  draw_perspective(world,player,dist_table,detail_limit_table)
 end
  
 if debug then
  reset_palette()
--  print(fps,2,2,7)
 
--  print("cpu: "..stat(1),2,10,7)
 
--	 print("pos: "..player.pos.x.." "..player.pos.y.." "..player.a,2,19,7)
--  print("msg: "..msg,2,19,7)
 end
end


function draw_map_view(world,player)
 cls()
 for y=1,#world do
  for x=1,#world[y] do

   rectfill(x*4,y*4,x*4+3,y*4+3,world[y][x])
  end
 end

 rectfill(
  player.pos.x*4,
  player.pos.y*4,
  player.pos.x*4+3,
  player.pos.y*4+3,7)
end

function draw_perspective(world,player,dist_table,detail_limit_table)
 -- sky
 rectfill(0,0,128,64,0)
    flip()
--[[ for i=48,60,2 do
  rectfill(0,i,128,i,1)
  rectfill(0,i+7,128,i+7,1)
 end]]
 
 local cam=player.cam
 local dr=player.dr
 -- stars
 for _,s in pairs(stars) do
  local invdet=1/(cam.x*dr.y-cam.y*dr.x)
  
  local tfx=invdet*(dr.y*s.x-dr.x*s.y)
  local tfy=invdet*(-cam.y*s.x+cam.x*s.y)
  local sx=64*(1+tfx/tfy)
  local sy=abs(64-s.z)
  pset(sx,sy,7)
     flip()
 end
 
 rectfill(0,64,128,128,1)
   flip()
 local floors={} 
 local zbuf={}
 local check=0
 local prevside=-1
-- local lworld=world
-- local ldist_table=dist_table
 local camx1=player.cam.x
 local camy=player.cam.y
 local rayx=player.pos.x
 local rayy=player.pos.y
 
 for x=0,127 do 
  local camx=2*x/128 -1
  
  local raydirx=
   player.dr.x+camx1*camx
  local raydiry=
   player.dr.y+camy*camx
   
  local mapx=flr(rayx)
  local mapy=flr(rayy)

  local rdy2=raydiry*raydiry
  local rdx2=raydirx*raydirx
  local ddx=sqrt(1+rdy2/rdx2)
  local ddy=sqrt(1+rdx2/rdy2)

  if abs(raydirx)<0.01 then
   ddx=100
  end
  if abs(raydiry)<0.01 then
   ddy=100
  end
  
  local hit=0
  local side=0
  local stepx=0
  local stepy=0
  local sidedistx=0
  local sidedisty=0
  local texidx=0
  
-- fooooo
  if raydirx<0 then
   stepx=-1 
   sidedistx=(rayx-mapx)*ddx 
  elseif raydirx>0 then
   stepx=1
   sidedistx=(mapx+1-rayx)*ddx 
  else
   stepx=0
   sidedistx=20000
  end
  
  if raydiry<0 then
   stepy=-1
   sidedisty=(rayy-mapy)*ddy
  elseif raydiry>0 then
   stepy=1  
   sidedisty=(mapy+1-rayy)*ddy
  else
   stepy=0
   sidedisty=20000
  end
  
  local osdx=sidedistx
  while hit==0 do
   if sidedistx<sidedisty then
    osdx=sidedistx
    sidedistx+=ddx
    mapx+=stepx
    side=0
   else
	   sidedisty+=ddy
    mapy+=stepy
    side=1
   end
  
   --side==0 -> blue
   --side==1 -> red/brown 
   
  if world[mapy][mapx]>0 then
    hit=1
    texidx=world[mapy][mapx]
   end
  end
  
  local perpwalldist=0
  
  if side==0 then
   perpwalldist=(mapx-rayx+
    (1-stepx)/2)/raydirx
  else
   perpwalldist=(mapy-rayy+
    (1-stepy)/2)/raydiry
  end
  zbuf[x]=perpwalldist
  
  local lheight=flr(128/perpwalldist)
--  local wheight=0--world[mapy][mapx]/perpwalldist
  local dstart=-lheight/2+64
  local dend=flr(lheight/2+64)

  if (dend==nil) dend=128
--[[  if x==52 then
   msg=""..(128/perpwalldist)
  end]]
--  line(52,0,52,128,14)
  -- hack for being very close
  -- to the wall. doesn't quite
  -- work
  if dstart>dend then
   dstart=0
   dend=128
  end
  if (dend<0) dend=h
  
  local wallx=0
  if side==0 then
   wallx=rayy+perpwalldist*raydiry
  else
   wallx=rayx+perpwalldist*raydirx
  end
  wallx-=flr(wallx)
  
  local texx=flr(wallx*16)
  local dcol=min(15,flr((dend-dstart)/2))
--	 if (side==0) dcol-=2
  local p=max(0,15-dcol)
  palette(p)  
  sspr(texidx*16+texx,0,1,16,x,dstart,1,dend-dstart+1)
   flip()
  --pal()
  --pset(x,32,dcol)
  
  local h=128
  
  -- draw every other vertical line
  local dend10=dend--+10
  if x%2==0 and dend10<h then
--   local dendplusten=dend+10
   add(floors,
    {
     x,
     check%2,
     dend10,
     raydirx,
     raydiry,
     flr(max(
      detail_limit_table[x],
      dend10))})
   check+=1
  end
 end
 reset_palette()
 floor_cast(floors,world,player,dist_table,detail_limit_table)

 ce_heap_sort(sprites,player)
 for _,s in pairs(sprites) do
  if s.flat then
   draw_flat_sprite(s,player,zbuf)
  else
   draw_billboard_sprite(s,player,zbuf)
  end
 end
 
 reset_palette()
 local par_col={}
 par_col[0]=4
 par_col[1]=9
 par_col[2]=10
 par_col[3]=10
 par_col[4]=7
 par_col[5]=7

 for _,s in pairs(particles) do
  s.z+=0.3
  s.life-=1
  if s.z>30 or s.life==0 then
   s.z=-30+rnd(4)
   s.life=150+flr(rnd(50))
  end
  
  local s_x=s.x-player.pos.x
  local s_y=s.y-player.pos.y
  local invdet=1/(cam.x*dr.y-cam.y*dr.x)
  
  local tfx=invdet*(dr.y*s_x-dr.x*s_y)
  local tfy=invdet*(-cam.y*s_x+cam.x*s_y)
  local scr_x=64*(1+tfx/tfy)
  local scr_y=64-(s.z/tfy)
--  int drawstarty = -spriteheight / 2 + h / 2 + vmovescreen;
  if tfy>0 and tfy<128 then
--   msg=">> "..(tfy/tfx)
   local sz=
    flr(clamp(4-sqrt(s_x*s_x+s_y*s_y),0,3))
   rectfill(
    scr_x,
    scr_y,
    scr_x+sz,
    scr_y+sz,
    par_col[clamp(flr(s.life/20),0,5)])
  end
 end

--[[ local bx=113
 line(0,32,128,32,7)
 line(0,64,128,64,7)
 line(0,96,128,96,7)

-- line(bx,0,bx,128,8)]]
 local cx=64
 local cy=64
 reset_palette()
-- sspr(0,32,32,32,cx+sin(timer/100)*8,cy+sin(timer/50)*10,64,64)
-- sspr(32,32,32,24,cx+sin((timer-3)/100)*8,cy+56+sin((timer-3)/50)*10,64,64)
end

function floor_cast(floors,world,player,dist_table,detail_limit_table)
 local h=128
 local px=player.pos.x
 local py=player.pos.y
 for _,f in pairs(floors) do
  local x=f[1]
  local check=f[2]
  local dend=f[3]
  local raydirx=f[4]
  local raydiry=f[5]
  local start_dither=f[6]    
--  local start_dither=detail_limit_table[x]
  
--  for y=h-check%2,dend+10,-2 do
  --653 to beat
  local curdist=0
  local cfloorx=0
  local cfloory=0
  local floortex=0
  local floortexx=0
  local floortexy=0
  
  local ey=0
  
  rectfill(x,128-start_dither,x+2,128-(dend),1)
     flip()
  for y=start_dither-check,dend+5,-2 do
   curdist=dist_table[y]

   cfloorx=curdist*raydirx+px
   cfloory=curdist*raydiry+py

--[[   local floortex=1+peek(0x4300+
    flr(cfloory)*32+flr(cfloorx))]]

--   pset(x,128-cfloory,14)
--   print(">"..y,64,80,15)
--   local floortex=world[flr(cfloory)][1]
   floortex=abs(world[flr(cfloory)][flr(cfloorx)])
   
   floortexx=(cfloorx*16)%16
   floortexy=(cfloory*16)%16
   local tcol=sget(floortex*16+floortexx,floortexy)

   pset(x,y,tcol)   
   flip()
   if floortex%16==4 then
    local trcol=sget(floortexx+32,floortexy)
    pset(x,128-y,trcol)
       flip()
   end
--   pset(x,128-y,sget(floortexx%16,floortexy%16))
  end
  for y=h-check,start_dither,-2 do
--  for y=h-check,dend,-2 do
   curdist=dist_table[y]

   cfloorx=curdist*raydirx+px
   cfloory=curdist*raydiry+py

--[[   local floortex=1+peek(0x4300+
    flr(cfloory)*32+flr(cfloorx))]]
   floortex=abs(world[flr(cfloory)][flr(cfloorx)])
   floortexx=(cfloorx*16)%16
   floortexy=(cfloory*16)%16
   local tcol=sget(floortex*16+floortexx,floortexy)

   rectfill(x,y,x+3,y,tcol)
      flip()
   if floortex%16==4 then
    local trcol=sget(floortexx+32,floortexy)
    rectfill(x,128-y,x+3,128-y,trcol)
       flip()
   end
--   line(x,y,x+3,y,sget(floortexx,floortexy))
--   pset(x,y, sget(floortexx,floortexy))
--    rectfill(x,128-y,x+1,128-y,sget(floortexx%16,floortexy%16))
--    pset(x,128-y,sget(floortexx%16,floortexy%16))
  end
--[[  if floortex%16==4 and ey>0 then
   rectfill(x,128-start_dither,x+3,ey+5,1)
  end]]
 end
end

local function dot_product(a,b)
 return a.x*b.x+a.y*b.y
end

local function len(a)
 return sqrt(a.x*a.x+a.y*a.y)
end

function acos(x)
 return atan2(x,-sqrt(1-x*x))
end

function lerp(a,b,percent)
 return (b-a)*percent+a
end

function draw_billboard_sprite(s,player,zbuf)
 local pos=player.pos
 local dr=player.dr
 local cam=player.cam
 
 local tex_width=32
 local s_x=s.pos.x-pos.x
 local s_y=s.pos.y-pos.y
 
 local s_dist=
  sqrt(s_x*s_x+s_y*s_y)

 local invdet=1.0/
  (cam.x*dr.y-
   cam.y*dr.x
  )
 local t_x=invdet*(
  dr.y*s_x-
  dr.x*s_y
 )
 local t_y=invdet*(
 -cam.y*s_x+
  cam.x*s_y
 )
--  if t_y>0 and t_y<128 then
 
 local sscr_x=flr(64*(1+t_x/t_y))
 local s_height=flr(abs(128/t_y))

 local ds_y=-s_height/2+64
 
 local s_width=s_height
 local ds_x=-s_width/2+sscr_x
 if ds_x<0 then
  ds_x=0
 end
 local de_x=s_width/2+sscr_x
 if (de_x>=128) de_x=127
 
 if t_y>0 and t_y<128 then
 
 -- new slighlty faster way
--[[  local visstart=-1
  local visend=-1
  local texstart=0
  local texend=(de_x-(-s_width/2+sscr_x))*32/s_width
  local setstart=false
  local visible=false
  for i=ds_x,de_x do
   if zbuf[flr(i)]>s_dist then
    visible=true
    if visstart==-1 then
     visstart=i
     texstart=(i-(-s_width/2+sscr_x))*32/s_width
     setstart=true
    end
   else
    if setstart and visend==-1 then
     visend=i
     texend=(i-(-s_width/2+sscr_x))*32/s_width    
    end
   end
  end
  if (visstart==-1) visstart=ds_x
  if (visend==-1) visend=de_x
  
  if visible then
   sspr(texstart,64,texend-texstart,32,visstart,ds_y,visend-visstart,s_height)
  end]]
 -- old, slower way
 
--[[  local foo=dot_product(dr,s.dr)/
  (len(dr)*len(s.dr))]]
  
  local foo=(s.a-player.a)
  if foo>360 then
   foo-=360
  elseif foo<0 then
   foo+=360
  end
  msg="a="..foo
  local rot_tex_idx=0
  
  if foo<25 or foo>335 then
   rot_tex_idx=32
  elseif foo>=25 and foo<155 then
   rot_tex_idx=64
  elseif foo>=155 and foo<205 then
   rot_tex_idx=96
  end
  
  palette(clamp(flr(s_dist-2),0,15))
  for i=ds_x,de_x do


   if zbuf[flr(i)]>s_dist then
    local texx=(
     i-(-s_width/2+sscr_x))*31 /s_width
    
    sspr(rot_tex_idx+texx,64,1,32,i,ds_y,1,s_height)
       flip()
   end
  end
 end
end

function draw_flat_sprite(s,player,zbuf)
 local pos=player.pos
 local dr=player.dr
 local cam=player.cam
 local a=s.a
 
 local tex_width=15
 local s_x=s.pos.x-pos.x
 local s_y=s.pos.y-pos.y
-- local se_x=(s.pos.x+1)-pos.x
-- local se_y=s.pos.y-pos.y
 local se_x=(s.pos.x-sin(a/360))-pos.x
 local se_y=(s.pos.y+cos(a/360))-pos.y
 
 local s_dist=
  sqrt(s_x*s_x+s_y*s_y)
 palette(min(15,flr(s_dist)))
  
 local invdet=1.0/
  (cam.x*dr.y-
   cam.y*dr.x
  )
 local t_x=invdet*(
  dr.y*s_x-
  dr.x*s_y
 )
 local te_x=invdet*(
  dr.y*se_x-
  dr.x*se_y
 )
 local t_y=invdet*(
 -cam.y*s_x+
  cam.x*s_y
 )
 local te_y=invdet*(
 -cam.y*se_x+
  cam.x*se_y
 )
 
 local sscr_x=flr(64*(1+t_x/t_y))
 local sscre_x=flr(64*(1+te_x/te_y))
 local s_height=flr(abs(128/t_y))
 local se_height=flr(abs(128/te_y))

 local ds_y=-s_height/2+64
 local dse_y=-se_height/2+64
 
 --local s_width=s_height
 
 local ds_x=sscr_x
 local de_x=sscre_x
 local tx_off=0
 local txe_off=tex_width
 
 if ds_x>de_x then    
  de_x,ds_x=ds_x,de_x
  ds_y,dse_y=dse_y,ds_y
  s_height,se_height=se_height,s_height
 end
 
 if ds_x<0 then
  local percent=abs(ds_x/(de_x-ds_x))
  tx_off=lerp(0,tex_width,percent)
  ds_y=lerp(ds_y,dse_y,percent)
  s_height=lerp(s_height,se_height,percent)
  ds_x=0
 end

 if de_x>=128 then
  local percent=1-abs((de_x-127)/(de_x-ds_x))
  txe_off=lerp(0,tex_width,percent)
  dse_y=lerp(ds_y,dse_y,percent)
  se_height=lerp(s_height,se_height,percent)
  de_x=127
 end
 
 if t_y>0 and t_y<128 
 and te_y>0 and te_y<128 then
--  msg=""..ds_x.."->"..de_x
  for i=ds_x,de_x do
   if zbuf[flr(i)]>s_dist then
    local percent=(i-ds_x)/(de_x-ds_x)
    local s=lerp(ds_y,dse_y,percent)
    local height=lerp(s_height,se_height,percent)
    --local texx=(
    -- i-(-s_width/2+sscr_x))*31 /s_width
    local texx=lerp(tx_off,txe_off,percent)
    sspr(texx,0,1,16,i,s,1,height)
--    sspr(texx,64,1,32,i,ds_y,1,s_height)
   end
  end
 end
end

function reset_palette()
 palette(0)
end

function palette(z)
  memcpy(0x5f00,0x5000+16*z,16)
end

function create_palettes()
 for z=0,7 do
  for i=0,15 do
   local col=sget(i,z+96)
   if i==12 then
    col=bor(0x80,i)
   end
   poke(0x5000+16*z+i,col)
  end
 end
end

-- originally by @casualeffects
function ce_heap_sort(data,player)
 if (#data==0) return
 local n = #data
 local p_pos=player.pos
 
 for d in all(data) do
  local dx=(d.pos.x-p_pos.x)/10
  local dy=(d.pos.y-p_pos.y)/10
  d.key=dx*dx+dy*dy
 end

 -- form a max heap
 for i = flr(n / 2) + 1, 1, -1 do
  -- m is the index of the max child
  local parent, value, m = i, data[i], i + i
  local key = value.key 
  
  while m <= n do
   -- find the max child
   if ((m < n) and (data[m + 1].key < data[m].key)) m += 1
   local mval = data[m]
 
   if (key < mval.key) break
   data[parent] = mval
   parent = m
   m += m
  end
  data[parent] = value
 end 

 -- read out the values,
 -- restoring the heap property
 -- after each step
 for i = n, 2, -1 do
  -- swap root with last
  local value = data[i]
  data[i], data[1] = data[1], value

  -- restore the heap
  local parent, terminate, m = 1, i - 1, 2
  local key = value.key 
  
  while m <= terminate do
   local mval = data[m]
   local mkey = mval.key
   if (m < terminate) and (data[m + 1].key < mkey) then
    m += 1
    mval = data[m]
    mkey = mval.key
   end
   if (key < mkey) break
   data[parent] = mval
   parent = m
   m += m
  end  
  
  data[parent] = value
 end
end
__gfx__
11111111111111115111511311b1153b11222111111222111111111111111111ddddddd5dddddddd112d3111111222115d5d515d5d5d5d5dddddddd5dddddddd
19a29a59a29a29a11311131b11311131411111442211511419a29a59a29a29a1dd5d6dddddd5ddd541d3b344221151141111111111111111dd5d6dddddd5ddd5
14954944954954a11331111b11311111221114222221114214954944954954a1dddddddddddddddd221b3422222111425d6761111d676715dddddddddddddddd
14424424454424911b31511b5115131122211222222211221442442445442491dddddddd6dddd6dd2223b222222211225dddd155ddddd615dddddddd6dddd6dd
149449449449444113b3111b1113135125211222525211221494494494494441d5ddd5dddddddddd25213222525211225d5d51555d5d5515d5ddd5dddddddddd
14424424425424411b33131313311b1152111525252111121442442442542441dddddddddd5ddd5d52111525252111121115511111151151dddddddddd5ddd5d
12222222222222211b3b111331311b11111111111111111112222222222222215d6ddddddddddddd111111111111111111511111111111115d6ddddddddddddd
14245242542442411b3315111111131111442211144222111424524254244241dddd5ddd5ddddddd11442211143d3311551155d667671556dddd5ddd5ddddddd
14444444444dd14113b3111311531351142222144222221114444444444dd141d5dddddddddd6d5d142222144223b2115511555555561555d5dddddddddd6d5d
12222222222211211b3135131511111112222512222221111222222222221121ddddddd6dddddddd12222512222b3111d51ddddddd5515d5ddddddd6dddddddd
1111111111111111131b31b11111515111252112222211441111111111111111ddddd5dddddddddd11252112222231445d11ddddddd5115dddddd5dddddddddd
1221221221221221151331b53111113121111122525114221221221221221221dd5dddddd5ddddd52111112252511422d51111111d5511d5dd5dddddd5ddddd5
1242452552441441111513313151113151111125251112221242452552441441d6dddd6dddd5dddd51133125251112221111111151111111d6dddd6dddd5dddd
121144144145114151111111111131b311442112511411521211441441451141dddddddddddddddd1143b11251141152555d6d6711555d55dddddddddddddddd
1111211121121111115311151131313b142222111142211111112111211211115d5ddddd5ddddddd14223211114221115555d5d61155d6d55d5ddddd5ddddddd
11111111111111111113311111b1113b12222211112222111111111111111111dddd5dddddd6d5d612222211112222111111111511111d6ddddd5dddddd6d5d6
2222222245244222112d31111112221155555551d555555511c111111ccd1111111111111111111d1111111111111111dddddddddddddddd111111111111111d
222245224422425241d3b34422115114dddddd51dddddddd1cc11111dcccd11115d15d15d15d15dd19a29a59a29a29a1dddddddddddddddd155555555555555d
2452442224222242221b34222221114276676651d6767666ccdc1111ccdccccc15d15d15d15d15dd14954222222454a1dddddddddddddddd155555d55555555d
54524222222252222223b2222222112267667651d6676766111ccccccdddcc1115d15d15d15d15dd14422c1cc1c22491dddddddddddddddd15555d555555555d
444242445225522525213222525211226676765156766776111c1111c1111c1115d15d15d15d15dd14942c5cc5c2444166666666666666661555d555555d555d
44522224442444245211152525211112676676515766766611ccd11dc1111c1115d15d15d1dd15dd1442251551522441dddddddddddddddd155d555555d5555d
442222222424442211111111111111116776765156766767ccddc11cc111cccc15d15d15515d15dd12222c5cc5c222216666666666666666155555555d55555d
242552422422422211442211143d33117667765156667676c11dcccccc11cc1c15515d15d15d15dd14242c5cc5c242416666666666666666155555555555555d
2224524424122221142222144223b2117767675156766667c1111c11dccccd1c15d15d15d15d15dd14441c5cc5c1d1417777777777777777155555555555555d
222442442222441212222512222b31116676675156676676c1111c111111c11c15d15d15d1dd155d12221c1cc1c1112166666666666666661555555555d5555d
121442222121442211252112222231446766775156766766cc11cc111111ccc115d15d15d15d15dd11111111111111117777777777777777155555555d55555d
2224421441124224211111225251142267767651576677671ccccccccd111ccc15d15d15d15d15dd1221221221221221777777777777777715555555d555555d
421221124412214451133125251112226767765156767676cc1dcd1dccd1ccd11551551d5155155d124242142144144177777777777777771555555d5555555d
42244221442242441143b1125114115266666651566666661c1c11111ccccd11155155155155155d121142142145114177777777777777771555d5555555555d
12144112222441241422321111422111d7dd75155dd6dd6d11cc11111dccd111155155155155156d11112111211211117777777777777777155d55555555556d
21112111141411121222221111222211111111111111111111c111111cc1111111d11d11d11d11d611111111111111117777777777777777ddddddddddddddd6
cccccccccccccccccccccccccccccccc666d6ddd666d66d61242424214242421010010150010010066fff66f666fff6611294441111911114424443422444224
ccccccccccccccccccccccccccccccccdddddddddddddddd149494a219494942005000001005000555dd5555555dd55511244941411491115445244444344454
cccccccccccccccccccccccccccccccc111111111111111114a494a219494a421010010100000100005500000005500011244941411449114452244244422444
cccccccccccccccccccccccccccccccc00000000000000001494a4a21a494a420000100001100001101101111101101111224941491244914422134454421444
cccccccccccccccccccccccccccccccc01010100100010101494a492194a49420500050100001000101101111101101111224441441149414444443452445443
cccccccccccccccccccccccccccccccc111111111111111114949492194949420001000010510050101101111101101111122441249124994224544421244224
ccccccccccccccc111cccccccccccccc212212122121222114949142191949425100010100000001101101111101101111122441244112442122444422242124
cccccccccccccc11e1cccccccccccccc52252155d212d2d214911142191119420001500050111000101101010101101191112241224912242214412444425214
ccccccccccc1111ee11111cccccccccc55d5d515512155551491d142191d19421500001000000050101101010101101044111241124411244444422444444444
ccccccccccc1ee11ee1ee11ccccccccc5555155d5515555512915142191519420001000000100001001100000001100049111244124441222444444445422434
ccccccccccc1e1e1e11111111ccccccc5d555d555dddd5d512911142192119421000150010010100d5115d555d5115d544411124112241221244244424411442
ccccccccccc11111eee11e1111cccccc555dd55ddddd5ddd12949442194449420150001005000005666666666666666624441111111221222243442124422442
cccccccccccc11ee1eee1ee1e1cccccc5d5ddddddddddddd12949442124449420000000001050001111111111111111122441111111111112444341244444424
cccccccccccc1eee1eee1ee1e11ccccc555dddd5555dd55512949492124949420101001000000100555555555555555522244144499111114424424444344444
cccccccccccc11ee1eeee1e1ee1ccccc5155d555d55551d512929292122929225050000050010010ff65d6656f6d55d612224124444911115212443422444224
ccccccccccccc1ee11eee1e1ee1ccccc111115151115111111424242112424210000501000100500f6d56f65d66d5d6f11224412444491114122544221245222
ccccccccccccc1eee1eee111ee1ccccc55555551d555555511c111111ccd1111dd666dd6ddd666dd00000000000000001111111111111111111111111111111d
cccc111ccccccc1ee1eeee1e1e1cccccdddddd51dddddddd1cc11111dcccd11155dd5555555dd55504409909904409901224941249912499155555555555555d
ccc11ee1cccccc1eee1eee1e1e1ccccc76676651d6767666ccdc1111ccdccccc00110000000110000990aa0490990aa01111111111111111155555d55555555d
ccc1e1e1ccccc11eee1eee1e1e1ccccc67667651d6676766111ccccccdddcc1110550111110550110000000000000000244412444412444115555d555555555d
cc1ee1e11cccc1eeeeeeee1e1e1ccccc6676765156766776111c1111c1111c111055011111055011000000000000000011111111111111111555d555555d555d
cc1e1ee11ccc11eeeeeeeeeee221cccc676676515766766611ccd11dc1111c1110550111110550110330a902209901101111112244412444155d555555d5555d
cc1eeee11ccc11eeeeeeeeee2221cccc6776765156766767ccddc11cc111cccc10550111110550110bb0a90440a90d101111111111111111155555555d55555d
ccc1eee111c111eeeeeeeeee2221cccc7667765156667676c11dcccccc11cc1c105501010105501100000000000000004441244441111112155555555555555d
ccc1eeee11c111eeeeeeeeee2221cccc7767675156766667c1111c11dccccd1c105501010105501000000000000000001111111111111111155555555555555d
ccc1eeee11111eeeeeeeeeee2221cccc6676675156676676c1111c111111c11c005500000005500004401109909909a012244412444124441555555555d5555d
ccc11eeee1111eeeeeeeeee22221cccc6766775156766766cc11cc111111ccc155dd5555555dd5550990dd0a909a09a01111111111111111155555555d55555d
cccc1eeeee111eeeeeeeee222221cccc67767651576677671ccccccccd111ccc6d66d6d6d6d66d6d0000000000000000441111111244412215555555d555555d
ccccc1eeeeeeeeeeeeeeee22221ccccc6767765156767676cc1dcd1dccd1ccd11111111111111111000000000000000011111111111111111555555d5555555d
cccccc1eeeeeeeeeeeeee222221ccccc66666651566666661c1c11111ccccd115555555555555555099044099022099024444124444124411555d5555555555d
cccccc11eeeeeeeeeeee2222211cccccd7dd75155dd6dd6d11cc11111dccd11166ddddddd6dddddd0aa0aa09a0440a902222222222222222155d55555555556d
ccccccc1eeeeeeeeeee2222221cccccc111111111111111111c111111cc111116dddd6ddddddddd600000000000000004444444444444444ddddddddddddddd6
cccc1111ccccccccccccc11111ccccccccccccc111ccccc155cccccccccccccccccc1111ccccccccccccc11111cccccccccccccccccccc511ccccc111ccccccc
cccc155511cc111111c115f551ccccccccccccc15f55cc155fcccccccccccccccccc155511cc111111c1155551ccccccccccccccccccccf551cc55f51ccccccc
cccc155ff5115555551555f51cccccccccccccc15ff5551559cccccccccccccccccc155555115555551555551ccccccccccccccccccccc9551555ff51ccccccc
ccccc15ff9155555555519f51cccccccccccccc159ff5555555cccccccccccccccccc15555555555555551151cccccccccccccccccccc5555555ff951ccccccc
ccccc15f99155555555551951cccccccccccccc1599555551155ccccccccccccccccc15111555555555551151ccccccccccccccccccc5511555559951ccccccc
ccccc15011511115555511151cccccccccccccc155555551aa155cccccccccccccccc15111555555555555111cccccccccccccccccc551aa155555551ccccccc
cccccc11151aaaa15551aaa1ccccccccccccccc115555551a0155ccccccccccccccccc111555555555555555ccccccccccccccccccc5510a155555511ccccccc
cccccc11151aa0a15551a0a1ccccccccccccccc115555551a015555ccccccccccccccc111555555555555555ccccccccccccccccc555510a155555511ccccccc
ccccccc1151aa0a15551a0a1ccccccccccccccc115555551aa155500ccccccccccccccc11555555555555555cccccccccccccccc005551aa155555511ccccccc
ccccccc1151aaaa15551aaa15cccccccccccccc115555551aa155000ccccccccccccccc115555555555555555ccccccccccccccc000551aa155555511ccccccc
ccccccc115511115115511155cccccccccccccc11555555511555050ccccccccccccc11115555555555555551ccccccccccccccc05055511555555511ccccccc
ccccccc111555555005555555cccccccccccccc11155555555555055ccccccccccccccc1115555555555555111cccccccccccccc11055555555555111ccccccc
ccccccc11100555000055505ccccccccccccccc11155555555550555ccccccccccccccc11155551111555511cccccccccccccccc11505555555555111ccccccc
ccccccc11110000055000015ccccccccccccccc11115555555005515cccccccccccccc1111111111111111111ccccccccccccccc11150055555551111ccccccc
cccccccc111111555555115ccccccccccccccccc111115555555511cccccccccccccc1cc111111111111111cccccccccccccccccc111155555551111cccccccc
ccccccc111111111155555ccccccccccccccccc1111111111115ccccccccccccccccccc111111111111111cccccccccccccccccccccc11155511111ccccccccc
ccccccc111111115555555ccccccccccccccccc1111111111155ccccccccccccccccccc111111115555551cccccccccccccccccccc111115555555cccccccccc
cccccc11111555555555555ccccccccccccccc111115555555555ccccccccccccccccc11111555555555555cccccccccccccccccc11555555555555ccccccccc
ccccc1111155555555555555ccccccccccccc11111555555555555ccccccccccccccc1111155555555555555cccccccccccccccc1155555555555555cccccccc
ccccc11111555555555555555cccccccccccc111115555555555555cccccccccccccc11111555555555555555cccccccccccccc111555555555555555ccccccc
ccccc111115555555555555555ccccccccccc111115555555555555cccccccccccccc111115555555555555555ccccccccccccc1115555555555555555cccccc
cccc1111115555555555555555cccccccccc11111155555555555555cccccccccccc1111115555555555555555ccccccccccccc1115555555555555555cccccc
cccc1111115555555555555555cccccccccc11111155555555555555cccccccccccc1111115555555555555555cccccccccccc11115555555555555555cccccc
cccc1111115555555555555555cccccccccc111111555555555555555ccccccccccc1111115555555555555555cccccccccccc11115555555555555555cccccc
cccc11111155555555555555555ccccccccc111111555555555555555ccccccccccc11111155555555555555555cccccccccc1111155555555555555555ccccc
ccc111111115555555555555555cccccccc1111111555555555555555cccccccccc111111115555555555555555cccccccccc1111155555555555555555ccccc
ccc111111115555555555555555cccccccc1111111155555555555555cccccccccc111111115555555555555555cccccccccc1111115555555555555555ccccc
ccc111111115555555555555555cccccccc11111111555555555555555ccccccccc111111115511111155555555ccccccccc11111115555555555555555ccccc
ccc111111115555555555555555cccccccc11111111555555555555555ccccccccc111111111111111111115555ccccccccc11111115555555555555555ccccc
ccc111111111111115555555555cccccccc11111111111111555555555ccccccccc111111111111111111111555cccccccc111111111111115555555555ccccc
ccc111111111111111111115555cccccccc111111111111111111115555cccccccc111111111111111111111155cccccccc111111111111111111115555ccccc
ccc111111111111111111111155cccccccc111111111111111111111155cccccccc111111111111111111111115cccccccc111111111111111111111155ccccc
0123456689abcdef11294441111911114424443422444224ddddd555d5dddddd5555155515551555000000000000000022222222222222222222222222222222
012325562493dde911244941411491115445244444344454dd5d6d5d5dd5ddd55d775d775d775d77000000000000000020000000000000000000000002222222
0123255d2493d52411244941411449114452244244422444ddddd5d5d5dddddd5d665d665d665d66000000000000000020000000500000000000000022222222
0111215d2243d52411224941491244914422134454421444dd5ddddddd6dd6dd55dd55dd55dd55dd000000000000000020000000000500000000002222222222
011111151221152211224441441149414444443452445443d5d5d5dddddddddd1555155515551555000000000000000020000050000000000000002222222222
001111111221112211122441249124994224544421244224dd5ddddddd5d5d5d5d775d775d775d77000000000000000020000000000000222200062226222222
0010111112211122111224412441124421224444222421245d65ddddd555d5dd5d665d665d665d66000000000000000020000000500002222200662226622222
000000000000000091112241224912242214412444425214dd555ddd5d5d5ddd55dd55dd55dd55dde0000000e000000020000500000002222200662226622222
000000000000000044111241124411244444422444444444d555d5ddd5d5dd5d1555155515551555000000000000000020000000000002222200660006602222
0000000000000000491112441244412224444444454224345d5d5ddddd555ddd5d775d775d775d77000000000000000020050000000000222000660006600222
000000000000000044411124112241221244244424411442d5ddd56dddd555dd5d665d665d665d66000000000000000020000500220000000000660006600222
000000000000000024441111111221222243442124422442dd5dddd6d5dd5dd555dd55dd55dd55dd000000000000000020000000222000000000000000000222
000000000000000022441111111111112444341244444424d6ddd56dddd5d5dd1555155515551555000000000000000022000000222000000000000000002222
000000000000000022244144499111114424424444344444dddd5d5ddddd5d5d5d775d775d775d77000000000000000022000000022200000000000000002222
0000000000000000122241244449111152124434224442245d5dd5dd5dddd5dd5d665d665d665d66000000000000000022000000022220000000222222002222
0123456789abcdef11224412444491114122544221245222dddd5d5dddd6d5d655dd55dd55dd55dd000000000000000022200000002222000002222222222222
00000000000000001111111111111111111111111111111d11111111111111110000000000000000000000000000000022222000000222000002222222222222
04409909904409901224941249912499155555555555555d10010010010010010000000000000000000000000000000022222200000000000002222222222222
0990aa0490990aa01111111111111111155555d55555555d11111111111111110000000000000000000000000000000022222220000000000002222222222222
0000000000000000244412444412444115555d555555555d12512512512512510000000000000000000000000000000022222226666006600662222222000222
000000000000000011111111111111111555d555555d555d15d15d15d15d15d10000000000000000000000000000000022222200000000000000020000000022
0330a902209901101111112244412444155d555555d5555d15d15d15d1dd15d10000000000000000000000000000000022222200000000000000000000000022
0bb0a90440a90d101111111111111111155555555d55555d15d15d15515d15d10000000000000000000000000000000022220000000500000000000022200002
00000000000000004441244441111112155555555555555d10919019019910910000000000000000000000000000000022200000500000000000000222222002
00000000000000001111111111111111155555555555555d19910910019019910000000000000000000000000000000020000000000000000000000222222002
04401109909909a012244412444124441555555555d5555d1a01aa10a1001a010000000000000000000000000000000020005005005000002222002222222002
0990dd0a909a09a01111111111111111155555555d55555d10019019910910010000000000000000000000000000000020000000000000022222222222220002
0000000000000000441111111244412215555555d555555d15d15d15d15d15d10000000000000000000000000000000020000050000000022222222222220002
000000000000000011111111111111111555555d5555555d1551551d515515510000000000000000000000000000000020000000000220000222222222200002
099044099022099024444124444124411555d5555555555d15515515515515510000000000000000000000000000000020000000002200000000044000000022
0aa0aa09a0440a902222222222222222155d55555555556d15515515515515610000000000000000000000000000000022222222222000000000044000000220
00000000000000004444444444444444ddddddddddddddd611d11d11d11d11d10000000000000000000000000000000022222222222222222222222222222200