A* (A-Star) Algoritması

1// A* algoritması JavaScript implementasyonu
2class AStarPathfinder {
3  constructor(grid, heuristicFunction = 'manhattan') {
4    this.grid = grid;
5    this.heuristicFunction = heuristicFunction;
6  }
7
8  // Ana A* algoritması - en kısa yolu hesaplar
9  findPath(start, goal) {
10    const openSet = new PriorityQueue();
11    const closedSet = new Set();
12    const gScore = new Map();
13    const fScore = new Map();
14    const cameFrom = new Map();
15
16    // Başlangıç düğümünü ayarla
17    gScore.set(this.getNodeKey(start), 0);
18    fScore.set(this.getNodeKey(start), this.heuristic(start, goal));
19    openSet.enqueue(start, fScore.get(this.getNodeKey(start)));
20
21    while (!openSet.isEmpty()) {
22      const current = openSet.dequeue();
23      const currentKey = this.getNodeKey(current);
24
25      // Hedefe ulaştık mı kontrol et
26      if (this.isGoal(current, goal)) {
27        return this.reconstructPath(cameFrom, current);
28      }
29
30      closedSet.add(currentKey);
31
32      // Komşu düğümleri işle
33      for (const neighbor of this.getNeighbors(current)) {
34        const neighborKey = this.getNodeKey(neighbor);
35        
36        if (closedSet.has(neighborKey) || this.isObstacle(neighbor)) {
37          continue;
38        }
39
40        const tentativeGScore = gScore.get(currentKey) + 
41                               this.getDistance(current, neighbor);
42
43        if (!gScore.has(neighborKey) || tentativeGScore < gScore.get(neighborKey)) {
44          cameFrom.set(neighborKey, current);
45          gScore.set(neighborKey, tentativeGScore);
46          fScore.set(neighborKey, tentativeGScore + this.heuristic(neighbor, goal));
47
48          if (!openSet.contains(neighbor)) {
49            openSet.enqueue(neighbor, fScore.get(neighborKey));
50          }
51        }
52      }
53    }
54
55    return []; // Yol bulunamadı
56  }
57
58  // Heuristik fonksiyon - hedef düğüme tahmini mesafe
59  heuristic(node, goal) {
60    switch (this.heuristicFunction) {
61      case 'manhattan':
62        return Math.abs(node.x - goal.x) + Math.abs(node.y - goal.y);
63      case 'euclidean':
64        return Math.sqrt(Math.pow(node.x - goal.x, 2) + Math.pow(node.y - goal.y, 2));
65      case 'diagonal':
66        return Math.max(Math.abs(node.x - goal.x), Math.abs(node.y - goal.y));
67      default:
68        return 0;
69    }
70  }
71
72  // İki düğüm arası gerçek mesafe hesapla
73  getDistance(node1, node2) {
74    return Math.sqrt(
75      Math.pow(node2.x - node1.x, 2) + Math.pow(node2.y - node1.y, 2)
76    );
77  }
78
79  // Komşu düğümleri getir (8-yönlü hareket)
80  getNeighbors(node) {
81    const neighbors = [];
82    const directions = [
83      { x: -1, y: -1 }, { x: 0, y: -1 }, { x: 1, y: -1 },
84      { x: -1, y: 0 },                    { x: 1, y: 0 },
85      { x: -1, y: 1 },  { x: 0, y: 1 },  { x: 1, y: 1 }
86    ];
87
88    for (const dir of directions) {
89      const newX = node.x + dir.x;
90      const newY = node.y + dir.y;
91
92      if (this.isValidPosition(newX, newY)) {
93        neighbors.push({ x: newX, y: newY });
94      }
95    }
96
97    return neighbors;
98  }
99
100  // Yolu yeniden oluştur
101  reconstructPath(cameFrom, current) {
102    const path = [current];
103    let currentKey = this.getNodeKey(current);
104
105    while (cameFrom.has(currentKey)) {
106      current = cameFrom.get(currentKey);
107      path.unshift(current);
108      currentKey = this.getNodeKey(current);
109    }
110
111    return path;
112  }
113
114  // Yardımcı fonksiyonlar
115  getNodeKey(node) {
116    return `${node.x},${node.y}`;
117  }
118
119  isGoal(node, goal) {
120    return node.x === goal.x && node.y === goal.y;
121  }
122
123  isValidPosition(x, y) {
124    return x >= 0 && x < this.grid.width && y >= 0 && y < this.grid.height;
125  }
126
127  isObstacle(node) {
128    return this.grid.data[node.y][node.x] === 1;
129  }
130}
131
132// Priority Queue implementasyonu
133class PriorityQueue {
134  constructor() {
135    this.items = [];
136  }
137
138  enqueue(element, priority) {
139    const queueElement = { element, priority };
140    let added = false;
141
142    for (let i = 0; i < this.items.length; i++) {
143      if (queueElement.priority < this.items[i].priority) {
144        this.items.splice(i, 0, queueElement);
145        added = true;
146        break;
147      }
148    }
149
150    if (!added) {
151      this.items.push(queueElement);
152    }
153  }
154
155  dequeue() {
156    return this.items.shift()?.element;
157  }
158
159  isEmpty() {
160    return this.items.length === 0;
161  }
162
163  contains(element) {
164    return this.items.some(item => 
165      item.element.x === element.x && item.element.y === element.y
166    );
167  }
168}