I agree upon the other answers her already, but also, try to think of WoW/Warcraft3 as actual 2D worlds. They arent that different from tilebased, its just the tiles.
You could also think of how does a GPS find the best path? there a loads of algortimns for pathfinding through linked maps.
I think some of the first "Quake bots" scripts also might help you, as they were developed to work in "unknown areas" because we could design our own levels from scratch.
All in all, my personal way to deal with such a map, would be to think of it as the A* pathfinder. But first I would pre-calc every "tile point" and index all these with "nearest neighbour" etc. Then when an object needed to go from A to B then just lookup in B, see to what its connected and keep repeating until you reach the goal.
Depending on the type of game and landscape/scenario, different pre-scan tactics might be usefull too. Some games have very little obstracles and these can be "streight line" movement + some "how do I get around" for objects.
Hope this makes a little sense and perhaps gave you some thoughts to work with.