0

I am making a grid based game which has "line of sight" targeting. Often times a game engine would use Raycast for this but I don't want to use an engine so I am trying to "roll my own" solution.

So basically, given P1,P2 pairs I want to find all those spaces between them (marked X).

I am having a big of a hard time figuring out how to do this. Somehow I have to find out which sides are closest together and use those as my starting points for "raycast". Then I guess I could take "samples" at cell-size increments and compare those with the indexes of the cells.

Unfortunately, I don't have any code yet ... I was hoping some could help with some pseudocode just to get the algorithm. I think if I could figure out how to get the start and end points for each of the pink lines then I could use that to find the orange squares.

enter image description here

max pleaner
  • 26,189
  • 9
  • 66
  • 118

1 Answers1

1
  1. Apparently, Bresenham algorithm is a good choice here.

enter image description here

I wish I could post some content in addition to the link but it wouldn't help me give a complete context. So, better to visit the link and use the information there. Don't miss out on the comments section. There are good insights there as well.

  1. Please check this as well Elegant/Clean (special case) Straight-line Grid Traversal Algorithm?.

enter image description here

Shridhar R Kulkarni
  • 6,653
  • 3
  • 37
  • 57
  • Thanks Shridhar, that should be enough info to get me going. – max pleaner Oct 05 '20 at 16:44
  • The reason I had wanted to make the line thicker was because of the whole "diagonal lines can look through walls" element. But I think that can be resolved by increasing the thickness of the walls (increasing the grid size if needed to accomodate). So Bresenham algorithm should do the job. – max pleaner Oct 05 '20 at 19:31
  • @maxpleaner I am glad you are unblocked now. – Shridhar R Kulkarni Oct 06 '20 at 01:43