anyone has a good C example of simple A* search

[legacy]

hi guys
today i am toying with robotics and the dish of day is "path planning". As far as i have understood, in order to perform path planning you'd better go for so called "A star search", which was a common LISP research task in '80.

here it is a python example of "ecursivity-and-a-search" in where the A* algorithm has been implemented to solve a(n amazing) maze with the specific extra goal of choosing the less expensive path (yeah you can also have learn you have to define the "cost", what is cost ? what evil are you talking about ? guessing about that, i have  been thinking that robot use chemical energy to move, so from the point of view of the battery it may be that the less the robot takes moves the better and the the most far it goes).

Anyway, i hope you enjoy this article, and .. personally i am looking for something similar written in C.



edit:
thread title mixup: "anyone has a good C example of simple A* search (recursivity approach)"

[legacy]

Wiki, about A*_search_algorithm

[senso]

If there is also mapping involved, also consider SLAM.

[iceisfun]

I have some C implementations of this but I would have to dig around in old archives, look in game engines that have been open sourced and you will find them.


However I recommend implementing it yourself to help with understanding it, there are a few key building blocks you will need

Node list with connected neighbours and possibly a traversal cost
Method of moving nodes between open and closed list
Method of sorting the open list based on distance from goal

Once you have those building blocks this task is pretty easy to get going, I suggest doing it in C# first while you understand and debug it instead of fighting against C issues unless your good with C.

If you need specific help with part of the A* search ask and I can help.


BTW : Recursion is usually the wrong approach, more often something like while(Node != Dest) { ... } then Walk back up list and assemble a path but within one or a few functions but not recursive, the depth of a search can grow quite large depending on the graph.

[legacy]

thank you for your help =)

what game's sources should i look at ? any example ?

C is not a problem for me.


i have implemented a sub optimal search, recursive approach conditioned by an heuristic function which tries to estimate the distance to the goal-exit, it suggests choices -what to do next-

'I' entrance
'O" exit
'.' visited cell
'@' dead lock reached (it should not happen with the new approach i am using)
' ' free space not visited

Code: [Select]

     |0123456789012345678
   0:|######### #########|
   1:|#       #I#       #|
   2:|#                 #|
   3:|#     #######     #|
   4:|#                 #|
   5:|#       # #       #|
   6:|#       #O#       #|
   7:|###################|

     |0123456789012345678
   0:|######### #########|
   1:|#.......#O#OO.....#|
   2:|#........OOOOO....#|
   3:|#.....#######O....#|
   4:|#........OOOOO....#|
   5:|#.......#O#.OO....#|
   6:|#.......#O#.OO....#|
   7:|###################|


Code: [Select]

     |0123456789012345678
   0:|######### #########|
   1:|#       #I#       #|
   2:|#                 #|
   3:|#                 #|
   4:|#       # #       #|
   5:|#       #        O#|
   6:|###################|

     |0123456789012345678
   0:|######### #########|
   1:|#       #O#       #|
   2:|#        O        #|
   3:|#        O        #|
   4:|#       #O#       #|
   5:|#       #OOOOOOOOO#|
   6:|###################|


Code: [Select]

     |0123456789012345678
   0:|######### #########|
   1:|#       #I#       #|
   2:|#         #  #  # #|
   3:|# #########  #### #|
   4:|# #          #    #|
   5:|#       # #  # # O#|
   6:|###################|

     |0123456789012345678
   0:|######### #########|
   1:|#       #O# OOOOOO#|
   2:|#OOOOOOOOO#OO#  #O#|
   3:|#O#########OO####O#|
   4:|#O#....OOOOOO#  OO#|
   5:|#OOOOOOO#.#OO# #OO#|
   6:|###################|


Code: [Select]

     |0123456789012345678
   0:|######### #########|
   1:|#   # ## I ## #   #|
   2:|# #   #     #   # #|
   3:|# ##### # # ##### #|
   4:|#        O        #|
   5:|# ##### # # ##### #|
   6:|# #   #     #   # #|
   7:|#   # ##   ## #   #|
   8:|###################|

     |0123456789012345678
   0:|######### #########|
   1:|#   # ##.O.##.#...#|
   2:|# #   #OOOOO#...#.#|
   3:|# #####O#O#O#####.#|
   4:|#      OOOOO......#|
   5:|# ##### #O#O#####.#|
   6:|# #   #  OOO#...#.#|
   7:|#   # ##   ##.#...#|
   8:|###################|


Code: [Select]

/*
 * circular issue, wrong method
 *
 * XXXXXXXXXIXXXXXXXXX
 * X...X.XX@@@XX.X...X
 * X.X...X@@ @@X...X.X
 * X.XXXXX@X X@XXXXX.X
 * X......@ O @......X
 * X.XXXXX@X X@XXXXX.X
 * X.X...X@@ @@X...X.X
 * X...X.XX@@@XX.X...X
 * XXXXXXXXXXXXXXXXXXX
 */



