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.

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.

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

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

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

possible output:

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

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>>

what happens:

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

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.

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:

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 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:

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