← Back to team overview

widelands-dev team mailing list archive

Re: [Merge] lp:~widelands-dev/widelands/findpath_modification into lp:widelands

 

see comment in diff

I know the link with tutorial - very well. If it is about integers I somehow understand it, but objects or std containers are too confusing to me. I know, I should try harder ;)

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

This comment above is not enough?

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


References