C++ Vectors and Optimization

bd123 (3)
This is my first time working with vectors in C++ and is the first time I have had to create any sort of path finding algorithm. Using the logic on this page http://en.wikipedia.org/wiki/Pathfinding I was able to get a program that runs and returns correct results. However I feel that it is horribly inefficient. As soon as I make the matrix containing the "maze" larger than 10x10 the program slows ALOT. Im not sure if it is my use of vectors or just a poor algorithm. Im not sure how to improve it and am very curious now that I got it working a returning a result. The program uses SDL to display the matrix on the screen but that isn't the issue right now.

These are the functions need to search the matrix for the path. The Matrix is a 2d array of 1s and 0s. 1s are movable squares while 0s cannot be moved on
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
int checkForPath(int Matrix[Y_SIZEOFMATRIX][X_SIZEOFMATRIX])
{
	int paths = 0;
	for(int i = 0; i<X_SIZEOFMATRIX; i++)
	{
	if(Matrix[i][X_SIZEOFMATRIX-1] == 1 && paths ==0) //end is goal
	{
		int count = 0;
		// Create Lists
		vector< vector<int> > openList(0, vector<int>(0));
		vector< vector<int> > closedList(0, vector<int>(0));
		//add end node to list of path
		vector<int> row;
		row.push_back(0);
		row.push_back(X_SIZEOFMATRIX-1);
		row.push_back(count);
		closedList.push_back(row);
		bool pathPossible = true;
		while(pathPossible == true)
		{
			for(int g = 0; g < closedList.size(); g++)
			{
				//Add adjacent cells to openList
				//up
				if(closedList[g][0] > 0)
				{
					vector<int> row;
					row.push_back(closedList[g][0]-1);
					row.push_back(closedList[g][1]);
					row.push_back(count+1);
					openList.push_back(row);
				}
				//down
				int bb = Y_SIZEOFMATRIX-1;
				if(closedList[g][0] < bb)
				{
					vector<int> row;
					row.push_back(closedList[g][0]+1);
					row.push_back(closedList[g][1]);
					row.push_back(count+1);
					openList.push_back(row);
				}
				//right
				int a = X_SIZEOFMATRIX-1;
				if(closedList[g][1] < a)
				{
					vector<int> row;
					row.push_back(closedList[g][0]);
					row.push_back(closedList[g][1]+1);
					row.push_back(count+1);
					openList.push_back(row);
				}
				//left
				if(closedList[g][1] > 0)
				{
					vector<int> row;
					row.push_back(closedList[g][0]);
					row.push_back(closedList[g][1]-1);
					row.push_back(count+1);
					openList.push_back(row);
				}
				//check open list for ok
				openList = processOpenList(openList,closedList,Matrix);
				//add remaining to closed
				int sizeBefore = closedList.size();
				for(int j =0; j < openList.size();j++)
				{
					vector<int> row;
					row.push_back(openList[j][0]);
					row.push_back(openList[j][1]);
					row.push_back(openList[j][2]);
					closedList.push_back(row);
				}
				int sizeAfter = closedList.size();
				if(sizeBefore == sizeAfter) //no new possiblilities
				{
					pathPossible = false;
					message = TTF_RenderText_Shaded( font, "No path exists",bgColor, textColor );
				}
				openList.clear(); //empty open List
				//loop through closed list?
				//Check for end
				if(closedList[g][1] == 0)
				{
					message = TTF_RenderText_Shaded( font, ":):):):):):):):):):):):):):):",bgColor, textColor );
					pathPossible = false;
					paths +=1;
				}
			}
			count++;
		}
	}
	}
	return paths;
}
vector< vector<int> > processOpenList(vector< vector<int> > open, vector< vector<int> > closed, int Matrix[Y_SIZEOFMATRIX][X_SIZEOFMATRIX])
{
	vector< vector<int> > temp(0, vector<int>(0));
	for(int j =0; j < open.size();j++)
	{
		if(Matrix[open[j][0]][open[j][1]] == 1)
		{
			bool existsInClosed = false;
			for(int k =0; k < closed.size();k++)
			{
				if(open[j][0] == closed[k][0] && open[j][1] == closed[k][1] && open[j][2] >= closed[k][2])
				{
					existsInClosed = true;
				}
			}
			if(existsInClosed == false)
			{
				vector<int> row;
				row.push_back(open[j][0]);
				row.push_back(open[j][1]);
				row.push_back(open[j][2]);
				temp.push_back(row);
			}
		}
	}
	return temp;
}


Entire program for reference
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
 
//Include SDL functions and datatypes
#include "SDL.h"
#include "SDL_ttf.h"
#include <string>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;

const int SCREEN_WIDTH = 800;
const int SCREEN_HEIGHT = 600;
const int SCREEN_BPP = 32;

const int X_SIZEOFMATRIX = 50;
const int Y_SIZEOFMATRIX = 50;
const int PERCENTDENSE = 70;

