Jump to content

  • Log In with Google      Sign In   
  • Create Account


#Actualtsolron

Posted 10 January 2013 - 04:10 AM

First off, this if for a game I'm designing, but what I need help on seemed to be more in the 'general' category of programming.

 

I've worked for several hours on modifying a Python Breadth-First-Search (BFS) I had written. The goal is a search which starts at node (x,y) and adds all nodes within a distance to a vector. I use a priority queue and while loop to ensure I find the shortest path, and so I'm not using recursion.

 

My issue is that when I push back my class TMove onto the vector tiles (std::vector<TMove> tiles), it doesn't properly add it. Here's the relevant code. The specific line is #235.

 

void BFS2(int t, int moves, int levelWidth, int levelHeight, std::vector<TMove> &vect)
{
	vect.clear();

	std::set<int> visited;
	std::vector<TMove> tiles;
	int numInTiles = 0;
	std::priority_queue< std::pair<int,int>, std::vector<std::pair<int,int>>, pQueueCompare> pQueue;

	// TMove( index of Terrain in terrain, movement required to get here, parent index )
	tiles.push_back(TMove(t, 0, 0));
	pQueue.push(std::make_pair(numInTiles,0));
	numInTiles++;

 

Originally I was using a std::unique_ptr<TMove>, but the same issue was happening. I don't think it's actually initializing anything within tiles, but I'm not sure quite why. Similar code has worked in past projects.

 

 

 

Other relevant code, including the rest of the Breadth-First-Search is below.

 

 

 

 

TMove.h

#ifndef TMove_H
#define TMove_H

#include "Terrain.h"
#include <memory>

class TMove
{
public:
	TMove(int Index, int Moves, int Parent);
	~TMove(void);
	int getMoves(void);
	int getIndex(void);
	int getParent(void);
private:
	int index;
	int moves;
	int parent;
};

#endif

 

TMove.cpp

#include "TMove.h"

TMove::TMove(int Index, int Moves, int Parent)
{
	index = index;
	moves = Moves;
	parent = Parent;
}

TMove::~TMove(void)
{
}

int TMove::getMoves(void)
{
	return moves;
}

int TMove::getIndex(void)
{
	return index;
}

int TMove::getParent(void)
{
	return parent;
}

 

Modified Breadth-First-Search

void BFS2(int t, int moves, int levelWidth, int levelHeight, std::vector<TMove> &vect)
{
	vect.clear();

	std::set<int> visited;
	std::vector<TMove> tiles;
	int numInTiles = 0;
	std::priority_queue< std::pair<int,int>, std::vector<std::pair<int,int>>, pQueueCompare> pQueue;

	// TMove( index of Terrain in terrain, movement required to get here, parent index )
	tiles.push_back(TMove(t, 0, 0));
	pQueue.push(std::make_pair(numInTiles,0));
	numInTiles++;

	int tempT = -1;
	int curMove = 0;

	// Keep looping while there are elements in the priority queue.
	while(pQueue.empty() == false)
	{
		// Get the current element.
		TMove current = tiles.at(pQueue.top().first);
		// Remove it from the priority queue.
		pQueue.pop();
		// Add it to the visited list and vect vector.
		//visited.insert(terrain.at(current->getIndex()));
		visited.insert(current.getIndex());
		vect.push_back(current);

		// Get data
		int index = current.getIndex();
		int X = terrain.at(index)->getX();
		int Y = terrain.at(index)->getY();
		int movement = current.getMoves();


		// Left
		if (X != 0)
		{
			tempT = current.getIndex() - 1;
			curMove = movement + terrainData[terrain.at(tempT)->getType()];
			if (curMove <= moves && visited.find(index - 1) == visited.end())
			{
				tiles.push_back(TMove(current.getIndex() - 1, curMove, index));
				pQueue.push(std::make_pair(numInTiles, curMove));
				numInTiles++;
			}
		}
		// Right
		if (X != levelWidth - 1)
		{
			tempT = current.getIndex() + 1;
			curMove = movement + terrainData[terrain.at(tempT)->getType()];
			if (curMove <= moves && visited.find(index + 1) == visited.end())
			{
				tiles.push_back(TMove(current.getIndex() + 1, curMove, index));
				pQueue.push(std::make_pair(numInTiles, curMove));
				numInTiles++;
			}
		}
		// Up
		if (Y != 0)
		{
			tempT = current.getIndex() - levelWidth;
			curMove = movement + terrainData[terrain.at(tempT)->getType()];
			if (curMove <= moves && visited.find(index - levelWidth) == visited.end())
			{
				tiles.push_back(TMove(current.getIndex() - levelWidth, curMove, index));
				pQueue.push(std::make_pair(numInTiles, curMove));
				numInTiles++;
			}
		}
		// Down
		if (Y != levelHeight - 1)
		{
			tempT = current.getIndex() + levelWidth;
			curMove = movement + terrainData[terrain.at(tempT)->getType()];
			if (curMove <= moves && visited.find(index - levelWidth) == visited.end())
			{
				tiles.push_back(TMove(current.getIndex() - levelWidth, curMove, index));
				pQueue.push(std::make_pair(numInTiles, curMove));
				numInTiles++;
			}
		}
	}
}

#2tsolron

Posted 10 January 2013 - 04:10 AM

First off, this if for a game I'm designing, but what I need help on seemed to be more in the 'general' category of programming.

 

I've worked for several hours on modifying a Python Breadth-First-Search (BFS) I had written. The goal is a search which starts at node (x,y) and adds all nodes within a distance to a vector. I use a priority queue and while loop to ensure I find the shortest path, and so I'm not using recursion.

 

My issue is that when I push back my class TMove onto the vector tiles (std::vector<TMove> tiles), it doesn't properly add it. Here's the relevant code. The specific line is #235.

 

void BFS2(int t, int moves, int levelWidth, int levelHeight, std::vector<TMove> &vect)
{
	vect.clear();

	std::set<int> visited;
	std::vector<TMove> tiles;
	int numInTiles = 0;
	std::priority_queue< std::pair<int,int>, std::vector<std::pair<int,int>>, pQueueCompare> pQueue;

	// TMove( index of Terrain in terrain, movement required to get here, parent index )
	tiles.push_back(TMove(t, 0, 0));
	pQueue.push(std::make_pair(numInTiles,0));
	numInTiles++;

 

Originally I was using a std::unique_ptr<TMove>, but the same issue was happening. I don't think it's actually initializing anything within tiles, but I'm not sure quite why. Similar code has worked in past projects.

 

 

 

Other relevant code, including the rest of the BFS is below.

 

 

 

 

TMove.h

#ifndef TMove_H
#define TMove_H

#include "Terrain.h"
#include <memory>

class TMove
{
public:
	TMove(int Index, int Moves, int Parent);
	~TMove(void);
	int getMoves(void);
	int getIndex(void);
	int getParent(void);
private:
	int index;
	int moves;
	int parent;
};

#endif

 

TMove.cpp

#include "TMove.h"

TMove::TMove(int Index, int Moves, int Parent)
{
	index = index;
	moves = Moves;
	parent = Parent;
}

TMove::~TMove(void)
{
}

int TMove::getMoves(void)
{
	return moves;
}

int TMove::getIndex(void)
{
	return index;
}

int TMove::getParent(void)
{
	return parent;
}

 

Modified Breadth-First-Search

void BFS2(int t, int moves, int levelWidth, int levelHeight, std::vector<TMove> &vect)
{
	vect.clear();

	std::set<int> visited;
	std::vector<TMove> tiles;
	int numInTiles = 0;
	std::priority_queue< std::pair<int,int>, std::vector<std::pair<int,int>>, pQueueCompare> pQueue;

	// TMove( index of Terrain in terrain, movement required to get here, parent index )
	tiles.push_back(TMove(t, 0, 0));
	pQueue.push(std::make_pair(numInTiles,0));
	numInTiles++;

	int tempT = -1;
	int curMove = 0;

	// Keep looping while there are elements in the priority queue.
	while(pQueue.empty() == false)
	{
		// Get the current element.
		TMove current = tiles.at(pQueue.top().first);
		// Remove it from the priority queue.
		pQueue.pop();
		// Add it to the visited list and vect vector.
		//visited.insert(terrain.at(current->getIndex()));
		visited.insert(current.getIndex());
		vect.push_back(current);

		// Get data
		int index = current.getIndex();
		int X = terrain.at(index)->getX();
		int Y = terrain.at(index)->getY();
		int movement = current.getMoves();


		// Left
		if (X != 0)
		{
			tempT = current.getIndex() - 1;
			curMove = movement + terrainData[terrain.at(tempT)->getType()];
			if (curMove <= moves && visited.find(index - 1) == visited.end())
			{
				tiles.push_back(TMove(current.getIndex() - 1, curMove, index));
				pQueue.push(std::make_pair(numInTiles, curMove));
				numInTiles++;
			}
		}
		// Right
		if (X != levelWidth - 1)
		{
			tempT = current.getIndex() + 1;
			curMove = movement + terrainData[terrain.at(tempT)->getType()];
			if (curMove <= moves && visited.find(index + 1) == visited.end())
			{
				tiles.push_back(TMove(current.getIndex() + 1, curMove, index));
				pQueue.push(std::make_pair(numInTiles, curMove));
				numInTiles++;
			}
		}
		// Up
		if (Y != 0)
		{
			tempT = current.getIndex() - levelWidth;
			curMove = movement + terrainData[terrain.at(tempT)->getType()];
			if (curMove <= moves && visited.find(index - levelWidth) == visited.end())
			{
				tiles.push_back(TMove(current.getIndex() - levelWidth, curMove, index));
				pQueue.push(std::make_pair(numInTiles, curMove));
				numInTiles++;
			}
		}
		// Down
		if (Y != levelHeight - 1)
		{
			tempT = current.getIndex() + levelWidth;
			curMove = movement + terrainData[terrain.at(tempT)->getType()];
			if (curMove <= moves && visited.find(index - levelWidth) == visited.end())
			{
				tiles.push_back(TMove(current.getIndex() - levelWidth, curMove, index));
				pQueue.push(std::make_pair(numInTiles, curMove));
				numInTiles++;
			}
		}
	}
}

#1tsolron

Posted 10 January 2013 - 04:09 AM

First off, this if for a game I'm designing, but what I need help on seemed to be more in the 'general' category of programming.

 

I've worked for several hours on modifying a Python Breadth-First-Search (BFS) I had written. The goal is a search which starts at node (x,y) and adds all nodes within a distance to a vector. I use a priority queue and while loop to ensure I find the shortest path, and so I'm not using recursion.

 

My issue is that when I push back my class TMove onto the vector tiles (std::vector<TMove> tiles), it doesn't properly add it. Here's the relevant code, and the specific line is made red.

 

void BFS2(int t, int moves, int levelWidth, int levelHeight, std::vector<TMove> &vect)
{
	vect.clear();

	std::set<int> visited;
	std::vector<TMove> tiles;
	int numInTiles = 0;
	std::priority_queue< std::pair<int,int>, std::vector<std::pair<int,int>>, pQueueCompare> pQueue;

	// TMove( index of Terrain in terrain, movement required to get here, parent index )
	tiles.push_back(TMove(t, 0, 0));
	pQueue.push(std::make_pair(numInTiles,0));
	numInTiles++;

 

Originally I was using a std::unique_ptr<TMove>, but the same issue was happening. I don't think it's actually initializing anything within tiles, but I'm not sure quite why. Similar code has worked in past projects.

 

 

 

Other relevant code, including the rest of the BFS is below.

 

 

 

 

TMove.h

#ifndef TMove_H
#define TMove_H

#include "Terrain.h"
#include <memory>

class TMove
{
public:
	TMove(int Index, int Moves, int Parent);
	~TMove(void);
	int getMoves(void);
	int getIndex(void);
	int getParent(void);
private:
	int index;
	int moves;
	int parent;
};

#endif

 

TMove.cpp

#include "TMove.h"

TMove::TMove(int Index, int Moves, int Parent)
{
	index = index;
	moves = Moves;
	parent = Parent;
}

TMove::~TMove(void)
{
}

int TMove::getMoves(void)
{
	return moves;
}

int TMove::getIndex(void)
{
	return index;
}

int TMove::getParent(void)
{
	return parent;
}

 

Modified Breadth-First-Search

void BFS2(int t, int moves, int levelWidth, int levelHeight, std::vector<TMove> &vect)
{
	vect.clear();

	std::set<int> visited;
	std::vector<TMove> tiles;
	int numInTiles = 0;
	std::priority_queue< std::pair<int,int>, std::vector<std::pair<int,int>>, pQueueCompare> pQueue;

	// TMove( index of Terrain in terrain, movement required to get here, parent index )
	tiles.push_back(TMove(t, 0, 0));
	pQueue.push(std::make_pair(numInTiles,0));
	numInTiles++;

	int tempT = -1;
	int curMove = 0;

	// Keep looping while there are elements in the priority queue.
	while(pQueue.empty() == false)
	{
		// Get the current element.
		TMove current = tiles.at(pQueue.top().first);
		// Remove it from the priority queue.
		pQueue.pop();
		// Add it to the visited list and vect vector.
		//visited.insert(terrain.at(current->getIndex()));
		visited.insert(current.getIndex());
		vect.push_back(current);

		// Get data
		int index = current.getIndex();
		int X = terrain.at(index)->getX();
		int Y = terrain.at(index)->getY();
		int movement = current.getMoves();


		// Left
		if (X != 0)
		{
			tempT = current.getIndex() - 1;
			curMove = movement + terrainData[terrain.at(tempT)->getType()];
			if (curMove <= moves && visited.find(index - 1) == visited.end())
			{
				tiles.push_back(TMove(current.getIndex() - 1, curMove, index));
				pQueue.push(std::make_pair(numInTiles, curMove));
				numInTiles++;
			}
		}
		// Right
		if (X != levelWidth - 1)
		{
			tempT = current.getIndex() + 1;
			curMove = movement + terrainData[terrain.at(tempT)->getType()];
			if (curMove <= moves && visited.find(index + 1) == visited.end())
			{
				tiles.push_back(TMove(current.getIndex() + 1, curMove, index));
				pQueue.push(std::make_pair(numInTiles, curMove));
				numInTiles++;
			}
		}
		// Up
		if (Y != 0)
		{
			tempT = current.getIndex() - levelWidth;
			curMove = movement + terrainData[terrain.at(tempT)->getType()];
			if (curMove <= moves && visited.find(index - levelWidth) == visited.end())
			{
				tiles.push_back(TMove(current.getIndex() - levelWidth, curMove, index));
				pQueue.push(std::make_pair(numInTiles, curMove));
				numInTiles++;
			}
		}
		// Down
		if (Y != levelHeight - 1)
		{
			tempT = current.getIndex() + levelWidth;
			curMove = movement + terrainData[terrain.at(tempT)->getType()];
			if (curMove <= moves && visited.find(index - levelWidth) == visited.end())
			{
				tiles.push_back(TMove(current.getIndex() - levelWidth, curMove, index));
				pQueue.push(std::make_pair(numInTiles, curMove));
				numInTiles++;
			}
		}
	}
}

 

 


PARTNERS