‏A* رو با لندمارک‌ها سریع‌تر کن

رد بلاب گیمز (Red Blob Games) تو یه صفحهٔ تعاملی تازه سراغ یکی از کم‌کدترین ترفندهای سریع‌کردن A* رفته: هیوریستیک تفاضلی (differential heuristic)، معروف به روش لندمارک. نویسنده می‌گه از ۲۰۰۷ با این تکنیک آشنا شده و از ۲۰۱۵ چند بار برای نوشتن این صفحه تلاش کرده و هر بار رهاش کرده، چون خودش هنوز خوب نفهمیده بودش. حرف اصلی‌ش اینه که کل تغییر فقط تو تابع هیوریستیکه و خود الگوریتم A* یه خط هم عوض نمی‌شه.

مشکل از اینجا شروع می‌شه که هیوریستیک معمول — فاصلهٔ منهتن یا اقلیدسی — از دیوارها و ساختار نقشه بی‌خبره، پس گاهی جست‌وجو رو به سمت اشتباه هل می‌ده و کلی خونهٔ اضافه بررسی می‌شه. ایدهٔ لندمارک اینه که چند نقطهٔ ثابت روی نقشه انتخاب کنی و فاصلهٔ همهٔ گره‌ها تا اون‌ها رو از قبل حساب کنی. مثال خود نویسنده: «از خونه‌ات به سمت برج ایفل راه بیفت تا برسی به خونهٔ دانیل» — لندمارک مقصد نیست، فقط جهت رو می‌ده.

پشتوانهٔ ریاضی‌ش نامساوی مثلثه: چون cost(B, X) + cost(X, L) ≥ cost(B, L)، پس cost(B, X) ≥ cost(B, L) - cost(X, L). یعنی از روی فاصله‌های ازپیش‌حساب‌شده تا لندمارک می‌شه یه حد پایینِ معتبر برای فاصلهٔ واقعی ساخت. با چند لندمارک، هر کدوم یه حد پایین می‌ده و کافیه بزرگ‌ترین‌شون رو برداری. تابع هیوریستیک تقریباً همینه:

function heuristicLandmark(B, X) {
    let h = heuristicManhattan(B, X); // or any base heuristic
    for (let i = 0; i < L.length; i++) {
        let lowerBound = L_cost[B][i] - L_cost[X][i];
        lowerBound = Math.abs(lowerBound); // if undirected
        if (lowerBound > h) { h = lowerBound; }
    }
    return h;
}

جای لندمارک‌ها مهمه: یه لندمارک وقتی کمک می‌کنه که «بعدِ» مقصد باشه، برای همین یه دونه هیچ‌وقت کافی نیست. انتخاب تعداد و محل‌شون به پروژه بستگی داره — اینکه همهٔ مسیرها به یه اندازه محتمل‌ان یا نه، و نقشه ثابته یا تغییر می‌کنه. نویسنده یه روش خودکار هم نشون می‌ده: چند مسیر تصادفی بگیر و ببین کدوم نقطه‌ها برای بیشترشون مفیدن. خبر خوب اینه که لندمارکِ بدجا هم بدتر از هیوریستیک معمولی نیست.

برای نقشه‌های متغیر یه هشدار می‌ده: اگه هزینهٔ یه یال کم بشه و جدول به‌روز نشه، هیوریستیک بیش‌برآورد می‌کنه و A* ممکنه مسیر غیربهینه برگردونه؛ اگه زیاد بشه، جواب بهینه می‌مونه ولی جست‌وجو کندتر می‌شه. تو دموهای صفحه، نقشه‌های Dragon Age و Cogmind و یه ماز تست شدن؛ مخصوصاً تو ماز — که A* معمولی توش خیلی بد عمل می‌کنه — همون چهار تا لندمارک تفاوت بزرگی می‌سازه. خود نویسنده تأکید می‌کنه هنوز تو پروژهٔ واقعی ازش استفاده نکرده.

نکات کلیدی:

• تغییر فقط تو تابع هیوریستیکه؛ کد A* دست‌نخورده می‌مونه و کل پیاده‌سازی گاهی حدود ۲۰ خطه
• پیش‌پردازش: برای هر لندمارک یه بار دایکسترا (یا BFS اگه وزن‌ها ۱ باشن) و ذخیره تو آرایهٔ cost[nodeId][landmarkId]
• حافظه: به ازای هر گره و هر لندمارک یه عدد ذخیره می‌شه
• تو گراف جهت‌دار باید یال‌ها رو برعکس کنی؛ تو گراف بدون جهت قدرمطلق اختلاف کافیه
• تو مقالات آکادمیک با اسم‌های differential heuristic، pivot و landmark دیده می‌شه