from polycal4 import *
from math import pi, cos, sin, ceil, atan2

SCREEN_WIDTH, SCREEN_HEIGHT, FONT_WIDTH, FONT_HEIGHT, HAS_COLOR, FONT_WIDTH, FONT_HEIGHT, set_pixel, draw_line, fill_rect, draw_circle, fill_circle, draw_string, show_screen, sleep, wait_key, wait_release, esc_key, HAS_KEYS = get_infos(["w","h","fw","fh","hc","fw","fh","sp","dl","fr","dc","fc","ds","sh","s","wk","wr","ek","hk"], 640, 480, 1)
get_infos = None

map=b"\xd9\x10\x48\x21\x50\x21\x38\x1a\x48\x14\x58\xa9\x01\x28\x71\x18\xb1\x01\x80\x02\x11\x60\x11\x38\x2a\x38\x14\x28\x15\x30\x91\x01\x78\x15\xe1\x01\x68\x44\x90\x01\x12\x30\x11\x30\x1a\x0b\x1a\x28\x14\x28\x35\x08\x1d\x41\x1d\x11\x1d\x09\x15\x30\x21\x20\x1d\x39\x1d\x29\x1d\xe0\x01\x0c\x88\x01\x12\x30\x19\x28\x1a\x1b\x1a\x18\x14\x38\xbd\x01\x10\x25\x20\x31\x20\x25\x19\x3d\x11\x1d\x70\x23\x10\x93\x01\x68\x14\x18\x11\x20\x2a\x0b\x2a\x10\x14\x30\x65\x28\x3d\x18\x1d\x30\x11\x38\x25\x09\x45\x09\x15\x50\xfb\x01\x50\x0c\x15\x14\x10\x19\x28\x52\x10\x0c\x48\x6d\x08\x45\x08\x25\x28\x21\x38\x75\x48\x93\x02\x30\x14\x25\x0c\x18\x11\x38\x3a\x68\x8d\x01\x1a\x3d\x28\x31\x38\x35\x14\x25\x40\xa3\x02\x28\x0c\x1d\x0c\x28\x19\x40\x22\x48\x11\x18\x5d\x52\x45\x18\x41\x38\x25\x14\x25\x40\xbb\x01\x19\x53\x28\x0c\x2d\x0c\x18\x21\x40\x12\x60\x2b\x10\x65\x1a\x3d\x38\x49\x38\x25\x14\x15\x48\x7b\x21\x23\x11\x5b\x20\x0c\x35\x0c\x20\x19\x40\x0a\x60\x3b\x18\x2d\x10\x65\x10\x0d\x20\x49\x48\x35\x58\x6b\x21\x23\x19\x53\x20\x0c\x35\x0c\x30\x21\x58\x0a\x18\x0e\x08\x43\x40\x2d\x19\x0d\x11\x0d\x09\x35\x28\x39\x40\x45\x58\x6b\x21\x13\x19\x53\x28\x0c\x2d\x0c\x30\x21\x58\x0a\x28\x4b\x48\x1d\x51\x25\x28\x49\x30\x55\x50\x73\x41\x5b\x28\x0c\x25\x0c\x38\x11\x88\x01\x53\x58\x0d\x49\x25\x38\x41\x38\x55\x50\x73\x31\x5b\x28\x0c\x25\x0c\x40\x11\x80\x01\x63\x48\x1d\x49\x25\x28\x41\x40\x75\x08\x09\x20\x6b\x31\x5b\x28\x0c\x2d\x14\x30\x19\x78\x5b\x50\x25\x49\x25\x28\x39\x38\x85\x01\x08\x11\x28\x73\x31\x43\x28\x0c\x3d\x0c\x30\x19\x30\x14\x28\x5b\x50\x35\x39\x35\x28\x31\x18\x0e\x18\x8d\x01\x19\x28\x63\x31\x4b\x20\x0c\x3d\x0c\x38\x19\x28\x24\x18\x63\x48\x3d\x41\x35\x18\x41\x40\x7d\x21\x28\x5b\x20\x11\x53\x18\x14\x35\x0c\x38\x21\x28\x14\x18\x6b\x40\x2d\x12\x0d\x49\x35\x10\x41\x48\x2d\x22\x25\x10\x29\x18\x5b\x19\x08\x11\x53\x20\x0c\x35\x0c\x38\x19\x30\x0c\x18\x7b\x38\x25\x12\x1d\x41\x35\x18\x31\x58\x2d\x22\x1d\x18\x31\x10\x53\x19\x08\x09\x63\x18\x0c\x35\x0c\x38\x11\x30\x0c\x18\x8b\x01\x30\x1d\x12\x25\x49\x2d\x18\x31\x60\x2d\x12\x25\x28\x29\x10\x43\x21\x10\x09\x5b\x18\x14\x2d\x14\x30\x11\x38\x0c\x10\x3b\x1c\x3b\x38\x0d\x1a\x1d\x51\x2d\x10\x41\x58\x2d\x0a\x2d\x30\x29\x10\x3b\x29\x08\x09\x5b\x20\x0c\x35\x0c\x28\x19\x10\x09\x20\x0c\x08\x4b\x1c\x2b\x30\x1d\x22\x1d\x49\x2d\x10\x41\x28\x14\x28\x55\x38\x29\x10\x3b\x09\x14\x09\x08\x11\x53\x28\x0c\x35\x0c\x20\x39\x20\x0c\x08\x43\x14\x33\x38\x15\x1a\x2d\x49\x25\x10\x39\x28\x1c\x20\x5d\x40\x29\x10\x33\x09\x0c\x11\x08\x11\x53\x28\x0c\x35\x0c\x18\x39\x20\x0c\x10\x43\x24\x1b\x40\x25\x0a\x3d\x39\x25\x18\x29\x30\x0c\x30\x5d\x40\x29\x10\x33\x21\x08\x19\x4b\x28\x0c\x35\x0c\x18\x31\x38\x83\x01\x38\x7d\x21\x2d\x18\x41\x20\x0c\x28\x5d\x40\x29\x10\x3b\x19\x0f\x11\x53\x28\x0c\x35\x0c\x10\x31\x50\x73\x30\x8d\x01\x19\x2d\x18\x31\x30\x0c\x28\x5d\x38\x29\x10\x43\x31\x4b\x28\x0c\x45\x0c\x08\x29\x30\x15\x10\x83\x01\x30\x8d\x01\x11\x2d\x18\x29\x30\x0c\x30\x5d\x38\x29\x10\x4b\x29\x43\x28\x0c\x4d\x0c\x08\x29\x14\x18\x25\x8b\x01\x38\x5d\x12\x25\x09\x2d\x18\x29\x30\x0c\x28\x35\x14\x25\x30\x29\x10\x5b\x19\x43\x30\x0c\x45\x0c\x18\x21\x1c\x10\x25\x43\x11\x3b\x40\x55\x0a\x2d\x09\x2d\x10\x29\x60\x35\x24\x1d\x30\x29\x10\x63\x11\x3b\x30\x0c\x25\x12\x25\x0c\x10\x21\x14\x20\x15\x2b\x20\x4b\x48\xad\x01\x18\x29\x50\x3d\x24\x1d\x28\x29\x10\x1b\x10\x43\x11\x33\x30\x0c\x65\x0c\x10\x19\x0c\x30\x2b\x30\x3b\x20\x1c\x30\x95\x01\x18\x21\x58\x3d\x24\x1d\x28\x29\x10\x1b\x10\x43\x11\x1b\x48\x0c\x35\x12\x25\x0c\x10\x19\x30\x2b\x38\x3b\x20\x14\x50\x7d\x10\x31\x48\x4d\x14\x25\x20\x29\x10\x23\x18\x3b\x09\x13\x60\x0c\x5d\x0c\x18\x11\x30\x1b\x58\x33\x20\x0c\x68\x65\x18\x29\x58\x6d\x28\x19\x10\x23\x28\x43\x60\x0c\x5d\x0c\x18\x19\x38\x0b\x60\x33\x18\x21\x70\x4d\x18\x31\x60\x5d\x30\x11\x10\x23\x30\x33\x58\x0c\x65\x0c\x20\x19\xa0\x01\x33\x08\x41\x58\x55\x18\x39\x58\x5d\x30\x11\x10\x23\x10\x14\x10\x33\x40\x0a\x0c\x5d\x0c\x20\x31\xa8\x01\x23\x10\x39\x58\x5d\x20\x31\x60\x55\x30\x09\x10\x23\x10\x24\x10\x3b\x30\x1a\x5d\x18\x39\x18\x1c\x50\x0f\x28\x1b\x10\x41\x40\x6d\x18\x31\x68\x4d\x50\x23\x18\x14\x18\x4b\x28\x1a\x5d\x20\x29\x20\x0c\x90\x01\x0b\x20\x41\x28\x7d\x20\x21\x30\x1a\x20\x4d\x28\x14\x20\x23\x10\x14\x0f\x14\x08\x5b\x20\x1a\x4d\x40\x11\x58\x12\x38\x12\x30\x49\x18\x3d\x22\x2d\x20\x21\x30\x12\x28\x45\x30\x0c\x28\x23\x10\x14\x08\x14\x10\x53\x30\x12\x3d\x38\x0a\x08\x19\x48\x12\x88\x01\x39\x08\x09\x08\x4d\x12\x35\x28\x11\x30\x12\x0c\x20\x45\x60\x23\x20\x0c\x08\x0c\x10\x5b\x18\x0c\x18\x12\x2d\x20\x1c\x10\x21\x48\x22\x70\x39\x20\x8d\x01\x20\x29\x30\x0c\x20\x3d\x38\x12\x20\x23\x18\x0d\x10\x0d\x10\x63\x28\x1a\x3d\x18\x0c\x18\x19\x48\x1a\x48\x14\x18\x41\x20\x55\x0f\x3d\x18\x39\x28\x0c\x18\x45\x10\x0c\x20\x12\x20\x23\x10\x12\x0d\x08\x0d\x18\x63\x18\x2a\x3d\x18\x0c\x08\x21\x58\x69\x08\x49\x18\x9d\x01\x10\x49\x28\x0c\x08\x45\x10\x14\x28\x12\x10\x23\x18\x0a\x20\x0a\x08\x73\x20\x22\x3d\x28\x0a\x99\x02\x18\x4d\x11\x4d\x08\x59\x20\x0c\x45\x18\x0c\x50\x23\x50\x7b\x20\x22\x3d\x20\x0a\x91\x02\x18\x4d\x21\x45\x08\x59\x20\x4d\x20\x0c\x28\x0c\x10\x23\x50\x83\x01\x28\x22\x35\x28\x89\x02\x18\x45\x39\x3d\x08\x51\x28\x35\x30\x0c\x48\x23\x28\x14\x08\x0c\x93\x01\x20\x2a\x35\x10\xb1\x01\x30\x31\x18\x3d\x41\x45\x10\x51\x20\x35\x38\x0c\x38\x23\x58\x33\x19\x3b\x30\x22\x35\x18\x79\x60\x21\x20\x2d\x0e\x49\x4d\x08\x61\x10\x35\x38\x0c\x40\x23\x20\x24\x08\x14\x33\x19\x3b\x20\x3a\x35\x18\x51\x38\x13\x28\x15\x11\x18\x3d\x61\x45\x10\x49\x1a\x3d\x38\x0c\x38\x23\x30\x14\x10\x14\x3b\x11\x43\x20\x3a\x2d\x10\x41\x78\x7d\x71\x3d\x10\x49\x0a\x0f\x08\x35\x50\x0c\x30\x23\x38\x12\x08\x4b\x11\x3b\x30\x32\x25\x10\x31\x78\x95\x01\x69\x3d\x10\x49\x1a\x2d\x28\x22\x40\x23\x38\x22\x4b\x11\x43\x38\x22\x25\x18\x21\x78\x95\x01\x79\x35\x10\x61\x3d\x70\x23\x50\x12\x43\x11\x4b\x14\x20\x0c\x08\x1a\x25\x18\x11\x80\x01\x9d\x01\x79\x35\x18\x39\x18\x35\x50\x0a\x28\x23\x28\x32\x0b\x08\x93\x01\x24\x18\x22\x25\x18\x11\x30\x33\x10\xb5\x01\x71\x35\x18\x39\x18\x35\x78\x23\x38\x1a\x20\x9b\x01\x0c\x20\x2a\x25\x10\x31\x08\x33\x08\xed\x01\x51\x35\x18\x39\x18\x35\x78\x23\x38\x0a\x0e\x0a\x20\x9b\x01\x28\x2a\x25\x10\x21\x18\x3b\xfd\x01\x29\x4d\x20\x31\x10\x35\x28\x2a\x28\x2b\x30\x12\x08\x12\x18\xa3\x01\x28\x2a\x25\x10\x11\x20\x13\x08\x0f\x08\x13\x8d\x01\x2a\x65\x11\x4d\x28\x21\x10\x35\x28\x3a\x18\x2b\x30\x1a\x08\x0a\x28\x9b\x01\x28\x2a\x25\x08\x21\x18\x13\x18\x13\x08\x8d\x01\x2a\x8d\x01\x1c\x15\x18\x31\x08\x35\x30\x12\x1b\x12\x10\x2b\x38\x12\x40\xa3\x01\x20\x22\x25\x18\x11\x20\x13\x10\x1b\x20\x6d\x3a\x7d\x2c\x0d\x18\x29\x10\x2d\x38\x12\x1b\x12\x08\x3b\x30\x0a\x48\xa3\x01\x20\x2a\x25\x10\x11\x12\x18\x13\x08\x13\x40\x55\x12\x1b\x1a\x7d\x1c\x15\x20\x21\x08\x25\x48\x3a\x3b\x08\x0b\x70\xa3\x01\x20\x2a\x25\x10\x21\x28\x0b\x08\x0b\x60\x45\x0a\x13\x1a\xad\x01\x18\x29\x1d\x60\x2a\x53\x20\x23\x08\x4b\x19\x6b\x08\x0e\x20\x22\x25\x10\x11\x68\x12\xb0\x01\x45\x22\x3d\x10\x31\x15\x38\x15\x40\x9b\x01\x08\x4b\x21\x63\x38\x1a\x1d\x18\x11\x28\x12\x28\x12\xc0\x01\x3d\x12\x0b\x12\x35\x10\x29\x08\x0d\x38\x25\x30\xa3\x01\x08\x43\x21\x73\x38\x1a\x15\x18\x11\x28\x1b\x18\x12\x40\x0a\x88\x01\x35\x1a\x0b\x0a\x35\x10\x41\x38\x15\x30\xab\x01\x08\x43\x19\x73\x40\x1a\x0d\x18\x19\x18\x4b\x40\x0a\x40\x1c\x40\x35\x1a\x3d\x10\x39\x78\x93\x01\x40\x33\x11\x6b\x50\x1a\x0d\x10\x19\x08\x73\x28\x0a\x38\x1c\x50\x6d\x20\x31\x80\x01\x73\x68\x33\x09\x6b\x48\x1a\x0d\x20\x11\x93\x01\x18\x0a\x38\x1c\x68\x3d\x88\x01\x1a\x38\x6b\x78\xa3\x01\x48\x1a\x0d\x20\x11\x9b\x02\x68\x1d\x88\x01\x2a\x28\x43\x48\x5a\x0e\x08\x7b\x11\x1b\x38\x22\x0d\x20\x11\x43\x19\xa3\x02\xa0\x01\x22\x28\x4b\x38\x6a\x10\x8b\x01\x09\x1b\x30\x22\x0d\x28\x11\x43\x09\x0c\x08\x0c\x11\xd3\x03\x08\x5b\x38\x32\x18\x22\x18\x93\x01\x09\x1b\x28\x1a\x0d\x10\x0f\x18\x11\x43\x29\xdb\x01\x19\xeb\x01\x08\x53\x38\x42\x10\x1a\x18\xbb\x01\x30\x22\x0d\x18\x19\xab\x02\x31\xeb\x01\x08\x4b\x40\x22\x08\x1a\x18\x12\x10\xcb\x01\x28\x22\x0d\x10\x21\x23\x58\xb3\x01\x19\x83\x02\x08\x43\x58\x2a\x28\x0a\x18\xc3\x01\x20\x22\x28\x21\x0b\x70\xc3\x03\x08\x3b\x18\x12\x50\x1a\x20\x0a\x20\xc3\x01\x20\x1a\x30\x19\x0b\x70\x9b\x01\x70\x13\x20\x8b\x01\x08\x4b\x60\x12\x20\x12\x28\xbb\x01\x20\x1a\x20\x31\x90\x01\x3b\xb8\x01\x0b\x0a\x60\x13\x10\x1b\x28\x1b\xa0\x01\x12\x18\x0a\x18\x43\x11\x6b\x30\x0b\x28\x29\xb0\x01\x13\x60\x12\xe8\x01\x0b\x30\x0b\x90\x01\x2a\x20\x0a\x10\x0b\x08\x33\x09\x0a\x09\x6b\x70\x21\xcd\x02\x14\xad\x01\xe8\x01\x1a\x30\x0a\x53\x11\x73\x30\x14\x11\x18\x29\x45\x0e\xd5\x01\x1c\x45\x14\x75\x60\x22\x78\x12\x40\xcb\x01\x30\x14\x28\x31\x35\x22\xad\x02\x24\x4d\x80\x01\x15\x58\x1a\x50\xcb\x01\x20\x1c\x28\x41\x35\x1a\x85\x01\x2c\x1d\x0c\x0d\x0c\x1d\x0c\x3d\x14\x45\x98\x01\x0f\x98\x01\x12\x28\xc3\x01\x18\x24\x18\x51\x35\x0a\xb5\x01\x14\x1d\x14\x0d\x0c\x3d\x14\x45\x50\x0e\xa0\x01\x1a\x08\x1c\x0b\x40\x53\x0f\x6b\x20\x1c\x08\x0c\x61\xe5\x01\x14\x25\x14\x15\x0c\x0d\x0c\x25\x0c\x35\x48\x3a\x28\x12\x30\x51\x20\x19\x10\x09\x60\x63\x28\x14\x18\x61\x6d\x13\x75\x14\x3d\x0c\x45\x0c\x0d\x58\x1a\x91\x02\x40\x31\x08\x6b\x20\x14\x20\x61\x5d\x13\xcd\x01\x80\x01\xe1\x02\x40\x21\x08\x6b\x20\x0c\x09\x28\xc1\x01\x08\x31\x20\x3d\xa8\x01\x89\x03\x38\x11\x08\x6b\x18\x14\x20\x21\x20\x21\x10\x29\x28\x11\x08\x41\x20\x15\xb0\x01\xa9\x03\x18\x21\x08\x53\x30\x14\x28\x19\x0f\x11\x68\x19\x20\x49\x88\x01\x81\x04\x12\x10\x11\x08\x3b\x50\x0e\x10\xb9\x09"


