import { areLinesReverseDirection, areLinesSameDirection } from "../edge";
import {
  ControlPoint,
  NodeRect,
  isEqualPoint,
  isSegmentCrossingRect,
} from "../point";

interface GetAStarPathParams {
  /**
   * Collection of potential control points between `sourceOffset` and `targetOffset`, excluding the `source` and `target` points.
   */
  points: ControlPoint[];
  source: ControlPoint;
  target: ControlPoint;
  /**
   * Node size information for the `source` and `target`, used to optimize edge routing without intersecting nodes.
   */
  sourceRect: NodeRect;
  targetRect: NodeRect;
}

/**
 * Utilizes the [A\* search algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm) combined with
 * [Manhattan Distance](https://simple.wikipedia.org/wiki/Manhattan_distance) to find the optimal path for edges.
 * 
 * @returns Control points including sourceOffset and targetOffset (not including source and target points).
 */
export const getAStarPath = ({
  points,
  source,
  target,
  sourceRect,
  targetRect,
}: GetAStarPathParams): ControlPoint[] => {
  if (points.length < 3) {
    return points;
  }
  const start = points[0];
  const end = points[points.length - 1];
  const openSet: ControlPoint[] = [start];
  const closedSet: Set<ControlPoint> = new Set();
  const cameFrom: Map<ControlPoint, ControlPoint> = new Map();
  const gScore: Map<ControlPoint, number> = new Map().set(start, 0);
  const fScore: Map<ControlPoint, number> = new Map().set(
    start,
    heuristicCostEstimate({
      from: start,
      to: start,
      start,
      end,
      source,
      target,
    })
  );

  while (openSet.length) {
    let current;
    let currentIdx;
    let lowestFScore = Infinity;
    openSet.forEach((p, idx) => {
      const score = fScore.get(p) ?? 0;
      if (score < lowestFScore) {
        lowestFScore = score;
        current = p;
        currentIdx = idx;
      }
    });

    if (!current) {
      break;
    }

    if (current === end) {
      return buildPath(cameFrom, current);
    }

    openSet.splice(currentIdx!, 1);
    closedSet.add(current);

    const curFScore = fScore.get(current) ?? 0;
    const previous = cameFrom.get(current);
    const neighbors = getNextNeighborPoints({
      points,
      previous,
      current,
      sourceRect,
      targetRect,
    });
    for (const neighbor of neighbors) {
      if (closedSet.has(neighbor)) {
        continue;
      }
      const neighborGScore = gScore.get(neighbor) ?? 0;
      const tentativeGScore = curFScore + estimateDistance(current, neighbor);
      if (openSet.includes(neighbor) && tentativeGScore >= neighborGScore) {
        continue;
      }
      openSet.push(neighbor);
      cameFrom.set(neighbor, current);
      gScore.set(neighbor, tentativeGScore);
      fScore.set(
        neighbor,
        neighborGScore +
        heuristicCostEstimate({
          from: current,
          to: neighbor,
          start,
          end,
          source,
          target,
        })
      );
    }
  }
  return [start, end];
};

const buildPath = (
  cameFrom: Map<ControlPoint, ControlPoint>,
  current: ControlPoint
): ControlPoint[] => {
  const path = [current];

  let previous = cameFrom.get(current);
  while (previous) {
    path.push(previous);
    previous = cameFrom.get(previous);
  }

  return path.reverse();
};

interface GetNextNeighborPointsParams {
  points: ControlPoint[];
  previous?: ControlPoint;
  current: ControlPoint;
  sourceRect: NodeRect;
  targetRect: NodeRect;
}

/**
 * Get the set of possible neighboring points for the current control point
 *
 * - The line is in a horizontal or vertical direction
 * - The line does not intersect with the two end nodes
 * - The line does not overlap with the previous line segment in reverse direction
 */
export const getNextNeighborPoints = ({
  points,
  previous,
  current,
  sourceRect,
  targetRect,
}: GetNextNeighborPointsParams): ControlPoint[] => {
  return points.filter((p) => {
    if (p === current) {
      return false;
    }
    // The connection is in the horizontal or vertical direction
    const rightDirection = p.x === current.x || p.y === current.y;
    // Reverse direction with the previous line segment (overlap)
    const reverseDirection = previous
      ? areLinesReverseDirection(previous, current, current, p)
      : false;
    return (
      rightDirection && // The line is in a horizontal or vertical direction
      !reverseDirection && // The line does not overlap with the previous line segment in reverse direction
      !isSegmentCrossingRect(p, current, sourceRect) && // Does not intersect with sourceNode
      !isSegmentCrossingRect(p, current, targetRect) // Does not intersect with targetNode
    );
  });
};

/**
 * 路径规划所需的启发式代价计算参数接口
 * 包含了计算路径代价所需的所有控制点信息:
 * - from/to: 当前路径段的起点和终点
 * - start/end: 整条路径的起点和终点
 * - source/target: 连接的源节点和目标节点位置
 */
interface HeuristicCostParams {
  from: ControlPoint;    // 当前路径段的起点
  to: ControlPoint;      // 当前路径段的终点
  start: ControlPoint;   // 整条路径的起始点
  end: ControlPoint;     // 整条路径的终点
  source: ControlPoint;  // 源节点的连接点
  target: ControlPoint;  // 目标节点的连接点
}

/**
 * 启发式路径代价估算函数
 * 
 * 该函数通过多个因素综合评估路径的优劣程度:
 * 1. 基础代价: 当前点到起点和终点的曼哈顿距离之和
 * 2. 起点优化: 如果是起始段,判断方向一致性给予奖励
 * 3. 终点优化: 如果是结束段,判断方向一致性给予奖励
 * 
 * 优化目标:
 * - 减少路径总长度
 * - 保持路径走向的连续性
 * - 使拐点在路径中更均匀分布
 * 
 * @param params 包含所有必要控制点的参数对象
 * @returns 计算得到的启发式代价值,值越小路径越优
 */
const heuristicCostEstimate = ({
  from,
  to,
  start,
  end,
  source,
  target,
}: HeuristicCostParams): number => {
  // 计算基础代价 - 到起点和终点的距离之和
  const base = estimateDistance(to, start) + estimateDistance(to, end);

  // 起点方向优化 - 如果是起始段且方向一致,给予奖励
  const startCost = isEqualPoint(from, start)
    ? areLinesSameDirection(from, to, source, start)
      ? -base / 2  // 方向一致时减少代价
      : 0
    : 0;

  // 终点方向优化 - 如果是结束段且方向一致,给予奖励  
  const endCost = isEqualPoint(to, end)
    ? areLinesSameDirection(from, to, end, target)
      ? -base / 2  // 方向一致时减少代价
      : 0
    : 0;

  return base + startCost + endCost;
};

/**
 * 计算两点间的估计距离
 * 
 * 采用曼哈顿距离(Manhattan distance)计算:
 * - 只计算水平和垂直方向的距离之和
 * - 避免使用欧几里得距离的开方运算
 * - 在网格化的路径规划中性能更优
 * 
 * @param p1 第一个控制点
 * @param p2 第二个控制点
 * @returns 两点间的曼哈顿距离
 */
const estimateDistance = (p1: ControlPoint, p2: ControlPoint): number =>
  Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);