[Pierre-Marie Baty]

hehe, I *am* the TraceLine specialist here

If you only want immediate obstacle detection, you can use a few TraceLines like this:

void BotCheckForObstaclesAtFeet (player_t *pPlayer)
{
   // this function fills an integer bitmap describing the presence and quality of any
   // obstacle right around the bot. Useful for low walls over which the bot has to jump,
   // or for determining if the bot should duck to pass a low ceiling. This function is
   // called every frame, systematically, in BotSense(), so that the bot knows, when
   // it starts thinking, the quality of the terrain in front of it. First it checks if
   // it is about to hit something when walking forward, and if so, it checks if the bot's
   // look hits a wall when looking straight horizontally. If so, then the bot might be
   // able to duck over something to pass by ; if not, then the bot might be able to
   // jump over the obstacle ; we do the appropriate checks.
   // NOTE: player's origin is 37 units above the ground (standing height)
   //	   player is 36 units high when ducking
   //	   max stair height is 18 units
   //	   max jump height is 45 units
   //	   max jump height is 63 units when doing a duck-jump
   TraceResult tr1, tr2, tr3, tr4, tr5;
   Vector v_feet;
   float angle_diff, check_distance;
   float left_check_dst, front_check_dst, right_check_dst;
   pPlayer->Bot.BotBody.hit_state = OBSTACLE_NONE; // first off, reset the hit state bitmap
   // given the bot's velocity, bot will check closer or further forward (range 60-120 units)
   check_distance = 0.4 * pPlayer->pEntity->v.velocity.Length2D ();
   angle_diff = UTIL_VecToAngles (pPlayer->pEntity->v.velocity).y - pPlayer->v_angle.y;
   // we gotta transpose this distance to both sides of the bot (and also forward)
   // left distance
   pPlayer->Bot.BotBody.left_check_dst = check_distance * sin (angle_diff);
   if (pPlayer->Bot.BotBody.left_check_dst < 60)
	  pPlayer->Bot.BotBody.left_check_dst = 60; // bound it to 60 units minimum
   else if (pPlayer->Bot.BotBody.left_check_dst > 120)
	  pPlayer->Bot.BotBody.left_check_dst = 120; // and 120 units maximum
   // forward distance
   pPlayer->Bot.BotBody.front_check_dst = check_distance * cos (angle_diff);
   if (pPlayer->Bot.BotBody.front_check_dst < 60)
	  pPlayer->Bot.BotBody.front_check_dst = 60; // bound it to 60 units minimum
   else if (pPlayer->Bot.BotBody.front_check_dst > 120)
	  pPlayer->Bot.BotBody.front_check_dst = 120; // and 120 units maximum
   // right distance
   pPlayer->Bot.BotBody.right_check_dst = check_distance * -sin (angle_diff);
   if (pPlayer->Bot.BotBody.right_check_dst < 60)
	  pPlayer->Bot.BotBody.right_check_dst = 60; // bound it to 60 units minimum
   else if (pPlayer->Bot.BotBody.right_check_dst > 120)
	  pPlayer->Bot.BotBody.right_check_dst = 120; // and 120 units maximum
   // get a quick access to these three
   left_check_dst = pPlayer->Bot.BotBody.left_check_dst;
   front_check_dst = pPlayer->Bot.BotBody.front_check_dst;
   right_check_dst = pPlayer->Bot.BotBody.right_check_dst;
   // get the bot's feet position
   v_feet = pPlayer->v_origin; // take the origin...
   v_feet.z = pPlayer->pEntity->v.absmin.z; // and lower it at the bottom of the bounding box
   // check on the left
   // do a trace 17 units above max stair height left...
   UTIL_TraceHull (v_feet + Vector (0, 0, 18 + 18 + 17),
				   v_feet + Vector (0, 0, 18 + 18 + 17) - (pPlayer->v_right * left_check_dst),
				   ignore_monsters, head_hull, pPlayer->pEntity, &tr1);
   // do a trace one unit above max jump height left...
   UTIL_TraceHull (v_feet + Vector (0, 0, 18 + 64),
				   v_feet + Vector (0, 0, 18 + 64) - (pPlayer->v_right * left_check_dst),
				   ignore_monsters, head_hull, pPlayer->pEntity, &tr2);
   // do a trace one unit lower than max stair height left...
   UTIL_TraceHull (v_feet + Vector (0, 0, 18 + 17),
				   v_feet + Vector (0, 0, 18 + 17) - (pPlayer->v_right * left_check_dst),
				   ignore_monsters, head_hull, pPlayer->pEntity, &tr3);
   // is there something in the way at feet level that is not a slope AND nothing in the way at eye level ?
   if ((tr3.flFraction < 1.0) && (tr3.vecPlaneNormal.z < 0.5) && (tr2.flFraction == 1.0))
	  pPlayer->Bot.BotBody.hit_state |= OBSTACLE_LEFT_LOWWALL; // bot can jump over this obstacle
   // is there something in the way at eye level AND nothing in the way at knee level ?
   if ((tr2.flFraction < 1.0) && (tr1.flFraction == 1.0) && IsOnFloor (pPlayer->pEntity))
	  pPlayer->Bot.BotBody.hit_state |= OBSTACLE_LEFT_LOWCEILING; // bot can duck under this obstacle
   // is there something in the way at eye level AND something in the way at knee level ?
   if ((tr2.flFraction < 1.0) && (tr1.flFraction < 1.0))
	  pPlayer->Bot.BotBody.hit_state |= OBSTACLE_LEFT_WALL; // bot will definitely hit something
   // if the area is clear on the left at head level, trace down to check for a possible fall
   if (tr2.flFraction == 1.0)
   {
	  UTIL_TraceHull (v_feet + Vector (0, 0, 18 + 64) - (pPlayer->v_right * left_check_dst),
					  v_feet + Vector (0, 0, 18 + 64) - (pPlayer->v_right * left_check_dst) + Vector (0, 0, -250),
					  ignore_monsters, head_hull, pPlayer->pEntity, &tr4);
	  // did the trace hit nothing OR some water ?
	  if ((tr4.flFraction == 1.0) || (POINT_CONTENTS (tr4.vecEndPos) == CONTENTS_WATER))
		 pPlayer->Bot.BotBody.hit_state |= OBSTACLE_LEFT_FALL; // bot can fall on the left
   }
   // check in front
   // do a trace 17 units above max stair height forward...
   UTIL_TraceHull (v_feet + Vector (0, 0, 18 + 18 + 17),
				   v_feet + Vector (0, 0, 18 + 18 + 17) + (pPlayer->v_forward * front_check_dst),
				   ignore_monsters, head_hull, pPlayer->pEntity, &tr1);
   // do a trace one unit above max jump height forward...
   UTIL_TraceHull (v_feet + Vector (0, 0, 18 + 64),
				   v_feet + Vector (0, 0, 18 + 64) + (pPlayer->v_forward * front_check_dst),
				   ignore_monsters, head_hull, pPlayer->pEntity, &tr2);
   // do a trace one unit lower than max stair height forward...
   UTIL_TraceHull (v_feet + Vector (0, 0, 18 + 17),
				   v_feet + Vector (0, 0, 18 + 17) + (pPlayer->v_forward * front_check_dst),
				   ignore_monsters, head_hull, pPlayer->pEntity, &tr3);
   // is there something in the way at feet level that is not a slope AND nothing in the way at eye level ?
   if ((tr3.flFraction < 1.0) && (tr3.vecPlaneNormal.z < 0.5) && (tr2.flFraction == 1.0))
	  pPlayer->Bot.BotBody.hit_state |= OBSTACLE_FRONT_LOWWALL; // bot can jump over this obstacle
   // is there something in the way at eye level AND nothing in the way at knee level ?
   if ((tr2.flFraction < 1.0) && (tr1.flFraction == 1.0) && IsOnFloor (pPlayer->pEntity))
	  pPlayer->Bot.BotBody.hit_state |= OBSTACLE_FRONT_LOWCEILING; // bot can duck under this obstacle
   // is there something in the way at eye level AND something in the way at knee level ?
   if ((tr2.flFraction < 1.0) && (tr1.flFraction < 1.0))
	  pPlayer->Bot.BotBody.hit_state |= OBSTACLE_FRONT_WALL; // bot will definitely hit something
   // if the area is clear in front at head level, trace down to check for a possible fall
   if (tr2.flFraction == 1.0)
   {
	  UTIL_TraceHull (v_feet + Vector (0, 0, 18 + 64) + (pPlayer->v_forward * front_check_dst),
					  v_feet + Vector (0, 0, 18 + 64) + (pPlayer->v_forward * front_check_dst) + Vector (0, 0, -250),
					  ignore_monsters, head_hull, pPlayer->pEntity, &tr4);
	  // did the trace hit nothing OR some water ?
	  if ((tr4.flFraction == 1.0) || (POINT_CONTENTS (tr4.vecEndPos) == CONTENTS_WATER))
	  {
		 pPlayer->Bot.BotBody.hit_state |= OBSTACLE_FRONT_FALL; // bot can fall in front
		 pPlayer->Bot.f_reach_time = server.time + 1.5; // reflex : don't reach point for 1.5 second
		 // trace backwards in front of the bot 17 units down to find the edge plane
		 TRACE_LINE (v_feet + Vector (0, 0, -10) + pPlayer->v_forward * (front_check_dst + 20.0),
					 v_feet + Vector (0, 0, -10) + pPlayer->v_forward * (front_check_dst + 20.0) - pPlayer->v_forward * 300,
					 ignore_monsters, pPlayer->pEntity, &tr5);
		 // did the trace hit something ?
		 if (tr5.flFraction < 1.0)
			pPlayer->Bot.BotBody.v_fall_plane_normal = tr5.vecPlaneNormal; // if so, then we found the edge plane
		 else
		 {
			// Houston, we have a problem. The bot is about to fall but we did NOT found the
			// edge plane. Make it jump as a reflex to reach the opposite side (if any)
			pPlayer->Bot.BotLegs.f_forward_time = server.time + 0.5; // run forward
			pPlayer->Bot.BotLegs.f_jump_time = server.time + 0.3; // banzaiii...
		 }
	  }
	  else
		 pPlayer->Bot.BotBody.v_fall_plane_normal = g_vecZero; // else no fall, so reset the edge plane
   }
   // check on the right
   // do a trace 17 units above max stair height right...
   UTIL_TraceHull (v_feet + Vector (0, 0, 18 + 18 + 17),
				   v_feet + Vector (0, 0, 18 + 18 + 17) + (pPlayer->v_right * right_check_dst),
				   ignore_monsters, head_hull, pPlayer->pEntity, &tr1);
   // do a trace one unit above max jump height right...
   UTIL_TraceHull (v_feet + Vector (0, 0, 18 + 64),
				   v_feet + Vector (0, 0, 18 + 64) + (pPlayer->v_right * right_check_dst),
				   ignore_monsters, head_hull, pPlayer->pEntity, &tr2);
   // do a trace one unit lower than max stair height right...
   UTIL_TraceHull (v_feet + Vector (0, 0, 18 + 17),
				   v_feet + Vector (0, 0, 18 + 17) + (pPlayer->v_right * right_check_dst),
				   ignore_monsters, head_hull, pPlayer->pEntity, &tr3);
   // is there something in the way at feet level that is not a slope AND nothing in the way at eye level ?
   if ((tr3.flFraction < 1.0) && (tr3.vecPlaneNormal.z < 0.5) && (tr2.flFraction == 1.0))
	  pPlayer->Bot.BotBody.hit_state |= OBSTACLE_RIGHT_LOWWALL; // bot can jump over this obstacle
   // is there something in the way at eye level AND nothing in the way at knee level ?
   if ((tr2.flFraction < 1.0) && (tr1.flFraction == 1.0) && IsOnFloor (pPlayer->pEntity))
	  pPlayer->Bot.BotBody.hit_state |= OBSTACLE_RIGHT_LOWCEILING; // bot can duck under this obstacle
   // is there something in the way at eye level AND something in the way at knee level ?
   if ((tr2.flFraction < 1.0) && (tr1.flFraction < 1.0))
	  pPlayer->Bot.BotBody.hit_state |= OBSTACLE_RIGHT_WALL; // bot will definitely hit something
   // if the area is clear on the right at head level, trace down to check for a possible fall
   if (tr2.flFraction == 1.0)
   {
	  UTIL_TraceHull (v_feet + Vector (0, 0, 18 + 64) + (pPlayer->v_right * right_check_dst),
					  v_feet + Vector (0, 0, 18 + 64) + (pPlayer->v_right * right_check_dst) + Vector (0, 0, -250),
					  ignore_monsters, head_hull, pPlayer->pEntity, &tr4);
	  // did the trace hit nothing OR some water ?
	  if ((tr4.flFraction == 1.0) || (POINT_CONTENTS (tr4.vecEndPos) == CONTENTS_WATER))
		 pPlayer->Bot.BotBody.hit_state |= OBSTACLE_RIGHT_FALL; // bot can fall on the right
   }
   return; // finished, surrounding obstacles bitmap is filled
}