pal = HAS_COLOR and ((119, 214, 76), (41, 147, 53), (79, 174, 62), (120, 213, 61), (54, 105, 38), (230, 231, 211), (184, 167, 128), (124, 103, 97), (71, 55, 40), (216, 196, 179), (185, 146, 107), (81, 73, 40), (103, 87, 80), (70, 87, 57), (52, 172, 66), (60, 200, 82), (53, 139, 57), (55, 55, 39), (96, 117, 185), (104, 136, 186), (70, 119, 128), (88, 71, 71), (170, 147, 140), (214, 215, 192), (154, 103, 90), (88, 70, 70), (170, 243, 118), (180, 145, 68), (244, 203, 48), (164, 110, 26), (245, 234, 140), (122, 77, 76)) or ((255, 255, 255), (0, 0, 0))

sprites=[
  #plaine
  HAS_COLOR and b"\xc0\x03\x5a\xc0\x07\x5a\x80\x08\x5a\xc0\x01\x5a\xc0\x05\x5a\xc0\x01\x5a\xc0\x05\x5a\xc0\x01\x5a\x40\x5a\xc0\x04\x5a\xc0\x01\x5a\x40\x5a\x80\x02\x5a\x80\x05\x5a\x80\x02\x5a\x80\x05\x5a\x80\x02\x5a\xc0\x07\x5a\x80\x0b\x5a\xc0\x07\x5a\x80\x08\x5a\xc0\x07\x5a\xc0\x03\x5a\xc0\x03\x5a\xc0\x03\x5a\xc0\x03\x5a\x80\x02\x5a\xc0\x01\x5a\xc0\x05\x5a\xc0\x01\x5a\xc0\x05\x5a\xc0\x01\x5a\xc0\x05\x5a\xc0\x01\x5a\xc0\x09\x5a\xc0\x07\x5a\xc0\x07\x5a\xc0\x07\x5a\xc0\x09\x5a\xc0\x07\x5a\xc0\x01\x5a\x80\x05\x5a\x80\x02\x5a\x80\x05\x5a\xc0\x02\x5a\xc0\x04\x5a\xc0\x02\x5a\xc0\x04\x5a\xc0\x02\x5a\xc0\x07\x5a\x80\x07" or b"\x50\x03\x1e\x03\x14\x03\x20\x03\x1e\x03\x32\x03\x10\x03\x0a\x03\x10\x03\x1e\x03\x36\x03\x14\x03\x0a\x03\x12\x03\x44",
  #montagne
  HAS_COLOR and b"\x80\x15\x55\x56\x80\x07\x55\x56\xc0\x06\x55\x47\x97\x01\x80\x06\x55\x47\x97\x01\xc0\x05\x55\x47\x56\x97\x01\x56\x80\x05\x55\x47\x56\x97\x01\x56\x80\x03\x55\x56\x40\x87\x02\x56\x97\x01\x80\x03\x55\x56\x40\x87\x02\x56\x97\x01\xc0\x02\x47\x56\x97\x01\xc7\x01\xd5\x01\x97\x01\x80\x02\x47\x56\x97\x01\xc7\x01\xd5\x01\x97\x01\xc0\x01\x48\x87\x01\x97\x01\x48\x55\x47\x55\x47\x58\x95\x01\xc0\x01\x48\x87\x01\x97\x01\x48\x55\x47\x55\x47\x58\x95\x01\xc0\x01\xc7\x01\x56\x58\x57\x48\x55\x48\x55\x47\x58\x95\x01\x80\x01\xc7\x01\x56\x58\x57\x48\x55\x48\x55\x47\x58\x95\x01\x40\x48\x47\xd9\x01\x56\x58\x88\x01\x55\x58\x95\x01\x98\x01\x40\x48\x47\xd9\x01\x56\x58\x88\x01\x55\x58\x95\x01\x98\x01\x40\xc8\x01\x99\x01\xd8\x01\x88\x01\xd8\x01\x55\x58\x40\xc8\x01\x99\x01\xd8\x01\x88\x01\xd8\x01\x55\x58\x88\x02\x59\x98\x02\x88\x01\x55\xd8\x01\x55\x88\x02\x59\x98\x02\x88\x01\x55\xd8\x01\x55\x88\x02\x99\x01\x98\x02\x95\x02\x58\x55\x88\x02\x99\x01\x98\x02\x95\x02\x58\x55\xc8\x01\xd9\x01\xd8\x01\x59\x58\xd5\x02\xc8\x01\xd9\x01\xd8\x01\x59\x58\xd5\x02\x40\xc8\x01\x99\x03\xd8\x01\x95\x01\x80\x01\xc8\x01\x99\x03\xd8\x01\x95\x01\xc0\x01\x88\x01\x99\x02\x98\x01\x99\x01\x58\x55\x80\x02\x88\x01\x99\x02\x98\x01\x99\x01\x58\x55\xc0\x02\x88\x01\x99\x04\x80\x03\x88\x01\x99\x04\xc0\x01" or b"\x34\x03\x1c\x05\x1a\x07\x14\x03\x04\x03\x02\x05\x12\x05\x02\x03\x04\x03\x10\x03\x04\x03\x06\x03\x10\x03\x02\x05\x04\x05\x0e\x03\x02\x03\x02\x03\x02\x07\x0c\x05\x04\x03\x06\x07\x0a\x03\x04\x05\x04\x03\x02\x05\x0a\x03\x02\x03\x02\x03\x02\x03\x02\x09\x06\x03\x02\x03\x02\x03\x06\x03\x02\x07\x08\x07\x06\x03\x02\x09\x0e\x0f\x28",
  #marecage
  HAS_COLOR and b"\x80\x13\x88\x02\x80\x06\x88\x02\xc0\x04\xc8\x01\x92\x02\x88\x01\xc0\x03\xc8\x01\x92\x02\x88\x01\x80\x03\x48\xd2\x04\x48\xc0\x02\x48\xd2\x04\x48\xc0\x02\x48\x92\x05\x48\x80\x02\x48\x92\x05\x48\xc0\x02\x88\x01\x92\x04\x48\xc0\x02\x88\x01\x92\x04\x48\xc0\x03\x48\x53\x92\x03\x53\x48\x80\x03\x48\x53\x92\x03\x53\x48\x80\x03\x48\x53\x92\x03\x53\x48\x80\x03\x48\x53\x92\x03\x53\x48\x80\x02\x88\x01\x93\x01\x92\x03\x53\x48\x80\x02\x88\x01\x93\x01\x92\x03\x53\x48\xc0\x01\x48\xd3\x01\x92\x03\x93\x01\x48\xc0\x01\x48\xd3\x01\x92\x03\x93\x01\x48\x80\x01\x48\x93\x01\x92\x04\x53\x48\xc0\x01\x48\x93\x01\x92\x04\x53\x48\xc0\x01\x48\x93\x01\xd2\x03\x93\x01\x48\xc0\x01\x48\x93\x01\xd2\x03\x93\x01\x48\x80\x02\x48\xd3\x01\xd2\x01\xd3\x01\x48\xc0\x02\x48\xd3\x01\xd2\x01\xd3\x01\x48\x80\x03\x88\x01\xd3\x02\x88\x01\xc0\x03\x88\x01\xd3\x02\x88\x01\xc0\x04\xc8\x02\xc0\x05\xc8\x02\x80\x13" or b"\x26\x0d\x12\x05\x02\x03\x02\x05\x12\x03\x02\x03\x02\x03\x02\x07\x0c\x03\x02\x03\x02\x03\x02\x03\x02\x09\x08\x05\x0a\x03\x02\x03\x02\x05\x06\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x05\x04\x05\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x04\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x05\x04\x05\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x06\x09\x02\x03\x0a\x05\x0a\x03\x02\x03\x02\x03\x02\x03\x02\x07\x0a\x05\x02\x03\x02\x03\x02\x03\x02\x03\x0e\x09\x02\x03\x02\x03\x16\x0b\x26",
  #mer
  HAS_COLOR and b"\x92\x02\x93\x01\x92\x03\x93\x01\x92\x03\x93\x01\x92\x03\x93\x01\x92\x02\x93\x03\x92\x01\x93\x03\x92\x01\x93\x03\x92\x01\x93\x25\x92\x01\x93\x03\x92\x01\x93\x03\x92\x01\x93\x03\x92\x01\x93\x02\x92\x03\x93\x01\x92\x03\x93\x01\x92\x03\x93\x01\x92\x25\x94\x01\x92\x03\x94\x01\x92\x03\x94\x01\x92\x03\x94\x01\x92\x02\x94\x03\x92\x01\x94\x03\x92\x01\x94\x03\x92\x01\x94\x35\x92\x01\x94\x03\x92\x01\x94\x03\x92\x01\x94\x03\x92\x01\x94\x02\x92\x03\x94\x01\xd2\x02\xd4\x01\x92\x03\x94\x01\xd2\x02\x54\x92\x10" or b"\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x05\x02\x0b\x02\x03\x02\x0b\x04\x07\x02\x07\x02\x07\x02\x0d\x02\x03\x02\x03\x02\x07\x02\x03\x02\x03\x04\x03\x02\x0b\x02\x03\x02\x15\x02\x03\x02\x0b\x02\x03\x04\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x05\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x04\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x05\x02\x0b\x02\x03\x02\x0b\x04\x07\x02\x07\x02\x07\x02\x0d\x02\x03\x02\x03\x02\x07\x02\x03\x02\x03\x04\x03\x02\x0b\x02\x03\x02\x15\x02\x03\x02\x0b\x02\x03\x04\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x05\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03\x02\x03",
  #colline
  HAS_COLOR and b"\x80\x23\x41\xc2\x01\x80\x06\x41\xc2\x01\x80\x05\x42\x41\xc2\x01\x43\x82\x01\x80\x04\x42\x41\xc2\x01\x43\x82\x01\xc0\x03\x44\x81\x01\x42\x43\x42\xc3\x01\x42\x80\x03\x44\x81\x01\x42\x43\x42\xc3\x01\x42\xc0\x02\x44\x41\x44\x82\x02\x83\x01\x42\x43\x42\x80\x02\x44\x41\x44\x82\x02\x83\x01\x42\x43\x42\xc0\x01\x41\x44\x41\x44\x81\x01\x82\x01\xc3\x01\x42\x43\x42\x80\x01\x41\x44\x41\x44\x81\x01\x82\x01\xc3\x01\x42\x43\x42\x40\x41\x44\x41\xc4\x01\x41\x42\x43\x42\xc3\x01\xc2\x01\x41\x44\x41\xc4\x01\x41\x42\x43\x42\xc3\x01\xc2\x01\x44\x41\x44\x41\x84\x01\x81\x01\xc2\x01\x43\x82\x01\x43\x42\x44\x41\x44\x41\x84\x01\x81\x01\xc2\x01\x43\x82\x01\x43\x42\x84\x01\x41\xc4\x01\x81\x01\x42\x83\x01\xc2\x02\x84\x01\x41\xc4\x01\x81\x01\x42\x83\x01\xc2\x02\x40\xc4\x02\x81\x01\x42\x83\x02\x82\x01\x80\x01\xc4\x02\x81\x01\x42\x83\x02\x82\x01\x80\x01\x41\x84\x01\x41\xc4\x01\x41\x42\xc3\x01\xc2\x01\x40\x41\x84\x01\x41\xc4\x01\x41\x42\xc3\x01\xc2\x01\x40\x44\x41\x84\x01\x41\x84\x01\x81\x01\xc2\x01\x80\x02\x44\x41\x84\x01\x41\x84\x01\x81\x01\xc2\x01\x80\x03\x84\x01\x80\x01\xc1\x01\xc0\x01\x42\xc0\x02\x84\x01\x80\x01\xc1\x01\xc0\x01\x42\x80\x21" or b"\x12\x03\x32\x03\x0e\x05\x1a\x03\x04\x03\x0c\x05\x08\x03\x02\x05\x0a\x03\x02\x05\x06\x09\x06\x03\x04\x07\x22\x05\x1a\x03\x02\x05\x16\x03\x02\x03\x02\x05\x0c\x05\x04\x03\x04\x07\x0a\x03\x04\x03\x04\x0b\x0a\x03\x02\x07\x18\x07\x28\x03\x2a",
  #foret
  HAS_COLOR and b"\xc0\x05\x4e\xc0\x07\x4e\xc0\x07\x8f\x01\x80\x07\x8f\x01\xc0\x03\x4f\xc0\x02\x50\xcf\x01\x80\x03\x4f\xc0\x02\x50\xcf\x01\x80\x03\x4e\x4f\xc0\x01\x50\x4e\x50\x4e\x4f\x50\xc0\x02\x4e\x4f\xc0\x01\x50\x4e\x50\x4e\x4f\x50\xc0\x02\xcf\x01\x40\x4d\x44\x90\x01\x4e\x50\x80\x03\xcf\x01\x40\x4d\x44\x90\x01\x4e\x50\xc0\x02\x50\x4e\x8f\x01\x44\x8e\x01\x84\x01\x90\x01\x4e\x80\x02\x50\x4e\x8f\x01\x44\x8e\x01\x84\x01\x90\x01\x4e\xc0\x01\x90\x02\x4e\x4f\x50\x44\x90\x01\xcf\x01\xc0\x01\x90\x02\x4e\x4f\x50\x44\x90\x01\xcf\x01\xc0\x01\x4d\x44\x50\x4e\x4f\x4d\x4b\x90\x01\x8e\x01\x4f\x90\x01\x80\x01\x4d\x44\x50\x4e\x4f\x4d\x4b\x90\x01\x8e\x01\x4f\x90\x01\xc0\x01\x50\x44\x50\x8e\x01\x51\x4b\x84\x01\x50\x44\x50\x80\x02\x50\x44\x50\x8e\x01\x51\x4b\x84\x01\x50\x44\x50\xc0\x01\x44\x90\x01\x8e\x02\x90\x01\x4e\x50\x8f\x01\xc0\x01\x44\x90\x01\x8e\x02\x90\x01\x4e\x50\x8f\x01\x80\x01\x4d\x44\x50\x8e\x01\xcf\x01\x90\x01\x4e\xcf\x01\x50\x40\x4d\x44\x50\x8e\x01\xcf\x01\x90\x01\x4e\xcf\x01\x50\x40\x44\x50\x4d\x44\x50\x4e\x50\x4d\x84\x02\x90\x01\x4d\x40\x44\x50\x4d\x44\x50\x4e\x50\x4d\x84\x02\x90\x01\x4d\x80\x01\x44\xd0\x01\x4e\x4f\x4e\x4b\x4d\x84\x01\x8d\x01\xc0\x01\x44\xd0\x01\x4e\x4f\x4e\x4b\x4d\x84\x01\x8d\x01\x80\x01\x4b\x84\x01\x50\x4e\x50\x8e\x01\x50\x51\x8d\x01\x4b\x50\x80\x01\x4b\x84\x01\x50\x4e\x50\x8e\x01\x50\x51\x8d\x01\x4b\x50\x80\x01\x51\x4b\x84\x02\x50\x4d\x4b\xc0\x03\x51\x4b\x84\x02\x50\x4d\x4b\x80\x04\x4d\x51\xcb\x01\x4d\x80\x05\x4d\x51\xcb\x01\x4d\x80\x04" or b"\x2a\x05\x02\x07\x12\x03\x0a\x05\x10\x07\x04\x09\x0c\x03\x08\x09\x10\x03\x02\x03\x02\x0d\x08\x03\x04\x03\x04\x03\x02\x07\x02\x03\x06\x03\x0e\x03\x04\x03\x06\x03\x04\x03\x02\x03\x02\x0f\x04\x03\x02\x03\x04\x03\x02\x09\x02\x05\x06\x03\x06\x05\x02\x07\x02\x05\x08\x03\x02\x0d\x02\x05\x0c\x03\x04\x05\x02\x05\x16\x05\x1a\x09\x16\x0d\x0a",
  #village
  HAS_COLOR and b"\xc0\x03\x5b\x5c\x80\x07\x5b\x5c\xc0\x06\x5d\x5b\x9c\x01\x80\x06\x5d\x5b\x9c\x01\xc0\x05\x5d\xdb\x01\x5c\x5b\x80\x05\x5d\xdb\x01\x5c\x5b\x80\x03\x96\x01\x47\x5d\x5b\x5d\xdb\x01\x9e\x01\x56\x80\x02\x96\x01\x47\x5d\x5b\x5d\xdb\x01\x9e\x01\x56\xc0\x01\x56\xc7\x01\x9d\x01\x5b\xdd\x01\x5b\x9e\x01\x87\x01\x96\x01\xc7\x01\x9d\x01\x5b\xdd\x01\x5b\x9e\x01\x87\x01\x56\x47\x80\x02\x9d\x02\x9b\x01\x5c\x9e\x01\x48\x56\x47\x80\x02\x9d\x02\x9b\x01\x5c\x9e\x01\x48\x56\x80\x01\x5d\x9c\x01\xdf\x01\x9b\x01\x5d\x9c\x01\x9e\x01\x56\x80\x01\x5d\x9c\x01\xdf\x01\x9b\x01\x5d\x9c\x01\x9e\x01\x56\x40\x5d\x5b\x5c\x5e\x5c\x5f\x48\xdd\x01\x5b\x9e\x01\x5c\x80\x01\x5d\x5b\x5c\x5e\x5c\x5f\x48\xdd\x01\x5b\x9e\x01\x5c\x80\x01\xdb\x01\x5c\x5e\x5c\x88\x01\x58\x5b\x5d\x5c\x58\xc0\x01\xdb\x01\x5c\x5e\x5c\x88\x01\x58\x5b\x5d\x5c\x58\x80\x01\x5d\x9b\x01\x9c\x01\x9e\x01\x5c\x4d\xdf\x01\x58\x4a\x40\x4d\x5d\x9b\x01\x9c\x01\x9e\x01\x5c\x4d\xdf\x01\x58\x4a\x40\x4d\x9d\x01\x9b\x01\xdc\x01\x8d\x01\x58\x48\x58\x4a\x58\x40\x4d\x9d\x01\x9b\x01\xdc\x01\x8d\x01\x58\x48\x58\x4a\x58\x40\x4d\x40\x5f\x9d\x01\x9c\x01\x58\xcd\x01\x48\x98\x01\x80\x01\x47\x40\x5f\x9d\x01\x9c\x01\x58\xcd\x01\x48\x98\x01\x80\x01\x47\x4d\x58\x5f\xd8\x01\x46\xc0\x03\x47\x56\x4d\x58\x5f\xd8\x01\x46\xc0\x03\x47\x56\x4d\x5f\x58\x4a\x48\x86\x01\x80\x01\x5c\xc0\x01\x47\x56\x40\x4d\x5f\x58\x4a\x48\x86\x01\x80\x01\x5c\xc0\x01\x47\x56\x40\x8d\x01\x5f\x4a\x48\x46\x80\x01\x58\x40\x58\x40\x96\x01\x80\x01\x8d\x01\x5f\x4a\x48\x46\x80\x01\x58\x40\x58\x40\x96\x01\x80\x11" or b"\x18\x03\x1c\x07\x1a\x03\x02\x03\x18\x0b\x16\x03\x06\x03\x0c\x05\x06\x03\x02\x03\x02\x03\x0a\x03\x02\x05\x04\x03\x02\x03\x02\x03\x08\x03\x02\x03\x02\x05\x12\x03\x02\x03\x02\x03\x02\x05\x0e\x15\x0e\x03\x0c\x03\x10\x03\x02\x03\x04\x03\x02\x03\x10\x03\x0c\x03\x10\x03\x04\x05\x04\x03\x10\x03\x04\x05\x04\x03\x2c",
  #donjon
  HAS_COLOR and b"\x80\x13\x85\x01\x40\x45\x80\x06\x85\x01\x40\x45\xc0\x05\x46\x47\x46\x87\x01\x45\x80\x05\x46\x47\x46\x87\x01\x45\x80\x05\x45\x48\x49\x4a\x46\x47\x80\x05\x45\x48\x49\x4a\x46\x47\x80\x05\x46\xc9\x01\x4a\x45\x80\x05\x46\xc9\x01\x4a\x45\x80\x05\x47\x45\x47\x45\x47\x4a\x80\x05\x47\x45\x47\x45\x47\x4a\x80\x05\x4b\x47\x46\x4a\x46\x47\x80\x05\x4b\x47\x46\x4a\x46\x47\x80\x05\x4c\x8b\x01\x87\x01\x46\x80\x05\x4c\x8b\x01\x87\x01\x46\x80\x05\xc7\x01\x86\x01\x4a\x80\x05\xc7\x01\x86\x01\x4a\x80\x05\x47\x4c\x4b\x48\x4a\x46\x80\x05\x47\x4c\x4b\x48\x4a\x46\x80\x05\x4c\x47\x4b\x48\x46\x4a\x80\x05\x4c\x47\x4b\x48\x46\x4a\x80\x05\x47\x4c\x47\xc6\x01\x80\x05\x47\x4c\x47\xc6\x01\x80\x05\xc7\x01\x46\x4a\x46\x80\x05\xc7\x01\x46\x4a\x46\xc0\x03\xcd\x01\x4c\x87\x01\xc6\x01\xc0\x03\xcd\x01\x4c\x87\x01\xc6\x01\x80\x03\x8d\x02\x47\x4c\x4b\x48\x46\x4a\x80\x03\x8d\x02\x47\x4c\x4b\x48\x46\x4a\xc0\x03\x8d\x02\x47\x4b\x48\x46\x80\x04\x8d\x02\x47\x4b\x48\x46\x80\x03" or b"\x22\x07\x04\x09\x04\x07\x08\x03\x04\x03\x04\x03\x04\x03\x02\x03\x04\x1d\x06\x03\x04\x03\x04\x03\x04\x03\x04\x03\x04\x1d\x06\x03\x04\x05\x04\x05\x04\x05\x04\x05\x04\x0d\x04\x05\x06\x03\x04\x03\x02\x03\x04\x03\x04\x05\x04\x1d\x08\x03\x04\x09\x04\x03\x02\x03\x04\x0d\x04\x0d\x06\x03\x04\x03\x08\x05\x04\x03\x04\x0b\x08\x0b\x08\x03\x02\x03\x08\x03\x02\x03\x02\x03\x04\x0b\x08\x0b",
  #player
  HAS_COLOR and b"\xc0\x02\x81\x03\x80\x05\x81\x03\xc0\x04\x81\x04\x80\x04\x81\x04\x80\x04\x41\x88\x03\x41\x80\x04\x41\x88\x03\x41\x80\x03\x5e\x40\x88\x04\x40\x5e\x80\x02\x5e\x40\x88\x04\x40\x5e\x80\x02\x9e\x01\x48\x5e\x43\x9e\x01\x43\x5e\x48\x9e\x01\x80\x02\x9e\x01\x48\x5e\x43\x9e\x01\x43\x5e\x48\x9e\x01\x80\x02\x9e\x01\x48\x5e\x48\x9e\x01\x48\x5e\x48\x9e\x01\x80\x02\x9e\x01\x48\x5e\x48\x9e\x01\x48\x5e\x48\x9e\x01\xc0\x02\x9e\x05\x48\xc0\x02\x9e\x05\x48\x80\x03\x41\x9e\x01\x88\x01\x9e\x01\x41\x88\x01\x80\x03\x41\x9e\x01\x88\x01\x9e\x01\x41\x88\x01\x80\x02\xc8\x02\xde\x01\xc1\x01\xc0\x02\xc8\x02\xde\x01\xc1\x01\x80\x02\x88\x01\x5d\x88\x02\xc1\x02\x80\x02\x88\x01\x5d\x88\x02\xc1\x02\x80\x02\x48\xdd\x01\x88\x01\x5d\x88\x01\x81\x01\x48\x80\x02\x48\xdd\x01\x88\x01\x5d\x88\x01\x81\x01\x48\x80\x02\x88\x01\x5d\xc8\x01\x5d\x41\xc8\x01\x41\x80\x02\x88\x01\x5d\xc8\x01\x5d\x41\xc8\x01\x41\x80\x02\x88\x01\x5d\xc8\x01\x5d\x88\x01\xc1\x01\x80\x02\x88\x01\x5d\xc8\x01\x5d\x88\x01\xc1\x01\x80\x02\x88\x03\x5d\xc1\x01\x48\xc0\x02\x88\x03\x5d\xc1\x01\x48\xc0\x03\x9d\x02\x80\x01\xc8\x01\xc0\x03\x9d\x02\x80\x01\xc8\x01\x80\x04\xc8\x01\x80\x01\xc8\x01\x80\x04\xc8\x01\x80\x01\xc8\x01\x80\x02" or b"\x0c\x09\x16\x03\x08\x03\x12\x11\x0c\x03\x02\x11\x02\x03\x08\x07\x0c\x07\x08\x03\x02\x03\x02\x03\x04\x03\x02\x03\x02\x03\x0a\x03\x10\x03\x0e\x03\x04\x05\x04\x03\x04\x03\x06\x0b\x06\x03\x02\x03\x02\x03\x04\x07\x02\x0b\x06\x05\x04\x05\x06\x09\x04\x05\x06\x07\x02\x07\x02\x07\x02\x03\x06\x07\x02\x0b\x04\x03\x08\x07\x02\x07\x06\x03\x0c\x15\x10\x07\x04\x07\x08"
]


