Thread: Implementation of path finder algorithm in C

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    37

    Implementation of path finder algorithm in C

    Hey all,

    I'm looking for a C implementation of the Lee path algorithm. It has to satisfy the following:
    * The algorithm is to work inside a two dimensional space
    * From each point, one can only traverse to the next point in four directions; up, down, left, right
    * Points can only be either blocked or nonblocked, only nonblocked points can be traversed

    Basically on a 2D rectangular grid, there can be any number for blocks (one block per x-y position). The path from one block to another must be found. The end result is that the algorithm must find the shortest path from one block to another (source and goal).

    It gets a little more complicated in that a given source A can connect to multiple goals B C D and so on. That is to say within a given path (whether already found or not) there are "sub-paths". Sort of like a highway that has multiple lanes. Several cars starting from the same point (source) can reach different destinations (goal) by choosing a lane which corresponds to a desired exit. For example, from source A we can use lane A to connect to goal B; lane B to goal C; lane C to goal B.

    I understand the main idea behind it. We have to expand out from the source to the goal, and then trace back to the start, the path that has the smallest cost function. It is also a requirement that we should not waste time with expanding from the source in all directions, instead we should use some sort of predictor to somehow narrow our expansion.

    C is my first programming and I very recently started to learn it. Now I understand that I wont be given code in its entirety. But I am just so confused on where to begin. There are so many requirements. I would appreciate any design hints you are willing to share.

    Thank you.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I would take this time to read up on Lee's algorithm on Wikipedia (if it's there), and Google it as well.

    Your main idea sounds too vague to put into pseudo code, let alone a program, just yet.

    We can assist you with the code portion (most generally), but you need to know the algorithm, and give it a starting code portion, at least. Be ready to ask specific questions and provide specific answers.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Lee's is basically a flood fill.
    Code:
    here =  start = 1
        while here is not the exit
            for each open move
                open move = here + 1
    It looks something like this:
    Code:
    #A##########
    #BCDEFGHIJK#
    #C########L#
    #D#LMNOPQ#M#
    #E#K####R#N#
    #F#J####S#O#
    #GHI##VUT#P#
    ######W#UVQR
    ############
    Here, the green path is the shortest to the exit (green-R). Assuming that both paths are being processed at the same time (it makes the two C marks at the same time, then the two D marks, etc), you can see that it would hit green-R (the exit in the lower right) long before the other path would have completed. Were you to let it keep running, red-V to green-Q would be red W, and instead of green-R, red-X would be the exit.

    So, what you end up doing is backtracking by simply moving from the exit to whatever neighbor has the lowest value. R to Q, Q to P and so on. Whatever value the exit has (in this case R, is the length of the shortest path.

    Do this for every sub block. Then store their values in a grid corresponding to the sub-block's location:
    Code:
    SEBGLP
    DKWXIG
    DSWGFX
    RSVPOK
    Move from the S in the upper left to the K in the lower right using the shortest sum possible. At least that sounds to me like what you're trying to do.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Buidl Library with ./configure script
    By Jardon in forum C Programming
    Replies: 6
    Last Post: 07-24-2009, 09:36 AM
  2. Shortest path algorithm with a maximum number of edges limit
    By blackslither in forum C Programming
    Replies: 4
    Last Post: 12-28-2008, 04:49 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM