9. Waypoint system

9.1 Waypoints

In Quake the bot must be able to travel from one point to another in the 3D environment. For instance the bot is currently at a specific point and knows the location of an item and wants to get there. The bot should be able to find the shortest path towards an item. To be able to calculate how to travel from one location to another the bot needs knowledge about the 3D environment. The Omicron bot uses a waypoint system to store this knowledge. A waypoints system is a representation of the 3D environment which stores the knowledge needed to calculate how to travel between different locations.


            network of waypoints with reversed reachability links

A waypoint system is a set of points in the 3D environment with reachability links between them. This waypoint system can be represented by a set of waypoints. The waypoint object stores a location and reachability links. The location of a waypoint is stored as a x, y and z coordinate in the right handed coordinate system used by Quake. Every waypoint has pointers to other waypoints. These pointers represent reversed reachability links. A pointer from waypoint V to waypoint W represents the knowledge that the bot can travel in a straight line from waypoint W to waypoint V. The links are stored reversed, because that way they are easier to use by a routing algorithm. A link is only stored, when there is a path between two waypoints the bot can travel along in a straight line. For each link also the distance between two linked waypoint is stored. A set of these waypoints represent a directed network of points in the 3D environment.

Specification of a waypoint:

          Pathlink :: number : N
                            distance : R

          Origin :: x : R
                        y : R
                        z : R

          Waypoint :: number : N
                              origin : Origin
                              pathlinks : Pathlink-set

9.2 Waypoint placement

The waypoints need to be efficiently placed in the Quake environment. It is most efficient to have as few waypoints as possible, but there have to be enough of them to give the bot the ability to travel from each location to any other. The less waypoints are used, the less space is required to store them. Calculating routes will also be faster, if there are less waypoints.

The Omicron bot dynamically places the waypoints, when exploring the environment. When the bot walks around it drops waypoints and by doing that, it remembers where it has been before and ofcourse it creates the representation of the Quake environment, needed to calculate how to travel between different locations. To explain the waypoint placement, reachability is used. This will be explained in the chapter Environment sampling.


        dynamically placed waypoints (blue stars)

In order to achieve the most efficient waypoint placement, when walking around, the bot keeps in mind the closest waypoint from which the current bot location is reachable. In the real-time environment the bot searches for this closest waypoint 10 times a second. When such a waypoint is found the bot keeps this waypoint in mind. As soon as the bot can't find a closest waypoint from which the current bot location is reachable the bot tries to drop a new waypoint. This waypoint should be dropped at the previous location (the location 0.1 seconds back in time) when there was still a closest waypoint from which that location was reachable. When a new waypoint is dropped, the reachability between this waypoint and the last remembered one is verified and a reachability link is created, if appropriate. Reachability links are also created, when there is a change from one waypoint to another, being the closest from which the bot location is reachable. The link is created between the last closest and the new closest waypoint, when the reachability is verified.

There are situations, the bot may not drop a waypoint, although there is no closest waypoint. When the bot isn't swimming, the bot must be on the ground to drop a waypoint. If the bot isn't on the ground, it could be at a location in mid air which is not reachable from any waypoint with normal movement (walking, jumping etc.). The bot is most likely not able to reach such a location a second time. The bot may also not drop waypoints on top of elevators. When the elevator is in one position the location on top of it might be reachable from certain waypoints, but in another position it might not be reachable. In general the bot may not drop waypoints on top of any moving structural system because the same kind of problem might occur. The bot also may not drop waypoints in lava or slime because the bot doesn't want to travel through such deadly fluids.

The Omicron bot uses a few special waypoints. These waypoints store additional information about the environment.


      item waypoint (yellow star) for the double shotgun

One of the special waypoints is the 'item' waypoint. Item waypoints are placed at the bottom center of the item. An item waypoint stores the knowledge there is an important item nearby and also stores which item it is. The 'item' waypoints aren't dropped for all items, only for the most important ones. These items are all weapons and all powerups except health and biosuit. For reachability the item waypoints are used just like normal waypoints. An item waypoint is dropped, when the bot touches the item. For one item at most one waypoint is placed.


                    teleporter waypoint (white star)

For teleporters also special waypoints are used. The teleporter waypoints are placed at the bottom center of teleporters. The waypoint stores the knowledge, the player will be teleported to another location, when approaching. There's a link from a waypoint at the teleporter destination to the teleporter waypoint. The distance stored with this link isn't the real distance because the teleporter transports a player to another location without traveling along a path. However, the teleportation takes a few tenth of a second and that's why the distance a player can run in this time is stored with the link. The teleporter waypoint is dropped, when a bot uses the teleporter. For each teleporter at most one such a waypoint is placed.


elevator top (red star) and bottom (orange star) waypoint

For elevators two special waypoints are used. One waypoint for the bottom and one for the top position of the elevator. The bottom waypoint can only be marked as reachable, when the elevator is in the bottom position. The reachability of this waypoint tells the bot if the elevator can be used to go up or not. The waypoint at the elevator top position is used in the same way as normal waypoints, with respect to reachability. The elevator waypoints are dropped, when a bot uses the elevator. For one elevator at most one bottom and at most one top waypoint is placed.

There are no special waypoints for the other structural systems.
 

9.3 Routing

To get from point A to point B in the 3D world the bot could calculate a route as a list of points. The bot can travel from one point to the next in this list to follow the route. The first point in this list is the location of A and the last point is the location of B. The other points in this list are the positions of waypoints. Each point in this list is reachable from the previous one. Such a route could be calculated using a network of waypoints. A route stored as a list of points calculated once isn't very flexible when used. The bot can't deviate too far from a route because the bot always needs to get back to it follow the route. If the bot can't get back to the route it has to calculate a new one.

