Mercurial > fife-parpg

comparison engine/core/pathfinder/routepather/routepathersearch.cpp @ 310:8afb9b443f66

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merged the pathfinding branch to trunk
author wenlin_fife@33b003aa-7bff-0310-803a-e67f0ece8222
date Fri, 14 Aug 2009 00:00:58 +0000
parents 1465536aec94
children 0fd74235b34d
comparison
equal deleted inserted replaced
309:f6b67f424ad2 310:8afb9b443f66
38 38
39 #include "routepathersearch.h" 39 #include "routepathersearch.h"
40 40
41 namespace FIFE { 41 namespace FIFE {
42 RoutePatherSearch::RoutePatherSearch(const int session_id, const Location& from, const Location& to, SearchSpace* searchSpace) 42 RoutePatherSearch::RoutePatherSearch(const int session_id, const Location& from, const Location& to, SearchSpace* searchSpace)
43 : Search(session_id, from, to, searchSpace), m_destCoordInt(0), m_startCoordInt(0), m_next(0) { 43 : m_destCoordInt(0), m_startCoordInt(0), m_next(0), m_to(to), m_from(from), m_sessionId(session_id), m_searchspace(searchSpace), m_status(search_status_incomplete){
44 m_startCoordInt = m_searchspace->convertCoordToInt(from.getLayerCoordinates()); 44 m_startCoordInt = m_searchspace->convertCoordToInt(from.getLayerCoordinates());
45 int max_index = m_searchspace->getMaxIndex(); 45 int max_index = m_searchspace->getMaxIndex();
46 m_destCoordInt = m_searchspace->convertCoordToInt(to.getLayerCoordinates()); 46 m_destCoordInt = m_searchspace->convertCoordToInt(to.getLayerCoordinates());
47 m_sortedfrontier.pushElement(PriorityQueue<int, float>::value_type(m_startCoordInt, 0.0f)); 47 m_sortedfrontier.pushElement(PriorityQueue<int, float>::value_type(m_startCoordInt, 0.0f));
48 m_spt.resize(max_index + 1, -1); 48 m_spt.resize(max_index + 1, -1);
49 m_sf.resize(max_index + 1, -1); 49 m_sf.resize(max_index + 1, -1);
50 m_gCosts.resize(max_index + 1, 0.0f); 50 m_gCosts.resize(max_index + 1, 0.0f);
51 m_heuristic = Heuristic::getHeuristic(searchSpace->getLayer()->getCellGrid()->getType()); 51 m_heuristic = Heuristic::getHeuristic(searchSpace->getLayer()->getCellGrid()->getType());
52 } 52 }
53
53 54
54 void RoutePatherSearch::updateSearch() { 55 void RoutePatherSearch::updateSearch() {
55 if(m_sortedfrontier.empty()) { 56 if(m_sortedfrontier.empty()) {
56 setSearchStatus(search_status_failed); 57 setSearchStatus(search_status_failed);
57 return; 58 return;
79 if(m_searchspace->isInSearchSpace(loc)) { 80 if(m_searchspace->isInSearchSpace(loc)) {
80 if((adjacentInt == m_next || loc.getLayer()->cellContainsBlockingInstance(loc.getLayerCoordinates())) && 81 if((adjacentInt == m_next || loc.getLayer()->cellContainsBlockingInstance(loc.getLayerCoordinates())) &&
81 adjacentInt != m_destCoordInt) { 82 adjacentInt != m_destCoordInt) {
82 continue; 83 continue;
83 } 84 }
84 85 float hCost = m_heuristic->calculate((*i), destCoord);
85 float hCost = m_heuristic->calculate((*i), destCoord); 86 //float hCost = Heuristic::getHeuristic(m_searchspace->getLayer()->getCellGrid()->getType())->calculate((*i), destCoord);
86 float gCost = m_gCosts[m_next] + loc.getLayer()->getCellGrid()->getAdjacentCost(nextCoord, (*i)); 87 float gCost = m_gCosts[m_next] + loc.getLayer()->getCellGrid()->getAdjacentCost(nextCoord, (*i));
87 if(m_sf[adjacentInt] == -1) { 88 if(m_sf[adjacentInt] == -1) {
88 m_sortedfrontier.pushElement(PriorityQueue<int, float>::value_type(adjacentInt, gCost + hCost)); 89 m_sortedfrontier.pushElement(PriorityQueue<int, float>::value_type(adjacentInt, gCost + hCost));
89 m_gCosts[adjacentInt] = gCost; 90 m_gCosts[adjacentInt] = gCost;
90 m_sf[adjacentInt] = m_next; 91 m_sf[adjacentInt] = m_next;
104 Path path; 105 Path path;
105 //This assures that the agent always steps into the center of the cell. 106 //This assures that the agent always steps into the center of the cell.
106 Location to(m_to); 107 Location to(m_to);
107 to.setExactLayerCoordinates(FIFE::intPt2doublePt(to.getLayerCoordinates())); 108 to.setExactLayerCoordinates(FIFE::intPt2doublePt(to.getLayerCoordinates()));
108 path.push_back(to); 109 path.push_back(to);
110 int count = 0;
109 while(current != end) { 111 while(current != end) {
110 current = m_spt[current]; 112 if(m_spt[current] < 0 ) {
113 // This is when the size of m_spt can not handle the distance of the location
114 setSearchStatus(search_status_failed);
115 break;
116 }
117 current = m_spt[current];
111 Location newnode; 118 Location newnode;
112 newnode.setLayer(m_searchspace->getLayer()); 119 newnode.setLayer(m_searchspace->getLayer());
113 ModelCoordinate currentCoord = m_searchspace->convertIntToCoord(current); 120 ModelCoordinate currentCoord = m_searchspace->convertIntToCoord(current);
114 newnode.setLayerCoordinates(currentCoord); 121 newnode.setLayerCoordinates(currentCoord);
115 path.push_front(newnode); 122 path.push_front(newnode);
116 } 123 }
117 path.front().setExactLayerCoordinates(m_from.getExactLayerCoordinates()); 124 path.front().setExactLayerCoordinates(m_from.getExactLayerCoordinates());
118 return path; 125 return path;
119 } 126 }
120 } 127 }