基于现有道路路径生成两点间可行走路径的算法需求

现有道路数据结构 #

道路数据存储在coords数组中，每条道路包含路径点、宽度、允许通行类型、是否单向等信息：

const coords = [
  {
    name: "Rijnstraat vervolg",
    points: [
      [695, 500],
      [680, 480],
      [580, 475],
      [520, 460],
    ],
    width: 10,
    types: [types.car, types.truck, types.pedestrian, types.bike],
    oneway: true,
  },
  // ... 更多道路数据
]

需求说明 #

需要实现函数，基于上述道路路径（图中黑线），生成从任意起点（黑/灰圆圈）到任意终点（黑/灰圆圈）的路径点数组，模拟行人沿道路行走的完整路线。

现有实现问题 #

此前尝试的递归函数仅能在部分场景生成到商铺点的路径，多数情况下完全失效，代码如下：

function calculatePathToShop(startPoint, shopPoint) {
  const targetShopPoint = findClosestPointOnPath(shopPoint);
  const targetPathIndex = findPathByPoint(targetShopPoint);
  const connectedPaths = calculateConnectedPaths(targetPathIndex);

  let startPathIndex = -1;
  connectedPaths.forEach(path => {
    const pathPoints = coords[path].points;
    pathPoints.forEach(pathPoint => {
      if (comparePoints(startPoint.point, pathPoint)) startPathIndex = path;
    });
  });

  if (startPathIndex == -1) return false;
  let startPathPoints = coords[startPathIndex].points;
  let targetPathPoints = coords[targetPathIndex].points;

  if (!comparePoints(startPoint.point, startPathPoints[0])) startPathPoints.reverse();

  ctx.strokeStyle = "rgba(255, 0, 0, .05)";
}

完整解决方案 #

1. 构建道路图网络 #

首先将所有道路转换为图结构，方便路径搜索：

• 以道路的端点作为图的节点
• 道路作为节点间的边，标记通行方向（oneway）、行人权限、以及道路长度（作为路径权重）
• 处理浮点数精度问题：判断两点是否重合时，用距离阈值（如<1）替代严格相等

2. 起点/终点预处理 #

• 若起点/终点不在道路端点上，先找到其距离最近的允许行人通行的道路段
• 生成从起点到该道路最近端点、以及该道路端点到终点的临时路径段，加入图中用于搜索

3. 最短路径搜索 #

使用Dijkstra算法（适合正权重的道路网络）计算起点到终点的最短道路序列：

• 算法核心是维护节点到起点的距离，每次选择距离最小的节点更新相邻节点的距离
• 记录路径的前驱节点和对应的道路索引，用于回溯生成道路序列

4. 路径点拼接 #

将搜索得到的道路序列转换为连续的路径点数组：

• 根据道路的连通方向，决定是否反转道路的points数组
• 拼接时跳过重复的端点，保证路径连续
• 补充起点到道路端点、道路端点到终点的路径点（可通过线性插值生成平滑过渡点）

核心代码实现 #

图结构构建

// 图结构：key为节点坐标字符串（如"x,y"），value为相邻节点列表
const graph = new Map();

// 遍历所有道路，生成图的边
coords.forEach((road, roadIndex) => {
  // 跳过不允许行人通行的道路
  if (!road.types.includes(types.pedestrian)) return;

  const points = road.points;
  // 计算道路总长度作为权重
  let totalLength = 0;
  for (let i = 0; i < points.length - 1; i++) {
    const dx = points[i+1][0] - points[i][0];
    const dy = points[i+1][1] - points[i][1];
    totalLength += Math.sqrt(dx * dx + dy * dy);
  }

  const startKey = points[0].join(',');
  const endKey = points[points.length - 1].join(',');

  // 添加正向边
  if (!graph.has(startKey)) graph.set(startKey, []);
  graph.get(startKey).push({
    node: endKey,
    roadIndex,
    length: totalLength,
    isOneway: road.oneway
  });

  // 非单向道路添加反向边
  if (!road.oneway) {
    if (!graph.has(endKey)) graph.set(endKey, []);
    graph.get(endKey).push({
      node: startKey,
      roadIndex,
      length: totalLength,
      isOneway: false
    });
  }
});

Dijkstra路径搜索

function findShortestRoads(startNodeKey, endNodeKey, graph) {
  const distances = new Map();
  const previous = new Map();
  const visited = new Set();

  // 初始化所有节点距离为无穷大
  graph.forEach((_, key) => distances.set(key, Infinity));
  distances.set(startNodeKey, 0);

  while (visited.size < graph.size) {
    // 找到当前未访问的距离最小节点
    let currentKey = null;
    let minDist = Infinity;
    distances.forEach((dist, key) => {
      if (!visited.has(key) && dist < minDist) {
        minDist = dist;
        currentKey = key;
      }
    });

    // 找不到节点或到达终点，终止循环
    if (!currentKey || currentKey === endNodeKey) break;
    visited.add(currentKey);

    // 更新相邻节点的距离
    const neighbors = graph.get(currentKey) || [];
    neighbors.forEach(neighbor => {
      const newDist = distances.get(currentKey) + neighbor.length;
      if (newDist < distances.get(neighbor.node)) {
        distances.set(neighbor.node, newDist);
        previous.set(neighbor.node, {
          fromKey: currentKey,
          roadIndex: neighbor.roadIndex
        });
      }
    });
  }

  // 回溯生成道路索引序列
  const roadSequence = [];
  let current = endNodeKey;
  while (previous.has(current)) {
    const prevData = previous.get(current);
    roadSequence.unshift(prevData.roadIndex);
    current = prevData.fromKey;
  }

  return roadSequence;
}

路径点拼接

// 辅助函数：判断两点是否重合（带精度容错）
function isSamePoint(p1, p2) {
  const dx = p1[0] - p2[0];
  const dy = p1[1] - p2[1];
  return Math.sqrt(dx*dx + dy*dy) < 1;
}

// 生成最终路径点数组
function buildPathPoints(startPoint, endPoint, roadSequence) {
  const finalPoints = [startPoint];
  let lastPoint = startPoint;

  // 先处理起点到最近道路端点的路径（需实现findClosestRoadEndpoint函数）
  const { closestEndpoint: startEndpoint } = findClosestRoadEndpoint(startPoint);
  // 线性插值添加中间点（示例简化，直接添加端点）
  finalPoints.push(startEndpoint);
  lastPoint = startEndpoint;

  // 遍历道路序列，拼接路径点
  roadSequence.forEach(roadIndex => {
    const road = coords[roadIndex];
    let roadPoints = [...road.points];

    // 判断道路方向是否需要反转
    const roadStart = roadPoints[0];
    const roadEnd = roadPoints[roadPoints.length - 1];
    if (!isSamePoint(lastPoint, roadStart)) {
      if (isSamePoint(lastPoint, roadEnd)) {
        roadPoints.reverse();
      } else {
        console.warn("道路段不连通，跳过");
        return;
      }
    }

    // 跳过重复的端点，添加剩余路径点
    finalPoints.push(...roadPoints.slice(1));
    lastPoint = roadPoints[roadPoints.length - 1];
  });

  // 处理道路端点到终点的路径
  const { closestEndpoint: endEndpoint } = findClosestRoadEndpoint(endPoint);
  finalPoints.push(endEndpoint);
  finalPoints.push(endPoint);

  return finalPoints;
}

补充说明 #

• 需实现findClosestRoadEndpoint函数：计算点到所有允许行人道路的最短距离，找到最近的道路端点
• 若需要更平滑的路径，可以在起点/终点与道路端点之间添加线性插值的中间点
• 处理单向道路时，严格按照oneway属性限制通行方向，避免生成违规路径

内容的提问来源于stack exchange，提问作者CodeFoxDev