Jump to content
  • Advertisement
sun1

Finding closest point in tilemap graph that has a clear raycast path to player

Recommended Posts

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*?

image.png

Share this post


Link to post
Share on other sites
Advertisement

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?".

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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. 

Share this post


Link to post
Share on other sites

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.

Edited by Alberth

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!