Search Unity

Finding All Grid Cells Touched By a Collider

Discussion in '2D' started by techniquea2z, Apr 7, 2022.

  1. techniquea2z

    techniquea2z

    Joined:
    Jun 3, 2017
    Posts:
    37
    I have a system of marking certain grid cells as impassible based on whether a collider is overlapping the center of the grid cell.

    upload_2022-4-7_14-3-21.png

    Before, I would have to iterate through EVERY cell in the Tilemap's Grid and check if the specific collider is overlapping that cell.

    It had terrible performance and a high startup time to do for each collider...

    So, I want to optimize by using the bounds of the collider to check if it touches any specific Vector3Int position in a Grid.

    As can be seen above, it isn't as accurate as iterating throgh everything. But, it is MUCH faster.

    This is the code:


    Code (CSharp):
    1. public void Scan()
    2.     {
    3.         var worldGrid = WorldGrid.Instance;
    4.  
    5.         _renderer ??= GetComponent<SpriteRenderer>();
    6.         _nullTile ??= Resources.Load<TileConfiguration>("NullTile");
    7.  
    8.         targetedTiles = new List<WorldCell>();
    9.  
    10.         // Iterate through each collider that will mark impassibility
    11.         foreach (var barrier in barriers)
    12.         {
    13.             var bounds = barrier.bounds;      // get bounds
    14.            
    15.             // try to convert Bounds to BoundsInt for grids
    16.             var cellBounds = new BoundsInt(
    17.                 worldGrid.Grid.WorldToCell(bounds.min),
    18.                 worldGrid.Grid.WorldToCell(bounds.size) + new Vector3Int(0, 0, 1));
    19.  
    20.             foreach(var cell in cellBounds.allPositionsWithin)
    21.             {
    22.                 var worldCellCenter = (Vector2)worldGrid.Grid.GetCellCenterWorld(cell);
    23.  
    24.                 var overlappingColliders = Physics2D.OverlapPointAll(worldCellCenter);
    25.              
    26.                 // If the barrier is covering the center of this tile
    27.                 if (overlappingColliders.Contains(barrier))
    28.                 {
    29.                     var worldCell = worldGrid[cell.x, cell.y];
    30.  
    31.                     if (!targetedTiles.Contains(worldCell))
    32.                         targetedTiles.Add(worldCell);
    33.  
    34.                     Assert.IsNotNull(_nullTile, $"_nullTime was null on {name}");
    35.  
    36.                     // Override Tile
    37.                     var overrideTile = new WorldCellTile(_nullTile, Vector3.one);
    38.  
    39.                     if (_renderer != null)
    40.                         worldCell.OverrideTile(_renderer.sortingLayerID, overrideTile);
    41.                     else
    42.                         worldCell.OverrideTile(0, overrideTile);
    43.                 }
    44.             }
    I'm wondering what I can do to get cellBounds.allPositionsWithin to be more accurate and return any grid cell that is touched by a collider.

    It should work for Box, Circle, and Polygon colliders:

    upload_2022-4-7_14-13-17.png

    Can anyone steer me in the right direction?
     
    techniquea2z, Apr 7, 2022
    #1

  2. Kurt-Dekker

    Kurt-Dekker

    Joined:
    Mar 16, 2013
    Posts:
    38,726
    Does this have to be run every frame? Can it be changed to only run when the underlying data changes? And then perhaps optimized to not consider colliders that didn't change?
     
    Kurt-Dekker, Apr 7, 2022
    #2

  3. MelvMay

    MelvMay

    Unity Technologies

    Joined:
    May 24, 2013
    Posts:
    11,473
    Before even beginning to think about complex solutions, try ensuring you're not doing it basically brute force. The code I referred to above will generate a whole new C# array and then throw it away each generation. This is going to be terrible for performance. As with all 2D physics queries, don't use the "All" or "NonAlloc" ones; use no-suffix ones. So in your case, use OverlapPoint. Create a List<Collider2D> in your script once and reuse it. It'll probably create pretty much no garbage (when the list capacity has been automatically set) and is faster.

    Also, why are "Barriers" not a Layer? That way you can simply pass that layer in your query above. Then you don't need to iterate the results because you'll only have barriers. This has to be much quicker than using the List<T>.Contains to search the whole list.

    It's mostly just doing least work getting the data initially and less about how to efficiently work with the data when you have it. You need to solve those first.
     
    MelvMay, Apr 8, 2022
    #3
    donovanski, techniquea2z and Kurt-Dekker like this.