Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualSparkon

Posted 22 October 2012 - 11:41 AM

Sounds to me like that inner loop can be optimized, if you only test 8 nodes per millisecond. (assuming modern PC)
Remember, adding threads will only increase capacity by the number of cores you have.
Optimizing your inner loop could give you 100x improvement in some cases Posted Image (not saying you could in this case)

What is your heuristic for A*? if its euclidian distance to goal, you could try squared distance, just as good but a lot faster.

There are also more advanced ones to handle dead ends better if your map have lots of those, you could check this out for example: http://www.ru.is/fac...jornssonH06.pdf

Though, when you've exhausted all algorithmic improvements and optimizations, at least it IS easily parallelized, and your assumption of 1 path per thread sounds very good.


For the DFS ( that is causing me most of the trouble ) to get from node 10 to 600 ( it's doing the worst path possible ) with ~15k recursion in the inner loop and ~8400 nodes and ~32600 edges ( only 4 directions ) it takes 1 seconds. Here is my code for the DFS ( for this algorithm i'm following a book )
void GraphSearch::DFSearch(int sourceID,int targetID,std::vector<int>& path)
{
// creating containers
std::stack<const MapEdge*> stack;
std::vector<int> visitedNodes(pNodes_->size(),node::NODE_UNVISITED); // creating the container here is quite slow, but DFS still takes 1 sec
std::vector<MapEdge*> connectingNodes;
sf::Clock clock;
float timeElapsed = 0;
int deep = 0;
MapEdge dummyStart(sourceID,sourceID,10);
stack.push(&dummyStart);
while(!stack.empty())
{
  timeElapsed += clock.restart().asSeconds();
  deep += 1;
  const MapEdge* next = stack.top();
  stack.pop();
  if (next->To() == targetID)
  {
   std::cout << "Time elapsed " << timeElapsed
	<< " on : " << deep << " recursions" << std::endl;
   return;
  }
  path[next->To()] = next->From();
  visitedNodes[next->To()] = node::NODE_VISITED;
  connectingNodes.clear();
  FindConnectingNodes(next->To(),connectingNodes); // this might be the problem since i'm looping through 32k edges * 15k recursions
  std::size_t s = connectingNodes.size();
  for(int i = 0;i <s;++i)
  {
   if (visitedNodes[connectingNodes[i]->To()] == node::NODE_UNVISITED)
	stack.push(connectingNodes[i]);
  }
}
}

edit : yes the FindConnectingNodes is definitively a problem, i've just given a run with VerySleepy and i've found out that is the most expensive call. something like 20% of the whole program ( windows call included)

#2Sparkon

Posted 22 October 2012 - 11:38 AM

Sounds to me like that inner loop can be optimized, if you only test 8 nodes per millisecond. (assuming modern PC)
Remember, adding threads will only increase capacity by the number of cores you have.
Optimizing your inner loop could give you 100x improvement in some cases Posted Image (not saying you could in this case)

What is your heuristic for A*? if its euclidian distance to goal, you could try squared distance, just as good but a lot faster.

There are also more advanced ones to handle dead ends better if your map have lots of those, you could check this out for example: http://www.ru.is/fac...jornssonH06.pdf

Though, when you've exhausted all algorithmic improvements and optimizations, at least it IS easily parallelized, and your assumption of 1 path per thread sounds very good.


For the DFS ( that is causing me most of the trouble ) to get from node 10 to 600 ( it's doing the worst path possible ) with ~15k recursion in the inner loop and ~8400 nodes and ~32600 edges ( only 4 directions ) it takes 1 seconds. Here is my code for the DFS ( for this algorithm i'm following a book )
void GraphSearch::DFSearch(int sourceID,int targetID,std::vector<int>& path)
{
// creating containers
std::stack<const MapEdge*> stack;
std::vector<int> visitedNodes(pNodes_->size(),node::NODE_UNVISITED); // creating the container here is quite slow, but DFS still takes 1 sec
std::vector<MapEdge*> connectingNodes;
sf::Clock clock;
float timeElapsed = 0;
int deep = 0;
MapEdge dummyStart(sourceID,sourceID,10);
stack.push(&dummyStart);
while(!stack.empty())
{
  timeElapsed += clock.restart().asSeconds();
  deep += 1;
  const MapEdge* next = stack.top();
  stack.pop();
  if (next->To() == targetID)
  {
   std::cout << "Time elapsed " << timeElapsed
	<< " on : " << deep << " recursions" << std::endl;
   return;
  }
  path[next->To()] = next->From();
  visitedNodes[next->To()] = node::NODE_VISITED;
  connectingNodes.clear();
  FindConnectingNodes(next->To(),connectingNodes); // this might be the problem since i'm looping through 32k edges * 15k recursions
  std::size_t s = connectingNodes.size();
  for(int i = 0;i <s;++i)
  {
   if (visitedNodes[connectingNodes[i]->To()] == node::NODE_UNVISITED)
	stack.push(connectingNodes[i]);
  }
}
}

#1Sparkon

Posted 22 October 2012 - 11:36 AM

Sounds to me like that inner loop can be optimized, if you only test 8 nodes per millisecond. (assuming modern PC)
Remember, adding threads will only increase capacity by the number of cores you have.
Optimizing your inner loop could give you 100x improvement in some cases Posted Image (not saying you could in this case)

What is your heuristic for A*? if its euclidian distance to goal, you could try squared distance, just as good but a lot faster.

There are also more advanced ones to handle dead ends better if your map have lots of those, you could check this out for example: http://www.ru.is/fac...jornssonH06.pdf

Though, when you've exhausted all algorithmic improvements and optimizations, at least it IS easily parallelized, and your assumption of 1 path per thread sounds very good.


For the DFS ( that is causing me most of the trouble ) to get from node 10 to 600 ( it's doing the worst path possible ) with ~15k recursion in the inner loop and ~8400 nodes and ~32600 edges ( only 4 directions ) it takes 1 seconds. Here is my code for the DFS ( for this algorithm i'm following a book )
void GraphSearch::DFSearch(int sourceID,int targetID,std::vector<int>& path)
{
// creating containers
std::stack<const MapEdge*> stack;
std::vector<int> visitedNodes(pNodes_->size(),node::NODE_UNVISITED); // creating the container here is quite slow, but DFS still takes 1 sec
std::vector<MapEdge*> connectingNodes;
sf::Clock clock;
float timeElapsed = 0;
int deep = 0;
MapEdge dummyStart(sourceID,sourceID,10);
stack.push(&dummyStart);
while(!stack.empty())
{
  timeElapsed += clock.restart().asSeconds();
  deep += 1;
  const MapEdge* next = stack.top();
  stack.pop();
  if (next->To() == targetID)
  {
   std::cout << "Time elapsed " << timeElapsed
    << " on : " << deep << " recursions" << std::endl;
   return;
  }
  path[next->To()] = next->From();
  visitedNodes[next->To()] = node::NODE_VISITED;
  connectingNodes.clear();
  FindConnectingNodes(next->To(),connectingNodes);
  std::size_t s = connectingNodes.size();
  for(int i = 0;i <s;++i)
  {
   if (visitedNodes[connectingNodes[i]->To()] == node::NODE_UNVISITED)
    stack.push(connectingNodes[i]);
  } 
}
}

PARTNERS