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