Using a BFS to generate the valid positions for the move actions

Unity Courses Ask
, ,
#1

I find the GetValidActionGridPositionList() func very expensive, since it asks for the path length every time.
Instead of iterating trough a double for, and trying every combination of x and y in a set range, shouldn’t we ask the pathfinding script to give a list of accessible nodes in a set distance, using some king of a BFS ( Breadth First Search ) algorithm on the nodes? Then, the move action would apply the other validations on the list. This seems better in time and memory complexity than caching the distances with a dictionary in some way.
I have yet to implement the code, but what do you think about the idea?
(I tried to find another person talking about a BFS on this vid’s comms too, but didn’t find anyone)

#2

The BFS is essentially A* Lite. (Well, so is the A* Hugo has used, as it doesn’t include movement costs like if you were on a tile that slows you down). I actually find it less efficient than the simplified A* Hugo is using because it doesn’t factor total distance into the decision.

The biggest problem is that we’re calculating the path for each tile multiple times per square.
There are a few things we can do to speed up the calculations. This is why my choice is to either maintain a Dictionary of paths or to let the pathfindingnode itself hold the data for getting from the starting tile to that particular tile. We can also optimize by only pre-caching paths that make sense… for instance, if the distance to a tile is greater than the maximum move distance, there is absolutely no point in running it’s path.

There are some other optimizations… if we run our for loops right, from the inside out, then we don’t necessarily have to finish calculating all the paths if our pathfinding encounters a path already calculated on an existing node that it’s searching…

This is a rough idea, and it’s not tested yet, but I’m thinking if a PathNode contains a path from the origin to itself, and we’ve already determined it’s the closest search point to our origin (because we sort by FCost), then we would append the route to get here so far to the path of the node we know has a connection, cache it and return it.

So our initialization might look like

void CacheAllPaths()
{
    Pathfinding.Instance.ResetAllNodes();
    For(int x=0;x<=maxMoveDistance;x++)
       for(int z=0;z<=maxMoveDistance;z++)
       {
            if(x+z==0) continue; //skip current 
            Pathfinding.Instance.CachePath(gridPosition, gridPosition+new GridPosition(x,z));
            Pathfinding.Instance.CachePath(gridPosition, gridPosition+new GridPosition(-x,z));
            Pathfinding.Instance.CachePath(gridPosition, gridPosition+new GridPosition(x,-z));
            Pathfinding.Instance.CachePath(gridPosition, gridPosition+new GridPosition(-x, -z);
        }
}

This obviously doesn’t include the actual CachePath methods, and assumes gridPosition is set to the unit’s current position. It’s just demonstrating a way to branch out from the center location of the gridPosition.

I’ll see if I can find more time to flesh out the PathFinding changes needed for this.

#3
#4

Privacy & Terms