Pathfinding A*

Pathfinding is the computational plotting of the shortest route between two points. A* is a pathfinding graph traversal algorithm widely used all through programming sectors due to its completeness, optimality, and optimal efficiency.

/*!
 * \brief Runs A Star pathfinding algorithm
 * \param start - start position, end - end (target) position
 * \return true if achivable, false otherwise
 */
bool A_Star::Run(const A_Vec2& start, const A_Vec2& end)
{
	//set final and start node
	m_final_node = end;
	m_start_node = start;
	//start node
	A_Node start_node{};
	start_node.m_position = start;
	//push start node to the open list
	// the start cost set by the heuristic function
	float start_cost = GetHeuristic(start_node.m_position);
	//set the initial cost to 0
	start_node.m_cost = 0.0f;
	//accumulative cost
	start_node.m_total = start_cost;
	//check if we can go in straight line (optimization)
	if (m_start_node == m_final_node || (m_straight_line && IsStraightLine(m_start_node, m_final_node))) {
		//push the node to the closed list
		m_closed_list.push_back(start_node);
		//set the predecesor of the node as the position
		start_node.m_parent = start_node.m_position;
		//set the current position of the node to the final (goal) position
		start_node.m_position = m_final_node;
		//push the visited node to the closed list
		m_closed_list.push_back(start_node);
		//since the path was found, then return true.
		return true;
	}
	//since we cant get in a stright line, push start node to the open list.
	pushOpen(start_node);
	//allocate memory for the closed and open list
	m_open_list.reserve(  terrain_width * 2);
	m_closed_list.reserve(terrain_width * 2);
	//loop through the open list until its empty
	while (!m_open_list.empty()) {
		//get the current node to check
		A_Node current_node = popOpen();
		//check if it is the end
		if (current_node.m_position == m_final_node){
			//push last node
			m_closed_list.push_back(current_node);
			//return true, we found a path
			PaintLists();
			return true;
		}
		//check if node is in closed list then we do not visit it again
		if (InClosedList(current_node))
			continue;

		//get neighbour nodes (within terrain bounds)
		const int end_r = ((current_node.m_position.first < terrain_width) ? 1 : 0);
		const int end_c = ((current_node.m_position.second < terrain_width) ? 1 : 0);

		//loop through the neighbour cells
		for (int r = ((current_node.m_position.first < 1) ? 0 : -1); r <= end_r; r++) {
			for (int c = ((current_node.m_position.second < 1) ? 0 : -1); c <= end_c; c++) {
				//to not check current cell
				if (r == 0 && c == 0)
					continue;
				//get neighbour positions
				const int neigh_r = current_node.m_position.first + r;
				const int neigh_c = current_node.m_position.second + c;
				//cehck if wall, do nothing since it is not a viable node
				if (g_terrain.IsWall(neigh_r, neigh_c))
					continue;
				//check if it is diagonal
				const bool is_diagonal = std::abs(c) + std::abs(r) > 1;
				//if there is a wall in the middle of the diagonal, not a valid path
				if (is_diagonal && (g_terrain.IsWall(current_node.m_position.first, neigh_c) ||
					g_terrain.IsWall(neigh_r, current_node.m_position.second)))
					continue;

				//push neighbour to open list
				A_Node neighbour{};
				//set position as row and column in terrain
				neighbour.m_position = { neigh_r, neigh_c };
				//check if node is diagonal (and possible path) and set pertinent cost
				if (is_diagonal)
					neighbour.m_cost = current_node.m_cost + sqrt_2;
				else
					neighbour.m_cost += current_node.m_cost;
				//increase influence cost depending on the terrain cell value
				float influence = 0.0f;
				if (m_analysis)
					influence += g_terrain.GetInfluenceMapValue(neigh_r, neigh_c);
				//calculate heuristic cost
				const float heuristic = GetHeuristic(neighbour.m_position);
				//set up total cost of neighbour's path
				neighbour.m_total = neighbour.m_cost + heuristic + influence;
				//set up path hierarchy
				neighbour.m_parent = current_node.m_position;
				//update cost and path hierarchy if node is already in closed list
				//but current cost is better.
				if (InClosedList(m_position) && m_closed_list[current_node].m_total > neighbour.m_total)
					m_closed_list.erase(m_closed_list.begin() + current_node.m_position);
				//push it to the open list
				pushOpen(neighbour);
			}
		}

		//push current to closed list
		m_closed_list.push_back(current_node);
	}
	//path found 
	return true;
}