Created
July 9, 2018 02:07
-
-
Save dmitry-bystrov/1927504345da7bc6fcfa6f2a1cbe9b25 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//Одним из самых интересных моментов в процессе разработки игры была реализация искуственного интеллекта для ботов. | |
//Чтобы они не просто двигались по карте случайным образом, а пытались окружить и поймать героя. Я решил | |
//реализовать волновой алгоритм поиска кратчайшего пути. Суть этого алгоритма заключается в том, что мы | |
//начинаем обход всей карты от исходной точки и на каждом шаге присваем клетке, на которую перешли, значение соответственно | |
//номеру шага. Таким образом у нас получается множество возможных маршрутов движения, один из которых в конце концов | |
//приводит нас к цели. И тогда остается только пройти от цели к источнику по номерам шагов в обратном порядке и передать | |
//уже готовый маршрут боту. | |
private void fillRouteMap(int routeMap[][]) { | |
int x; | |
int y; | |
for (int step = 1; step < MAX_ROUTE_STEP_COUNT; step++) { | |
for (int i = 0; i < routeMap.length; i++) { | |
for (int j = 0; j < routeMap[i].length; j++) { | |
if (routeMap[i][j] != step - 1) continue; | |
for (Direction direction : Direction.values()) { | |
x = i + direction.getX(); | |
y = j + direction.getY(); | |
if (x < 0 || y < 0 || x >= routeMap.length || y >= routeMap[x].length) continue; | |
if (routeMap[x][y] == ROUTE_TARGET_CELL) { | |
fillRouteList(x, y, routeMap, step); | |
return; | |
} | |
if (routeMap[x][y] == ROUTE_EMPTY_CELL) { | |
if (gameManager.isCellEmpty(x, y)) { | |
routeMap[x][y] = step; | |
} else { | |
routeMap[x][y] = ROUTE_WALL_CELL; | |
} | |
} | |
} | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
На скриншоте с примером работы волнового алгоритма видно как заполняется маршрутная карта и строится уже готовый маршрут, который передаётся ботам: