def get_best_shelter(life):
	_best_shelter = {'distance': -1, 'shelter': None}
	
	if life['group'] and groups.get_shelter(life, life['group']):
		_shelter = groups.get_shelter(life, life['group'])
		
		if _shelter:
			_nearest_chunk_key = references.find_nearest_key_in_reference(life, _shelter)
			_shelter_center = [int(val)+(WORLD_INFO['chunk_size']/2) for val in _nearest_chunk_key.split(',')]
			_dist = numbers.distance(life['pos'], _shelter_center)
			
			judge_chunk(life, _nearest_chunk_key)
			
			if _dist <= logic.time_until_midnight()*life['speed_max']:
				print life['name'],'can get to shelter in time'
				return _nearest_chunk_key
			else:
				print life['name'],'cant get to shelter in time'
	
	for chunk_key in [chunk_id for chunk_id in life['known_chunks'] if chunks.get_flag(life, chunk_id, 'shelter')]:
		chunk_center = [int(val)+(WORLD_INFO['chunk_size']/2) for val in chunk_key.split(',')]
		_score = numbers.distance(life['pos'], chunk_center)
		
		if not _best_shelter['shelter'] or _score<_best_shelter['distance']:
			_best_shelter['shelter'] = chunk_key
			_best_shelter['distance'] = _score
	
	return _best_shelter['shelter']

def get_best_shelter(life):
    _best_shelter = {"distance": -1, "shelter": None}

    if life["group"] and groups.get_shelter(life, life["group"]):
        _shelter = groups.get_shelter(life, life["group"])

        if _shelter:
            _nearest_chunk_key = references.find_nearest_key_in_reference(life, _shelter)
            _shelter_center = [int(val) + (WORLD_INFO["chunk_size"] / 2) for val in _nearest_chunk_key.split(",")]
            _dist = numbers.distance(life["pos"], _shelter_center)

            judge_chunk(life, _nearest_chunk_key)

            if _dist <= logic.time_until_midnight() * life["speed_max"]:
                print life["name"], "can get to shelter in time"
                return _nearest_chunk_key
            else:
                print life["name"], "cant get to shelter in time"

    print life["name"], life["group"], [
        chunk_id for chunk_id in life["known_chunks"] if chunks.get_flag(life, chunk_id, "shelter")
    ]
    for chunk_key in [chunk_id for chunk_id in life["known_chunks"] if chunks.get_flag(life, chunk_id, "shelter")]:
        chunk_center = [int(val) + (WORLD_INFO["chunk_size"] / 2) for val in chunk_key.split(",")]
        _score = numbers.distance(life["pos"], chunk_center)

        if not _best_shelter["shelter"] or _score < _best_shelter["distance"]:
            _best_shelter["shelter"] = chunk_key
            _best_shelter["distance"] = _score

    return _best_shelter["shelter"]

def update_targets_around_noise(life, noise):
	_most_likely_target = {'target': None, 'last_seen_time': 0}
	
	if 'target' in noise and not life['id'] == noise['target']:
		_visiblity = numbers.clip(sight.get_stealth_coverage(LIFE[noise['target']]), 0.0, 1.0)
		_visiblity = numbers.clip(_visiblity+(numbers.distance(life['pos'], LIFE[noise['target']]['pos']))/(sight.get_vision(life)/2), 0, 1.0)
		
		if _visiblity >= sight.get_visiblity_of_position(life, LIFE[noise['target']]['pos']):
			brain.meet_alife(life, LIFE[noise['target']])
			
			life['know'][noise['target']]['escaped'] = 1
			life['know'][noise['target']]['last_seen_at'] = noise['pos'][:]
			life['know'][noise['target']]['last_seen_time'] = 0
	
	for target in life['know'].values():
		if not target['escaped'] or not target['last_seen_at'] or target['dead']:
			continue
		
		if numbers.distance(target['last_seen_at'], noise['pos']) > noise['volume']:
			continue
		
		if judgement.is_target_threat(life, target['life']['id']):
			if not _most_likely_target['target'] or target['last_seen_time'] < _most_likely_target['last_seen_time']:
				_most_likely_target['last_seen_time'] = target['last_seen_time']
				_most_likely_target['target'] = target
	
	if _most_likely_target['target']:
		_most_likely_target['target']['escaped'] = 1
		_most_likely_target['target']['last_seen_at'] = noise['pos'][:]
		_most_likely_target['target']['last_seen_time'] = 1
		
		logging.debug('%s heard a noise, attributing it to %s.' % (' '.join(life['name']), ' '.join(_most_likely_target['target']['life']['name'])))

