I have been reading quite a bit in order to make the following choice: which path-finding solution should one implement in a game where the world proceduraly generated, of really large dimensions?
Here is how I see the main solutions and their pros/cons:
1) grid-based path-finding - this is the only option that would not require any pre-processing, which fits well. However, as the world expands, memory used grows exponentially up to insane levels. This can be handled in terms of processing paths, trough solutions such as the Block A* or Subgoal A* algorithms. However, the memory usage is the problem difficult to circumvent;
2) navmesh - this would be lovely to have, due to its precision, fast path calculation and low memory usage. However, it can take an obscene pre-processing time.
3) visibility graph - this option also needs high pre-processing time, although it can be lessened by the use of fast pre-processing algorithms. Then, path calculation is generally fast too. But memory usage can get even more insane than grid-based depending on the configuration of the procedural world.
So, what would be best approach (others not present in this list are also welcome) for such a situation? Are there techniques or tricks that can be used to handle procedural infinite-like worlds?
Suggestions, ideas and references are all welcome.
Just to give more details, one should see the application I am talking about as a very very large office level, where rooms are generated prodecuraly. The algorithm works like the following. First, rooms are placed. Next, walls. Then the doors and later the furniture/obstacles that go in each room. So, the environment can get really huge and with lots of objects, since new rooms are generated once the players approaches the boundary of the already generated area. It means that there will be not large open areas without obstacles.