Hi, my problem is a little difficult to describe. But I have a question about an enemy that I'm working on. It's a 2d game based in unity. What I want to achieve is an enemy ai which will move to the closet node in a graph which has a clear shot at the player. If there is no close node, then it remains where it is since it cant take a shot. I've already got A* working with my nav graph in a tile base game. I've uploaded an image of what my game looks like while debugging. You can assume the player is the red square. 

I've thought about simply splitting the tile map into 4 quadrants which can be searched based on where the enemy is spawn. For example, if its in the right quadrant, then search all nodes in the right by casting a ray at the player position and move to other quadrants if no match found. Finding the closest node with not obstacle in the path and moving the enemy there. But this could easily search all nodes before finding or not finding a valid node.

Are there any algorithms that I can use or some methods todo this? Is there a way todo this through A*?

I hesitate to answer because I fear I may be missing some nuance or other (and I didn't fully understand the part about quadrants). But, it seems like Dijkstra (equivalent to A* with a constant heuristic of zero) would work, or BFS if weights are uniform.

These algorithms allow you to find an optimal node that satisfies a predicate, as opposed to finding a single specified node. Here the predicate would be, "is there a line of sight from this node to the player?".

What I meant about quadrants was splitting the screen space up to prevent having to iterate through all nodes. Instead start with 1/4 of the screen space, cast a ray from those and check only those nodes before moving to another unchecked part of the screen. The problem is I could have quite alot of nodes in a level so it makes sense to reduce the amount of ray casting I will have todo.

Updating "is there a line of sight from this node to the player?" question every time the player moves could take a large performance hit but maybe I'm micro optimising? I could give it a go and see if it works well enough.

"Closest node" is the first part here. That means you don't want to search the entire space for something that can hit the target and then see how close it is. That means a lot of testing. However, if you do a pathfind from your current location, you are more likely to find "the closest node" quickly. That said, since you don't have a defined goal spot, you would need to do something along the lines of a flood fill out from your current location -- e.g. Dijkstra. -- and test each node you come to.

Please note that this is a bitch in many games because raycasts can be expensive. Therefore testing each potential spot can add up quickly.

Another approach is to work outwards from the target. That is, paint what the target can see and then find one of those spots that's close to you. I forget the description for that sort of visibility painting since I'm just now into my first caffeine of the morning but someone else may jump in and help.

I'll admit I still don't understand how the quadrant method reduces the amount of work to be done But it may just be me.

In any case, I would, as you said, see how a straightforward implementation performs before worrying too much about optimization. If performance is an issue though, there should be ways to address it. Some ideas off the top of my head:

- Amortize the cost of searches by spreading them over multiple updates. Obviously the player might move while the search is executing, but if the search runs fast enough (say, in under a second), the error might be acceptable.

- Similarly (and with the same caveat regarding player position), run searches on separate threads (admittedly this could be nontrivial).

- You may already be doing this, but if you're using a general ray casting system (e.g. associated with a physics system like Unity's), use an optimized domain-specific algorithm instead, like 2D-DDA or Bresenham.

- If rounding the player/agent position to the nearest cell is acceptable, and if all or most obstacles are static, you could precompute line-of-sight information and store it as part of the map data. That might seem like an impractical amount of data, but given that it would be (conceptually) a triangular 2-d array and that you can use one bit per entry, it might be manageable. For example, some quick math (don't hold me to this result) gives me about 600 bytes for a 100x100 grid, which isn't bad. This would of course make your line-of-sight tests trivial.

There are also other interesting approaches involving e.g. navigation meshes and visibility regions, but they're admittedly nontrivial and would be a significant departure from your current grid-based approach.

On 10/15/2018 at 3:20 AM, Zakwayda said:

- If rounding the player/agent position to the nearest cell is acceptable, and if all or most obstacles are static, you could precompute line-of-sight information and store it as part of the map data. That might seem like an impractical amount of data, but given that it would be (conceptually) a triangular 2-d array and that you can use one bit per entry, it might be manageable. For example, some quick math (don't hold me to this result) gives me about 600 bytes for a 100x100 grid, which isn't bad. This would of course make your line-of-sight tests trivial.

Normally I'd be hesitant, but if you literally only care about visibility from one pathable node to another, it becomes even more trivial. I believe the scene above only has about 43 nodes, so quite a manageable amount to precalculate. 

Your screenshot looks like everything is static, can't you pre-compute all nodes with a clear shot path to a region? Or at least the set of nodes that you should investigate more closely?

Edit: Alternatively, to get a straight line from the player tile to tile X, there is a set of tiles between the player and that tile X. This is a tree of free tile checks. For a given size of a tile, the tree is pre-computable. At run-time, you can explore that tree, and chop of branches if you run into a non-free tile. Perhaps you can code it as a Dijkstra search where every tile has a specific set of neighbour tiles (namely those that have rays running through the 'current' tile), rather than the generic 'all around' approach.