widelands-dev team mailing list archive

[GunChleoc <fios@xxxxxxxxxxxxxxxxxxx>]

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.