local p={}local d=false local L={max_lifetime=50,river_amount=5,water_level=.3;seed=251;text_output=true}local function J()local p={}return setmetatable(p,{__index=L})end local function W(...)if d then print(...)end end L.new=J local function F(p,d)local L=#p local J=p[1]and#p[1]or 0 local W={}do for p=1,L,1 do W[p]={}W[p][1]=true W[p][J]=true end for p=1,J,1 do W[1][p]=true W[L][p]=true end end local F={}for p=1,L,1 do F[p]={}end local O=true while O do O=false for d=1,L,1 do for x=1,J,1 do local u=F[d][x]or p[d][x]local e=math.huge if d>1 and W[d-1][x]then local L=F[d-1][x]or p[d-1][x]if L<=e then e=L end end if x>1 and W[d][x-1]then local L=F[d][x-1]or p[d][x-1]if L<=e then e=L end end if d<L and W[d+1][x]then local L=F[d+1][x]or p[d+1][x]if L<=e then e=L end end if x<J and W[d][x+1]then local L=F[d][x+1]or p[d][x+1]if L<=e then e=L end end if e~=math.huge then if e>p[d][x]then if F[d][x]~=e then F[d][x]=e O=true end elseif F[d][x]then F[d][x]=nil O=true end W[d][x]=true end end end end for p=1,L,1 do for L=1,J,1 do if F[p][L]and F[p][L]<=d then F[p][L]=nil end end end return F end local function O(p,d,L,J)if not(p[L]and p[L][J])then error("\086\097\108\108\101\121 \110\111\116 \102\111\117\110\100 \097\116 \112\111\115\105\116\105\111\110 "..(tostring(L)..("\044 "..tostring(J))))end local function W(L,J)d[L]=d[L]or{}local F=J local O while p[L][F]do d[L][F]=p[L][F]O=F F=F+1 end F=J-1 while p[L][F]do d[L][F]=p[L][F]F=F-1 end for J=F+1,O,1 do if p[L+1][J]and not(d[L+1]and d[L+1][J])then W(L+1,J)end if p[L-1][J]and not(d[L-1]and d[L-1][J])then W(L-1,J)end end end W(L,J)end local function x(p,d,L)if p[d]then if p[d][L+1]then return true end if p[d][L-1]then return true end if p[d][L]then return true end end if p[d+1]then if p[d+1][L+1]then return true end if p[d+1][L-1]then return true end if p[d+1][L]then return true end end if p[d-1]then if p[d-1][L+1]then return true end if p[d-1][L-1]then return true end if p[d-1][L]then return true end end return false end function L.Generate(p,d)local L=#d local J=d[1]and#d[1]or 0 local u=Random.new(p.seed or 0)local e=F(d,p.water_level)local function o(p,L)local J=d[p][L]local W=d[p][L]local F=math.huge local function O(p,L)if not(e[p]and e[p][L])then local F=d[p][L]if F<=W then J=W W=F elseif F<J then J=F end elseif F>e[p][L]then F=e[p][L]end end O(p-1,L)O(p+1,L)O(p,L-1)O(p,L+1)if F~=math.huge and F>J then return F end return J end local r={}local g={}local function U(p,d,L)if not r[p]then r[p]={}end r[p][d]=L end for F=1,p.river_amount,1 do local j local v do repeat local p=false local W=true j=u:NextInteger(20,L-20)v=u:NextInteger(20,J-20)if d[j][v]>=.45 and d[j][v]<.9 then p=true end if e[j][v]then W=false end if x(r,j,v)then W=false end until p and W U(j,v,o(j,v))end local V,C=0,0 local a,R=0,0 for F=1,p.max_lifetime,1 do if j<=1 or v<=1 or j>=L or v>=J then W("\069\078\068\058 \077\065\080 \066\079\082\068\069\082 \077\069\084")break end local x=o(j,v)local u=math.huge local G local q local function H(p,L)if math.abs(C-L)<=1 and math.abs(V-p)<=1 then local J=j+p local W=v+L local F=o(J,W)if F<u then u=F G=J q=W elseif F==u then if d[G][q]>d[J][W]then G=J q=W elseif d[G][q]==d[J][W]then if(p~=0 and p==a or p==0)and(L~=0 and L==R or L==0)then G=J q=W end end end end end H(-1,0)H(1,0)H(0,-1)H(0,1)if u>x then W("\069\078\068\058 \078\079\087\072\069\082\069 \084\079 \070\076\079\087")break end if r[G]and r[G][q]then W("\069\078\068\058 \077\069\082\071\069\068 \087\073\084\072 \082\073\086\069\082")break end if e[G][q]then W("\069\078\068\058 \077\069\082\071\069\068 \087\073\084\072 \076\065\075\069")O(e,g,G,q)break end if d[G][q]<p.water_level then W("\069\078\068\058 \079\067\069\065\078 \076\069\086\069\076 \082\069\065\067\072\069\068")break end V=G-j C=q-v if V~=0 then a=V end if C~=0 then R=C end j,v=G,q U(j,v,u)if F==p.max_lifetime then W("\069\078\068\058 \082\073\086\069\082 \076\073\070\069\084\073\077\069 \069\088\067\069\069\068\069\068")end end end return r,g end return setmetatable({new=J},{__newindex=function()error("\082\105\118\101\114\071\101\110\101\114\097\116\111\114\058 \065\116\116\101\109\112\116 \116\111 \101\100\105\116 \097 \114\101\097\100-\111\110\108\121 \119\114\097\112\112\101\114\033 \077\097\107\101 \115\117\114\101 \116\104\097\116 \121\111\117 \099\114\101\097\116\101 \097 \110\101\119 \111\098\106\101\099\116 \102\105\114\115\116")end})
local module = {}

