FOV_MRPAS.gd

extends Node
class_name FOV_MRPAS

# TODO: static typing

var _circle_array := []  # to contain a mask to make fov rounded
var last_radius   := 0   # to check if circle mask needs to be re-built

var map

func _clear_fov() -> void:
	for j in range(map.h):
		for i in range(map.w):
			map.fovmap[j][i] = FOVData.HIDDEN

func _init(game_map) -> void:
	map = game_map

	for j in range(map.h):
		map.fovmap.append([])
		for i in range(map.w):
			map.fovmap[j].append(FOVData.HIDDEN)


####################################################################
# 		Helper Functions
#
# nc = no-bounds-check
#- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
func _is_opaque(x:int, y:int) -> bool:
	# TODO: account for transparent tiles. Consider using a callback
	#       much like Rot.js, and to allow varying levels of visibility
	return (x < 0 or x >= map.w or
			y < 0 or y >= map.h or
			map.tilemap[y][x] == MapData.ID_WALL)

func _is_opaque_nc(x:int, y:int) -> bool:
	return map.tilemap[y][x] == MapData.ID_WALL


func _set_visible(x:int, y:int, enable:=true) -> void:
	if x >= 0 and x < map.w and y >= 0 and y < map.h:
		map.fovmap[y][x] = int(enable)

func _set_visible_nc(x:int, y:int, enable:=true) -> void:
	map.fovmap[y][x] = int(enable)


func _is_visisble(x:int, y:int) -> bool:
	return x >= 0 and x < map.w and y >= 0 and y < map.h \
		and map.fovmap[y][x] == FOVData.VISIBLE

func _is_visisble_nc(x:int, y:int) -> bool:
	return map.fovmap[y][x] == FOVData.VISIBLE



################################################################################
#		Filled Mid-point Circle
################################################################################
func _make_fov_circle_mask(radius:int) -> void:
	var size:int = radius * 2 +1
	var cx:int = radius
	var cy:int = radius
	var err:int = -radius
	var x:int = radius
	var y:int = 0

	for j in range(size):
		_circle_array.append([])
		for i in range(size):
			_circle_array[j].append(FOVData.HIDDEN)

	while x >= y:
		var last_y = y

		err += y
		y   += 1
		err += y

		_make_lines(cx, cy, x, last_y, size)

		if err >= 0:
			if x != last_y:
				_make_lines(cx, cy, last_y, x, size)

			err -= x
			x   -= 1
			err -= x


func _apply_fov_circle_mask(pos:Vector2, radius:int) -> void:
	var size:int = radius * 2 + 1

	for j in range(size):
		for i in range(size):
			var x = (pos.x + i - radius)
			var y = (pos.y + j - radius)
			if _circle_array[j][i] == FOVData.HIDDEN:
				if x >= 0 and y >= 0 and x < map.w and y < map.h:
					_set_visible_nc(x, y, false)

func _make_lines(cx:int, cy:int, x:int, y:int, size:int) -> void:
	_line(cx-x, cy+y, cx+x, size)
	if y != 0:
		_line(cx-x, cy-y, cx+x, size)

func _line(x0:int, y0:int, x1:int, size:int) -> void:
	for x in range(x0, x1):
		_put_pixel(x, y0, size)

func _put_pixel(x:int, y:int, size:int) -> void:
	if x >= 0 and y >= 0 and x < size and y < size:
		_circle_array[y][x] = FOVData.VISIBLE





####################################################################
# 		Restrictive Precise Angle Shadowcasting (from js)
#- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# Works perfectly, as far as I can tell.
#
# Ported from:
#     https://github.com/domasx2/mrpas-js/blob/master/mrpas.js
#- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
func calc_fov(pos:Vector2, radius:int=data.fov_radius) -> void:
	_clear_fov()

	_set_visible_nc(pos.x, pos.y, true) #player can see himself

	#compute the 4 quadrants of the map
	_mrpas_js_compute_quadrant(pos, radius,  1,  1)
	_mrpas_js_compute_quadrant(pos, radius,  1, -1)
	_mrpas_js_compute_quadrant(pos, radius, -1,  1)
	_mrpas_js_compute_quadrant(pos, radius, -1, -1)

	if radius != last_radius:
		_make_fov_circle_mask(radius)
	_apply_fov_circle_mask(pos, radius)

	last_radius = radius


