Alternative implementation for GetNeighbourList

Unity Courses Talk
,
#1

An alternative to the GetNeighbourList function that uses our GridPosition ‘+’ operator override and the gridSystem.IsValidGridPosition function might look like:

    private List<PathNode> GetNeighbourList(PathNode node)
    {
        List<PathNode> neighbourList = new List<PathNode>();

        List<GridPosition> neighbourPositionList = new List<GridPosition>()
        {
            node.GetGridPosition() + new GridPosition( 1,  0), // N
            node.GetGridPosition() + new GridPosition( 1,  1), // NE
            node.GetGridPosition() + new GridPosition( 0,  1), // E
            node.GetGridPosition() + new GridPosition(-1,  1), // SE
            node.GetGridPosition() + new GridPosition(-1,  0), // S
            node.GetGridPosition() + new GridPosition(-1, -1), // SW
            node.GetGridPosition() + new GridPosition( 0, -1), // W
            node.GetGridPosition() + new GridPosition( 1, -1), // NW
        };

        foreach (GridPosition neighbourPosition in neighbourPositionList)
        {
            if (gridSystem.IsValidGridPosition(neighbourPosition)) {
                neighbourList.Add(GetNode(neighbourPosition));
            }
        }

        return neighbourList;
    }

Here, we generate all of the grid positions up front, then iterate through them and use the gridSystem to test if they are valid. If the neighbouring position is valid we add the PathNode at that grid position.

3 Likes
#2

When I did mine, I use for loops

    private List<PathNode> GetNeighbourList(PathNode currentNode)
    {
        var neighbours = new List<PathNode>();
        var gridPosition = currentNode.GetGridPosition();

        for (var z = -1; z <= 1; z++)
        {
            for (var x = -1; x <= 1; x++)
            {
                if (x == 0 && z == 0) continue; // skip self
                //if (x != 0 && z != 0) continue; // skip diagonals

                var neighbourPosition = new GridPosition(gridPosition.X + x, gridPosition.Z + z);
                if (!_grid.IsValidGridPosition(neighbourPosition)) continue;

                var neighbourNode = GetNode(neighbourPosition);
                if (!neighbourNode.GetIsWalkable()) continue;

                neighbours.Add(neighbourNode);
            }
        }

        return neighbours;
    }
5 Likes
#3

All great options!

#4

Essentially what I ended up doing…

I am a Synty pack junkie and attempted to move into the Battle Royale demo scene, but quickly discovered that the lack of valid grid position checking meant that pathfinding would discover a route that placed me outside of the grid where I was forever stuck. Checking positions to see if they’re valid before offering them as neighbors solved that, but I’ve always hated how clumsy the “tons-of-if-statements” solution felt, so I like yours much better. Thanks for posting!

#5

I ended up moving the logic for getting the neighbouring objects onto the grid system, so in my PathNode class, I have:

public IEnumerable<PathNode> GetNeighbours()
{
    return _gridSystem.GetNeighbouringGridObjects(this);
}

The grid system (which uses a “grid dictionary” to store GridObjects with their GridPosition as a key) uses the following:

public IEnumerable<TGridObject> GetNeighbouringGridObjects(TGridObject centreGridObject)
{
    var centreGridPosition = centreGridObject.Position;
    var objects = GetAllGridObjectsWithinGridRangeOfCentre(1, centreGridPosition)
        .Except(GetAllGridObjectsWithinGridRangeOfCentre(0, centreGridPosition));
    return objects;
}

private IEnumerable<TGridObject> GetAllGridObjectsWithinGridRangeOfCentre(int range, GridPosition centre)
{
    var allGridObjectsWithinRangeOfCentre = _gridDictionary
        .Where(keyValuePair => keyValuePair.Key.GridDistanceFrom(centre) <= range)
        .Select(pair => pair.Value);
    return allGridObjectsWithinRangeOfCentre;
}

As the grid dictionary is only populated with valid grid positions to start with, I avoid the need for further validity checks here (until I start working with obstacles).