but definitely what works best is the flat scan. Fire up TraceLines at flat from the left of the bot's field of view, incrementing by 1 degree to the right each time, and send the results to an array. You can then use these distance to build a very convincing navigation.

void BotSee (player_t *pPlayer)
{
   // this is the function that makes the bot see. It fires bursts of TraceLines, incrementing
   // the trace angle each iteration, and store the results of the scan in an array, which
   // median index corresponds to the direction the bot is facing. This is a logic modeling
   // of the human eye. Unfortunately, the processing power required for a 3D scan is too high,
   // so here we just do a flat scan. The idea is not perfect, though. The list of potential
   // entities in sight is built from the engine's own list, then each of them is replaced in
   // its context, i.e. a corresponding is made between it and the right scan angle.
   // And finally, the bot keeps an eye on the chat messages on its screen...
   bot_eyes_t *pBotEyes;
   float angle, distance;
   int fov_index, entity_index, entity_count;
   Vector v_forward, v_groundslope, v_originalangle, v_viewangle;
   TraceResult tr1, tr2, tr3;
   edict_t *pEntity;
   if (DebugLevel.eyes_disabled)
	  return; // cancel if we don't want the AI to see
   pBotEyes = &pPlayer->Bot.BotEyes; // quick access to bot eyes
   if (!pPlayer->is_alive)
	  return; // cancel if bot is dead (saves tracelines)
   if (pBotEyes->blinded_time > server.time)
	  return; // cancel if bot is blinded
   // ask the engine for the entity list
   // erase the previous array
   memset (pBotEyes->pEntitiesInSight, NULL, sizeof (pBotEyes->pEntitiesInSight));
   // cycle through all entities in game
   entity_count = 0;
   for (entity_index = 0; entity_index < gpGlobals->maxEntities; entity_index++)
   {
	  pEntity = INDEXENT (entity_index + 1); // bind that entity number
	  if (FNullEnt (pEntity))
		 continue; // if unregistered, skip it
	  if (BotCanSeeOfEntity (pPlayer, pEntity) == g_vecZero)
		 continue; // if not in sight, discard this item
	  pBotEyes->pEntitiesInSight[entity_count] = pEntity; // bot can see this entity
	  entity_count++; // we know now one entity more
	  if (entity_count == BOT_EYE_SENSITIVITY)
		 break; // if too much entities in sight, stop
   }
   pBotEyes->entity_count = entity_count; // keep track of how many entity this bot sees
   if (pBotEyes->sample_time > server.time)
	  return; // don't go further if not time to sample the field of view yet
   // figure out the ground slope
   v_forward = Vector (pPlayer->v_forward.x, pPlayer->v_forward.y, 0); // build base vector
   TRACE_LINE (pPlayer->v_origin,
			   pPlayer->v_origin + Vector (0, 0, -9999),
			   ignore_monsters, pPlayer->pEntity, &tr1);
   TRACE_LINE (pPlayer->v_origin + (v_forward * 15),
			   pPlayer->v_origin + (v_forward * 15) + Vector (0, 0, -9999),
			   ignore_monsters, pPlayer->pEntity, &tr2);
   v_groundslope = tr2.vecEndPos - tr1.vecEndPos;
   // now figure out a corresponding angle and clamp its X component (pitch) in bounds
   v_originalangle = UTIL_VecToAngles (v_groundslope);
   v_originalangle.x = -v_originalangle.x * 0.75; // fakeclient aim bug fix + temperate pitch
   if (v_originalangle.x < -45)
	  v_originalangle.x = -45;
   else if (v_originalangle.x > 45)
	  v_originalangle.x = 45;
   // store the capture point
   pBotEyes->v_capture_point = pPlayer->v_eyeposition;
   // scan 100 degrees of bot's field of view from LEFT to RIGHT (yaw angles are inverted)...
   fov_index = 0;
   for (angle = 50; angle >= -50; angle -= (angle * angle) / 1500 + 1.5)
   {
	  v_viewangle = v_originalangle; // restore bot's current v_angle
	  v_viewangle.y = WrapAngle (v_viewangle.y + angle); // pan it from left to right
	  MAKE_VECTORS (v_viewangle); // build base vectors in that direction
	  // trace line slightly under eyes level
	  TRACE_LINE (pPlayer->v_eyeposition,
				  pPlayer->v_eyeposition + (gpGlobals->v_forward * 10000),
				  ignore_monsters, pPlayer->pEntity, &tr1);
	  // if debug level is high, draw the field of view of this bot
	  if (pPlayer->is_watched && (DebugLevel.eyes > 1))
		 UTIL_DrawLine (pListenserverPlayer,
						pPlayer->v_eyeposition,
						pPlayer->v_eyeposition + ((gpGlobals->v_forward * 10000) * tr1.flFraction),
						1, 255, 0, 0);
	  distance = tr1.flFraction * 10000; // store distance to obstacle
	  // if this plane is a slope that is smooth enough for bot to climb it or a slope that goes down...
	  if ((AngleOfVectors (tr1.vecPlaneNormal, Vector (0, 0, 1)) < 30) || (AngleOfVectors (tr1.vecPlaneNormal, Vector (0, 0, -1)) < 30))
	  {
		 // trace line parallel to previous starting a bit lower to get a new hit point
		 TRACE_LINE (pPlayer->v_eyeposition + Vector (0, 0, -5),
					 (pPlayer->v_eyeposition + Vector (0, 0, -5)) + (gpGlobals->v_forward * 10000),
					 ignore_monsters, pPlayer->pEntity, &tr2);
		 // compute a normalized vector parallel to slope
		 Vector v_parallel = (tr1.vecEndPos - tr2.vecEndPos).Normalize ();
		 // trace line parallel to slope so that the bot 'sees' up or down the slope
		 TRACE_LINE (pPlayer->v_eyeposition + (((gpGlobals->v_forward * 10000) * tr1.flFraction) * 0.99),
					 (pPlayer->v_eyeposition + (((gpGlobals->v_forward * 10000) * tr1.flFraction) * 0.99)) + (v_parallel * 10000),
					 ignore_monsters, pPlayer->pEntity, &tr3);
		 // if debug level is high, draw the field of view of this bot
		 if (pPlayer->is_watched && (DebugLevel.eyes > 1))
			UTIL_DrawLine (pListenserverPlayer,
						   pPlayer->v_eyeposition + (((gpGlobals->v_forward * 10000) * tr1.flFraction) * 0.99),
						   (pPlayer->v_eyeposition + (((gpGlobals->v_forward * 10000) * tr1.flFraction) * 0.99)) + ((v_parallel * 10000) * tr3.flFraction),
						   1, 255, 0, 0);
		 // add distance from this traceline to the first one so that bot 'sees' up or down the slope
		 distance += tr3.flFraction * 10000;
	  }
 
	  // store the results of the scan in bot's FOV array
	  pBotEyes->BotFOV[fov_index].scan_angles = v_viewangle;
	  pBotEyes->BotFOV[fov_index].distance = distance;
	  pBotEyes->BotFOV[fov_index].vecEndPos = tr1.vecEndPos;
	  pBotEyes->BotFOV[fov_index].Normal = tr1.vecPlaneNormal;
	  pBotEyes->BotFOV[fov_index].pHit = tr1.pHit;
	  fov_index++; // increment FOV array index
   }
   // we just can't match up with the human eye's refresh rate... bots will sample less often
   pBotEyes->sample_time = server.time + 0.20; // next sampling in 200 ms
   return;
}