New heuristic method

Code: [Select]

     |0123456789012345678
   0:|###################|
   1:|#   # ## I ## #   #|
   2:|# #   #     #   # #|
   3:|# ##### # # ##### #|
   4:|#        O        #|
   5:|# ##### # # ##### #|
   6:|# #   #     #   # #|
   7:|#   # ##   ## #   #|
   8:|###################|

     |0123456789012345678
   0:|###################|
   1:|#   # ## O ## #   #|
   2:|# #   #  O  #   # #|
   3:|# ##### #O# ##### #|
   4:|#        O        #|
   5:|# ##### # # ##### #|
   6:|# #   #     #   # #|
   7:|#   # ##   ## #   #|
   8:|###################|


[legacy]

Node list with connected neighbours and possibly a traversal cost

this part is not well understood for me, how to create the tree ?

[legacy]

To handle the connection between nodes i have thought about using a matrix

so a an extreme easy maze like this

Code: [Select]

     |01234
   0:|#####|
   1:|## ##|
   2:|#   #|
   3:|## ##|
   4:|#####|

looks this way

nodes, and their relations, considering 1 step of movement (up, down, left, right)

Code: [Select]

id0, (2, 1)
id1, (1, 2)
id2, (2, 2)
id3, (3, 2)
id4, (2, 3)
id0->id2 (   2,    1)->(   2,    2) down
id1->id2 (   1,    2)->(   2,    2) right
id2->id0 (   2,    2)->(   2,    1) up
id2->id1 (   2,    2)->(   1,    2) left
id2->id3 (   2,    2)->(   3,    2) right
id2->id4 (   2,    2)->(   2,    3) down
id3->id2 (   3,    2)->(   2,    2) left
id4->id2 (   2,    3)->(   2,    2) up

movement matrix

Code: [Select]

    |01234
   0|..D..
   1|..R..
   2|UL.RD
   3|..L..
   4|..U..

It appears to me that this information grows up too much

[IanB]

To help code your solution, it may help to write down your maze solving algorithm in English first.

For example:

A maze solution is any sequence of paths that starts at an entrance and finishes at an exit.

A path begins at any point (cell) where there are two or more directions to follow (a fork in the road).

A path finishes at any point meeting one of the following conditions:
1. It reaches a dead end
2. It reaches a point where new paths diverge
3. It reaches a point (cell) already visited
4. It reaches an exit

To solve a maze:

Follow all paths not already followed, backtracking as necessary.
Eliminate any paths that reach a point where there are no new paths to follow.
Continue until a path is found that reaches an exit.

[iceisfun]

In the case of a flat X,Y grid the adjacent cells are easy to find, many games device a non-uniform node list that requires each node to maintain a list of connected nodes such as a map in a 3d game might go up and down or in a long straight hall way.

On your flat X,Y grid you can assume that each adjacent cell that is not blocked is connected and has a weight of either 1 or sqrt(2) for corners, if you want your path to prefere to go straight instead of taking angles just tweak these weights so going at a angle is more expensive (a longer path) and the algorithm will tend to go to the left, right up and down as these paths will appear "shorter"

Most of the game samples I have are in C++ or C# and now I've scrapped most of my stuff in favor of Recast which is a full featured nav mesh system written in C++ ( https://github.com/memononen/recastnavigation ) for pathing in 3D environments.

Can you post your code?

[iceisfun]

I've been digging for a while now and the only c like implementation I have has a bug, I can't find the cleaned up version.

[legacy]

which bug is it ?


and what do you think about combining the "BelmanFord minimal path finder", a typical algorithm used at the mac level of internet working devices (e.g. routers), with the cross matric which describes the maze ?

here it is an example of a BelmanFord implementation i did in C at my university (as homework), his cross matrix is described as "cost" with the meaning of "how does it cost  to reach node A[j] from node A thought path[k]"

Code: [Select]

[!] show
   A  B  C  D  E  F  G 
A  *  9  -  -  3  -  -
B  9  *  2  -  1  9  -
C  -  2  *  1  1  -  -
D  -  -  1  *  -  3  2
E  3  1  1  -  *  9  -
F  -  9  -  3  9  *  4
G  -  -  -  2  -  4  *
[!] cover_tab show
source = A
node:  from   cost  path
  A:    A      -
  B:    E      4    AEB
  C:    E      4    AEC
  D:    C      5    AECD
  E:    A      3    AE
  F:    D      8    AECDF
  G:    D      7    AECDG
