For some reason my walkable grid doesn't connect lower and upper floor

[heckert]

For starters, here is my grid interface:

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public interface IGridSystem<TGridObject>
{
    public int Height { get; }
    public int Width { get; }

    //public GridSystemHex(int width, int height, float cellSize, Func<GridSystemHex<TGridObject>, GridPosition, TGridObject> createGridObject);
    public Vector3 GetWorldPosition(GridPosition gridPosition);
    public GridPosition GetGridPosition(Vector3 worldPosition);
    public TGridObject GetGridObject(GridPosition gridPosition);
    public bool IsValidGridPosition(GridPosition gridPosition);
    public void CreateDebugObjects(Transform debugPrefab, Transform parent = null);
    public void Map(System.Action<TGridObject> action);

}

[Brian_Trotter]

@heckert

        totalNeighbourList.AddRange(neighbourList);
        //Debug.Log($"Total neighbours before: {totalNeighbourList.Count}");

        foreach (PathNode pathNode in neighbourList)
        {
            totalNeighbourList.Add(TryGetNode(gridPosition.x, gridPosition.z, currentFloor + 1)); //Above
            totalNeighbourList.Add(TryGetNode(gridPosition.x, gridPosition.z, currentFloor - 1)); //Below
        }
        //Debug.Log($"Total neighbours after: {totalNeighbourList.Count}");

        totalNeighbourList.RemoveAll((PathNode pathNode) => (null == pathNode));

So it looks like your handling floor pathfinding here. It looks like you’re determining if there’s a position above or below each position in the neighbor list, but I’m not seeing how you would prevent, for example, me from moving through the ceiling or through the floor here. This is why Hugo went with placing PathfindingLInks which would expressly say "from this GridPosition, you can move to this other GridPosition.

[heckert]

That is going to be the next lesson…

