How can I optimize a tower defense game targeting system?

I am in the initial development stages for a tower defense game, and as one of if not the largest performance drain (everything else is event based,) the targeting and range detection system is extremely important. It is the only code that runs constantly, and I am doing my best to make it as efficient as possible. For that, I want to ask for ideas on how to squeeze the most efficiency possible out of my targeting system, and how I can improve / add on to it.

Currently, my hostile movements are based off of waypoints that they go between.
My first check is to group these hostiles based on their current target waypoint (event based) to have them move themselves to another folder; towers can then check to see if there are any hostiles in the waypoints they cover (which they calculate through some clever Vector3 math once upon being spawned.) They also only perform magnitude checks based upon these waypoints.

My second check involves grouping up towers when a tower in close proximity, and essentially making a “master” range based upon the range of all of those towers. Before those towers will perform any sort of distance or waypoint check, this “master” range will perform the waypoint check and distance check, meaning that a bunch of towers in close proximity won’t perform their checks if the only enemies are across the map.

Besides that, there’s some obvious stuff (if there’s no enemies, don’t bother running.)

Relevant tables that are mentioned:
groupingTable is the table that is responsible for holding the tower groups. It looks like this:

local groupingTable = {
[1] = {["Master"] = towerTable, ["ChildrenTower"] = {towerTable, towerTable}},
[2] = {["Master"] = towerTable, ["ChildrenTower"] = {towerTable, towerTable}},
["Unassigned"] = {towerTable, towerTable}
}

The main loop inside of the server manager for the towers:

-- Main tower hit detection loop
coroutine.wrap(function()
	while true do
		wait(1/12)
		if isDictocc(enemyTable) then -- first check is to see if any enemies exist, since it's a dictionary we use some jank
			-- next check is to see if our masters have anything in their waypoints
			--print("Enemies exist.")
			for _, entry in ipairs(groupingTable) do
				local targs = {}
				for _, waypoint in pairs(entry["Master"].ValidWaypoints) do
					local hostilefold = HostileHolder[waypoint.Name]
					local newtargs = hostilefold:GetChildren()
					if (#newtargs) > 0 then
						-- if there's hostiles in that waypoint, perform distance check
						for i, v in pairs(newtargs) do
							table.insert(targs, v)
						end
					end
				end

				local targetInRange = false
				for _, target in ipairs(targs) do
					if (target.Position - entry["Master"].Model.Position).Magnitude <= entry["Master"].TowerInfo.Range then
						targetInRange = true
						break	
					end
				end
				
				if targetInRange then
					--print("Hostiles were in group master range.")
					for _, OurTower in ipairs(entry["ChildrenTowers"]) do
						-- check to see if this tower is on cooldown
						if not OurTower.OnAttackCooldown then
							--print("We are firing from a group.")
							OurTower:Fire(targs)
						end
					end
				end
			end
			
			for _, tower in pairs(groupingTable["Unassigned"]) do
				if not tower.OnAttackCooldown then
					--print("I am an unassigned tower, and I can fire.")
					local targetTab = {}
					for _, waypoint in ipairs(tower.ValidWaypoints) do
						local hostilefold = HostileHolder[waypoint.Name]
						for _, targ in ipairs(hostilefold:GetChildren()) do
							table.insert(targetTab, targ)	
						end
					end
					
					if #targetTab > 0 then
						--print("We found a target in a valid waypoint.")
						tower:Fire(targetTab)
					end
				end
			end
		end
	end
end)()

The :Fire() function of the Tower metatable

function Tower:Fire(TargetTable)
	-- finds the hostile we can / should shoot atwh
	self.OnAttackCooldown = true
	local firstTarget, lastTarget
	local firstTargetDist, lastTargetDist = -1, -1
	for _, hostile in pairs(TargetTable) do
		--print("I am a tower, and I am sweeping for hostiles in range.")
		if (hostile.Position - self.Model.Position).Magnitude <= self.TowerInfo.Range then
			-- if they pass distance check, figure out if its first or last
			local dist = (1000 * tonumber(hostile.Parent.Name)) + 
				(hostile.Position - Waypoints[tostring(tonumber(hostile.Parent.Name) - 1)].Position).Magnitude
			if dist > firstTargetDist then
				--print("We have found a first target.")
				firstTargetDist = dist
				firstTarget = hostile
			end
			if dist < lastTargetDist then
				--print("We have found a last target.")
				lastTargetDist = dist
				lastTarget = hostile
			end
		end
	end
	
	-- at this point, we already know that we *can* fire at it, so it's just directing how to fire
	local target = firstTarget -- make this say other stuff like last and stuff
	
	if target then
		if self.TowerInfo.AttackType == "Projectile" then
			if self.TowerInfo.ProjectileType == "Linear" then
				local projectile = Attack.Projectile.Linear(self.Model.Position, firstTarget.Position, self.TowerInfo)
				Attack.HitRegistration.Touch(projectile, self.TowerInfo.Damage, 
					self.TowerInfo.ProjectilePierce, self.TowerInfo.CanNotDamage)
			end
		end
		coroutine.wrap(function()
			wait(self.TowerInfo.AttackSpeed)
			self.OnAttackCooldown = false
		end)()
	else
		self.OnAttackCooldown = false
	end
end
3 Likes

I was about to suggest researching quadtrees or some other positional binning/hashing algorithm, until you mentioned checking which waypoints the targets are between. That’s so, so much better.

Assuming your tower defense is one of those where there’s a fixed, unchanging (or rarely changing) path and you build towers beside it, you can reduce the position of a target from a x,y position, to one number: how far into the track the target is. A tower can then know the sections of the path it can reach (there can be many such sections, e.g. at a long but narrow U-bend). It also allows sorting targets. The first target in the queue (which should also be optimized! learn about heaps and other self-sorting data structures) is guaranteed to be the one closest to the spawn, and the last one is guaranteed to be the one that’s reached the furthest. This also helps to find the closest target, by finding any nearby target and traversing the queue in the direction that gives ever nearer targets. This need not involve magnitude - you might want to assign section borders within continuous runs of accessible path, and within each section know the point that is closest to the tower; you may now simply compare the target’s position on the path to the nearest position to the tower on the path on the section, which is, again, a simple one-number comparison.
Basically, each section should be associated with one “nearest point” to the tower, and moving away from that point should always mean going further from the tower in euclidean space. If the path is bent, like a zig zag, then this isn’t always the case, there can be multiple such points in the sections of the path the tower can reach.

image

Actually, you can mostly discard all of that. In a tower defense game, you aren’t really looking for the closest target to the tower, but the one that’s the furthest into the path :slight_smile: so looking for the tail end of the queue

You can now, for each tower, scan the heap or such, looking for a target that’s closest to the end of the path but no further than the furthest position the tower can target. And you can keep track of where each tower has their minimum hitting section, and not process the towers whose minimum is beyond the position of the current target furthest along the path.


But for targets that move freely, such as flying enemies, or all enemies if you’ve got something like Desktop TD, you could use a quadtree or grid to skip scanning enemies that are in areas of the map the tower clearly can’t reach.

13 Likes