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.
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.
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.