But in the current one it should already be possible to move between both grids, and even though I added the “above” and “below” neighbours to the list (and postponed culling of all invalid neighbours (the ones where TryGetNode() returns null) below, it seems there are never any in the list so the neighbouring positions on the adjacent floor don’t make it into the list of possible target grid cells. I tried commenting out the culling completely (and consequently added a null check as first condition into the FindPath() loop, but that didn’t make a difference…

[Brian_Trotter]

I’m not sure where to help there, to be honest.

[heckert]

I have some debugging output to my scene view at the beginning of FindPath():

           Debug.DrawLine(LevelGrid.Instance.GetWorldPosition(startGridPosition),
            LevelGrid.Instance.GetWorldPosition(endGridPosition), Color.magenta, 30f);

This show one other issue I have in my project much more clearly than before, especially when I increase a unit’s movement range during runtime. The lines drawn have a much larger area than the grid cells that get to be the valid target positions for moving…

Also, when I select a ground-floor unit placed next to the elevated floor, the lines go up to the elevated floor as well, but even an adjacent cell is not reachable.

The unit on the upper floor OTOH doesn’t have any of the lines going towards the lower floor.

I would think there are several bugs that add to each other…

I also put some DrawLine()s into the MoveAction’s TakeAction().

One thing I could see was that

int pathfindingDistanceMultiplier = 10;
if (pathLength > _maxMoveDistance * pathfindingDistanceMultiplier) continue;

is cutting off the range too much…

[heckert]

No wonder, movement starts to feel sluggish and jerky again:

With a movement range set to 3 and Debug logs on GetNeighbourList() I get those numbers:

It gets called about 7000 times, which appears a bit excessive…

Each blue marker is for an “above” neighbour. Cyan cells are culled in MoveAction for their distance, and the long red markers are those where HasPath() returned false…

No matter what, FindPath() doesn’t seem to grab neighbouring cells on another floor.

Also I’m thinking it might actually be useful to scan the grids for neighbours once in a big sweep and have each PathNode keep a list of its neighbours cached…

Also somewhat strange, GetValidActionGridPositionList() logs the positions added to the list, which I would think is when pathfinding for selecting the action is done.
But then tons of calls to calculate neighbours are done afterwards which takes several seconds…

[Brian_Trotter]

@heckert

It gets called about 7000 times, which appears a bit excessive…

This is one of the performance flaws in the current system. Each location within range is actually ran by the Pathfinding up to 3 times. Once to see if a path exists, once to see if it’s in range, and then if the MoveAction is selected on that tile, one more time. In the meantime, the UI and animations are unresponsive because we’re doing all of that pathfinding in a blocking manner.

@heckert

Also I’m thinking it might actually be useful to scan the grids for neighbours once in a big sweep and have each PathNode keep a list of its neighbours cached…

This is actually not a bad idea at all.

I’ve been trying to think of a way, in that regard, to calculate valid neighbors on a floor above or below the current floor.

A few parameters need to be observed (for sanity’s sake)…

1. The tile immediately above or below the tile being tested cannot be a valid neighbor, whether it is occupied or not. If there is no tile, then you can’t walk on air, if there is a tile, you cannot move through walls or floors.
2. To be a neighbor, it is probably best that the tile be truly adjacent (cardinal directions only) to the tile in question.
3. Much like condition 1, that neighbor can’t have a valid moveable tile on the same floor as the tile we’re moving from.

Perhaps something like this:

    private List<PathNode> GetMultiFloorNeighborList(PathNode currentNode)
    {
        List<PathNode> neighborList = new List<PathNode>();
        GridPosition gridPosition = currentNode.GetGridPosition();
        int floor = gridPosition.floor;
        for (int x = -1; x < 2; x++)
        {
            for (int z = -1; z < 2; z++)
            {
                //Cannot be a neighbor to one's self, nor can floor above or below be a neighbor
                if (x == 0 && z == 0) continue;
                //If position is NOT walkable on the same floor
                if (!IsWalkableGridPosition(new GridPosition(x, z, floor)))
                {
                    //First rule out diagonals... a diagonal should not be a neighbor
                    if (Mathf.Abs(x) == Mathf.Abs(z)) continue;
                    //Test floors above and below for walkable tiles
                    if (IsWalkableGridPosition(new GridPosition(x, z, floor + 1)))
                    {
                        neighborList.Add(GetNode(x,z,floor+1));
                    } else if (IsWalkableGridPosition(new GridPosition(x, z, floor - 1)))
                    {
                        neighborList.Add(GetNode(x,z,floor-1));
                    }
                }
                //At this point, the position is walkable on the same floor, so we can add it to the list.
                else
                {
                    neighborList.Add(GetNode(x,z,floor));
                }
            }
        }
        return neighborList;
    }

[Brian_Trotter]

Hmm… This did not work when I plugged it into the course project, replacing the GetNeigborList… Stay tuned.

[Brian_Trotter]

The script above was seriously flawed, as I forgot to include the grid position we were testing along with the x,z coordinates…
Nevertheless, it failed, and with some Debugs, I got to see just what’s taking so long, and part of why the Pathfinding links on the next lecture was the way @CodeMonkey went with the multi-floors.

Is there a particular reason you are against the pathfinding links? The only thing I can think of that pathfinding links may not work for is procedural generation. If that’s the case, I’ll see what more I can come up with…

[Brian_Trotter]

And right when I thought I was walking down the wrong path, I found my simple error, adding the gridposition’s floor to the gridPosition + new GridPosition(x,z, floor) (should be x,z, 0)
Working script:

   private List<PathNode> GetMultiFloorNeighborList(PathNode currentNode)
    {
        List<PathNode> neighborList = new List<PathNode>();
        GridPosition gridPosition = currentNode.GetGridPosition();
        int floor = gridPosition.floor;
        for (int x = -1; x < 2; x++)
        {
            for (int z = -1; z < 2; z++)
            {
                //Cannot be a neighbor to one's self, nor can floor above or below be a neighbor
                if (x == 0 && z == 0) continue;
                GridPosition testGridPosition = gridPosition + new GridPosition(x, z, 0);
                //If position is NOT walkable on the same floor
                if (!IsWalkableGridPosition(testGridPosition))
                {
                    //First rule out diagonals... a diagonal should not be a neighbor
                    if (Mathf.Abs(x) == Mathf.Abs(z)) continue;
                    
                    //Test floors above and below for walkable tiles
                    GridPosition floorAbove = testGridPosition + new GridPosition(0, 0, + 1);
                    GridPosition floorBelow = testGridPosition + new GridPosition(0, 0, - 1);
                    if (IsWalkableGridPosition(floorAbove))
                    {
                        neighborList.Add(GetNode(floorAbove.x, floorAbove.z, floorAbove.floor));
                    } else if (IsWalkableGridPosition(floorBelow))
                    {
                        neighborList.Add(GetNode(floorBelow.x, floorBelow.z, floorBelow.floor));
                    }
                }
                //At this point, the position is walkable on the same floor, so we can add it to the list.
                else
                {
                    neighborList.Add(GetNode(testGridPosition.x, testGridPosition.z, floor));
                }
            }
        }
        return neighborList;
    }

[heckert]

I’m definitely not against them. I’m just not sure that whatever issue I have that makes the flawed first part of the cross-floor pathfinding work as it does in the lesson might impact the following steps and I’d rather squish it soonest rather than hatching it and having even more difficulties in tracking it down.

Since all that GetNeighbourList() does is taking in one pathnode and collecting all nodes thar are adjacent in all directions without doing any logical selection except dropping all potential neighbours that actually don’t exist because they’re outside the grids’ bounds, this information should be static throughout the game.
Thus running through all pathnodes once to gather this information and handing the cached list back (or rather a clone of it) should certainly speed up the pathfinding calculations quite a bit.
OTOH it won’t change any semantics so while I should make that change, it won’t help squishing the bug…

Debug.Log($"Total neighbours before: n-count: {neighbourList.Count} total-count: {totalNeighbourList.Count}");

So I get the same 8 neighbours around the unit on the same floor.

Debug.Log($"Total neighbours after: {totalNeighbourList.Count}");

This is when all neighbouring “above” and “below” nodes are added to the totalNeighbourList.

When this output is activated, I also get “Total neighbours after culling: 16”, so the 8 potential grid nodes on floor 2 (which doesn’t exist) get thrown out.

GetNeighbourList() appears to be correct, so my next guess would be that within the MoveAction inside of GetValidActionGridPositionList() some are sorted out as invalid, that shouldnt…

In particular…

for (int x = -_maxMoveDistance; x <= _maxMoveDistance; x++)
{
  for (int z = -_maxMoveDistance; z <= _maxMoveDistance; z++)
  {
    //for (int floor = 0; floor <= _maxMoveDistance; floor++)
    for (int floor = 0; floor < LevelGrid.Instance.FloorAmount; floor++)
    {
        GridPosition offsetGridPosition = new GridPosition(x, z, floor);
        GridPosition testGridPosition = unitGridPosition + offsetGridPosition;
        // Is the test position within the bounds of the grid?
        if (!LevelGrid.Instance.IsValidGridPosition(testGridPosition)) continue;

So… We take a subset of the grid around the unit limited by the maxMoveDistance, and for each position we then go through all floors…

unit at (ux,uz, floor==0)
loop floor 0: offset is (x,z, 0) → testGridPosition is (ux+x, uz+z, 0)
loop floor 1: offset is (x,z, 1) → testGridPosition is (ux+x, uz+z, 1)
So this should still be a valid grid position and my debug-rays do show rays going from the unit on floor 0 going up to floor 1 positions in its range…
For some reason they don’t get to be valid target positions though…

unit at (ux,uz, floor==1)
loop floor 0: offset is (x,z, 0) → testGridPosition is (ux+x, uz+z, 1)
loop floor 1: offset is (x,z, 1) → testGridPosition is (ux+x, uz+z, 2)

This looks like there is an issue, right here. Setting the testPosition’s floor to the loop floor is fine, but we can’t allow using the unit’s floor value at this point…

This would explain why no rays go from the floor-1 unit down to floor 0.

Let’s fix it, and go on…

     GridPosition offsetGridPosition = new GridPosition(x, z, 0);
     GridPosition testGridPosition = unitGridPosition + offsetGridPosition;
     testGridPosition.floor = floor;

And suddenly there are rays going from the floor-1 unit down to floor 0, as there should be.

[heckert]

And the floor-0 nodes right beneath the floor-1 unit now become valid movement targets, similar to what the lesson shows.

But they’re still confined to the area of floor-1.

One difference I saw in the level layout of my project was that I had the wall set so the top floor has complete grid cells and the lower floor end right at its cell boundary.
In the course the layout is so that there is one position on the higher floor that is only supported half way and the other is in the air.
I retracted my walls around floor 1 for one unit and everything appears to be working, just as shown in the lesson.
(Only that the amount of debugging draws happening is insanse and really slows the game down).

So, I will adjust my level accordingly, drop all debug messages/draws, and maybe do the neighbour nodes optimization…

[heckert]

Even with all debugging output neutralized it’s still somewhat jaggy. It should still be finre for now so I can safely continue to the next lesson…

[Brian_Trotter]

I made a couple of optimizations to the movement code (caching paths once calculated)…

Caching paths for smoother Move times

As has been noted in several posts, the Movement calculations in our system can be rather expensive, enough to slow the system down, and create noteable pauses when we move on a tile. Much of this is due to repeated calls to our PathFinding. For example: Our pathfinding is called for each potential move tiles once to determine if there is a path, and again to determine the length of that path. Within MoveAction, we currenntly have these checks to Pathfinding for each tile being tested: …

[heckert]

Well, as the old saying goes… Step one is making it work. Step two is making it work efficiently…

[heckert]

So, caching neighbours improved it a little bit but there’s still a some jaggedness during a unit’s movement which is somewhat surprising at first since the MoveAction doesn’t do anything special inside its Update().
Digging a little deeper and I find that the cause is actually the GridSystemVisual updating the MoveAction target cells at each step of the unit, which is triggered by listening to OnAnyUnitMoved (which is triggered by the unit itself checking within its Update() on whether its current position is still the same grid position it remembered from last frame).
And to do this visual update, the GridSystemVisual runs UpdateGridVisual() which refreshes the shown visuals and to do so it calls the action’s GetValidActionGridPositionList(), and here we go through pathfinding on all potential target positions in the squared range of maxMoveDistance…

So the solution to improve this bit would be to have the GridSystemVisual tap into OnActionStart/OnActionCompleted and only update the visuals once, when the movement has finished.

Thus:

GridSystemVisual.cs
@@ -36,8 +36,12 @@ public class GridSystemVisual : MonoBehaviour
+    [SerializeField] private bool _updateVisualsDuringAction;
+    private bool _isActionInProgress = false;
 
     List<GridVisualTypeMaterial> _activeMaterialList;
@@ -102,6 +106,12 @@ public class GridSystemVisual : MonoBehaviour
         }
+
+        if (!_updateVisualsDuringAction)
+        {
+            BaseAction.OnAnyActionStarted += BaseAction_OnAnyActionStarted;
+            BaseAction.OnAnyActionCompleted += BaseAction_OnAnyActionCompleted;
+        }
     }
 
@@ -138,6 +148,10 @@ public class GridSystemVisual : MonoBehaviour

     private void LevelGrid_OnAnyUnitMovedGridPosition(object sender, EventArgs e)
     {
+        if (_isActionInProgress)
+        {
+            return;
+        }
         UpdateGridVisual();
     }

+    private void BaseAction_OnAnyActionStarted(object sender, EventArgs e)
+    {
+        _isActionInProgress = true;
+    }
+
+    private void BaseAction_OnAnyActionCompleted(object sender, EventArgs e)
+    {
+        _isActionInProgress = false;
+        UpdateGridVisual();
+    }

[Brian_Trotter]

I’m not sure in which lecture, but at a certain point, @CodeMonkey makes this subtle change to the GridSystemVisual, and it does make a striking difference in movement performance.

        UnitActionSystem.Instance.OnBusyChanged += UnitActionSystem_OnBusyChanged;
        //LevelGrid.Instance.OnAnyUnitMovedGridPosition += LevelGrid_OnAnyUnitMovedGridPosition;

This change means the visuals only update after an action is completed.

[heckert]

@Brian_Trotter

This change means the visuals only update after an action is completed.

Exactly, because updating the visuals required running the whole pathfinding calculation on each step of the move which made the whole action stutter. Only updating the grid visuals after the action has completed eliminates the issue.

At the end of my current lecture (where the jump/drop animations for moving between floors were added) he mentions there being an issue with adding too many floors and later on he will give some improvements… Since I made it configurable, if I wanted dynamic updates back all I need would be setting a flag in the inspector

[Brian_Trotter]

It’s also why I was scratching my head when you said that the movement was stuttering… I was running the final course code, where Hugo had already fixed the issue.