Актуальность

Ниже представлено мое семантическое аннотирование библиотеки MicroPather написаной leethomason на С++. Я надеюсь это поможет разобраться в используемых приемах всем желающим.
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

1.Описание библеотеки

MicroPather решает задачи по поиску путей, в том числе A* (astar или a-star), написан независимо от платформы C++, который может быть легко интегрирован в существующий код. MicroPather фокусируется на том, чтобы быть механизмом поиска путей для видеоигр, но является универсальным решателем A *. MicroPather имеет открытый исходный код с лицензией, подходящей для использования с открытым исходным кодом или в коммерческих целях.

Целями MicroPather являются:

 • Простая интеграция в игры и другое программное обеспечение.

 • Простой в использовании и понятный интерфейс.

 • Быстродействие

2. Описание темы

В видеоиграх проблема поиска пути возникает во многих современных играх. Каково кратчайшее расстояние от точки А до точки В? Люди хорошо справляются с этой проблемой. Вы естественным образом находите путь почти каждый раз, когда двигаетесь, но его сложно выразить в виде компьютерного алгоритма. A * - это метод "рабочей лошадки" для решения путевых задач. Он оптимизирован для быстрого поиска решения, а не с помощью грубой силы, но он никогда не подведет, если решение есть.

A * гораздо более универсален, чем просто поиск пути. A * и MicroPather можно было бы использовать для поиска решения задач общего состояния, например, их можно было бы использовать для решения головоломки с кубиком рубика.

3. Описание процесса установки библиотеки

Вкратце, эти шаги таковы: 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.

4.Таблица семантического аннотирования

Micropather.h

№	Идиома	Строки кода	Комментарии
1	compile time constant	39,42,45,51,59,62,62,68	DEBUG не путать с _DEBUG
2	Защита заголовка	26,27,508	-
3	implicit prologue	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	declare namespace	84	-
8	typedef	74,78,81	-
9	if	12,22,29,30,115,258-261	-
10	while	13,20,21,27	-
11	for	32,367	-
12	switch	19	-
13	break	24,34	-
14	write formatted string to stdout	23	-
15	call	26(5-14),99,102(45-54),105(50-60),118,119,213,214,249,251,252	-
16	string to number	32	Проверка ввода
17	number to string	30	Проверка ввода
18	define generic type	92,93	-
19	constructor	95,274,375,399,451,486	-
20	destructor	96,162,275,376,452	-
21	destroy object	95(8-15),121	-
21	no return value	98,99	-
22	define	98,99-101	-
23	return value	103,106,111(30-40),320(20-30),321(20-30),356,357,371,383(30-40),384(30-40)	-
24	increment and decrement	109,367(40-45)	-
25	overload operator	102,105,266,487	-
26	access control	94,113,264,273,312,350,389,417,485	-
27	unsigned type	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	allocate heap	117(28-42)	-
29	copy	120	-
30	type size	120(30-50),367(30-45)	-
31	struct definition	138-142,191-195,314-317,351-373,398-406	-
32	float type	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	define class	93,159-186,189,202-267,271-341,348-396,413-508	-
34	define method	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	dynamic dispatch	162,170,178,185	-
36	Чистые виртуальные функции	170,178,185	-
37	float limits	214(15-20,24-29),258(30-36,40-46),261(0-26)	-
38	create object	193,222,229,230,497,498,499,500,502,504	-
39	integer type	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	boolean type	222,223,356,357,451(50-61)	-
41	name of receiver	215,241	-
42	multiple line comment	1-23,30-38,146-157,409-412,420-450	Комментарии для понимания библеотеки и ее возможных адаптаций
43	write-once variable	302(20-26),356(19-30),364,379(20-30,30-40),390,391	-
44	Константные функции	320,321,356,357,363,383,384	-
45	bit operators	320(20-24),321(21-25)	-
46	compound assignment	368,369	-
47	Дружественный класс	415	-
48	enum	418-426	Состояния решения
49	binary, octal, and hex literals	365	Создание Hash

Micropather.cpp

№	Идиома	Строки кода	Комментарии
1	implicit prologue	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	declare namespace	45	-
6	if	95-99,142-145,148-160,395-411,527-549,551-570,732-734,837-849,871,874-885,937-958	-
7	while	93-101,152-153,397-406,435-442,519-523,543-548,793-801,902-960,1012-1052	-
8	for	314-316,556-565,629-633,650-655,691-698,736-746,1056-1064,1066-1069	-
9	break	98,438,441,800	-
10	write formatted string to stdout	84,86,122,124,133,135,188,242,573,580,590,862,865,866	-
11	call	80,81,91,102,117,118,138,791,803,1025,1030,1068	-
12	constructor	50-58,68,203-205,480-491,892-896	-
13	destructor	59,,494-497	-
14	no return value	261,269,393,510,595,789,833	-
15	return value	65,127,317,389,500,733,782,785,968,1073	-
16	increment and decrement	386,388,761,781,784,807,887,1066,1067	-
17	overload operator	69	-
18	access control	49,67,165,196	-
19	unsigned type	321,416,556,560,625,818,1066,1067	-
20	allocate heap	227(10-90),704	-
21	type size	72,310(36-54,55-61)	-
22	float type	840(30-35),845(28-32),1026	-
23	define class	47-74,,163-200,	-
24	define method	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	float limits	91(20-27)	-
26	create object	817,889,890	-
27	integer type	855	-
28	boolean type	65,247	-
29	name of receiver	166(30-35),475(5-10)	-
30	multiple line comment	220-221,323-369,661-678,974-995	Комментарии для понимания библеотеки и ее возможных адаптаций
31	write-once variable	68(10-15),69(12-17),197(15-21),198(16-22),625,626	-
32	Константные методы	814	-
33	compound assignment	254(15-17),279(14-16),313(9-11),778(12-14)	-
34	Изменение поведения предупреждающих сообщений компилятора	27,28	Отключения обработчика исключений и Усечение дебагером имен (Необходимо для корректной работы STL и MVC)
35	invoke method	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	struct member access	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	free heap	238-240,715
39	memset	297,705	(http://cppstudio.com/post/673/) Функции Clear() и Reset() вызываются часто поэтому используется memset для оптимизации
40	true and false	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	continue	926,1019,1035	-
44	coalesce	398(40-41),423(35-36,878(54-55),931(39-40),932(41-42),1028(40-41),1029(42-43),1031(35-36)	-