¶ Overview
Initially, every unit occupies one tile on a map and standing still. Regardless of unit rendering, unit is always standing at the central point of the tile. Movement always starts and finishes at the central point of the tile. Transition from tile to tile is always transactional and unit cannot leave the tile, but not enter the other one. Unit starts the movement with C2S::UNIT_COMMAND::CMD_MOVE_TO command sent to a server. Argument contains path that units wants to traverse. Server verifies that path is valid and if so, server sets unit for a movement.
¶ Path validation
Server validates suggested path when receives C2S::UNIT_COMMAND::CMD_MOVE_TO command. Validation rules are the following:
- Path is a sequence of tiles where each may be reached from the previous one.
- Path is within map boundaries.
- Starting point of the path matches unit position.
If path is considered as invalid then S2C::ERROR message is sent by a server and client shall terminate movement of the unit. Additionally, server sends S2C::UNIT_STOP command declaring actual position of the unit violating the movements. Client shall reposition the unit accordingly. This should not happen with honest clients.
¶ Path simulation
If path is considered as valid by the server, then two mirroring movements start simultaneously:
- Client simulates the movement of the unit along the declared path
- Server simulates the movement of the unit along the declared path
Both client and server recalculate visibility area and fog of war as unit moves along the path. They are not synching the data and server holds the master data for the movement. Client-based simulation is always a little bit ahead of server-based simulation due to the network lag of initial C2S::UNIT_COMMAND::CMD_MOVE_TO message.
¶ Timings and Speed
Each unit passes the map with its own speed measured in meters per second. To complete transition from a tile to a neighbouring tile unit needs to go from one central point to the other. Time required is distance between tile centers divided by unit speed. Transition from one tile to the other happens on the border between the tiles.
¶ Hitting an obstacle
It may happen that unit starts transition to the next tile at the border, but it is not passable at all or currently occupied by another unit. This is possible either on purpose by malicious client or rarely for honest clients (e.g., when two units simultaneously compete for a cell to occupy). In this case, unit which cannot transit to the next tile on a path will put its path on hold right at the exact moment of transition (at transition point). Both client and server should simulate this event to stay coherent. Unit tries to reoccupy target tile continuously every 100ms until one of two events happen:
- Next tile on a path is unblocked and unit continues the movement
- Client sends C2S::UNIT_COMMAND::CMD_STOP command to stop movement of the unit. Unit is at transition point between the tiles and both server and a client need to simulates its way back to a tile center.
¶ Extending a path
Client may extend existing unit path by sending additional C2S::UNIT_COMMAND::CMD_MOVE_TO command to already moving unit. Newly suggested path in the command shall start from the previously declared destination tile and it will be concatenated to all previously sent paths to form a single unit path. In order for the command to initiate a new path, not the extension, unit must be stopped first (forcedly by a server or by a client).
¶ Stopping the movement
Movement is stopped either by a server sending S2C::UNIT_STOP or by client sending C2S::UNIT_COMMAND::CMD_STOP. There are only a few situations when server decides to stop the movement and enforce certain position for a unit:
- Next tile on a unit path is occupied by another unit or not passable. In this case stop is temporary and both client and server should put transition on hold until the next tile is unblocked or client stops unit movement. Path simulation is on hold.
- Initial path or extension path suggested by C2S::UNIT_COMMAND::CMD_MOVE_TO command is invalid and server sends S2C::UNIT_STOP to reinforce actual position of this unit. This is client mistake and path simulation does not start.
- Unit reached the destination point on a path and path was not extended by a client. Path simulation is completed.
Every time server stops the unit, it also sends the reason behind the stop command.
When client sends C2S::UNIT_COMMAND::CMD_STOP it provides to the server a tile where unit needs to be stopped along the path. If provided tile is already behind according to the server simulation, then unit is stopped as soon as possible. CMD_STOP by a client is the way to trim previously declared path.
¶ Dynamic path reconstruction
It is possible and a good practice for a client to construct preliminary full path based on the fog of war data (and sometimes optimistically on non-discovered tiles), but adjust it dynamically as unit goes along the path.
C2S::UNIT_COMMAND::CMD_STOP and C2S::UNIT_COMMAND::CMD_MOVE_TO commands may be used to dynamically reconstruct unit path as it navigates through the map. Initial path suggestion in sent as the first command. If no obstacles along the path, then it may be extended further. However, if there are obstacles, then path can be shortened with CMD_STOP command to avoid collision and then when a new path continuation is found extended again with CMD_MOVE_TO command. These commands can be used many times to adjust path of the unit as it goes.
¶ Client implementation
Let's consider the following example. Player directs Zombie unit to go straight up 12 cells, but it is unclear if there is anything blocking the path in non-discovered tiles.
Optimistic approach to pathfinding:
- Send CMD_MOVE_TO to go up 5 cells. The path is valid and we optimistically assume that there are no obstacles.
- Visibility area moves with the unit and client receives the data about non-discovered tiles on a path. If there are no obstacles, client may send additional CMD_MOVE_TO to extend the path and reach the destination. If non-discovered tiles turn out to be obstacles, then path may be trimmed with CMD_STOP command, and a new path extension will be sent via CMD_MOVE_TO to avoid collision with obstacles.
Pessimistic approach to pathfinding may ignore all non-discovered tiles at all and consider all of them as non-passable. In this case initial path suggested may be built based on fog of war data. It will be longer, but won't hit unexpected obstacles.