widelands-dev team mailing list archive

[GunChleoc <fios@xxxxxxxxxxxxxxxxxxx>]

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.