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.