I wrote a maze program using a vector of lots of coordinates. Testing a 100x100 grid, when I used vector<int>
the program took 383 seconds, but when I used pair<int,int>
it took only 13 seconds. Where did this dramatic speedup come from?
Here is the code: (still to be improved)
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <string>
#include <algorithm>
#include <utility>
using namespace std;
const int HEIGHT = 100, WIDTH = 100;
bool in_bounds(int x, int y)
{
// Cells (0,0) to (WIDTH-1, HEIGHT -1)
return (x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT);
}
bool in_vector(int x, int y, vector<pair<int,int> > v)
{
return find(v.begin(), v.end(), pair<int,int>(x,y)) != v.end();
}
vector<string> get_dir(int x, int y, vector<pair<int,int> > v)
{
vector<string> open_dir; // Open neighbor cells
if (in_bounds(x+1,y) && !in_vector(x+1,y,v))
open_dir.push_back("e");
if (in_bounds(x-1,y) && !in_vector(x-1,y,v))
open_dir.push_back("w");
if (in_bounds(x,y+1) && !in_vector(x,y+1,v))
open_dir.push_back("n");
if (in_bounds(x,y-1) && !in_vector(x,y-1,v))
open_dir.push_back("s");
return open_dir;
}
int main()
{
vector<pair <int,int> > in_maze_cells {make_pair(0, 0)}, path {make_pair(0, 0)};
vector<vector<string> > hor_walls (WIDTH, vector<string>(HEIGHT, "--")),
vert_walls (WIDTH, vector<string>(HEIGHT, "|"));
srand(time(0));
while (in_maze_cells.size() != HEIGHT * WIDTH)
{
pair <int,int> current_cell = path.back();
int x = current_cell.first;
int y = current_cell.second;
vector<string> open_dir = get_dir(x, y, in_maze_cells);
if (open_dir.size())
{
// Randomly pick an open cell and move to it
string dir = open_dir[rand() % open_dir.size()];
pair<int,int> new_cell;
// Left and bottom wall coordinates match cell coordinates
if (dir == "e"){
new_cell = make_pair(x+1,y);
vert_walls[x+1][y] = " ";
}
if (dir == "w"){
new_cell = make_pair(x-1,y);
vert_walls[x][y] = " ";
}
if (dir == "n"){
new_cell = make_pair(x,y+1);
hor_walls[x][y+1] = " ";
}
if (dir == "s"){
new_cell = make_pair(x,y-1);
hor_walls[x][y] = " ";
}
in_maze_cells.push_back(new_cell);
path.push_back(new_cell);
}
else
path.pop_back(); // Backtracking
}
// Top row
for(int i=0; i<WIDTH; i++)
cout << "+--";
cout << "+" << endl;
for(int i=HEIGHT-1; i>=0; i--)
{
for(int j=0; j<WIDTH; j++)
cout << vert_walls[j][i] << " ";
cout << "|" << endl;
for(int j=0; j<WIDTH; j++)
cout << "+" << hor_walls[j][i];
cout << "+" << endl;
}
return 0;
}