def _get_nearest_chunk_in_list(pos, chunks, check_these_chunks_first=[]):
	_nearest_chunk = {'chunk_key': None, 'distance': -1}
	
	if check_these_chunks_first:
		for chunk_key in check_these_chunks_first:
			if not chunk_key in chunks:
				continue
			
			chunk_center = [int(val)+(WORLD_INFO['chunk_size']/2) for val in chunk_key.split(',')]
			_dist = numbers.distance(pos, chunk_center)
			
			if not _nearest_chunk['chunk_key'] or _dist < _nearest_chunk['distance']:
				_nearest_chunk['distance'] = _dist
				_nearest_chunk['chunk_key'] = chunk_key
	
	if _nearest_chunk['chunk_key']:
		return _nearest_chunk
	
	for chunk_key in chunks:
		chunk_center = [int(val)+(WORLD_INFO['chunk_size']/2) for val in chunk_key.split(',')]
		_dist = numbers.distance(pos, chunk_center)
		
		if not _nearest_chunk['chunk_key'] or _dist < _nearest_chunk['distance']:
			_nearest_chunk['distance'] = _dist
			_nearest_chunk['chunk_key'] = chunk_key
	
	return _nearest_chunk

def handle_camera(entity_id, min_zoom=3.5, max_zoom=14.5, max_enemy_distance=2400, center_distance=600.0):
	if not entity_id in entities.ENTITIES:
		display.CAMERA['zoom_speed'] = .005
		display.CAMERA['next_zoom'] = 4.5
		
		return False
	
	if not clock.is_ticking():
		return False
	
	_player = entities.get_entity(entity_id)
	_center_pos = _player['position'].copy()
	_median_distance = []
	
	if 'in_space' in _player and _player['in_space']:
		_distance_to_center = numbers.distance(_player['position'], (worlds.get_size()[0]/2, worlds.get_size()[1]/2))
		
		_min_zoom = 2.0
		_max_zoom = max_zoom
		display.CAMERA['next_zoom'] = numbers.clip(_max_zoom*((_distance_to_center/3000.0)-1), _min_zoom, _max_zoom)
	
	elif _player['death_timer'] == -1:
		for enemy_id in entities.get_sprite_groups(['enemies', 'hazards']):
			_enemy = entities.get_entity(enemy_id)
			
			if 'player' in _enemy:
				continue
			
			_dist = numbers.distance(_player['position'], _enemy['position'])
			if _dist>=max_enemy_distance:
				continue
			
			_median_distance.append(_dist)
			_center_pos = numbers.interp_velocity(_center_pos, _enemy['position'], 0.5)
		
		if not _median_distance:
			_median_distance = [0]
		
		_distance_to_nearest_enemy = sum(_median_distance)/len(_median_distance)
		_min_zoom = min_zoom
		_max_zoom = max_zoom
		display.CAMERA['next_zoom'] = numbers.clip(_max_zoom*(_distance_to_nearest_enemy/float(center_distance)), _min_zoom, _max_zoom)
	else:
		display.CAMERA['zoom_speed'] = .05
		display.CAMERA['next_zoom'] = 1.5
	
	if display.CAMERA['next_zoom'] < 5:
		display.CAMERA['next_center_on'] = _center_pos
	else:
		display.CAMERA['next_center_on'] = _player['position'].copy()

