Jump to content
  • Advertisement
Sign in to follow this  
PatchMonster

Ray To Rectangle Collision

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
Quote:
Original post by jyk
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?)


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

Share this post


Link to post
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 this post


Link to post
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]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!