Path finding

Path finding is a mathematical problem of finding the best (or, at least, as plausible as we can) path in a graph from one node to another, when some nodes are joined by edges (maybe edge from A to B is different from one from B to A) and we can pass by each arc paying a specific cost. For Freeciv, the "nodes" mean tiles and "edges" mean just ajacency of them, and paths are sequences of tiles that units can walk (note that actually the path objects may also contain information of what the units do in the way or at the end). Only paths between adjacent tiles are considered for now (not airlifts, far-ranged actions etc.)
Path finding is performed both client-side, when a player clicks a unit with ta mouse and the client traces a blue line to another tile where the mouse points now, and server-side for units controlled by AI or advisors (autoexplore, autoworkers). Server-side pathfinding may consume a large part of the turn change lag. Client side paths are sent to server as unit orders that are stored in savegames and may span several turns (but unitwaittime commonly aborts them). Server side ("advisor") paths are executed from another, simpler data format, and they don't go to savegames.
== Used algorithms ==
Much information on this topic you may find in comments within common/aicore/path_finding.h].
Before paving a path, map is processed around a unit iteratively until the destination tile is reached. Or the map is processed within some moving distance we consider suitable for planning, and all targets reached are considered. Any way, the iteration is performed from lesser potential path move costs to bigger.
We put our starting tile as iterator, make a map reflection array with necessary data for each tile (nodes) initialized with 0's and then start iterations. An iteration means we look at current iterator for whatever purpose we need (e.g. consider can and do want we attack this tile), process it and then pull out of the queue a node of the next tile by cost of accessing it (the cost is basically path length in move fragments spent on it (movement cost, MC) but may be modified by extra cost (EC)). The queue is, as you can guess, an array of nodes sorted by access cost. We put nodes into it by processing each next iterator, that means, we look at each adjacent node that was not processed before, see what is the cost to step from here to there, add it to the cost we've paid to get to the iterator and place or update the (yet unprocessed, adjacent to iterator) new node in the queue with this cost. You can easily see that the costs are always growing with each new iteration, since cost of each step is not negative and both the adjacent tiles we consider during processing our node and the tiles that remain in the queue after it have similar or bigger costs.
Before, I've described a simple Dijkstra's algorithm if you don't have extra costs. But actually we can't analize just total path cost. We might need move points, fuel ("air" units) and health ("helicopters" or, actually, just any damaged units) to get farther and/or to perform actions better (action, as you can see, is considered also just a step with a cost). To get those resources when we a sparse of them, we may consider waiting on a tile we've reached before for one or more turns, exchanging for the gain we wont an amount of move points we don't spend. The waited node, to make it into the algorithm we use, is put back into the queue with the cost of the waiting. When we pull it out of the queue, we don't give it to our "look what can we do here" function; instead, we start an inner iteration loop (with its own queue) to pave path from this tile by already processed tiles that get any extra resource after this waiting, until we hit into an unprocessed tile we could not reach before that now goes to a normal queue. Since in process of this operation nodes of many tiles change their state which recorded optimal path to them before, path to tiles that go through potential waiting points are recorded in structures out of the node lattice, segments, that are accessible by their end tile node.
Each pathfinding method, within Freeciv code, combines two main structures: parameter that contains information about the unit (or group of loaded units) we move around and functions we use to get move and extra costs, possibility to enter and/or leave a tile, iterate the map etc.; and map that contains the node lattice. The map type must agree with the functions we have in the parameter; its specialization (currently, normal, fuel or danger map) is hidden from outer code by pf_map_new() function that takes into account what methods in the parameter are NULLs.
Now, about the PF algorithms we have and ones we need.
=== Normal pathfinder ===
Normal pathfinder currently is a simple Dijkstra's algorithm that is used for ground units moving within their continent (maybe boarding standing ships) or ships navigating an ocean (maybe entering ports).
What could be improved:
* if the unit has some minimal possible movement cost, we, finding path to a pre-determined target, can add to tiles extra cost equal to the minimal possible distance to that target. That turns our algorithm into a faster A* one that won't iterate by (if we are on a umiform plain) full circle of radius of the distance to the target, but by a much smaller ellipse.
* Attack is always considered requiring a full single move. For rulesets where we don't have "tired attack" rule, this can be laxed to one fragment. And where we do have this rule, we may just pass moves left (we track them any way) to the target evaluation procedure that will decide if we can bear the risk of attacking at not full strength. Likely, we need this feature only for targets of the ongoing turn, so no waiting is needed.
=== Danger pathfinder ===
This one used to guide triremes before v.2.2 when it was fired for inefficiency (too many sunken units) with almost all the dangerous terrain features. Probably, its realization is broken in some places, but it still goes inside the code. The idea is that we divide all tiles accessible for the unit on safe ones and dangerous ones, and try to never end turn at the latter. Actually, the danger iterating function just never marks dangerous tiles as processed and never passes it to the iteratively applied function. Danger nodes go to their own queue, and it is iterated innnerly without taking anything from the main one as long as it is not empty. While path to a safe tile is reconsidered when a shorter one by total cost is found, the dangerous ones are iterated to try to get more moves left at them (and in some other case I don't understand, possibly it really has never fired). When we reach a safe node from a danger one and the path is shorter, we supply to the former an array of dangerous positions crossed, the danger segment. The segment also remembers have we waited before entering the danger area (obviously, only safe nodes are considered for waiting).
I can't tell for sure without testing but likely the algorithm does not prevent ending turn on a dangerous node even in cases it can be possibly avoided. And you will have to analize the found path thoroughly to understand what is your probability to get alive to the destination (that 2.1 AI missed to do).
What could be done if we ever have sinking triremes and dangerous glaciers again:
* While in the algorithm any safe node is put back for waiting, we can use only ones bordering unsafe region.
* For sure, we should process unsafe nodes, just we must track the risk and see if it is worthy to take.
* Let's use extra costs for AI pathfinding. We have military amortization coefficiency that approximates how much less valuable gets an operation gain (because of technology progress, inefficiency of long planning etc.) with each turn spent. We can as well scale it down for a turn spent on a dangerous tile due to probability of sinking there without any gain; if we use returnable units in the operation, we may amortize [success probability] × ([target gain] + [units cost] × [escape after accomplishing the mission probability]) that should be compared to unamortized units cost to see if there is any profit at all. So, we can express extra cost of getting with no mp left to a dangerous tile as waiting some (usually fractional) number of turns N in which the operation gain will be amortized to the same part; that extra length will be proportional to the logarithm of the amortization coefficiency. At the end point, we will just take the total extra cost and exponentiate it to get our delivery probability, and a more efficient way through dangers will probably be traced considering partial extra xosts.
=== Fuel pathfinder ===
This path finding task is commonly referred as "air path finding" though we have a lot of fueled naval units in our rulesets and in theory may have such land units (though some old parts of code might still assume that the unit's speed is not terrain-dependent). Fuel is a unit's counter that is set to some type-dependent maximal value when a unit starts its turn in a city or on a native base (or near a safe coast terrain, for coast-fueled units) and is reduced by one if it starts turn in other place; if it falls to 0, the unit is lost. 
For fueled units pathfinding, the number of remaining movements is scaled to the fuel amount (this assumption gets wrong if there are local movement bonuses). Tiles where the unit can refuel (and that are reached best with positive mp) are put back into the queue with the cost of the lost mp's spent. To distinguish on the map between cases of passing without waiting, waiting and making loops and hooks for waiting on another tiles, segments are used that are, intristically, dynamically allocated per-step records referred from each other and/or from the tiles where they lead, and are reference counted. To trace a path to a tile, you iterate from the starting node sometimes returning to nodes where tou can wait and tracing segments from them by nodes that are already processed but waiting gives you more mp (read, more fuel) at them, that are stored in a separate waited queue, so you can try getting farther. When the target tile is reached, you trace back from it by segments to the nearest refuel node back (or to the start position), and only then you mind the directions stored in nodes themselves. Waiting is distinguished by reaching a refuel node by a segment that refers to not the node's own segment.
One of the mandatory parts of a fueled unit parameter is a minimal mp requirement node callback that cuts off ways that the unit won't be able to pass without crashing due to a fuel shortage. At v.2.6.5, an attack (or another action) of a non-missile air unit is considered impossible if there going to be no refuel base in its accessibility radius from the target tile. Sometimes we would decide to sacrifice the unit, or the base the plane relies on is actually surrounded by enemy forces, so this limitation is not ideal for AI logic and makes a player sometimes move by arrow keys only.
Up to v.2.6.4, some parts of air path finder were pitifully broken; mainly, bugs in waiting code have prevented from taking off planes driven by AI and ones with not full mp driven by player orders.
=== Amphibious path finding ===
This type of path finding is used by AI to transport units by ferries where they can't or don't want to go on their own. Amphibious parameter pft_amphibious defined in pf_tools.h is a structure different from normal parameters; actually, its two properties land and sea are two actual parameters filled by the caller for the cargo and the ferry, and its third parameter-type property combined is filled then by the function pft_fill_amphibious_parameter and has a backlink to the amphibious structure in its data field. This combined parameter is used by the AI in a normal pathfinding algorithm; it uses the "sea" movement cost where the ferry can go and the cargo's elsewhere, scaled to their relative speed. What goes where, is stored in move_scope field of the node as MS_TRANSPORT bit flag, that can be switched off on the next node (the cargo disembarks) but not on; in some theoretically possible cases when the transport can enter a tile only by a cardinal river and we first found it from a diagonal node, that gets wrong. Also, if we can reach the target by tiles containing both river and maglev, we'll go by trireme as far as possible and may waste some time. Also, non-Marine AI units should stop attempt performing attacks from transports.
=== Reverse maps ===
Reverse map tells us how fast an arbitrary unit of some player from an arbitrary place can go to a given target. Such maps are used by AI to find all units dangerous for a specific city (2 to 6 attacker's turns radius) or a Barbarian Leader (3 turns radius). This object contains a hash where keys are some parameters describing unit type, initial position etc. (only the simplest normal map parameters supported, no fuel or danger considered) and the values are position records from a corresponding normal map where the target tile is found.
== Things we may need ==
=== Helicopter (losing hp) maps ===
Currently, if a player moves a Helicopter with a mouse, it just uses normal pathfinder and it's the player's business to look what happens with its health. AI can't do it and just won't move its units if they lose hp starting their turn out of a city, a base or a carrier, unless it has a wonder that compensates this effect (but keeps producing them any way). Historically, helicopters used to be considered by the AI as fueled units with fuel=ceil(100/hp_loss_pct), but to the time when an improved (but still broken) fuel pathfinder was developed it was decided to leave them out. We can actually revive this idea but with these concerns:
# When a helicopter attacks losing all mp in the open, its survival chance is reduced compared to the winning chance, since if its hp fall under its hp loss amount, it dies at turn change. We should calculate it when we plan an operation.
# Unlikely to fueled units that in a tile either don't refuel at all or regain full fuel, units that lose hp may regenerate different amount of hp in different cities, that may span different number of turns (and often at least 2 since we must stand still a turn to repair). So, we should return to one waiting point several times during path finding, and for far paths, we might need to distribute regeneration between several points in our way...
# When our main concern is hp in the final point, we'd better track how healthy is our helicopter in its way due to the danger of some random unfriendly encounter.
Category:Development