Raycasting Collision Detection

Question

I need to check for collisions when firing a bullet, but I have a few questions first. My game is 2D and tile based, it also uses the XNA framework. From what I've read raycasting or continuous collision detection is the way to go for high speed bullets. XNA has a method called Ray.Intersects which takes a bounding box, does this mean that I should be starting at a point and looping through all the tiles in a line to see which tile intersects like this?

Now that example required 10 checks and now I have the information I need to know where the collision is exactly, but wait what if a person jumps in line of the ray? Well now I need to be performing these checks every frame in order to determine if a player comes in line. Assuming my game has a solid 60 FPS I'm now up to 60 checks every second or 10 checks a frame. Maybe I've shot my weapon 5 times and the wall is 50 blocks away, that would be a lot of checks.

So if you couldn't figure out what I'm getting at here these are my questions.

• In order to preform raycast collisions do I start at a point (barrel of weapon) and loop through all the tiles asking "does the ray hit this tile?" until I've hit something (a wall)?
• How do I optimize it or does it even need optimizing?

Remember the system needs to...

• be able to obtain all the necessary information such as where does the collision take place exactly?
• account for players or obstructions getting in the path of the ray.

Answer 1

Assuming you've benchmarked this and are sure this is a bottleneck keep reading. If not stop. Don't worry and be happy :).

It's true that you will need to run the collision check algorithm every time you fire a bullet. And depending on how long it takes the bullet/laser to disappear you will have to do it multiple frames. However when you implement a solid spatial partitioning algorithm the number of candidates that can intersect the ray are few.

One of the most well know implementations is the quad tree. Basically it's a data structure that let's you ask quickly in what tile the starting point of your ray is. It also enables you to quickly look up adjacent tiles and it will allow you to ignore most of your tiles. It will also tell you quickly what other objects are on the inspected tile. Also don't forget the following optimization: if you start from the bullet source and keep checking from there you can stop as soon as you've detected a hit.

Note I also found this neat tutorial, it's a bit dated but it might get the idea across, it will especially show that one tile in a quad could, and probably should, hold multiple 'world' tiles. http://www.heroicvirtuecreations.com/QuadTree.html