Fawkes API  Fawkes Development Version
astar.cpp
1 
2 /***************************************************************************
3  * astar.cpp - Implementation of A*
4  *
5  * Generated: Mon Sep 15 18:38:00 2002
6  * Copyright 2002-2007 Stefan Jacobs, Martin Liebenberg
7  *
8  ****************************************************************************/
9 
10 /* This program is free software; you can redistribute it and/or modify
11  * it under the terms of the GNU General Public License as published by
12  * the Free Software Foundation; either version 2 of the License, or
13  * (at your option) any later version. A runtime exception applies to
14  * this software (see LICENSE.GPL_WRE file mentioned below for details).
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU Library General Public License for more details.
20  *
21  * Read the full text in the LICENSE.GPL_WRE file in the doc directory.
22  */
23 
24 #include <utils/search/astar.h>
25 
26 
27 namespace fawkes {
28 
29 /** @class AStar <utils/search/astar.h>
30  * This is an implementation of the A* search algorithm.
31  *
32  * @author Stefan Jacobs, Martin Liebenberg
33  */
34 /** @var AStar::closedList
35  * This is AStars closedList.
36  */
37 /** @var AStar::solution
38  * This is the final solution vector.
39  */
40 /** @var AStar::openList
41  * This is AStars openlist.
42  */
43 /** @struct AStar::Cmp <utils/search/astar.h>
44  * Comparison structure to be used for the ordering on AStar::openList.
45  * @fn AStar::Cmp::operator() ( AStarState * a1, AStarState * a2 ) const
46  * The relation >= of this ordering.
47  * @param a1 the left operand
48  * @param a2 the right operand
49  * @return true, if a1 <= b1, else false
50  */
51 
52 
53 /** Constructor.
54  * This is the constructor for the AStar Object.
55  */
57 {
58  while ( openList.size() > 0 )
59  {
60  openList.pop();
61  }
62  closedList.clear();
63  solution.clear();
64 }
65 
66  /** Destructor.
67  * This destructs the AStarObject.
68  */
70 {
71 
72  AStarState * best = 0;
73  while ( openList.size() > 0 )
74  {
75  best = openList.top();
76  openList.pop();
77  delete best;
78  }
79  closedList.clear();
80 }
81 
82  /** Solves a situation given by the initial state with AStar, and
83  * returns a vector of AStarStates that solve the problem.
84  * @param initialState pointer of AStarState to the initial state
85  * @return a vector of pointers of AStarState with the solution sequence
86  */
87 std::vector< AStarState * > AStar::solve( AStarState * initialState )
88 {
89  AStarState * best = 0;
90  while ( openList.size() > 0 )
91  {
92  best = openList.top();
93  openList.pop();
94  delete best;
95  }
96  closedList.clear();
97 
98  openList.push( initialState );
99  return getSolutionSequence( search() );
100 }
101 
102 
103 /** Search with astar. */
104 AStarState * AStar::search( )
105 {
106  AStarState * best = 0;
107  long key = 0;
108  std::vector< AStarState * > children;
109 
110  // while the openlist not is empty
111  while ( openList.size() > 0 )
112  {
113  // take the best state, and check if it is on closed list
114  do
115  {
116  if ( openList.size() > 0 )
117  {
118  best = openList.top();
119  openList.pop( );
120  }
121  else
122  return 0;
123  key = best->calculateKey( );
124  }
125  while ( closedList.find( key ) != closedList.end() );
126 
127  // put best state on closed list
128  closedList[key] = best;
129 
130  // check if its a goal.
131  if ( best->isGoal( ) )
132  {
133  return best;
134  }
135  // generate all its children
136  children = best->generateChildren( );
137  for ( unsigned int i = 0; i < children.size(); i++ )
138  openList.push( children[i] );
139  }
140  return 0;
141 }
142 
143 
144  /** Generates a solution sequence for a given state
145  * Initial solution is in solution[0]!
146  * @param node a pointer of AStarState to the goal
147  * @return the path from solution to initial solution
148  */
149 std::vector< AStarState * > AStar::getSolutionSequence( AStarState * node )
150 {
151  solution.clear();
152  AStarState * state = node;
153 
154  while ( state != 0 )
155  {
156  closedList.erase(state->key);
157  solution.insert( solution.begin(), state );
158  state = state->father;
159  }
160 
161  //delete the states, which are not part of the solution
162  while ( closedList.size() > 0 )
163  {
164  state = closedList.begin()->second;
165  closedList.erase(state->key);
166  delete state;
167  }
168  return solution;
169 }
170 
171 
172 } // end namespace fawkes
This is the abstract(!) class for an A* State.
Definition: astar_state.h:36
virtual std::vector< AStarState * > generateChildren()=0
Generate all successors and put them to this vector.
Fawkes library namespace.
~AStar()
Destructor.
Definition: astar.cpp:69
virtual bool isGoal()=0
Check, wether we reached a goal or not.
virtual long calculateKey()=0
Generates a unique key for this state.
std::vector< AStarState * > solve(AStarState *initialState)
Solves a situation given by the initial state with AStar, and returns a vector of AStarStates that so...
Definition: astar.cpp:87
AStar()
Constructor.
Definition: astar.cpp:56