# Ray To Rectangle Collision

This topic is 3335 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm in need of more information on ray to rectangle collision in 2D graphics. I'm creating a GTA-like 2D game so guns are present and I am wondering if there are any popular algorithms to detect where a ray hits a rectangle. Illustrated here's the problem: http://i35.tinypic.com/14obtbd.jpg Here's the ugly placeholder code for placing the projectile at the block point: http://codepad.org/DEZRf47Z Since the shots hit instantaneously, the point where the collision occurs must be calculated in one frame. Major bottleneck at the moment. Right now the placeholder code just moves the projectile pixel-by-pixel checking the block list as it moves. I have a few ideas on algorithms but I'd rather not re-invent the wheel with something possibly not as efficient. Any links/tips?

##### Share on other sites
Is the environment tiled, with tiles either completely obstructed or completely unobstructed? If so, how big are the tiles with respect to the character? (Does the red outline delineate a tile?)

##### Share on other sites
Quote:
 Original post by jykIs the environment tiled, with tiles either completely obstructed or completely unobstructed? If so, how big are the tiles with respect to the character? (Does the red outline delineate a tile?)

Tiles are 40x40 and blocks are placed within these. All shapes are rectangular but subject to rotations (namely humans).

##### Share on other sites
Quote:
 Tiles are 40x40 and blocks are placed within these.
You didn't answer a couple of the questions, so I'll restate them:

1. How big are the tiles relative to the character in your image?

2. Does the red outline delineate a tile? (Answering this question would also answer question number 1.)

Anyway, you definitely don't need to perform the intersection test by stepping pixel by pixel. If you search the forum archives for phrases such as 'ray box intersection', 'ray aabb intersection', and 'ray obb intersection', you should find some good references (even some sample code). For axis-aligned obstacles that are aligned to the grid, you could also use 3D-DDA (2D-DDA in this case), which is a fast algorithm that can be used for raycasting in a tiled environment.

##### Share on other sites
Quote:
Original post by jyk
Quote:
 Tiles are 40x40 and blocks are placed within these.
You didn't answer a couple of the questions, so I'll restate them:

1. How big are the tiles relative to the character in your image?

2. Does the red outline delineate a tile? (Answering this question would also answer question number 1.)

Anyway, you definitely don't need to perform the intersection test by stepping pixel by pixel. If you search the forum archives for phrases such as 'ray box intersection', 'ray aabb intersection', and 'ray obb intersection', you should find some good references (even some sample code). For axis-aligned obstacles that are aligned to the grid, you could also use 3D-DDA (2D-DDA in this case), which is a fast algorithm that can be used for raycasting in a tiled environment.

Sorry, I didn't have my whole mind last night.

1) The tiles are 40x40 obstructions while the character has a 36x10 torso blocking box. Generally speaking the tiles will either be fully obstructed or fully passable. The rectangles aren't axis-aligned either.

2) Yes, it does. Also, the dashed yellow is the ray.

Found some things on the forum that somewhat relate.

Edit: what do you think of this solution?:
1) Get all blocks within a rectangle drawn with two opposite vertices being line end and begin. You get a rectangle with two triangles on each side of the ray.
2) Compile list of blocks within the whole AABB.
3) If block is only in one side of the rectangle, then skip it as it does not cross the ray. If block is in both sides of the rectangle, you have a hit (crossing the ray).

[Edited by - PatchMonster on October 24, 2009 8:59:24 PM]

1. 1
2. 2
3. 3
Rutin
15
4. 4
khawk
13
5. 5
frob
12

• 9
• 9
• 11
• 11
• 23
• ### Forum Statistics

• Total Topics
633664
• Total Posts
3013238
×