def _find_nearest_reference(life, ref_type, skip_current=False, skip_known=False, skip_unknown=False, ignore_array=[]):
    _lowest = {"chunk_key": None, "reference": None, "distance": -1}

    for reference in WORLD_INFO["reference_map"][ref_type]:
        if reference in ignore_array:
            continue

        _nearest_key = find_nearest_key_in_reference(life, reference)

        if skip_current and maps.get_chunk(_nearest_key) == lfe.get_current_chunk(life):
            continue

        if skip_known and _nearest_key in life["known_chunks"]:
            continue

        if skip_unknown and not _nearest_key in life["known_chunks"]:
            continue

        _center = [int(val) + (WORLD_INFO["chunk_size"] / 2) for val in _nearest_key.split(",")]
        _distance = numbers.distance(life["pos"], _center)

        if not _lowest["chunk_key"] or _distance < _lowest["distance"]:
            _lowest["distance"] = _distance
            _lowest["chunk_key"] = _nearest_key
            _lowest["reference"] = reference

    return _lowest

def tick_eyemine(entity):
	if 'max_explode_velocity' in entity and entity['current_speed']>=entity['max_explode_velocity']:
		entities.trigger_event(entity, 'kill')
		entities.trigger_event(entity, 'explode')
		
		return entities.delete_entity(entity)
	
	if entity['current_target'] and entity['current_target'] in entities.ENTITIES:
		_target_object = entities.get_entity(entity['current_target'])
	else:
		_target_object = None
	
	for soldier_id in entities.get_sprite_groups(['enemies', 'players']):
		if entity['_id'] == soldier_id:
			continue
		
		if numbers.distance(entity['position'], entities.get_entity(soldier_id)['position'], old=True)>50:
			continue
		
		if _target_object and not entity['current_target'] == soldier_id and 'player' in _target_object:
			entities.trigger_event(_target_object,
			                       'score',
			                       target_id=entity['_id'],
			                       amount=10,
			                       text='Creative Escape')
		
		entities.trigger_event(entities.get_entity(soldier_id), 'hit', damage=6, target_id=entity['_id'])
		entities.trigger_event(entity, 'kill')
		entities.trigger_event(entity, 'explode')
		entities.delete_entity(entity)
		
		break

def _target_filter(life, target_list, escaped_only, ignore_escaped, recent_only=False, ignore_lost=False, limit_distance=-1, filter_func=None):
	if not target_list:
		return []
	
	_return_targets = []
	
	for target in target_list:
		if LIFE[target]['dead']:
			continue
		
		_knows = brain.knows_alife_by_id(life, target)
		
		if (escaped_only and not _knows['escaped']==1) or (ignore_escaped and _knows['escaped']>=ignore_escaped):
			continue
		
		if ignore_lost and _knows['escaped'] == 2:
			continue
		
		if recent_only and _knows['last_seen_time'] >= 95:
			continue
		
		if not limit_distance == -1 and _knows['last_seen_at'] and numbers.distance(life['pos'], _knows['last_seen_at'])>limit_distance:
			continue
		
		if filter_func and not filter_func(life, target):
			continue
	
		_return_targets.append(target)
	
	return _return_targets

def explore_unknown_chunks(life):
	if life['path']:
		return True
	
	_chunk_key = references.path_along_reference(life, 'roads')
	
	if not _chunk_key:
		return False
	
	_walkable_area = chunks.get_walkable_areas(_chunk_key)
	if not _walkable_area:
		print 'no walkable area'
		return False
	
	_closest_pos = {'pos': None, 'distance': -1}
	for pos in _walkable_area:
		_distance = numbers.distance(life['pos'], pos)
				
		if _distance <= 1:
			_closest_pos['pos'] = pos
			break
		
		if not _closest_pos['pos'] or _distance<_closest_pos['distance']:
			_closest_pos['pos'] = pos
			_closest_pos['distance'] = _distance
	
	lfe.clear_actions(life)
	lfe.add_action(life,{'action': 'move','to': _closest_pos['pos']},200)
	
	return True

def _find_nearest_reference(life, ref_type, skip_current=False, skip_known=False, skip_unknown=False, ignore_array=[]):
	_lowest = {'chunk_key': None, 'reference': None, 'distance': -1}
	
	for reference in WORLD_INFO['reference_map'][ref_type]:
		if reference in ignore_array:
			continue
		
		_nearest_key = find_nearest_key_in_reference(life, reference)

		if skip_current and maps.get_chunk(_nearest_key) == lfe.get_current_chunk(life):
			continue
			
		if skip_known and _nearest_key in life['known_chunks']:
			continue

		if skip_unknown and not _nearest_key in life['known_chunks']:
			continue

		_center = [int(val)+(WORLD_INFO['chunk_size']/2) for val in _nearest_key.split(',')]
		_distance = numbers.distance(life['pos'], _center)
		
		if not _lowest['chunk_key'] or _distance<_lowest['distance']:
			_lowest['distance'] = _distance
			_lowest['chunk_key'] = _nearest_key
			_lowest['reference'] = reference
	
	return _lowest

