.:: Bots United ::.

.:: Bots United ::. (http://forums.bots-united.com/index.php)
-   Releases, Installers, Docs & Coding (http://forums.bots-united.com/forumdisplay.php?f=48)
-   -   a much faster version of waypoint checking code. (http://forums.bots-united.com/showthread.php?t=3135)

Whistler 05-12-2004 09:34
a much faster version of waypoint checking code.
 
PHP Code:
bool WaypointNodesValid()
{
   int iTPoints = 0;
   int iCTPoints = 0;
   int iGoalPoints = 0;
   int iRescuePoints = 0;
   int iConnections;
   int i, j;

   for (i = 0; i < g_iNumWaypoints; i++)
   {
      iConnections = 0;

      for (int n = 0; n < MAX_PATH_INDEX; n++)
      {
         if (paths[i]->index[n] != -1)
         {
            if (paths[i]->index[n] > g_iNumWaypoints)
            {
               SERVER_PRINT(UTIL_VarArgs("Node %d connected with invalid Waypoint Nr. %d!\n", i, paths[i]->index[n]));
               return FALSE;
            }
            iConnections++;
            break;
         }
      }

      if (iConnections == 0)
      {
         if (!WaypointIsConnected(i))
         {
            SERVER_PRINT(UTIL_VarArgs("Node %d isn't connected with any other Waypoint!\n", i));
            return FALSE;
         }
      }

      if (paths[i]->iPathNumber != i)
      {
         SERVER_PRINT(UTIL_VarArgs("Node %d pathnumber differs from index!\n", i));
         return FALSE;
      }

      if (paths[i]->flags & W_FL_CAMP)
      {
         if (paths[i]->fcampendx == 0.0 && paths[i]->fcampendy == 0.0)
         {
            SERVER_PRINT(UTIL_VarArgs("Node %d Camp-Endposition not set!\n", i));
            return FALSE;
         }
      }
      else if (paths[i]->flags & W_FL_TERRORIST)
         iTPoints++;
      else if (paths[i]->flags & W_FL_COUNTER)
         iCTPoints++;
      else if (paths[i]->flags & W_FL_GOAL)
         iGoalPoints++;
      else if (paths[i]->flags & W_FL_RESCUE)
         iRescuePoints++;

      int x = 0;

      while (x < MAX_PATH_INDEX)
      {
         if (paths[i]->index[x] != -1)
         {
            if (paths[i]->index[x] >= g_iNumWaypoints || paths[i]->index[x] < -1)
            {
               SERVER_PRINT(UTIL_VarArgs("Node %d - Pathindex %d out of Range!\n", i, x));
               g_engfuncs.pfnSetOrigin(pHostEdict, paths[i]->origin);
               g_bWaypointOn = TRUE;
               bEditNoclip = TRUE;
               return FALSE;
            }
            else if (paths[i]->index[x] == i)
            {
               SERVER_PRINT(UTIL_VarArgs("Node %d - Pathindex %d points to itself!\n", i, x));
               g_engfuncs.pfnSetOrigin(pHostEdict, paths[i]->origin);
               g_bWaypointOn = TRUE;
               bEditNoclip = TRUE;
               return FALSE;
            }
         }
         x++;
      }
   }
   if (g_iMapType & MAP_CS)
   {
      if (iRescuePoints == 0)
      {
         SERVER_PRINT("You didn't set a Rescue Point!\n");
         return FALSE;
      }
   }
   if (iTPoints == 0)
   {
      SERVER_PRINT("You didn't set any Terrorist Important Point!\n");
      return FALSE;
   }
   else if (iCTPoints == 0)
   {
      SERVER_PRINT("You didn't set any CT Important Point!\n");
      return FALSE;
   }
   else if (iGoalPoints == 0)
   {
      SERVER_PRINT("You didn't set any Goal Point!\n");
      return FALSE;
   }

   bool rgbVisited[MAX_WAYPOINTS];
   PATHNODE *stack = NULL;

   // first check incoming connectivity
   // initialize the "visited" table
   for (i = 0; i < g_iNumWaypoints; i++)
      rgbVisited[i] = FALSE;

   // check from Waypoint nr. 0
   stack = (PATHNODE *)malloc(sizeof(PATHNODE));
   stack->NextNode = NULL;
   stack->iIndex = 0;

   while (stack)
   {
      // pop a node from the stack
      PATHNODE *current = stack;
      stack = stack->NextNode;

      rgbVisited[current->iIndex] = TRUE;

      for (j = 0; j < MAX_PATH_INDEX; j++)
      {
         int iIndex = paths[current->iIndex]->index[j];
         if (rgbVisited[iIndex])
            continue; // skip this waypoint as it's already visited
         if (iIndex >= 0 && iIndex < g_iNumWaypoints)
         {
            PATHNODE *newnode = (PATHNODE *)malloc(sizeof(PATHNODE));
            newnode->NextNode = stack;
            newnode->iIndex = iIndex;
            stack = newnode;
         }
      }

      free(current);
   }

   for (i = 0; i < g_iNumWaypoints; i++)
   {
      if (!rgbVisited[i])
      {
         SERVER_PRINT(UTIL_VarArgs("Path broken from Waypoint Nr. 0 to Waypoint Nr. %d!\n", i));
         g_engfuncs.pfnSetOrigin(pHostEdict, paths[i]->origin);
         g_bWaypointOn = TRUE;
         bEditNoclip = TRUE;
         return FALSE;
      }
   }

   // then check outgoing connectivity
   std::vector<int> in_paths[MAX_WAYPOINTS]; // store incoming paths for speedup

   for (i = 0; i < g_iNumWaypoints; i++)
      for (j = 0; j < MAX_PATH_INDEX; j++)
         if (paths[i]->index[j] >= 0 && paths[i]->index[j] < g_iNumWaypoints)
            in_paths[paths[i]->index[j]].push_back(i);

   // initialize the "visited" table
   for (i = 0; i < g_iNumWaypoints; i++)
      rgbVisited[i] = FALSE;

   // check from Waypoint nr. 0
   stack = (PATHNODE *)malloc(sizeof(PATHNODE));
   stack->NextNode = NULL;
   stack->iIndex = 0;

   while (stack)
   {
      // pop a node from the stack
      PATHNODE *current = stack;
      stack = stack->NextNode;

      rgbVisited[current->iIndex] = TRUE;

      for (j = 0; j < (int)in_paths[current->iIndex].size(); j++)
      {
         if (rgbVisited[in_paths[current->iIndex][j]])
            continue; // skip this waypoint as it's already visited
         PATHNODE *newnode = (PATHNODE *)malloc(sizeof(PATHNODE));
         newnode->NextNode = stack;
         newnode->iIndex = in_paths[current->iIndex][j];
         stack = newnode;
      }
      free(current);
   }

   for (i = 0; i < g_iNumWaypoints; i++)
   {
      if (!rgbVisited[i])
      {
         SERVER_PRINT(UTIL_VarArgs("Path broken from Waypoint Nr. %d to Waypoint Nr. 0!\n", i));
         g_engfuncs.pfnSetOrigin(pHostEdict, paths[i]->origin);
         g_bWaypointOn = TRUE;
         bEditNoclip = TRUE;
         return FALSE;
      }
   }

   return TRUE;
} 

@$3.1415rin 05-12-2004 10:04
Re: a much faster version of waypoint checking code.
 
sometimes it may be useful to describe the functionality of some piece of posted code in a few sentences ...

this is a version of this podbot function checking paths before saving, to avoid whatever, right ? that stuff that can be found in every forum to be ignored by nocheck ? :P

here a fast way to check if there is a near waypoint, can also be found in http://www.lampel.net/johannes/joebo...XPDoc-beta.pdf

PHP Code:
int CWaypointGraph::getNearest(const Vector &VOrigin,bool bVisible, bool bReachable, float fMin, float fMax,long lFlags){
//
// note that this function only searches for the nearest waypoint within a distance of min. 1,5*8192/64 = 192
// and maximum of 255 units.
//
float fDistance, fNearest = 1E30;
int iMinIndex = -1;
 
vector<int>::iterator iter,end;
int iHash = getHashcode(VOrigin); // get hashcode for that location
 
int iOX,iOY,iXBase,iYBase;
 
fNearest = fMax = fMax * fMax;
fMin = fMin * fMin;
 
for(iOY = -1; iOY <= 1; iOY ++){ // and check the buckets around there
iYBase = iHash + iOY * 64;
if(iYBase < 0 || iYBase > 4095 )
continue;
for(iOX = -1; iOX <= 1; iOX ++){
iXBase = iYBase + iOX;
 
if(iXBase < 0 || iXBase > 4095 )
    continue;
 
end = m_pLHash[iXBase].end();
for(iter=m_pLHash[iXBase].begin();iter != end; iter ++){
    fDistance = (VOrigin - m_pWaypoints[*iter].m_VOrigin).squareLength();
 
    if(fDistance < fNearest && fDistance >= fMin){
     if(bVisible){ // if we have to check if it's visible
#ifdef __JOEBOTXPDLL
     if(!FVisibleEx(VOrigin,m_pWaypoints[*iter].m_VOrigin)){
     continue;
     }
#endif
     }
     if(bReachable){ // so do we gotta check if it's reachable ?!
     //todo
     if(!g_pMap.getReachable(VOrigin,m_pWaypoints[*iter].m_VOrigin))
     continue;
     }
     if(m_pWaypoints[*iter].m_lFlags & lFlags != lFlags)
     continue;
 
     fNearest = fDistance;
     iMinIndex = *iter;
    }
}
}
}
 
if(iMinIndex == -1){
return getNearesto(VOrigin,bVisible,bReachable,sqrt(fMin),sqrt(fMax),lFlags);
}
 
return iMinIndex;
}
 
void CWaypointGraph::addToHashTable(int iWP){
int iHash = getHashcode(m_pWaypoints[iWP].m_VOrigin);
m_pLHash[iHash].push_back(iWP);
}
bool CWaypointGraph::removeFromHashtable(int iRemove){
// let's first assume that the origin stored at this waypoint is still right
int iHash = getHashcode(m_pWaypoints[iRemove].m_VOrigin);
vector<int>::iterator iter;
for(iter = m_pLHash[iHash].begin(); iter != m_pLHash[iHash].end(); iter ++){// look into the bucket and delete it
if(*iter == iRemove){
m_pLHash[iHash].erase(iter);
return true;
}
}
// not found : so maybe the origin isnt still right ?!
// let's loop thru all and see if we can get it
for(iHash = 0; iHash < 4096; iHash ++){
for(iter = m_pLHash[iHash].begin(); iter != m_pLHash[iHash].end(); iter ++){
if(*iter == iRemove){
    m_pLHash[iHash].erase(iter);
    return true;
}
}
}
return false;
} 

Whistler 08-12-2004 13:13
Re: a much faster version of waypoint checking code.
 
here's a bit of explanations on the code above...
the original POD-Bot uses Floyd-Warshall algorithm to find all paths between all nodes... but this is just not necessary:
1. we needn't find the shortest path, finding a random path is enough
2. have you noticed that POD-Bot only reports "path broken from 0 to n" or "from n to 0" ? so actually we only need to verify connections between waypoint nr. 0 and the other waypoints
I just do a traverse in the waypoint graph with Depth-first Search.
because I'm lazy, I used the std::vector. you can try using a linked list instead if you don't want to use standard library.

@$3.1415rin 08-12-2004 15:56
Re: a much faster version of waypoint checking code.
 
just a note : linked list and std:vector is a bit difference, since vector allows you very fast random access, while a linked list ( without additional tables ) does not

sPlOrYgOn 09-12-2004 03:45
Re: a much faster version of waypoint checking code.
 
thanks Whistler :)
It definately feels faster on my slow comp :)

Huntkillaz 09-12-2004 10:12
Re: a much faster version of waypoint checking code.
 
ooo can i test it plzzzzzzzzzzzzzzzzzzz...(just emai it to huntakillaz at gmail)

my super slow comp should be good for this :D

Whistler 11-12-2004 06:30
Re: a much faster version of waypoint checking code.
 
Quote:
Originally Posted by Huntkillaz
ooo can i test it plzzzzzzzzzzzzzzzzzzz...(just emai it to huntakillaz at gmail)

my super slow comp should be good for this :D
download the YaPB from http://yapb.bots-united.com and try "yapb wp save". ;)


All times are GMT +2. The time now is 07:30.

Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.