تكتب عنوانين في تطبيق خرائط فيظهر المسار قبل أن ترفع إصبعك. خلف ذلك سلسلة من المسائل، وكل واحدة منها مسألة كلاسيكية: قراءة ملف خرائط ثنائي مضغوط، وتحويل الشوارع إلى بيان (graph)، وإيجاد أقصر مسار بين مئات الآلاف من الطرق بسرعة لا يبلغها بحث عادي.
كنت قد قرأت عن كل هذا ولم أنفّذ شيئًا منه. routing-from-scratch هو المشروع الذي نفّذته فيه: حساب مسارات السيارات (routing) على بيانات OpenStreetMap حقيقية، مكتوب من الصفر بلغة Go دون أي اعتماديات غير المكتبة القياسية. هو مشروع تعليمي، ويقول ذلك عن نفسه: لأي استعمال حقيقي، استعمل OSRM أو Valhalla أو GraphHopper.
ماذا يقدّم
المشروع أربعة أجزاء:
- قارئ وكاتب لصيغة OSM PBF مع codec مكتوب يدويًّا لصيغة protobuf، إضافة إلى قارئ OSM XML.
- بيان الطرق: مصفوفات CSR، وقواعد الاتجاه الواحد (oneway)، وسرعات حسب نوع الطريق، والاقتصار على أكبر مركّبة قوية الترابط (strongly connected component).
- Dijkstra ثم A* ثم contraction hierarchies، وكلها مُتحقَّق منها مقابل بعضها ومقابل Floyd–Warshall.
- جدول قياس أداء (benchmark) ونقطة وصول HTTP صغيرة مع صفحة خريطة.
في صفحة الخريطة تنقر مرتين لتحديد A و B، ويمكن سحب العلامتين. الصفحة تطلب المسار بالخوارزميات الثلاث وتعرض زمن الرحلة (وهو متطابق دائمًا)، وعدد العقد المثبَّتة (settled nodes)، وزمن الاستعلام.
والـ API مسار واحد: GET /route?from=lon,lat&to=lon,lat&algo=dijkstra|astar|ch يُرجع Feature بصيغة GeoJSON (من نوع LineString) مع duration_s و distance_m و settled و query_us و snap_m، وهذا الأخير هو بُعد كل نقطة عن العقدة التي أُلصقت بها. و GET /info يُرجع حجم البيان وحدوده.
طريقة الاستعمال
ثبّت الملفات التنفيذية route-server و route-bench و osm2pbf بواسطة Go:
go install github.com/AbdeldjalilChougui/routing-from-scratch/cmd/...@latest أو انسخ المستودع، وفيه عيّنة صغيرة لوسط تلمسان، وشغّل من هناك:
git clone https://github.com/AbdeldjalilChougui/routing-from-scratch.git cd routing-from-scratch go test ./... # ~30 s, includes brute-force cross-checks go run ./cmd/route-server # committed Tlemcen fixture, http://127.0.0.1:8090/ go run ./cmd/route-bench testdata/tlemcen-centre.osm.pbf # benchmark table لمنطقة أكبر (غير مرفقة بالمستودع)، نزّل الطرق بواسطة Overpass وحوّلها بكاتب PBF الخاص بالمشروع:
scripts/fetch-osm.sh 35.60 -0.80 35.80 -0.45 data/oran.osm # ~11 MB XML go run ./cmd/osm2pbf data/oran.osm data/oran.osm.pbf # ~0.9 MB PBF go run ./cmd/route-server data/oran.osm.pbf ما بنيته من الصفر
الـ codec الخاص بـ PBF (internal/pbf). ملف PBF سلسلة من [4-byte length][BlobHeader][Blob]. الـ Blobs رسائل protobuf من نوع PrimitiveBlock مضغوطة بـ zlib، في كل واحدة جدول نصوص (string table) و granularity وإزاحات، ومجموعات من DenseNodes (معرّفات وإحداثيات مرمّزة بـ delta و zigzag) أو من Way (وسوم من جدول النصوص ومراجع مرمّزة بـ delta). المفكّك يقرأ حقول protobuf الخام (varints، و length-delimited، و packed) دون كود مولَّد. والكاتب يفعل العكس، ويستعمله cmd/osm2pbf واختبارات الذهاب والعودة. والخصائص غير المدعومة في required_features مثل HistoricalInformation تُرفض، كما تفرض المواصفة.
البيان (internal/graph). كل عقدة في طريق صالح للسيارات تصبح رأسًا، وكل زوج متتالٍ يصبح ضلعًا. الوزن هو زمن الرحلة بأعشار الثانية، مقرَّبًا إلى الأعلى. السرعة تأتي من maxspeed (بـ km/h أو mph) أو من قيمة افتراضية حسب نوع الطريق. والاتجاه يأتي من oneway=yes/-1/no ومن الدوّارات والطرق السريعة. وقواعد الوصول تُسقط access=no/private وممرات المواقف والمداخل الخاصة. والأضلاع المتوازية يُحتفظ منها بالوزن الأصغر. وفي النهاية يُقتصر البيان على أكبر مركّبة قوية الترابط (بخوارزمية Kosaraju التكرارية)، حتى تستطيع كل نقطة ملصقة الوصول إلى كل نقطة أخرى. التخزين بصيغة CSR (FirstOut و Head و W) مع CSR معكوس.
Dijkstra و A* (internal/route/dijkstra.go). كومة ثنائية (binary heap) مع حذف مؤجَّل. المخازن المؤقتة يُعاد استعمالها بين الاستعلامات، ولا يُصفَّر إلا ما لُمس منها. A* يضيف haversine(v, t) / MaxSpeed. و MaxSpeed تُحسب من الأضلاع نفسها (أكبر مسافة مستقيمة بالأمتار مقسومة على الوزن)، فتبقى الدالة التقديرية (heuristic) مقبولة ومتسقة مهما كانت البيانات.
Contraction hierarchies (internal/route/ch.go):
- الترتيب. الأولوية هي فرق الأضلاع (الاختصارات اللازمة ناقص الأضلاع المحذوفة) مضافًا إليه عدد الجيران المُقلَّصين سابقًا. التحديث مؤجَّل: تُسحب العقدة الدنيا، يُعاد حساب أولويتها، ولا تُقلَّص إلا إذا بقيت هي الدنيا.
- التقليص (contraction). لكل جار داخل
uللعقدةv، يُشغَّل Dijkstra شاهد محدود (يتجنبv، وبحدّ أقصى 200 عقدة مثبَّتة) يفحص كل جار خارجx. إذا لم يوجد مسار بتكلفة لا تتجاوزw(u,v)+w(v,x)، يُضاف الاختصارu→xوتُسجَّلvكعقدته الوسطى. - الاستعلام. Dijkstra ثنائي الاتجاه على البيانين الصاعدين. يتوقف عندما يصبح أدنى ما في الطابورين أكبر من أو يساوي أفضل تكلفة التقاء، ثم تُفكّ الاختصارات تعاوديًّا عبر عقدها الوسطى.
ما تعلّمته
A* ليس أسرع تلقائيًّا. كانت هذه هي المفاجأة. الأمر go run ./cmd/route-bench -n 1000 <file> يشغّل 1000 استعلام عشوائي لكل خوارزمية ويتحقق من أن الثلاث تُرجع التكاليف نفسها (0 اختلاف في كل تشغيل). على منطقة وهران (91,547 عقدة و 188,329 ضلعًا؛ المعالجة المسبقة لـ CH استغرقت 10.1 ثانية وأنتجت 212,760 اختصارًا):
| algorithm | avg query | avg settled nodes | speed-up vs Dijkstra |
|---|---|---|---|
| Dijkstra | 46.8 ms | 45,972 | 1.0x |
| A* | 73.3 ms | 25,324 | 0.6x |
| CH | 0.40 ms | 142 | 116x |
وعلى منطقة تلمسان (30,047 عقدة و 60,815 ضلعًا؛ المعالجة المسبقة لـ CH 4.5 ثانية)، كان المتوسط 18.6 ms لـ Dijkstra و 24.6 ms لـ A* و 0.12 ms لـ CH، بعدد عقد مثبَّتة 15,339 و 9,205 و 79.
A* يثبّت عقدًا أقل بنحو 40% لكنه أبطأ هنا. دالته التقديرية، أي المسافة المستقيمة مقسومة على أعلى سرعة في البيان، ضعيفة عندما تكون أغلب الشوارع بسرعة 25 km/h وقليل من الطرق يسمح بـ 80 إلى 100 km/h، وكل تقييم لها يكلّف حساب Haversine. أما CH فيثبّت عقدًا أقل بمرتبتين عشريتين مقابل بضع ثوانٍ من المعالجة المسبقة.
وتحفّظ يرافق هذه الأرقام: قيست على حاسوب محمول كان مشغولًا بعمليات بناء أخرى، فالأزمنة المطلقة فيها تشويش. عدد العقد المثبَّتة هو المؤشر المستقر.
الأوزان الصحيحة تجعل المقارنة دقيقة. عندما يكون زمن الرحلة أعدادًا صحيحة بأعشار الثانية، فإما أن تتفق الخوارزميات الثلاث حتى الوحدة، وإما أن فيها خطأ. مع الأعداد العشرية كنت سأجادل أخطاء التقريب.
حدّ بحث الشاهد يؤثر في السرعة لا في الصحة. بلوغ حدّ الـ 200 عقدة يضيف اختصارات غير ضرورية فقط. ويوجد اختبار بحدّ قيمته 1 يتحقق من أن الصحة لا تعتمد عليه أبدًا.
القوة الغاشمة تُبقيك صادقًا. على 10 بيانات عشوائية شبيهة بالطرق (من 30 إلى 120 عقدة، بعضها باتجاه واحد، وبعض الأزواج غير متصلة)، تُقارن كل الأزواج في Dijkstra و A* و CH مع Floyd–Warshall. وتُفحص صحة المسار أيضًا: تسلسل العقد المُرجَع مكوّن من أضلاع حقيقية ومجموعه يساوي التكلفة. واختبارات أخرى تغطي شبكة 30×30، والكومة، وكتابة PBF ثم قراءته، وقواعد وسوم OSM على ملف XML مكتوب يدويًّا، وفهرس الشبكة مقابل أقرب عقدة بالقوة الغاشمة، ورموز الخطأ في /route (400/404/422).
أشياء يجب معرفتها
- ملف تعريف السيارة فقط. لا توجد قيود انعطاف، ولا تكاليف انعطاف، ولا إشارات مرور، ولا
maxspeed:forward/backward. - الإلصاق (snapping) يتم إلى أقرب عقدة، لا إلى أقرب نقطة على ضلع.
- المعالجة المسبقة لـ CH تعمل بخيط واحد وغير محسَّنة. تستغرق ثوانيَ لمدينة، وتحتاج عملًا إضافيًّا لبلد كامل.
- قارئ PBF يعالج العقد والطرق (dense و plain). العلاقات (relations) تُتجاهل، والمدعوم هو blobs من نوع zlib/raw فقط (لا lzma ولا zstd).
- صفحة الخريطة تحمّل MapLibre من unpkg والبلاطات النقطية من tile.openstreetmap.org.
لماذا بنيته
محركات حساب المسارات سهلة الاستعمال وصعبة الرؤية من الداخل. الأفكار التي تقوم عليها، أي أقصر المسارات والدوال التقديرية والمعالجة المسبقة، مادة معروفة، لكن القراءة عن contraction hierarchies شيء، وجعلها تُرجع جواب Dijkstra نفسه على مدينة حقيقية شيء آخر. الانطلاق من بايتات PBF الخام، دون مكتبة في الطريق، يعني أن كل طبقة كانت لي لأخطئ فيها ثم أصلحها. وهذا كان المقصود.
احصل على الكود
الكود المصدري وعيّنة تلمسان والاختبارات على GitHub: https://github.com/AbdeldjalilChougui/routing-from-scratch. الكود برخصة MIT. الملف testdata/tlemcen-centre.osm.pbf يحتوي بيانات OpenStreetMap، © مساهمو OpenStreetMap، برخصة Open Database License (ODbL) 1.0؛ وكل ما تنتجه منه يجب أن يحتفظ بهذه النسبة وهذه الرخصة.
نُشر في الأصل على abdeldjalilchougui.biz.
![Physical AI Engineering — Ch.13: Computing Platforms for Physical AI [EN]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fg3ou3b2eumf1epqj4bk4.png)

![Physical AI Engineering — Ch.04: Localization Mapping and World Understanding [EN]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fuscy0mautxl2mb4834vd.png)