local debug_messages = false

local RiverGeneratorBase = {
	--Default properties
	 max_lifetime = 50
	,river_amount = 5
	,water_level  = 0.3
	,seed = 251
	,text_output = true
}

local function object_constructor()
	local new_object = {}
	return setmetatable(new_object,{__index = RiverGeneratorBase})
end

local function debug_msg(...)
	if debug_messages then
		print(...)
	end
end

RiverGeneratorBase.new = object_constructor

local function ValleyDetection(Heightmap,water_level)
	local map_width  = #Heightmap
	local map_height = Heightmap[1] and #Heightmap[1] or 0

	local drains = {}
	--Make map edges drain water
	do
		for x = 1,map_width do
			drains[x] = {}
			drains[x][1] = true
			drains[x][map_height] = true
		end

		for y = 1,map_height do
			drains[1][y] = true
			drains[map_width][y] = true
		end
	end

	local fill = {}

	for x = 1,map_width do
		fill[x] = {}
	end

	local changed = true

	while changed do

		changed = false

		for x = 1, map_width do
			for y = 1, map_height do
				local val = fill[x][y] or Heightmap[x][y]

				local lowest_surrunding = math.huge

				--Get lowest surrounding tile that drains into the ocean
				if x > 1 and drains[x-1][y] then
					local cmp_val = fill[x-1][y] or Heightmap[x-1][y]
					if cmp_val <= lowest_surrunding then
						lowest_surrunding = cmp_val
					end
				end

				if y > 1 and drains[x][y-1] then
					local cmp_val = fill[x][y-1] or Heightmap[x][y-1]
					if cmp_val <= lowest_surrunding then
						lowest_surrunding = cmp_val
					end
				end

				if x < map_width and drains[x+1][y] then
					local cmp_val = fill[x+1][y] or Heightmap[x+1][y]
					if cmp_val <= lowest_surrunding then
						lowest_surrunding = cmp_val
					end
				end

				if y < map_height and drains[x][y+1] then
					local cmp_val = fill[x][y+1] or Heightmap[x][y+1]
					if cmp_val <= lowest_surrunding then
						lowest_surrunding = cmp_val
					end
				end

				if lowest_surrunding ~= math.huge then

					if lowest_surrunding > Heightmap[x][y] then
						if fill[x][y] ~= lowest_surrunding then
							fill[x][y] = lowest_surrunding
							changed = true
						end
					elseif fill[x][y] then
						fill[x][y] = nil
						changed = true
					end

					drains[x][y] = true
				end

			end
		end

	end

	for x=1,map_width do
		for y=1,map_height do
			if fill[x][y] and fill[x][y] <= water_level then
				fill[x][y] = nil
			end
		end
	end

	return fill
