1  /**
  2   * Motor de cálculo de rutas 100% offline
  3   * Implementa algoritmos de búsqueda de caminos para calcular rutas sin acceso a Internet
  4   */
  5  import { browser } from '$app/environment';
  6  import type { Place, RoutePoint, RouteStep, RouteResult } from '../models';
  7  
  8  // Now using interfaces imported from models.ts
  9  
 10  // Interfaz para nodos del grafo de la red de carreteras
 11  interface Node {
 12    id: string;
 13    lat: number;
 14    lng: number;
 15    connections: Connection[];
 16  }
 17  
 18  // Interfaz para conexiones entre nodos
 19  interface Connection {
 20    targetId: string;
 21    distance: number;  // Metros
 22    duration: number;  // Segundos
 23    wayName: string;
 24    wayType: string;
 25  }
 26  
 27  // Interfaz para grafo de carreteras
 28  interface RoadGraph {
 29    nodes: Record<string, Node>;
 30    version: string;
 31    lastUpdated: number;
 32  }
 33  
 34  // Datos de muestra para un grafo de carreteras simplificado
 35  // En una implementación real, estos datos se cargarían de un archivo generado
 36  // a partir de datos OSM (OpenStreetMap)
 37  const SAMPLE_GRAPH: RoadGraph = {
 38    version: "1.0",
 39    lastUpdated: Date.now(),
 40    nodes: {
 41      // Madrid - Puerta del Sol
 42      "n1": {
 43        id: "n1",
 44        lat: 40.416705, 
 45        lng: -3.703582,
 46        connections: [
 47          { 
 48            targetId: "n2", 
 49            distance: 380, 
 50            duration: 300, 
 51            wayName: "Calle Mayor", 
 52            wayType: "street" 
 53          },
 54          { 
 55            targetId: "n5", 
 56            distance: 450, 
 57            duration: 360, 
 58            wayName: "Calle Alcalá", 
 59            wayType: "street" 
 60          }
 61        ]
 62      },
 63      // Plaza Mayor
 64      "n2": {
 65        id: "n2",
 66        lat: 40.415557, 
 67        lng: -3.707233,
 68        connections: [
 69          { 
 70            targetId: "n1", 
 71            distance: 380, 
 72            duration: 300, 
 73            wayName: "Calle Mayor", 
 74            wayType: "street" 
 75          },
 76          { 
 77            targetId: "n3", 
 78            distance: 900, 
 79            duration: 720, 
 80            wayName: "Calle Toledo", 
 81            wayType: "street" 
 82          }
 83        ]
 84      },
 85      // Plaza de Cascorro
 86      "n3": {
 87        id: "n3",
 88        lat: 40.410996, 
 89        lng: -3.707416,
 90        connections: [
 91          { 
 92            targetId: "n2", 
 93            distance: 900, 
 94            duration: 720, 
 95            wayName: "Calle Toledo", 
 96            wayType: "street" 
 97          },
 98          { 
 99            targetId: "n4", 
100            distance: 650, 
101            duration: 520, 
102            wayName: "Calle Embajadores", 
103            wayType: "street" 
104          }
105        ]
106      },
107      // Glorieta de Embajadores
108      "n4": {
109        id: "n4",
110        lat: 40.405936, 
111        lng: -3.703595,
112        connections: [
113          { 
114            targetId: "n3", 
115            distance: 650, 
116            duration: 520, 
117            wayName: "Calle Embajadores", 
118            wayType: "street" 
119          },
120          { 
121            targetId: "n6", 
122            distance: 950, 
123            duration: 760, 
124            wayName: "Paseo de las Delicias", 
125            wayType: "avenue" 
126          }
127        ]
128      },
129      // Museo del Prado
130      "n5": {
131        id: "n5",
132        lat: 40.413561, 
133        lng: -3.692479,
134        connections: [
135          { 
136            targetId: "n1", 
137            distance: 450, 
138            duration: 360, 
139            wayName: "Calle Alcalá", 
140            wayType: "street" 
141          },
142          { 
143            targetId: "n7", 
144            distance: 1200, 
145            duration: 960, 
146            wayName: "Paseo del Prado", 
147            wayType: "avenue" 
148          }
149        ]
150      },
151      // Estación de Atocha
152      "n6": {
153        id: "n6",
154        lat: 40.406514, 
155        lng: -3.691481,
156        connections: [
157          { 
158            targetId: "n4", 
159            distance: 950, 
160            duration: 760, 
161            wayName: "Paseo de las Delicias", 
162            wayType: "avenue" 
163          },
164          { 
165            targetId: "n7", 
166            distance: 500, 
167            duration: 400, 
168            wayName: "Paseo de la Infanta Isabel", 
169            wayType: "avenue" 
170          }
171        ]
172      },
173      // Parque del Retiro (Puerta de Alcalá)
174      "n7": {
175        id: "n7",
176        lat: 40.420512, 
177        lng: -3.688133,
178        connections: [
179          { 
180            targetId: "n5", 
181            distance: 1200, 
182            duration: 960, 
183            wayName: "Paseo del Prado", 
184            wayType: "avenue" 
185          },
186          { 
187            targetId: "n6", 
188            distance: 500, 
189            duration: 400, 
190            wayName: "Paseo de la Infanta Isabel", 
191            wayType: "avenue" 
192          }
193        ]
194      }
195    }
196  };
197  
198  // Cargar el grafo de carreteras
199  export async function loadRoadGraph(): Promise<RoadGraph> {
200    if (!browser) {
201      return SAMPLE_GRAPH;
202    }
203    
204    try {
205      // En una implementación real, cargaríamos desde un archivo o IndexedDB
206      // Para esta demostración, usamos el grafo estático
207      return SAMPLE_GRAPH;
208    } catch (error) {
209      console.error('[routing-engine] Error al cargar grafo de carreteras:', error);
210      return SAMPLE_GRAPH;
211    }
212  }
213  
214  // Calcular una ruta entre dos puntos
215  export async function calculateOfflineRoute(
216    startPoint: RoutePoint | Place,
217    endPoint: RoutePoint | Place,
218    viaPoints: (RoutePoint | Place)[] = []
219  ): Promise<RouteResult> {
220    if (!browser) {
221      throw new Error('Solo disponible en el navegador');
222    }
223    
224    try {
225      // Cargar grafo de carreteras
226      const roadGraph = await loadRoadGraph();
227      
228      // Encontrar nodos más cercanos a los puntos
229      const startNode = findNearestNode(roadGraph, startPoint.lat, startPoint.lng);
230      const endNode = findNearestNode(roadGraph, endPoint.lat, endPoint.lng);
231      
232      // Convertir viaPoints a nodos
233      const viaNodes = viaPoints.map(point => 
234        findNearestNode(roadGraph, point.lat, point.lng)
235      );
236      
237      // Si no hay puntos intermedios, calculamos la ruta directa
238      if (viaNodes.length === 0) {
239        const route = findPath(roadGraph, startNode.id, endNode.id);
240        return formatRouteResult(roadGraph, route, startPoint, endPoint, []);
241      }
242      
243      // Si hay puntos intermedios, calculamos la ruta por partes
244      const routeParts = [];
245      let currentStart = startNode;
246      
247      // Para cada punto intermedio
248      for (const viaNode of viaNodes) {
249        const routePart = findPath(roadGraph, currentStart.id, viaNode.id);
250        routeParts.push(routePart);
251        currentStart = viaNode;
252      }
253      
254      // Última parte de la ruta
255      const lastPart = findPath(roadGraph, currentStart.id, endNode.id);
256      routeParts.push(lastPart);
257      
258      // Unir todas las partes
259      const combinedRoute = combineRoutes(routeParts);
260      
261      // Formatear resultado
262      return formatRouteResult(roadGraph, combinedRoute, startPoint, endPoint, viaPoints);
263    } catch (error) {
264      console.error('[routing-engine] Error al calcular ruta:', error);
265      throw error;
266    }
267  }
268  
269  // Encontrar el nodo más cercano a unas coordenadas
270  function findNearestNode(graph: RoadGraph, lat: number, lng: number): Node {
271    const nodes = Object.values(graph.nodes);
272    
273    // Encontrar el nodo más cercano usando la distancia euclidiana
274    let nearestNode = nodes[0];
275    let minDistance = calculateDistance(lat, lng, nearestNode.lat, nearestNode.lng);
276    
277    for (const node of nodes) {
278      const distance = calculateDistance(lat, lng, node.lat, node.lng);
279      
280      if (distance < minDistance) {
281        minDistance = distance;
282        nearestNode = node;
283      }
284    }
285    
286    return nearestNode;
287  }
288  
289  // Calcular distancia en metros entre dos puntos
290  function calculateDistance(lat1: number, lng1: number, lat2: number, lng2: number): number {
291    const R = 6371000; // Radio de la Tierra en metros
292    const dLat = toRadians(lat2 - lat1);
293    const dLng = toRadians(lng2 - lng1);
294    
295    const a = 
296      Math.sin(dLat/2) * Math.sin(dLat/2) +
297      Math.cos(toRadians(lat1)) * Math.cos(toRadians(lat2)) * 
298      Math.sin(dLng/2) * Math.sin(dLng/2);
299    
300    const c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
301    const distance = R * c;
302    
303    return distance;
304  }
305  
306  // Convertir grados a radianes
307  function toRadians(degrees: number): number {
308    return degrees * Math.PI / 180;
309  }
310  
311  // Interfaz para representar un camino
312  interface Path {
313    nodes: string[];
314    totalDistance: number;
315    totalDuration: number;
316    steps: {
317      fromId: string;
318      toId: string;
319      connection: Connection;
320    }[];
321  }
322  
323  // Algoritmo de Dijkstra para encontrar la ruta más corta entre dos nodos
324  function findPath(graph: RoadGraph, startId: string, endId: string): Path {
325    // Inicializar distancias y nodos previos
326    const distances: Record<string, number> = {};
327    const durations: Record<string, number> = {};
328    const previous: Record<string, string | null> = {};
329    const connections: Record<string, Connection> = {};
330    
331    // Inicializar con valores infinitos
332    Object.keys(graph.nodes).forEach(nodeId => {
333      distances[nodeId] = Infinity;
334      durations[nodeId] = Infinity;
335      previous[nodeId] = null;
336    });
337    
338    // Distancia y duración desde el inicio a sí mismo es 0
339    distances[startId] = 0;
340    durations[startId] = 0;
341    
342    // Conjunto de nodos no visitados
343    const unvisited = new Set(Object.keys(graph.nodes));
344    
345    // Mientras haya nodos no visitados
346    while (unvisited.size > 0) {
347      // Encontrar el nodo no visitado con la menor distancia
348      let current: string | null = null;
349      let minDistance = Infinity;
350      
351      for (const nodeId of unvisited) {
352        if (distances[nodeId] < minDistance) {
353          minDistance = distances[nodeId];
354          current = nodeId;
355        }
356      }
357      
358      // Si no hay nodos alcanzables, terminar
359      if (current === null || distances[current] === Infinity) {
360        break;
361      }
362      
363      // Si hemos llegado al destino, terminar
364      if (current === endId) {
365        break;
366      }
367      
368      // Marcar como visitado
369      unvisited.delete(current);
370      
371      // Actualizar distancias de los vecinos
372      const node = graph.nodes[current];
373      
374      for (const connection of node.connections) {
375        // Si el nodo ya está visitado, ignorar
376        if (!unvisited.has(connection.targetId)) {
377          continue;
378        }
379        
380        // Calcular nueva distancia
381        const newDistance = distances[current] + connection.distance;
382        const newDuration = durations[current] + connection.duration;
383        
384        // Si la nueva distancia es menor, actualizar
385        if (newDistance < distances[connection.targetId]) {
386          distances[connection.targetId] = newDistance;
387          durations[connection.targetId] = newDuration;
388          previous[connection.targetId] = current;
389          connections[connection.targetId] = connection;
390        }
391      }
392    }
393    
394    // Reconstruir el camino
395    const path: string[] = [];
396    const steps: { fromId: string; toId: string; connection: Connection }[] = [];
397    let current = endId;
398    
399    // Si no hay camino al destino
400    if (previous[current] === null && current !== startId) {
401      throw new Error(`No se pudo encontrar una ruta entre ${startId} y ${endId}`);
402    }
403    
404    // Reconstruir el camino desde el final hasta el inicio
405    while (current) {
406      path.unshift(current);
407      
408      if (previous[current] !== null) {
409        steps.unshift({
410          fromId: previous[current]!,
411          toId: current,
412          connection: connections[current]
413        });
414      }
415      
416      current = previous[current]!;
417      
418      if (current === null || current === startId) {
419        path.unshift(startId);
420        break;
421      }
422    }
423    
424    // Retornar el camino completo
425    return {
426      nodes: path,
427      totalDistance: distances[endId],
428      totalDuration: durations[endId],
429      steps
430    };
431  }
432  
433  // Combinar varias rutas en una sola
434  function combineRoutes(routes: Path[]): Path {
435    if (routes.length === 0) {
436      throw new Error('No hay rutas para combinar');
437    }
438    
439    if (routes.length === 1) {
440      return routes[0];
441    }
442    
443    // Inicializar con la primera ruta
444    const combinedRoute: Path = {
445      nodes: [...routes[0].nodes],
446      totalDistance: routes[0].totalDistance,
447      totalDuration: routes[0].totalDuration,
448      steps: [...routes[0].steps]
449    };
450    
451    // Añadir el resto de rutas
452    for (let i = 1; i < routes.length; i++) {
453      const route = routes[i];
454      
455      // Añadir nodos (excepto el primero que ya está incluido)
456      combinedRoute.nodes.push(...route.nodes.slice(1));
457      
458      // Añadir pasos
459      combinedRoute.steps.push(...route.steps);
460      
461      // Actualizar distancia y duración totales
462      combinedRoute.totalDistance += route.totalDistance;
463      combinedRoute.totalDuration += route.totalDuration;
464    }
465    
466    return combinedRoute;
467  }
468  
469  // Formatear resultado de la ruta
470  function formatRouteResult(
471    graph: RoadGraph,
472    path: Path,
473    startPoint: RoutePoint | Place,
474    endPoint: RoutePoint | Place,
475    viaPoints: (RoutePoint | Place)[]
476  ): RouteResult {
477    // Crear pasos de la ruta
478    const steps: RouteStep[] = path.steps.map(step => {
479      const fromNode = graph.nodes[step.fromId];
480      const toNode = graph.nodes[step.toId];
481      
482      return {
483        distance: step.connection.distance,
484        duration: step.connection.duration,
485        name: step.connection.wayName,
486        type: step.connection.wayType,
487        instruction: generateInstruction(step.connection.wayName, step.connection.wayType),
488        startPoint: {
489          lat: fromNode.lat,
490          lng: fromNode.lng
491        },
492        endPoint: {
493          lat: toNode.lat,
494          lng: toNode.lng
495        }
496      };
497    });
498    
499    // Crear geometría GeoJSON para la ruta
500    const coordinates = path.nodes.map(nodeId => {
501      const node = graph.nodes[nodeId];
502      return [node.lng, node.lat]; // GeoJSON usa [longitud, latitud]
503    });
504    
505    const geometry = {
506      type: "LineString",
507      coordinates
508    };
509    
510    // Asegurar que startPoint y endPoint tienen el formato correcto
511    const start: RoutePoint = {
512      lat: startPoint.lat,
513      lng: startPoint.lng,
514      name: 'name' in startPoint ? startPoint.name : 'Inicio'
515    };
516    
517    const end: RoutePoint = {
518      lat: endPoint.lat,
519      lng: endPoint.lng,
520      name: 'name' in endPoint ? endPoint.name : 'Destino'
521    };
522    
523    // Formatear puntos intermedios
524    const via: RoutePoint[] = viaPoints.map(point => ({
525      lat: point.lat,
526      lng: point.lng,
527      name: 'name' in point ? point.name : 'Punto intermedio'
528    }));
529    
530    // Crear resultado final
531    return {
532      distance: path.totalDistance,
533      duration: path.totalDuration,
534      startPoint: start,
535      endPoint: end,
536      viaPoints: via,
537      steps,
538      geometry: {
539        type: "Feature",
540        properties: {},
541        geometry
542      }
543    };
544  }
545  
546  // Generar instrucción de navegación basada en el nombre y tipo de vía
547  function generateInstruction(wayName: string, wayType: string): string {
548    const typeText = wayType === 'avenue' ? 'el paseo' : 'la calle';
549    return `Continúa por ${typeText} ${wayName}`;
550  }