(C++) GetDistancesPath

 

GetDistancesPath is a maze code snippet: if you have a maze its distances to the exit of every free square (for example to solve a maze) you need an algorithm to 'walk' over these distances to the exit. 'GetDistancesPath' does exactly this.

 

 

 

 

 

Project and source code

 

Operating system: Ubuntu 10.04 LTS Lucid Lynx

IDE: Qt Creator 2.0.0

Project type: Qt4 GUI Application

Compiler: G++ 4.4.1

Libraries used:

• Qt: version 4.7.0 (32 bit)
• STL: from GCC, shipped with Qt Creator 2.0.0

 

 

 

 

 

---

#include <vector> //From http://www.richelbilderbeek.nl/GetDistancesPath.htm std::vector<std::vector<int> > GetDistancesPath(   const std::vector<std::vector<int> >& distances,   const int playerX,   const int playerY) {   const int size = distances.size();   std::vector<std::vector<int> > solution(size, std::vector<int>(size,0));   {     int x = playerX;     int y = playerY;     int distance = distances[y][x] - 1;     while (distance >= 0)     {       //We must be where we are now       solution[y][x] = 1;       if ( x!=0 && distances[y][x-1] == distance ) { --x; --distance; continue; }       if ( x!=0 && distances[y][x-1] == distance ) { --x; --distance; continue; }       if ( x!=size-1 && distances[y][x+1] == distance ) { ++x; --distance; continue; }       if ( x!=size-1 && distances[y][x+1] == distance ) { ++x; --distance; continue; }       if ( y!=0 && distances[y-1][x] == distance ) { --y; --distance; continue; }       if ( y!=0 && distances[y-1][x] == distance ) { --y; --distance; continue; }       if ( y!=size-1 && distances[y+1][x] == distance ) { ++y; --distance; continue; }       if ( y!=size-1 && distances[y+1][x] == distance ) { ++y; --distance; continue; }     }   }   return solution; }