Binary Space Partitioning algorithm for the navigator agent in the Virtual Environment | ||||
The International Conference on Electrical Engineering | ||||
Article 13, Volume 5, 5th International Conference on Electrical Engineering ICEENG 2006, May 2006, Page 1-16 PDF (254.72 K) | ||||
Document Type: Original Article | ||||
DOI: 10.21608/iceeng.2006.33525 | ||||
View on SCiNiTO | ||||
Authors | ||||
Khaled Elmenshawy; Ismail Abd-Elghafar; Ali Ali Fahmy | ||||
Abstract | ||||
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. | ||||
Keywords | ||||
Virtual Environment; navigator agent; watching agent; headquarter agent | ||||
Statistics Article View: 126 PDF Download: 194 |
||||