Requesting help with 2D raycasting for hitscan-style weapons

[TwoDaemon]

Hi all,

First post here from a relatively new coder to LOVE. I've spent the past few days poking at bits of code, little experimental stuff, and I've found it a lot of fun to work with.

Anyway, I've been messing around with doing simple hitscan-style impacts, tracing a path and testing for objects along it using Shape:testSegment(), which works fine. However, it seems to me that since you have to specify the shape you're testing for, this could quickly get out of hand if there are a lot of possible shapes to hit, since in the most obvious, crude implementation you'd have to test every single shape.

I notice that in the box2d documentation a "b2DynamicTree" class is described which appears to be designed to help with this, with efficient sorting of objects so you can traverse the tree, raycasting as you go, apparently skipping objects which aren't likely to matter in some fashion. However, I can't find this implemented in LOVE. Am I missing it, or should I produce something like it myself? And if the latter, how would one go about such a thing? I must admit, my memories of lectures on this stuff are pretty hazy. I just want to find out what the next object hit is if drawn in a line out from the firing point (I'm using physics shapes for everything solid anyway, to take advantage of collision detection stuff), but it seems like kind of a pain if I have to test every shape.

I've searched the forums and documentation for similar topics and found nothing, but my apologies if I missed anything. Thanks in advance for any help.

[Robin]

Relatively welcome, TwoDaemon!

Now, as to your problem -- I'm not sure, but I think what you are referring to is something implemented in Box2D which has no Lua bindings in LÖVE. If that is the case, you could try writing it yourself (so you don't have to write the implementation yourself, only the “glue” between the Box2D API and the Lua interface). If you succeed, you could try to get the devs to add it to vanilla LÖVE.

If not (or you can't or don't want to try), you can submit a feature request to the tracker, but keep in mind that, if it is implemented, it might take quite a while before you see the result.

[Taehl]

Since my current project doesn't use the physics engine, raycasting gets even more tricky (and utterly vital for things like basic collision). Here's a modified, 2D version of a function I'm currently using, maybe you'll find it useful:

Code: Select all

-- Do a trace from (sx,sy) to (dx,dy), checking for objects in ... tables. Return either the object collided with or false.
-- Example: if trace(player.x,player.y, player.x,player.y+1, enemies, tiles) then print("You can't walk there!") end
function trace(sx,dx, sy,dy, ...)
	local dist = ((dx-sx1)^2+(dy-sy)^2)^0.5
	for i=0, dist do
		local tx = math.round((sx*(dist-i) + dx*i)/dist)
		local ty = math.round((sy*(dist-i) + dy*i)/dist)
		for j=1, select("#", ...) do
			local t = select(j, ...)
			if t[tx] then if t[tx][ty] then return t[tx][ty] end end
	end end
	return false
end

