User:SXX/Pathfinding and movement

Introduction

This article is created because I don't really want to put tons of obvious comments into the code, but in same time I believe that article like that would help a lot to anyone who decide to understand pathfinding and movement of VCMI.

Ideas for improvements

1. Make pathfinding via teleport channels cheat-proof.

   Currently to have options allowTeleportOneWay and allowTeleportOneWayRandom works client pathfinder using data about channels which include teleporters that player yet have to see. E.g to be exact sure player can see if one-way teleporter have one or more exits.

2. Recreate pathing information when hero stacks has changed (e.g dismiss).

   This is needed for pathfinding through whirlpools. E.g we automatically enable it for heroes that only have one unit in one stack.

   This may be also useful for movement cost as far as I get.

Client specific

Step by step movement in CPlayerInterface::doMoveHero

This is text representation of what for loop code doing except some useless things like sounds.

1. Initialize outTeleportObj with nullptr
2. Initialize tileAfterThis = true. This variable used to determine we want to visit object or do transit movement
3. Check if node after next one is present, if so:
   1. set tileAfterThis = true.
   2. Check if tile after next one is CGTeleport object, if so:
      1. Set nextTeleporter = CGTeleport id. This variable used by:

         • CPlayerInterface::requestRealized to check if we're moving via teleporter. Then it's not going to set CONTINUE_MOVE as showTeleportDialog should do that.
         • CPlayerInterface::showTeleportDialog to choose where we want teleport to when it's allowed.

   - - - - - - -

4. If current tile hero staying on is CGTeleport object get it as priorObject
5. If next tile have visitable CGObjectInstance get is as nextObject
6. If nextObject is CGTeleport instance then get it as nextObjectTeleport
7. Now if we see that priorObject and nextObjectTeleport are connected teleporters it's mean we might be teleported on previous movement. Then:
   1. Check if this is our first movement in loop. This would mean that hero is currently staying on teleporter it's need to use. Then:
      1. Set nextTeleporter = nextObjectTeleport id. This is needed as before nextTeleporter wasn't set.
      2. Set stillMoveHero to WAITING_MOVE which means some other code (requestRealized, showTeleportDialog, etc) should allow to say us if we continue movement or stop.
      3. Sent normal movement request, but with destination as current hero position.
      4. Now wait before we get TeleportDialog query and showTeleportDialog set stillMoveHero to CONTINUE_MOVE.
   2. Execute continue to jump to next iteration.

   - - - - - - -

8. Check if more than 0 turns is needed to reach next tile. Then:
   1. set StillMoveHero to STOP_MOVE.
   2. Execute break to stop movement loop.

   - - - - - - -

9. set StillMoveHero to WAITING_MOVE. Read above to check why.
10. set endpost to our destination. Tricky part: for the last Z coordinate we use current hero position instead of destination Z coordinate. This is needed because only situation when destination Z and hero Z is different it's when it's movement via teleporters, but current code shouldn't ever used in case of teleportation.

    When I write those lines it's isn't actually this way, but it's have to be.

11. Set guarded if next tile have guarded creature. It's mean we sure that movement will start the battle.

    - - - - - - -

12. Now we need to check if next tile has visitable object, but we want to go through it:

    * Check tileAfterThis is true which means next tile exist

    * Check nextObject isn't nullptr which means we actually have to request transit

    * Check if nextObject->isAllowTransit is true which means next object actually allow transit through it. E.g transit via one way teleporters and events is impossible.

    * Check if nextObjectTeleport and outTeleportObj are not connected. This is needed because we it's possible that more than 2 next objects on our may be teleporters, but we don't only want to visit latest one while transit via remaining.

    1. set "nextTeleporter" to -1 because we now know there won't be TeleportDialog query after this movement.
    2. call moveHero with transit argument.
13. If previous check isn't pass then
    1. if outTeleportObj not nullptr, outTeleportObj->id == nextTeleporter and nextObjectTeleport not connected with outTeleportObj then:
       1. set "nextTeleporter" to -1 for same reason above

          Basically this is mean that next object is not entry teleporter we want to use.

    2. Just call moveHero without transit argument.
14. Now wait before we get TeleportDialog query and showTeleportDialog set stillMoveHero to CONTINUE_MOVE.

    - - - - - - -

15. Check if guarded is true or there dialog appear, then:
    1. Execute "break" to stop movement loop.