Beginner A* Code with an error

[Roland Deschain]

I have started programming, and I tried doing a path finding algorithm. (The drawPath is an auxiliary function to be able to see the path found.) There seems to be a problem with the code, but I seem to not be able to find it. I would appreciate any comments about the code, whether it is a mistake or an improbable part.
This is the code:

  Position.h
#pragma once
class Position {
private:
	float _x, _y;
public:
	Position();
	Position(float x, float y);
	
	void setPosition(float x, float y);

	float getX();
	float getY();
};

 Position.cpp
#include "Position.h"
Position::Position() : _x(0), _y(0)
{}
Position::Position(float x, float y) : _x(x), _y(y)
{}

void Position::setPosition(float x, float y) 
{
	_x = x;
	_y = y;
}

float Position::getX()
{
	return _x;
}
float Position::getY()
{
	return _y;
}

Point.h
#pragma once
#include "Position.h"

class Point {
private:
	Position* _position;
	Point* _parent;
	bool _walkable;
	float g, h, f;

public:
	Point();
	Point(Position* position, bool walkable);

	Position* getPosition();
	Point* getParent();

	float getG();
	float getH();
	float getF();
	float distanceBetween(Point* end);

	bool hasParent();
	bool isWalkable();

	void setParent(Point* parent);
	void setWalkable(bool walkable);
	void calculateG();
	void calculateF(Point* destination);
	void calculateH(Point* destination);
};

Point.cpp
#include "Point.h"
#include <cmath>

Point::Point() : _walkable(false)
{
	_position = &Position();
}
Point::Point(Position* position, bool walkable) : _position(position), _walkable(walkable)
{}

Position* Point::getPosition()
{
	return _position;
}
Point* Point::getParent()
{
	return _parent;
}

float Point::getG()
{
	return g;
}
float Point::getH()
{
	return h;
}
float Point::getF()
{
	return f;
}

bool Point::hasParent()
{
	bool hasParent = true;
	if (_parent != nullptr) {
		hasParent = false;
	}
	return hasParent;
}
bool Point::isWalkable()
{
	return _walkable;
}

void Point::setParent(Point* parent)
{
	_parent = parent;
}
void Point::setWalkable(bool walkable)
{
	_walkable = walkable;
}
void Point::calculateF(Point* destination)
{
	calculateG();
	calculateH(destination);
	f = g + h;
}
void Point::calculateH(Point* destination)
{
	h = distanceBetween(destination);
}
void Point::calculateG()
{
	g = 0;
	if (hasParent()) {
		_parent->calculateG();
		g = _parent->g + distanceBetween(_parent);
	}
}
float Point::distanceBetween(Point* end)
{
	return std::sqrt(std::pow(end->getPosition()->getX() - getPosition()->getX(), 2) + std::pow(end->getPosition()->getY() - getPosition()->getY(), 2));
}

Map.h
#pragma once
#include "Point.h"
#include <list>

class Map {
private:
	std::list<Point*> points;
	float _width, _height;
	float _tileSize;
public:
	Map();
	Map(double width, double height, double tile_size);

	float getTileSize();

	Point* closestPoint(Position* position);

	std::list<Point*> closePoints(Point* point);

	void drawPath(std::list<Point*> path);
};

Map.cpp
#include "Map.h"
#include <iostream>
Map::Map() : _width(0), _height(0), _tileSize(1)
{
	float w = 0, h;
	while (w <= _width) {
		h = 0;
		while (h <= _height) {
			points.push_back(&Point(&Position(w, h), true));
			h += _tileSize;
		}
		w += _tileSize;
	}
}
Map::Map(double width, double height, double tile_size) : _width(width), _height(height), _tileSize(tile_size)
{
	int w = 0, h;
	while (w <= _width) {
		h = 0;
		while (h <= _height) {
			points.push_back(&Point(&Position(w,h),true));
			h =  h + _tileSize;
		}
		w = w + _tileSize;
	}

}

float Map::getTileSize()
{
	return _tileSize;
}

Point* Map::closestPoint(Position* position)
{
	std::list<Point*>::iterator i;
	for (i = points.begin(); i != points.end(); i++) {
		if ((*i)->getPosition()->getX() >= position->getX() - _tileSize/2 && (*i)->getPosition()->getX() <= position->getX() + _tileSize/2) {
			if ((*i)->getPosition()->getX() >= position->getX() - _tileSize/2 && (*i)->getPosition()->getX() <= position->getX() + _tileSize/2) {
				return (*i);
			}
		}
	}
}

std::list<Point*> Map::closePoints(Point* point)
{
	std::list<Point*> list;
	std::list<Point*>::iterator i;
	for (i = points.begin(); i != points.end(); i++) {
		if ((*i)->isWalkable()) {
			if ((*i)->getPosition()->getX() >= point->getPosition()->getX() - _tileSize && (*i)->getPosition()->getX() <= point->getPosition()->getX() + _tileSize) {
				if ((*i)->getPosition()->getX() >= point->getPosition()->getX() - _tileSize && (*i)->getPosition()->getX() <= point->getPosition()->getX() + _tileSize) {
					list.push_back(*i);
				}
			}
		}
	}
	return list;
}


