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.

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.

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.