GetValidGridPositions() performance using pathfinding

[shaggy]

I’m working on a pretty large grid (~30x15) and a very high maximum move distance, and performance of this function seems quite bad . While it’s not noticeable when I have a smaller grid, or smaller maximum move distance, I notice my game freezing when this function gets called now.
I’m taking every grid object within the maximum move distance, checking if it’s walkable, and then calculating the Path there, to see if it’s reachable and if the path is not too long.

Trying to calculate the path to every single possible grid position this way seems to get very performance-hungry very quickly. I hope to get some suggestions / approaches on how to make this more manageable.

And ofc thanks CodeMonkey for the amazing course, it’s helped and taught me a ton already.

Edit: Doing it once to check for valid positions before moving is fine performance wise (albeit with a noticable dip in fps), but my PC starts suffering if I want to use it for things like:

• displaying and updating the grid visuals, to display the path the player would take to get to the mouse position, and showing all valid positions the player can move to
• calculating it from multiple different positions to find the best possible enemy AI actions

Edit#2: I am working with a Hex grid in case that would change things in a significant way. Currently brainstorming some ideas on how I can significantly increase the amount of GridObjects that I can add to the valid list, or eliminate, before I actually have to call pathfinding on them.

[Brian_Trotter]

The pathfinding setup we’re using in this course is not the most efficient setup possible. Ultimately, @CodeMonkey recommends using the A* Pathfinding Project but this is, of course, a paid option.

There are a couple of tweaks I can recommend to help reduce the load in the Pathfinding System.

• Add all nodes with a Distance lower than the maximum move distance to the closed list. This will help reduce the number of nodes tested.
• At the beginning of each Unit’s turn, cache all paths (within the max move distance) in a Dictionary<GridPosition, List<GridPosition>>. Consult this Dictionary rather than calculating a new path multiple times for various possible AI Actions.

[bixarrio]

Some more options could include the ‘Jobs system’ which is a more advanced topic but could significantly improve the performance.

Also, the game freezes because it’s doing the whole thing in a single frame. You could try to spread the algorithm over more frames, but I don’t know how well this would work. Usually frames a pretty fast and taking 3 or 4 frames to calculate the paths at 60fps will only take ~0.06 seconds. It’s not great, but at least you won’t freeze the game.

A completely different option is to track the mouse. Don’t show all valid positions at once, but track the mouse and only calculate a path to the cursor (when it’s over the tiles). Then show only the path to that position. It will require the player to ‘scan the map’ with the mouse to determine where they could legally go. It’s an example of how technical limitations shape game mechanics.

[shaggy]

Thank you and @bixarrio for your answers!

I have another question concerning the performance. Do the GetPathLength & IsValidPath functions in the Pathfinding class have to fully execute and complete the FindPath function anyway? Or is there some automatic optimization going on behind the scenes when those functions are called, as opposed to directly calling FindPath and getting the information from that?

[shaggy]

Update: I’ve thought about my problem more, and figured that just occasionally calling pathfinding on a relatively “small” grid like mine should really not be such a big performance problem.
I then narrowed down the problem to my specific attempt at creating smart enemy AI, there was a lot of performance loss there, as opposed to just getting valid grid positions and finding paths occasionally, like on events triggering to update visuals.

Updating Visuals for all possible move positions, and showing the path to the mouse, still have an impact on performance but it’s not super relevant.

One thing I did change about the GetValidGridPosition function of the MoveAction, that may or may not have helped, is the following:

I changed the code to start at the furthest positions within the maxMoveDistance (4 different for loops going from the maximum distance to 0, instead of one for loop going from -x -y to +x +y), calculate the path to them, and add all nodes in the Path to the List of valid grid positions.

Then, all the nodes that are already on the Path to the furthest Nodes can be ignored. Therefore, I only have to call Pathfinding to the outermost nodes, and to nodes that are hard to reach / not in the path to these nodes.

I’m not sure how much that improved the performance but in theory it should be a bit better. Would appreciate feedback on this, and if it’s possible to optimize the approach further, but other than that my main problem is solved.

[shaggy]

Actually, something very strange is happening. If I deactivate the gameobject that is responsible for updating grid visuals for valid move positions etc, and activate it after pressing play, it calculates everything very fast whenever it updates.

However, if the gameobject is active from the start, it’s extremely slow and lags out the game every time it updates.

My script has no Update function, it just uses events to update visuals. It has no Awake function, it subscribes to events and does the first update in Start(). It has the exact same functionality regardless of when it is activated.

What could possibly be causing this?

[Brian_Trotter]

If it’s not activated, Start() should never run, meaning it shouldn’t work… unless you have a different GameObject activating it.

I have no idea why it would work more efficiently activated after pressing Play rather than starting activated, that one is a mystery…

[shaggy]

well the solution in the end was very simple, I actually created a copy of the entire object with the script, instead of just the visual part, for every single grid position on start(). So basically with a large grid my grid visual script was running hundreds of times at once, explaining why the performance wasnt exactly great