PathFinding/main.cc

// Example of world building, display, and successor computation for the artificial 
// intelligence path-finding lab
//
// Author: Didier LIME
// Adapted by : Jovian HERSEMEULE
// Date: 2018-10-03

#include <iostream>
#include <list>
#include <cstdlib>
#include <ctime>
#include <stack>

using namespace std;

class World
{
	private:
		// Number of columns
		unsigned int l;

		// Number of lines
		unsigned int h;

                // Size of the array
                const unsigned int size;

		// Unidimensional array for tiles
		int* board;

	public:
		// Constructor
		World(unsigned int l_, unsigned int h_, double p)
                :l(l_), h(h_), size(l_ * h_)
		{
			board = new int[size]();

			// Add walls to the first and last columns
			for (unsigned int i = 0; i < h; i++)
			{
				board[i * l] = 1;
				board[i * l + l - 1] = 1;
			}

			// Add walls to the first and last lines
			for (unsigned int j = 0; j < l; j++)
			{
				board[j] = 1;
				board[(h - 1) * l + j] = 1;
			}

			for (unsigned int i = 0; i < h; i++)
			{
				for (unsigned int j = 0; j < l; j++)
				{
					// add a wall in this tile with probability p and provided that it is neither
					// the starting tile nor the goal tile 
					if ((double) rand() / RAND_MAX < p && !(i == 1 && j == 1) && !(i == h - 2 && j == l - 2))
					{
						board[i * l + j] = 1;
					}
				}
			}
		}

		// Display the world
		void display()
		{
			for (unsigned int i = 0; i < h; i++)
			{
				for (unsigned int j = 0; j < l; j++)
				{
					switch (board[i * l + j])
					{
						case 0:
							cout << " ";
							break;

						case 1:
							cout << "#";
							break;
					}
				}
				cout << endl;
			}
		}

		// compute the successors of tile number i in world w
		// we return the number n of valid successors
		// the actual list is in array r where only the first n
		// elements are significant
		unsigned int successors(unsigned int i, unsigned int r[4])
		{
			unsigned int n = 0;

			if (i >= 0 && i < size && board[i] != 1)
			{
				// if i is a correct tile number (inside the array and not on a wall)
				// look in the four adjacent tiles and keep only those with no wall
				const unsigned int moves[] = { i - 1, i + 1, i - l, i + l};

				for (unsigned int k = 0; k < 4; k++)
				{
					if (board[moves[k]] != 1)
					{
						r[n] = moves[k];
						n++;
					}
				}
			}

			return n;
		}

		// Depth-first search
		// starting from tile number s0, find a path to tile number t
		// return true if such a path exists, false otherwise
		// if it exists the path is given in variable path (hence the reference &)
		bool dfs(unsigned int s0, unsigned int t, list<unsigned int>& path)
		{
			bool r = false;

                        bool explored[size];

                        stack<unsigned int> open;
			open.push(s0);

                        for (unsigned int k(0); k < size; k ++)
                            explored[k] = false;

                        explored[s0] = true;

                        int current;
			int neighbour;
			unsigned int succs[4];
			unsigned int nbSuccs;

                        do {
				current = open.top();
				open.pop();

				nbSuccs = successors(current, succs);

				for (unsigned int i(0); i < nbSuccs; i++) {
					neighbour = succs[i];

					if (!explored[neighbour])
						open.push(neighbour);
				}

				// Build path
				path.push_back(current);


                        } while (!r && !open.empty());

			return r;
		} 
};

int main()
{
	// Initialise the random number generator
	srand(time(0));

	// Create a world
	World w(20, 10, 0.2);

	// Display it
	w.display();

	// Print the tile numbers of the successors of the starting tile (1, 1)
	unsigned int succs[4];
	unsigned int n = w.successors(21, succs);

	for (unsigned int k = 0; k < n; k++)
	{
		cout << succs[k] << " ";
	}
	cout << endl;

	return 0;
}