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.