Timeline for Pointy top hexagonal A* pathfinding
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 18, 2012 at 6:41 | comment | added | Roy T. | Hmm, I have some fixing of code to do! | |
| Apr 17, 2012 at 21:44 | comment | added | amitp | Yep, not only is it an overestimate, but (ActualCost + H) when H is large assigns too much weight to the H portion and too little to the G portion. In other words, when picking the best item from the Open set, it's mostly guided by H, and G doesn't play much of a role. This turns A* into best-first search, which isn't bad, but it may not be what you wanted. | |
| Apr 17, 2012 at 18:15 | history | edited | Roy T. | CC BY-SA 3.0 |
removed possibly faulty optimization
|
| Apr 17, 2012 at 18:14 | comment | added | Roy T. | I have to double check this in my own implementation, I think it doesn't matter because as long as you haven't found the path the heuristic part of the cost is on the same scale. But it could interfere if (ActualCost + H) is a false overestimate to the goal because of a large H and a low ActualCost thus violating the 'admissible heuristic' clause of the H in A*. I've edited the optimization out of my answer for now. | |
| Apr 17, 2012 at 15:41 | comment | added | amitp | True, you don't need sqrt for sorting, but A* also uses the heuristic for addition (adding the heuristic to the cost), and there the sqrt does matter. | |
| Apr 17, 2012 at 15:30 | history | answered | Roy T. | CC BY-SA 3.0 |