SPRITE_SIZE = HAS_COLOR and 32 or 16
SPRITES_HORIZ = SCREEN_WIDTH // SPRITE_SIZE
SPRITES_HORIZ += SCREEN_WIDTH > SPRITES_HORIZ*SPRITE_SIZE
SPRITES_VERT = SCREEN_HEIGHT // SPRITE_SIZE
SPRITES_VERT += SCREEN_HEIGHT > SPRITES_VERT*SPRITE_SIZE

def getmap(xr, yr, x=0, y=0, i=0, rle=map, w=146, nbits=3):
  xr, yr = int(xr), int(yr)
  xold, yold, iold = x, y, i
  maskval = (1 << nbits) - 1
  maskcnt = (0xFF >> nbits >> 1) << nbits
  while i<len(rle) and (y < yr or y == yr and x <= xr):
    xold, yold, iold = x, y, i
    v=rle[i]
    c = (v & maskcnt) >> nbits
    if v & 0b10000000:
      i += 1
      c |= rle[i] << (7 - nbits)
    x += c
    y += x // w
    x %= w
    i += 1
  return rle[iold] & maskval, xold, yold, iold

def dess(rle,x0,y0, detour=0, w=SPRITE_SIZE, nvals=len(pal)):
  i, x = 0, 0
  x0, y0 = int(x0), int(y0)
  nbits = 0
  nvals -= 1
  while(nvals):
    nvals >>= 1
    nbits += 1
  maskval = (1 << nbits) - 1
  maskcnt = (0xFF >> nbits >> 1) << nbits
  couleur_fond = rle[0] & maskval
  while i<len(rle):
    v = rle[i]
    mv = v & maskval
    c = (v & maskcnt) >> nbits
    if v & 0b10000000:
      i += 1
      c |= rle[i] << (7 - nbits)
    while c:
      cw = min(c, w - x)
      if not(detour) or mv != couleur_fond:
        fill_rect(x0 + x, y0, cw, 1, pal[mv])
      c -= cw
      x = (x + cw) % w
      y0 += x == 0
    i += 1

