Modern navigation systems often provide to the users more than one paths (also called routes) from a starting location (called start or source) to the destination location (called target). The goal is to provide the users with multiple options so that they can choose a route of their choice for traveling. Consider the image below where Google Maps shows three different routes from Liverpool to Auburn (two towns in Sydney).
Intuitively, the routes provided to the users should be significantly different from each other but should have similar traveling time (so that the users have more diverse but feasible options). We call these multiple routes provided to the users "alternative routes". It is not easy to formally define what is a set of "good" alternative paths. However, intuitively, these alternative paths should be significantly different from each other and must be meaningful (e.g., should not contain unnecessary detours or U-turns etc.). Since the quality of alternative paths is subjective, typically user studies are conducted to evaluate what the users perceive to be good quality alternative paths.
While there has been a lot of existing work on recommending alternative routes in road networks (e.g., Google Maps and other navigation systems), there has not been much work on computing alternative routes in computer games. Unlike roads where users can only travel on the roads, in game maps, characters can move anywhere on the plane except the areas blocked by obstacles (e.g., buildings, forests etc.). Consider the image below that shows the Hills of Glory map from the Warcraft 3 game. Here, a game character can only move within the white area - the grey area represents obstacles and the character cannot enter or pass through the grey area. The red and green circles correspond to the start and target and the image shows four alternative paths between the start and target. The green path is the shortest path from the source to the target and its length is 291.7. The blue, purple and red paths are three other alternative paths with lengths 311.5, 329.2 and 403.4, respectively. In some cases, corners of two obstacles touch each other (see the two blue ovals in the image below that show two examples of obstacles touching each other at corners). Our implementation assumes that a valid path can pass through such corners, i.e., the blue path is a valid path.
You may be wondering why the alternative paths are important in computer games. If a character (or a set of characters) are to be moved from one location to another, typically a shortest path is computed and the character is directed to follow this path to reach the target. However, in many cases, it is desirable to have more than one paths for the character(s) to choose from. Consider the example where a set of army units wants to attack a target location. Sending all the units through the shortest path is not the ideal option (e.g., the path may pass through narrow valleys and may be congested, there is a significant risk of losing all or majority of the army units if the path passes through an area which can be easily attacked, it may be better to attack the location from different directions etc.). Therefore, it may be preferable to disperse different units on different alternative paths. Also, in strategy games, if the opponent character always takes the shortest path to the target, their moves/plan may become predictable. Therefore, it may be better to compute alternative paths and randomly assign one of the alternative paths to the character. Similarly, a robot moving in an indoor venue (e.g., a warehouse) may want to look at several alternative paths to make a decision on what path to take to reach the target.
Since there is no well-established and formal definition of what constitutes a set of high-quality alternative routes, we are conducting a user study to understand which of the existing techniques generate good quality alternative routes (as perceived by the users). In this research, we have selected three different approaches (named A, B and C for anonymity) that compute four alternative paths in game maps between the start and target. We display the alternative paths generated by the three approaches and ask the users to rate each approach from 1 to 5 (higher the better).
We request you to complete two different sets of questions (the links are given at the end of the page). In the first set of questions, you will be shown some pre-selected start and target pairs on different game maps. There are 9 game maps and you will be shown three sets of start-target pairs for each game map (e.g., 9x3=27 in total). In the second set of questions, you can select the start and target yourself by clicking anywhere on the map. Please do not choose start/target on obstacles (grey area) as there is no path to/from the grey area to any other location on the map. Again, there are 9 game maps and you can select as many start-target pairs on each map as you want (minimum 1 for each map).
Please view the alternative paths generated by an approach by clicking the radio button next to it. For each approach, choose its rating between 1 to 5 (higher the better) and click "Submit" to submit your ratings for all three approaches. The lengths of all alternative paths will also be shown (see the image above). At any stage, if you want to submit a comment (optional), you can write the comment in the comment box before pressing the "Submit" button. You can also zoom in/out using the "Map Scale" drop-down menu.
The explanatory statement contains further information such as consent, possible risks and benefits for participants, confidentiality, storage of data, results and complaints etc. Click here to access the explanatory statement.
Please complete both of the following surveys. We recommend you to complete "Pre-selected start-target pairs" first so that you are used to the system before you select your own start-target pairs.
* Please email me if the above links do not work. My email address can be found at home page.