Binary Space Partitioning algorithm for the navigator agent in the Virtual Environment

ABSTRACT
Virtual environment can be brought to life by adding walking characters (navigator agent)
to enhance the navigation process. The navigator agent helps the visitor to find specific locations
in the virtual environment. It is specialized in determining appropriate free and safe paths through
the virtual environment, and can provide guidance to the user that tries to follow such paths. Path
finding depends on a number of waypoints to be set out in the virtual environment. The navigator
agent receives an initiation message from the headquarter agent depends on the reaction of the
watching agent and sends a request to the navigation module to plan the shortest and safe path.
This paper discusses the development of a real-time navigation algorithm for the navigator agent
as a guide tour through the virtual environment. The algorithm is handled by two channels. The
first is the 3D Graph, which contains all nodes and path structure information. The second is the
Motion Planning channel, which calculates the fastest route through the path structure from the
current position to a destination position. This algorithm is called Binary Space Partitioning
Algorithm (BSP). BSP divides the 2D map of the Virtual Environment into two configurations or
more depending on the start and destination locations, after that it generates two trees, one from
the initial side (Tstart) and the second from the destination side (Tgoal). The navigator agent uses
join algorithm to connect these trees together. A path is found when the two trees can be
connected. Finally, the navigator agent provides two choices for the user, the first one it draws a
generated path on the scene, then the user follow this path or, the second choice is the navigator
agent calls the animation algorithm to move on the path as a tour guide for the user. The time has
been taken to explore the virtual environment by using the Binary Space Partitioning algorithm is
decreased approximately by the half compared by the traditional motion-planning algorithms.