<URL: http://bugs.freeciv.org/Ticket/Display.html?id=19822 >
On 1/17/07, Marko Lindqvist <[EMAIL PROTECTED]> wrote: > This patch removes segment_length and step completely. When segment > or path length is needed, it's determined by extra iteration. I'm > afraid this is unavoidable performance hit. This version of the patch > is for S2_0 since problem was easist to reproduce there. Version for trunk and S2_1. - ML
diff -Nurd -X.diff_ignore freeciv/common/aicore/path_finding.c freeciv/common/aicore/path_finding.c --- freeciv/common/aicore/path_finding.c 2006-07-17 23:56:45.000000000 +0300 +++ freeciv/common/aicore/path_finding.c 2007-01-17 20:29:47.000000000 +0200 @@ -68,9 +68,6 @@ struct danger_node { bool is_dangerous; bool waited; /* TRUE if waited to get here */ - int step; /* # of steps we took to get here */ - int segment_length; /* only used for dangerous tiles, the length - * of the current dangerous streak */ struct pf_danger_pos { enum direction8 dir; int cost; @@ -503,8 +500,6 @@ if (pf_map->params->is_pos_dangerous) { /* The starting point is safe */ pf_map->d_lattice[pf_map->tile->index].is_dangerous = FALSE; - /* Initialize step counter */ - pf_map->d_lattice[pf_map->tile->index].step = 0; } return pf_map; @@ -823,19 +818,35 @@ /*********************************************************************** Creating path segment going back from d_node1 to a safe tile. ***********************************************************************/ -static void create_danger_segment(struct pf_map *pf_map, enum direction8 dir, - struct danger_node *d_node1, int length) +static void create_danger_segment(struct pf_map *pf_map, + struct danger_node *d_node1) { int i; struct tile *ptile = pf_map->tile; struct pf_node *node = &pf_map->lattice[ptile->index]; + struct danger_node *d_node = &pf_map->d_lattice[ptile->index]; + int length = 0; /* Allocating memory */ if (d_node1->danger_segment) { freelog(LOG_ERROR, "Possible memory leak in create_danger_segment"); } + + /* First iteration for determining segment length */ + while(d_node->is_dangerous) { + length++; + ptile = mapstep(ptile, DIR_REVERSE(node->dir_to_here)); + node = &pf_map->lattice[ptile->index]; + d_node = &pf_map->d_lattice[ptile->index]; + } + + /* Allocate memory for segment */ d_node1->danger_segment = fc_malloc(length * sizeof(struct pf_danger_pos)); + /* Reset tile and node pointers for main iteration */ + ptile = pf_map->tile; + node = &pf_map->lattice[ptile->index]; + /* Now fill the positions */ for (i = 0; i < length; i++) { /* Record the direction */ @@ -928,11 +939,6 @@ int loc_cost = (pf_map->status[pf_map->tile->index] != NS_WAITING ? node->cost : node->cost + get_moves_left(pf_map, node->cost)); - /* Step number at xy taking into account waiting - * (waiting counts as one step) */ - int loc_step - = (pf_map->status[pf_map->tile->index] != NS_WAITING ? d_node->step - : d_node->step + 1); /* The previous position is contained in {x,y} fields of map */ adjc_dir_iterate(pf_map->tile, tile1, dir) { @@ -1002,7 +1008,6 @@ node1->extra_cost = extra; node1->cost = cost; node1->dir_to_here = dir; - d_node1->step = loc_step + 1; /* Clear the previously recorded path back */ if (d_node1->danger_segment) { free(d_node1->danger_segment); @@ -1010,15 +1015,11 @@ } if (d_node->is_dangerous) { /* Transition from red to blue, need to record the path back */ - create_danger_segment(pf_map, dir, d_node1, - d_node->segment_length); + create_danger_segment(pf_map, d_node1); } else { /* We don't consider waiting to get to a safe tile as * "real" waiting */ d_node1->waited = FALSE; - if (pf_map->status[pf_map->tile->index] == NS_WAITING) { - d_node1->step--; - } } pf_map->status[index1] = NS_NEW; pq_insert(pf_map->queue, index1, -cost_of_path); @@ -1039,14 +1040,6 @@ node1->extra_cost = extra; node1->cost = cost; node1->dir_to_here = dir; - d_node1->step = loc_step + 1; - if (d_node->is_dangerous) { - /* Increment the number of steps we are making across danger */ - d_node1->segment_length = d_node->segment_length + 1; - } else { - /* We just moved into the danger area */ - d_node1->segment_length = 1; - } pf_map->status[index1] = NS_NEW; d_node1->waited = (pf_map->status[pf_map->tile->index] == NS_WAITING); @@ -1119,6 +1112,8 @@ bool waited = FALSE; struct pf_node *node = &pf_map->lattice[ptile->index]; struct danger_node *d_node = &pf_map->d_lattice[ptile->index]; + int length = 0; + struct tile *iter_tile = ptile; if (pf_map->params->turn_mode != TM_BEST_TIME && pf_map->params->turn_mode != TM_WORST_TIME) { @@ -1126,11 +1121,47 @@ return NULL; } + /* First iterate to find path length */ + while(!same_pos(iter_tile, pf_map->params->start_tile)) { + + if (!d_node->is_dangerous && d_node->waited) { + length += 2; + } else { + length++; + } + + if (!d_node->is_dangerous) { + /* We are in the normal node and dir_to_here field is valid */ + dir_next = node->dir_to_here; + /* d_node->danger_segment is the indicator of what lies ahead + * if it's non-NULL, we are entering a danger segment, + * if it's NULL, we are not on one so danger_seg should be NULL */ + danger_seg = d_node->danger_segment; + segment_index = 0; + } else { + /* We are in a danger segment */ + dir_next = danger_seg[segment_index].dir; + segment_index++; + } + + /* Step backward */ + iter_tile = mapstep(iter_tile, DIR_REVERSE(dir_next)); + node = &pf_map->lattice[iter_tile->index]; + d_node = &pf_map->d_lattice[iter_tile->index]; + } + + /* Allocate memory for path */ path->positions - = fc_malloc((d_node->step + 1) * sizeof(struct pf_position)); - path->length = d_node->step + 1; + = fc_malloc((length + 1) * sizeof(struct pf_position)); + path->length = length + 1; - for (i = d_node->step; i >= 0; i--) { + /* Reset variables for main iteration */ + iter_tile = ptile; + node = &pf_map->lattice[ptile->index]; + d_node = &pf_map->d_lattice[ptile->index]; + waited = FALSE; + + for (i = length; i >= 0; i--) { bool old_waited = FALSE; /* 1: Deal with waiting */ @@ -1138,7 +1169,7 @@ if (waited) { /* Waited at _this_ tile, need to record it twice in the path. * Here we record our state _after_ waiting (e.g. full move points) */ - path->positions[i].tile = ptile; + path->positions[i].tile = iter_tile; path->positions[i].total_EC = node->extra_cost; path->positions[i].turn = get_turn(pf_map, node->cost) + 1; path->positions[i].moves_left = get_move_rate(pf_map->params); @@ -1157,7 +1188,7 @@ } /* 2: Fill the current position */ - path->positions[i].tile = ptile; + path->positions[i].tile = iter_tile; if (!d_node->is_dangerous) { path->positions[i].total_MC = node->cost; path->positions[i].total_EC = node->extra_cost; @@ -1178,7 +1209,7 @@ /* 3: Check if we finished */ if (i == 0) { /* We should be back at the start now! */ - assert(same_pos(ptile, pf_map->params->start_tile)); + assert(same_pos(iter_tile, pf_map->params->start_tile)); return path; } @@ -1198,9 +1229,9 @@ } /* 5: Step further back */ - ptile = mapstep(ptile, DIR_REVERSE(dir_next)); - node = &pf_map->lattice[ptile->index]; - d_node = &pf_map->d_lattice[ptile->index]; + iter_tile = mapstep(iter_tile, DIR_REVERSE(dir_next)); + node = &pf_map->lattice[iter_tile->index]; + d_node = &pf_map->d_lattice[iter_tile->index]; }
_______________________________________________ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev