patchFreeciv - Patches: patch #3901, Rewrite get_MC callbacks for...

Show feedback again

patch #3901: Rewrite get_MC callbacks for complex nativity

Submitted by:  Emmet Hikory <persia>
Submitted on:  Wed May 8 08:09:33 2013  
Category: aiPriority: 5 - Normal
Status: DonePrivacy: Public
Assigned to: pepeto <pepeto>Open/Closed: Closed
Planned Release: 2.6.0Contains string changes: None

Add a New Comment (Rich MarkupRich Markup):

You are not logged in

Please log in, so followups can be emailed to you.


(Jump to the original submission Jump to the original submission)

Mon May 12 12:41:18 2014, SVN revision 24881:

Pathfinding: rewrite the move cost callbacks for getting more flexibility with
rulesets. The callbacks are no more selected mainly from the unit move type
(land, sea, both), assuming terrain nativity and unit flags tests are enough to
determine how a move will cost.

Patch by Emmet Hikory (persia@gna) and me

See gna patch #3901

(Browse SVN revision 24881)

pepeto <pepeto>
Project MemberIn charge of this item.
Fri May 9 18:48:23 2014, comment #16:

You are right. Patch attached.

(file #20695)

pepeto <pepeto>
Project MemberIn charge of this item.
Fri May 9 10:39:48 2014, comment #15:

My branch has (and so my patch should have):

Your patch seems to have (at least when I created a branch from it):

I was testing the flags for early-termination, but it makes the indenting confusing. When cleaning up the indentation, I suspect you made it easy to read by reordering it. I expect this causes every call to always check tile nativity, even for units that don't care (unless there is some compiler optimisation that means that conditional ordering doesn't actually matter, in which case this isn't important at all), but I could be wrong.

Emmet Hikory <persia>
Project Member
Fri May 9 07:35:54 2014, comment #14:

> In pf_able_to_attack(), I prefer checking flags before
> nativity, but that's just (potentially useless) optimisation,
> based on my speculative estimates of call costs.

What to do you mean exactly?

pepeto <pepeto>
Project MemberIn charge of this item.
Fri May 9 07:22:43 2014, comment #13:

Wow! That definitely solves it, and matches the behaviour that seems to be encoded in unit_move_to_tile_test(). In pf_able_to_attack(), I prefer checking flags before nativity, but that's just (potentially useless) optimisation, based on my speculative estimates of call costs.

Thanks so much for the detailed review and rewrite to make it do what I wanted, except better than I could have written it.

Emmet Hikory <persia>
Project Member
Fri May 9 07:20:46 2014, comment #12:

> I want also to clarify that CodingStyle says that such
> variables should be left uninitialized (added to CodingStyle in
> patch #3603)

Thanks you Marko, I didn't notice the changes to CodingStyle. Especially because I read mosly the wikia page and it didn't get up to date...

pepeto <pepeto>
Project MemberIn charge of this item.
Fri May 9 00:58:42 2014, comment #11:

> It is not needed as it is initialized when it is used (pcity =
> tile_city(ptile)), the pointer is not used anywhere else.

I want also to clarify that CodingStyle says that such variables should be left uninitialized (added to CodingStyle in patch #3603)

Marko Lindqvist <cazfi>
Project Administrator
Thu May 8 09:51:10 2014, comment #10:

New version matching my previous comment.

(file #20690)

pepeto <pepeto>
Project MemberIn charge of this item.
Thu May 8 08:05:24 2014, comment #9:

Thanks for your arguments.

For is_native_move(), I will check. I think it isn't at the right place in single_move_cost() (it forbids to move to transport e.g.). The calls to pf_is_ok_move_tile() should have discourage to calculate the cost if the move was not possible I think.

Ok for city channel.

> not initialising pcity to NULL in pf_is_ok_move_tile (why?)

It is not needed as it is initialized when it is used (pcity = tile_city(ptile)), the pointer is not used anywhere else.

> removing the redundant check of whether the potential transport owner

Sorry, I forgot I had touched that.

pepeto <pepeto>
Project MemberIn charge of this item.
Thu May 8 00:42:44 2014, comment #8:

Thanks again for the detailed review.

How is move nativity checked before calling single_move_cost? Without calling is_native_move(), a unit may move between any two tiles that are native to that unit, even if the two tiles are only native because of a road that does not permit that type of movement (e.g. a cardinal-only road on two diagonal tiles, with no between tiles, and considering a diagonal move, in otherwise non-native terrain). Since the actual move processing prohibits this, this could result in a best path being calculated that cannot be executed.

I don't think it is safe to limit city channel checking to only the source tile. With the implementation you have, it means that every city is an acceptable destination for every unit, even non-native cities with no surrounding native terrain that are not part of a city channel. With an implementation that only guards the city channel check, it still allows units to disembark from transport to non-native cities or prohibits units from disembarking from transport to cities at the far end of a city channel (depending on implementation). Yes, it would be redundant for cases of moving between two cities, or between native tiles and cities, but there are cases where it is not redundant.

I'm fine with the overlap change: it's too hard to usefully distinguish when there is going to still be an active blocade later :)

Two changes I noticed beyond the list: not initialising pcity to NULL in pf_is_ok_move_tile (why?), and removing the redundant check of whether the potential transport owner and moving player were the same (good catch!).

Emmet Hikory <persia>
Project Member
Wed May 7 21:23:35 2014, comment #7:

I finished to review your work. I attach a modified version of it:

  • do not limit single_move_cost() (test would have been done before) ;
  • limit the city channel city to source tile (I think this would be redondant else, or may I be wrong?) ;
  • do not consider enemy units and attacks for overlap_move() as its utilisation look to request ;
  • fixed indentation according to the coding style.

Note that is replace the fix bug #22022.

(file #20674)

pepeto <pepeto>
Project MemberIn charge of this item.
Tue Apr 29 16:56:20 2014, comment #6:

Rebased against r24826

(file #20614)

Emmet Hikory <persia>
Project Member
Sun Apr 20 20:59:37 2014, comment #5:

Updated patch addressing identified issues from review. Overlap moves now have a separate cost function (set to param->move_rate, rather than SINGLE_MOVE to discourage attempting to land in two places in one turn). Overlap moves still consider attacking, but only if they would be moving to non-native territory (this may cause issues with paths post-combat, but pathfinding handles non-terminal combat poorly anyway, so not a regression). The order of conditionals for pf_is_ok_move_tile() was adjusted, which should speed resolution for most cases involving entering or leaving cities (while potentially slowing resolution when entering transport in an otherwise inaccessible city in games permitting city channels (should be rare)). Patch applies over r24782.

(file #20540)

Emmet Hikory <persia>
Project Member
Wed Apr 16 22:46:57 2014, comment #4:

After some discussion on IRC, pepeto and I concluded that the comment "/* Entering port or bombardment */" introduced into sea_overlap_move() in r12065 was, while sensible, not the intended purpose of this use of SINGLE_MOVE. Rather, this use of SINGLE_MOVE is intended to represent the cost of moving to normally inaccessible territory as a result of overlap movement, to facilitate path planning for ferries. As a result, it is probably inappropriate to check pf_is_able_to_attack() in overlap moves, and there should probably be a new function overlap_move_cost, initially always returning SINGLE_MOVE, but used to indicate semantic construction for future developers encountering this issue, or needing to apply special values for this condition.

There was also some discussion about the appropriate ordering of the city_channel_tile() check and the potential_transport check in pf_is_ok_move_tile(), and interaction of this ordering with potential application of is_source_tile to city_channels and use in overlap moves.

Note that bug #21871 is now targeted only towards S2_5, so this patch must also address that issue in final form.

Review remains underway: those with rulesets that depend on complex nativity may feel free to test with the current patch (which addresses the vast majority of client-side GoTo issues), but be aware there may be additional changes as a result of deeper review.

Emmet Hikory <persia>
Project Member
Thu Apr 3 08:47:51 2014, comment #3:

The attached patch is rebased on r24748 and only checks whether a transport is present without orders, rather than checking if it has available capacity (similar logic to that in bug #21871, which patch is rendered unnecessary if this is applied), and further only checks this for destination tiles, so that one may disembark from transport with orders.

It appears there is still potential for confusion: when performing an overlap move, transports are never checked for orders: this may cause the AI to be slightly more likely to try to use transports that will not be there when they arrive for certain sorts of moves, but in all cases these are attempts it would attempt with the logic in r24748, so do not represent a regression.

(file #20465)

Emmet Hikory <persia>
Project Member
Sun Mar 23 13:42:45 2014, comment #2:

Found an oddity testing with this: If a transport is full, units in the transport cannot disembark from it with client-side GoTo pathfinding if the transport is on a tile that is otherwise non-native to the disembarking unit. This seems to be a result of checking pf_is_ok_move_tile() on the source, and excluding tiles where the transport has no available capacity. Possible solutions involve a) passing a boolean to indicate whether to test transport capacity, b) move the transport capacity test into the callers, c) split into pf_is_ok_src_tile() and pf_is_ok_dst_tile(), and d) don't bother checking capacity in pathfinding, and only block the moves at the actual move time (this may confuse the AI). I'll pick one after thinking about it, unless someone else has a preference, or a better solution than those listed above.

Note that the AI doesn't seem to have issues disembarking from ships (at least it successfully disembarks settlers and military forces on foreign shores), and players can work around this with direct movement (number keys, arrow keys, etc.).

Emmet Hikory <persia>
Project Member
Thu Mar 20 03:55:07 2014, comment #1:

Rebased against r24699

(file #20392)

Emmet Hikory <persia>
Project Member
Wed May 8 08:09:33 2013, original submission:

The pathfinding get_MC callbacks are selected based on utype_move_type(), have inherent assumptions about which flags could apply to which move_types, terrain nativity of cities, and binary nativity. For UMT_BOTH units, there is additional awkwardness in that AI requests for different types of movement with different restrictions are not honored. Aside from inconsistency, there are probably bugs hiding in the conflation of various conditions, and it certainly isn't suitable for highly complex rulesets with widely overlapping nativity.

This patch provides a complete rewrite, with three get_MC functions for the three generic needs (normal, overlap, attack), with inline helper functions providing logic to avoid the potential for partial updates in the future. This makes it fairly easy to see the behaviour differences for the different callbacks, and also independently verify the correctness of the logic permitting attacks, permitting moves, and assigning costs for various actions.

The logical tests are constructed in such a way that in most cases no condition will be checked twice for a given set of starting conditions. The exception is that whether the unit is native to either the source or destination may be checked twice if the unit cannot attack non-native tiles, cannot attack from non-native tiles, is on a non-native tile, and is considering a move to a native tile containing non-allied units (source is checked twice here: I'm not quite sure how to check destination twice, although my tautological tables imply it should be possible). I chose not to cache this value mostly because we usually don't need to call it more than once. Suggestions on ways to rearrange the logic so that we don't either force such calls when unnecessary or ever call it twice are appreciated: perhaps in the event it is called once, the value can be cached to be used later, although this is only useful if the cost of such caching is less than the cost of checking tile nativity (which is fairly expensive). Note also that we don't bother checking to see if the target tile is a city in pf_able_to_attack() mostly because we know that if it happens to be a city, we can't conquer it until the inhabitants have
been attacked: depending on the intent of the attack nativity conditionals, it may be appropriate to check for native cities in the event the tiles in question are not native (probably by implementing can_class_exist_at_tile()). There may be other interesting tests for pf_able_to_attack() (e.g. UTYF_CIVILIAN): I'm unsure how much to add here vs. how much processing should be done at each step for pathfinding to behave both well and fast. Suggestions welcome.

Some of the behaviour changes caused with this patch include:
* UMT_BOTH units now do not travel through unallied unit tiles when called in overlap or attack modes.
* UMT_SEA units now do not travel through unallied unit tiles when called in overlap mode.
* UCF_MISSILE and UTYF_ONEATTACK units are now charged the remainder of their movement within a turn when attacking.
* UMT_SEA and UMT_BOTH units are now able to use citychannel tiles (and must have UCF_BUILD_ANYWHERE to use cities without adjacent nativity).
* UMT_SEA and UMT_BOTH units now check for available transport on non-native tiles.
* Several cases that were previously assigned SINGLE_MOVE now use single_move_cost, and tile_move_cost_ptrs() may return different move costs for these actions, depending on available terrain, transport, etc.
* Units attempting to conquer unoccupied non-allied cities now must check UTYF_CAN_OCCUPY_CITY to do so.

This patch functionally depends on patch #3897 and patch #3900: without the former, fueled units are incorrectly charged for UCF_MISSILE and UTYF_ONEATTACK attacks, and without the latter, pathfinding loses even the rudimentary UTYF_IGTER handling presently available. The patch itself isn't very readable: reviewers are encouraged to look at pre-application and post-application pf_tools.c side-by-side to more clearly see the differences in the beginning of the file: changes near the end are more readable as diff.

Note that reverse_move() does not compile if the #ifdef UNUSED protection is removed. While I've tried to preserve the intent of reverse_move_unit(), I suspect that in nearly all cases it would be better to use get_MC(dest, dir, src, param) to calculate the value: the exception being that slow_invasions handling would not be correct with such logic (but this bug already exists in pf_reverse_map_get_costs()).

Emmet Hikory <persia>
Project Member


(Note: upload size limit is set to 1024 kB, after insertion of the required escape characters.)

Attach File(s):

Attached Files
file #20614:  native-get_MC-callbacks+rebase2.patch added by persia (21kB - application/octet-stream)
file #20540:  native-get_MC-callbacks+firstreview.patch added by persia (21kB - application/octet-stream)
file #20465:  native-get_MC-callbacks+transports.patch added by persia (20kB - application/octet-stream)
file #20392:  native-get_MC-callbacks+rebase.patch added by persia (19kB - application/octet-stream)
file #17925:  native-get_MC-callbacks.patch added by persia (21kB - application/octet-stream)


Depends on the following items: None found

Items that depend on this one: None found


Carbon-Copy List
  • -unavailable- added by cazfi (Posted a comment)
  • -unavailable- added by pepeto (Updated the item)
  • -unavailable- added by persia (Submitted the item)

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.


    Error: not logged in



    Follow 15 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon May 12 12:42:06 2014pepetoStatusReady For Test=>Done
    Fri May 9 18:48:23 2014pepetoAttached File-=>Added trunk_pf_native_get_MC_callbacks3.diff, #20695
    Thu May 8 09:51:10 2014pepetoAttached File-=>Added trunk_pf_native_get_MC_callbacks2.diff, #20690
      StatusIn Progress=>Ready For Test
    Thu May 8 08:05:24 2014pepetoStatusReady For Test=>In Progress
    Wed May 7 21:23:35 2014pepetoAttached File-=>Added trunk_pf_native_get_MC_callbacks.diff, #20674
      StatusNone=>Ready For Test
    Tue Apr 29 16:56:20 2014persiaAttached File-=>Added native-get_MC-callbacks+rebase2.patch, #20614
    Sun Apr 20 20:59:37 2014persiaAttached File-=>Added native-get_MC-callbacks+firstreview.patch, #20540
    Wed Apr 16 22:46:57 2014persiaPlanned Release=>2.6.0
    Thu Apr 3 08:47:51 2014persiaAttached File-=>Added native-get_MC-callbacks+transports.patch, #20465
    Thu Mar 20 03:55:07 2014persiaAttached File-=>Added native-get_MC-callbacks+rebase.patch, #20392
    Wed Jan 8 12:40:34 2014pepetoAssigned toNone=>pepeto
    Wed May 8 08:09:33 2013persiaAttached File-=>Added native-get_MC-callbacks.patch, #17925
    Show feedback again

    Back to the top

    Powered by Savane 3.1-cleanup