СБОРНИК
НАУЧНЫХ ТРУДОВ НГТУ

ISSN: 2307-6879
English | Русский

Последний выпуск
№2(92) Апрель - Июнь 2018

Алгоритм поиска пути из пункта А в пункт Б

Выпуск № 2 (88) Апрель - Июнь 2017
Авторы:

Е.П. Миков,
В.А. Бондарь
DOI: http://dx.doi.org/10.17212/2307-6879-2017-2-33-40
Аннотация

Поиск пути из точки А в точку Б – одна из самых распространенных задач при разработке игр. Для решения этой задачи есть множество алгоритмов, но программа, разработанная нами,  является уникальным вариантом реализации метода поиска пути. Многие программисты и разработчики игр не владеют информацией на предмет того, какой алгоритм поиска пути из двух отдаленных точек наиболее эффективен. Чтобы реализовать задуманный проект, возникает необходимость ознакомления с множеством алгоритмов, из которых далеко не каждый удобен в пользовании. В ходе написания нашей программы были испробованы многие методы и в итоге определены самые совершенные и, как оказалось, наиболее популярные алгоритмы поиска, именуемые A* (A star). Цель работы – создание драйвера-программы для роботов, основанных на схемах Arduin, для нахождения кратчайшего пути из точки А в точку Б. Следует отметить, что у схем Arduin есть такой недостаток, как отсутствие многопоточности. В связи с этим в ходе реализации проекта появилась еще одна цель – это оптимизация алгоритма для одного потока процесса. Следовательно, нашей конечной целью можно назвать способ написания однопоточного алгоритма.


Ключевые слова: алгоритмизация, поиск пути, С#, программа, однопоточность, оптимизация, Arduin, разработка игр

Список литературы

1. Рихтер Д. CLR via C#: программирование на платформе Microsoft .NET Framework 4.5 на языке C#. – 4-е изд. – Спб.: Питер, 2017. – 896 с.



2. Дейтел П., Дейтел Х. Как программировать на Visual C# 2012: включая работу в Windows 7 и Windows 8. – 5-е изд. – СПб.: Питер, 2014. – 585 с.



3. Мак-Дональд М. WPF: Windows Presentation Foundation в .NET 4.5 с примерами на C# 5.0: для профессионалов. – 4-е изд. – М.: Вильямс, 2012. – 1024 с.



4. Павловская Т.А. C#: программирование на языке высокого уровня. – СПб.: Питер, 2009. – 432 с.



5. Евстигнеев В.А. Итеративные алгоритмы глобального анализа графов. Пути и покрытия // Применение теории графов в программировании / под ред. А.П. Ершова. – М.: Наука, 1985. – Гл. 3. – С. 138–150.



6. Таланов В.А. Нахождения кратчайших путей в графе // Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных. – Н. Новгород: Изд-во Нижегор. гос. ун-та, 2005. – Гл. 3.4. – С. 236–237. – ISBN 5–85747–810–8.



7. Галкина В.А. Построение кратчайших путей в ориентированном графе // Галкина В.А. Дискретная математика. Комбинаторная оптимизация на графах. – М.: Гелиос АРВ, 2003. – Гл. 4. – С. 75–94. – ISBN 5–85438–069–2.



8. Берж К. Задача о кратчайшем пути // Берж К. Теория графов и ее применения / под ред. И.А. Вайнштейна. – М.: Издательство иностранной литературы, 1962. – Гл. 7. – С. 75–81.

Просмотров: 664