![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
I've played a lot of freeciv and freecol over recent years. Both games let you order a unit to go to some square, and hopefully it takes the fastest route there. The 'world' is a square grid, of various terrain types and associated movement costs -- e.g. plains or desert take 1 move, but mountains take 3; roads and rivers take 1/3 no matter what terrain type they're laid over.
A* is this sweet magic algorithm for finding shortest paths in some graphs efficiently, vs. doing breadth-first search in all directions, but I was having trouble applying it mentally. I was using the common Manhattan distance heuristic, h((0,0),(x,y)) = x+y, and I wasn't getting good results: the algorithm would cheerfully march down a straight plains path to the goal, while ignoring a path that might step away and into mountains, but then ride a river to the goal much faster.
So I backed off, and thought about BFS. I realized that would work better if instead of naive BFS, enqueuing grid squares as you found them, instead you ranked them by total travel time so far. This is basically A* without a heuristic. Instead of exploring all paths N squares away, you'd explore all paths N moves away; it would still be radiating in all sorts of directions, but at least you'd find the shortest path to the goal.
Then I realized I'd been using the wrong heuristic; the right one should be the shortest possible journey. Or as WP says, "it never overestimates the actual cost to get to the nearest goal node." So the heuristic in this application has to consider rivers and roads, such that h() = (x+y)/3, not (x+y). This works much better: the plains march looks less attractive as it advances, converting cheap heuristic moves into actual plains moves, and the "mountain and away" move gets a chance to be considered.
Actually, units and roads can go diagonally, though rivers are rectilinear, so the proper heuristic is h((0,0),(x,y)) = max(x,y)/3.
Actually actually, infantry units only have one move, but are still guaranteed one square of movement per turn, so can march across mountains as easily as across plains; it's mounted units, with e.g. 4 move in freecol, that really care about base terrain type. Also fractional movement can be useful, e.g. I think a unit with 2/3 move left (after moving on river) can still move onto an adjacent plains.
A* is this sweet magic algorithm for finding shortest paths in some graphs efficiently, vs. doing breadth-first search in all directions, but I was having trouble applying it mentally. I was using the common Manhattan distance heuristic, h((0,0),(x,y)) = x+y, and I wasn't getting good results: the algorithm would cheerfully march down a straight plains path to the goal, while ignoring a path that might step away and into mountains, but then ride a river to the goal much faster.
So I backed off, and thought about BFS. I realized that would work better if instead of naive BFS, enqueuing grid squares as you found them, instead you ranked them by total travel time so far. This is basically A* without a heuristic. Instead of exploring all paths N squares away, you'd explore all paths N moves away; it would still be radiating in all sorts of directions, but at least you'd find the shortest path to the goal.
Then I realized I'd been using the wrong heuristic; the right one should be the shortest possible journey. Or as WP says, "it never overestimates the actual cost to get to the nearest goal node." So the heuristic in this application has to consider rivers and roads, such that h() = (x+y)/3, not (x+y). This works much better: the plains march looks less attractive as it advances, converting cheap heuristic moves into actual plains moves, and the "mountain and away" move gets a chance to be considered.
Actually, units and roads can go diagonally, though rivers are rectilinear, so the proper heuristic is h((0,0),(x,y)) = max(x,y)/3.
Actually actually, infantry units only have one move, but are still guaranteed one square of movement per turn, so can march across mountains as easily as across plains; it's mounted units, with e.g. 4 move in freecol, that really care about base terrain type. Also fractional movement can be useful, e.g. I think a unit with 2/3 move left (after moving on river) can still move onto an adjacent plains.
transferable problem-solving
Date: 2017-01-17 18:39 (UTC)From:These kinds of conceptual problems make for enjoyable reading, even when I'm not adept in the skill under discussion. I feel as though the problem-solving approach carries over into other terrain--like a temporary skill boost. So, er, thanks for the top-up.
(Nothing very clever to add, I'm afraid.)
{rf}
no subject
Date: 2017-01-17 22:46 (UTC)From:I suppose the Mars rover route planners have plenty of cores to throw at the problem.