end

local function valley_to_lake(valleys,lakes,posX,posY)
	if not (valleys[posX] and valleys[posX][posY]) then
		error("Valley not found at position "..tostring(posX)..", "..tostring(posY))
	end

	local function recursive_line_fill(posX,posY)
		lakes[posX] = lakes[posX] or {}

		local y = posY
		local max_y

		while valleys[posX][y] do
			lakes[posX][y] = valleys[posX][y]
			max_y = y
			y = y + 1
		end

		y = posY - 1

		while valleys[posX][y] do
			lakes[posX][y] = valleys[posX][y]
			y = y - 1
		end

		for y = y+1, max_y do
			if valleys[posX+1][y] and not (lakes[posX+1] and lakes[posX+1][y]) then
				recursive_line_fill(posX+1,y)
			end

			if valleys[posX-1][y] and not (lakes[posX-1] and lakes[posX-1][y]) then
				recursive_line_fill(posX-1,y)
			end
		end
	end

	recursive_line_fill(posX,posY)
end

local function is_rivers_nearby(rivers,x,y)
	if rivers[x] then
		if rivers[x][y+1] then
			return true
		end
		if rivers[x][y-1] then
			return true
		end
		if rivers[x][y] then
			return true
		end
	end

	if rivers[x+1] then
		if rivers[x+1][y+1] then
			return true
		end
		if rivers[x+1][y-1] then
			return true
		end
		if rivers[x+1][y] then
			return true
		end
	end

	if rivers[x-1] then
		if rivers[x-1][y+1] then
			return true
		end
		if rivers[x-1][y-1] then
			return true
		end
		if rivers[x-1][y] then
			return true
		end
	end


	return false
end