def show(compass=False):
  x0 = int(state[0]) - (SPRITES_HORIZ - 1)//2
  y0 = int(state[1]) - (SPRITES_VERT - 1)//2
  xr, yr, ir = 0, 0, 0
  for dy in range(SPRITES_VERT):
    for dx in range(SPRITES_HORIZ):
      if not(HAS_COLOR) and dx + x0 == int(state[0]) and dy + y0 == int(state[1]):
        i = -1
      else:
        i, xr, yr, ir = getmap(dx + x0, dy + y0, xr, yr, ir)
      if i != screen_sprites[dy*SPRITES_HORIZ+dx]:
        dess(sprites[i], dx*SPRITE_SIZE, dy*SPRITE_SIZE)
        screen_sprites[dy*SPRITES_HORIZ+dx] = i
        if HAS_COLOR and dx + x0 == int(state[0]) and dy + y0 == int(state[1]):
          dess(sprites[-1], dx*SPRITE_SIZE, dy*SPRITE_SIZE, 1)
  draw_string(" {}".format(len(state[7])), 0, SCREEN_HEIGHT-FONT_HEIGHT, (255, 127, 0))
  draw_string(" {:03d}%+{}".format(int(state[4]), state[5]), SPRITE_SIZE, SCREEN_HEIGHT-FONT_HEIGHT, (255, 0, 0))
  draw_string(" {}pts".format(int(state[3])), 4 * SPRITE_SIZE, SCREEN_HEIGHT-FONT_HEIGHT, (0, 127, 0))
  if compass:
    r = SPRITE_SIZE // 2 - 1
    x = r + 1
    fill_circle(x, x, r, (255, 255, 255))
    if not HAS_COLOR: draw_circle(x, x, r, (0, 0, 255))
    a = state[2] * pi / 180
    draw_line(x, x, x + r * cos(a), x + r * sin(a), (0, 0, 255))
  show_screen()