Grid Distance is calculated in the GridPosition class:

public int GridDistanceFrom(GridPosition gridPosition) => GridDistance(this, gridPosition);

private static int GridDistance(GridPosition a, GridPosition b)
{
    const int straightCost = 1;
    const int diagonalCost = 1;
    return WeightedGridDistance(a, b, straightCost, diagonalCost);
}
        
private static int WeightedGridDistance(GridPosition a, GridPosition b, int straightCost, int diagonalCost)
{
    var dX = Math.Abs(a.X - b.X);
    var dZ = Math.Abs(a.Z - b.Z);
    var dDiagonal = Math.Min(dX, dZ);
    var dStraight = Math.Abs(dX - dZ);
    var cost = (dDiagonal * diagonalCost) + (dStraight * straightCost);
    return cost;
}

I use the same WeightedGridDistance with costs of 10 and 14 for calculating H Costs.

I’m aware LINQ statements have a reputation for poor performance but, coming from having years of SQL database experience, I find myself naturally gravitating to them over loops. I think that passing the results back as IEnumerables as much as possible is supposed to reduce unnecessary garbage collection, but I can’t recall where I got that idea, and would happily accept any correction on that (or any other) matter.

2 Likes
#6

Having it all passed back as IEnumerable means that the queries (the actual filters, etc. in the Where and Select clauses) are only executed once you are requesting individual values. I would imagine that it would reduce some garbage because it’s not actually creating lists, but iterating over existing ones. I may be wrong. There are some expression trees sitting in memory, waiting to be executed, though.

There is one tiny danger that may not be obvious at first glance; State can change between you requesting the data and actually observing the data (remember, the data is only collected once you ‘look’ at it). I have had this happen to me before and it took some time to figuring it out. I cannot give exact details because I can’t remember exactly what it was but it had to do with exactly this. I think (and I may be absolutely wrong) it was something like this

var query = someList.Where(a => a.enabled);

foreach(var thing in query)
{
    //do something that assumes query stays the same
}

// something happens here (anywhere in the system) that changes someList

foreach(var thing in query)
{
    //do something else that assumes query is still the same, but query has changed because the state of someList has changed. 
}

as opposed to

var query = someList.Where(a => a.enabled).ToList(); // get the data now

foreach(var thing in query)
{
    //do something that assumes query stays the same
}

// something happens here (anywhere in the system) that changes someList

foreach(var thing in query)
{
    //do something else that assumes query is still the same, and it is because we got the data already 
}

I think this is a rather exceptional case and not many people experience this, ever, but it can happen

#7

Thanks bixarrio. Have been trying to me mindful of how I’m using it. There was one time that I didn’t, and Rider helpfully flagged it for me with a warning. From reading through the explanation the warning linked to, it definitely sounds like the sort of thing you’re talking about.

#8

Yup, that sounds about right.

#9

Actually, IEnumerables can lead to even MORE garbage collection, and even more worrisome, more iterations over the same segments of code. We ran into this in the Shops and Abilities course, where we set the targets to be an IEnumerable, and then ran multiple filters on them. Each filter ran the IEnumerable again when it was executed. When you filtered a filtered IEnumerable, it would run the filter again and again too. Not pretty.

Linq, in particular, can be pretty nasty when it comes to Garbage collection. Don’t get me wrong, I am a huge fan of IEnumerables and Linq expressions, and outside of Update loops, I use them all the time. If you use a Linq expression every frame, however, you’re going to find yourself in a Garbage Collection nightmare, as each clause in the expression puts a new copy of the collection on the heap, needing to be GC’d at some point. You’ll be pushing garbage to the heap faster than the GC can keep up with it.
I used to play a squad v squad strategy game on mobile that often had timed battles… 5 minutes to finish the battle, or you lose. At high levels, even on auto battle at 4x speed, these battles often lasted the full 5 minutes. Nothing more frustrating than in the middle of that battle the game completely stopping for 20 seconds while the GC stops everything to clean up. We’d complain about it, the company would go “oh, we see what we did” and patch it, then the new feature department would push code based on the old buggy version for a new feature and it would happen all over again.
But I digress.

