10. Environment sampling

To analyze the surroundings the Omicron bot samples the environment. The bot has knowledge to calculate facts about the nearby environment. This knowledge is used at different points. The first is where the bot analyses the surroundings to base general decisions upon. In Quake this comes down to locating entities and hearing sounds of entities. The second is where the bot deals with moving towards a goal or into a certain direction. The bot analyses the surroundings to decide how to move. For instance walk, jump or swim.

10.1 Locating entities

The Omicron bot is able to locate entities in two ways. The first is visibility. If an entity is visible the bot can see it from it's current position. The second way the bot can locate an entity is to determine whether or not it is reachable. An entity is reachable, if the bot can travel towards the location of the entity in a more or less straight line. The traveling may be done by walking, jumping or swimming.

Visibility

In reality an object is visible, when light travels from the object to the viewers eye. This light is assumed to travel in a straight line. To calculate if an entity is visible in Quake a straight line is traced between the entity and the viewer's eye. When this line isn't obstructed by other objects, the entity is visible. In real life an object doesn't have to be visible when the light can travel in that straight line because there must be light in the first place. When an object is situated in a dark area, it might not be visible because there simply isn't any light. When calculating the visibility of entities in Quake, the presence of light is not taken into account. In reality there might be traveling many light rays from an object to the viewers eye. To determine visibility in Quake only one straight line is traced from the center of the object to the viewers eye, because tracing many light rays would be too time consuming.

Reachability

The Omicron bot only marks entities as reachable, if the bot can move towards the location of the entity in a more or less straight line. An entity that is situated around the corner, for instance, won't be recognized as reachable. The algorithm used to calculate reachability doesn't mark all entities as reachable, that actually are. The algorithm is designed recognize entities as unreachable that aren't reachable.

The algorithm used to calculate reachability first traces a line from the bot location to the entity. When the traced line is blocked by another object, the entity isn't recognized as reachable. In the next illustration the entity is represented by a red dot and the bot location by the blue dot. In this illustration the entity can't be recognized as reachable, because the wall is blocking the traced line and the wall is too height to jump over.


              Reachability blocked by a wall.

If the entity is located lower and the traced line is blocked by another object the entity could be reachable. In the next image such a situation is illustrated. The location of the bot is represented by the blue dot and the entity by the red dot. To recognize such entities as reachable two new lines are traced. One horizontal from the current position to above the entity location. The second is traced from the location above the entity at the height of the current position to the entity.
 
 
                  Side view of an entity in a trench.

When the traced line isn't blocked by another object, the entity still doesn't have to be reachable. In the next image such a situation is illustrated. The entity is represented by the red dot and the location of the bot by the blue dot. However when the bot was located at the red dot and the entity at the blue one, the entity would be reachable.


                Side view of an unreachable place.

The following step of the algorithm is to check if the entity is located higher than the maximum jump height of a player. If this is not the case, the algorithm calculates if the bot can reach the entity with one jump at running speed. If the bot can reach the entity with one jump it is recognized as reachable. Otherwise the algorithm calculates if the bot can reach the entity with several jumps.
To do this the bot performs several imaginary jumps towards the entity. Every jump is to a location in the direction of the entity, at half of the the maximum distance a player can jump. At half the distance the bot is at the top of the jump parabola and also at the maximum jump height. From the start point the algorithm gets the floor height at the location half the maximum jump distance away. If the floor height is lower than the maximum player jump height relative to the start position, the bot continues with the imaginary jumps from this new location. If the floor height is higher than the maximum jump height, the algorithm checks if the bot can jump to a location a quarter of the maximum jump distance away. Again the floor height is calculated and compared to the maximum jump height. As long as the floor height is higher than the maximum jump height the distance of the imaginary jump is cut in half. When the distance has been cut in half more than a specific number of times, the destination is recognized as unreachable. If the bot finds a spot to jump to before cutting the distance in half more than the specific number of times, the bot continues performing imaginary jumps from the found spot. When the bot could perform several imaginary jumps to reach the destination, the entity is recognized as reachable.


Side view of stairs with steps the bot can only jump up.

In the above illustration the bot is located at the blue dot. The steps of the stairs are too high to walk up. The bot has to jump up to every next step. With the algorithm which performs several imaginary jumps the bot can also recognize the entity represented by the red dot as reachable in the above illustration.

10.2 Hearing entities

In the Quake environment the entities can produce sounds. The sounds can be heard, if they are able to travel from their origin to the player's ear through the geometry structures of the indoor Quake environment.

To be able the do something with the sounds caused by the entities, they are stored in a list for their duration. For a sound in the list the sound type, the location of the sound and the entity causing the sound are stored. Calculating how the sounds travels through the 3D environment and if a bot can hear the sounds at a specific volume, is quite complex. The Omicron bot can analyze sounds in two ways. It can verify if the sound can be heard and it can try to locate a sound.

Audibility

When calculating if a sound can be heard, the Omicron bot only takes the distance from the ear to the sound location into account. The bot knows the maximum distance at which the sound can be heard in an open space. This distance depends on the type of the sound. Simply calculating the distance between the bot's ear and the location of the sound and comparing this to the maximum distance, the bot can check, if the sound can be heard.

Locating sounds

When locating sounds the Omicron bot also doesn't take the geometry of the environment into account. The bot knows the maximum distance at which the sound can be heard in an open space. The bot calculates a probability the sound can be located by a human player. This probability depends on the number of entities located in a radius around the current position, that can produce the given sound. If it is likely enough, the bot is allowed to use the exact location of the sound.
 

10.3 Moving

The Omicron bot is able to move towards a nearby reachable goal. It is also possible to just move in a specified direction. The bot analyses the nearby surroundings to determine how to move. There are several possible ways to move. Among these are walking, jumping, swimming or a combination. When moving towards a nearby goal or in a specified direction, the bot always tries to move in a more or less straight line.

The first decision the bot makes, is whether to swim or not. When the bot is up to it's middle in a fluid, it will swim.

Swimming

When swimming under the fluid surface, a player has total freedom and can move in any direction. The bot tries to move straight into the given direction or towards the nearby goal. The bot checks for obstacles at the top, bottom and left and right and tries to avoid them. This way, it's like the bot is moving into a funnel towards the nearby goal or into the given direction. To find the obstacles the bot traces several lines.

Walking and/or Jumping

First the environment is sampled at the bot's feet to find a barrier, the bot can't just walk over. If a barrier is found the bot will try to jump upon it. If there wasn't any barrier, the bot searches for obstacles at the left and the right and in front. If obstacles are found at the left or the right, the bot will try to walk around them. If obstacles are found at the front, which the bot can't avoid, the bot is assumed to be blocked. Finally the looks for non walkable areas ahead. These non walkable areas are gaps in the floor, lava or slime. If such a non walkable area is found the bot will try to jump over the area. This is done by predicting the jump several seconds ahead, until the bot would land on the ground or in water. The prediction is done by calculating the expected movement of the bot in steps of 0.1 seconds. Collisions are calculated and the predicted movement is adjusted, when they are found. If the predicted jump will lead the bot into lava or slime, the bot is assumed to be blocked. Otherwise the bot will perform the jump.