Because the Omicron bot operates in a real-time environment and needs a flexible system the routes aren't stored as list of points. The Omicron bot doesn't calculate a route in advance but dynamically chooses waypoints leading towards a goal. From the waypoints that are reachable from the current position the bot chooses the one closest to it's goal and moves towards this waypoint. When arriving at that waypoint the bot chooses the next reachable waypoint closest to it's goal. The bot follows waypoints this way until the goal is reached.

The bot needs to know the distance towards the goal for every reachable waypoint in order to choose the closest one. For a specific goal all the distances of the waypoints towards this goal are calculated and stored. For goals which are often used by bots the distances are cached.
 

Routing algorithm

To calculate the distances a cache update algorithm is used. This algorithm works as follows. The waypoint nearest to the goal and from which the goal is reachable, is started with. The distance from this waypoint to the goal is stored. From this first waypoint the distances towards the goal of the other waypoints are calculated. In doing so, a sequence of waypoints is maintained. Waypoints are always read from the front of the sequence and written at the end of the sequence. The first waypoint (the one started with) is initially placed as the only waypoint in the sequence. Waypoints are taken from the front until the sequence is empty. For each waypoint of the sequence all the waypoints, from which that waypoint is reachable, are taken into account. These are the waypoints pointed to by the reachability links of the waypoint from the sequence, because all the reachability links between waypoints are stored in reversed order. For a waypoint, where a reachability link points to, the distance towards the goal is calculated. This distance is the distance to the former waypoint from the sequence plus the distance towards that waypoint. This last distance is stored with the reachability link. When the distance is calculated and there isn't a distance stored for the waypoint yet, or the calculated distance is shorter than the already stored one, this new distance is stored for the waypoint. When a new distance is stored, the waypoint is written at the end of the sequence, if it is not already in the sequence. This process continues until the sequence is empty. At that moment for all waypoints the shortest distance towards the goal is calculated and stored.

Here's an example. The same network as above has been taken but here the reachability links with distances are given.
 

         network of  waypoints with reachability links and distances
 

The sequence with waypoints will be represented here as "sequence = [waypoint numbers separated by commas]". The distances stored for waypoints will be represented here as "distances = {pairs of (waypoint number, distance) separated by commas}.

Lets assume waypoint 1 is the closest one from which the goal is reachable. The distance from waypoint 1 towards this goal is 5. This first waypoint will be placed in the sequence: "sequence  = [1]". The distances are initialized to "distances = {(1, 5)}". The first waypoint is taken from the sequence. Following the reachability links, the waypoints 2 and 4 are found. The distance from waypoint 2 towards the goal is calculated. This distance is 5 (from waypoint 1 to the goal) plus 7 (distance along reachability link) which makes 12. For waypoint 2 isn't a distance stored yet and therefore the new distance will be stored. The waypoint isn't in the sequence already so it is written to the end of it.

"sequence = [2]"
"distances = {(1, 5), (2, 12)}"

The distance from waypoint 4 towards the goal is 5 + 8 = 13. There also isn't a distance stored for this waypoint so the new distance is stored. This waypoint is also written to the end of the sequence.

"sequence = [2, 4]"
"distances = {(1, 5), (2, 12), (4, 13)}"

Waypoint 2 is taken from the front of the sequence and the reachability links are followed. Waypoints 1, 3 and 4 are found. The distance from waypoint 1 to the goal is calculated. This distance is 12 (from waypoint 2 to the goal) plus 7 (distance along reachability link) which makes 19. This new distance is larger than the distance already stored for waypoint 1 (which is 5). That's why the new distance isn't stored and waypoint 1 also isn't written to the end of the sequence. The algorithm continues with waypoint 3. The distance towards the goal is 26. There wasn't a distance stored for waypoint 3 so the new distance is stored. This waypoint is written to the end of the sequence. Then the distance from waypoint 4 towards the goal is calculated. The distance from this waypoint towards the goal is 12 (distance stored for waypoint 2) plus 18 (distance from waypoint 4 to waypoint 2) which makes 30. This new distance is larger than the one already stored. The new distance isn't stored and the waypoint isn't written to the end of the sequence. The new configuration is:

"sequence = [4, 3]"
"distances = {(1, 5), (2, 12), (3, 26), (4, 13)}"

Now waypoint 4 is taken from the front of the sequence. Following the reachability links the waypoints 3 and 5 are found. For waypoint 3 the calculated distance is 13 + 12 = 25 which is shorter than the already stored one. This new distance is stored for waypoint 3. The waypoint isn't written to the end of the sequence because it is already in the sequence. The distance calculated for waypoint 5 is 13 + 16 = 29. This new distance is stored for waypoint 5 because there wasn't stored one yet. The waypoint is also written to the end of the sequence. The new configuration is:

"sequence = [3, 5]"
"distances = {(1, 5), (2, 12), (3, 25), (4, 13), (5, 29)}"

The configuration after processing waypoint 3 and 5  is listed here.

"sequence = [6]"
"distances = {(1, 5), (2, 12), (3, 25), (4, 13), (5, 29), (6, 44)}"

Waypoint 6 is taken from the front of the sequence and the reachability links are followed. Only waypoint 5 is found. The calculated distance for this waypoint is 44 + 15 = 59. This distance is larger than the already stored on for waypoint 5. The waypoint isn't written to the end of the sequence. The sequence has become empty and the process terminates. For all the waypoints the shortest distance towards the goal is stored.

Using the calculated distances the Omicron bot can now choose from the reachable waypoints the one closest to it's goal.