[!] cover_tab show
source = B
node:  from   cost  path
  A:    E      4    BEA
  B:    B      -
  C:    E      2    BEC
  D:    C      3    BECD
  E:    B      1    BE
  F:    D      6    BECDF
  G:    D      5    BECDG
[!] cover_tab show
source = C
node:  from   cost  path
  A:    E      4    CEA
  B:    E      2    CEB
  C:    C      -
  D:    C      1    CD
  E:    C      1    CE
  F:    D      4    CDF
  G:    D      3    CDG
[!] cover_tab show
source = D
node:  from   cost  path
  A:    E      5    DCEA
  B:    E      3    DCEB
  C:    D      1    DC
  D:    D      -
  E:    C      2    DCE
  F:    D      3    DF
  G:    D      2    DG
[!] cover_tab show
source = E
node:  from   cost  path
  A:    E      3    EA
  B:    E      1    EB
  C:    E      1    EC
  D:    C      2    ECD
  E:    E      -
  F:    D      5    ECDF
  G:    D      4    ECDG
[!] cover_tab show
source = F
node:  from   cost  path
  A:    E      8    FDCEA
  B:    E      6    FDCEB
  C:    D      4    FDC
  D:    F      3    FD
  E:    C      5    FDCE
  F:    F      -
  G:    F      4    FG
[!] cover_tab show
source = G
node:  from   cost  path
  A:    E      7    GDCEA
  B:    E      5    GDCEB
  C:    D      3    GDC
  D:    G      2    GD
  E:    C      4    GDCE
  F:    G      4    GF
  G:    G      -


[legacy]

A good pathfinder example.

[legacy]

UP 

[Bored@Work]

UP 

What did you, yes YOU do the last few days, besides posting "UP"?

[legacy]

last few days ? i have been implementing algorithm (1) in C 
but my previous questions are still without answers.


(1)

[legacy]

Also found this (aStarTutorial)

[legacy]

interesting python code, designed following the previous (1) flowchart

Code: [Select]

def process(self):
    # add starting cell to open heap queue
    heapq.heappush(self.op, (self.start.f, self.start))
    while len(self.op):
        # pop cell from heap queue
        f, cell = heapq.heappop(self.op)
        # add cell to closed list so we don't process it twice
        self.cl.add(cell)
        # if ending cell, display found path
        if cell is self.end:
            self.display_path()
            break
        # get adjacent cells for cell
        adj_cells = self.get_adjacent_cells(cell)
        for c in adj_cells:
            if c.reachable and c not in self.cl:
                if (c.f, c) in self.op:
                    # if adj cell in open list, check if current path is
                    # better than the one previously found for this adj
                    # cell.
                    if c.g > cell.g + 10:
                        self.update_cell(c, cell)
                else:
                    self.update_cell(c, cell)
                    # add adj cell to open list
                    heapq.heappush(self.op, (c.f, c))


[legacy]

From the above python code it appears to me one condition is missing: what happens if It reaches a dead end ?
More specifically when the adjacent list is empty: you have to roll back your solution to the first one cell in the open list, than start a new search.

Code: [Select]


######### #########
#       #I#       #
#        |        #
#        |/---->-\#
#       #|#      |#
#       #x#      O#
###################
 
x is dead end


[legacy]

More reading, may be interesting: here it is an article about "toward more realistic pathfinding"

[legacy]

Recast which is a full featured nav mesh system written in C++

too complicated

Can you post your code?

still proof version, very very proof. In the previous examples i used a recursivity approach, which is working but it is not the best approach at all.

[legacy]

If there is also mapping involved, also consider SLAM.

any good teaching stuff around ?

[legacy]

what do you think about "wave-front" ?

[legacy]

Code: [Select]


     |0123456789012345678
   0:|###################|
   1:|#   # ## I.## #   #|
   2:|# #   #    .#   # #|
   3:|# #  #      .#  # #|
   4:|# #  #  ### .#  # #|
   5:|# #  #      .#  # #|
   6:|# #   #    .#   # #|
   7:|# ##### ###.##### #|
   8:|#          .      #|
   9:|#          .      #|
  10:|#          .      #|
  11:|#          .      #|
  12:|#          .      #|
  13:|#          .      #|
  14:|#          .      #|
  15:|#          .      #|
  16:|#          .      #|
  17:|#          .      #|
  18:|# ######  . #######|
  19:|# #   #  .  #   # #|
  20:|# #  #  .    #  # #|
  21:|# #  #   .   #  # #|
  22:|# #  #   O   #  # #|
  23:|# #   #     #   # #|
  24:|#   # ### ### #   #|
  25:|###################|

Improvement 

[legacy]

Also Vector Field Histogram (VFH) Method is using A*!
Nice to know!