def interpolx2y(x1, y1, x2, y2, x):
  return y1 + (y2 - y1) * (x - x1) / (x2 - x1)

def interpoly2x(x1, y1, x2, y2, y):
  return x1 + (x2 - x1) * (y - y1) / (y2 - y1)

def sign(x):
  return (x > 0) - (x < 0) 

def segments(x1, y1, x2, y2):
 dx = sign(x2 - x1)
 dy = sign(y2 - y1)
 lx, ly = [], []
 if dx:
   if dx>0:
     r = range(int(x1) + 1, int(x2) + (ceil(x2) > x2))
   else:
     r = range(int(x1) + ( ceil(x1) > x1) - 1, int(x2), -1)
   for x in r:
     lx.append((x, interpolx2y(x1, y1, x2, y2, x)))
 if dy:
   if dy>0:
     r = range(int(y1) + 1, int(y2) + (ceil(y2) > y2))
   else:
     r = range(int(y1) + ( ceil(y1) > y1) - 1, int(y2), -1)
   for y in r:
     ly.append((interpoly2x(x1, y1, x2, y2, y), y))
 l = [(x1, y1)]
 while len(lx) or len(ly):
   if not(len(ly)) or len(lx) and abs(lx[0][0] - l[len(l) - 1][0]) < abs(ly[0][0] - l[len(l) - 1][0]):
     l.append(lx[0])
     lx.pop(0)
   else:
     l.append(ly[0])
     ly.pop(0)
 l.append((x2, y2))
 return l

