Pathfinder

From FIFE development wiki
Jump to: navigation, search


Introduction

The new Pathfinder was introduced with commit 3992. It's based on cell caches and cells, for pathfinding a sort of A* algorithm is used. This made it possible to walk with agents over several layers and add support for multi cell objects.

A cell cache is an abstract depiction of one or a few layers and contains additional information about the playing field. Every cache contains cells, based on the size of the assigned layers. A cell represents a layer coordinate, so if your walkable layer have a width of 20 and a height of 20 then the cache have 400 cells. In addition, contiguous cells are grouped into zones. The cell is the smallest adjustable component in this system.

Together with the new Pathfinder, a new renderer has been released. It can show different cell properties, paths and it is used for a basic Fog of War.

More details: CellRenderer


Components

Cell

A cell is a part of the playing surface, its size dependent on the grid. Cells have default cost and speed multipliers the default value for both is 1.0 but you can change it. The speed multiplier influenced the speed with which an agent moves across the cell. If you set the value to 0.5 the speed is only half as fast, 2.0 doubled the speed.

Cells with lower costs, be used by the pathfinder preferred. Imagine a map with a stone way on grassland and a swamp. Lets say the agent should prefer the stone way but should also be able to run through the swamp and grassland. To achieve this we set the cost multiplier for stone way to 0.25, for swamp to 4.0 and grassland remains 1.0. So to move on a swamp cell is 16 times as expensive as to walk on a stone way and 4 times as expensive as on grassland.


Furthermore the blocking property, which every cell contains, can have five different states:

  • CTYPE_NO_BLOCKER means there is no blocker.
  • CTYPE_STATIC_BLOCKER means there is at least one blocking instance which is static.
  • CTYPE_DYNAMIC_BLOCKER means there is at least one blocking instance which is not static.
  • CTYPE_CELL_NO_BLOCKER means there will never be a blocker. Regardless of the instances on this cell.
  • CTYPE_CELL_BLOCKER means there will always be a blocker. Regardless of the instances on this cell.


You have also the possibility to add your own cell change listener to a cell. It can inform you which instance entered or exited the cell or if the blocking has changed. This is for example useful for location trigger.


To be able to walk to another layer or to beam to another location on the same layer, you have to create transitions. Currently only one transition per cell is allowed.


CellCache

The parent of a cache is a walkable layer. It is possible but not necessary to add interact layers to the walkable layer. The data of the walkable layer and of the interact layers are fused together to one cell cache.

Cell caches have also default cost and speed multipliers as cells. But default cell multipliers based on this cache multipliers. Additionally you can register special costs per cache. A special cost needs an identifier and a value. You can add cells to special costs. It can be used for pathfinding or simply to assign a specific game value to cells.


There is additionally the possibility to split cells in different areas. This makes it possible, for example to divide houses in different parts like kitchen, hallway, bedroom and so on.


The caches have an automatic algo to group cells into zones. The zones are needed to exclude impassable goals. A good example is a house with one closed door and a window. If your agent looks through the window and see the interior, a player could use it as new target for the agent. But if the door is closed no path can be found. Therefore the inner house have a different zone as the square in front of the house. The same problem would arise if a second agent will move on the door cell (if the door is open). In such cases, the zone needs to be updated. To initiate updates narrow cells are used. If it is enabled, the cache seeks those cells themselves, or otherwise do it yourself if you need them. In case no narrow cells are set the zones are static.


There are also a few functions to collect cells, per line, in rect and in circle.


Route

The route contains the search status of the path, the path itself and additional data as occupied cells, cost id, the length of the path, current/old/next positions on the path and so on.


Pathfinder

The Pathfinder can create, solve and follow routes. You can specify if the route should be solved immediately, this skips the normal session search mechanism and solves the path instantly. Otherwise you can set the priority of a search session by default MEDIUM_PRIORITY is used.

If you have registered a special cost id on cell cache then you can here use this cost id for pathfinding.

You can change the maximal allowed path calculation steps. In case the value is too high it can begin to jerk, if the value is too low the paths take longer to be calculated. Default value is 1000.