В последние несколько недель мы много внимания уделяли ИИ игроков в нашей игре. Мы использовали еще несколько продвинутых трюков, чтобы помочь нашему игроку ориентироваться в лабиринте с помощью упражнений. Но это происходит за счет производительности. Игра теперь может стать немного прерывистой, когда много врагов или когда наш игрок находится далеко от цели. Кроме того, выполнение итераций анализа занимает больше времени, чем хотелось бы.
На этой неделе мы улучшим производительность нашего ИИ, кэшируя определенный путь. Многие наши вычисления для измерения кратчайшего пути повторяются. Мы можем отслеживать их и вообще избегать всего алгоритма BFS во многих случаях!
На этой неделе вы должны взглянуть на ветку search-caching в нашем репозитории Github для полного кода, который мы здесь реализуем. Мы сосредоточимся на изменениях в файле MazeUtils.hs.
Мы также собираемся сделать небольшое профилирование для этой статьи. Профилирование кода — это важный навык, который необходимо изучить, если вы когда-нибудь захотите использовать Haskell в производственной среде. Чтобы узнать о некоторых других полезных навыках, ознакомьтесь с нашим Контрольным списком производства!
Профилирование нашего кода
Как упоминалось выше, у нас есть довольно хорошее представление о том, где находится узкое место производительности для нашего кода. Но всегда стоит быть уверенным. Итак, чтобы перепроверить, мы собираемся запустить наш код в режиме профилирования. Здесь мы рассмотрим некоторые основы, но вам также следует ознакомиться с этой статьей, которую мы написали о профилировании некоторое время назад.
Мы получим отчет для нашего кода, который скажет нам, какие функции занимают больше всего времени. Это подскажет нам, где мы можем сделать наиболее эффективные улучшения. Это также даст нам конкретный способ доказать наше улучшение позже.
Для начала нам нужно пересобрать наш код с помощью stack build --profile. Имейте в виду, что это может занять некоторое время, так как все библиотеки также должны быть пересобраны. Затем мы можем повторно запустить программу анализа, которую мы использовали на прошлой неделе:
stack exec -- analyze-game maze_save_2 --enemies +RTS -pВот сокращенный вывод в файле `analyze-game.EXE.prof:
total time = 32.62 secsCOST CENTRE %time drillBFS.newParentsMap.\ 21.9 drillBFS.unvisitedNextItems.\ 21.7 drillBFS.newVisitedSet 19.4 getDrillAdjacentItems 6.2 drillBFS 4.5 drillBFS.newSearchQueue 4.0 getDrillAdjacentItems.mkItemFromResult 3.0 bfs.newParentsMap.\ 2.1 bfs.newVisitedSet 2.0 getDrillAdjacentItems.mkItemFromResult.(...) 1.7 drillBFS.unvisitedNextItems 1.4 bfs.unvisitedNextCells.\ 1.1 drillBFS.newParentsMap 1.0 getDrillAdjacentItems.bounds 1.0 bfs 0.6 getAdjacentLocations 0.5
Неудивительно, что мы видим, что drillBFS и его помощники являются главными виновниками. На них приходится семь лучших записей в списке и колоссальные 82% времени, которое мы тратим. Расчеты искусственного интеллекта противника происходят с задержкой примерно в 6,3% случаев. Итак, давайте сосредоточимся на исправлении алгоритма плеера.
Базовый кеш игрока
Пытаясь улучшить ИИ игроков, мы можем сделать одно важное наблюдение. Возможно, некоторые из вас уже заметили это, когда читали об этом ИИ. По большей части наш игрок все время следует по одному пути. Мы вычисляем полный путь от начала до конца для каждого цикла перемещения игрока, но затем отбрасываем большую его часть. Единственный раз, когда нас «сдувает» с этого пути, это когда нам нужно убегать от врагов.
Есть всего несколько обстоятельств, когда мы меняем этот путь! Итак, давайте создадим тип PlayerMemory, который будет отслеживать это. Это должно сэкономить нам массу времени!
newtype PlayerMemory = PlayerMemory (Maybe [Location])data Player = Player { … , playerMemory :: PlayerMemory }
Мы добавим эту память к нашему типу игрока. Когда мы инициализируем его из экземпляров JSON, он должен начинаться пустым. Нет необходимости отслеживать это в файле сохранения игры.
Это изменение немного усложнит наш API перемещения. Теперь он выдаст PlayerMemory в качестве вывода:
makePlayerMove :: World -> (PlayerMove, PlayerMemory)Использование нашей памяти
Когда дело доходит до перемещения, нам сначала нужно поместить путь в память. Для начала сделаем PlayerMemory из пути, полученного из BFS.
makePlayerMove :: World -> (PlayerMove, PlayerMemory)
makePlayerMove w =
( PlayerMove finalMoveDirection useStun drillDirection
, ...
)
where
shortestPath = getShortestPathWithDrills …
memoryFromMove = PlayerMemory (Just shortestPath)
...В общем, мы хотим вернуть эту «память». Но есть одно обстоятельство, при котором мы хотим аннулировать его. Когда нам придется отступить от наших врагов, мы отклонимся от этого идеального пути. В этом случае мы вернем Nothing. Вот как выглядит эта логика:
makePlayerMove :: World -> (PlayerMove, PlayerMemory)
makePlayerMove w =
( PlayerMove finalMoveDirection useStun drillDirection
, if emptyCache then (PlayerMemory Nothing) else memoryFromMove
)
where
(finalMoveDirection, useStun, emptyCache) = if not enemyClose
then (shortestPathMoveDirection, False, False)
else if canStun
then (shortestPathMoveDirection, True, False)
else case find (/= shortestPathMoveLocation) possibleMoves of
Nothing -> (DirectionNone, False, True)
Just l -> (getMoveDirection playerLoc, False, True)Теперь давайте рассмотрим, когда мы используем кэшированную информацию, так как это позволит нам вообще пропустить вызов BFS! При этом мы добавим еще одну проверку достоверности. Мы гарантируем, что список не пуст и что наше текущее местоположение находится в начале списка. Тогда мы можем использовать конец списка памяти как вызов кратчайшего пути!
makePlayerMove :: World -> (PlayerMove, PlayerMemory)
makePlayerMove w = ...
where
(useCache, cachePath) = case playerMemory currentPlayer of
(PlayerMemory (Just (first : rest))) ->
(first == playerLoc, rest)
_ -> (False, [])
shortestPath = if useCache then cachePath
else getShortestPathWithDrills ...Последнее, что нам нужно, это убедиться, что кеш возвращается в память. Это простая модификация нашей функции для перемещения игрока:
modifyWorldForPlayerMove :: World -> Location -> PlayerMemory -> World
modifyWorldForPlayerMove w newLoc memory = ...
where
currentPlayer = worldPlayer w
playerWithMemory = currentPlayer {playerMemory = memory}
playerAfterMove = movePlayer newLoc playerWithMemory
...Теперь мы можем снова запустить наш анализ. Мы увидим, что функции ИИ нашего игрока по-прежнему вносят наибольший вклад. Но процент сильно упал. Теперь они занимают всего около 55% нашего общего времени, вместо 82%! Между тем, процент времени от обычных функций BFS теперь составляет примерно 35%. Самое главное, общее время анализа сократилось в пять раз. При первом запуске это было 32,62 секунды, а теперь всего 6,79 секунды, огромное улучшение!
total time = 6.79 secsCOST CENTRE %time drillBFS.unvisitedNextItems.\ 14.3 drillBFS.newParentsMap.\ 14.2 drillBFS.newVisitedSet 12.6 bfs.newParentsMap.\ 9.9 bfs.newVisitedSet 9.2 bfs.unvisitedNextCells.\ 5.7 getDrillAdjacentItems 4.3 drillBFS.newSearchQueue 2.8 getAdjacentLocations 2.8 drillBFS 2.6 bfs 2.6 getDrillAdjacentItems.mkItemFromResult 2.0 bfs.newSearchQueue 1.8 getDrillAdjacentItems.mkItemFromResult.(...) 1.1 bfs.unwindPath 1.1 bfs.unvisitedNextCells 1.0 drillBFS.unvisitedNextItems 0.9 bfs.newParentsMap 0.7
Вывод
Профилирование — важный инструмент, который мы можем использовать для улучшения нашего кода, независимо от того, на каком языке мы работаем. Когда наша программа работает не так, как нам хотелось бы, мы должны быть уверены, что исправили ее правильные части. Возможно, с самого начала было заманчиво сделать другое предположение. Поскольку вражеских персонажей много, было бы естественно сначала заняться этим алгоритмом. Но результаты нашего профилирования ясно показали, что проблема заключалась в искусственном интеллекте игрока.
На следующей неделе мы начнем изучать различные концепции ИИ. Мы начнем двигаться к ИИ, который можно обучить с помощью машин. Наш код будет проще, но наш продукт будет не так хорош, по крайней мере, на старте! Но мы начнем привыкать к тому, как ИИ может оценивать позиции.
Для получения дополнительных полезных ресурсов для улучшения ваших навыков в Haskell загрузите наш Контрольный список производства! У него есть много разных инструментов и библиотек, которые стоит попробовать!
