Crumbling Crypt - PICO-8 Line of sight and Pathfinding

line_of_sight_and_pathfinding.p8

-- Bresenham's line + A*
-- Made for Crumbling Crypt: https://ko-fi.com/Post/Crumbling-Crypt-1--A-minimalist-Roguelike-B0B1SPL7E

-- calc manthattan distance, which is the grid based
-- tile distance between two points
function heuristic(a, b)
	return (abs(a.x - b.x)+ abs(a.y-b.y))
end

-- Insertion Sort by @impbox
function sort(array)
    for i=1,#array do
        local j = i
        while j > 1 and array[j-1].f > array[j].f do
            array[j],array[j-1] = array[j-1],array[j]
            j = j - 1
        end
    end
end

function is_legal_spot(spot, enemy)
	local x = spot.x
	local y = spot.y
	if x < 0 or x > 128 or y < 0 or y > 128 then
		return false
	end

	for otherEnemy in all(enemies) do
		if enemy != otherEnemy then
			if on_same_screen(enemy, otherEnemy) then
				if (otherEnemy.x == x) and (otherEnemy.y == y) then
					return false
				end
			end
		end
	end


	return true
end

-- helper to check against all tiles that are walls
function wall_tile_helper(spot)
	local x = spot.x
	local y = spot.y

	--land = {1}
	--0
	local tileId = mget(x,y)
	if (tileId == 1) or (tileId == 18) then
		return false
	end
	return true
end

-- find existing neighbour tiles that are walkable (non walls)
function get_neighbours(pos, enemy)
	local neighbours={}
	local xPos = pos.x
	local yPos = pos.y


	local up = {x = xPos, y=yPos-1}
	local down = {x = xPos, y=yPos+1}
	local left = {x = xPos-1, y=yPos}
	local right = {x = xPos+1, y=yPos}



	if is_legal_spot(up, enemy) and wall_tile_helper(up) then
		add(neighbours,up)
	end

	if is_legal_spot(down, enemy) and wall_tile_helper(down) then
		add(neighbours,down)
	end

	if is_legal_spot(left, enemy) and wall_tile_helper(left) then
		add(neighbours,left)
	end

	if is_legal_spot(right, enemy) and wall_tile_helper(right) then
		add(neighbours,right)
	end

	return neighbours
end

--- a* from colony management
function find_path(enemy, goal)

	openSet = {}
	closedList = {}
	startNode = {x=enemy.x, y=enemy.y}
	startNode.g = 0
	startNode.h = heuristic(startNode, goal)
	startNode.f = startNode.g + startNode.h
	startNode.parent = 0
	endNode = goal
	enemy.path = {}

	add(openSet, startNode)

	while (#openSet > 0 and #openSet < 1000) do
		-- i should sort here
		

		-- pop the least value out of the open
		sort(openSet)
		local current = openSet[1]
		
		local newOpen = {}
		for i=2,#openSet do
			add(newOpen, openSet[i])
		end
		openSet = newOpen

		-- if we are on the goal, trace back on the parents and add those to the
		-- path
		if (current.x == goal.x) and (current.y == goal.y) then
			while not (current == startNode) do
				add(enemy.path, current)
				current = current.parent
			end
			enemy.closedList = closedList
			return
		end

		-- add node to closed
		add(closedList, current)



		-- get valid neighbours
		local neighbours = get_neighbours(current, enemy)
		for node in all(neighbours) do
			

			-- check if item is alredy in the closed
			local alreadyInClosed = false
			for closedNode in all(closedList) do
				if (closedNode.x == node.x) and (closedNode.y == node.y) then
					alreadyInClosed = true
				end
			end

			-- if not in closed
			if not alreadyInClosed then

				-- setup new node
				local tile = mget(node.x,node.y)
				local weight = 2
				if tile == 16 then weight = 2 end


				node.g = current.g + weight
				node.h = heuristic(goal, node)
				node.f = node.g+node.h

				-- check if node is already in the openList
				local alreadyInOpen = false
				for openNode in all(openSet) do
					if (openNode.x == node.x) and (openNode.y == node.y) then
						alreadyInOpen = true
						
						-- check if the current g value is lower than a precious one
						if (openNode.g >= node.g) then
							-- if yes, refresh said note in then refresh the values
							openNode.parent = current
							openNode.g = node.g
							openNode.f = node.f
							openNode.h = node.h
							--sort(openSet)
						end
					end
				end

				-- if the node is not in the open, the add node to the open
				if (not alreadyInOpen) then
					node.parent = current
					add(openSet,node)
				end
			end	

		end
	end
end

-- line of sight with bresenham lines
-- got if from god-knows-where at this point
-- if you are it, please send a message :D
-- thanks
function line_of_sight(x0,y0,x1,y1)

  local sx,sy,dx,dy

  if x0 < x1 then
    sx = 1
    dx = x1 - x0
  else
    sx = -1
    dx = x0 - x1
  end

  if y0 < y1 then
    sy = 1
    dy = y1 - y0
  else
    sy = -1
    dy = y0 - y1
  end

  local err, e2 = dx-dy, nil


  while not(x0 == x1 and y0 == y1) do
    e2 = err + err
    if e2 > -dy then
      err = err - dy
      x0  = x0 + sx
    end
    if e2 < dx then
      err = err + dx
      y0  = y0 + sy
    end
	local tile = mget(x0, y0)
    if (tile == 1) or (tile == 18) then return false end
  end

  return true
end

function on_same_screen(entityA, entityB)
	return (flr(entityA.x/16) == flr(entityB.x/16)) and (flr(entityA.y/16) == flr(entityB.y/16))
end

Made for Crumbling Crypt: https://ko-fi.com/Post/Crumbling-Crypt-1--A-minimalist-Roguelike-B0B1SPL7E