I am improving a video game of mine where I currently have the problem that NPCs can shoot through walls. In order to fix this issue, I have decided to completely re-do my work regarding ground combat.
I use a tight grid for finding paths from any point A to B. I store my grid as an image-like structure and use Jump Point Search for the pathfinding itself. My goal is to find a location that is as far away from the enemy as possible (limited by the firearms's range) that also has a direct line of sight to the enemy.
In my latest approach, I determined all nodes in my grid that are within weapon range and that are connected to the enemy's location (colored in green in the image below). The final missing part is filtering these points so that only the points with a valid line of sight remain.
I can also detect the border lines (colored in blue) very fast. I could check for every node, if a line from this node to the enemy would intersect any border line. If that is not the case, I have clear line of sight. However, I assume this to be neither fast nor the optimal solution.
Do you have any ideas or suggestions? I am glad for any hint!
I visualized the grid in the following image to give you an idea of what I am talking about. If a character would stand in the lower right green area, he could not shoot the enemy in the upper left area because of missing line of sight.
