< index
< 13. Path finding

=====================================
13.1 Creating a path
=====================================

> 13.2 Computing the path

13.1.1. Allocating a pathfinder from a map

First, you have to allocate a path using a map from the Field of view module.

A*:
C++ : TCODPath::TCODPath(const TCODMap *map, float diagonalCost=1.41f)
C   : TCOD_path_t TCOD_path_new_using_map(TCOD_map_t map, float diagonalCost)
Py  : path_new_using_map(map, diagonalCost=1.41)

Dijkstra:
C++ : TCODDijkstra::TCODDijkstra(const TCODMap *map, float diagonalCost=1.41f)
C   : TCOD_dijkstra_t TCOD_dijkstra_new(TCOD_map_t map, float diagonalCost)
Py  : dijkstra_new(map, diagonalCost=1.41)

ParameterDescription
mapThe map. The path finder will use the 'walkable' property of the cells to find a path.
diagonalCostCost of a diagonal movement compared to an horizontal or vertical movement. On a standard cartesian map, it should be sqrt(2) (1.41f).
It you want the same cost for all movements, use 1.0f.
If you don't want the path finder to use diagonal movements, use 0.0f.

Examples:

A*:
C++ : TCODMap *myMap = new TCODMap(50,50);
      TCODPath *path = new TCODPath(myMap); // allocate the path
C   : TCOD_map_t my_map=TCOD_map_new(50,50,true);
      TCOD_path_t path = TCOD_path_new_using_map(my_map,1.41f);
Py  : my_map=libtcod.map_new(50,50,True)
      path = libtcod.path_new_using_map(my_map)

Dijkstra:
C++ : TCODMap *myMap = new TCODMap(50,50);
      TCODDijkstra *dijkstra = new TCODDijkstra(myMap); // allocate the path
C   : TCOD_map_t my_map=TCOD_map_new(50,50,true);
      TCOD_dijkstra_t dijk = TCOD_dijkstra_new(my_map,1.41f);
Py  : my_map=libtcod.map_new(50,50,True)
      dijk = libtcod.dijkstra_new(my_map)

13.1.2. Allocating a pathfinder using a callback

Since the walkable status of a cell may depend on a lot of parameters (the creature type, the weather, the terrain type...), you can also create a path by providing a function rather than relying on a TCODMap.

callback:
C++ : class ITCODPathCallback {
      public: virtual float getWalkCost( int xFrom, int yFrom, int xTo, int yTo, void *userData ) const = 0;
      };
C   : typedef float (*TCOD_path_func_t)( int xFrom, int yFrom, int xTo, int yTo, void *user_data )
Py  : def path_func(xFrom,yFrom,xTo,yTo,userData) : ...

A* constructor:
C++ : TCODPath::TCODPath(int width, int height, const ITCODPathCallback *callback, void *userData, float diagonalCost=1.41f)
C   : TCOD_path_t TCOD_path_new_using_function(int width, int height, TCOD_path_func_t callback, void *user_data, float diagonalCost)
Py  : path_new_using_function(width, height, path_func, user_data=0, diagonalCost=1.41)

Dijkstra constructor:
C++ : TCODDijkstra::TCODDijkstra(int width, int height, const ITCODPathCallback *callback, void *userData, float diagonalCost=1.41f)
C   : TCOD_dijkstra_t TCOD_dijkstra_new_using_function(int width, int height, TCOD_path_func_t callback, void *user_data, float diagonalCost)
Py  : dijkstra_new_using_function(width, height, path_func, user_data=0, diagonalCost=1.41)

ParameterDescription
width,heightThe size of the map (in map cells).
callbackA custom function that must return the walk cost from coordinates xFrom,yFrom to coordinates xTo,yTo.
The cost must be > 0.0f if the cell xTo,yTo is walkable.
It must be equal to 0.0f if it's not.
You must not take additional cost due to diagonal movements into account as it's already done by the pathfinder.
userDataCustom data that will be passed to the function.
diagonalCostCost of a diagonal movement compared to an horizontal or vertical movement. On a standard cartesian map, it should be sqrt(2) (1.41f).
It you want the same cost for all movements, use 1.0f.
If you don't want the path finder to use diagonal movements, use 0.0f.

Example :

C++ : class MyCallback : public ITCODPathCallback {
        public :
        float getWalkCost(int xFrom, int yFrom, int xTo, int yTo, void *userData ) const { ... }
      };
      TCODPath *path = new TCODPath(50,50,new MyCallback(),NULL); // allocate the path
      TCODDijkstra *dijkstra = new TCODDijkstra(50,50,new MyCallback(),NULL); // allocate Dijkstra
C   : float my_func(int xFrom, int yFrom, int xTo, int yTo, void *user_data) { ... }
      TCOD_path_t path = TCOD_path_new_using_function(50,50,my_func,NULL,1.41f);
      TCOD_dijkstra_t dijkstra = TCOD_dijkstra_new_using_function(50,50,my_func,NULL,1.41f);
Py  : def my_func(xFrom, yFrom, xTo, yTo, user_data) :
          # return a float cost for this movement
          return 1.0
      path = libtcod.path_new_using_function(50,50,my_func)
      dijkstra = libtcod.dijkstra_new_using_function(50,50,my_func)