1 Like
#10

So, I was wrong.

#11

Interesting… I may have to dig deeper on this, then. For the EnemyAI script (yes, I tinker with pretty much everything that Hugo has written in the course; I find it amplifies what I am learning from him), I have split some LINQ statements across multiple variables to improve readability (and debug-ability):

private static bool TryToTakeEnemyAIAction(Unit unit)
{
    UnitAction[] availableActionTypes = unit.GetActions();
    IEnumerable<BaseAction> affordableActionTypes = availableActionTypes
        .Where(unit.CanAfford);
    IEnumerable<ActionTargetEvaluation> evaluatedEnemyAIActions = affordableActionTypes
        .Select(affordableAction => affordableAction.GetBestActionTarget());
    IEnumerable<ActionTargetEvaluation> viableEnemyAIActions = evaluatedEnemyAIActions
        .Where(evaluatedAction => evaluatedAction is not null);
    IOrderedEnumerable<ActionTargetEvaluation> rankedEnemyAIActions = viableEnemyAIActions
        .OrderByDescending(viableAction => viableAction.Evaluation);
    ActionTargetEvaluation bestEnemyAIAction = rankedEnemyAIActions.FirstOrDefault();

    if (bestEnemyAIAction is null) return false;

    UnitActionSystem.SetSelectedAction(bestEnemyAIAction.Action);
    UnitActionSystem.InitiateSelectedAction(bestEnemyAIAction.Target);
    return true;
}

public class ActionTargetEvaluation
{
    public BaseAction Action;
    public GridPosition Target;
    public int Evaluation;
}

So does my initial filter to get the enemy’s affordable action types end up getting run multiple times by the point where my chain of enumerables get enumerated into the single bestEnemyAIAction? As you point out, not a huge deal when it’s being run once per enemy’s turn, but good to know whether this approach is feasible to apply in a realtime context.

#12

availableActionTypes will be evaluated once, because it’s a []
Then nothing will be evaluated at all until bestEnemyAIAction, at which point affordableActionTypes will be run 5 times, evaluated four times, viable 3 times, ranked twice and best once.
There are a few ways you can avoid this multiple run scenario…
1 is method chaining, which isn’t as readable as this is

ActionTargetEvaluation bestEnemyAIAction = availableActionTypes.Where(unit.CanAfford)
    .Select(affordableAction => affordableAction.GetBestActionTarget())
    .Where(evaluatedAction => evaluatedAction is not null)
    .OrderByDescending(viableAction => viableAction.Evaluation)
    .FirstOrDefault();

Linq would take care of making only one copy of the data set for each expression on the heap, which is still annoying, but not as bad as running the queries separately.
The other is still using your setup, but “realizing” them into [] instead each time. This would require twice the heap space, but maintain readability. Once a Linq expression is converted with .ToList(), ToArray(), First(), or FirstOrDefault(), the query is realized, effectively fixed as a collection rather than remaining as a query.

UnitAction [] availableActionTypes = unit.GetActions();
BaseAction[] affordableActionTypes = availableActionTypes.Where(unit.CanAfford).ToArray();
ActionTargetEvaluation[] evaluatedEnemyAIActions = affordableActionTypes.Select(affordableAction => GetBestActionTarget()).ToArray();
AcitonTargetEvaluation[] viableEnemyAIActions = evaluatedEnemyAIActions.Where(evaluatedAction is not null).ToArray();
ActionTargetEvaluation[] rankedEnemyAIActions = viableEnemyAIActions.OrderByDescending(viableAction=> viableAction.Evaluation).ToArray[];
ActionTargetEvaluation[] bestEnemyAIAction = rankedEnemyAIActions.FirstOrDefault();

