Collision checking of bullets [Solved]

[LiquidDandruff]

Right now i am checking if enemies are hit by having each enemy loop through each bullet. Doing it this way seems kind of expensive and if there are a lot of bullets or a lot of enemies the game slows down fast. What's a better way to check for collision?

in each zombie's update loop

Code: Select all

	for _,b in ipairs(game.bullets) do
		if quadsColliding(rotatebox(self:gethitbox()), rotatebox(b:gethitbox())) then
			self:damaged(math.random(1,5))
		end
	end

[Robin]

Indeed, it might be inefficient for large amounts of bullets and enemies. If you want to optimise, I'd suggest a spatial hash, where you would make a grid, grouping your enemies in blocks, so you only need to check against a few of those blocks. It makes more sense to put the enemies in a spatial hash than the bullets, because bullets tend to move faster and tend to be fewer in number than enemies. If the reverse is true, it might make more sense to put the bullets in a spatial hash instead and loop over all the enemies.

This approach works better if #enemies and #bullets differ more and if there tends to be more difference in distance between bullets and enemies, and blocks are still large enough to prevent enemies/bullets constantly switching blocks.

[LiquidDandruff]

thanks for the suggestion, robin! after reading up on what spacial hashing is, i decided to convert this code to lua, and its working great so far : http://conkerjo.wordpress.com/2009/06/1 ... ollisions/

Code: Select all

require("SECS")

--creat hashclass
spacialhash = class:new()

--setup parameters
function spacialhash:init(areax,areay,areawidth,areaheight,bucketsize)
	self.xpos,self.ypos		=	areax,areay
	self.columns,self.rows	=	math.floor(areawidth/bucketsize),math.floor(areaheight/bucketsize)
	self.bucketsize 		= 	bucketsize


	self.buckets 			= 	{}

    for i = 1,self.columns*self.rows do
        --table.insert(self.buckets,{})
		self.buckets[i]={}
	end
	
end

--clear the hash table each frame
function spacialhash:update()
    for i = 1,self.columns*self.rows do
        --table.insert(self.buckets,{})
		self.buckets[i]={}
	end	
end

--debug, draws each bucket
function spacialhash:draw()
	local c1,c2,c3 = love.graphics.getColor()
	love.graphics.setColor(25,25,112)
	for x = 1,self.columns  do
		for y = 1,self.rows do
			love.graphics.rectangle("line",self.xpos,self.ypos,self.bucketsize,self.bucketsize)
			self.ypos = self.ypos+self.bucketsize
		end
		self.ypos=-self.bucketsize
		love.graphics.rectangle("line",self.xpos,self.ypos,self.bucketsize,self.bucketsize)
		self.xpos = self.xpos+self.bucketsize
	end
	self.xpos=-self.bucketsize

	love.graphics.setColor(c1,c2,c3)
end

--get the objects that are in this object's bucket
function spacialhash:getnearby(object)	--bulletsnearby
	local objects,buckets = {}, self:getidforobj(object.box)

	for _,bucket in ipairs(buckets) do
		table.insert(objects,self.buckets[bucket])		
	end
	
	return unpack(objects)
end

--hash object to bucket(s)
function spacialhash:hash(object)
	local buckets = self:getidforobj(object.box) 


	for _,bucket in ipairs(buckets) do
		--table.insert(self.buckets,bucket,object)
		if self.buckets[bucket] then table.insert(self.buckets[bucket],object) end

	end 
end

--unhash object, slow
function spacialhash:unhash(object)
	local buckets = self:getidforobj(object.box) 

	for _,bucket in ipairs(buckets) do
		--table.insert(self.buckets,bucket,object)
		if table.contains(self.buckets[bucket], object) then 
			for _,obj in ipairs(bucket) do		
				if obj ==object then
				obj = nil
				end
			end
		end

	end 
end

--debug, returns the bucket number of the object in string
function spacialhash:inbuckets(object)
	local g1,g2,g3,g4,g = unpack(shash:getidforobj(object.box))
	if g1 then	-- messy and slow
	g=g1
		if g2 then
		g=g1..","..g2
			if g3 then
			g=g1..","..g2..","..g3
				if g4 then
				g=g1..","..g2..","..g3..","..g4
				end
			end
		end
	end
	return g
end	

--interal function, returns the bucket(s) that the object occupies
function spacialhash:getidforobj(object)
	local bucketsobjisin		= {}
	
	--bounding box of the object
	local lmin,lmax,tr,br,bl	= {},{},{},{},{}	
	lmin.x,lmin.y 	= object.x,object.y
	lmax.x,lmax.y	= object.x+object.w,object.y+object.h
	
	--TopLeft
	self:addbucket(lmin,bucketsobjisin);
	--TopRight
	tr.x,tr.y 	= lmax.x,lmin.y
	self:addbucket(tr, bucketsobjisin);
	--BottomRight
	br.x,br.y	= lmax.x,lmax.y
	self:addbucket(br, bucketsobjisin);
	--BottomLeft
	bl.x,bl.y	= lmin.x,lmax.y
	self:addbucket(bl, bucketsobjisin);	
	
	return bucketsobjisin
end

function spacialhash:addbucket(vec2,buckettoaddto)
	local cellpos = math.floor(vec2.x/self.bucketsize)+math.floor(vec2.y/self.bucketsize)*self.columns--areawidth/bucketsize

	if not table.contains(buckettoaddto,cellpos) then
		table.insert(buckettoaddto,cellpos)
	end
end

function table.contains(table, element)
  for _, value in pairs(table) do
    if value == element then
      return true
    end
  end
  return false
end

and an example usage:

Code: Select all

	nearby = shash:getnearby(self) 
	if nearby then 
		for _,obj in ipairs(nearby)  do
			if obj ~= self then
				if self:disttotarget(obj) <= self.w then
					table.insert(obslist,obj)
				end
			end
		end
	end