Jump to content
  • Advertisement
Sign in to follow this  

ray intersection in regular grid

This topic is 4234 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

hello, i have a regular grid where each cell may represent an unpassable obstacle. now i am looking for an algorithm that shoots a ray from a certain point into a certain direction and returns the first intersection point with such an unpassable cell. the grid datastructure is just a 2d-array where i can access each cell with x,y and ask if it is passable or not. thanks!

Share this post

Link to post
Share on other sites
First find what your height in your grid will be based on your x
x and y are the height and width of an arbitrary triangle based on your angle.

|\ .
| \ ray
y | \ .
|___\ .

angle from s

tan(s)=x / y

y=((x + x1) / tan(s)) + y1

x=tan(s) * (y + y1) + x1

Then run through your grid horizontally using this equation (plugging in value for x) and request solidity of grid(x,y)

Also, then to compensate for the case where a line hits two or
more squares within an x, do it vertically (using the second equation) and plugging into to solidity(x,y)

Share this post

Link to post
Share on other sites

I have done this by prebuilding an array of the vectors traversals for an adaquate number of angles intervals (the path cell dx/dy offsets are stored working outward from the 0,0 center point). Visibility is scanned for all the angles/vectors within the view boresite and when one cell blocks then everything further is assumed not seen. (I used a similar system for a boresite culling of a grid based chunk rendering system also)

My simplification assumes that the entire cell is blocked and that the center point is in the middle of the cell. The array would be built for the maximum allowable distance (in cells) that can be seen (ie- 32). If that distance is too far then it gets prohibitive because the data and processing is proportionally N^2 to the max distance.

Within the above limitations, the data is static so you might as well prebuild it.

My usage was for complete scaning of an area within a pie section, and if you are back tracing from the target to the viewpoint, then something like Bresenham would be more applicable.

Share this post

Link to post
Share on other sites
thanks a lot guys! your solutions are working, but i forgot to mention something really important.

i am not only looking for the nearest sild grid cell, but in more detail for the nearest intersection point on that cell.

so the given position is a floating point. for example (4.7|2.1) that would mean that the position is on the tile(4|2) and there on the subposition (0.7|0.1)

so if the direction would change a little, the resulting point would slide along the closest sides of the solid grid cells.


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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!