My graph is changing a lot, my whole environment from walls to objects is destructable and contains complex logic like access controlled doors.

Maybe your game doesn't change much. Lack of good pathfinding is what's constricting that the most. If good pathfinding existed, games in general could become more dynamic.