In the civilization series, auto-explore works by plotting out places where fog of war is still present and navigating towards them. If, once fog of war is clear, that it is evident that a portion of the map is inaccessible, the pathfinder gives up. If there are no fog of war left or no accessible patches of fog, the command is toggled off and no longer does anything. Such a system could work for MegaGlest (perhaps hinting the first place to look would be the corners of the map).