Pathfinding assistance requested

This is a discussion on Pathfinding assistance requested within the Game Programming forums, part of the General Programming Boards category; I'm encountering difficulty with my pathfinding routine. I have done plenty of searching and understand the method but I'm having ...

  1. #1
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681

    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.

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Checking array for string
    By Ayreon in forum C Programming
    Replies: 87
    Last Post: 03-09-2009, 04:25 PM
  2. Pathfinding question
    By h3ro in forum General AI Programming
    Replies: 13
    Last Post: 05-15-2008, 11:29 AM
  3. AI (Pathfinding)
    By jdinger in forum Game Programming
    Replies: 7
    Last Post: 04-16-2003, 11:20 AM
  4. AI (pathfinding) tutorial
    By dirkduck in forum Game Programming
    Replies: 3
    Last Post: 02-09-2002, 12:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21