experiments.cpp

Go to the documentation of this file.

//-----------------------------------------------------------------------------
/** @file experiments.cpp
    Example program loading tiling maps from files.

    $Id: experiments_8cpp-source.html,v 1.1.1.1 2003/08/07 19:41:38 emarkus Exp $
    $Source: /usr/cvsroot/www_pathfind/libpathfind/0.1.0/doc/experiments_8cpp-source.html,v $
*/
//-----------------------------------------------------------------------------

#include <memory>
#include "pathfind.h"
#include <iostream>
#include <fstream>
#include <sstream>

using namespace std;
using namespace PathFind;

//-----------------------------------------------------------------------------

static const int s_numberRuns           = 400;
static const long long int s_nodesLimit = 100000000L;

//-----------------------------------------------------------------------------

typedef enum {A_STAR, FRINGE, IDA_STAR} SearchAlgorithm;

//-----------------------------------------------------------------------------

void printHeader(SearchAlgorithm searchAlgorithm, Tiling::Type type,
                 const char* name)
{
    cout << "==============================================================\n";
    switch (searchAlgorithm)
    {
    case A_STAR:
        cout << "A_STAR";
        break;
    case FRINGE:
        cout << "FRINGE";
        break;
    case IDA_STAR:
        cout << "IDA_STAR";
        break;
    }
    cout << "  ";
    switch (type)
    {
    case Tiling::TILE:
        cout << "TILE";
        break;
    case Tiling::OCTILE:
        cout << "OCTILE";
        break;
    case Tiling::OCTILE_UNICOST:
        cout << "OCTILE_UNICOST";
        break;
    case Tiling::HEX:
        cout << "HEX";
        break;
    }
    cout << "  ";
    cout << name;
    cout << '\n';
    cout << "==============================================================\n";
}

StatisticsCollection 
runExperiment(SearchAlgorithm searchAlgorithm, Search* search,
              const Tiling& tiling, vector< pair<int,int> >& paths,
              const int fileIndex, int numberRuns, const char *fileName)
{
    //printHeader(searchAlgorithm, tiling.getType(), fileName);
    //cout << tiling.getWidth() << "x" << tiling.getHeight() << '\n';

    SearchUtils searchUtils;
    StatisticsCollection statistics = search->createStatistics();

    if ( numberRuns > s_numberRuns )
        numberRuns = s_numberRuns;

    clock_t startTime = clock();
    for (int runIndex = 0; runIndex < numberRuns; ++runIndex)
    {
        // Choose random start and target
        int start, target;
        start = paths[runIndex].first;
        target = paths[runIndex].second;

        //searchUtils.findRandomStartTarget(tiling, start, target);
        //cout << "Run " << runIndex << ":\n";
        //tiling.printFormatted(cout, start, target);
        //cout << '\n';
        
        // Do the search
        search->findPath(tiling, start, target);
        //cout << '\n';
        //const vector<int>& path = search->getPath();
        //tiling.printFormatted(cout, path);
        //cout << '\n';
        //tiling.printPathAndLabels(cout, path, search->getVisitedNodes());
        //cout << '\n';
        
        // Accumulate statistics
        const StatisticsCollection& searchStatistics = search->getStatistics();

        cout << "  " << fileIndex;
        cout << "  " << runIndex;
        cout << "  " << start; 
        cout << "  " << target;
        cout << "  " << tiling.getHeuristic(start,target);
        cout << "  " << searchStatistics.get("path_cost").getMean();
        cout << "  " << search->getPath().size();
        cout << "  " << searchStatistics.get("nodes_expanded").getMean();
        cout << "  " << searchStatistics.get("cpu_time").getMean();
        cout << "  " << searchStatistics.get("iterations").getMean();
         
        cout << '\n';

        statistics.add(searchStatistics);
    }

    statistics.create("cpu_time_avg");
    double timeDiff =
        static_cast<double>(clock() - startTime) / CLOCKS_PER_SEC;
    statistics.get("cpu_time_avg").add( timeDiff /  numberRuns );
    //    cout << "cpu_time_avg = " << timeDiff /  numberRuns << endl;
    statistics.print(cout);

    return statistics;
}