def find_nearest_key_in_reference(life, reference_id, unknown=False, ignore_current=False, threshold=-1):
	_lowest = {'chunk_key': None, 'distance': 9000}

	#Dirty hack here...
	#We can use the list of visible chunks to find the nearest key in the reference
	#This is actually SLOWER if the NPC can't see any keys in the reference and a search
	#has to be done (the way we're doing it now.)
	
	_reference = get_reference(reference_id)
	
	for _key in _reference:
		if unknown and _key in life['known_chunks']:
			continue
		
		if ignore_current and lfe.get_current_chunk_id(life) == _key:
			print 'ignoring current'
			continue
		
		if not maps.get_chunk(_key)['ground']:
			continue
		
		_center = [int(val)+(WORLD_INFO['chunk_size']/2) for val in _key.split(',')]
		_distance = numbers.distance(life['pos'], _center)
		
		if not _lowest['chunk_key'] or _distance<_lowest['distance']:
			_lowest['distance'] = _distance
			_lowest['chunk_key'] = _key
		
		if threshold > -1 and _lowest['distance'] <= threshold:
			break
	
	return _lowest['chunk_key']

def get_items_at(position, check_bodies=False):
	"""Returns list of all items at a given position."""
	_items = []
	_chunk = alife.chunks.get_chunk(alife.chunks.get_chunk_key_at(position))
	
	for _item in _chunk['items']:
		if not _item in ITEMS:
			continue
		
		item = ITEMS[_item]
		
		if is_item_owned(_item):
			continue
		
		if tuple(item['pos']) == tuple(position):
			_items.append(item)
	
	#TODO: This is awful
	if check_bodies:
		#for pos in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (1, -1), (-1, 1), (1, 1), (0, 0)]:
		#	__pos = (_pos[0]+pos[0], _pos[1]+pos[1], _pos[2])
		#	_items.extend(items.get_items_at(__pos))
			
		#Sue me again.
		for life_id in LIFE[SETTINGS['controlling']]['seen']:
			if numbers.distance(LIFE[SETTINGS['controlling']]['pos'], LIFE[life_id]['pos'])>1:
				continue
			
			for item_uid in life.get_all_equipped_items(LIFE[life_id]):
				_items.append(ITEMS[item_uid])
	
	return _items

def understand(life):
	if SETTINGS['controlling']:
		_dist_to_player = numbers.distance(life['pos'], LIFE[SETTINGS['controlling']]['pos'])
		if _dist_to_player < 100:
			if life['think_rate_max']>=30:
				if _dist_to_player < 75:
					life['think_rate_max'] = 1
					life['online'] = True
					logging.debug('[Agent] %s brought online (Reason: Near viewer)' % ' '.join(life['name']))
				
			else:
				life['think_rate_max'] = 1
		else:
			if _dist_to_player >= OFFLINE_ALIFE_DISTANCE and life['online']:
				life['online'] = False
				logging.debug('[Agent] %s went offline (Reason: Away from viewer)' % ' '.join(life['name']))
			elif life['think_rate_max']<30:
				if _dist_to_player < OFFLINE_ALIFE_DISTANCE:
					life['online'] = True
				
				logging.debug('[Agent] %s went passive (Reason: Away from viewer)' % ' '.join(life['name']))
			
			life['think_rate_max'] = numbers.clip(15*(((_dist_to_player-100)+30)/30), 30, 60)
	else:
		life['think_rate_max'] = 5
	
	if not life['online'] or life['asleep']:
		return False
	
	if len(life['actions'])-len(lfe.find_action(life, matches=[{'action': 'move'}, {'action': 'dijkstra_move'}]))>0:
		lfe.clear_actions(life)
		life['path'] = []
		
		return False
	
	if life['think_rate']>0:
		life['think_rate'] -= 1
		
		return False
	
	for module in CONSTANT_MODULES:
		module.setup(life)
	
	life['think_rate'] = life['think_rate_max']
	
	#if life['name'][0].startswith('Tim'):
	#	_goal, _tier, _plan = planner.get_next_goal(life, debug='attack')
	#else:
	_goal, _tier, _plan = planner.get_next_goal(life)
	
	if _goal:
		lfe.change_goal(life, _goal, _tier, _plan)
	else:
		lfe.change_goal(life, 'idle', TIER_RELAXED, [])
		#logging.error('%s has no possible goal.' % ' '.join(life['name']))
		
		return False
	
	planner.think(life)
	