func _mrpas_js_compute_quadrant(position, maxRadius, dx, dy):
	var start_angle = []
	var end_angle = []

	for i in range(100):
		start_angle.append(null)
		end_angle.append(null)

	# octant: vertical edge:
	# - - - - - - - - - - - - - - - - - - - - - - -
	var iteration           = 1
	var done                = false
	var totalObstacles      = 0
	var obstaclesInLastLine = 0
	var minAngle            = 0.0

	var x = 0
	var y = position.y + dy

	var slopesPerCell; var halfSlopes; var processedCell
	var minx; var maxx; var miny; var maxy; var pos; var visible; var idx
	var startSlope; var centerSlope; var endSlope

	if y < 0 or y >= map.h:  done = true

	while not done:
		#process cells in the line
		slopesPerCell = 1.0 / (iteration + 1)
		halfSlopes = slopesPerCell * 0.5
		processedCell = int(minAngle / slopesPerCell)

		minx = max(        0, position.x - iteration)
		maxx = min(map.w - 1, position.x + iteration)

		done = true

		x = position.x + (processedCell * dx)

		while x >= minx and x <= maxx:
			pos = Vector2(x, y)
			visible = true

			startSlope = processedCell * slopesPerCell
			centerSlope = startSlope + halfSlopes
			endSlope = startSlope + slopesPerCell

			if obstaclesInLastLine > 0 and not _is_visisble_nc(x, y):
				idx = 0

				while visible and idx < obstaclesInLastLine:
					if not _is_opaque_nc(x, y):
						if centerSlope > start_angle[idx]    \
						and centerSlope < end_angle[idx]:
							visible = false

					elif startSlope >= start_angle[idx]    \
					and endSlope <= end_angle[idx]:
						visible = false

					if visible \
					and ( not _is_visisble_nc(x, y-dy)
					or    _is_opaque_nc(x, y-dy)     ) \
					and ( x-dx >= 0 and x-dx < map.w
					and ( not _is_visisble_nc(x-dx, y-dy)
					or    _is_opaque_nc(x-dx, y-dy)  )):
						visible = false
					idx += 1

			if visible:
				_set_visible_nc(x, y)
				done = false

				#if the cell is opaque, block the adjacent slopes
				if _is_opaque_nc(x, y):
					if minAngle >= startSlope:
						minAngle = endSlope
					else:
						start_angle[totalObstacles] = startSlope
						end_angle[totalObstacles] = endSlope
						totalObstacles += 1

			processedCell += 1
			x += dx

		if iteration == maxRadius: done = true

		iteration += 1
		obstaclesInLastLine = totalObstacles

		y += dy
		if y < 0 or y >= map.h:    done = true
		if minAngle == 1.0:        done = true

	# octant: horizontal edge
	# - - - - - - - - - - - - - - - - - - - - - - -
	iteration           = 1 # iteration of the algo for this octant
	done                = false
	totalObstacles      = 0
	obstaclesInLastLine = 0
	minAngle            = 0.0

	x = position.x + dx # the outer slope's coordinates (first processed line)
	y = 0

	slopesPerCell=0; halfSlopes=0; processedCell = 0
	minx=0; maxx=0; miny=0; maxy=0; pos=Vector2(); visible=false; idx =0
	startSlope=0; centerSlope=0; endSlope=0

	if x < 0 or x >= map.w:	done = true

	while not done:
		# process cells in the line
		slopesPerCell = 1.0 / (iteration + 1)
		halfSlopes = slopesPerCell * 0.5
		processedCell = int(minAngle / slopesPerCell)

		miny = max(        0, position.y - iteration)
		maxy = min(map.h - 1, position.y + iteration)

		done = true

		y = position.y + (processedCell * dy)

		while y >= miny and y <= maxy:
			pos = Vector2(x, y)
			visible = true

			startSlope = (processedCell * slopesPerCell)
			centerSlope = startSlope + halfSlopes
			endSlope = startSlope + slopesPerCell

			if obstaclesInLastLine > 0 and not _is_visisble_nc(x, y):
				idx = 0

				while visible and idx < obstaclesInLastLine:
					if not _is_opaque_nc(x, y):
						if centerSlope > start_angle[idx]   \
						and centerSlope < end_angle[idx]:
							visible = false

					elif startSlope >= start_angle[idx]     \
					and endSlope <= end_angle[idx]:
						visible = false

					if visible \
					and ( not _is_visisble_nc(x-dx, y)
					or    _is_opaque_nc(x-dx, y)    )   \
					and ( y-dy >= 0 and y-dy < map.h
					and ( not _is_visisble_nc(x-dx, y-dy)
					or   _is_opaque_nc(x-dx, y-dy) )):
						visible = false
					idx += 1

			if visible:
				_set_visible_nc(x, y)
				done = false

				#if the cell is opaque, block the adjacent slopes
				if _is_opaque_nc(x, y):
					if minAngle >= startSlope:
						minAngle = endSlope
					else:
						start_angle[totalObstacles] = startSlope
						end_angle[totalObstacles] = endSlope
						totalObstacles += 1

			processedCell += 1
			y += dy

		if iteration == maxRadius: done = true

		iteration += 1
		obstaclesInLastLine = totalObstacles

		x += dx
		if x < 0 or x >= map.w: done = true
		if minAngle == 1.0: done = true