Author Topic: Finished my A* algorithm, but there are some problems...  (Read 6361 times)

0 Members and 1 Guest are viewing this topic.

SciTech02

• Robot Overlord
• Posts: 136
• Life's but a green duck with soy sauce. -MegaHAL
Finished my A* algorithm, but there are some problems...
« on: October 10, 2008, 05:47:39 PM »
Well, I've finally finished it (I've attached the .txt file at the bottom of this post).  Right now, it basically finds it's way from the start cell to the goal cell and prints the map with the path and analyzed cells marked (at least that's what it's supposed to).  It is based primarily on Abe Howell's ER1 mapper: link: http://www.abotics.com/buildit_yourself.htm (it's at the very bottom of the page).  His algorithm is written in Visual Basic, so I tried the best I could to "translate" it into a Python script.

Alright, here's the problem(s).  It treats blocked cells as regular, open cells.  In my program, blocked cells are represented by zeros and open cells are represented by ones (just like Admin's wavefront tutorial).  The original program set up a boolean called "CellStatus", it was true if the cell being analyzed was open and false if it was blocked.  So part of the script looked like this:

IF (CellStatus = false) THEN:
SouthCell:

Basically, the code could be written without a boolean, just by saying: if cell = 0, ignore this cell and jump to south cell (because 0 means it's blocked).  There are no "goto" abilities in Python like there are in Visual Basic or C/C++.  So, I wrote it a little differently:

if map[Ycell][Xcell] != 0:
"analyze cell"

Therefore, a cell that does equal zero will not satisfy the first if condition, will not be analyzed and the program will go to the next if condition for the next cell (skipping the cell that equals zero).  However, this does not happen; it treats each blocked cell as an open cell and I don't know why.

The second and (hopefully) last problem is about parent cells.  In both C++ and Visual Basic versions of this algorithm, parent cells are represented like this:

parent(cell A) = [cell B]

Now, this type of xy variable does not exist in Python, so I made the surrounding cells parent the middle, current cell.  So when a cell with the lowest F score is selected, it is the parent of the four surrounding cells and the next cell with the lowest F score is the parent of it's surrounding cells.  These parent/formerly current cells are put in a list and the map has them marked.  However, when the map is printed, every analyzed cell is marked as a parent cell (so no path is visible).  I think it might have something to do with my heuristics (usually 3 out of 4 surrounding cells have equal F scores, so my program picks the first one it comes across as the next cell to be analyzed), or I may be approaching the selection of parent cells completely wrong, I don't know.

I have tried to figure out how to get around these problems, but I just can't think of anything; so I ask you guys for help.  I also ask for feedback on my code, for it would be most helpful.

SciTech02

EDIT: In the attached code, I typed a '>' instead of a '!=' as I stated above.  I did this because I was trying different methods and I forgot to return the code to its original state.  They both mean the same thing (since unblocked cells have values greater than 0) and both gave unsatisfactory results (treating blocked cells as open cells).
« Last Edit: October 11, 2008, 03:03:17 PM by SciTech02 »
Check out the Evolution Robotics, ER1 robot, and ERSP Resource Page: http://www.societyofrobots.com/member_tutorials/node/336

Ro-Bot-X

• Contest Winner
• Supreme Robot
• Posts: 1,431
• Store: RoBotXDesigns.ca
Re: Finished my A* algorithm, but there are some problems...
« Reply #1 on: October 10, 2008, 06:15:35 PM »
I got the file and I will look over it tonight, but I can't promisse any help since I am not a good programmer. I think you've allready done more than I can do at this time. Anyway, I'll give it a try.

Thanks for sharing, even if it's not completly functional.
Check out the uBotino robot controller!

SciTech02

• Robot Overlord
• Posts: 136
• Life's but a green duck with soy sauce. -MegaHAL
Re: Finished my A* algorithm, but there are some problems...
« Reply #2 on: October 12, 2008, 06:52:55 PM »
UPDATE: I think I fixed the problem with the blocked cells being treated as open cells (my program now ignores cells that are blocked).  Here was the problem; in the code, the if conditions for the surrounding cells look like this:

if map[NcellY][NcellX] != 0 or {cell not in closed list}:                         #This example is for the cell directly above the current cell (the "north" cell)
{analyze cell}

The error was my using the word "or".  This basically made the program analyze any cell that was not on the closed list, regardless if the cell did not equal 0.  I fixed this by replacing "or" with "and"; now both conditions must be true for the cell to be analyzed.

However, I'm still stumped with the parent cell problem; which seems to me almost a language problem (Python does not support xy variables as I said above).  If anyone has suggestions or ideas, I'm listening.
Check out the Evolution Robotics, ER1 robot, and ERSP Resource Page: http://www.societyofrobots.com/member_tutorials/node/336