I have been programming for a little while, but I am relativly new to c++. I am trying to implement the A* algorithm and have managed to produce the code below. The implementation producces the expected result, the shortest path from point A to B in a 2D grid, but I suspect i leave behind some memory leaks.
I tested this by overloading the new and delete operators to keep track of the amount of bytes allocated on the heap and it showed that a lot of memeory never got released. However I also tested the number of nodes that never got deleted but it showed that there were that all allocated nodes also got their destructor called. Note in the code that i only call new on Node, hence my confunsion. I have much confusion about this and would be happy for an explenation.
I have tried using smart pointers, but enden up with circular refrences which were difficult to resolve.
This is also my first post on Stack Overflow so please feel free to point how I can improve my questions. Thanks in advance.
#include<vector>
#include<array>
#include<cmath>
int mynodes = 0;
int memory_left = 0;
void* operator new(size_t size)
{
memory_left += size;
return malloc(size);
}
void operator delete(void* memory, size_t size)
{
memory_left -= size;
free(memory);
}
struct Node{
std::array<int, 2> position;
Node* parent = nullptr;
double h, g, f;
Node(const std::array<int, 2>& pos)
:position(pos){mynodes++;}
~Node(){ mynodes--; }
};
std::vector<std::array<int, 2>> find_children(const std::vector<std::vector<int>>& grid, const std::array<int, 2>& pos){
std::vector<std::array<int, 2>> children;
children.reserve(8);
for(int t = -1; t < 2; t++){
for(int q = -1; q < 2; q++){
if(t != 0 || q != 0){
if(abs(t) == abs(q)) continue;
std::array<int, 2> cur_pos = {pos[0]+q, pos[1]+t};
if(cur_pos[0] >= 0 && cur_pos[0] < grid[0].size() && cur_pos[1] >= 0 && cur_pos[1] < grid.size())
{
if(grid[cur_pos[1]][cur_pos[0]] == 0)
{
children.push_back(cur_pos);
}
}
}
}
}
return children;
}
bool search_vect(const std::vector<Node*>& set, const std::array<int, 2>& pos)
{
for(Node* node : set)
{
if(node->position[0] == pos[0] && node->position[1] == pos[1]) return true;
}
return false;
}
void releaseNodes(std::vector<Node*>& set)
{
for(auto& node : set)
{
delete node;
}
set.clear();
}
std::vector<std::array<int, 2>> find_path(const std::vector<std::vector<int>>& grid, std::array<int, 2> start, std::array<int, 2> end){
Node* cur_node = new Node(start);
std::vector<Node*> open_vect;
std::vector<Node*> closed_vect;
open_vect.push_back(cur_node);
while(cur_node->position != end){
double lowest_f = INFINITY;
size_t idx = 0;
for(size_t i = 0; i < open_vect.size(); i++)
{
if(open_vect[i]->f < lowest_f)
{
cur_node = open_vect[i];
lowest_f = cur_node->f;
idx = i;
}
}
open_vect.erase(open_vect.begin() + idx);
std::vector<std::array<int, 2>> children = find_children(grid, cur_node->position);
closed_vect.push_back(cur_node);
for(const auto& child_pos : children){
// if(closed_vect.find(child_pos) != closed_vect.end() || open_vect.find(child_pos) != open_vect.end()) continue;
if(search_vect(closed_vect, child_pos) || search_vect(open_vect, child_pos))
{
continue;
}
Node* new_node = new Node(child_pos);
new_node->g = cur_node->g + 1;
new_node->h = abs(end[0] - child_pos[0]) + abs(end[1] - child_pos[1]);
new_node->f = new_node->g + new_node->h;
new_node->parent = cur_node;
// double h = sqrt(pow(end[0] - child_pos[0], 2) + pow(end[1] - child_pos[1], 2));
open_vect.push_back(new_node);
}
}
std::vector<std::array<int, 2>> path;
while(cur_node != nullptr){
path.push_back(cur_node->position);
cur_node = cur_node->parent;
}
releaseNodes(open_vect);
releaseNodes(closed_vect);
return path;
}
int main()
{
std::vector<std::vector<int>> grid( 100 , std::vector<int> (100, 0));
{
auto path = find_path(grid, {1, 1}, {98, 98});
}
}