Various small code style nits. There is 1 loop that I'm worried about - can you 
please revisit the code there and add an explicit break condition, and/or a 
comment?

Diff comments:

> === modified file 'src/ai/ai_help_structs.cc'
> --- src/ai/ai_help_structs.cc 2017-11-24 09:19:52 +0000
> +++ src/ai/ai_help_structs.cc 2018-02-10 21:04:15 +0000
> @@ -191,8 +191,15 @@
>       return false;
>  }
>  
> -NearFlag::NearFlag(const Flag& f, int32_t const c, int32_t const d)
> -   : flag(&f), cost(c), distance(d) {
> +NearFlag::NearFlag(const Flag& f, int32_t const c)
> +   : flag(&f), current_road_distance(c) {
> +     to_be_checked = true;
> +}
> +
> +NearFlag::NearFlag() {
> +     flag = nullptr;

It would be easier to read if you had:

NearFlag::NearFlag() : NearFlag(nullptr, 0) {}

> +     current_road_distance = 0;
> +     to_be_checked = true;
>  }
>  
>  EventTimeQueue::EventTimeQueue() {
> 
> === modified file 'src/ai/defaultai.cc'
> --- src/ai/defaultai.cc       2018-01-30 11:44:48 +0000
> +++ src/ai/defaultai.cc       2018-02-10 21:04:15 +0000
> @@ -3278,94 +3306,153 @@
>       // is connected to a warehouse?
>       const bool needs_warehouse = flag.get_economy()->warehouses().empty();
>  
> -     // Various tests to invoke building of a shortcut (new road)
> -     if (flag.nr_of_roads() == 0 || needs_warehouse) {
> -             create_shortcut_road(flag, 17, 22, gametime);
> -             inhibit_road_building_ = gametime + 800;
> -     } else if (!has_building && flag.nr_of_roads() == 1) {
> -             // This is end of road without any building, we do not initiate 
> interconnection thus
> +     if (!has_building && flag.nr_of_roads() == 1) {
>               return false;
> -     } else if (flag.nr_of_roads() == 1 || std::rand() % 10 == 0) {
> -             if (spots_ > kSpotsEnough) {
> -                     // This is the normal situation
> -                     create_shortcut_road(flag, 15, 22, gametime);
> -                     inhibit_road_building_ = gametime + 800;
> -             } else if (spots_ > kSpotsTooLittle) {
> -                     // We are short of spots so shortening must be 
> significant
> -                     create_shortcut_road(flag, 15, 35, gametime);
> -                     inhibit_road_building_ = gametime + 800;
> -             } else {
> -                     // We are very short of spots so shortening must be 
> even bigger
> -                     create_shortcut_road(flag, 15, 50, gametime);
> -                     inhibit_road_building_ = gametime + 800;
> -             }
> -             // a warehouse with 3 or less roads
>       } else if (is_warehouse && flag.nr_of_roads() <= 3) {
> -             create_shortcut_road(flag, 9, -10, gametime);
> -             inhibit_road_building_ = gametime + 400;
> -             // and when a flag is full with wares
> -     } else if (spots_ > kSpotsEnough && flag.current_wares() > 5) {
> -             create_shortcut_road(flag, 9, -5, gametime);
> -             inhibit_road_building_ = gametime + 400;
> +             ;
> +     } else if (needs_warehouse) {
> +             ;
> +     } else if (flag.current_wares() > 5) {
> +             ;
> +     } else if (has_building && std::rand() % 3 == 0) {
> +             ;
> +     } else if (std::rand() % 10 == 0) {
> +             ;
>       } else {
>               return false;
>       }
>  
> +     int16_t expected_shortcut = 27;
> +     if (has_building) {
> +             expected_shortcut -= 3;
> +     }
> +     expected_shortcut -= flag.current_wares() * 3;
> +     if (is_warehouse) {
> +             expected_shortcut -= 10;
> +     }
> +     if (std::rand() % 5 == 0) {
> +             expected_shortcut -= 10;
> +     }
> +     expected_shortcut -= 2 * flag.nr_of_roads();
> +
> +     create_shortcut_road(flag, 14, expected_shortcut, gametime);
> +
>       return true;
>  }
>  
> -// the function takes a road (road is smallest section of roads with two 
> flags on the ends)
> -// and tries to find alternative route from one flag to another.
> -// if route exists, it is not too long, and current road is not intensively 
> used
> +// This function takes a road (road is smallest section of roads with two 
> flags on the ends)
> +// look for longer section of road that starts and ends with building/road 
> crossing
> +// and tries to find alternative route from one end flag to another.
> +// If route exists, it is not too long, and current road is not intensively 
> used
>  // the road can be dismantled
> -bool DefaultAI::dispensable_road_test(Widelands::Road& road) {
> +bool DefaultAI::dispensable_road_test(const Widelands::Road& road) {
>  
>       Flag& roadstartflag = road.get_flag(Road::FlagStart);
>       Flag& roadendflag = road.get_flag(Road::FlagEnd);
>  
> -     // We do not dismantle (even consider it) if the road is busy (some 
> wares on flags), unless there
> -     // is shortage of build spots
> -
> -     if (spots_ > kSpotsEnough && roadstartflag.current_wares() + 
> roadendflag.current_wares() > 0) {
> +     // Collecting full path (from crossing/building to another 
> crossing/building)
> +     std::vector<Widelands::Flag*> full_road;
> +     full_road.push_back(&roadstartflag);
> +     full_road.push_back(&roadendflag);
> +
> +     // Making sure it starts with proper flag NOCOM

Why the NOCOM?

> +     uint16_t road_length = road.get_path().get_nsteps();
> +
> +     for (int j = 0; j < 2; j++) {

It's common practice to use ++j in C++. Your code works just as well, but 
changing this will make it easier to read for others.

> +             bool new_road_found = true;
> +             while (new_road_found && full_road.back()->nr_of_roads() <= 2 &&
> +                    full_road.back()->get_building() == nullptr) {
> +                     const size_t sz = full_road.size();

It's not clear what "sz" means. Rename it to "full_road_size" or something like 
that.

> +                     new_road_found = false;
> +                     for (uint8_t i = 1; i <= 6; ++i) {
> +                             Road* const near_road = 
> full_road.back()->get_road(i);
> +
> +                             if (!near_road) {
> +                                     continue;
> +                             }
> +
> +                             Flag* other_end;
> +                             if 
> (near_road->get_flag(Road::FlagStart).get_position().hash() ==
> +                                 full_road.back()->get_position().hash()) {
> +                                     other_end = 
> &near_road->get_flag(Road::FlagEnd);
> +                             } else {
> +                                     other_end = 
> &near_road->get_flag(Road::FlagStart);
> +                             }
> +
> +                             if (other_end->get_position() == full_road[sz - 
> 2]->get_position()) {
> +                                     continue;
> +                             }
> +                             full_road.push_back(other_end);
> +                             road_length += 
> near_road->get_path().get_nsteps();
> +                             new_road_found = true;
> +                             break;
> +                     }
> +             }
> +             // we walked to one end, not let revert the concent of 
> full_road and repeat in opposite

now let's revert the content?

> +             // direction
> +             std::reverse(full_road.begin(), full_road.end());
> +     }
> +
> +     // To make decision how intensively the road is used, we count wares on 
> it, but we distinguish
> +     // situation when entire road has only 2 flags or is longer
> +     uint16_t wares_on_road = 0;
> +     assert(full_road.size() > 1);
> +     if (full_road.size() == 2) {
> +             wares_on_road = roadstartflag.current_wares() + 
> roadendflag.current_wares();
> +     } else {
> +             // We count wares only on inner flags
> +             for (uint16_t k = 1; k < full_road.size() - 1; k++) {

++k, see above.

> +                     wares_on_road += full_road[k]->current_wares();
> +             }
> +     }
> +
> +     // If it by chance starts or end next to a warehouse...

ends

> +     if (Building* b = full_road.front()->get_building()) {
> +             BuildingObserver& bo = 
> get_building_observer(b->descr().name().c_str());
> +             if (bo.type == BuildingObserver::Type::kWarehouse) {
> +                     return false;
> +             }
> +     }
> +     if (Building* b = full_road.back()->get_building()) {
> +             BuildingObserver& bo = 
> get_building_observer(b->descr().name().c_str());
> +             if (bo.type == BuildingObserver::Type::kWarehouse) {
> +                     return false;
> +             }
> +     }
> +
> +     if (spots_ > kSpotsEnough && wares_on_road > 5) {
>               return false;
> -     } else if (roadstartflag.current_wares() + roadendflag.current_wares() 
> > 2) {
> +     } else if (wares_on_road > 8) {
>               return false;
>       }
>  
>       std::priority_queue<NearFlag> queue;
>       // only used to collect flags reachable walking over roads
>       std::vector<NearFlag> reachableflags;
> -     queue.push(NearFlag(roadstartflag, 0, 0));
> -     uint8_t pathcounts = 0;
> -     uint8_t checkradius = 0;
> -     if (spots_ > kSpotsEnough) {
> -             checkradius = 7;
> -     } else if (spots_ > kSpotsTooLittle) {
> -             checkradius = 11;
> -     } else {
> -             checkradius = 15;
> +     std::set<uint32_t> existing_road_flags;  // get rid of this

// TODO(tiborb): get rid of this?

> +     for (uint16_t j = 1; j < full_road.size() - 1; j++) {

++j

> +             existing_road_flags.insert(full_road[j]->get_position().hash());
>       }
>  
> +     queue.push(NearFlag(*full_road.front(), 0));
> +     uint16_t alternative_path = std::numeric_limits<uint16_t>::max();
> +     const uint8_t checkradius = 3 * 
> game().map().calc_distance(full_road.front()->get_position(),
> +                                                                
> full_road.back()->get_position());
> +
>       // algorithm to walk on roads
>       while (!queue.empty()) {
>  
> -             // testing if we stand on the roadendflag
> -             // if is is for first time, just go on,
> -             // if second time, the goal is met, function returns true
> -             if (roadendflag.get_position().x == 
> queue.top().flag->get_position().x &&
> -                 roadendflag.get_position().y == 
> queue.top().flag->get_position().y) {
> -                     pathcounts += 1;
> -                     if (pathcounts > 1) {
> -                             // OK, this is a second route how to get to 
> roadendflag
> -                             return true;
> -                     }
> -                     queue.pop();
> -                     continue;
> +             // Testing if we stand on the roadendflag... if yes, the 
> alternative path is found, no reason
> +             // to go on
> +             if (full_road.back()->get_position().x == 
> queue.top().flag->get_position().x &&
> +                 full_road.back()->get_position().y == 
> queue.top().flag->get_position().y) {
> +                     alternative_path = queue.top().current_road_distance;
> +                     break;
>               }
>  
> +             // If we were here, do not evaluate the flag again
>               std::vector<NearFlag>::iterator f =
>                  find(reachableflags.begin(), reachableflags.end(), 
> queue.top().flag);
> -
>               if (f != reachableflags.end()) {
>                       queue.pop();
>                       continue;
> @@ -3382,27 +3470,51 @@
>                               continue;
>                       }
>  
> +                     // alternate road cannot lead via road to be dismantled
> +                     if (near_road->serial() == road.serial()) {
> +                             continue;
> +                     }
> +
>                       Flag* endflag = &near_road->get_flag(Road::FlagStart);
>  
>                       if (endflag == nf.flag) {
>                               endflag = &near_road->get_flag(Road::FlagEnd);
>                       }
>  
> -                     int32_t dist =
> -                        
> game().map().calc_distance(roadstartflag.get_position(), 
> endflag->get_position());
> -
> -                     if (dist > checkradius) {  //  out of range of interest
> +                     // When walking on nearby roads, we do not go too far 
> from start and end of road
> +                     const int32_t dist1 =
> +                        
> game().map().calc_distance(full_road.front()->get_position(), 
> endflag->get_position());
> +                     const int32_t dist2 =
> +                        
> game().map().calc_distance(full_road.back()->get_position(), 
> endflag->get_position());
> +                     if ((dist1 + dist2) > checkradius) {
>                               continue;
>                       }
>  
> -                     queue.push(NearFlag(*endflag, 0, dist));
> +                     const uint32_t new_length = nf.current_road_distance + 
> near_road->get_path().get_nsteps();
> +                     queue.push(NearFlag(*endflag, new_length));
>               }
>       }
> +
> +     if (alternative_path + wares_on_road <= road_length + 12) {
> +             return true;
> +     }
> +
>       return false;
>  }
>  
> -// trying to connect the flag to another one, be it from own economy
> +// Trying to connect the flag to another one, be it from own economy
>  // or other economy
> +// The procedure is:
> +// - Collect all flags within checkradius into RoadCandidates, but first we 
> dont even know if a road
> +// can be built to them
> +// - Walking over road network to collect info on flags that are accessible 
> over road network
> +// - Than merge info from NearFlags to RoadCandidates and consider roads to 
> few best candidates from

Then merge

> +// RoadCandidates. We use score named "reduction" that is basically diff 
> between connection over
> +// existing roads minus possible road from starting flag to candidate flag. 
> Of course there are two
> +// special cases:
> +// - the candidate flag does not belong to the same economy, so no road 
> connection exists
> +// - they are from same economy, but are connected beyond range of 
> checkradius, so actual length of
> +// connection is not known
>  bool DefaultAI::create_shortcut_road(const Flag& flag,
>                                       uint16_t checkradius,
>                                       int16_t min_reduction,
> @@ -3532,32 +3646,41 @@
>                       // This is a candidate, sending all necessary info to 
> RoadCandidates
>                       const bool different_economy = 
> (player_immovable->get_economy() != flag.get_economy());
>                       const int32_t air_distance = 
> map.calc_distance(flag.get_position(), reachable_coords);
> -                     RoadCandidates.add_flag(reachable_coords, air_distance, 
> different_economy);
> +                     if 
> (!RoadCandidates.has_candidate(reachable_coords.hash())) {
> +                             RoadCandidates.add_flag(reachable_coords, 
> air_distance, different_economy);
> +                     }
>               }
>       }
>  
>       // now we walk over roads and if field is reachable by roads, we change 
> the distance assigned
>       // above
> -     std::priority_queue<NearFlag> queue;
> -     std::vector<NearFlag> nearflags;  // only used to collect flags 
> reachable walk over roads
> -     queue.push(NearFlag(flag, 0, 0));
> +     std::map<uint32_t, NearFlag> nearflags;  // only used to collect flags 
> reachable walk over roads
> +     nearflags[flag.get_position().hash()] = NearFlag(flag, 0);
>  
>       // algorithm to walk on roads
> -     while (!queue.empty()) {
> -             std::vector<NearFlag>::iterator f =
> -                find(nearflags.begin(), nearflags.end(), queue.top().flag);
> -
> -             if (f != nearflags.end()) {
> -                     queue.pop();
> -                     continue;
> -             }
> -
> -             nearflags.push_back(queue.top());
> -             queue.pop();
> -             NearFlag& nf = nearflags.back();
> -
> +     // All nodes are marked as to_be_checked and under some conditions, the 
> same node can be checked
> +     // twice
> +     for (;;) {

Are you sure that this loop will always terminate? It's not obvious from the 
code.

> +             // looking for a node with shortest existing road distance from 
> starting flag and one that has
> +             // to be checked
> +             uint32_t start_field = std::numeric_limits<uint32_t>::max();
> +             uint32_t nearest_distance = 10000;
> +             for (auto item : nearflags) {
> +                     if (item.second.current_road_distance < 
> nearest_distance && item.second.to_be_checked) {
> +                             nearest_distance = 
> item.second.current_road_distance;
> +                             start_field = item.first;
> +                     }
> +             }
> +             // OK, so no node to be checked - quitting now
> +             if (start_field == std::numeric_limits<uint32_t>::max()) {
> +                     break;
> +             }
> +
> +             nearflags[start_field].to_be_checked = false;
> +
> +             // Now going over roads leading from this flag
>               for (uint8_t i = 1; i <= 6; ++i) {
> -                     Road* const road = nf.flag->get_road(i);
> +                     Road* const road = 
> nearflags[start_field].flag->get_road(i);
>  
>                       if (!road) {
>                               continue;
> @@ -3565,68 +3688,111 @@
>  
>                       Flag* endflag = &road->get_flag(Road::FlagStart);
>  
> -                     if (endflag == nf.flag) {
> +                     if (endflag == nearflags[start_field].flag) {
>                               endflag = &road->get_flag(Road::FlagEnd);
>                       }
>  
> -                     int32_t dist = map.calc_distance(flag.get_position(), 
> endflag->get_position());
> -
> -                     if (dist > checkradius + 5) {  //  Testing bigger 
> vicinity then checkradius....
> +                     const uint32_t endflag_hash = 
> endflag->get_position().hash();
> +
> +                     const int32_t dist = 
> map.calc_distance(flag.get_position(), endflag->get_position());
> +
> +                     if (dist > checkradius + 2) {  //  Testing bigger 
> vicinity then checkradius....
>                               continue;
>                       }
>  
> -                     queue.push(NearFlag(*endflag, nf.cost + 
> road->get_path().get_nsteps(), dist));
> +                     // There is few scenarios for this neighbour flag
> +                     if (nearflags.count(endflag_hash) == 0) {
> +                             // This is brand new flag
> +                             nearflags[endflag_hash] =
> +                                NearFlag(*endflag, 
> nearflags[start_field].current_road_distance +
> +                                                      
> road->get_path().get_nsteps());
> +                     } else {
> +                             // We know about this flag already
> +                             if 
> (nearflags[endflag_hash].current_road_distance >
> +                                 
> nearflags[start_field].current_road_distance + road->get_path().get_nsteps()) 
> {
> +                                     // ..but this current connection is 
> shorter than one found before
> +                                     
> nearflags[endflag_hash].current_road_distance =
> +                                        
> nearflags[start_field].current_road_distance + road->get_path().get_nsteps();
> +                                     // So let re-check neighbours once more
> +                                     nearflags[endflag_hash].to_be_checked = 
> true;
> +                             }
> +                     }
>               }
>       }
>  
>       // Sending calculated walking costs from nearflags to RoadCandidates to 
> update info on
>       // Candidate flags/roads
>       for (auto& nf_walk : nearflags) {
> -             if (map.calc_distance(flag.get_position(), 
> nf_walk.flag->get_position()) <= checkradius) {
> -                     // nearflags contains also flags beyond the radius, so 
> we skip these
> -                     RoadCandidates.set_road_distance(
> -                        nf_walk.flag->get_position(), 
> static_cast<int32_t>(nf_walk.cost));
> +             // NearFlag contains also flags beyond check radius, these are 
> not relevent for us
> +             if 
> (RoadCandidates.has_candidate(nf_walk.second.flag->get_position().hash())) {
> +                     RoadCandidates.set_cur_road_distance(
> +                        nf_walk.second.flag->get_position(), 
> nf_walk.second.current_road_distance);
>               }
>       }
>  
> -     // We do not calculate roads to all nearby flags, ideally we 
> investigate 4 roads, but the number
> -     // can be higher if a road cannot be built to considered flag. The 
> logic is: 2 points for
> -     // possible
> -     // road, 1 for impossible, and count < 10 so in worst scenario we will 
> calculate 10 impossible
> -     // roads without finding any possible
> -     uint32_t count = 0;
> +     // Here we must consider how much are buildable fields lacking
> +     // the number will be transformed to a weight passed to findpath 
> function
> +     int32_t fields_necessity = 0;
> +     if (spots_ < kSpotsTooLittle) {
> +             fields_necessity += 10;
> +     }
> +     if (map_allows_seafaring_ && num_ports == 0) {
> +             fields_necessity += 10;
> +     }
> +     if (num_ports < 4) {
> +             fields_necessity += 5;
> +     }
> +     if (spots_ < kSpotsEnough) {
> +             fields_necessity += 5;
> +     }
> +     fields_necessity *= 
> std::abs(management_data.get_military_number_at(64)) * 5;
> +
> +     // We need to sort these flags somehow, because we are not going to 
> investigate all of them
> +     // so sorting first by current road lenght (that might contain fake 
> values for flags that were

length

> +     // not reached over roads) and secondary by air_distance (nearer flags 
> first)
> +     std::sort(std::begin(RoadCandidates.flags_queue), 
> std::end(RoadCandidates.flags_queue),
> +               [](const FlagsForRoads::Candidate& a, const 
> FlagsForRoads::Candidate& b) {
> +                       // Here we are doing a kind of bucketing
> +                       const int32_t a_length = a.current_road_length / 50;
> +                       const int32_t b_length = b.current_road_length / 50;
> +                       return std::tie(b_length, a.air_distance) < 
> std::tie(a_length, b.air_distance);
> +               });
> +
> +     // Now we calculate roads from here to few best looking 
> RoadCandidates....
> +     uint32_t possible_roads_count = 0;
>       uint32_t current = 0;  // hash of flag that we are going to calculate 
> in the iteration
> -     while (count < 10 && RoadCandidates.get_best_uncalculated(&current)) {
> +     while (possible_roads_count < 5 && 
> RoadCandidates.get_best_uncalculated(&current)) {
>               const Widelands::Coords coords = Coords::unhash(current);
> -
>               Path path;
>  
>               // value of pathcost is not important, it just indicates, that 
> the path can be built
> -             const int32_t pathcost = map.findpath(flag.get_position(), 
> coords, 0, path, check);
> +             // We send this information to RoadCandidates, with length of 
> possible road if applicable
> +             const int32_t pathcost =
> +                map.findpath(flag.get_position(), coords, 0, path, check, 0, 
> fields_necessity);
>               if (pathcost >= 0) {
>                       RoadCandidates.road_possible(coords, path.get_nsteps());
> -                     count += 2;
> -             } else {
> -                     RoadCandidates.road_impossible(coords);
> -                     count += 1;
> +                     possible_roads_count += 1;
>               }
>       }
>  
> -     // Well and finally building the winning road
> +     // re-sorting again, now by reduction score (custom operator specified 
> in .h file)
> +     std::sort(std::begin(RoadCandidates.flags_queue), 
> std::end(RoadCandidates.flags_queue));
> +
> +     // Well and finally building the winning road (if any)
>       uint32_t winner_hash = 0;
>       if (RoadCandidates.get_winner(&winner_hash)) {
>               const Widelands::Coords target_coords = 
> Coords::unhash(winner_hash);
>               Path& path = *new Path();
>  #ifndef NDEBUG
> -             const int32_t pathcost = map.findpath(flag.get_position(), 
> target_coords, 0, path, check);
> +             const int32_t pathcost =
> +                map.findpath(flag.get_position(), target_coords, 0, path, 
> check, 0, fields_necessity);
>               assert(pathcost >= 0);
>  #else
> -             map.findpath(flag.get_position(), target_coords, 0, path, 
> check);
> +             map.findpath(flag.get_position(), target_coords, 0, path, 
> check, 0, fields_necessity);
>  #endif
>               game().send_player_build_road(player_number(), path);
>               return true;
>       }
> -
>       // if all possible roads skipped
>       if (last_attempt_) {
>               Building* bld = flag.get_building();


-- 
https://code.launchpad.net/~widelands-dev/widelands/findpath_modification/+merge/337103
Your team Widelands Developers is subscribed to branch 
lp:~widelands-dev/widelands/findpath_modification.

_______________________________________________
Mailing list: https://launchpad.net/~widelands-dev
Post to     : widelands-dev@lists.launchpad.net
Unsubscribe : https://launchpad.net/~widelands-dev
More help   : https://help.launchpad.net/ListHelp

Reply via email to