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;

}

Go back to Richel Bilderbeek's C++ page.

Go back to Richel Bilderbeek's homepage.

(C++) GetDistancesPath

Project and source code