Python Libtcod: How to do pathfinding with variable move cost terrain?

Question

I am building a turn-based strategy game using Libtcod and Python. The game map has variable terrain and each tile can be 1 of 5 types:

• Plains - Costs 1 to move over
• Forest - Costs 2
• River - Costs 4
• Hill - Costs 3
• Mountain - Impassable

Each type has its own movement cost, so that it costs less "move points" to move through plains than through a forest, for example. I want to display all the squares a unit can move to given its movement range/starting move points.

Libtcod has pathfinding functionality built for both A* and Dijtskra and it is trivial to display all the squares in a given range, without accounting for terrain.

However, I cannot figure out how I can implement the terrain costs, without having to write my own pathfinding algorithm. Looking at the docs I know it has something to do with:

def path_func(xFrom,yFrom,xTo,yTo,userData) : ... path_new_using_function(width, height, path_func, user_data=0, diagonalCost=1.41) dijkstra_new_using_function(width, height, path_func, user_data=0, diagonalCost=1.41)

but I cannot figure out what the custom function is supposed to do. According to the docs, it supposed to

...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.

but, isn't that the point of the dijtskra algorithm to begin with? That is, the algorithm is supposed to take into account the variable costs of each tile and then build a path accordingly.

The map itself already has the terrain and move costs applied to it, I just need a way to bridge that data with the pathfinding.

Answer 1

I made my own implementation of the A* algorithm for aesthetic walk path generation; which included bridges which were placed only when they could, according to A*, considering an added step count:

https://github.com/lillian-lemmer/sshrpg/blob/master/plotbrush/mapgen.py#L622

As you can see, all you need to do is manipulate the A* algorithm is to increase the the tentative score (cost from start) for particular types/attributes of tiles/points on the map.

If you look on line 660 I increase the tentative_g_score (cost from start) by eight for water, so this is like saying "only build a bridge if the alternative is walking 8~ steps to get around it." Including tile data with your A* algorithm, and not just the cartesian coordinates, is a great way to perform adjustments to the algorithm based on attributes of the map.

Answer 2

As far as I understand, what you want to achieve is very well possible with tcod's built-in pathfinding function.

path_new_using_function will call your path_func with adjacent cells, so you can simply have it return the values you listed above depending on the terrain below (xFrom, yFrom) and/or (xTo, yTo).