Pathfinding in AI logic

[Leoreth]

I recently wrote an AI method like this:

bool CvUnitAI::AI_rebuildMove(int iMinimumCost)
{
    CvCity* pBestCity = NULL;
    int iBestProduction = 0;

    int iLoop, iCurrentProduction;
    for (CvCity* pLoopCity = GET_PLAYER(getOwnerINLINE()).firstCity(&iLoop); pLoopCity != NULL; pLoopCity = GET_PLAYER(getOwnerINLINE()).nextCity(&iLoop))
    {
        if (GET_PLAYER(getOwnerINLINE()).AI_plotTargetMissionAIs(pLoopCity->plot(), MISSIONAI_REBUILD) == 0)
        {
            if (generatePath(pLoopCity->plot(), MOVE_SAFE_TERRITORY, true))
            {
                iCurrentProduction = pLoopCity->getRebuildProduction();

                if (iCurrentProduction >= iMinimumCost && iCurrentProduction > iBestProduction)
                {
                    pBestCity = pLoopCity;
                    iBestProduction = iCurrentProduction;
                }
            }
        }
    }

    if (pBestCity != NULL)
    {
        getGroup()->pushMission(MISSION_MOVE_TO, pBestCity->getX(), pBestCity->getY(), MOVE_SAFE_TERRITORY, false, false, MISSIONAI_REBUILD);
        return true;
    }

    return false;
}

It's not really necessary for my question to understand what a "rebuild move" is, but if you are familiar with unit AI you probably have seen this pattern before: iterate all cities, filter to the ones that are applicable, can be reached and are not already targeted by the same mission, and the select the "best" one.

My question here is about the "reachable" part that uses the AI logic for pathfinding. I originally forgot the "if generatePath" check in the for loop, which resulted in a bug where I assigned a target city to the unit that it could not path to and would instead keep idling in its current location.

The cause of my confusion is what this function considers "pathable". When debugging this issue I found units that would not move even though when I took control of them I could easily order them there manually. The route certainly was through friendly territory with no enemy units around. I tried multiple "AI flags" as well, neither made a difference.

My eventual "fix" was to check for reachability before even considering the city. The outcome was that the mission was not considered and the unit could do something else. However I was not able to get it to actually go there even though it clearly should be possible to.

What's going on? Am I misunderstanding how "generatePath" works? What is the equivalent code to the pathing shown to the human player?

Edit: when writing this I realised that this code misses the part where the unit checks if it already is at the target location and executes the intended rebuild mission. However that does not explain the behaviour I saw - it also occurred if the current plot and the target plot were different.

 

[devolution]

Hi @Leoreth ,

Your code looks fine to me at a glance but there are a couple of additions that may be helpful:

- area check to exclude non-reachable cities in other areas. This is strictly speaking not necessary but should be helpful as an optimization.
- usage of MOVE_IGNORE_DANGER may be considered if this is a military unit, otherwise danger along the path would cause the PF attempt to fail
- double-check that you don't have any "custom / special logic" in canMoveInto / path*Valid function that could exclude the target/route from being viable (the blocking condition may not remain constant)

Regarding the GUI pathfinder, I believe it allows any path that is valid when the user queues the move. Update: iFlags = 0 is actually passed to the PF

 

[Leoreth]

Good advice, I'll definitely apply it.

I tried iFlags=0 in my situation as well. The GUI pathfinder happily gave me a path, the unit AI did not consider the target plot reachable with iFlags=0.

 

[f1rpo]

When I search CvGameCoreUtils.cpp for "AIControl", I only see conditions related to plot danger. But I suppose you've tried the MOVE_IGNORE_DANGER flag, and you wrote that no enemy units were near anyway. There could be relevant checks for AI control elsewhere in the code. Well, not seeing any in the BtS version of CvUnit::canMoveInto. Seems that, when letting CvSelectionGroupAI::AI_isControlled return true indiscriminately, loading a savegame and moving units still works. (Not sure what might happen in between turns.) But somehow I doubt that this will show invalid paths for the units in question. My last resort with pathfinding mysteries has been to add assertions or conditional breakpoints in pathfinding code looking for particular plot-to-plot transitions that I felt should be valid.

 

[<Nexus>]

You may also want to contact @snowern because he is really into pathfiding.

 

[devolution]

I wanted to amend my reply but then I saw that our eminent modder, @f1rpo had joined in . I did edit my message which originally stated that I assumed that the UI pathfinder would use the MOVE_IGNORE_DANGER flag which turned out to be a flawed assumption!. Like @f1rpo pointed out, this flag only has an effect for AI controlled units.
Summary: When a human player performs pathfinding without automation, it is as if the MOVE_IGNORE_DANGER flag had been used for the current turn. For subsequent turns, automoves (like this queued human move) will be subject to danger checks at the start of each turn and before continueMission.

I realize that this may not be the answer you wanted but at least it sheds some lights on the PF with respect to the human, AI and automation cases.