void Map::drawPath(std::list<Point*> path)
{
	int x = 0;
	float height = 0;
	bool FOUND;
	std::list<Point*>::iterator i,t;
	for (i = points.begin(); i != points.end(); i++) {
		if ((*i)->getPosition()->getY() != height) {
			std::cout << std::endl;
		}
		FOUND = false;
		for (t = path.begin(); t != path.end(); t++) {
			if ((*i) == (*t)) {
				FOUND = true;
				break;
			}
		}
		if (FOUND) {
			std::cout << "*";
		}
		else if((*i)->isWalkable()){
			std::cout << " ";
		}
		else {
			std::cout << "X";
		}
		height = (*i)->getPosition()->getY();
	}
}

PathFinder.h
#pragma once
#include "Map.h"
class PathFinder {
private:
	Map* _map;
	
	Point* lowest_f(std::list<Point*> set);
	std::list<Point*> reconstructPath(Point* destination);

public:
	PathFinder();
	PathFinder(Map* map);
	
	std::list<Point*> findPath(Point* start, Point* destination);

	void drawPath(std::list<Point*> path);
};

PathFinder.cpp
#include "PathFinder.h"
#include <climits>

PathFinder::PathFinder()
{
	_map = &Map();
}
PathFinder::PathFinder(Map* map) : _map(map)
{}

void PathFinder::drawPath(std::list<Point*> path)
{
	_map->drawPath(path);
}
Point* PathFinder::lowest_f(std::list<Point*> set)
{
	int min = INT_MIN;
	Point* aux = 0;
	std::list<Point*>::iterator i;
	for (i = set.begin(); i != set.end(); i++) {
		if ((*i)->getF() < min) {
			min = (*i)->getF();
			aux = (*i);
		}
	}
	return aux;
}
std::list<Point*> PathFinder::reconstructPath(Point* destination)
{
	std::list<Point*> list;
	Point* current = destination;
	
	do {
		list.push_front(current);
		current = current->getParent();
	} while (current->hasParent());

	return list;
}

std::list<Point*> PathFinder::findPath(Point* start, Point* destination)
{
	std::list<Point*> closedSet = {}, openSet = { start }, neighbor;
	std::list<Point*>::iterator i, w, t;
	Point* current = start;
	Point* auxiliar;
	float tentative_g;
	bool FOUND;

	current->calculateF(destination);

	while(!openSet.empty())
	{
		current = lowest_f(openSet);
		if (current == destination) {
			return reconstructPath(current);
		}
		openSet.remove(current);
		closedSet.push_front(current);

		neighbor = _map->closePoints(current);
		for (i = neighbor.begin(); i != neighbor.end(); i++) {
			for (t = closedSet.begin(); t != closedSet.end(); t++) {
				if ((*i) == (*t)) {
					continue;
				}				
			}

			tentative_g = current->getG() + current->distanceBetween((*i));
			FOUND = false;
			for (w = openSet.begin(); t != openSet.end(); t++) {
				if ((*i) == (*t)) {
					FOUND = true;
					break;
				}
			}
			if (!FOUND) {
				(*i)->setParent(current);
				(*i)->calculateF(destination);
				openSet.push_back(*i);
			}
			else if (tentative_g >= (*i)->getG()){
				continue;
			}
			(*i)->setParent(current);
			(*i)->calculateF(destination);
		}
	}
	return {};
	
}

Main.cpp
#include "PathFinder.h"

int main() {
	Map map(100, 100, 10);
	PathFinder pathfinder(&map);
	
	pathfinder.drawPath(pathfinder.findPath(map.closestPoint(&Position(0, 0)), map.closestPoint(&Position(260, 100))));
	system("PAUSE");
}

[dhayden]

Line 44: Why is position a pointer? Doesn't a point always have a position?

Line 47: What are f, h, and h?

Line 104: Your hasParent() returns true when there ISN'T a parent. Why have this function at all when the caller could instead just call getParent() and test it themself?

Line 155: Why a list of pointers instead of a list of Points?

Line 168: When passing a container, it's always a good idea to pass it by reference (or const reference). Otherwise each time you call the function, the compiler will make a copy of the whole container.

Line 180: Here's your bug and it's related to my questions about using pointers instead of values. You're pushing the address of a temporary variable onto the list. The variable will be deleted it's memory free to be reused anytime after line 180 finishes. Furthermore, the Position whose address you're passing to the Point is also a temporary.

So by the time you reach line 181, your program is toast.

Change the pointers I mentioned to instances and see how it works then.

[shahfrid]

I am a beginner. When i tried my first code.
#include <iostream.h>
#include <conio.h>
int main()
{
clrscr()
cout <<"My First Programming.";
getch();
return 0;
}

above code i tried and when compiled then the error is
1 22 E:\Dev-Cpp\Untitled1.cpp [Error] iostream.h: No such file or directory

what is my fault? what to do now?
Please help

[joe864864]

@shahfrid open your own thread for your question.
Please read: Welcome -- read before posting!
http://www.cplusplus.com/forum/beginner/1/