# -*- coding: utf-8 -*-
r"""A* sobre a grelha de colisao extraida do .nav do client.

A GRELHA vem de tools/extrair_colisao.py: 1536x1536 celulas de 10 unidades, com os
obstaculos rasterizados dos grupos 2 e 14 do berneo.nav. Validada contra 78.643 posicoes
reais de monstro do servidor oficial -- 0,32 por cento delas caem em celula bloqueada,
contra 2,41 por cento de pontos ao acaso na mesma regiao.

PORQUE E PRECISO. Ate 29/08 o mob apontava ao jogador a cada pacote. Quando esta perto, um
passo do jogador muda o rumo dele em dezenas de graus, e ele gira -- o jogador descreveu-o
como "vira de um lado pro outro mas andando em minha direcao". O oficial nao gira porque nao
aponta ao alvo: segue um CAMINHO calculado, em segmentos rectos, e a rectidao de 93 por cento
que se mediu nele e consequencia disso, nao uma regra. Tentou-se imitar a consequencia
congelando o rumo, e o resultado foi trocar o giro por outro defeito.

BUSCA LIMITADA. O mapa tem 2,36 milhoes de celulas e isto corre em Python dentro do laco do
mundo. Uma perseguicao vai no maximo a 200 unidades (20 celulas), portanto a busca fecha-se
numa janela a volta dos dois pontos e num tecto de nos expandidos. Sem isso, um alvo
inalcancavel varreria o mapa inteiro a cada tique.
"""
import heapq
import math
import os
import struct

LADO_CEL = 10.0
MAX_NOS = 3000          # tecto de nos expandidos por busca
MARGEM_JANELA = 25      # celulas de folga a volta da caixa origem-destino

_grelha = None
_larg = _alt = 0


def carregar(mapa="berneo", log=print):
    """Le a grelha de colisao. Devolve True se ficou disponivel."""
    global _grelha, _larg, _alt
    if _grelha is not None:
        return True
    cam = os.path.join(os.path.dirname(os.path.abspath(__file__)),
                       "Data", "Maps", "Colisao_%s.bin" % mapa)
    if not os.path.exists(cam):
        log("[caminho] sem Colisao_%s.bin -- o mob anda em linha recta" % mapa)
        return False
    b = open(cam, "rb").read()
    _larg, _alt, _ = struct.unpack_from("<3I", b, 0)
    _grelha = b[12:]
    bloq = sum(_grelha)
    log("[caminho] grelha %dx%d, %d celulas bloqueadas (%.1f%%)"
        % (_larg, _alt, bloq, 100.0 * bloq / len(_grelha)))
    return True


def livre(cx, cy):
    if not (0 <= cx < _larg and 0 <= cy < _alt):
        return False
    return _grelha[cy * _larg + cx] == 0


def bloqueado_em(x, y):
    """A posicao do mundo (x, y) esta em celula bloqueada?"""
    if _grelha is None:
        return False
    return not livre(int(x // LADO_CEL), int(y // LADO_CEL))


VIZINHOS = ((1, 0, 1.0), (-1, 0, 1.0), (0, 1, 1.0), (0, -1, 1.0),
            (1, 1, 1.4142), (1, -1, 1.4142), (-1, 1, 1.4142), (-1, -1, 1.4142))


def caminho(x0, y0, x1, y1):
    """Lista de pontos (x, y) do mundo, de (x0,y0) ate perto de (x1,y1).

    Devolve [] se nao houver grelha, se o destino for inalcancavel dentro do tecto, ou se a
    linha recta ja servir -- nesse ultimo caso quem chama continua a fazer o que fazia.
    """
    if _grelha is None:
        return []
    a = (int(x0 // LADO_CEL), int(y0 // LADO_CEL))
    b = (int(x1 // LADO_CEL), int(y1 // LADO_CEL))
    if a == b or not livre(*b):
        return []
    if linha_livre(a, b):
        return []                      # sem obstaculo pelo meio: nao vale a pena caminho

    jx0 = min(a[0], b[0]) - MARGEM_JANELA
    jx1 = max(a[0], b[0]) + MARGEM_JANELA
    jy0 = min(a[1], b[1]) - MARGEM_JANELA
    jy1 = max(a[1], b[1]) + MARGEM_JANELA

    def h(n):
        return math.hypot(n[0] - b[0], n[1] - b[1])

    aberto = [(h(a), 0.0, a)]
    veio = {a: None}
    custo = {a: 0.0}
    nos = 0
    while aberto:
        _, g, n = heapq.heappop(aberto)
        if n == b:
            break
        nos += 1
        if nos > MAX_NOS:
            return []
        for dx, dy, w in VIZINHOS:
            m = (n[0] + dx, n[1] + dy)
            if not (jx0 <= m[0] <= jx1 and jy0 <= m[1] <= jy1):
                continue
            if not livre(*m):
                continue
            if dx and dy and not (livre(n[0] + dx, n[1]) and livre(n[0], n[1] + dy)):
                continue               # nao corta esquinas
            ng = g + w
            if ng < custo.get(m, 1e18):
                custo[m] = ng
                veio[m] = n
                heapq.heappush(aberto, (ng + h(m), ng, m))
    if b not in veio:
        return []

    bruto = []
    n = b
    while n is not None:
        bruto.append(n)
        n = veio[n]
    bruto.reverse()
    return [(cx * LADO_CEL + LADO_CEL / 2.0, cy * LADO_CEL + LADO_CEL / 2.0)
            for cx, cy in suavizar(bruto)]


def linha_livre(a, b):
    """Bresenham: da para ir a direito de a ate b sem tocar em celula bloqueada?"""
    x0, y0 = a
    x1, y1 = b
    dx, dy = abs(x1 - x0), abs(y1 - y0)
    sx = 1 if x0 < x1 else -1
    sy = 1 if y0 < y1 else -1
    err = dx - dy
    while True:
        if not livre(x0, y0):
            return False
        if (x0, y0) == (x1, y1):
            return True
        e2 = 2 * err
        if e2 > -dy:
            err -= dy
            x0 += sx
        if e2 < dx:
            err += dx
            y0 += sy


def suavizar(pontos):
    """Tira os pontos que nao sao precisos: fica so onde o caminho MUDA de direccao.

    Sem isto o caminho tem um ponto por celula e o mob volta a dar passos curtos, que e
    exactamente o defeito que se andou a corrigir. Com isto ficam segmentos rectos longos --
    a forma que se mediu no oficial.
    """
    if len(pontos) <= 2:
        return pontos
    saida = [pontos[0]]
    i = 0
    while i < len(pontos) - 1:
        j = len(pontos) - 1
        while j > i + 1 and not linha_livre(pontos[i], pontos[j]):
            j -= 1
        saida.append(pontos[j])
        i = j
    return saida
