Estou implementando um algoritmo de localização de caminhos A* em C++ para resolver um labirinto, mas estou encontrando uma falha de segmentação (SIGSEGV) quando o tamanho do labirinto é alto (~10.000x10.000 ou maior).
O erro ocorre na
~__shared_count()funçãoshared_ptr_base.hafternode = queue.top()é chamada na linha 58 e dezenas de~Node()desconstrutores são chamados depois disso.
Editar: O erro realmente ocorre na _Sp_counted_base<_S_atomic>::_M_release()função agora, embora eu não saiba o que mudei.
Aqui estão as partes do meu código que devem ser relevantes. Sou novo no uso de ponteiros compartilhados, então não tenho certeza de qual é o problema ou como corrigi-lo.
principal.cpp
#include <iostream>
#include <queue>
#include <random>
#include <vector>
#include <algorithm>
#include <stack>
#include <fstream>
#include "Node.hpp"
constexpr uint16_t maze_size = 10000;
void solve(const uint16_t start_x, const uint16_t start_y, const uint16_t goal_x,
const uint16_t goal_y,
const std::vector<std::vector<std::pair<bool, bool> > > &walls) {
std::vector<std::vector<bool> > visited(maze_size, std::vector<bool>(maze_size, false));
// Min heap for our queue
std::priority_queue<Node, std::vector<Node>, std::greater<> > queue;
Node node(start_x, start_y, goal_x, goal_y);
visited[node.x][node.y] = true;
while (!node.solved(goal_x, goal_y)) {
// Add all valid neighbors to the queue
{
const auto x = node.x;
const auto y = node.y;
const auto ptr = std::make_shared<Node>(node);
// Right
if (x < maze_size - 1 && !walls[x][y].first && !visited[x + 1][y]) {
queue.emplace(x + 1, y, goal_x, goal_y, ptr);
visited[x + 1][y] = true;
}
// Left
if (x > 0 && !walls[x - 1][y].first && !visited[x - 1][y]) {
queue.emplace(x - 1, y, goal_x, goal_y, ptr);
visited[x - 1][y] = true;
}
// Down
if (y < maze_size - 1 && !walls[x][y].second && !visited[x][y + 1]) {
queue.emplace(x, y + 1, goal_x, goal_y, ptr);
visited[x][y + 1] = true;
}
// Up
if (y > 0 && !walls[x][y - 1].second && !visited[x][y - 1]) {
queue.emplace(x, y - 1, goal_x, goal_y, ptr);
visited[x][y - 1] = true;
}
}
node = queue.top();
queue.pop();
}
}
Nó.hpp
#ifndef NODE_HPP
#define NODE_HPP
#include <cstdint>
#include <memory>
class Node {
public:
uint16_t x, y;
uint32_t steps;
uint32_t value;
std::shared_ptr<Node> parent;
Node(const uint16_t x, const uint16_t y, const uint16_t goal_x, const uint16_t goal_y,
const std::shared_ptr<Node> &parent = nullptr) : x(x), y(y), parent(parent) {
steps = parent ? parent->steps + 1 : 0;
value = abs(static_cast<int32_t>(goal_x) - static_cast<int32_t>(x)) +
abs(static_cast<int32_t>(goal_y) - static_cast<int32_t>(y)) +
steps;
}
[[nodiscard]] bool solved(const uint16_t goal_x, const uint16_t goal_y) const {
return x == goal_x && y == goal_y;
}
// Overload the > operator for the priority queue
bool operator>(const Node &rhs) const {
if (value == rhs.value) {
return steps < rhs.steps;
}
return value > rhs.value;
}
};
#endif
Saída Valgrind
valgrind --leak-check=full ./Tests
==5385== Memcheck, a memory error detector
==5385== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==5385== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==5385== Command: ./Tests
==5385==
Maze loaded10000
==5385== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5385==
==5385== Process terminating with default action of signal 11 (SIGSEGV)
==5385== Access not within mapped region at address 0x1FFE801FF8
==5385== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5385== at 0x116230: std::_Sp_counted_ptr_inplace<Node, std::allocator<void>, (__gnu_cxx::_Lock_policy)2>::_M_dispose() (shared_ptr_base.h:613)
==5385== If you believe this happened as a result of a stack
==5385== overflow in your program's main thread (unlikely but
==5385== possible), you can try to increase the size of the
==5385== main thread stack using the --main-stacksize= flag.
==5385== The main thread stack size used in this run was 8388608.
==5385==
==5385== HEAP SUMMARY:
==5385== in use at exit: 239,026,864 bytes in 556,422 blocks
==5385== total heap usage: 3,380,473 allocs, 2,824,051 frees, 374,594,816 bytes allocated
==5385==
==5385== LEAK SUMMARY:
==5385== definitely lost: 0 bytes in 0 blocks
==5385== indirectly lost: 0 bytes in 0 blocks
==5385== possibly lost: 0 bytes in 0 blocks
==5385== still reachable: 239,026,864 bytes in 556,422 blocks
==5385== suppressed: 0 bytes in 0 blocks
==5385== Reachable blocks (those to which a pointer was found) are not shown.
==5385== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==5385==
==5385== For lists of detected and suppressed errors, rerun with: -s
==5385== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)
Você poderia tentar reproduzir o erro usando a seguinte função para carregar este arquivo labirinto . Desculpe pelo tamanho. Você pode carregá-lo usando esta função:
std::vector<std::vector<std::pair<bool, bool> > > readVectorFromFile(const std::string &filename) {
std::vector<std::vector<std::pair<bool, bool> > > vec;
std::ifstream inFile(filename, std::ios::binary);
if (!inFile) {
std::cerr << "Error opening file for reading: " << filename << std::endl;
return vec;
}
// Read the size of the outer vector
size_t outerSize;
inFile.read(reinterpret_cast<char *>(&outerSize), sizeof(outerSize));
vec.resize(outerSize);
for (auto &innerVec: vec) {
// Read the size of each inner vector
size_t innerSize;
inFile.read(reinterpret_cast<char *>(&innerSize), sizeof(innerSize));
innerVec.resize(innerSize);
// Read each pair in the inner vector
for (auto &pair: innerVec) {
inFile.read(reinterpret_cast<char *>(&pair.first), sizeof(bool));
inFile.read(reinterpret_cast<char *>(&pair.second), sizeof(bool));
}
}
inFile.close();
return vec;
}
O principal seria algo como:
int main() {
auto walls = readVectorFromFile("maze.dat");
std::cout << "Maze loaded" << std::endl;
solve(0, 0, maze_size - 1, maze_size - 1, walls);
return 0;
}