Game AI and pathfinding

Czech technical University in Prague
Faculty of Information Technology
Department of Software Engineering
© Adam Vesecký, MI-APH, 2019

Raycasting

Raycasting

  • we simply cast a ray, obtain an object it hits and process the result according to our needs
  • use-cases: rendering, physics, AI
  • used as a variation of raster effects to bypass hardware limits in early-gaming era
    • racing games, combat games and first FPS

1992: StreetFighter 2

1992: Outrunners

1992: Wolfenstein 3D

Basic idea

  • send out a ray that starts at the player location
  • move this ray foward with the direction of the player
  • if the ray hits an object, process it

Principle

Precise sampling

Fixed sampling

Calculation

  • knowing the direction, we need to calculate all rays that cover our field of view
  • to rotate a vector, we can use a rotation matrix

Example: Dark hall

  • src/labs/lab05/example-raycaster.ts
  • use WSAD to move around

Example: Dark hall rendering process

Visibility cone

  • Raycaster use-case for game AI
  • determines whether the bot/NPC can see the player or not
  • sometimes it's only a visual feature while the bots cast direct rays to the player

Commandos (1998)

SneakR (2015)

Example: Visibility cone

Pathfinding

Pathfinding algorithms

  • breadth-first search ignores costs
  • Dijkstra ignores position of the target
  • A* takes into account both of them

Example: Breadth-first search

Example: Dijkstra search

AStar algorithm

start := first node

goal := final node

cost := cost from start to current node

estimation := cost estimation from current node to goal

prio := priority of a node

heuristic := priority calculator

PQ := priority queue

 

1. Create PQ

2. Put start to PQ

3. While PQ is not empty

  3.1 current := node from PQ with lowest priority

  3.2. for each neighbor of current

    3.2.1. if neighbor === goal then FINISH

    3.2.2. newCost := cost(start, current) + distance(current, neighbor)

    3.2.3. estimation := distance(neighbor, goal)

    3.2.4. prio := heuristic(newCost, estimation)

    3.2.5. if there already is a node with lower priority prio in PQ, goto 3.2

    3.2.6. put neighbor with priority prio to PQ

    3.2.7. goto 3.2.

  3.3. goto 3  

Heuristics and distance measurement

Distance measurement

  • Manhattan distance:
  • Euclidean distance:

Heuristics

  • weighted sum of the cost and distance
  • penalty for turning
  • distance from nearest route
  • distance from nearest teleport

Example: AStar tile grid, manhattan dist.

Example: AStar tile grid, euclidean dist.

Example: AStar octile grid, manhattan dist.

Example: AStar octile grid, euclidean dist.

Example: AStar Optimistic heuristic

Example: AStar Pessimistic heuristic

Example: AStar Very optimistic heuristic

Example: AStar Very pessimistic heuristic

Perlin noise for terrain generation

Force field

  • the map is preprocessed, no additional pathfinding required
  • the object is attracted to the closest path, the path leads to the target
  • good for games with a single point of attraction (tower defense paths)

HPA*

  • the level is divided into areas/clusters
  • we use A* pathfinding only inside particular cluster

State machines

Task: cargo bots

Task: cargo bots

  • src/labs/lab05/bots
  • there are sources of petrol and iron
  • the bots need to bring them to the warehouse
  • if the warehouse contains enough cargo (30 iron, 10 petrol), the factory will build a new bot
  • every source has got their own capacity - if the capacity is exhausted, the icon will fade out

State machine

Task: cargo bots

  • the whole model is stored in model.ts
  • GameModel contains the map and global attributes
  • BotModel is a model for each bot
  • CargoSourceModel is a model for iron ores and petrol rigs
  • WarehouseModel and FactoryModel are models for the warehouse and the factory
  • components are responsible for movement logic and visual appearance
  • shared attributes are stored in the model
  • complex tasks, such as moving cargo from the source to a bot, is handled by the model (loadCargo, unLoadCargo etc.)

Task: cargo bots

Task 1

  • finish the implemetation of the FSM in order to make the bots perform their tasks
  • make only changes in bots/bot-ai-component.ts
  • methods:
    • processIdleState
    • processGoingToLoadState
    • processGoingToUnloadState
    • processLoadingState
    • processUnloadingState
  • parameters:
    • isEntering - true if the FSM has just entered the state
    • delta, absolute - time from the update loop
  • every method needs to return either a new state or the current one:
    • IDLE, GOING_TO_UNLOAD, GOING_TO_LOAD, LOADING, UNLOADING
  • BotAIComponent contains methods you can use:
    • goLoad, goUnload, arrivedToTarget, isBotLoaded, moveToTarget

Task: cargo bots

Task 2

  • loading and unloading should take some time - use loadingDelay variable and leave particular states after this delay

Task 3

  • modify goLoad method in order to make the bot prefer cargo of lower amount (if there is no iron, it doesn't make sense to fetch petrol)
  • you can use this.gameModel.goingToLoadPetrol and this.gameModel.goingToLoadOre to check how many bots are currently on their way for appropriate cargo

Task 4

  • modify the behavior in such a way that only one bot can load/unload from/to the same source
  • you will need to modify model.ts : WarehouseModel, FactoryModel and CargoSourceModel in order to store an information that an object is occupied

Task 5

  • Task 4 may need to introduce new states (PENDING, WAITING,...)
  • try to create a diagram of a behavior tree that could better deal with the logic
  • use slides from Lecture 09