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.

BTW I only list on wiki things that need detailed explanation while more of smaller issues can be found on my Trello.

First of all I'm going to call flying / walking on water as "special movement".

New movement design for special movement support

Currently all movements mechanics is based on fact that server trust to client: server have no idea how pathfinding works and just move hero from tile to tile. Unfortunately it's cause few problems:

1. Client may just stop movement any time, e.g when hero flying over blocked tile or water.

   This can be avoided by adding check on server side that won't let player to finish his turn unless hero is on ACCESSIBLE / VISITABLE tile, but then hero may just don't have enough movement points to move there.

2. On server-side all movement handled by "moveHero" that basically duplicate tons of checks client doing and this code is hard to read and maintain.

So here is my vision how movement must work:

1. Client sending path to server instead of one tile movement.

   If it's multi-turn path then only part for current turn would be sent.

2. Server receive path and then verify it using pathfinder.

   CPathfinder should be able to verify given path without rebuilding whole graph. First of all it's too expensive and also there is nothing bad if client and server run different pathfinding code. As long as path valid and hero have enough movement points it's okay.

3. If path is valid then server start to move hero step-by-step.

   Server still going to wait N.N seconds for client to confirm each hero step. So player will be able to stop movement just like now, but if server decide that it's can't be done then movement going to continue.

   This also solve issue with "events" as server just going to force movement.

Special movement tasks and challenges within pathfinder

1. Some "simple" rules:
   1. Hero with special movement can't stop on water or blocked tiles.
   2. Hero that flying can't go into visitable tiles from blocked one.
   3. For long paths there can't be movement over water or blocked tiles if not fit into one turn.

      The problem is that when special movement is permanent it's harder to implement that limitation within current pathfinder design.

2. Current "automatic" embark/disembark don't work well with special movement.

   Basically you shouldn't be able to visit any objects on water without a boat, but except you have free embark/disembark those will never be visitable while special movement available and your hero isn't in boat.

3. Currently cost calculation for movement in boat are broken when hero isn't in boat yet.

   getMovementCost rework required in order to make it actually usable in pathfinder.

4. Pathfinder is depend on duration of FLYING_MOVEMENT / WATER_WALKING bonuses.

   Currently spells only give them for one turn, but artifacts have permanent effect so it's would be great to support arbitrary number of turns. Basically pathfinder must check number of turns remaining and only build paths using those bonuses only if they'll remain on certain turn.

5. Hard. If hero have both bonuses pathfinder must choose movement type that is cheaper.

   This in fact would add new complexity layer to pathfinding and likely increase cost too. Considering that situation is really rare I'll ignore it for now.

6. Events. Fact that those can be activated within special movement are just plain bad game design.

   My current solution is to force continue hero movement so it's shouldn't be issue at all. Though it's not really related to pathfinder itself.

Unfinished things and thoughts on teleporters support

1. Unification needed for knownTeleportChannels and knownSubterraneanGates

   This data basically have to be in TeamState and not VCAI!

2. Transit via whirlpools

   Shouldn't be possible to move via them unless hero protected.

3. Current exit choice mechanics let you avoid battle.

   There is clear issue that automatic pathfinding via teleporters give you ability to avoid battle that may happen with default H3 mechanics otherwise. Probably auto pathfinding via teleporters must be disabled if any exit is invisible or blocked by enemy hero.

   Anyway it's game design issue and some trade off would be needed.

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.

   There is at least mantis#2098 that related so we need to update pathfinding information in many different cases: new stack appear, artifact equipped, etc.

3. Support for pathfinding via Inferno "Castle Gate".

   It's also possible to teleport from teammate Inferno to your one (but not vice versa).

4. For AI it's would be handy if pathfinder would be able to find shortest way to tile utilizing spells available to hero.
5. Pathfinder must support patrol limitations: mantis#1696

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.