A* is a very famous algorithm for games-programmers which efficiently finds routes from one point to another, intelligently avoiding obstacles and looking for the shortest possible path. Using @redblobgames‘s tutorials and code, I’ve added it to GoA. It’s quite fun to play with, so here’s an interactive demo:
- Move the mouse to choose a start point (previewed by a white hemi-sphere)
- Left click to set start point
- Move the mouse to path-find to wherever the mouse is
- Path will be drawn as fast as possible
- Green line: indicates direct path start to end
- White spheres: show the on-the-ground “best” path
- Blue outlines: show the “frontier” of how far A* had explored in other directions before finding the perfect solution
- Click the “expand” box to open up the interactive config options.
- Adjust, then click “expand” to hide them again, and move the mouse – the new options will be used immediately
- far_penaltyUphillHexes: penalty for TOTAL uphill difference over whole path. Multiplied by the height difference – most things are a height of only 0.001 apart, up to 0.5 for exreme height changes, so this needs to be quite high. NOTE: if the start and end are same height, even though there’s bumps in between, this will have no effect; it’s quite dumb!
- far_bonusDownhillHexes: opposite of above: the bonus for going downhill; same conditions apply.
- neighbour_penaltyUphillHexes: penalty when going from hex to hex going uphill. Unlike “far” version above, is only ever applied to adjacent hexes, so calc is a lot more accurate.
- neighbour_bonusDownhillHexes: ditto but for going downhill.