Main   Class Hierarchy   Classes   Compound List   Files   Compound Members   File Members   Pages  

astar.cpp

Go to the documentation of this file.
00001 //-----------------------------------------------------------------------------
00002 /** @file astar.cpp
00003     @see astar.h
00004 
00005     $Id: astar_8cpp-source.html,v 1.1.1.1 2003/08/07 19:41:38 emarkus Exp $
00006     $Source: /usr/cvsroot/www_pathfind/libpathfind/0.1.0/doc/astar_8cpp-source.html,v $
00007 */
00008 //-----------------------------------------------------------------------------
00009 
00010 #include "astar.h"
00011 
00012 #include <iostream>
00013 #include <math.h>
00014 #include <memory>
00015 #include <assert.h>
00016 #include "util.h"
00017 
00018 using namespace std;
00019 using namespace PathFind;
00020 
00021 //-----------------------------------------------------------------------------
00022 
00023 AStarNode::Compare::~Compare()
00024 {
00025     ;
00026 }
00027 
00028 bool AStarNode::Compare::operator()(const AStarNode& node1,
00029                                     const AStarNode& node2)
00030 {
00031     int f1 = node1.m_f;
00032     int f2 = node2.m_f;
00033     if (f1 != f2)
00034         return (f1 < f2);
00035     int g1 = node1.m_g;
00036     int g2 = node2.m_g;
00037     return (g1 > g2);
00038 }
00039 
00040 //-----------------------------------------------------------------------------
00041 
00042 void AStarNode::print(ostream& ostrm) const
00043 {
00044     ostrm << "id:" << m_nodeId << '(' << m_g << ',' << m_h << ',' << m_f 
00045           << ',' << m_parent << ')';
00046 }
00047 
00048 //-----------------------------------------------------------------------------
00049 
00050 void AStarClosed::add(const AStarNode& node)
00051 {
00052     m_list.push_back(node);
00053 }
00054 
00055 vector<int> AStarClosed::constructPath(int start, int target)
00056 {
00057     vector<int> result;
00058     int nodeId = target;
00059     while (true)
00060     {
00061         result.push_back(nodeId);
00062         if (nodeId == start)
00063             break;
00064         const AStarNode* node = search(nodeId);
00065         assert(node != 0);
00066         nodeId = node->m_parent;
00067     }
00068     assert(result.size() > 0);
00069     assert(*result.begin() == target);
00070     assert(*(result.end() - 1) == start);
00071     return result;
00072 }
00073 
00074 void AStarClosed::init(int maxNodeId)
00075 {
00076     m_list.clear();
00077 }
00078 
00079 void AStarClosed::print(ostream& ostrm) const
00080 {
00081    ostrm << "Closed {\n";
00082    for (list<AStarNode>::const_iterator i = m_list.begin();
00083         i != m_list.end(); ++i) 
00084    {
00085        i->print(ostrm);
00086        ostrm << '\n';
00087    }   
00088    ostrm << "}\n";
00089 }
00090 
00091 void AStarClosed::remove(int nodeId)
00092 {
00093     for (list<AStarNode>::iterator i = m_list.begin();
00094          i != m_list.end(); ++i)
00095         if (i->m_nodeId == nodeId)
00096         {
00097             m_list.erase(i);
00098             return;
00099         }
00100 }
00101 
00102 const AStarNode* AStarClosed::search(int nodeId) const
00103 {
00104     for (list<AStarNode>::const_iterator i = m_list.begin();
00105          i != m_list.end(); ++i)
00106         if (i->m_nodeId == nodeId)
00107             return &(*i);
00108     return 0;
00109 }
00110 
00111 //-----------------------------------------------------------------------------


Generated on Thu Aug 7 13:04:49 2003 by Doxygen1.3.1