CODEWITHSUNDEEP
c#
james
james

Reputation: 1041

Get all cells in X distance of another cell. (XY Grid)

Currently I have a function to go through a grid and update the distance of the cell to the closest cell marked as an exit. 

    foreach(var tile in TileList.Values.ToList())
    {
        tile.DistanceToExit = this.GetDistanceToExit(tile);
    }

    public int GetDistanceToExit(Tile wantedTile)
    {
        int closestTileDistance = int.MaxValue;
        foreach(var tmptile in TileList.Where(o=>o.Value.Type== TileType.Exit))
        {
                int dx = tmptile.Key.x - wantedTile.Location.x;
                int dy = tmptile.Key.y - wantedTile.Location.y;

                double distance = Math.Sqrt(dx*dx + dy*dy);
                int dis = (int)Math.Round(distance, MidpointRounding.AwayFromZero);

                if(dis < closestTileDistance)
                {
                    closestTileDistance = dis;
                }
        }
        return closestTileDistance;
    }

The problem is this is very slow when you start getting into 100x100 size grids.

I only need to know which cells are within X cells of an exit cell. So I was thinking I should work backwards from an exit.

Is there an algorithm for getting all cells that are within X distance of a specified cell without having to loop though all cells as I have above?

Upvotes: 0

Views: 529

Answers (1)

Kyle David Krueger
Kyle David Krueger

Reputation: 76

I would go backwards from the exit so you don't have to loop through every tile. I would also not store the distance if you don't need to, just a boolean that says if the tile is close to an exit.

this expression should select all tiles that are as close or closer than some distance to an exit:

    List<Tile> exits = tiles.Where(t=>t.type = exit).ToList()

    List<Tile> closeTiles = exits.SelectMany(e=> tiles.Where(t=> ((t.X - e.X) ^ 2) + ((t.X - e.X) ^ 2) <= distance ^ 2)).Distinct().ToList()

I wrote this in VB and then converted it to C# so sorry if there are any syntax errors, but this should work. The distinct is there because a tile could be close enough to multiple exits, and would then appear in the list multiple times.

Upvotes: 2

Related Questions