def control_zes():
	_zes = get_faction('ZES')
	
	if not 'intro_created' in _zes['flags'] and _zes['members'] and SETTINGS['controlling']:
		_zes = get_faction('ZES')
		_zes['flags']['intro_created'] = True
		_item_uid = weapons.spawn_and_arm('glock', '9x19mm magazine', '9x19mm round', 17)
		_kill_target = get_faction('Bandits')['members'][0]
		_kill_target_direction = numbers.distance(LIFE[_zes['members'][0]]['pos'], LIFE[_kill_target]['pos'])
		_quest_item_uid = lfe.get_inventory_item_matching(LIFE[_kill_target], {'type': 'radio'})
		_mission = missions.create_mission('zes_glock', target=SETTINGS['controlling'],
		                                   item_uid=_item_uid,
		                                   quest_item_uid=_quest_item_uid,
		                                   deliver_target=_zes['members'][0],
		                                   kill_target=_kill_target,
		                                   location=lfe.get_current_chunk_id(LIFE[_kill_target]))
		
		lfe.add_item_to_inventory(LIFE[_zes['members'][0]], _item_uid)
		alife.brain.meet_alife(LIFE[_zes['members'][0]], LIFE[SETTINGS['controlling']])
		alife.memory.create_question(LIFE[_zes['members'][0]],
		                             SETTINGS['controlling'],
		                             'zes_intro',
		                             kill_target_name=' '.join(LIFE[_kill_target]['name']),
		                             kill_target_direction=language.get_real_direction(_kill_target_direction))
		missions.remember_mission(LIFE[_zes['members'][0]], _mission)
		missions.activate_mission(LIFE[_zes['members'][0]], '1')

def find_target(life, target, distance=5, follow=False, call=True):
    _target = brain.knows_alife_by_id(life, target)
    _dist = numbers.distance(life["pos"], _target["last_seen_at"])

    _can_see = sight.can_see_target(life, target)
    if _can_see and _dist <= distance:
        if follow:
            return True

        lfe.stop(life)

        return True

    if _target["escaped"] == 1:
        search_for_target(life, target)
        return False

    if not _can_see and sight.can_see_position(life, _target["last_seen_at"]) and _dist < distance:
        if call:
            if not _target["escaped"]:
                memory.create_question(life, target, "GET_LOCATION")

            speech.communicate(life, "call", matches=[target])

        _target["escaped"] = 1

        return False

    if not lfe.path_dest(life) == tuple(_target["last_seen_at"][:2]):
        lfe.walk_to(life, _target["last_seen_at"])

    return False

def find_target(life, target, distance=5, follow=False, call=True):
	_target = brain.knows_alife_by_id(life, target)
	_dist = numbers.distance(life['pos'], _target['last_seen_at'])
	
	_can_see = sight.can_see_target(life, target)
	if _can_see and _dist<=distance:
		if follow:
			return True
		
		lfe.stop(life)
		
		return True
	
	if _target['escaped'] == 1:
		search_for_target(life, target)
		return False
	
	if not _can_see and sight.can_see_position(life, _target['last_seen_at']) and _dist<distance:
		if call:
			if not _target['escaped']:
				memory.create_question(life, target, 'GET_LOCATION')
				
			speech.communicate(life, 'call', matches=[target])
		
		_target['escaped'] = 1
		
		return False
	
	if not lfe.path_dest(life) == tuple(_target['last_seen_at'][:2]):
		lfe.clear_actions(life)
		lfe.add_action(life,
			          {'action': 'move','to': _target['last_seen_at'][:2]},
			          200)
	
	return False