//function prototypes
SDL_Surface *load_image( std::string );
void apply_surface( int , int , SDL_Surface* , SDL_Surface* );
void seedArray(int[Y_SIZEOFMATRIX][X_SIZEOFMATRIX]);
bool displayLattice(int[Y_SIZEOFMATRIX][X_SIZEOFMATRIX]);
int checkForPath(int[Y_SIZEOFMATRIX][X_SIZEOFMATRIX]);
vector< vector<int> > processOpenList(vector< vector<int> >,vector< vector<int> >,int[Y_SIZEOFMATRIX][X_SIZEOFMATRIX]);
//Global Variables
SDL_Surface *screen = NULL;
SDL_Surface *message = NULL;
SDL_Event event;
TTF_Font *font = NULL;
SDL_Color textColor = {255, 255, 255 };
SDL_Color bgColor = {0,0,0};
bool renderBoard = true;

//The button Class
class Button
{
private:
	//The attributes of the button
	SDL_Rect box;

public:

	//Initialize the variables
	Button();
	Button( int x, int y, int w, int h );

	bool handle_events(bool playerTurn);
};

int main( int argc, char* args[] )
{
	//Initialize all SDL stuff
	bool quit = false;
	SDL_Init( SDL_INIT_EVERYTHING );
	TTF_Init();
	font = TTF_OpenFont( "lazy.ttf", 20 );

	//Set up the screen
	screen = SDL_SetVideoMode( SCREEN_WIDTH, SCREEN_HEIGHT, SCREEN_BPP, SDL_SWSURFACE );

	//Set the window caption
	SDL_WM_SetCaption("Lab 1", NULL );

	int lattice[Y_SIZEOFMATRIX][X_SIZEOFMATRIX];
	seedArray(lattice);
	message = TTF_RenderText_Shaded( font, "Press enter to solve",bgColor, textColor );
	int numPaths = 0;
	bool foundIt = false;
	//While the user hasn't quit
	while( quit == false )
	{
		//Something has been done
		while( SDL_PollEvent( &event ) )
		{
			//If the user closed the window
			if( event.type == SDL_QUIT )
			{
				//Quit the program
				quit = true;
			}
			if(event.type == SDL_KEYDOWN)
			{
				if(event.key.keysym.sym == SDLK_s)
				{
					message = TTF_RenderText_Shaded( font, "!!!!!!!!!!",bgColor, textColor );
					renderBoard = true;
					numPaths = checkForPath(lattice);
					if(numPaths > 0){foundIt =true;}
				}
			}
		}
		if(foundIt)
		{
		string msg("Path Exisits ");
		message = TTF_RenderText_Shaded( font, msg.c_str(), bgColor, textColor );
		}
		//Render the screen
		if(renderBoard)
		{
			renderBoard = displayLattice(lattice);
		}
		apply_surface(300,450,message,screen);
		SDL_Flip(screen);
	}
	return 0;
}

void seedArray(int Matrix[Y_SIZEOFMATRIX][X_SIZEOFMATRIX])
{
	//removed for char count
}
bool displayLattice(int Matrix[Y_SIZEOFMATRIX][X_SIZEOFMATRIX])
{
	//char count
}
int checkForPath(int Matrix[Y_SIZEOFMATRIX][X_SIZEOFMATRIX])
{
	//see above
}
vector< vector<int> > processOpenList(vector< vector<int> > open, vector< vector<int> > closed, int Matrix[Y_SIZEOFMATRIX][X_SIZEOFMATRIX])
{
	//see above
}
SDL_Surface *load_image( std::string filename )
{
	SDL_Surface* loadedImage = NULL;
	SDL_Surface* optimizedImage = NULL;
	loadedImage = SDL_LoadBMP( filename.c_str() );
	if( loadedImage != NULL )
	{
		optimizedImage = SDL_DisplayFormat( loadedImage );
		SDL_FreeSurface( loadedImage );
	}
	return optimizedImage;
}
void apply_surface( int x, int y, SDL_Surface* source, SDL_Surface* destination )
{
	SDL_Rect offset;
	offset.x = x;
	offset.y = y;
	SDL_BlitSurface( source, NULL, destination, &offset );
};


I really appreciate any advice or pointers you guys can give me, Thanks!
Peter87 (11254)
What algorithm are you using?

Try to avoid copying the vectors unnecessary. When you pass a vector to a function pass it as a reference.
bd123 (3)
I am using the algorithm that was on the wikipedia page because it seemed the easiest to start with
First, create a list of coordinates, which we will use as a queue. The queue will be initialized with one coordinate, the end coordinate. Each coordinate will also have a counter variable attached (the purpose of this will soon become evident). Thus, the queue starts off as ((3,8,0)).
Then, go through every element in the queue, including elements added to the end over the course of the algorithm, and to each element, do the following:
Create a list of the four adjacent cells, with a counter variable of the current element's counter variable + 1 (in our example, the four cells are ((2,8,1),(3,7,1),(4,8,1),(3,9,1)))
Check all cells in each list for the following two conditions:
If the cell is a wall, remove it from the list
If there is an element in the main list with the same coordinate and an equal or lower counter, remove it from the list
Add all remaining cells in the list to the end of the main list
Go to the next item in the list


What do you mean by copying? Do i copy them when passing them to the function using the names when I should be using a pointer instead?
Topic archived. No new replies allowed.