Autowaypointing...

[He@dShot]

Hi! I want to create an autowaypoint system that will automatically create waypoints on the map depending on the desired radius...How can I do that ?
I have the ideea but it just wont come to me...

[KWo]

I would like to know that, too, for "my" podbot mm.

[The Storm]

Me too haven't actually created any kind of waypointing code. You can look at RACC, he is using and autogenerating navmeshes like the official CS:CZ bot. The navmesh is not actually waypoints, it is movable areas where the bot can go and special places where he can camp or jump and such, the basic is generated at first map load, the other part is continue to be generating by the real players moves. One thing is for sure, it's not easy stuff.

[Whistler]

there is an autowaypointing program in RealBot WIP version. However as POD-Bot is quite paranoid on the consistency of waypoints, it will still need to be improved a lot to be used with POD-Bots.

There is also Quake3 Arena which uses Area Awareness System for navigation, check out the Id Software FTP for the source, and there is a technical doc in the filebase as well.

[Cheeseh]

I put a rather complex auto waypoint generation into my RCBot that uses humans to generate waypoints automatically for use with HPB Bot type waypoints.

What I usually do is keep track of 5 last positions a player has been in (seperated by a little time) and whenever the current point is not visible fromn the last placed waypoint, a new waypoint is placed on the nearest visible point. This is for corner waypointing. There is also the distance taken into consideration, i.e. whether a waypoint already exists at the location wher you want to make a new waypoint, you don't want to make new waypoints in the sample place all the time.

There are also other special cases such as ladders (which I tried to autowaypoint) and also jumping. for example, when jumping a JUMP waypoint is placed if none are around and then a new waypoint is generated when the player hits the ground, and a path is automatically formed from the jump waypoint to the ground waypoint.

