Worst-case optimal exploration of terrains with obstacles