dfs.c File Reference

Runs the depth first search algorithm on a maze. More...

#include <stdio.h>
#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include "pathfinding/maze.h"
#include "pathfinding/floodfill.h"
#include "pathfinding/binary_heap.h"
#include "pathfinding/dfs.h"

Include dependency graph for dfs.c:

Functions
void	dfs_depth_first_search (maze_grid_t *p_grid, maze_grid_cell_t *p_start_node, maze_navigator_state_t *p_navigator, floodfill_explore_func_t p_explore_func, floodfill_move_navigator_t p_move_navigator)
	Conducts a depth first search on a maze. More...
bool	dfs_is_all_reachable_visited (maze_grid_t *p_grid, maze_navigator_state_t *p_navigator)
	Checks if all reachable nodes from the navigator's current position has been visisted. More...

Detailed Description

Runs the depth first search algorithm on a maze.

Author

Christopher Kok (chris.nosp@m.@for.nosp@m.celig.nosp@m.htni.nosp@m.ng.xy.nosp@m.z)

Version

0.1

Date

2023-11-18

Copyright

Copyright (c) 2023

Function Documentation

dfs_depth_first_search()

void dfs_depth_first_search	(	maze_grid_t *	p_grid,
		maze_grid_cell_t *	p_start_node,
		maze_navigator_state_t *	p_navigator,
		floodfill_explore_func_t	p_explore_func,
		floodfill_move_navigator_t	p_move_navigator
	)

Conducts a depth first search on a maze.

Parameters

[in]	p_grid	Pointer to the grid.
[in]	p_start_node	Pointer to the start node.
[in,out]	p_navigator	Pointer to the navigator state.
[in]	p_explore_func	Function pointer to explore the current node.
[in]	p_move_navigator	Function pointer to move the navigator.

References maze_grid::columns, maze_grid_cell::coordinates, dfs_is_all_reachable_visited(), maze_grid_cell::is_visited, maze_get_dir_from_to(), maze_nav_modify_walls(), MAZE_NONE, maze_navigator_state::orientation, maze_grid_cell::p_came_from, maze_navigator_state::p_current_node, maze_grid::p_grid_array, maze_grid_cell::p_next, and maze_grid::rows.

Here is the call graph for this function:

dfs_is_all_reachable_visited()

bool dfs_is_all_reachable_visited	(	maze_grid_t *	p_grid,
		maze_navigator_state_t *	p_navigator
	)

Checks if all reachable nodes from the navigator's current position has been visisted.

Parameters

[in]	p_grid	Pointer to the grid.
[in]	p_navigator	Pointer to the navigator state.

Returns

true All reachable nodes have been visited.

false Not all reachable nodes have been visited.

References binary_heap_delete_min(), binary_heap_peek(), binary_heap::capacity, maze_grid::columns, maze_grid_cell::f, maze_grid_cell::g, maze_grid_cell::h, maze_grid_cell::is_visited, binary_heap::p_array, maze_navigator_state::p_current_node, maze_grid::p_grid_array, binary_heap_node::p_maze_node, maze_grid::rows, and binary_heap::size.

Here is the call graph for this function:

Here is the caller graph for this function: