I am using Python with libtcodpy to build a turn-based strategy game.
In this game each unit has a maximum range which varies from 4-10. This range determines how many "steps" the unit can take and therefore the distance it can move on the game map.
I wish to output all the squares which the unit can move to, based upon its range as well as variable terrain, which increases the number of steps necessary to move over it.
This function is what I have to generate these squares and it works but is intolerably slow (takes about 1-2 seconds for the squares to highlight on the map):
#Gets a list of all the squares the unit can move to (so that they
#can be highlighted later)
def get_total_squares(max_range, playerx, playery, team):
global coord_in_range #List where the final coords will be stored
global T_Map #Instance of the Map class, i.e the map
#This iterates through an area of the game map defined by the square
#created by the player's maximum range (where the player is in the center
#of the square)
for x in range((playerx-max_range), (playerx+max_range+1)):
for y in range ((playery-max_range), (playery+max_range+1)):
#This creates a path for every square in the above area
path = libtcod.path_new_using_map(new_map, 0)
#This computes a path to every square in the above area
libtcod.path_compute(path, playerx, playery, x, y)
#This gives the number of steps the unit takes to walk one specific path
num_steps = libtcod.path_size(path)
#This is a blank list which will be populated with the coordinates of
#the tiles of one specific path
coord_of_path = []
#This populates the above list
for i in range(libtcod.path_size(path)):
coord_of_path.append(libtcod.path_get(path, i))
#This is a list of all the tiles in the map which can hinder movement
#henceforth called "terrain_tiles"
terrain_tiles = [tile for tile in T_Map.tile_array
if tile.terrain_name in ('Tall Grass', 'Hills', 'Forest', 'Water')]
#This iterates through all the "terrain tiles" and
#if the tile is in the path, adds that tiles movement penalty
#to the total number of steps to take that path
for tile in terrain_tiles:
if (tile.x, tile.y) in coord_of_path:
num_steps += tile.move_cost
#This is what actually determines whether the path is added to the
#list of walkable paths; if the path's step count, taking into account
#modifications from terrain, is greater than the unit's range that path is not added
if num_steps <=max_range:
for i in range(libtcod.path_size(path)):
coord_in_range.append(libtcod.path_get(path, i))
return coord_in_range
I'm quite certain something in here is acting as a bottleneck and very certain it has something to do with adjusting the paths due to terrain, since if I do it without considering terrain, it runs very fast.
If the full code is necessary (I don't think it should be as, stated above, the problem must lie here) I will post it.
2 Answers 2
What you're trying to compute here is the cost of the unit to travel to each accessible square in the region. You do it by iterating over all squares in the region, computing a path to the destination square, and adding up the cost of getting there.
Suppose that this figure shows the cost of traversing each square, and you have a unit in the square marked A:
┌───┬───┬───┬───┐
│ 1 │ 2 │ 1 │ 1 │
├───┼───┼───┼───┤
│ 2 │ 2 │ 2 │ 1 │
├───┼───┼───┼───┤
│ 1 │ 3 │ 1 │ 1 │
├───┼───┼───┼───┤
│ 1 │ 2 │ 1 │ A │
└───┴───┴───┴───┘
Then your algorithm goes like this:
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
│ * │ . │ . │ . │ │ . │ * │ . │ . │ │ . │ . │ * │ . │ │ . │ . │ . │ * │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤
│ . │ * │ . │ . │ │ . │ * │ . │ . │ │ . │ . │ * │ . │ │ . │ . │ . │ * │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤
│ . │ . │ * │ . │ │ . │ . │ * │ . │ │ . │ . │ * │ . │ │ . │ . │ . │ * │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤
│ . │ . │ . │ A │ │ . │ . │ . │ A │ │ . │ . │ . │ A │ │ . │ . │ . │ A │
└───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘
1 +たす 2 +たす 1 =わ 4 1 +たす 2 +たす 2 =わ 5 1 +たす 2 +たす 1 =わ 4 1 +たす 1 +たす 1 =わ 3
and so on. There is wasted work here, because each path starts again from scratch instead of making use of previously computed information. The point is that after computing the first path above, we already know the following costs:
┌───┬───┬───┬───┐
│ 4 │ . │ . │ . │
├───┼───┼───┼───┤
│ . │ 3 │ . │ . │
├───┼───┼───┼───┤
│ . │ . │ 1 │ . │
├───┼───┼───┼───┤
│ . │ . │ . │ A │
└───┴───┴───┴───┘
and so to compute the second path we can start from the square marked "3" instead of having to start all the way back at A.
If you make this idea into an algorithm then you get Dijkstra's algorithm.
But you may be able to do better than that. If the cost of moving over a square of terrain never changes during the game, then the cost of moving along a path never changes either. So you could pre-compute the cost of all paths (using the Floyd–Warshall algorithm) and remember them.
Great answer by Gareth and references to two great path finding algorithms. I'd like to add to Gareth's answer and address this issue you raise:
I'm quite certain something in here is acting as a bottleneck and very certain it has something to do with adjusting the paths due to terrain, since if I do it without considering terrain, it runs very fast.
I suspect that the libtcod uses an efficient algorithm like Dijkstra's to calculate the paths and the path object does not really contain every path, but rather a path through every point.
As Gareth describes:
There is wasted work here, because each path starts again from scratch instead of making use of previously computed information. The point is that after computing the first path above, we already know the ... costs
I think the reason the terrain cost calculation is so expensive is that, unlike the libtcod, you actually are iterating over EVERY possible path to EVERY point in the map.
Does the libtcod API provide a way to include the cost of movement? If not, I recommend you investigate the A* Algorithm. Here's a good start.