As a rule of thumb, when using the same data set over a series of separate methods (as in the case of the Shops and Abilities example, the UserData holds an IEnumerable<GameObject> that gets manipulated and filtered over an unknown quantity of filters in separate ScriptableObjects, I recommend realizing the query into an array. When it’s all in the same method, I recommend method chaining. In this case, you’re realizing the bestEnemyAIAction with FirstOrDefault(). If you really want to go see things go off the chart, if you were to use your original query, but then instead of bestEnemyAIAction you used rankedEnemyAIActions.FirstOrDefault() in the remainder of the method

if(rankedEnemyAIActions.FirstOrDefault() is null) return false;
UnitActionSystem.SetSelectedAction(rankedEnemyAIAction.First().Action);
UnitActionSystem.InitiateSelectedAction(rankedEnemyAIAction.First().Target);

The query would be realized three times, each time being run again. (Of course, you’d never do that, I’m just providing an insane example).

1 Like
#13

Here is my 2cents:

    private bool TryGetPathNode(int x, int y, out PathNode pathNode)
    {
        GridPosition testGridPosition = new GridPosition(x, y);
        if (gridSystem.IsValidGridPosition(testGridPosition))
        {
            pathNode = gridSystem.GetGridObject(new GridPosition(x, y));
            return true;
        }
        pathNode = null;
        return false;
    }

private List<PathNode> GetNeighbourPathNodeList(PathNode pathNode)
    {
        List<PathNode> neighbourNodeList = new List<PathNode>();
        GridPosition currentGridPosition = pathNode.GetGridPosition();
        for (int offsetX = -1; offsetX < 2; offsetX++)
        {
            for (int offsetY = -1; offsetY < 2; offsetY++)
            {
                if (offsetX == 0 && offsetY == 0)
                {
                    continue;
                }
                if (TryGetPathNode(currentGridPosition.x + offsetX, currentGridPosition.y + offsetY, out PathNode neighbourPathNode))
                {
                    neighbourNodeList.Add(neighbourPathNode);
                }   
            }
        }
        return neighbourNodeList;
    }
}

For me was logical to use a validation function we defined earlier.
But these two for loops with constant checking for (0,0) is rubbing me the wrong way.

Update: actually later it got pretty annoying to deal with “out” ref. So it was a nice flex but not a very easy one to use.

#14

I tried to keep things somewhat coordinated. (Thanks to Alexey first for reminding me I should rename GetNode() to TryGetNode() for clarity).

First, I put some check on if the queried position was valid, same as some others in the thread already did:

private PathNode TryGetNode(int x, int z)
{
     GridPosition gridPosition = new GridPosition(x, z);
     if (gridSystem.IsValidGridPosition(gridPosition))
     {
         return  gridSystem.GetGridObject(gridPosition);
     }
     else
     {
         return null;
     }
}

The other thing I did was to simplify GetNeighbourList().
I checked the documentation on how lists handle someList.Add(null) and according to it that is perfectly valid.

Thus:

private List<PathNode> GetNeighbourList(PathNode currentNode)
{
    List<PathNode> neighbourList = new();
    GridPosition gridPosition = currentNode.GridPosition;

    neighbourList.Add(TryGetNode(gridPosition.x - 1, gridPosition.z + 0)); //Left
    neighbourList.Add(TryGetNode(gridPosition.x + 1, gridPosition.z + 0)); //Right
    neighbourList.Add(TryGetNode(gridPosition.x + 0, gridPosition.z + 1)); //Above
    neighbourList.Add(TryGetNode(gridPosition.x + 0, gridPosition.z - 1)); //Below

    if (allowDiagonalMovement)
    {
        neighbourList.Add(TryGetNode(gridPosition.x - 1, gridPosition.z + 1)); //UpLeft
        neighbourList.Add(TryGetNode(gridPosition.x + 1, gridPosition.z + 1)); //UpRight
        neighbourList.Add(TryGetNode(gridPosition.x - 1, gridPosition.z - 1)); //DownLeft
        neighbourList.Add(TryGetNode(gridPosition.x + 1, gridPosition.z - 1)); //DownRight
    }

    neighbourList.RemoveAll((PathNode pathNode) => (null == pathNode));
    return neighbourList;
}
1 Like

Privacy & Terms