# 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.

## 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 on other sites
s=source
x and y are the height and width of an arbitrary triangle based on your angle.
  s=(x1,y1)  |\ .  | \ rayy |  \ .  |___\ .    x

angle from s

tan(s)=x / y

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

or
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 on other sites
Bresenham's line algorithm can be used for this.

##### 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 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.

thanks!

1. 1
2. 2
3. 3
Rutin
19
4. 4
5. 5

• 10
• 14
• 30
• 13
• 11
• ### Forum Statistics

• Total Topics
631782
• Total Posts
3002332
×