def peut_aller(id):
  return id != 1 and (id != 3 or state[6])

def dist(x, y):
  return ((x - state[0])**2 + (y - state[1])**2)**.5

def a_gagne():
  return len(state[7]) >= 10

def en_avant(l, refresh=True):
  state[3] -= .1
  a = state[2] * pi / 180
  destx = state[0] + l*cos(a)
  desty = state[1] + l*sin(a)
  l = segments(state[0], state[1], destx, desty)
  for k in range(1, len(l)):
    c, xr, yr, ir  = getmap(int(min(state[0],l[k][0])), int(min(state[1],l[k][1])))
    if not(peut_aller(c)) or not(peut_aller(getmap(l[k][0], l[k][1], xr, yr, ir)[0])): break
    d = dist(l[k][0], l[k][1]) * (.2 + ((c == 5) and .1 or (c == 4) and .2 or (c == 2) and .3))
    state[3] -= d # score
    state[4] -= d # life
    state[0:2] = l[k][0:2]
    if c==7 and not(xr in state[7]):
      if state[4] >= 100:
        state[4] = max(state[4] - 100, 0)
        state[3] += 100
        state[5] += 1
        state[7].append(xr)
    if c==6 and xr != state[8]:
      if not state[6] and len(state[7]) >= 9:
        state[6] = 1
      elif state[5]:
        state[4] = min(250, state[4] + 120)
        state[5] -= 1
      state[8] = xr
    if refresh: show()

