Dynamic Pathfinding

Hi, I’m currently working on a game that creates a randomized maze using tiles and such, and to make it even more complex it regenerates parts of it as the game goes. What I would like to do is add some AI within the maze to track and follow the character.

My issue is that since everything is generated at run time, I naturally can’t use a navmesh (at least as far as I know…) so that’s out. I’ve messed with the Astar A* Pathfinding and it sorta works, but it causes issues with lag when it needs to recheck the grid. So I’m just wondering if anyone knows of a more efficient way or a way to optimize the pathfinding.


With A*, you only need to calculate the pathfinding mesh/grid when your maze is generated. Afterwards, there’s optimized ways to update your pathfinding when you spawn in your objects without completely generating the whole thing again. Unity’s native NavMesh has a form of this, but I’m not sure if it’s that efficient if you have a whole bunch of them.

Essentially, you could use the native AI in Unity, but it might not be that efficient if you have a lot of these dynamic objects (which is essentially your whole maze).