Generating composite human motion such as locomotion and gestures is important for interactive applications, such as interactive storytelling and computer games. In interactive story environments, CG characters do not merely stand in one position. Rather, they should be able to compose gestures and locomotion based on the discourse of the story and the locations of objects in the scene. Thus, in the present paper, we propose a conversational locomotion model for CG character. We constructed a conversational locomotion network for a virtual environment. A multi-path searching algorithm calculates the optimal walking path, which uses node activation from the story locations and conversation units. The CG character also locally adjusts its position so that it does not block the referenced object from the user’s sight. We have applied the proposed technique to an interactive 3D movie system and have demonstrated composite motion of the locomotion and conversation of a CG character, which improves the immersion of the viewer in the story environment.