How to store best route using A*

This is a discussion on How to store best route using A* within the C++ Programming forums, part of the General Programming Boards category; Hello, I have create my first A* algorithm with uses an open list and then selects the cell with the ...

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

    Smile How to store best route using A*

    Hello,

    I have create my first A* algorithm with uses an open list and then selects the cell with the lowest proposed distance, opening more cells to the open list.

    My problem is I don't know the best method to ensure only the best route is kept (in a stack/array?) Please view the video below and you can see how the alogrithm is currently working. The green squares are closed visited cells and the purple cells are on the open list.

    YouTube - Fire Simulation 3

    Many thanks

  2. #2
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438

    The straight and narrow

    If u hav read up on a* then u will kno the best path is found by backtracing the parent squares, if you hav the search implementd correctly then u hav only t do the backtrace function, p.s a hint is it can b done in a console, bin that hokey 3d till then

  3. #3
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    I just mean to say i kno the 3d thing is an app you are using, and if you are having trouble wit the algorithm i dont think it helps to implement straight off in a graphics environment, its just gloss, the important stuff is always behind scenes
    Last edited by rogster001; 12-12-2009 at 03:54 PM.

  4. #4
    Registered User
    Join Date
    Nov 2009
    Posts
    8
    don't you like the 3D environment 007?

  5. #5
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    Quote Originally Posted by pawikan View Post
    don't u like the 3D environment 007?
    mate,its magictastic, but u said its not yours and i am trying t say t you watch your model work in memory,on your own machine,get it right n after add all the whistles an bells u like
    Last edited by rogster001; 12-12-2009 at 04:23 PM.

  6. #6
    Registered User
    Join Date
    Nov 2009
    Posts
    8
    Thanks 007, your suggestions have been really good and I have now managed to complete what I originally set out to achieve thank you! - could you show me what your screens look like when you program something like this without showing it graphically?

    I have now coded the requirement to search through the parent cells by backtracking

    I have noticed that when extra weighting is placed on diagonal movements, it seems to have more of a direct route, although in the final room (in the video) it seems less efficient. Whereas, when all movements are equal (the first part of the movie) there is a point in the 2nd room that is inefficient due to trying to go diagonally, although in the final 3rd room it seems more efficient that the using weighting. - is this a known issue with A*?

    YouTube - Fire Simulator 4
    Last edited by pawikan; 12-13-2009 at 06:41 AM.

  7. #7
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    well done eh, i hated the parent square bit, that was defintely the hardest part for me making a sensible function to output the final path, i want to return to it and do the most stripped down version i can create sometime, did you use an object orientated approach or traditional arrays or a mixture? i say this as i did both ways but found the non OO version much better, i sure there is a good case for doing a version like that though. especially when you consider multiple units eventually.

    I think if you check the article A* Pathfinding for Beginners it explains a bit about the treatment of diagonals.
    Also i dont know if you can easily do this in your graphics environment but it is very useful for testing if you can repeatedly generate random maps, and also test with masses of obstacles as well as no obstacles, you need to see if your search is crashing when there is no path available (it should be able to deal with such cases) and also repeatedly doing random maps will let you spot how well your search is working, sometimes you will see it make an odd move thats makes you realise something not right.
    My version i sat there for ages clicking on the screen over and over getting new maps till my eyes went square following it haha.

    Its also good while testing to colour your search so you can see it working before the actual backtrace and showing the final route.

    this is good for testing no path scenarios as you should see the search balloon outwards and fill the map as far as it can.
    Last edited by rogster001; 12-14-2009 at 04:46 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 03:55 AM
  2. Free Store of memory
    By George2 in forum C++ Programming
    Replies: 6
    Last Post: 11-12-2007, 02:27 PM
  3. store data from ifstream and store in link list
    By peter_hii in forum C++ Programming
    Replies: 2
    Last Post: 10-26-2006, 09:50 AM
  4. Do you store store one off data arrays in a class?
    By blood.angel in forum C++ Programming
    Replies: 5
    Last Post: 06-24-2002, 01:05 PM
  5. how to store a node on hard disk
    By ALLRIGHT in forum C Programming
    Replies: 3
    Last Post: 05-13-2002, 11:11 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21