Pathfind updates

[MowFord]

I backported careful pathing to WingsXI a bit ago and one thing that I spent a lot of time with was making sure it didn't cause mobs to get stuck indefinitely (easily exploitable). The thing I settled on is a bit of a monster, but it does work well:

 if (isNavMeshEnabled() && m_carefulPathing)
    {
        // - when careful pathing is enabled on a mob, it snaps to nearest navmesh every `StepTo`
        //    - If the next point in its pathlist cannot be raycast, it increments a counter `CarefulPathSnapCount`
        //    - if that counter gets past a threshold
        //    -  `CarefulPathSnapMax`, the path is cleared and mob is snapped away from the destination a bit and repathed
        //      - would like to maybe pathfind to the middle point in the list of its remaining pathpoints (`nextPoint = m_points[(int16)(( m_currentPoint + m_points.size() - 1) / 2)];`)
        //    - Another variable, `CarefulPathSnapMin`, is incremented. This is actually the requisit number of failed aforementioned raycasts.
        //    - This essentially lets a mob's path get sloppier if it continuously gets stuck
        //    - For example: pathing Anantaboga back and forth between zoneline near his spawn and the tunnels towards o.crabs got `CarefulPathSnapMin` up to 10, but he still pathed pretty cleanly (cut some corners but never bounced down to the water level, etc)
        //    - Note that in these changes, raycast has a check for a new concept, `CNavMesh::onSameFloor`. This is, i think, the main thing being relied on when the next pathpoint's raycast failure is determined up above
        if (m_POwner->objtype == TYPE_MOB && static_cast<CMobEntity*>(m_POwner)->GetBattleTargetID() != 0)
        {
            if (m_currentPoint == 0 && origDistanceMoved == 0)// when mob is close to destination, reset sloppy pathing (i.e. when path is recently cleared)
            {
                ShowDebug("Mob %s (%u) is now resetting careful pathing sloppiness\n", m_POwner->GetName(), m_POwner->id);
                m_POwner->SetLocalVar("CarefulPathSnapMax", 10);
                m_POwner->SetLocalVar("CarefulPathSnapMin", 1);
            }

        }
        else
        {
            // do not snapTo while not in combat
            m_POwner->SetLocalVar("CarefulPathSnapMax", 1);
            m_POwner->SetLocalVar("CarefulPathSnapMin", 0);
        }

        // loosen the meaning of "careful pathing" to only snap so many times if you can't raycast to the next pathPoint
        if (m_POwner->GetLocalVar("CarefulPathSnapMax") > 1 &&
            !m_POwner->loc.zone->m_navMesh->raycast(startingPoint, targetPoint, false))
        {
            m_POwner->SetLocalVar("CarefulPathSnapCount", m_POwner->GetLocalVar("CarefulPathSnapCount") + 1);
        }
        else
        {
            m_POwner->SetLocalVar("CarefulPathSnapCount", 0);
        }

        // Snap mob to closest navmesh every StepTo, unless we've hit our limit on snapping when unable to raycast to next point
        // do not re-path if not in combat
        if (m_POwner->GetLocalVar("CarefulPathSnapCount") < m_POwner->GetLocalVar("CarefulPathSnapMax") ||
            m_POwner->GetLocalVar("CarefulPathSnapMax") <= 1)
        {
            // When snapping, get sloppier over time by skipping the first few Steps when unable to raycast to next point
            // But only skip the snapto after a few un-raycastable pathpoints
            if (m_POwner->GetLocalVar("CarefulPathSnapCount") >= m_POwner->GetLocalVar("CarefulPathSnapMin") - 4 &&
                m_POwner->GetLocalVar("CarefulPathSnapMax") > 1)
            {
                m_POwner->loc.zone->m_navMesh->snapToValidPosition(m_POwner->loc.p);
            }
        }
        else
        {
            ShowDebug("Mob %s (%u) snapped %u times and is resetting path\n", m_POwner->GetName(), m_POwner->id, m_POwner->GetLocalVar("CarefulPathSnapCount"));
            m_POwner->SetLocalVar("CarefulPathSnapMax", m_POwner->GetLocalVar("CarefulPathSnapMax") + 1);
            m_POwner->SetLocalVar("CarefulPathSnapMin", m_POwner->GetLocalVar("CarefulPathSnapMin") + 1);

            // recalculate path by:
            // -- backpedaling a few yalms away from the destination, snap to valid point, then clear path
            targetPoint = m_points[m_points.size() - 1];
            // below can NaN if points are close enough
            if (abs(targetPoint.x - m_POwner->loc.p.x) > .1f)
                m_POwner->loc.p.x += 2 * (targetPoint.x - m_POwner->loc.p.x) / abs(targetPoint.x - m_POwner->loc.p.x);
            if (abs(targetPoint.z - m_POwner->loc.p.z) > .1f)
                m_POwner->loc.p.z += 2 * (targetPoint.z - m_POwner->loc.p.z) / abs(targetPoint.z - m_POwner->loc.p.z);
            m_POwner->loc.zone->m_navMesh->snapToValidPosition(m_POwner->loc.p);
            startingPoint = m_POwner->loc.p;
            Clear();
            FindClosestPath(startingPoint, targetPoint);
            m_POwner->SetLocalVar("CarefulPathSnapCount", 0);
            return;
        }

Curious if LSB is interested in me cleaning it up, style-wise, and creating a PR. I'm not positive the logic can be changed much to solve the problem, but I'm open to that as well of course.

[bendangelo]

Hi, I originally implemented the navmeshes. What map is this on? It might be better to redo the navmesh so nothing can get stuck. But I'm not against putting this in to fix exploits.

[MowFord]

dynamis sandy is a clear case. The small doorway in this area

allows you to pull from the east side, then run around towards the east gate entryway and the mob will stay stuck on that wall

[bendangelo]

Thanks for the info. Do all dynamis maps have this issue? I can look into making a fix. I'm assuming on retail the mobs would cleanly run around and never get stuck?

[MowFord]

it's not only dynamis, it's anywhere the opening juts out a bit (i.e. a doorway, etc)

my code above fixes it by just determining that a mob is trying to pathTo but not moving, so it refuses to snap to a valid navmesh point for 1 tick, then if it keeps happening that value increases (the "sloppiness" referenced in the comments)

I'm not sure the navmeshes need a fix tbh. I think it's just a matter of needing a better pathing algorithm

[bendangelo]

Ok that makes sense.

[RAIST5150]

Reminds me of the navmesh fixes a while back for bushes and such... used to be you could range pull through them and they would get stuck behind them.

Another targeted navmesh fix would be nice if that is possible, but that may prove quite challenging if the chokes are map layout specific. An extra layer of logic to catch things could be a nice countermeasure until such fixes can be made.

[bendangelo]

ok thanks for the info. I will spend some time looking into this. On retail would the mob run through the bush, run around it or get stuck? I need to know how to fix this.

[RAIST5150]

ok thanks for the info. I will spend some time looking into this. On retail would the mob run through the bush, run around it or get stuck? I need to know how to fix this.

The bush and around corners thing got fixed a good year or so back... maybe longer.

Was a big cheezing tactic in places like Escha Ru'aun. Could get a pack of mobs to clump at the end of a wall or behind a bush, step back a bit and just AOE spam them down.

Now you get the '"cannot see', 'cannot attack" type of messages.

Now that I think on it... May not have actually been a navmesh change. Could have been some form of line of sight change?

[bendangelo]

Yeah looks like a client change. It was probably easier on their end to just stop the player from casting spells lol. Ok thanks for the info. I think ideally it'll run through whatever things a player can.

[WinterSolstice8]

No, it was not a client change. This got ported in from Eden.

#3524

[bendangelo]

Hey, from my research it looks like retail doesn't use navmeshes at all. There was a video of a FFXI dev mentioning how it was such a pain placing all the mob waypoints. It looks like mobs roam using a waypoint system. In battles the mob will just run directly towards you unless there is a "wall" infront of it, at that point it will run towards the closest waypoint until it gets visibility of you. This explains some of the wonkiness.

I think going forward it makes sense to keep the navmeshes (who wants to place thousands of waypoints?) and just fix the player chasing code.