# Thread: How to store best route using A*

1. ## 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. ## 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. 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

4. don't you like the 3D environment 007?

5. Originally Posted by pawikan
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

6. 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

7. 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.

Popular pages Recent additions