Are we talking pathfinding within rooms, or between rooms? I'm guessing between rooms, because pathfinding in a 3x3 grid is pretty trivial and you could basically brute-force it, try all permutations, and still perform pretty well.
I think the problem you're having is that the way you store your room layout (in a database) isn't really conducive to most path-finding algorithms, which assume that it's easy to load and traverse every node in the graph, right?
You've probably got a couple of options here:
- Limit the number of rooms you search, which limits how many rooms you're going to have to load. You're going to have a bunch of rooms in memory already to display them to the user, as a first pass you could just limit your path finding to whatever you've already got loaded. The downside here is that you might not find a path which twists through rooms that are not loaded.
- Pre-calculate some fraction of possible paths when you generate the level. This could potentially mean you have a whole lot more data to store.
- Some other data structure/storage mechanism for your level (e.g. a quadtree). This could be a lot of work...
As always, there's never a perfect solution.