/** Generates a file with random passable start/target locations
    for a given map file.
*/
void generatePaths( const char *filename )
{
    ifstream file(filename);
    LineReader reader(file);
    Tiling tiling(reader);
            
    string outfile;
    outfile = (outfile + filename) + ".paths";
    ofstream out(outfile.c_str());
    SearchUtils searchUtils;
    for (int runIndex = 0; runIndex < s_numberRuns; ++runIndex)
    {
        // Choose random start and target
        int start, target;
        searchUtils.findRandomStartTarget(tiling, start, target);
        out << runIndex << " " << start << " " << target << "\n";
    }
    
    out.close();
} 


int main(int argc, char *argv[])
{
    try
    {

        if ( argc == 1 )
        {
            cerr <<
                "Usage: experiments [RUN_ASTAR|RUN_FRINGE|RUN_IDASTAR"
                "|RUN_IDASTAR_f|RUN_IDASTAR_F|GEN_PATHS]"; 
            cerr << " <mapfiles>" << endl;
            exit(EXIT_FAILURE);
        }

        SearchAlgorithm searchAlgorithm = A_STAR;
        string command = argv[1];
        IDAStar::Caching caching = IDAStar::NO_CACHING;

        if ( command == "RUN_ASTAR" )
        {
            searchAlgorithm = A_STAR;
        }
        else if (command == "RUN_FRINGE")
        {
            searchAlgorithm = FRINGE;
        }
        else if ( command == "RUN_IDASTAR" )
        {
            searchAlgorithm = IDA_STAR;
            caching = IDAStar::NO_CACHING;
        }
        else if ( command == "RUN_IDASTAR_f" )
        {
            searchAlgorithm = IDA_STAR;
            caching = IDAStar::f_CACHING;
        }
        else if ( command == "RUN_IDASTAR_F" )
        {
            searchAlgorithm = IDA_STAR;
            caching = IDAStar::F_CACHING;
        }
        else if ( command == "GEN_PATHS" )
        {
            for ( int i=2 ; i<argc ; i++ ) 
            {
                generatePaths( argv[i] );
            }
            exit(EXIT_SUCCESS);
        }
        else 
        {
            cerr << "Unknown command '" << command << "'" << endl; 
            exit(EXIT_FAILURE);
        }

        // Run either A_STAR or IDA_STAR experiments.
        StatisticsCollection *statisticsSum = 0;
        auto_ptr<Search> search;
        switch (searchAlgorithm)
        {
        case A_STAR:
            search.reset(new AStar<>());
            break;
        case FRINGE:
            search.reset(new FringeSearch<>());
            break;
        case IDA_STAR:
            search.reset(new IDAStar(caching));
            break;
        }
        search->setNodesLimit(s_nodesLimit);
        for ( int i=2 ; i<argc ; i++ ) {
            // Read in map when constucting tiling object.
            ifstream file(argv[i]);
            LineReader reader(file);
            Tiling tiling(reader);

            // Read in start/target states to do pathfinding on.
            string pathfileName;
            pathfileName = (pathfileName + argv[i]) + ".paths";
            ifstream pathfile(pathfileName.c_str());
            if ( !pathfile ) {
                cerr << "Could not open pathfile " << pathfileName << endl;
                exit(1);
            }   
            vector< pair<int,int> > paths(100);
            int vidx, idx, start, target;
            vidx = 0;
            while ( pathfile >> idx >> start >> target ) 
            {
                pair<int,int> path;
                path.first = start;
                path.second = target;

                paths[vidx++] = path;
                if ( vidx >= (int) paths.size() )
                    paths.resize(2*paths.size());
            }

            // ... now ready to run experiments
            StatisticsCollection statistics =
                runExperiment(searchAlgorithm, search.get(), tiling, paths,
                              i-1, vidx, argv[i]);

            // gather statstic, need to create it the first time.
            if ( statisticsSum == 0 )
                statisticsSum = new StatisticsCollection(statistics);
            else
                statisticsSum->add(statistics);
        }
        cout << '\n';
        if ( argc > 2 )
        {
            statisticsSum->print(cout);
        }
    }
    catch (const exception& e)
    {
        cerr << "Error: " << e.what() << '\n';
        return -1;
    }
    return 0;
}

//-----------------------------------------------------------------------------

---