Finding which object in the table is closest

[Griff]

So I haven’t started to implement attacks yet since I’m not sure how I would figure out which enemy is actually closest to my tower. Basically I want to find the enemy closest to the tower and fire an arrow at them.

[darkfrei]

Just sort table with special comparing function that compares square distances?

[vilonis]

You don’t even have to sort the list of enemies.

For each tower, walk through the list of all enemies (using a for loop), keeping track of the “closest enemy so far” and how far away from the tower they are. When you get to the end of the list, you know “closest so far” is actually the closest, period.

This isn’t a super efficient way to do it, but it is efficient enough to get started with, and vastly simpler than spatial partitioning approaches.

[Azzla]

What vilonis said. I happen to have a function for exactly this that I was using for an Auto-Battler prototype. For the purposes of library independence I added the relevant vector functions locally:

Code: Select all

local function len(x,y)
	return math.sqrt(x*x + y*y)
end
local function dist(x1,y1, x2,y2)
	return len(x1-x2, y1-y2)
end

--Returns the closest enemy within range of position vector (x,y).
function GetClosestInRange(enemies, position, range)
	local closest_enemy
	local closest_dist = 999999 --some arbitrarily large number

	for _,enemy in ipairs(enemies) do
		local distance = dist(position.x,position.y, enemy.x,enemy.y)
		if distance <= range then
			if distance < closest_dist then
				closest_dist = distance
				closest_enemy = enemy
			end
		end
	end
	return closest_enemy --nil if nothing is in range.
end

This is a context-independent way of handling it, but you could simplify/optimize this by making it a method of your tower and capturing the relevant variables. Something like:

Code: Select all

function Tower:getClosestEnemyInRange(enemies)
	if not self.target then self.closest_dist = 999999 end
	for _,enemy in ipairs(enemies) do
		local distance = dist(self.x,self.y, enemy.x,enemy.y)
		if distance < self.closest_dist then
			self.target = enemy
			self.closest_dist = distance
		end
	end
end

[Trystan]

Just to add a little bit more. If you want to do a lot of checks per frame and need it to be a little bit faster you don't need to take the square root for each object, since closer things will have a smaller distance squared than farther things. You can then take the square root of the winner at the end if you need actual distance.

Quick example..

Code: Select all

function getClosest(tower, enemies)
	local bestDist = math.huge
	local bestEnemy = nil
	local distSquared
	for _, e in ipairs(enemies) do
		distSquared = (tower.x - e.x) * (tower.x - e.x) + (tower.y - e.y) * (tower.y - e.y)
		if distSquared < bestDist then
			bestDist = distSquared
			bestEnemy = e
		end
	end
	-- return distance and enemy
  	-- if we need the actual distance we can square root it here
  	return math.sqrt(bestDist), bestEnemy
  end

[RNavega]

Code: Select all

	local closest_dist = 999999 --some arbitrarily large number

This reminded me, for this "absurdly large initial value" kind of thing, there's that constant that's loaded by default:

Code: Select all

math.huge

But my favorite is in Python: float("inf") creates a positive infinity value, nothing is above it.

Edit: it looks like math.huge is the same, if you print it, it says "inf".

Edit 2: an alias to math.huge is tonumber("inf")