text: /*
   * This file is part of the Simutrans project under the Artistic License.
   * (see LICENSE.txt)
   */
  
  #include <algorithm>
  #include "../simdebug.h"
  #include "fabrikbauer.h"
  #include "hausbauer.h"
  #include "../simworld.h"
  #include "../simintr.h"
  #include "../simfab.h"
  #include "../simmesg.h"
  #include "../utils/simrandom.h"
  #include "../simcity.h"
  #include "../simhalt.h"
  #include "../player/simplay.h"
  
  #include "../boden/grund.h"
  
  #include "../dataobj/settings.h"
  #include "../dataobj/environment.h"
  #include "../network/pakset_info.h"
  #include "../dataobj/translator.h"
  
  #include "../tpl/vector_tpl.h"
  #include "../tpl/array_tpl.h"
  #include "../finder/building_placefinder.h"
  
  #include "../utils/cbuffer_t.h"
  
  #include "../descriptor/objversion.h"
  
  #include "../gui/minimap.h" // to update map after construction of new industry
  
  
  karte_ptr_t factory_builder_t::welt;
  
  /// Default factory spacing
  static int DISTANCE = 40;
  
  /// all factories and their exclusion areas
  static array_tpl<uint8> fab_map;
  
  /// width of the factory map
  static sint32 fab_map_w=0;
  
  
  /**
   * Marks factories and their exclusion region in the position map.
   */
  static void add_factory_to_fab_map(karte_t const* const welt, fabrik_t const* const fab)
  {
  	koord3d      const& pos     = fab->get_pos();
  	sint16       const  spacing = welt->get_settings().get_min_factory_spacing();
  	building_desc_t const& bdsc  = *fab->get_desc()->get_building();
  	uint8        const  rotate  = fab->get_rotate();
  	sint16       const  start_y = max(0, pos.y - spacing);
  	sint16       const  start_x = max(0, pos.x - spacing);
  	sint16       const  end_y   = min(welt->get_size().y - 1, pos.y + bdsc.get_y(rotate) + spacing);
  	sint16       const  end_x   = min(welt->get_size().x - 1, pos.x + bdsc.get_x(rotate) + spacing);
  	for (sint16 y = start_y; y < end_y; ++y) {
  		for (sint16 x = start_x; x < end_x; ++x) {
  			fab_map[fab_map_w * y + x / 8] |= 1 << (x % 8);
  		}
  	}
  }
  
  
  /**
   * Creates map with all factories and exclusion area.
   */
  void init_fab_map( karte_t *welt )
  {
  	fab_map_w = ((welt->get_size().x+7)/8);
  	fab_map.resize( fab_map_w*welt->get_size().y );
  	for( int i=0;  i<fab_map_w*welt->get_size().y;  i++ ) {
  		fab_map[i] = 0;
  	}
  	FOR(slist_tpl<fabrik_t*>, const f, welt->get_fab_list()) {
  		add_factory_to_fab_map(welt, f);
  	}
  	if(  welt->get_settings().get_max_factory_spacing_percent() > 0  ) {
  		DISTANCE = (welt->get_size_max() * welt->get_settings().get_max_factory_spacing_percent()) / 100l;
  	}
  	else {
  		DISTANCE = welt->get_settings().get_max_factory_spacing();
  	}
  }
  
  
  /**
   * @param x,y world position, needs to be valid coordinates
   * @returns true, if factory coordinate
   */
  inline bool is_factory_at(sint16 x, sint16 y)
  {
  	uint32 idx = (fab_map_w*y)+(x/8);
  	return idx < fab_map.get_count()  &&  (fab_map[idx]&(1<<(x%8)))!=0;
  }
  
  
  void factory_builder_t::new_world()
  {
  	init_fab_map( welt );
  }
  
  
  /**
   * Searches for a suitable building site using suche_platz().
   * The site is chosen so that there is a street next to the building site.
   */
  class factory_site_searcher_t: public building_placefinder_t  {
  
  	factory_desc_t::site_t site;
  public:
  	factory_site_searcher_t(karte_t* welt, factory_desc_t::site_t site_) : building_placefinder_t(welt), site(site_) {}
  
  	bool is_area_ok(koord pos, sint16 w, sint16 h, climate_bits cl) const OVERRIDE
  	{
  		if(  !building_placefinder_t::is_area_ok(pos, w, h, cl)  ) {
  			return false;
  		}
  		uint16 mincond = 0;
  		uint16 condmet = 0;
  		switch(site) {
  			case factory_desc_t::forest:
  				mincond = w*h+w+h; // at least w*h+w+h trees, i.e. few tiles with more than one tree
  				break;
  
  			case factory_desc_t::shore:
  			case factory_desc_t::river:
  			case factory_desc_t::City:
  			default:
  				mincond = 1;
  		}
  
  		// needs to run one tile wider than the factory on all sides
  		for (sint16 y = -1;  y <= h; y++) {
  			for (sint16 x = -1; x <= w; x++) {
  				koord k(pos + koord(x,y));
  				grund_t *gr = welt->lookup_kartenboden(k);
  				if (!gr) {
  					return false;
  				}
  				// do not build on an existing factory
  				if( is_factory_at(k.x, k.y)  ) {
  					return false;
  				}
  				if(  0 <= x  &&  x < w  &&  0 <= y  &&  y < h  ) {
  					// actual factorz tile: is there something top like elevated monorails?
  					if(  gr->get_leitung()!=NULL  ||  welt->lookup(gr->get_pos()+koord3d(0,0,1)  )!=NULL) {
  						// something on top (monorail or power lines)
  						return false;
  					}
  					// check for trees unless the map was generated without trees
  					if(  site==factory_desc_t::forest  &&  welt->get_settings().get_tree_distribution()!=settings_t::TREE_DIST_NONE  &&  condmet < mincond  ) {
  						for(uint8 i=0; i< gr->get_top(); i++) {
  							if (gr->obj_bei(i)->get_typ() == obj_t::baum) {
  								condmet++;
  							}
  						}
  					}
  				}
  				else {
  					// border tile: check for road, shore, river
  					if(  condmet < mincond  &&  (-1==x  ||  x==w)  &&  (-1==y  ||  y==h)  ) {
  						switch (site) {
  							case factory_desc_t::City:
  								condmet += gr->hat_weg(road_wt);
  								break;
  							case factory_desc_t::shore:
  								condmet += welt->get_climate(k)==water_climate;
  								break;
  							case factory_desc_t::river:
  							if(  welt->get_settings().get_river_number() >0  ) {
  								weg_t* river = gr->get_weg(water_wt);
  								if (river  &&  river->get_desc()->get_styp()==type_river) {
  									condmet++;
  									DBG_DEBUG("factory_site_searcher_t::is_area_ok()", "Found river near %s", pos.get_str());
  								}
  								break;
  							}
  							else {
  								// always succeeds on maps without river ...
  								condmet++;
  								break;
  							}
  							default: ;
  						}
  					}
  				}
  			}
  		}
  		if(  site==factory_desc_t::forest  &&  condmet>=3  ) {
  			dbg->message("", "found %d at %s", condmet, pos.get_str() );
  		}
  		return condmet >= mincond;
  	}
  };
  
  
  stringhashtable_tpl<const factory_desc_t *> factory_builder_t::desc_table;
  
  
  /**
   * Compares factory descriptors by their name.
   * Used in get_random_consumer().
   * @return true, if @p a < @p b, false otherwise.
   */
  static bool compare_fabrik_desc(const factory_desc_t* a, const factory_desc_t* b)
  {
  	const int diff = strcmp( a->get_name(), b->get_name() );
  	return diff < 0;
  }
  
  
  // returns a random consumer
  const factory_desc_t *factory_builder_t::get_random_consumer(bool electric, climate_bits cl, uint16 timeline )
  {
  	// get a random city factory
  	weighted_vector_tpl<const factory_desc_t *> consumer;
  
  	FOR(stringhashtable_tpl<factory_desc_t const*>, const& i, desc_table) {
  		factory_desc_t const* const current = i.value;
  		// only insert end consumers
  		if (  current->is_consumer_only()  &&
  			current->get_building()->is_allowed_climate_bits(cl)  &&
  			(electric ^ !current->is_electricity_producer())  &&
  			current->get_building()->is_available(timeline)  ) {
  				consumer.insert_unique_ordered(current, current->get_distribution_weight(), compare_fabrik_desc);
  		}
  	}
  	// no consumer installed?
  	if (consumer.empty()) {
  DBG_MESSAGE("factory_builder_t::get_random_consumer()","No suitable consumer found");
  		return NULL;
  	}
  	// now find a random one
  	factory_desc_t const* const fd = pick_any_weighted(consumer);
  	DBG_MESSAGE("factory_builder_t::get_random_consumer()", "consumer %s found.", fd->get_name());
  	return fd;
  }
  
  
  const factory_desc_t *factory_builder_t::get_desc(const char *factory_name)
  {
  	return desc_table.get(factory_name);
  }
  
  
  void factory_builder_t::register_desc(factory_desc_t *desc)
  {
  	uint16 p=desc->get_productivity();
  	if(p&0x8000) {
  		koord k=desc->get_building()->get_size();
  
  		// to be compatible with old factories, since new code only steps once per factory, not per tile
  		desc->set_productivity( (p&0x7FFF)*k.x*k.y );
  DBG_DEBUG("factory_builder_t::register_desc()","Correction for old factory: Increase production from %i by %i",p&0x7FFF,k.x*k.y);
  	}
  	if(  const factory_desc_t *old_desc = desc_table.remove(desc->get_name())  ) {
  		dbg->doubled( "factory", desc->get_name() );
  		delete old_desc;
  	}
  	desc_table.put(desc->get_name(), desc);
  }
  
  
  bool factory_builder_t::successfully_loaded()
  {
  	FOR(stringhashtable_tpl<factory_desc_t const*>, const& i, desc_table) {
  		factory_desc_t const* const current = i.value;
  		if(  field_group_desc_t * fg = const_cast<field_group_desc_t *>(current->get_field_group())  ) {
  			// initialize weighted vector for the field class indices
  			fg->init_field_class_indices();
  		}
  		// check for crossconnects
  		for(  int j=0;  j < current->get_supplier_count();  j++  ) {
  			weighted_vector_tpl<const factory_desc_t *>producer;
  			find_producer( producer, current->get_supplier(j)->get_input_type(), 0 );
  			if(  producer.is_contained(current)  ) {
  				// must not happen else
  				dbg->fatal( "factory_builder_t::successfully_loaded()", "Factory %s output %s cannot be its own input!", i.key, current->get_supplier(j)->get_input_type()->get_name() );
  			}
  		}
  		checksum_t *chk = new checksum_t();
  		current->calc_checksum(chk);
  		pakset_info_t::append(current->get_name(), obj_factory, chk);
  	}
  	return true;
  }
  
  
  int factory_builder_t::count_producers(const goods_desc_t *ware, uint16 timeline)
  {
  	int count=0;
  
  	// iterate over all factories and check if they produce this good...
  	FOR(stringhashtable_tpl<factory_desc_t const*>, const& t, desc_table) {
  		factory_desc_t const* const tmp = t.value;
  		for (uint i = 0; i < tmp->get_product_count(); i++) {
  			const factory_product_desc_t *product = tmp->get_product(i);
  			if(  product->get_output_type()==ware  &&  tmp->get_distribution_weight()>0  &&  tmp->get_building()->is_available(timeline)  ) {
  				count++;
  			}
  		}
  	}
  DBG_MESSAGE("factory_builder_t::count_producers()","%i producer for good '%s' found.", count, translator::translate(ware->get_name()));
  	return count;
  }
  
  
  /*
   * Finds a random producer producing @p ware.
   * @param timeline the current time(months)
   */
  void factory_builder_t::find_producer(weighted_vector_tpl<const factory_desc_t *> &producer, const goods_desc_t *ware, uint16 timeline )
  {
  	// find all producers
  	producer.clear();
  	FOR(stringhashtable_tpl<factory_desc_t const*>, const& t, desc_table) {
  		factory_desc_t const* const tmp = t.value;
  		if (  tmp->get_distribution_weight()>0  &&  tmp->get_building()->is_available(timeline)  ) {
  			for(  uint i=0; i<tmp->get_product_count();  i++  ) {
  				const factory_product_desc_t *product = tmp->get_product(i);
  				if(  product->get_output_type()==ware  ) {
  					producer.insert_unique_ordered(tmp, tmp->get_distribution_weight(), compare_fabrik_desc);
  					break;
  				}
  			}
  		}
  	}
  
  	// no producer installed?
  	if(  producer.empty()  ) {
  		dbg->error("factory_builder_t::find_producer()", "no producer for good '%s' was found.", translator::translate(ware->get_name()));
  	}
  	DBG_MESSAGE("factory_builder_t::find_producer()", "%i producer for good '%s' found.", producer.get_count(), translator::translate(ware->get_name()) );
  }
  
  
  bool factory_builder_t::check_construction_site(koord pos, koord size, factory_desc_t::site_t site, bool is_factory, climate_bits cl)
  {
  	// check for water (no shore in sight!)
  	if(site==factory_desc_t::Water) {
  		for(int y=0;y<size.y;y++) {
  			for(int x=0;x<size.x;x++) {
  				const grund_t *gr=welt->lookup_kartenboden(pos+koord(x,y));
  				if(gr==NULL  ||  !gr->is_water()  ||  gr->get_grund_hang()!=slope_t::flat) {
  					return false;
  				}
  			}
  		}
  	}
  	else {
  		if (is_factory  &&  site!=factory_desc_t::Land) {
  			return factory_site_searcher_t(welt, site).is_area_ok(pos, size.x, size.y, cl);
  		}
  		else {
  			// check on land
  			// do not build too close or on an existing factory
  			if( !welt->is_within_limits(pos)  || is_factory_at(pos.x, pos.y)  ) {
  				return false;
  			}
  			return welt->square_is_free(pos, size.x, size.y, NULL, cl);
  		}
  	}
  	return true;
  }
  
  
  koord3d factory_builder_t::find_random_construction_site(koord pos, int radius, koord size, factory_desc_t::site_t site, const building_desc_t *desc, bool ignore_climates, uint32 max_iterations)
  {
  	bool is_factory = desc->get_type()==building_desc_t::factory;
  	bool wasser = site == factory_desc_t::Water;
  
  	if(wasser) {
  		// to ensure at least 3x3 water around (maybe this should be the station catchment area+1?)
  		size += koord(6,6);
  	}
  
  	climate_bits climates = !ignore_climates ? desc->get_allowed_climate_bits() : ALL_CLIMATES;
  	if (ignore_climates  &&  site != factory_desc_t::Water) {
  		//site = factory_desc_t::Land;
  	}
  
  	uint32 diam   = 2*radius + 1;
  	uint32 area   = diam * diam;
  	uint32 index  = simrand(area);
  	koord k;
  
  	max_iterations = min( area/(size.x*size.y)+1, max_iterations );
  	const uint32 a = diam+1;
  	const uint32 c = 37; // very unlikely to have this as a factor in somewhere ...
  
  	// in order to stop on the first occurence, one has to iterate over all tiles in a reproducable but random enough manner
  	for(  uint32 i = 0;  i<max_iterations; i++,  index = (a*index+c) % area  ) {
  
  		// so it is guaranteed that the iteration hits all tiles and does not repeat itself
  		k = koord( pos.x - radius + (index % diam), pos.y - radius + (index / diam) );
  
  		// check place (it will actually check an grosse.x/y size rectangle, so we can iterate over less tiles)
  		if(  factory_builder_t::check_construction_site(k, size, site, is_factory, climates)  ) {
  			// then accept first hit
  			if (site != factory_desc_t::Water && site != factory_desc_t::Land) {
  				DBG_MESSAGE("factory_builder_t::find_random_construction_site","Found spot for %d at %s / %d\n", site, k.get_str(), max_iterations);
  			}
  			// we accept first hit
  			goto finish;
  		}
  	}
  	// nothing found
  	if (site != factory_desc_t::Water  &&  site != factory_desc_t::Land) {
  		DBG_MESSAGE("factory_builder_t::find_random_construction_site","No spot found for location %d of %s near %s / %d\n", site, desc->get_name(), pos.get_str(), max_iterations);
  	}
  	return koord3d::invalid;
  
  finish:
  	if(wasser) {
  		// take care of offset
  		return welt->lookup_kartenboden(k+koord(3, 3))->get_pos();
  	}
  	return welt->lookup_kartenboden(k)->get_pos();
  }
  
  
  // Create a certain number of tourist attractions
  void factory_builder_t::distribute_attractions(int max_number)
  {
  	// current number of tourist attractions constructed
  	int current_number=0;
  
  	// select without timeline disappearing dates
  	if(hausbauer_t::get_random_attraction(welt->get_timeline_year_month(),true,temperate_climate)==NULL) {
  		// nothing at all?
  		return;
  	}
  
  	// very fast, so we do not bother updating progress bar
  	dbg->message("factory_builder_t::distribute_attractions()", "Distributing %i tourist attractions", max_number);
  
  	int retrys = max_number*4;
  	while(current_number<max_number  &&  retrys-->0) {
  		koord3d pos=koord3d( koord::koord_random(welt->get_size().x,welt->get_size().y),1);
  		const building_desc_t *attraction=hausbauer_t::get_random_attraction(welt->get_timeline_year_month(),true,(climate)simrand((int)arctic_climate+1));
  
  		// no attractions for that climate or too new
  		if(attraction==NULL  ||  (welt->use_timeline()  &&  attraction->get_intro_year_month()>welt->get_current_month()) ) {
  			continue;
  		}
  
  		int rotation=simrand(attraction->get_all_layouts()-1);
  		pos = find_random_construction_site(pos.get_2d(), 20, attraction->get_size(rotation), factory_desc_t::Land, attraction, false, 0x0FFFFFFF); // so far -> land only
  		if(welt->lookup(pos)) {
  			// space found, build attraction
  			hausbauer_t::build(welt->get_public_player(), pos.get_2d(), rotation, attraction);
  			current_number ++;
  			retrys = max_number*4;
  		}
  
  	}
  	// update an open map
  	minimap_t::get_instance()->calc_map_size();
  }
  
  /**
   * Compares cities by their distance to an origin.
   */
  class RelativeDistanceOrdering
  {
  private:
  	const koord m_origin;
  
  public:
  	RelativeDistanceOrdering(const koord& origin)
  		: m_origin(origin)
  	{ /* nothing */ }
  
  	/// @returns true if @p a is closer to the origin than @p b, otherwise false.
  	bool operator()(const stadt_t *a, const stadt_t *b) const
  	{
  		return koord_distance(m_origin, a->get_pos()) < koord_distance(m_origin, b->get_pos());
  	}
  };
  
  
  /*
   * Builds a single new factory.
   */
  fabrik_t* factory_builder_t::build_factory(koord3d* parent, const factory_desc_t* info, sint32 initial_prod_base, int rotate, koord3d pos, player_t* owner)
  {
  	fabrik_t * fab = new fabrik_t(pos, owner, info, initial_prod_base);
  
  	// now build factory
  	fab->build(rotate, true /*add fields*/, initial_prod_base != -1 /* force initial prodbase ? */);
  	welt->add_fab(fab);
  	add_factory_to_fab_map(welt, fab);
  
  	if(parent) {
  		fab->add_lieferziel(parent->get_2d());
  	}
  
  	// make all water station
  	if(info->get_placement() == factory_desc_t::Water) {
  		const building_desc_t *desc = info->get_building();
  		koord dim = desc->get_size(rotate);
  
  		// create water halt
  		halthandle_t halt = haltestelle_t::create(pos.get_2d(), welt->get_public_player());
  		if(halt.is_bound()) {
  
  			// add all other tiles of the factory to the halt
  			for(  int x=pos.x;  x<pos.x+dim.x;  x++  ) {
  				for(  int y=pos.y;  y<pos.y+dim.y;  y++  ) {
  					if(welt->is_within_limits(x,y)) {
  						grund_t *gr = welt->lookup_kartenboden(x,y);
  						// build the halt on factory tiles on open water only,
  						// since the halt can't be removed otherwise
  						if(gr->is_water()  &&  !(gr->hat_weg(water_wt))  &&  gr->find<gebaeude_t>()) {
  							halt->add_grund( gr );
  						}
  					}
  				}
  			}
  			halt->set_name( translator::translate(info->get_name()) );
  			halt->recalc_station_type();
  		}
  	}
  	else {
  		// connect factory to stations
  		// search for nearby stations and connect factory to them
  		koord dim = info->get_building()->get_size(rotate);
  
  		for(  int x=pos.x;  x<pos.x+dim.x;  x++  ) {
  			for(  int y=pos.y;  y<pos.y+dim.y;  y++  ) {
  				const planquadrat_t *plan = welt->access(x,y);
  				const halthandle_t *halt_list = plan->get_haltlist();
  
  				for(  unsigned h=0;  h<plan->get_haltlist_count();  h++  ) {
  					if (halt_list[h]->connect_factory(fab)) {
  						if (x != pos.x  ||  y != pos.y) {
  							// factory halt list is already correct at pos
  							fab->link_halt(halt_list[h]);
  						}
  					}
  					// cannot call halt_list[h]->verbinde_fabriken() here,
  					// as it modifies halt_list in its calls to fabrik_t::unlink_halt and fabrik_t::link_halt
  				}
  			}
  		}
  	}
  
  	// add passenger to pax>0, (so no suicide diver at the fish swarm)
  	if(info->get_pax_level()>0) {
  		const weighted_vector_tpl<stadt_t*>& staedte = welt->get_cities();
  		vector_tpl<stadt_t *>distance_stadt( staedte.get_count() );
  
  		FOR(weighted_vector_tpl<stadt_t*>, const i, staedte) {
  			distance_stadt.insert_ordered(i, RelativeDistanceOrdering(fab->get_pos().get_2d()));
  		}
  		settings_t const& s = welt->get_settings();
  		FOR(vector_tpl<stadt_t*>, const i, distance_stadt) {
  			uint32 const ntgt = fab->get_target_cities().get_count();
  			if (ntgt >= s.get_factory_worker_maximum_towns()) break;
  			if (ntgt < s.get_factory_worker_minimum_towns() ||
  					koord_distance(fab->get_pos(), i->get_pos()) < s.get_factory_worker_radius()) {
  				fab->add_target_city(i);
  			}
  		}
  	}
  	return fab;
  }
  
  
  // Check if we have to rotate the factories before building this tree
  bool factory_builder_t::can_factory_tree_rotate( const factory_desc_t *desc )
  {
  	// we are finished: we cannot rotate
  	if(!desc->get_building()->can_rotate()) {
  		return false;
  	}
  
  	// now check all suppliers if they can rotate
  	for(  int i=0;  i<desc->get_supplier_count();  i++   ) {
  
  		const goods_desc_t *ware = desc->get_supplier(i)->get_input_type();
  
  		// unfortunately, for every for iteration we have to check all factories ...
  		FOR(stringhashtable_tpl<factory_desc_t const*>, const& t, desc_table) {
  			factory_desc_t const* const tmp = t.value;
  			// now check if we produce this good...
  			for (uint i = 0; i < tmp->get_product_count(); i++) {
  				if(tmp->get_product(i)->get_output_type()==ware  &&  tmp->get_distribution_weight()>0) {
  
  					if(!can_factory_tree_rotate( tmp )) {
  						return false;
  					}
  					// check next factory
  					break;
  				}
  			}
  		}
  	}
  	// all good -> true;
  	return true;
  }
  
  
  /*
   * Builds a new full chain of factories. Precondition before calling this function:
   * @p pos is suitable for factory construction and number of chains
   * is the maximum number of good types for which suppliers chains are built
   * (meaning there are no unfinished factory chains).
   */
  int factory_builder_t::build_link(koord3d* parent, const factory_desc_t* info, sint32 initial_prod_base, int rotate, koord3d* pos, player_t* player, int number_of_chains, bool ignore_climates)
  {
  	int n = 1;
  	int org_rotation = -1;
  
  	if(info==NULL) {
  		// no industry found
  		return 0;
  	}
  
  	// no cities at all?
  	if (info->get_placement() == factory_desc_t::City  &&  welt->get_cities().empty()) {
  		return 0;
  	}
  
  	// if a factory is not rotate-able, rotate the world until we can save it
  	if(welt->cannot_save()  &&  parent==NULL  &&  !can_factory_tree_rotate(info)  ) {
  		org_rotation = welt->get_settings().get_rotation();
  		for(  int i=0;  i<3  &&  welt->cannot_save();  i++  ) {
  			pos->rotate90( welt->get_size().y-info->get_building()->get_y(rotate) );
  			welt->rotate90();
  		}
  		assert( !welt->cannot_save() );
  	}
  
  	// in town we need a different place search
  	if (info->get_placement() == factory_desc_t::City) {
  
  		koord size=info->get_building()->get_size(0);
  
  		// build consumer (factory) in town
  		stadt_t *city = welt->find_nearest_city(pos->get_2d());
  
  		climate_bits cl = ignore_climates ? ALL_CLIMATES : info->get_building()->get_allowed_climate_bits();
  
  		/* Three variants:
  		 * A:
  		 * A building site, preferably close to the town hall with a street next to it.
  		 * This could be a temporary problem, if a city has no such site and the search
  		 * continues to the next city.
  		 * Otherwise seems to me the most realistic.
  		 */
  		bool is_rotate=info->get_building()->get_all_layouts()>1  &&  size.x!=size.y  &&  info->get_building()->can_rotate();
  		// first try with standard orientation
  		koord k = factory_site_searcher_t(welt, factory_desc_t::City).find_place(city->get_pos(), size.x, size.y, cl );
  
  		// second try: rotated
  		koord k1 = koord::invalid;
  		if (is_rotate  &&  (k == koord::invalid  ||  simrand(256)<128)) {
  			k1 = factory_site_searcher_t(welt, factory_desc_t::City).find_place(city->get_pos(), size.y, size.x, cl );
  		}
  
  		rotate = simrand( info->get_building()->get_all_layouts() );
  		if (k1 == koord::invalid) {
  			if (size.x != size.y) {
  				rotate &= 2; // rotation must be even number
  			}
  		}
  		else {
  			k = k1;
  			rotate |= 1; // rotation must be odd number
  		}
  		if (!info->get_building()->can_rotate()) {
  			rotate = 0;
  		}
  
  		INT_CHECK( "fabrikbauer 588" );
  
  		/* B:
  		 * Also good.  The final factories stand possibly somewhat outside of the city however not far away.
  		 * (does not obey climates though!)
  		 */
  #if 0
  		k = find_random_construction_site(welt, welt->lookup(city->get_pos())->get_boden()->get_pos(), 3, land_bau.dim).get_2d();
  #endif
  
  		/* C:
  		 * A building site, as near as possible to the city hall.
  		 *  If several final factories land in one city, they are often
  		 * often hidden behind a row of houses, cut off from roads.
  		 */
  #if 0
  		k = building_placefinder_t(welt).find_place(city->get_pos(), land_bau.dim.x, land_bau.dim.y, info->get_building()->get_allowed_climate_bits(), &is_rotate);
  #endif
  
  		if(k != koord::invalid) {
  			*pos = welt->lookup_kartenboden(k)->get_pos();
  		}
  		else {
  			return 0;
  		}
  	}
  
  	DBG_MESSAGE("factory_builder_t::build_link","Construction of %s at (%i,%i).",info->get_name(),pos->x,pos->y);
  	INT_CHECK("fabrikbauer 594");
  
  	const fabrik_t *our_fab=build_factory(parent, info, initial_prod_base, rotate, *pos, player);
  
  	INT_CHECK("fabrikbauer 596");
  
  	// now build supply chains for all products
  	for(int i=0; i<info->get_supplier_count()  &&  i<number_of_chains; i++) {
  		n += build_chain_link( our_fab, info, i, player);
  	}
  
  	// everything built -> update map if needed
  	if(parent==NULL) {
  		DBG_MESSAGE("factory_builder_t::build_link()","update karte");
  
  		// update the map if needed
  		minimap_t::get_instance()->calc_map_size();
  
  		INT_CHECK( "fabrikbauer 730" );
  
  		// must rotate back?
  		if(org_rotation>=0) {
  			for (int i = 0; i < 4 && welt->get_settings().get_rotation() != org_rotation; ++i) {
  				pos->rotate90( welt->get_size().y-1 );
  				welt->rotate90();
  			}
  			welt->update_map();
  		}
  	}
  
  	return n;
  }
  
  
  int factory_builder_t::build_chain_link(const fabrik_t* our_fab, const factory_desc_t* info, int supplier_nr, player_t* player)
  {
  	int n = 0; // number of additional factories
  	/* first we try to connect to existing factories and will do some
  	 * cross-connect (if wanted)
  	 * We must take care to add capacity for cross-connected factories!
  	 */
  	const factory_supplier_desc_t *supplier = info->get_supplier(supplier_nr);
  	const goods_desc_t *ware = supplier->get_input_type();
  	const int producer_count=count_producers( ware, welt->get_timeline_year_month() );
  
  	if(producer_count==0) {
  		dbg->error("factory_builder_t::build_chain_link()","No producer for %s found, chain incomplete!",ware->get_name() );
  		return 0;
  	}
  
  	// how much do we need?
  	sint32 consumption = our_fab->get_base_production()*supplier->get_consumption();
  
  	slist_tpl<factories_to_crossconnect_t> factories_to_correct;
  	slist_tpl<fabrik_t *> new_factories;           // since the cross-correction must be done later
  	slist_tpl<fabrik_t *> crossconnected_supplier; // also done after the construction of new chains
  
  	int lcount = supplier->get_supplier_count();
  	int lfound = 0; // number of found producers
  
  	DBG_MESSAGE("factory_builder_t::build_chain_link","supplier_count %i, lcount %i (need %i of %s)",info->get_supplier_count(),lcount,consumption,ware->get_name());
  
  	// search if there already is one or two (cross-connect everything if possible)
  	FOR(slist_tpl<fabrik_t*>, const fab, welt->get_fab_list()) {
  
  		// Try to find matching factories for this consumption, but don't find more than two times number of factories requested.
  		if (  (lcount != 0  ||  consumption <= 0)  &&  lcount < lfound + 1  )
  			break;
  
  		// connect to an existing one if this is a producer
  		if(  fab->vorrat_an(ware) > -1  ) {
  
  			const int distance = koord_distance(fab->get_pos(),our_fab->get_pos());
  			if(  distance > welt->get_settings().get_min_factory_spacing()  &&  distance <= DISTANCE  ) {
  				// ok, this would match but can she supply enough?
  
  				// now guess how much this factory can supply
  				const factory_desc_t* const fd = fab->get_desc();
  				for (uint gg = 0; gg < fd->get_product_count(); gg++) {
  					if (fd->get_product(gg)->get_output_type() == ware && fab->get_lieferziele().get_count() < 10) { // does not make sense to split into more ...
  						sint32 production_left = fab->get_base_production() * fd->get_product(gg)->get_factor();
  						const vector_tpl <koord> & lieferziele = fab->get_lieferziele();
  
  						// decrease remaining production by supplier demand
  						FOR(vector_tpl<koord>, const& i, lieferziele) {
  							if (production_left <= 0) break;
  							fabrik_t* const zfab = fabrik_t::get_fab(i);
  							for(int zz=0;  zz<zfab->get_desc()->get_supplier_count();  zz++) {
  								if(zfab->get_desc()->get_supplier(zz)->get_input_type()==ware) {
  									production_left -= zfab->get_base_production()*zfab->get_desc()->get_supplier(zz)->get_consumption();
  									break;
  								}
  							}
  						}
  
  						// here is actually capacity left (or sometimes just connect anyway)!
  						if (production_left > 0 || simrand(100) < (uint32)welt->get_settings().get_crossconnect_factor()) {
  							if(production_left>0) {
  								consumption -= production_left;
  								fab->add_lieferziel(our_fab->get_pos().get_2d());
  								DBG_MESSAGE("factory_builder_t::build_chain_link","supplier %s can supply approx %i of %s to us", fd->get_name(), production_left, ware->get_name());
  							}
  							else {
  								/* we steal something; however the total capacity
  								 * needed is the same. Therefore, we just keep book
  								 * from whose factories from how many we stole */
  								crossconnected_supplier.append(fab);
  								FOR(vector_tpl<koord>, const& t, lieferziele) {
  									fabrik_t* zfab = fabrik_t::get_fab(t);
  									for(int zz=0;  zz<zfab->get_desc()->get_supplier_count();  zz++) {
  										if(zfab->get_desc()->get_supplier(zz)->get_input_type()==ware) {
  
  											slist_tpl<factories_to_crossconnect_t>::iterator i = std::find(factories_to_correct.begin(), factories_to_correct.end(), factories_to_crossconnect_t(zfab, 0));
  											if (i == factories_to_correct.end()) {
  												factories_to_correct.append(factories_to_crossconnect_t(zfab, 1));
  											}
  											else {
  												i->demand += 1;
  											}
  
  										}
  									}
  								}
  								// the needed production to be built does not change!
  							}
  							lfound ++;
  						}
  						break; // since we found the product ...
  					}
  				}
  			}
  		}
  	}
  
  	INT_CHECK( "fabrikbauer 670" );
  
  	/* try to add all types of factories until demand is satisfied
  	 */
  	weighted_vector_tpl<const factory_desc_t *>producer;
  	find_producer( producer, ware, welt->get_timeline_year_month() );
  	if(  producer.empty()  ) {
  		// can happen with timeline
  		if(!info->is_consumer_only()) {
  			dbg->error( "factory_builder_t::build_chain_link()", "no producer for %s!", ware->get_name() );
  			return 0;
  		}
  		else {
  			// only consumer: Will do with partly covered chains
  			dbg->error( "factory_builder_t::build_chain_link()", "no producer for %s!", ware->get_name() );
  		}
  	}
  
  	bool ignore_climates = false; // ignore climates after some retrys
  	int retry=25; // and not more than 25 (happens mostly in towns)
  
  	while(  (lcount>lfound  ||  lcount==0)  &&  consumption>0  &&  retry>0  ) {
  		const factory_desc_t *producer_d = pick_any_weighted( producer );
  		int rotate = simrand(producer_d->get_building()->get_all_layouts()-1);
  		koord3d parent_pos = our_fab->get_pos();
  		// ignore climates after 40 tries
  
  		// if climates are ignored, then placement as well ...
  		factory_desc_t::site_t placement = ignore_climates ? (producer_d->get_placement() == factory_desc_t::City ? factory_desc_t::City : factory_desc_t::Land) : producer_d->get_placement();
  
  		INT_CHECK("fabrikbauer 697");
  
  		koord3d k = find_random_construction_site( our_fab->get_pos().get_2d(), DISTANCE, producer_d->get_building()->get_size(rotate), placement, producer_d->get_building(), ignore_climates, 20000 );
  		if(  k == koord3d::invalid  ) {
  			// this factory cannot buuild in the desired vincinity
  			producer.remove( producer_d );
  			if(  producer.empty()  ) {
  				if(  ignore_climates  ) {
  					// absolutely no place to construct something here
  					break;
  				}
  				find_producer( producer, ware, welt->get_timeline_year_month() );
  				ignore_climates = true;
  			}
  			continue;
  		}
  
  		INT_CHECK("fabrikbauer 697");
  
  		DBG_MESSAGE("factory_builder_t::build_chain_link","Try to built supplier %s at (%i,%i) r=%i for %s.",producer_d->get_name(),k.x,k.y,rotate,info->get_name());
  		n += build_link(&parent_pos, producer_d, -1 /*random prodbase */, rotate, &k, player, 10000, ignore_climates);
  		lfound ++;
  
  		INT_CHECK( "fabrikbauer 702" );
  
  		// now subtract current supplier
  		fabrik_t *fab = fabrik_t::get_fab(k.get_2d() );
  		if(fab==NULL) {
  			DBG_MESSAGE( "factory_builder_t::build_chain_link", "Failed to build at %s", k.get_str() );
  			retry --;
  			continue;
  		}
  		new_factories.append(fab);
  
  		// connect new supplier to us
  		const factory_desc_t* const fd = fab->get_desc();
  		for (uint gg = 0; gg < fab->get_desc()->get_product_count(); gg++) {
  			if (fd->get_product(gg)->get_output_type() == ware) {
  				sint32 production = fab->get_base_production() * fd->get_product(gg)->get_factor();
  				// the take care of how much this factory could supply
  				consumption -= production;
  				DBG_MESSAGE("factory_builder_t::build_chain_link", "new supplier %s can supply approx %i of %s to us", fd->get_name(), production, ware->get_name());
  				break;
  			}
  		}
  	}
  
  	// now we add us to all cross-connected factories
  	FOR(slist_tpl<fabrik_t*>, const i, crossconnected_supplier) {
  		i->add_lieferziel(our_fab->get_pos().get_2d());
  	}
  
  	/* now the cross-connect part:
  	 * connect also the factories we stole from before ...
  	 */
  	FOR(slist_tpl<fabrik_t*>, const fab, new_factories) {
  		for (slist_tpl<factories_to_crossconnect_t>::iterator i = factories_to_correct.begin(), end = factories_to_correct.end(); i != end;) {
  			i->demand -= 1;
  			fab->add_lieferziel(i->fab->get_pos().get_2d());
  			i->fab->add_supplier(fab->get_pos().get_2d());
  			if (i->demand < 0) {
  				i = factories_to_correct.erase(i);
  			}
  			else {
  				++i;
  			}
  		}
  	}
  
  	INT_CHECK( "fabrikbauer 723" );
  
  	return n;
  }
  
  
  /*
   * This function is called whenever it is time for industry growth.
   * If there is still a pending consumer, this method will first complete another chain for it.
   * If not, it will decide to either build a power station (if power is needed)
   * or build a new consumer near the indicated position.
   * @return number of factories built
   */
  int factory_builder_t::increase_industry_density( bool tell_me )
  {
  	int nr = 0;
  	fabrik_t *last_built_consumer = NULL;
  #if MSG_LEVEL >= 3
  	const goods_desc_t *last_built_consumer_ware = NULL;
  #endif
  
  	// find last consumer
  	minivec_tpl<const goods_desc_t *>ware_needed;
  	if(!welt->get_fab_list().empty()) {
  		FOR(slist_tpl<fabrik_t*>, const fab, welt->get_fab_list()) {
  			if (fab->get_desc()->is_consumer_only()) {
  				last_built_consumer = fab;
  				break;
  			}
  		}
  
  		// ok, found consumer
  		if(  last_built_consumer  ) {
  			ware_needed.clear();
  			ware_needed.resize( last_built_consumer->get_desc()->get_supplier_count() );
  			for(  int i=0;  i < last_built_consumer->get_desc()->get_supplier_count();  i++  ) {
  				ware_needed.append_unique( last_built_consumer->get_desc()->get_supplier(i)->get_input_type() );
  			}
  
  			FOR(vector_tpl<koord>, const& j, last_built_consumer->get_suppliers()) {
  				factory_desc_t const* const fd = fabrik_t::get_fab(j)->get_desc();
  				for (uint32 k = 0; k < fd->get_product_count(); k++) {
  					ware_needed.remove( fd->get_product(k)->get_output_type() );
  				}
  			}
  		}
  	}
  
  	// first: do we have to continue unfinished factory chains?
  	if(  !ware_needed.empty()  && last_built_consumer  ) {
  
  		int org_rotation = -1;
  		// rotate until we can save it if one of the factories is non-rotate-able ...
  		if(welt->cannot_save()  &&  !can_factory_tree_rotate(last_built_consumer->get_desc()) ) {
  			org_rotation = welt->get_settings().get_rotation();
  			for(  int i=0;  i<3  &&  welt->cannot_save();  i++  ) {
  				welt->rotate90();
  			}
  			assert( !welt->cannot_save() );
  		}
  
  
  		uint32 last_suppliers = last_built_consumer->get_suppliers().get_count();
  		do {
  			// we have the ware but not the supplier for it ...
  			int last_built_consumer_missing_supplier = 99999;
  			for(  int i=0;  i < last_built_consumer->get_desc()->get_supplier_count();  i++  ) {
  				if(  last_built_consumer->get_desc()->get_supplier(i)->get_input_type() == ware_needed[0]  ) {
  					last_built_consumer_missing_supplier = i;
  					break;
  				}
  			}
  
  			nr += build_chain_link( last_built_consumer, last_built_consumer->get_desc(), last_built_consumer_missing_supplier, welt->get_public_player() );
  #if MSG_LEVEL >=3
  			last_built_consumer_ware = ware_needed[ 0 ];
  #endif
  			ware_needed.remove_at( 0 );
  
  		} while(  !ware_needed.empty()  &&  last_built_consumer->get_suppliers().get_count()==last_suppliers  );
  
  		// must rotate back?
  		if(org_rotation>=0) {
  			for (int i = 0; i < 4 && welt->get_settings().get_rotation() != org_rotation; ++i) {
  				welt->rotate90();
  			}
  			welt->update_map();
  		}
  
  		// only return if successful
  		if(  last_built_consumer->get_suppliers().get_count() > last_suppliers  ) {
  			DBG_MESSAGE( "factory_builder_t::increase_industry_density()", "added ware %s to factory %s", last_built_consumer_ware->get_name(), last_built_consumer->get_name() );
  			// tell the player
  			if(tell_me) {
  				stadt_t *s = welt->find_nearest_city( last_built_consumer->get_pos().get_2d() );
  				const char *stadt_name = s ? s->get_name() : translator::translate("nowhere");
  				cbuffer_t buf;
  				buf.printf( translator::translate("Factory chain extended\nfor %s near\n%s built with\n%i factories."), translator::translate(last_built_consumer->get_name()), stadt_name, nr );
  				welt->get_message()->add_message(buf, last_built_consumer->get_pos().get_2d(), message_t::industry, CITY_KI, last_built_consumer->get_desc()->get_building()->get_tile(0)->get_background(0, 0, 0));
  			}
  			minimap_t::get_instance()->calc_map();
  			return nr;
  		}
  		else {
  			DBG_MESSAGE( "factory_builder_t::increase_industry_density()", "failed to add ware %s to factory %s", last_built_consumer_ware->get_name(), last_built_consumer->get_name() );
  		}
  	}
  
  	// ok, no chains to finish, thus we must start anew
  
  	// first determine electric supply and demand
  	uint32 electric_supply = 0;
  	uint32 electric_demand = 1;
  
  	FOR(slist_tpl<fabrik_t*>, const fab, welt->get_fab_list()) {
  		if(  fab->get_desc()->is_electricity_producer()  ) {
  			electric_supply += fab->get_scaled_electric_demand() / PRODUCTION_DELTA_T;
  		}
  		else {
  			electric_demand += fab->get_scaled_electric_demand() / PRODUCTION_DELTA_T;
  		}
  	}
  
  	// now decide producer of electricity or normal ...
  	sint32 promille = (electric_supply*1000l)/electric_demand;
  	int    no_electric = promille > welt->get_settings().get_electric_promille(); // =1 -> build normal factories only
  	DBG_MESSAGE( "factory_builder_t::increase_industry_density()", "production of electricity/total production is %i/%i (%i o/oo)", electric_supply, electric_demand, promille );
  
  	while(  no_electric<2  ) {
  		bool ignore_climates = false;
  
  		for(int retries=20;  retries>0;  retries--  ) {
  			const factory_desc_t *fab=get_random_consumer( no_electric==0, ALL_CLIMATES, welt->get_timeline_year_month() );
  			if(fab) {
  				const bool in_city = fab->get_placement() == factory_desc_t::City;
  				if (in_city && welt->get_cities().empty()) {
  					// we cannot build this factory here
  					continue;
  				}
  				koord3d pos;
  				int rotation = simrand( fab->get_building()->get_all_layouts() );
  				if(!in_city) {
  					// find somewhere on the map
  					pos = find_random_construction_site( koord(welt->get_size().x/2,welt->get_size().y/2), welt->get_size_max()/2, fab->get_building()->get_size(rotation),fab->get_placement(),fab->get_building(),ignore_climates,10000);
  				}
  				else {
  					// or within the city limit
  					const stadt_t *city = pick_any_weighted(welt->get_cities());
  					koord diff = city->get_rechtsunten()-city->get_linksoben();
  					pos = find_random_construction_site( city->get_center(), max(diff.x,diff.y)/2, fab->get_building()->get_size(rotation),fab->get_placement(),fab->get_building(),ignore_climates, 1000);
  				}
  				if(welt->lookup(pos)) {
  					// Space found...
  					nr += build_link(NULL, fab, -1 /* random prodbase */, rotation, &pos, welt->get_public_player(), 1, ignore_climates);
  					if(nr>0) {
  						fabrik_t *our_fab = fabrik_t::get_fab( pos.get_2d() );
  						minimap_t::get_instance()->calc_map_size();
  						// tell the player
  						if(tell_me) {
  							const char *stadt_name = translator::translate("nowhere");
  							if (!our_fab->get_target_cities().empty()) {
  								stadt_name = our_fab->get_target_cities()[0]->get_name();
  							}
  							cbuffer_t buf;
  							buf.printf( translator::translate("New factory chain\nfor %s near\n%s built with\n%i factories."), translator::translate(our_fab->get_name()), stadt_name, nr );
  							welt->get_message()->add_message(buf, pos.get_2d(), message_t::industry, CITY_KI, our_fab->get_desc()->get_building()->get_tile(0)->get_background(0, 0, 0));
  						}
  						return nr;
  					}
  				}
  				else if(  retries==1  &&  !ignore_climates  ) {
  					// from now on, we will ignore climates to avoid broken chains
  					ignore_climates = true;
  					retries = 20;
  				}
  			}
  		}
  		// try building normal factories if building power plants was not successful
  		no_electric++;
  	}
  
  	// we should not reach here, because it means neither land nor city industries exist ...
  	dbg->warning( "factory_builder_t::increase_industry_density()", "No suitable city industry found => pak missing something?" );
  	return 0;
  }
  