It requires you have your objects in table_of_objects[x][y]=object format like I do. Note that, the way it is there, it will look for objects only on integer grid coordinates (if it would detect something at (4,3), but not (4,3.5). That's easy to change, though). If anyone has any suggestions to improve it, I'd love to hear it.

[TwoDaemon]

Thanks for your help, Robin. I'm afraid my grasp of C is somewhat lacking. I've had a glance around the LÖVE source to see how the bindings work but so far I've been unable to unravel much of what's going on there, so I don't think I've got much chance of adding the box2d implementation to the mix.
I do have a vague idea of how the box2d implementation of the b2DynamicTree thing works, though. I might try and see if I can implement something like it in lua instead, might be a trifle easier for me.

As I read it, Taehl, that's effectively a tile-by-tile check from one point to another, comparing the (x,y) coords along the line against two-dimensional tables of objects which are similarly sorted by [x][y]? That does make sense, aye, thanks for the suggestion. However, the purpose I'm aiming for isn't tile-locked. I'm trying for a generic top-down free movement action system for the moment, then I'll expand it into an actual game. I think to use the system you're using I'd have to effectively check pixel-by-pixel, which seems a bit inefficient. On the other hand, might still be more efficient than checking against every single shape in existence, depending on the number of shapes...

Oh, side question - related to the raycasting stuff, does anyone know how efficient the Shape:testSegment() calculations are? Is it, say, more or less efficient than a simple distance trigonometry calculation?

As I understand it (or, if I've utterly misunderstood it, the idea I've erroneously reached is that) the box2d general raycasting system uses a tree in which every node has two children and effectively represents a (rectangular, axis-aligned) bounding box that overlaps the bounding boxes of both its children. Each leaf is an actual world object (well, its bounding box) while the nodes are effectively abstract. When you raycast from one point to another, you check against the root node. If you don't hit it, well, you're not going to hit anything. If you do hit it, you check against its two children and pick the nearest (or somesuch). Repeat until you hit a leaf (well, you'd need a list of possibles to find the closest, but still). Logically, such a system ought to drastically reduce the number of objects you have to test against, given a lot of objects in the world. Of course recalculating the tree would be a pain so I guess you'd have to only use it for fixed objects, since a moving object would force a regular recalculation of the tree. I'll try implementing it, I think, see if it's any good. It'll keep me occupied anyhow.

[The Burrito]

To give you some idea of performance, this is performing each process 1 Million times and the number of seconds it takes to do so (less is better).

testperf.png (22.01 KiB) Viewed 4648 times

As you can see its quite fast.
The first testSegment is only 100 units long, the long testSegment is about 1200 units long, and hits a shape after about 500, so not much extra time for longer tests. Test point and getlocalpoint are largely for comparison, since any alternate system could very well use them.

[Taehl]

It would be pretty easy to make it so that the player can move freely in a world made of tiles (as a matter of fact, that's what I do). But you want per-pixel collision? Hm... For something like that, you may want to implement a quadtree - they're very well-suited to this sort of thing. They introduce some performance overhead, but they've been proven hundreds of times over to bring vast performance improvements to such situations. I'm afraid I don't have any code for it, though.

[TwoDaemon]

Okay, yes, that's pretty efficient. I guess I'm still having trouble grasping how powerful computers are, heh. The quadtree thing is also extremely interesting, and I can see how such a thing might reasonably be implemented.

I start to get the impression that I've been drastically overcomplicating things. Thanks muchly for the info, Burrito and Taehl!

[pygy]

You will probably get the fastest solution by using the physics module. AFAIK, it will use the b2Dynamic tree (or another appropriate, fast algorithm/datastructure) to do the task internally.

I didn't test any of this, so I may be wrong
Here's the gist of it:

Register an add callback to the physics world using world:setCallback(...). It should push all collisions inside a table.

When a ray should be fired, create a shape representing it's trajectory (very long, very thin), and then :setSensor(true) on it.

in the love.update() callback:
* call world:update() then
* traverse the collisions table to determine the closest point of collision. You can test only one of the two coordinates since all points are co-linear. That's your hit point.
* destroy the ray shape then set the collision variable to hold an empty table.

You're done :-)

[The Burrito]

* call world:update() then
* traverse the collisions table to determine the closest point of collision. You can test only one of the two coordinates since all points are co-linear. That's your hit point.
* destroy the ray shape then set the collision variable to hold an empty table.

Sadly, this is actually slower than iterating through every shape in the world with testSegment and determining the shortest trace.
Also from what I understand, box2D uses a system that only updates when it thinks it needs to, so if you create an object intersecting another the callbacks won't be called until something moves.

[pygy]

Sadly, this is actually slower than iterating through every shape in the world with testSegment and determining the shortest trace.
Also from what I understand, box2D uses a system that only updates when it thinks it needs to, so if you create an object intersecting another the callbacks won't be called until something moves.

I'll take your word for the second point, but I don't get how the brute force method can be always faster...

The collision detection should be ~O( a * log2(n) ) vs O( b * n ), where a is the time it takes for a collision callback to fire and perform its duty, and b is the time testSegment takes to run...

For n = 200, a would have to be 25 times bigger than b for your point to hold. For n = 2000, we're up to 180 times...