def en_arriere(l): en_avant(-l)

def a_droite(a): state[2] += a

def a_gauche(a): a_droite(-a)

def oriente(a):
  a_droite(a - state[2])
  return state

def aller(x, y):
  oriente(atan2(y - state[1], x - state[0]) * 180 / pi)
  en_avant(dist(x, y))

def aller_selon_loop(f):
  try:
    while not(esc_key()) and f() and not(a_gagne()): pass
  except KeyboardInterrupt:
    return aller_selon_loop(f)  

def aller_selon(f):
  global state, screen_sprites
  screen_sprites = [255,] * (SPRITES_HORIZ * SPRITES_VERT)
  # x y a dx dy score life tokens boat ldonj lvill
  state = [47.5, 43.5, 0, 0, 250, 1, 0, [], 0]
  aller_selon_loop(f)
  state[3] += 1000 * a_gagne()
  return state[3]

id_action = 0

def action_clavier():
  show(True)
  if HAS_KEYS:
    wait_release()
    k = 0
    while not(k in (KEY_LEFT, KEY_RIGHT, KEY_UP, KEY_DOWN, KEY_ENTER, KEY_ESC)):
      k = wait_key()
  else:
    global id_action
    ids_actions = (" Recule", " Avance", " Gauche", " Droite", " Quitter")
    nb_actions = len(ids_actions)
    id_action -= 1
    try:
      while(1):
        id_action = (id_action + 1) % nb_actions
        draw_string(ids_actions[id_action], SCREEN_WIDTH - 2*SPRITE_SIZE, SCREEN_HEIGHT-FONT_HEIGHT, (255, 0, 255))
        show_screen()
        sleep(150)
    except KeyboardInterrupt:
      k = (KEY_DOWN, KEY_UP, KEY_LEFT, KEY_RIGHT, KEY_ESC)[id_action]
  if k == KEY_ESC: return 0
  if k in (KEY_LEFT, KEY_RIGHT):
    d = ((k == KEY_RIGHT)  or -1) * 45
    a_droite(d)
  else:
    en_avant(k == KEY_DOWN and -1 or 1, False)
  return 1