Creating high quality indicative routes in heterogeneous virtual environments

Abstract

In this thesis we will attempt to close the gap between fast grid-based method and epsilon-approximation methods that solve the Weighted Region problem. In order to compare both methods, we will define a formula to calculate the epsilon-value of grid-based methods and define the bounds of the epsilon-value for epsilon-approximation methods. Furthermore, we will improve on heuristics for A* grid methods for weighted regions and present an adapted version of the Hierarchical A* method that improves the running times of A* grid in heterogeneous environments. Finally, we present three pruned-graph methods that reduce the construction and query times of Steiner-graph methods.