Complex maps (that is have lots of wall corners) adds up more nodes. Open areas with lots of surrounding walls are dangerous, the amount of links can become impossible due to permutations. Some algoritms have a way to cope with that but has it's own drawbacks (it is said?), I haven't encountered any though (if anyone knows, let me know).

I've thought of considering BSP a good solution, for maps with low amount of nodes (or relatively sparse) but irrelevant amount of links allowing huge spaces without being a drawback for speed and especially memory. If a partition contains no walls it doesn't need to be further partitioned either. Between two sisterpartitions, the shortest way from two points is straight. Between two aunt-related partitions the shortest way can be both straight and pass trough the nephew's sister. Between two higher level related points pathfinding is delegated via common mother, starting delegation at closest daughter partition. If neither daugthers fails the pathfinding problem is raised onto the common mothers mother. If she doesn't have a mother, there is no connection between the points.