Path finding
BlitzMax Forums/BlitzMax Beginners Area/Path finding
| ||
| Hi, I'm not great with path finding, but am looking to use A* on a tile based map, however there is a specific thing I need to do. When I select a unit within the map I need it to display all possible tiles where the unit could move to such as in this image: GREEN is the unit. RED is all possible destination tiles  I am presuming A* would be the best possible solution but was hoping maybe someone could point me the the right direction) |
| ||
| A* would be fine. You would need to scan every edge tile your map with your pathfinder. |
| ||
| Hello. For this behavior are more apropiate use amplitude search. First expand each node in each level. Bye, Paposo |
| ||
| @paposa Many thanks i'll look at this now |
| ||
| Sorry, dont suppose you can point me to any online resources or info on this kind of path finding as i cant seem to find alot of info? |
| ||
| http://www.blitzbasic.com/Community/posts.php?topic=76448 |
| ||
| @ Vilu - thanks but i ment for Paposo's suggestion of Amplitude path finding? |
| ||
| I think something was lost in translation by Paposo's post. From the descriptions, my guess would be that he was referring to breadth first pathfinding. http://en.wikipedia.org/wiki/Breadth-first_search I'd agree with him, that it's more suitable than a* for what you want to do. |
| ||
| ah, thank you very much :-D |
| ||
| Yes. Gabriel are true. Sorry. I talk english very very bad. Bye, Paposo |
| ||
| Has anyone actually used breadth first within bmax? I’m having great trouble with it, determining any kind of path built around the criteria I originally mentioned? The playing area is made of a grid, each square represents a different type of terrain, each terrain type costs a different amount of move points to traverse it, and each unit has a max amount of move points per turn. I have it so that I can get a shortest path from unit to mouse pointer but have still no idea about how to work out all possible moves for the unit? Any help appreciated? |
| ||
| Hello. For get the best path use A* For get all cells at N points of player use BFS In A* use a PrioritaryQueue for the list of nodes pending In BFS use a FIFO Queue for same. I not have a BFS. I have a generic A* routine in BMax. If you need i post. Bye, Paposo |
| ||
| For get the best path use A* Not true. A* returns an optimum path depending on the heuristic used. |
| ||
| @paposo thanks again for your help |
| ||
| @tonyg what? I assume a good heuristic. A good heuristic get a value slighty small than real value. BFS obtain ever the best path whitout any direction of exploration. A* make any direction and it explore small region of cells. Bye, Paposo |
| ||
| A good heuristic doesn't always give the BEST path. It will return a GOOD path. To get the BEST path you need to use Djikstra's algo. A* heuristic is a trade-off between getting the best path and getting a good path in the best time. |
| ||
| Yes. you are true. |
   |