I have a character that is placed on a grid. It has a variable maximum walking distance. Grid fields can be walkable or not walkable. As the character may has to walk around certain not walkable fields to reach his destination his maximum walking distance isn't allways represented by a circle.
See these examples:
Without obstacles, walking distance 7:
With obstacles, walking distance 7:
Note how the obstacles affect the players maximum walking distance
To calculate this i've written this recursive function:
static Vector2Int[] GetWalkableFields (Vector2Int position, int steps) {
List<Vector2Int> walkableFields = new List<Vector2Int>();
if (steps > 0) {
foreach (Vector2Int v in GetNearbyFileds(position)) {
if (m_mc.IsInBounds(v) && m_mc.IsWalkable(v.x, v.y)) {
walkableFields.Add(v);
walkableFields.AddRange(GetWalkableFields(v, steps - 1));
}
}
return walkableFields.ToArray();
} else {
Vector2Int[] v = { position };
return v;
}
}
And this function, that returns all four neighbour fields of a field:
public static Vector2Int[] GetNearbyFileds(Vector2Int position) {
Vector2Int[] neighbors = new Vector2Int[4];
neighbors[0] = new Vector2Int(position.x, position.y - 1);
neighbors[1] = new Vector2Int(position.x, position.y + 1);
neighbors[2] = new Vector2Int(position.x - 1, position.y);
neighbors[3] = new Vector2Int(position.x + 1, position.y);
return neighbors;
}
The function is called with the players position and maximum walking distance (steps) and get's the four neighbour fields and unless the steps are zero calls itselve for every neighbour field with the maximum walking distance decremented.
As you can see in the screenshots, this works absolutely fine. The problem is, as the calculation not only goes away from the player but, in some recursion paths, goes back and fourht between tiles until stepcount zero is reached without even having traveled one field, that this way of calculating the path is really resource heavy. For a walking distance of 7 there are 27646 possible walkways that all are getting calculated. If a player is able to walk 11 fields the calculation takes a few seconds, if he can walk 12 fields Unity crashes while calculating.
Is there a way to calculate this more efficient?
Thank you in advance.