I replied in the diff.

Maybe you need a different tutorial, or to sit down with somebody to teach you. 
That tutorial is maybe too abstract, and you need some exercises to go along 
with it? Or maybe what's confusing you here is the combination of pointers and 
object orientation?

Diff comments:

> 
> === modified file 'src/ai/defaultai.cc'
> --- src/ai/defaultai.cc       2018-02-12 11:43:28 +0000
> +++ src/ai/defaultai.cc       2018-02-13 07:54:42 +0000
> @@ -3537,32 +3647,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 (;;) {
> +             // 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 NearFlag left to be checked - quitting the loop now

No, because it's not obvious that item.second.to_be_checked will become false 
for all items eventually. Otherwise, we wouldn't have this discussion ;)

> +             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;


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