# Pathfinding assistance requested

• 06-02-2004
Thantos
Pathfinding assistance requested
I'm encountering difficulty with my pathfinding routine. I have done plenty of searching and understand the method but I'm having difficulty putting it into code. One problem is that I'm forcing myself to do it in C++ which I'm still pretty green on.

The problem is that while the routine works it horribly slow when trying to find sectors at more then 12ish steps.

Current map I'm using follows this pattern, except it goes to 5000 instead of 40 :)

Each sector attaches to up to 4 other sectors, up, down, left, right.

So sector 0 attaches to 1, 2, 3, and 4 but not to 6, 7, 9, and 11

The algorithm I'm using is kinda based off of A* except that all movement costs are the same so I'm not factoring any movement costs.

What I'm doing is maintaining two lists, one of the working in-progess and one of the completed paths.
Also I'm maintaining the size of the shortest path. I'm also maintaining the shortest distances to each sector as I find them.

The general method is that it makes a copy of the current paths, adds on its connections and puts it back on the working pile. I'm always working from the first list so that I'm <hopefully> working with the shortest path and will not waste a lot of time.

Below is the code for the control function
Code:

```void findpath(Zone *zones, int from, int to, int depth, list<int> &autonav, list<int> forbidden, int numzones)   // zones = the array of zone classes, from is the sector we want to come from, to is the sector we want to move to   // autonav is the list that will be used by the caller to make the move   // forbidden is the list of sectors we want to avoid (currently none)   // numzones is the number of sectors in the map {   list <list <int> > paths, completed;   int *dist = new int[numzones];     for (int i=0; i<numzones; i++)       dist[i] = -1;   int smallest = -1;   int count=0;   int zone = from;   int size = -2;   cout<<"  Navigator: Sector "<<to<<" is not adjucent.  Plotting course sir. "<<endl;   do   {     if( !paths.empty() )     {       size = (paths.front()).size();       zone = (paths.front()).back();     }   if ( smallest != -1 && size > smallest)       paths.pop_front(); // The current list is deeper then out shortest route     else       beginplot(zones, paths, completed, zone, to, size, depth, smallest, forbidden, dist);   }while( !paths.empty());   if ( completed.size() )   {     list <list<int> >::iterator loc;     for ( loc = completed.begin(); loc!= completed.end(); loc++)       if ( loc->size() == smallest )       {         autonav = *loc;         break;       }   } }```
The workhorse function
Code:

```void beginplot(     Zone *zones, // Same as the other zones     list< list<int> > &working, // The paths we are currently working on     list< list<int > > &completed, // The paths that are already completed     int currzone, // The current zone     int tar,  // The zone we want to get to     int depth, // The current depth     int maxdepth, // How deep we can go     int &smallest, // The size of the smallest path     const list<int> &forbidden, // The list of the zones we aren't allowed to go into     int *dists     ){   if ( currzone == tar) // We are at the target so move the list from the working pile to the completed pile   {     int size = (working.front()).size();     completed.push_back(working.front());     working.pop_front();     if ( smallest == -1 || size < smallest) // If we are the smallest update the size       smallest = size;     return;   }   if (dists[currzone] == -1 || depth < dists[currzone])  // if we made it to this sector in the shortest length update     dists[currzone] = depth;   if ( depth >= maxdepth || // If we have meet or exceeded the maxdepth       depth>dists[currzone] || // If some other path made it to this sector quicker       ( smallest != -1 && (working.front()).size() >= smallest) || // If our path has gone on longer then the shortest path       forbiddencheck(forbidden, currzone) ) // Or if we are in a forbidden sector   {     working.pop_front(); // Remove the list from the work pile     return;   }   if ( working.empty() ) // Basically here for when we are at the sector we want to move from   {     for (int i=0; i<Conns; i++)     {       int tzone = zones[currzone].getconn(i);       if ( tzone != -1)       {         list<int> temp;         temp.push_back(tzone);         working.push_back(temp);       }     }   }   else   {     list<int> currpath = working.front(); // Get the list     working.pop_front(); // Remove the list from the work pile     for (int i=0; i <Conns; i++) // Steps through all the connections.  //Conns is a global const int that gives the number of connections per sector     {       int tzone = zones[currzone].getconn(i);  // Which sector does this current connection point to       if ( tzone != -1 ) // -1 is the value for no connection       {         list<int> temp = currpath; // make a copy of the list         temp.push_back(tzone); // add on the sector the current connection point to         if ( dupcheck(temp) == false ) // make sure we didn't just put a duplicate in its place           working.push_back(temp); // add the list to the end of the working pile       }     }   } }```
And the zone class defination
Code:

```const int Conns = 4; class Zone {   int connections[Conns];   int numconn;   public:   Zone()   {     for (int i=0; i < Conns; i++)       connections[i] = -1;     numconn=0;   }   int getconn(int p)   {     return connections[p];   }   int loadconn(int p, int z)   {     connections[p] = z;     numconn++;   }   int getnumconn(){ return numconn; } };```
Sorry for the long posts, but I would be very greatful if anyone could suggest any improvements.
• 06-02-2004
Thantos
Fixed it. I ended up keeping track of the number of lists going and step a sigaction to display it when I hit ctrl c. On a longer ones I was having over 20k lists going.

I moved some checking around (namely the distance on each zone and looking for the target) and changed it so that once I found a path it stopped looking.