widelands-dev team mailing list archive
-
widelands-dev team
-
Mailing list archive
-
Message #12529
Re: [Merge] lp:~widelands-dev/widelands/findpath_modification into lp:widelands
I am hopelessly lost in regard to pointers and references and I am afraid it will never get better.
Also see comment in the code...
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
> + if (start_field == std::numeric_limits<uint32_t>::max()) {
> + break;
> + }
> +
If there are no more NearFlags with to_be_checked = true, the code quits (above). Each checked NearFlag is (below) set to_be_checked = false.
> + 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.
References