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

The workhorse functionCode:`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;

}

}

}

And the zone class definationCode:`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

}

}

}

}

Sorry for the long posts, but I would be very greatful if anyone could suggest any improvements.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; }

};