Below is my semantic annotation of the MicroPather library written by leethomason in C++. I hope this will help everyone understand the techniques used.
https://github.com/leethomason/MicroPather
MicroPather решает задачи по поиску путей, в том числе A* (astar или a-star), написан независимо от платформы C++, который может быть легко интегрирован в существующий код. MicroPather фокусируется на том, чтобы быть механизмом поиска путей для видеоигр, но является универсальным решателем A *. MicroPather имеет открытый исходный код с лицензией, подходящей для использования с открытым исходным кодом или в коммерческих целях.
Целями MicroPather являются:
• Простая интеграция в игры и другое программное обеспечение.
• Простой в использовании и понятный интерфейс.
• Быстродействие
В видеоиграх проблема поиска пути возникает во многих современных играх. Каково кратчайшее расстояние от точки А до точки В? Люди хорошо справляются с этой проблемой. Вы естественным образом находите путь почти каждый раз, когда двигаетесь, но его сложно выразить в виде компьютерного алгоритма. A * - это метод "рабочей лошадки" для решения путевых задач. Он оптимизирован для быстрого поиска решения, а не с помощью грубой силы, но он никогда не подведет, если решение есть.
A * гораздо более универсален, чем просто поиск пути. A * и MicroPather можно было бы использовать для поиска решения задач общего состояния, например, их можно было бы использовать для решения головоломки с кубиком рубика.
Вкратце, эти шаги таковы: 1. Включите файлы MicroPather 2. Реализуйте графический интерфейс 3. Вызовите решателя 4. Включите файлы программы Есть только 2 файла для micropather: micropather.cpp и micropather.h. Таким образом, нет ни сборки, ни make, просто добавьте эти 2 файла в свой проект. Они являются стандартными для C++ и не требуют исключений или RTTI. Предполагая, что вы создаете отладочную версию своего проекта с помощью _DEBUG или DEBUG (а это делают все), MicroPather выполнит дополнительную проверку в этих режимах. Пример использования: GitHub - leethomason/MicroPather: MicroPather is a path finder and A* solver (astar or a-star) written in platform independent C++ that can be easily integrated into existing code. MicroPather focuses on being a path finding engine for video games but is a generic A* solver.
Micropather.h
|
№ |
Идиома |
Строки кода |
Комментарии |
|
1 |
39,42,45,51,59,62,62,68 |
DEBUG не путать с _DEBUG |
|
|
2 |
Защита заголовка |
26,27,508 |
- |
|
3 |
44,47,61,64,73,76,77 |
- |
|
|
4 |
Управление ходом программы на этапе компиляции |
41-46,49-53,56-69,72-82,86-130,246-255,493-495 |
- |
|
5 |
Директивы препроцессора |
59,60,61,62,72(5-15),75(5-15) |
- |
|
6 |
Системные макросы |
62(120-135) |
- |
|
7 |
84 |
- |
|
|
8 |
74,78,81 |
- |
|
|
9 |
12,22,29,30,115,258-261 |
- |
|
|
10 |
13,20,21,27 |
- |
|
|
11 |
32,367 |
- |
|
|
12 |
19 |
- |
|
|
13 |
24,34 |
- |
|
|
14 |
23 |
- |
|
|
15 |
26(5-14),99,102(45-54),105(50-60),118,119,213,214,249,251,252 |
- |
|
|
16 |
32 |
Проверка ввода |
|
|
17 |
30 |
Проверка ввода |
|
|
18 |
92,93 |
- |
|
|
19 |
95,274,375,399,451,486 |
- |
|
|
20 |
96,162,275,376,452 |
- |
|
|
21 |
95(8-15),121 |
- |
|
|
21 |
98,99 |
- |
|
|
22 |
98,99-101 |
- |
|
|
23 |
103,106,111(30-40),320(20-30),321(20-30),356,357,371,383(30-40),384(30-40) |
- |
|
|
24 |
109,367(40-45) |
- |
|
|
25 |
102,105,266,487 |
- |
|
|
26 |
94,113,264,273,312,350,389,417,485 |
- |
|
|
27 |
81(6-15),111,114(20-30),116,126,127,205(35-44),223,274(30-40,41-48),292,310,319,320,321,322(10-18),335,336,337,339,340,364,365,451(30-41,41-50),503 |
- |
|
|
28 |
117(28-42) |
- |
|
|
29 |
120 |
- |
|
|
30 |
120(30-50),367(30-45) |
- |
|
|
31 |
138-142,191-195,314-317,351-373,398-406 |
- |
|
|
32 |
141,207,208,219,220,221,223,294,295,361,381(40-50),402,406,463(60-70),474(40-51),500(10-15) |
- |
|
|
33 |
93,159-186,189,202-267,271-341,348-396,413-508 |
- |
|
|
34 |
98,99-101,108,111,114,170,178,185,205,211,212-216,235-239,240-245,247-254,257-262,278,292-296,299,302,306,310,323,324,363-373,378,379,380,383,384,463,474,479,482,483,489,491 |
- |
|
|
35 |
162,170,178,185 |
- |
|
|
36 |
Чистые виртуальные функции |
170,178,185 |
- |
|
37 |
214(15-20,24-29),258(30-36,40-46),261(0-26) |
- |
|
|
38 |
193,222,229,230,497,498,499,500,502,504 |
- |
|
|
39 |
226,227,302(27-31,32-38),306(20-26,26-31),331,332,380(40-51),381,386,387,394,395,400,401,404,405,463 |
- |
|
|
40 |
222,223,356,357,451(50-61) |
- |
|
|
41 |
215,241 |
- |
|
|
42 |
1-23,30-38,146-157,409-412,420-450 |
Комментарии для понимания библеотеки и ее возможных адаптаций |
|
|
43 |
302(20-26),356(19-30),364,379(20-30,30-40),390,391 |
- |
|
|
44 |
Константные функции |
320,321,356,357,363,383,384 |
- |
|
45 |
320(20-24),321(21-25) |
- |
|
|
46 |
368,369 |
- |
|
|
47 |
Дружественный класс |
415 |
- |
|
48 |
418-426 |
Состояния решения |
|
|
49 |
365 |
Создание Hash |
|
№ |
Идиома |
Строки кода |
Комментарии |
|
1 |
31,32,40 |
- |
|
|
2 |
Управление ходом программы на этапе компиляции |
26-29,39-41,55-57,83-87,113-115,121-125,132-136,185-189,206-210,241-243,572-575,578-587,559-591,597-656,660-679,797-799,861-867,877-879,882-884,961-963,1065-1071 |
- |
|
3 |
Директивы препроцессора |
206(2-10),223(2-10) |
- |
|
4 |
Системные макросы |
653(38-39,41-46),757(19-24),767(20-25),1025(20-25) |
- |
|
5 |
45 |
- |
|
|
6 |
95-99,142-145,148-160,395-411,527-549,551-570,732-734,837-849,871,874-885,937-958 |
- |
|
|
7 |
93-101,152-153,397-406,435-442,519-523,543-548,793-801,902-960,1012-1052 |
- |
|
|
8 |
314-316,556-565,629-633,650-655,691-698,736-746,1056-1064,1066-1069 |
- |
|
|
9 |
98,438,441,800 |
- |
|
|
10 |
- |
||
|
11 |
80,81,91,102,117,118,138,791,803,1025,1030,1068 |
- |
|
|
12 |
50-58,68,203-205,480-491,892-896 |
- |
|
|
13 |
59,,494-497 |
- |
|
|
14 |
261,269,393,510,595,789,833 |
- |
|
|
15 |
65,127,317,389,500,733,782,785,968,1073 |
- |
|
|
16 |
386,388,761,781,784,807,887,1066,1067 |
- |
|
|
17 |
69 |
- |
|
|
18 |
49,67,165,196 |
- |
|
|
19 |
321,416,556,560,625,818,1066,1067 |
- |
|
|
20 |
227(10-90),704 |
- |
|
|
21 |
72,310(36-54,55-61) |
- |
|
|
22 |
840(30-35),845(28-32),1026 |
- |
|
|
23 |
47-74,,163-200, |
- |
|
|
24 |
61,62,63,65,77-106,130-160,169-181,247-258,261-266,269-305,308-318,373-390,393-411,414-427,456-470,473-478,500-507,510-599,682-686,689-699,702-710,730-747,750-760,763-786,781-811,814-830,833-851,855-969,972-1053 |
- |
|
|
25 |
91(20-27) |
- |
|
|
26 |
817,889,890 |
- |
|
|
27 |
855 |
- |
|
|
28 |
65,247 |
- |
|
|
29 |
166(30-35),475(5-10) |
- |
|
|
30 |
220-221,323-369,661-678,974-995 |
Комментарии для понимания библеотеки и ее возможных адаптаций |
|
|
31 |
68(10-15),69(12-17),197(15-21),198(16-22),625,626 |
- |
|
|
32 |
Константные методы |
814 |
- |
|
33 |
254(15-17),279(14-16),313(9-11),778(12-14) |
- |
|
|
34 |
Изменение поведения предупреждающих сообщений компилятора |
27,28 |
Отключения обработчика исключений |
|
35 |
54(30-40),56(35-45),96,112,114,123,134,143,144,150,173,229,237,447,448,449,450,513,558,644,646,684,685,758,820,823,859,943,953,956,1047,1050,1054 |
- |
|
|
36 |
65(38-45),85(42-47),86(45-50),91(10-14),92(15-21),95(20-25,26-31),97(10-15),100(10-15),102(7-11),111(20-30),117(11-17),118(11-17),119(7-11),123(10-14),124(11-15),134(30-40),135(40-50),138(15-25),142(15-20,25-30,35-40,40-46),144(20-25),148(20-25,26-30,30-35),149(10-15),153(10-14),685,696,772,773,950,951,952,1057(40-45),1059(25-32),1060(27-34) |
- |
|
|
37 |
Динамическое форматирование |
86(14-21),135(29-41) |
Выводит двоичное число с точностью до 0.1 |
|
38 |
238-240,715 |
|
|
|
39 |
memset |
297,705 |
(http://cppstudio.com/post/673/) |
|
40 |
93,255,397,793,819 |
- |
|
|
41 |
Явное приведение типа |
732(25-29)\,840(40-45,52-57),845(40-45,52-57) |
- |
|
42 |
GLOUTPUT |
798,878,883 |
?как то связано с OpenGl? |
|
43 |
|
926,1019,1035 |
- |
|
44 |
398(40-41),423(35-36,878(54-55),931(39-40),932(41-42),1028(40-41),1029(42-43),1031(35-36) |
- |