def _spread(noise):
	for alife in LIFE.values():
		if alife['dead']:
			continue
		
		if sight.can_see_position(alife, noise['pos']):
			continue
		
		_dist = numbers.distance(noise['pos'], alife['pos'])
		
		if _dist>noise['volume']:
			continue
		
		update_targets_around_noise(alife, noise)		
		
		_direction_to = numbers.direction_to(alife['pos'], noise['pos'])
		_direction_string = language.get_real_direction(_direction_to)
		
		#TODO: Check walls between positions
		#TODO: Add memory
		if _dist >=noise['volume']/2:
			if 'player' in alife:
				gfx.message(random.choice(FAR_TEXT).replace('@t', noise['text'][1]).replace('@d', _direction_string))
		else:
			if 'player' in alife:
				gfx.message(random.choice(FAR_TEXT).replace('@t', noise['text'][0]).replace('@d', _direction_string))
				

def judge_camp(life, camp, for_founding=False):
    # This is kinda complicated so I'll do my best to describe what's happening.
    # The ALife keeps track of chunks it's aware of, which we'll use when
    # calculating how much of a camp we know about (value between 0..1)
    # First we score the camp based on what we DO know, which is pretty cut and dry:
    #
    # We consider:
    # 	How big the camp is vs. how many people we think we're going to need to fit in it (not a factor ATM)
    # 		A big camp won't be attractive to just one ALife, but a faction will love the idea of having a larger base
    # 	Distance from other camps
    # 		Certain ALife will prefer isolation
    #
    # After scoring this camp, we simply multiply by the percentage of the camp
    # that is known. This will encourage ALife to discover a camp first before
    # moving in.

    # In addition to all that, we want to prevent returning camps that are too close
    # to other camps. This is hardcoded (can't think of a reason why the ALife would want this)

    if for_founding:
        for _known_camp in [c["reference"] for c in life["known_camps"].values()]:
            for _pos1 in _known_camp:
                pos1 = [int(i) for i in _pos1.split(",")]
                for _pos2 in camp:
                    pos2 = [int(i) for i in _pos2.split(",")]
                    _dist = numbers.distance(pos1, pos2) / WORLD_INFO["chunk_size"]

                    if _dist <= 15:
                        return 0

    _known_chunks_of_camp = references.get_known_chunks_in_reference(life, camp)

    _current_population = 0
    _current_trust = 0
    for _target in life["know"].values():
        if not references.is_in_reference(_target["last_seen_at"], camp):
            continue

        _current_population += 1

        if can_trust(life, _target["life"]["id"]):
            _current_trust += _target["trust"]
        else:
            _current_trust -= _target["danger"]

    _percent_known = len(_known_chunks_of_camp) / float(len(camp))
    _score = _current_trust
    _camp = camps.get_camp_via_reference(camp)

    if _camp:
        _score += judge_group(life, camps.get_controlling_group(_camp))

    if stats.desires_to_create_camp(life):
        _score += len(groups.get_group(life, life["group"])["members"]) / 2 <= len(_known_chunks_of_camp)

        # TODO: Why does this cause a crash?
        # return int(round(_percent_known*10))
        # print 'camp score:',(len(camp)*_percent_known),_score,(len(camp)*_percent_known)*_score
    return (len(camp) * _percent_known) * _score

def create_path(start, end, avoid_positions=[]):
	_start = start
	_end = end

	if not numbers.distance(_start, _end):
		return []

	return astar(start, end, avoid=avoid_positions)

def create_smoke_streamer(pos, size, length, color=tcod.gray):
	_direction = random.randint(0, 359)
	_end_velocity = numbers.velocity(_direction, length)
	_end_pos = [int(round(pos[0]+_end_velocity[0])), int(round(pos[1]+_end_velocity[1]))]
	
	for new_pos in render_los.draw_line(pos[0], pos[1], _end_pos[0], _end_pos[1]):
		_new_pos = [new_pos[0], new_pos[1], pos[2]]
		create_smoke_cloud(_new_pos, size, age=-numbers.distance(pos, new_pos)/float(length), color=color)