Thread: 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
Link to map

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.

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.