I have all the code here if any one can understand it!

	if ( IsAutoWaypointOn() )
	{
		if ( !m_bSetUpAutoWaypoint || !EntityIsAlive(m_pPlayer) )
		{
			int i;
			int start = 0;

			if ( EntityIsAlive(m_pPlayer) )
				start = 1; // grab one location


			m_fLastAutoWaypointCheckTime = gpGlobals->time + gBotGlobals.m_fAutoWaypointCheckTime;

			if ( EntityIsAlive(m_pPlayer) )
				m_vLastAutoWaypointCheckPos[0].SetVector(m_pPlayer->v.origin);

			for ( i = start; i < MAX_STORED_AUTOWAYPOINT; i++ )
			{
				m_vLastAutoWaypointCheckPos[i].UnSetPoint();
			}

			m_vLastAutoWaypointPlacePos = m_pPlayer->v.origin;
			m_bSetUpAutoWaypoint = TRUE;
			m_fCanPlaceJump = 0;
			m_iLastButtons = 0;

			m_iLastJumpWaypointIndex = -1;
			m_iLastLadderWaypointIndex = -1;
			m_iLastMoveType = 0;
			m_fCanPlaceLadder = 0;
			m_iJoinLadderWaypointIndex = -1;
		}
		else
		{
			entvars_t *pev = &m_pPlayer->v;
			Vector vPlayerOrigin = pev->origin;

			// ****************************************************
			// Jump waypoint
			//
			// wait until checkJump is not -1 (meaning that bot is in the air)
			// set checkJump to time+0.5 after landing 
			// 
			// ****************************************************

			if ( (pev->waterlevel < 3) && (m_fCanPlaceJump < gpGlobals->time) )
			{	
				BOOL bStunt = gBotGlobals.IsMod(MOD_TS)&&(m_iLastButtons & IN_ALT1);
				Vector v_floor;

				if ( (m_fCanPlaceJump != -1) && (bStunt||(m_iLastButtons & IN_JUMP)) && !(pev->flags & FL_ONGROUND) )
				{
					int iNearestWpt = WaypointLocations.NearestWaypoint(vPlayerOrigin, 80.0, -1, TRUE, FALSE, FALSE, NULL);

					m_iLastJumpWaypointIndex = -1;
					
					if ( iNearestWpt == -1 )
					{
						if ( bStunt )
						{
							m_iLastJumpWaypointIndex = WaypointAddOrigin(vPlayerOrigin,W_FL_STUNT,m_pPlayer,m_bWaypointOn,m_bWaypointOn);

							if ( (m_iLastJumpWaypointIndex != -1) && UTIL_CanStand(waypoints[m_iLastJumpWaypointIndex].origin,&v_floor) )
							{
								waypoints[m_iLastJumpWaypointIndex].flags &= ~W_FL_CROUCH;
								waypoints[m_iLastJumpWaypointIndex].origin = v_floor+Vector(0,0,36);
							}
						}
						else
							m_iLastJumpWaypointIndex = WaypointAddOrigin(vPlayerOrigin,W_FL_JUMP,m_pPlayer,m_bWaypointOn,m_bWaypointOn);
					}
					else
						m_iLastJumpWaypointIndex = iNearestWpt; // can still update a current waypoint for land position
					
					m_vLastAutoWaypointPlacePos = vPlayerOrigin;

					m_fCanPlaceJump = -1;

					if ( bStunt )
						m_iJumpType = JUMP_TYPE_STUNT;
					else
						m_iJumpType = JUMP_TYPE_JUMP;
				}
				// ****************************************************
				// Join jump waypoint to the landed waypoint
				// ****************************************************
				else if ( (m_fCanPlaceJump == -1) && (pev->flags & FL_ONGROUND) )
				{
					if ( m_iLastJumpWaypointIndex != -1 )
					{
						int iNearestWpt = WaypointLocations.NearestWaypoint(vPlayerOrigin, 80.0, -1, TRUE, FALSE, FALSE, NULL);
						
						if ( iNearestWpt == -1 )
						{
							int iNewWpt = WaypointAddOrigin(vPlayerOrigin,0,m_pPlayer,m_bWaypointOn,m_bWaypointOn);

							if ( iNewWpt != -1 )
							{
								if ( BotNavigate_FindPathFromTo(m_iLastJumpWaypointIndex,iNewWpt,-1) == NULL )
								{
									WaypointAddPath(m_iLastJumpWaypointIndex,iNewWpt);																	
								}

								if ( m_iJumpType == JUMP_TYPE_STUNT )							
									waypoints[m_iLastJumpWaypointIndex].flags |= W_FL_STUNT;																
								else
									waypoints[m_iLastJumpWaypointIndex].flags |= W_FL_JUMP;
								
								if ( UTIL_CanStand(waypoints[iNewWpt].origin,&v_floor) )
								{
									waypoints[iNewWpt].flags &= ~W_FL_CROUCH;
									waypoints[iNewWpt].origin = v_floor+Vector(0,0,36);
								}
							}
						}
						else if ( iNearestWpt != m_iLastJumpWaypointIndex )
						{
							if ( BotNavigate_FindPathFromTo(m_iLastJumpWaypointIndex,iNearestWpt,-1) == NULL )
							{
								WaypointAddPath(m_iLastJumpWaypointIndex,iNearestWpt);
								
								if ( m_iJumpType == JUMP_TYPE_STUNT )
									waypoints[m_iLastJumpWaypointIndex].flags |= W_FL_STUNT;								
								else
									waypoints[m_iLastJumpWaypointIndex].flags |= W_FL_JUMP;								
							}
						}
					}

					m_iLastJumpWaypointIndex = -1;

					// wait a sec after player lands before checking jump again
					m_fCanPlaceJump = gpGlobals->time + 0.5;
				}				
			}

			BOOL bCheckDistance = (pev->movetype != MOVETYPE_FLY) && (m_fCanPlaceLadder == 0); // always check distance unless ladder climbing

			// ****************************************************
			// Ladder waypoint
			// make the frist waypoint (e.g. bottom waypoint)
			// ****************************************************
			if ( (pev->movetype == MOVETYPE_FLY) && !(m_iLastMoveType == MOVETYPE_FLY) )
			{
				// went ON to a ladder

				int iNearestWpt = WaypointLocations.NearestWaypoint(vPlayerOrigin, 80.0, -1, TRUE, FALSE, FALSE, NULL);

				m_iLastLadderWaypointIndex = -1;
					
				if ( iNearestWpt == -1 )
					m_iLastLadderWaypointIndex = WaypointAddOrigin(vPlayerOrigin,W_FL_LADDER,m_pPlayer,m_bWaypointOn,m_bWaypointOn);
				else
				{
					m_iLastLadderWaypointIndex = iNearestWpt; // can still update a current waypoint for land position

					waypoints[m_iLastLadderWaypointIndex].flags |= W_FL_LADDER; // update flags
				}
					
				m_vLastAutoWaypointPlacePos = vPlayerOrigin;

				bCheckDistance = FALSE;

				m_fCanPlaceLadder = 0;

				// need to unset every check point when going on ladder first time
				for ( int i = 0; i < MAX_STORED_AUTOWAYPOINT; i ++ )
				{
						m_vLastAutoWaypointCheckPos[i].UnSetPoint();					
				}
			}
			else if ( !(pev->movetype == MOVETYPE_FLY) && (m_iLastMoveType == MOVETYPE_FLY) )
			{
				// went OFF a ladder
				m_fCanPlaceLadder = gpGlobals->time + 0.2;
			}
			
			// ****************************************************
			// If we have walked off a ladder for a small amount of time
			// Make the top/bottom ladder waypoint
			// ****************************************************
			if ( m_fCanPlaceLadder && (m_fCanPlaceLadder < gpGlobals->time ) )
			{
				if ( m_iLastLadderWaypointIndex != -1 )
					// place a ladder waypoint before jumping off
				{
					int iNearestWpt = WaypointLocations.NearestWaypoint(vPlayerOrigin, 80.0, -1, TRUE, FALSE, FALSE, NULL);
					
					if ( iNearestWpt == -1 )
					{
						int iNewWpt = WaypointAddOrigin(vPlayerOrigin,W_FL_LADDER,m_pPlayer,m_bWaypointOn,m_bWaypointOn);
						
						if ( iNewWpt != -1 )
						{
							m_iJoinLadderWaypointIndex = iNewWpt;

							if ( BotNavigate_FindPathFromTo(m_iLastLadderWaypointIndex,iNewWpt,-1) == NULL )
								WaypointAddPath(m_iLastLadderWaypointIndex,iNewWpt);
						}
					}
					else if ( iNearestWpt != m_iLastLadderWaypointIndex )
					{
						m_iJoinLadderWaypointIndex = iNearestWpt;

						if ( BotNavigate_FindPathFromTo(m_iLastLadderWaypointIndex,iNearestWpt,-1) == NULL )
							WaypointAddPath(m_iLastLadderWaypointIndex,iNearestWpt);
					}				
				}
				
				m_iLastLadderWaypointIndex = -1;
				
				bCheckDistance = FALSE;

				m_fCanPlaceLadder = 0;
			}
			
			// ****************************************************
			// Join top ladder waypoint to a ground waypoint
			// ****************************************************
			if ( (m_iJoinLadderWaypointIndex != -1) && (pev->flags & FL_ONGROUND) && (pev->movetype == MOVETYPE_WALK) )
			{
				int iNearestWpt = WaypointLocations.NearestWaypoint(vPlayerOrigin, 40.0, m_iJoinLadderWaypointIndex, TRUE, FALSE, FALSE, NULL);
				
				if ( iNearestWpt == -1 )
				{
					int iNewWpt = WaypointAddOrigin(vPlayerOrigin,0,m_pPlayer,m_bWaypointOn,m_bWaypointOn);
					
					if ( iNewWpt != -1 )
					{
						if ( BotNavigate_FindPathFromTo(m_iJoinLadderWaypointIndex,iNewWpt,-1) == NULL )
							WaypointAddPath(m_iJoinLadderWaypointIndex,iNewWpt);
					}
				}
				else if ( iNearestWpt != m_iJoinLadderWaypointIndex )
				{
					if ( BotNavigate_FindPathFromTo(m_iJoinLadderWaypointIndex,iNearestWpt,-1) == NULL )
						WaypointAddPath(m_iJoinLadderWaypointIndex,iNearestWpt);
				}

				m_iJoinLadderWaypointIndex = -1;
			}

			m_iLastButtons = pev->button;
			m_iLastMoveType = pev->movetype;

			if ( m_fLastAutoWaypointCheckTime < gpGlobals->time )
			{
				// ****************************************
				// Corner - Check
				// ****************************************
				//
				// place a "Check - point" at player origin
				//

				CAutoWaypointCheck *vCurVector;				
				Vector vCheckOrigin;

				Vector vPlacePosition;
				int iFlags = 0;
				BOOL bPlace = FALSE;
				
				int i;
				int n;

				TraceResult tr;

				int numset = 0;
				int last = 0;

				for ( n = 0; n < MAX_STORED_AUTOWAYPOINT; n ++ )
				{
					if ( m_vLastAutoWaypointCheckPos[n].IsVectorSet() )
					{
						numset++;
					}
				}

				if ( numset == MAX_STORED_AUTOWAYPOINT )
				{
					// move check points down
					for ( n = 0; n < (MAX_STORED_AUTOWAYPOINT-1); n ++ )
					{
						m_vLastAutoWaypointCheckPos[n] = m_vLastAutoWaypointCheckPos[n+1];						
					}
					
					last = MAX_STORED_AUTOWAYPOINT-1;
				}
				else
				{					
					last = numset;
				}

				iFlags = 0;

				// sort out flags for this waypoint depending on player
				if ((pev->flags & FL_DUCKING) == FL_DUCKING)
				{
					iFlags |= W_FL_CROUCH;  // crouching waypoint
				}
				
				if (pev->movetype == MOVETYPE_FLY)
					iFlags |= W_FL_LADDER;  // waypoint on a ladder

				m_vLastAutoWaypointCheckPos[last].SetPoint(vPlayerOrigin,iFlags);
				
				if ( (m_iLastJumpWaypointIndex==-1) && bCheckDistance && ((vPlayerOrigin - m_vLastAutoWaypointPlacePos).Length() > 200) )
				{
					int iNearestWpt = WaypointLocations.NearestWaypoint(vPlayerOrigin, 150.0, -1, TRUE, FALSE, FALSE, NULL);
					
					if ( iNearestWpt == -1 )
						WaypointAddOrigin(vPlayerOrigin,0,m_pPlayer,m_bWaypointOn,m_bWaypointOn);
					
					// set regardless
					m_vLastAutoWaypointPlacePos = vPlayerOrigin;
				}

				// search for occluded check points from player
				for ( i = 0; i < MAX_STORED_AUTOWAYPOINT; i++ )
				{
					vCurVector = &m_vLastAutoWaypointCheckPos[i];

					if ( !vCurVector->IsVectorSet() )
						continue;

					vCheckOrigin = vCurVector->GetVector();

					UTIL_TraceLine(vPlayerOrigin,vCheckOrigin,ignore_monsters,ignore_glass,m_pPlayer,&tr);

					if ( m_bDebugAutoWaypoint )
					{
						WaypointDrawBeam(m_pPlayer,vCheckOrigin+Vector(0,0,16),vCheckOrigin-Vector(0,0,16),20,1,255,1,1,150,10);
						WaypointDrawBeam(m_pPlayer,vPlayerOrigin,vCheckOrigin,20,1,1,255,1,150,10);
					}
					
					if ( tr.flFraction < 1.0 )
					{
						if ( tr.pHit )
						{
							// on a lift/train moving "fast"
							if ( tr.pHit->v.velocity.Length() > 20.0 )
								continue;
						}
						// find next which is visible
						for ( n = i+1; n < MAX_STORED_AUTOWAYPOINT; n++ )
						{
							vCurVector = &m_vLastAutoWaypointCheckPos[n];
							
							if ( !vCurVector->IsVectorSet() )
								continue;
							
							vCheckOrigin = vCurVector->GetVector();
							
							UTIL_TraceLine(vPlayerOrigin,vCheckOrigin,ignore_monsters,ignore_glass,m_pPlayer,&tr);

							if ( m_bDebugAutoWaypoint )
								WaypointDrawBeam(m_pPlayer,vPlayerOrigin,vCheckOrigin,20,1,1,1,255,150,10);
							
							if ( tr.flFraction >= 1.0 )
							{
								int iNearestWpt = WaypointLocations.NearestWaypoint(vCheckOrigin, 100.0, -1, TRUE, FALSE, FALSE, NULL);
								
								if ( iNearestWpt == -1 )
								{
									bPlace = TRUE;		
									vPlacePosition = vCheckOrigin;
									iFlags = vCurVector->getFlags();
									
									break;
								}
								else
									continue;
							}
						}
						
					}
				}

				if ( bPlace )
				{
					int inewwpt = WaypointAddOrigin(vPlacePosition,iFlags,m_pPlayer,m_bWaypointOn,m_bWaypointOn,FALSE);
					Vector v_floor;

					m_vLastAutoWaypointPlacePos = vPlacePosition;

					if ( (m_iLastJumpWaypointIndex != -1) && UTIL_CanStand(waypoints[inewwpt].origin,&v_floor) )
					{
						waypoints[inewwpt].flags &= ~W_FL_CROUCH;
						//waypoints[inewwpt].origin = v_floor+Vector(0,0,36);
					}
					//clear from i

					int pos = n;
					int n = 0;

					for ( n = 0; pos < MAX_STORED_AUTOWAYPOINT; n ++ )
					{
						m_vLastAutoWaypointCheckPos[n] = m_vLastAutoWaypointCheckPos[pos];

						pos++;
					}

					for ( n = n; n < MAX_STORED_AUTOWAYPOINT; n ++ )
					{
						m_vLastAutoWaypointCheckPos[n].UnSetPoint();					
					}
				}

				m_fLastAutoWaypointCheckTime = gpGlobals->time + gBotGlobals.m_fAutoWaypointCheckTime;
			}
		}

bear in mind this autowaypointing is for natural-selection in particular

[Count Floyd]

There are lots of problems you can easily overlook when doing autowaypointing (like guys using hostages to reach otherwise unreachable spots etc.) and you don't have a map representation right from the start (which has the bots appear looking dumb at the beginning) so I wouldn't advise doing that.
If you're using other terrain representations one of these might be helpfull:
http://serenity.uncc.edu/youngblood/...DE2008Hale.pdf
http://www.aiide.org/aiide2005/talks/isla.ppt

or just simulate a bounding box moving around like turtle rock studios did for their in-built bots in cs and cs:source.

[AlexBreems]

Somebody can knows where to take the information on algorithm autowaypointing at zBot?

[Immortal_BLG]

I only know (read in wiki), that zBot too uses created by Id Software: Area Awareness System, but improved by turtle rock studios

Sorry for my bad english, I use translator...

[AlexBreems]

Thank you for information

[Whistler]

nope, CZero bot is navmesh-based and not using 3D bounding boxes like Id Software. I think there is a presentation somewhere which has some (but not much) information about the CZero bot.