The paper proposes an efficient method to plan a path for humanoid robots to locomote in rather complex life environments which are partially dense. The path planned by the proposed method means a transitional sequence of double-support postures, where both feet are in contact with the environment, and any pair of consecutive postures share one of the feet at the same position and attitude, due to alternation of the support foot. First, it finds a rough path by representing the robot body in a variable-volume box, and simultaneously, evaluates the sparsity/density of obstacles based on the volume. For segments of the path where the volume of the box is large enough to contain the whole-body, only the self-collision avoidance is considered and a simple navigation technique is applied. For the other segments where the volume is so small that the robot body is not fully contained within the path, a probabilistic method based on RRT-connect is applied in order to find a fine path on which the robot exploits its variable whole-body configuration. In this way, the robot automatically conforms its body representation to the evaluated complexity of the environment and balance the trade-off between the dimension of search space, namely, the variety of robot motions and the computation time, particularly in environments which are partially dense such as our life scenes.