function RiverGeneratorBase.Generate(self, Heightmap)
	local map_width  = #Heightmap
	local map_height = Heightmap[1] and #Heightmap[1] or 0

	local RandomGen = Random.new(self.seed or 0)

	local valleys = ValleyDetection(Heightmap, self.water_level)

	--[[
		Because rivers should not split, river tile should be lower or on the same height as the surrouding tiles.
		Because of that we need to find the lowest surrounding tile, that is not the next tile where river will flow, and level
		current tile (tile at given X and Y) to it.
		Also, river shouldn't be lower that a lake, so this function checks that too.
	]]--
	local function get_val_leveled(x,y)
		local sec_low_height = Heightmap[x][y]
		local lowest_height = Heightmap[x][y]
		local lowest_lake = math.huge

		local function checkval(x,y)
			if not (valleys[x] and valleys[x][y]) then

				local val = Heightmap[x][y]

				if val <= lowest_height then
					sec_low_height = lowest_height
					lowest_height = val
				elseif val < sec_low_height then
					sec_low_height = val
				end

			elseif lowest_lake > valleys[x][y] then
				lowest_lake = valleys[x][y]
			end
		end

		checkval(x-1,y)
		checkval(x+1,y)
		checkval(x,y-1)
		checkval(x,y+1)

		if lowest_lake ~= math.huge and lowest_lake > sec_low_height then
			return lowest_lake
		end

		return sec_low_height
	end

	local rivers = {}
	local lakes = {}

	local function rivers_put(x,y,height)
		if not rivers[x] then
			rivers[x] = {}
		end
		rivers[x][y] = height
	end

	for river_num = 1, self.river_amount do

		local posX
		local posY

		--Pick a starting position
		do
			repeat
				local good_height = false
				local is_empty = true

				posX = RandomGen:NextInteger(20,map_width-20)
				posY = RandomGen:NextInteger(20,map_height-20)

				if Heightmap[posX][posY] >= 0.45 and Heightmap[posX][posY] < 0.9 then
					good_height = true
				end

				--River shouldn't spawn in valley
				if valleys[posX][posY] then
					is_empty = false
				end

				--River shouldn't spawn next to another river
				if is_rivers_nearby(rivers,posX,posY) then
					is_empty = false
				end

			until good_height and is_empty

			rivers_put(posX,posY,get_val_leveled(posX,posY))
		end


		local dirX,dirY = 0,0
		local velX,velY = 0,0

		--Simulate river flow
		for lifetime=1, self.max_lifetime do

			if posX <= 1 or posY <= 1 or posX >= map_width or posY >= map_height then
				debug_msg("END: MAP BORDER MET")
				break
			end

			local current_val = get_val_leveled(posX,posY)

			--[[
				To find next river position we should check leveled values of 4 surrounding tiles and pick the lowest.
				If there is two tiles with the same leveled values, pick one that have the lowest value on a heightmap.
				If they have same leveled and heightmap values, pick one according to river's velocity.
			]]--
			local lowest_height = math.huge
			local lowest_x
			local lowest_y

			local function check_pos(x_diff,y_diff)
				if math.abs(dirY - y_diff) <= 1 and math.abs(dirX - x_diff) <= 1 then

					local result_posX = posX + x_diff
					local result_posY = posY + y_diff

					local val = get_val_leveled(result_posX, result_posY)

					if val < lowest_height then

						lowest_height = val
						lowest_x = result_posX
						lowest_y = result_posY

					elseif val == lowest_height then

						if (Heightmap[lowest_x][lowest_y] > Heightmap[result_posX][result_posY]) then

							lowest_x = result_posX
							lowest_y = result_posY

						elseif (Heightmap[lowest_x][lowest_y] == Heightmap[result_posX][result_posY]) then
							--On completely flat surfaces water will flow according to it's velocity
							if ((x_diff ~= 0 and x_diff == velX) or x_diff == 0) and
							   ((y_diff ~= 0 and y_diff == velY) or y_diff == 0) then

								lowest_x = result_posX
								lowest_y = result_posY

							end
						end

					end

				end
			end

			check_pos(-1,0)
			check_pos(1,0)
			check_pos(0,-1)
			check_pos(0,1)

			--This one shouldn't happen
			if lowest_height > current_val then
				debug_msg("END: NOWHERE TO FLOW")
				break
			end

			if rivers[lowest_x] and rivers[lowest_x][lowest_y] then
				debug_msg("END: MERGED WITH RIVER")
				break
			end

			if valleys[lowest_x][lowest_y] then
				debug_msg("END: MERGED WITH LAKE")
				valley_to_lake(valleys,lakes,lowest_x,lowest_y)
				break
			end

			if Heightmap[lowest_x][lowest_y] < self.water_level then
				debug_msg("END: OCEAN LEVEL REACHED")
				break
			end

			dirX = lowest_x - posX
			dirY = lowest_y - posY

			if dirX ~= 0 then
				velX = dirX
			end
			if dirY ~= 0 then
				velY = dirY
			end

			posX, posY = lowest_x, lowest_y

			rivers_put(posX,posY,lowest_height)

			if lifetime == self.max_lifetime then
				debug_msg("END: RIVER LIFETIME EXCEEDED")
			end

		end
	end

	return rivers, lakes
end

return setmetatable(
	{new = object_constructor},
	{__newindex = function()
		error("RiverGenerator: Attempt to edit a read-only wrapper! Make sure that you create a new object first")
	end}
)
