World built at runtime with prefabs

So I have a world that is generated from prefabs at runtime. “Rooms” and items in them are determined and placed when the generation script is called. They can be at different depths along the Y axis (above and below each other). The total scene bounds could encompass as much as 256 in the y axis, and 2048 in the x and z axis. Given this information, what would be the best approach to building the grid graph, and what type?

The ideal setup, I think, would be to add model a navmesh for each prefab. Then add a script to that prefab at runtime to add a graph to the Astar Path, using the proper mesh, and offset it to the position of the prefab. Finally, run a scan. Does this sound feasible?

That is possible, it is the solution that is used in Folk Tale: http://www.gamesfoundry.com/
However it requires a lot of work and code to get it to work well.

My suggestion is that you have a grid graph in the scene which covers the maximum bounds the scene can have. After placing all prefabs, you just call AstarPath.active.Scan () and let it scan all the prefabs.