This paper presents a new randomized roadmap method for motion planning for many dof robots that can be used to obtain high quality roadmaps even when C-space is crowded. The main novelty in our approach is that roadmap candidate points are chosen on C-obstacle surfaces. As a consequence, the roadmap is likely to contain difficult paths, such as those traversing long, narrow passages in C-space. The approach can be used for both collision-free path planning and for manipulation planning of contact tasks. Experimental results with a planar articulated 6 dof robot show that, after preprocessing, difficult path planning operations can often be carried out in less than a second.