First of all it should be noted that path-finding is not about finding shortest paths but about finding the "best" paths. Now, each paths has two major characteristics: (1) How long it is (or how much does it cost in terms of time) and (2) How dangerous it is (or how much does it cost in terms of resources). We use MC (and total_MC) to describe (1) and use EC (and total_EC) to describe (2). Of course, when it comes to selecting the "best" path, we need to compromise between taking the shortest road and taking the fastest road. To that end, we use the "combined cost", calculated as total_CC = PF_TURN_FACTOR * total_MC + move_rate * total_EC, where PF_TURN_FACTOR is a large constant. This means that each EC point is equivalent to 1/PF_TURN_FACTOR-th of one turn, or, equivalently, we are willing to spend one more turn on the road to avoid PF_TURN_FACTOR worth of danger. Note that if ECs are kept significantly lower than PF_TURN_FACTOR, the total_EC will only act as a tie-breaker between equally long paths. Note, that user is expected to ask "So this best bath, how long will it take me to walk it?". For that reason we keep our accounts of MCs and ECs separately, as one cannot answer the above question basing on total_CC alone. The above setup allows us to find elegant solutions to involved questions. A good example would be designing a road from A to B: ================ The future road should be as short as possible, but out of many shortest roads we want to select the one which is fastest to construct. For example: the initial conditions ("-"s mark existing road) A.....B ..... .---. a possible solution A-----B ..... .---. the best solution (utilize existing road) A.....B \.../ .---. To solve the problem we simply declare that MC between any two tiles shall be MOVE_COST_ROAD EC of any tile shall be the time to construct a road there ================= In some cases we would like to impose extra restrictions on the paths/tiles we want to consider. For example, a trireme might want to never enter deep sea. A chariot, would like to find paths going to enemy cities but not going _through_ them. This can be achieved through an additional tile_behaviour callback, which would return TB_IGNORE for tiles we don't want to visit and TB_DONT_LEAVE for tiles we won't be able to leave (at least alive). There are few other options, including "omniscience" (if true, all tiles are assumed to be KNOWN) and "zoc_used" (if true, we will consider restrictions imposed by zones of control upon our movements). The path-finding can be used in two major modes: (1) We know where we want to go and need the best path there How many miles to Dublin? Three score and ten, sir. Will we be there by candlelight? (2) We know what we want and need the nearest one Ou est la toilette la plus proche? In the first case we use pf_get_path and pf_get_position (the latter will only tell us the distance but not the path to take). In the second case we use pf_next to iterate through all tiles in the order of increased distance and break when we found what we were looking for. In this case we use pf_next_get_* to get information about the "next closest tile". ===== Examples ===== Hope that's all. G.