Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Cheaper method than using raycast to check if an object exists at a location

Discussion in 'Scripting' started by lkarus, Jul 2, 2015.

  1. lkarus

    lkarus

    Joined:
    Feb 25, 2015
    Posts:
    51
    Hello, so I currently have a 2D grid on my level. I have walls ( cover spots) and enemies patrolling around the map.

    So for each grid, I am trying to check if each node on the grid is visible from the enemies position. The only solution I can think of is using ray cast and shoot a ray from the grid toward the enemy / enemies. If the ray hits an enemy, this node on the grid is visible. If it hits a wall or nothing, that means that this grid is safe from the enemies view. So currently I have a 20 x 20 grid. It might be okay if I check 400 grids toward 1 enemy, but it can get really troublesome if the grid or the number of enemy increases.

    Is raycasting the only method I can possibly use? Or is there something that is cheaper than raycasting that I can use for my current situation.

    Any help would be appreciated and thank you in advance for anyone who takes the time to read this post and possibly help me out.
     
  2. WheresMommy

    WheresMommy

    Joined:
    Oct 4, 2012
    Posts:
    890
    May I ask, why you want to check all of the 400 grid parts? Maybe you can downsize your raycasts to a specific distance, so your enemy is checking only, lets say 5 * 5 around him which would make it way more efficient. Maybe you can explain, what the behaviour should affect :)
     
  3. lkarus

    lkarus

    Joined:
    Feb 25, 2015
    Posts:
    51
    Right. So I am currently working on some stealth pathfinding. So I am trying to check all 400 grids to see which grids are visible by the enemy / enemies. The grids that are visible from by the enemies are nodes that the seeker should try to not pass since it will end of exposing the seeker to the enemies patrolling around. Hope that helped!
     
  4. Todd-Wasson

    Todd-Wasson

    Joined:
    Aug 7, 2014
    Posts:
    1,079
    I can't help but think there's got to be a way to do this kind of line-of-sight stuff in 3D by rendering the scene from the cameras only to the zbuffer or something like that. Since I have no idea how to do that, I'll just ask about the raycasting: ;)

    Would you really need to check all 400 grid cells? A ray from one spot to another (player to one enemy) will only go through a few of them. Maybe I'm misunderstanding what you're doing.

    Are the raycasts against 3D objects in these grid cells, or is each grid cell just empty or full? If they're just empty/full I'd think you could do this probably a lot more efficiently by hand coding it than using Unity raycasts. Just my first thoughts on it without having tried it myself:

    If the grid is 2D from a top down view, you could write your own raycaster using the direction vector and starting position of the ray to walk from one cell to the next on your way from the enemy to the player until you get to the cell of the enemy. Then the limiting factor wouldn't be the number of cells, but the distance between the player and the enemy and the grid resolution. After some distance you could just stop and say he's too far away to see.

    Mark all the borders between cells beforehand as being filled or unfilled, then it should probably just be a matter of walking along the x direction by the cell size and computing the y coord, then converting that to a cell number that's full or empty to the left or right. Then do the same for the x coord. Start at the enemy and as soon as you hit a full cell, stop. The enemy can't see the player. Check the next enemy.

    The boundaries might not be quite enough info because for example the x = 13 boundary could have a full cell to the left and an empty one to the right. So maybe you'd have to walk it through two hits to know you actually went through a full cell and hit something, or use the direction of the ray to figure out whether it should be looking up the cell to the left of x = 13 or the cell to the right. Then same for up/down on y. Hmm...
     
    Last edited: Jul 2, 2015
  5. WheresMommy

    WheresMommy

    Joined:
    Oct 4, 2012
    Posts:
    890
    not sure if I understand. So your enemy is patrolling around the grid and you are trying to visualize where your player can hide all over the whole scene, right?
     
  6. lkarus

    lkarus

    Joined:
    Feb 25, 2015
    Posts:
    51
    So I was able to whip out a quick screen shot of the thing I am currently working on.
    aaacasda.png

    So as I mentioned, I am working on some stealth AI where the seeker (the small game object circled in blue) needs to find a way to the target location (game object circled in purple) by not being seen by the enemy.

    Currently my enemies has a view angle (?) of 180 degree. So the seeker decided not to take the route through the upper half of the level, because there are no places to hide himself as he walks toward the target.
    The red cubes are nodes that can be seen by any of the enemies (these are not all of the viewables nodes, I just do my A* and when I pop the cheapest node off the list, I also do a raycast to see if this node can be seen by the enemy), the green nodes are nodes that can be seen from the position from either of the enemies but are not in the enemies sight.

    So as a result, the block cube and line is the path it decided to take. I currently use ray cast to check the nodes that are popped from the open list whether or not this node is viewable from either of the enemies. If it is, I give it a huge weight so the seeker doesnt consider this route unless its the only route it can take.

    I was able to get away by shooting ray casting at all 400 nodes because the enemies are currently static, I just need to calculate it once. However, if the enemies were to move, the nodes that can be seen from their old position and their new position might be different. So, when ever the enemy moves to a new node, I need to check whether or not there are additional nodes that can be seen, or nodes that were seen in the previous position, but not in the new position. I will have to be shooting ray casts every time they move to a new node, and I thought this was an insane thing to do, if the map gets bigger and the number of enemies increases.

    Currently yes, I think checking all 400 grids is the only way I can check whether or not every node can be seen / cant be seen by the enemies.

    I hope this will clarify any questions you guys might have.
     
  7. WheresMommy

    WheresMommy

    Joined:
    Oct 4, 2012
    Posts:
    890
    So I understand this as a simulation? The enemies are running around the whole time and the player clicks on "run" if he wants? Just trying to understand the game-design of this one, so we could figure out methods to simplify this massive thing ;)
     
  8. Baste

    Baste

    Joined:
    Jan 24, 2013
    Posts:
    6,294
    You could look into replicating what's the behaviour of Occulsion culling.

    So, you'd divide your map into cells, and precalculate which cells that can see which other cells. Then, you tell the AI which cell they are in, and which cell the player is in, and only do the raycasts if the player is in a cell the AI can see stuff in.

    It's a bit hard, but it's definitely doable.
     
  9. WheresMommy

    WheresMommy

    Joined:
    Oct 4, 2012
    Posts:
    890
    I like that approach, but I guess, if you are using cells, you won't be able to "calculate" the path for a whole map. Another approach could be using multiple cameras, but I guess, this would be a bit to overload...
     
  10. lkarus

    lkarus

    Joined:
    Feb 25, 2015
    Posts:
    51
    Yes, its more like a simulation than a game. The enemies will be walking along a set of way points predefined and the seeker will have to find its way around them to the target location.

    I looked into this and read that this can not be used in run time. The red walls, are something that I place on run time, so I dont think occulsion culling is a method I can use.
     
  11. HiddenMonk

    HiddenMonk

    Joined:
    Dec 19, 2014
    Posts:
    987
    Not sure, but ill spit an idea.

    1 - Find best path to take ignoring all enemies.
    2 - Before moving to the first closest point, at that first closest point do a raycast to all enemies and see if any see that spot.
    If they do, test another spot that you can move to until you find 1 that no one sees.
    3 - Once you find a safe spot, move to it and recalculate the best path.

    Rinse and repeat.

    The pros of this might be less raycasts, but you will be running the pathfinding code a lot more. I am not sure which 1 is better.

    Edit - the more I think it, the less my method seems the way to go.
    Unless maybe if you..
    1 - Find best path to take ignoring all enemies.
    2 - Walk the path in code and test each and every one of them. If you run into a spot where the enemies can see, refind the best path from the beginning with that spot marked as bad.
    Do that until you reached the target, and then start moving your guy.

    Any time an enemy has moved, you will need to redo this. Not sure how good this would be.
     
    Last edited: Jul 2, 2015
  12. lkarus

    lkarus

    Joined:
    Feb 25, 2015
    Posts:
    51
    So if I understood this correctly, for step 2, I would just be iterating through the nodes in the open list, and if I pop a node from the list and find out that this node is visible from the enemy, I'll mark this node as a 'bad' node. So the program will look for another route excluding the previous route it was considering.

    However, since my enemies will be moving back and forth, when the seeker is looking for a path, the path it has calculated might not be in the sight of the enemies. But after the calculation is done and the seeker is moving, there might be a chance that the enemy will be seeing part of the path, and even maybe see the seeker walking pass it.
     
  13. HiddenMonk

    HiddenMonk

    Joined:
    Dec 19, 2014
    Posts:
    987
    It seems that regardless of what method you choose, you will need to do recalculations everytime the enemies move.

    With the method I stated..
    Before you move your player, you find a path to give it.
    The way you get the path is...
    1- Get the best path ignoring all enemies
    2- Test each spot to see if the enemy can see any spots of your best path. If so, mark the spot as bad and recalculate a best path.
    You will repeat that proccess until you have successfully found a properly safe path to walk.
    3- when you finally got a safe path to walk, now you start to move your character along that path, however, if any of the enemies have moved from after you calculated your path, you will need to redo all the calculations before moving again.

    With this method I do not see how the enemy might see the player.

    I have no idea if this is a good way to do things. The performance of this is kind of up in the air. Some frames it can be fast, while others extremely slow.
     
  14. Adroytus

    Adroytus

    Joined:
    Apr 1, 2014
    Posts:
    8
    If the enemies are walking on a predefined path, can you compute what is visible at each waypoint ahead of time?

    If not, you could use a QuadTree to reduce the number of cells that you have to check. Basically, each of your cells belong to a bigger parent cell (eg. a square of 4 cells can be lumped into a single cell), and then those bigger parent cells belong to an even larger parent cell. If a big cell is not visible to an enemy none of its child cells are visible either. If a big cell is visible, then you can send raycasts from the child cells to determine exactly which cells are visible.
     
  15. HiddenMonk

    HiddenMonk

    Joined:
    Dec 19, 2014
    Posts:
    987
    Maybe instead of a raycast, you can use something like this...
    (This method has a problem described in my edit. Probably shouldnt be used)
    Code (CSharp):
    1. using System;
    2. using UnityEngine;
    3.  
    4. public class TestVisionCone : MonoBehaviour
    5. {
    6.     public Transform target;
    7.     public float fieldOfView = 180f;
    8.     public float viewDistance = 10f;
    9.  
    10.     void Update()
    11.     {
    12.         VisionCone();
    13.     }
    14.  
    15.     void VisionCone()
    16.     {
    17.         float angle = Vector3.Angle(target.position - transform.position, transform.forward);
    18.  
    19.         if(angle < fieldOfView * .5f) //the .5f is important, just ignore it and put in your fov as you would.
    20.         {
    21.             Debug.Log("You are in my field of view");
    22.  
    23.             if(Vector3.Distance(transform.position, target.position) < viewDistance)
    24.             {
    25.                 Debug.Log("You are close to me");
    26.             }else{
    27.                 Debug.Log("You are to far to see");
    28.             }
    29.         }else{
    30.             Debug.Log("You are not in my field of view");
    31.         }
    32.     }
    33. }
    So, the key here is "if(Vector3.Angle(tileSpot.position - enemy.position, enemy.forward) < fieldOfView * .5f)"
    (this method was taken from this post - http://answers.unity3d.com/questions/899523/make-enemy-to-see-player-in-unity-2d.html - as well as the unity docs http://docs.unity3d.com/ScriptReference/Vector3.Angle.html)
    Please note that the * .5f is important, so dont leave it out.

    You do that simple one line of code to determine if it is even possible for the Tile spot to be seen. Only if it is possible would we then check to see if it is actually close enough, and if it is, we mark it as bad.

    Now the question is, is vector3.angle more costly than raycasts. Maybe we can go even more simpler...
    According to the profiler, using the method above with all objects within view and within range..
    500 objects = about .5 ms in Time and Self
    1500 objects = about 1.6 ms in Time and Self
    3000 objects = about 3.8 ms in Time and Self
    (edit - when using a custom static method instead of just inline code for checking the angle, for 500 objects the time went up to from about .5 ms to about .8 ms)

    Using a simple bool raycast method "Physics.Raycast(transform.position, target.position - transform.position);"
    500 objects = about .5 ms in Self, but about 1 ms in Time
    1500 objects = about 1.8 ms in Self, but about 3.5 ms in Time
    3000 objects = about 3.6 ms in Self, but about 6.8 ms in Time

    It is not showing where those extra ms come from. There must be something more that the raycasts are doing.
    They raycasts performance might also depend on how many objects are near the ray.
    Also note that this was based on the bool raycast, however, when testing with a raycast that gave an out hitInfo, it didnt seem to make a difference.
    However, if I did a check such as "if(hitInfo.collider && hitInfo.distance < viewDistance)"
    then I saw it take a little bit more time.

    It is probably best for the time being to use this method instead of raycasts since its probably much easier to use as you do not need to worry about adding colliders or anything, and it seems to be faster.

    EDIT - It just hit me...WALLS
    You would have to use the method above just to determine if the spot is possible to be seen, you would then still need to do a raycast to see if anything is in the way.

    So lets say the enemy is in a corner, looking outwards away from any spots, using this method would save you from raycasting any spots, however, if the enemy is looking the other way towards all the spots, then not only will you spend the time checking with this VisionCone method, but also with raycasts, which would give poorer results.

    In this case, it might be better to just to a smaller check with the dot product such as
    "if(Math.Sign(Vector3.Dot(target.position - transform.position, transform.forward)) != -1)"
    This is basically like a 180 degree fov check.
    Its performance on 500 objects is about .2 ms, .3 ms if you will also check for the distance.

    So it would look like this..
    Code (CSharp):
    1. if(Math.Sign(Vector3.Dot(target.position - transform.position, transform.forward)) != -1)
    2. {
    3.     //do your raycast logic here
    4. }
     
    Last edited: Jul 3, 2015
  16. Todd-Wasson

    Todd-Wasson

    Joined:
    Aug 7, 2014
    Posts:
    1,079
    Yeah, I was just thinking something similar. Maybe do a vector from each side of each wall to the enemy, then a third vector to the player and do some angle checks or dots on vectors generated with cross products to see if the enemy-player vector is between the enemy-wall vectors or not.

    If you're looking for speed, unroll everything and don't use the Vector functions. They're useful for prototyping, but the function overhead is a lot more expensive than the simple computations they do. Here's an article I wrote on that:

    http://www.performancesimulations.c...ses-in-unitys-physics-or-any-math-heavy-code/
     
    Last edited: Jul 3, 2015
  17. HiddenMonk

    HiddenMonk

    Joined:
    Dec 19, 2014
    Posts:
    987
    Another Idea...

    Maybe we can use a CapsuleCastAll?
    Size the capsulecast so that it is your field of view, then shoot it out.

    This can work if your fov is going to just be 180, however, if you field of view is less, then this means we need a capsulecast that enlarges as it shoots out.
    So we would do a capsulecastall at a certain size, such as a length of 2 from the enemy position towards its viewing direction, then at the enemy position + distance - radius (or something like that), we have our new origin for the capsulecast, we resize it to something like 4 and keep doing this.

    Not sure about the accuracy, but it is an idea.

    Otherwise maybe you can use many raycastall or even many spherecastall and shoot them out from the enemys position towards a certain direction of their own within the fov to create a cone shape. If you make the sphereCast radius a decent size, you might be able to get away with something like 20 sphere casts.

    You are probably stepping in the zone of accuracy vs performance
     
    Last edited: Jul 3, 2015
  18. lkarus

    lkarus

    Joined:
    Feb 25, 2015
    Posts:
    51
    Yes for now, I have the enemies walk on a predefined path (walk forward until you hit a wall, turn 180 degrees back and walk backwards, if it hits a wall, turn back and repeat).

    I might expand on the way it moves but yes I think I'll be providing the waypoints the enemies walk on for the sake of this simulation.

    Can you elaborate on this part? So the original code that you posted currently only checks if the tile is in the enemies fov, ignoring any possible walls that might be blocking the enemy's view. I understood uptill here, but it kind of threw me off what happens next.


    This might be the last resort I choose to do. I'd like the simulation to be as accurate as possible. If that would seem impossible, I would have to make some sacrifices on the accuracy department.

    Thanks for all the post guys! I'm able to see this problem from different perspectives.

    And the Vector link was really interesting!
     
  19. HiddenMonk

    HiddenMonk

    Joined:
    Dec 19, 2014
    Posts:
    987
    You can ignore the original code as I forgot about walls when posting it, however, the last code I posted in that post regarding the dot is what you might use instead for a possible performance increase.
     
  20. lkarus

    lkarus

    Joined:
    Feb 25, 2015
    Posts:
    51
    Oh, so your code you posted later filters out the conditions when the tile is is not in the enemy's fov. If the tile is in the enemy's fov (0 ~ 180 degree), I should raycast toward the enemy to see if there is a wall blocking its view or not. Am I correct?
     
  21. HiddenMonk

    HiddenMonk

    Joined:
    Dec 19, 2014
    Posts:
    987
    Correct

    Note that if all tiles are in the field of view, then you are getting a performance loss.
     
  22. lkarus

    lkarus

    Joined:
    Feb 25, 2015
    Posts:
    51
    Hm....so its a double edge sword...I guess I'll have to think of a way in figuring out when to just raycast and when to use the code that you have provided (hopefully there is a way to do so).

    Thanks for the help everyone! Really helped out a lot
     
  23. Pavlon

    Pavlon

    Joined:
    Apr 15, 2015
    Posts:
    191
    lkarus likes this.
  24. Roni92pl

    Roni92pl

    Joined:
    Jun 2, 2015
    Posts:
    396
    My game needs up to milion of raycasts. What can u do? Time-slicing is the only option in such case.