A* Pathfinding

This module was developed to determine the shortest, (i.e. the fastest) path from a to b on a two-dimensional playing field called maze. A distinction is made between walkable and non-walkable paths. For the representation of a maze a two nested vector is used.

How does the A* - Algorithm works?

It is started with the help of a specified labirynth and a start and end node, of which only the position is known at the beginning of the runtime. Now all possible paths around this node are examined, and these then again just like the start node until a node arrives at the position of the end node. Then the fastest possible way from start to end is explored, i.e. the best node to go, and then output.

why the A*-Algorithm is extremely fast:

The path problem is solved as quickly as possible by calculating a score from the estimated distance and the sum of paths already taken, which is used to prioritize the order in which the neighbor nodes are investigated. This also has the effect that A* always knows in which direction the end node is and therefore does not first examine the neighbor away from it, but first all fast paths.

The formula used for this is:

f(n) = g(n) + h(n)

---

n

is the Node Object itself

---

g(n)

Is the estimate of how far n is from the end node

(current_cell.x – goal.x)^2 + (current_cell.y – goal.y)^2

---

h(n) Is the number of travelled path units from the start node to the current position of n

---

f(n) the sum of both g(n) and h(n)

is a score value with which we select and examine from different nodes the one with the best score, with the greatest probability of being the fastest path, which makes the code much faster, because otherwise the graph would not look like above, but like this:

much slower search,
because the algorith has no clue,
in which direction to go first,
so it goes in each direction with
the same priority

---

Example:

############################### -----------------------------------> ###############################
#a  #   # #         #   #     # -----------------------------------> #s++#   # #++++++++#   #     #
### # ### # ####### # ### ##### -----------------------------------> ###+# ### #+#######+# ### #####
# #       # #     #     # #   # -----------------------------------> # #+++++++#+#     #+++  # #   #
# ##### # # ##### ### ### ### # -----------------------------------> # ##### #+#+##### ###+### ### #
#   # # #     #         # #   # -----------------------------------> #   # # #+++  #    +++  # #   #
### # # ### ####### ##### # ### -----------------------------------> ### # # ### #######+##### # ###
#   #   # #     #           # # -----------------------------------> #   #   # #     #  +++++++  # #
# ### ### ### # ### ##### ### # -----------------------------------> # ### ### ### # ### #####+### #
#       #   # # #   #         # -----------------------------------> #       #   # # #   #    +++  #
### ####### ### ########### # # -----------------------------------> ### ####### ### ###########+# #
#   #       # #   # # #     # # -----------------------------------> #   #       # #   # # #  +++# #
### # ### # # # ### # # # ### # -----------------------------------> ### # ### # # # ### # # #+### #
#       # # # #       # # # # # -----------------------------------> #       # # # #       # #+# # #
# # ##### # # ##### # ### # ### -----------------------------------> # # ##### # # ##### # ###+# ###
# #     # # #   #   # #   #   # -----------------------------------> # #     # # #   #   # #  +#   #
### ######### ### ####### # ### -----------------------------------> ### ######### ### #######+# ###
#   #   # #   #   #   # #     # -----------------------------------> #   #   # #   #   #   # #+++++#
# ### # # # ##### ### # ##### # -----------------------------------> # ### # # # ##### ### # #####+#
#     #         #           #b# -----------------------------------> #     #         #           #g#
############################### -----------------------------------> ###############################

---

included Features

AStarResult - Class

---

The main AStar() function returns a AStarResult class-object, which provides

• whole path went
• the total amount of moves done
• print out the hole maze

AStar-Pathfinding-Cpp/examples/prepare_maze.cpp

Lines 43 to 55 in f803f8a

	// returns AStarResult Class
	AStarResult result = AStar(prepare_maze(maze), start, end);
	// returns min movements made to get from start_node to end_node
	cout << "A* made " << result.movements << " moves to reach (" <<
	end[0] << ", " << end[1] << ")"
	<< " from (" << start[0] << ", " << start[1] << ")\n";
	// prints out the whole maze with drawn path
	result.print_maze_solution_path();
	// .path_went variable contains the path went by the fastest node
	vector<pos_type> went_path = result.path_went;

possible output:

A* made 64 moves to reach (19, 29) from (1, 1)
###############################
#s+++++++   # +++       #     #
#  #### +#  # +#+ #  ####  ####
#       +#  # +#++++ #        #
#  #### +#### +#  #+ #######  #
#     # +++++++#  #++++ #  #  #
######################+ #  ####
#  #                 #+       #
#  #######  ####  ####+ #  #  #
#  #     #  #        #+ #  #  #
#  #  #  #  #######  #+ #  #  #
#  #  #        #      + #  #  #
#  #  #  #######  ####++#######
#     #        #  #    ++++++ #
#  ####  #  #  #  #  #######+ #
#  #     #  #  #  #  #  #  #+ #
#  ##########  #  #  #  #  #+ #
#           #  #  #  # ++++++ #
#  #######  ########## +#######
#        #           # ++++++g#
###############################

prepare_maze - function

---

The prepare function converts a maze consisting out of
barriers (f.ex. '#') and walkable terrain (f.ex. ' ')
is converted to a maze out of zeroes and ones,
the ones represent the not walkable terrain and the zeroes the walkable terrain by default.

All this settings could be adjusted in the #define statements at the beginning of this package.

This is because AStar() needs this 2-dimensional vector
to figure out wheather its a walkable or not walkable terrain.

prepare_maze() can handle a vector<string> or vector<vector<char>>

AStar-Pathfinding-Cpp/examples/prepare_maze.cpp

Lines 7 to 32 in 6bf0d47

	vector<string> maze = {
	"###############################",
	"#a # # #",
	"# #### # # # # #### ####",
	"# # # # # #",
	"# #### #### # # ####### #",
	"# # # # # # #",
	"###################### # ####",
	"# # # #",
	"# ####### #### #### # # #",
	"# # # # # # # #",
	"# # # # ####### # # # #",
	"# # # # # # #",
	"# # # ####### #### #######",
	"# # # # #",
	"# #### # # # # ####### #",
	"# # # # # # # # # #",
	"# ########## # # # # # #",
	"# # # # # #",
	"# ####### ########## #######",
	"# # # b#",
	"###############################"
	};
	// prepare maze to be able to pass it into AStar()
	vector<vector<int>> prepared_maze = prepare_maze(maze);

what happens:

########## -----> 1111111111
#        # -----> 1000000001
# ##### ## -----> 1011111011
# ##    ## -----> 1011000011
# ##  #### -----> 1011001111
# ###    # -----> 1011100001
#  #  ## # -----> 1001001101
###  ##  # -----> 1110011001
##  ##  ## -----> 1100110011
########## -----> 1111111111

---

find_obj - function

find_obj finds an character out of a maze in ascii format,
such as vector<string> or vector<vector<char>>
and returns a vector<int> with the (x, y) position of the character into the maze.

This is usefull to figure out the start and ends position in your maze,
so that you can pass this info into Astar(), which needs the position
of the start and end node at second and third position like findobj() returns it for you.

AStar-Pathfinding-Cpp/examples/prepare_maze.cpp

Lines 36 to 44 in 8488ab5

	vector<int> start = findobj(maze, 'a');
	vector<int> end = findobj(maze, 'b');
	// returns AStarResult Class
	AStarResult result = AStar(prepare_maze(maze), start, end);

---

readmaze - function

readmaze reads in a maze from the consoles cin stream,
the first line must consist of two integers that indicate the height and width of the mazes to be read in.
In the following you can pass in the maze like this:

    10 10        // first 10 = m = rows, second 10 = n = columns
    ##########
    #        #
    # ##### ##
    # ##    ##
    # ##  ####
    # ###    #
    #  #  ## #
    ###  ##  #
    ##  ##  ##
    ##########

readmaze converts this directly to the maze format by calling the prepare_maze - function,
which AStar() needs,
so in the numeric one:

    1111111111
    1000000001
    1011111011
    1011000011
    1011001111
    1011100001
    1001001101
    1110011001
    1100110011
    1111111111

so you can pass in the return value vector<vector<int>> directly into the AStar - function:

AStar-Pathfinding-Cpp/examples/readmaze.cpp

Lines 10 to 16 in 44eef83

	// read in maze from the console
	vector<vector<int>> maze = readmaze();
	// returns AStarResult Class
	AStarResult result = AStar(maze, pos_type{1, 1}, pos_type{5, 5});

the disatvantage here is, that because readmaze converts the ascii maze into a numeric one at one time,
you must know the start and end position before,
you would hardcode them,
but that's probably not, what you want.

So theres the pardon readunpreparedmaze presented in the following.

---

readunpreparedmaze - function

readunpreparedmaze does the same thing like readmaze in general,
but does not already convert it into a numeric vector,
but into a ascii one.

you'll get returned the following:

    ##########
    #a       #
    # ##### ##
    # ##    ##
    # ##  ####
    # ###    #
    #  #  ## #
    ###  ##  #
    ##  ## b##
    ##########

which makes it possible to find objects into this vector<srting> which is returned with the findobj - function, like shown here:

AStar-Pathfinding-Cpp/examples/readunpreparedmaze.cpp

Lines 10 to 21 in f756a92

	// read in maze from the console, but not directly convert it into a numeric maze
	vector<vector<int>> maze = readunpreparedmaze();
	/* because it's not already been converted into a numeric maze,
	* you can get the position by finding chars here and don't need to know (and hardcode)
	* the start and end position before
	* */
	pos_type start_pos = findobj(maze, 'a');
	pos_type end_pos = findobj(maze, 'b');
	// returns AStarResult Class
	AStarResult result = AStar(prepare_maze(maze), start_pos, end_pos);

note, that you need to convert this maze with prepared_maze() manully, before passing it into AStar()

With that being said, have fun with it!

© Copyright by LukeProducts