Grid Lattice and Path Planning

Intro

Motivation for path planning

Follow gradient

• Agent follows around obstacle
  • Pick a direction that lands in a cell minimizing the distance to goal
  • Can get stuck in local minima or maxima

Solution?

• Track candidate path choices and explore until acceptable solution found

Graphs

• A graph is formed by
  • Nodes (N) connected by
  • Edges (E)
    • cost of traversing the path related to the length or difficulty

Types of graphs

• DAG
• directed cyclic graphs

Risk

Game dependency tree

Graph from uniform structure (Grid)

• Early games built from tiles
  • can think of each grid as a node and the adjacency to other traversable cells as edges

Other game types with unique geometry?

• Connecting rooms

Planning

• Manipulate current state of the world to reach a goal
• Operaters- movements taken to change state
  • grid movement- NSWE
  • NavMesh- represent navigable areas with convex polygons connected to each other

Path planning

• States
  • Discretized space- want just the right detail in a discretized representation
    • Tile-based: tiles are inhernetly discrete
    • Can have different waypoints
    • Voxels- cubelike- 3D grid representation
• Operators

Basic strategy for path planning in games

• Create a data structure (graph) that facilities path planning
• Quantize-
• path creation with search algorithm
• localize the path back to the game world
• initiate agent movement and continue until goal reached

Path planning algorithms

• Must search the state space to move agent to goal state
• Computational isues
  • Completeness- will the algorithm find an answer if one exists
  • Time complexity
  • space complexity - How much memory required- performing calculations or caching data
• Optimiality- will it find the best solution

Search strategies

• Blind search- Only consider nodes and edges/weights
• Heuristic search- domain knowledge can drive heuristic rules

Depth first search

• Whichever node you consider first, you expand upon that further and further until you run out of choices, then work your way back and consider other possiblities
• Can easily keep track of where you are based on nature of tree structure, don’t need to worry about getting caught in loops, can leverage recursion

DFS in path planning

Breadth-First Search

• Consider all the children of the starting point before move to next level, which would be like the grandchildren from the starting point
• Can work well for returning a result, because never return a path longer than the shortest chain

Pathfinding

• Sample games where path planning fails
  • discretized space not complete or
  • physical capabilities of the agent doesn’t align with the discretized space

Pathfinding in Sim City

• Sims not considering travel time on shorter dirt road

Issues

• Failures when graph rep or intended path not coordinated with the AI agent and simulated space (environment)

Tile-based games

• Inherent graph structure can be leveraged for path planning
• AI exist in discrete locations
• Easy to keep track of where you can and cannot go

Grid navigation

• 2D tile representation
  • squares- 4 or 8 way
  • Hexagonal board- 6-way

Discretization of continuous space

Generation

• Boundaries and terrain type regions
• Gradients may depend on perspective
  • e.g. can go downhill but not uphill

Discretized space- grid lattice

• Instead of tiles, might have geometry of arbitrary shape or structure relative to grid lattice cells
• Size our grid lattice relative to the world boundaries
  • world perimeter- largest grid we can fit in the game world
• Grids cells with intersection with obstacles are marked as untraversable with blue x’s
• Use integer representation to avoid floating point issues

Generation

• Confirm that world boundaries don’t go through grid lines
• Verify no obstacle point within a grid cell, or vice versa
• Quit as soon as intersection found
• Tests for points before more expensive tests like edge intersections

Grid cells point containment

• Could treat grid cells as polygons
• Assuming axis-aligned dimensions of the grid, can just perform range checks for x and y

Problematic edge cases

• Issues with geometry perfectly algined with grid cells
• Proper line intersection- 2 lines not parallel that intersect somewhere other than an endpoint

Problematic case

• If a polygon was same size as grid cell, might fail to mark as untraversable
• Fix: shrink by 1 unit, now the point test against the polygon would reveal all 4 vertices inside the grid cell

Validity

• May wish to id individual edges
• Validity: Agent can safely navigate from one node to the next adjacent node
• Valid partial blockage- leaves 2 convex polygon shapes
• Invalid partial blockage- 1 of the 2 adjacent grid cells is concave, the other convex
  • Convex geometry- From any interior point, you can see the entirety of the perimeter
  • In Grid (2,2)- Convex- the agent can travel to the left, but up and down might be blocked

Off grid?

• What to do if agent is outside a navigable grid cell
• Can use random movement to eventually get to a valid position
• Can cheat and teleport

Continuous position/movement vs path from discrete graph

• Awkward/blocky movement
• Quantization-induced awkwardness
  • Quantize the agent and goal positions
• “String pulling”- post process path
  • Hold the ends of a string to the agent and goal, then tighten the string
  • this identifies inflection points
• Validity-based optimization- Further improvement
• Can also have a steering behavior at runtime (greedy)

Post Process (String pulling)

• Smoothed path
• Startrek- quadtree- a hierarchical grid
  • Needed to perform string pulling for movements of spaceships on their 2D maps

Search efficiency with a grid lattice

• Grid lattice search algorithm must visit a lot of nodes
• Search space grows very quickly with a grid lattice, especially with a higher-resolution grid
• NxN grids ⇒ N^2 nodes and a lot of edges

Summary

• Grid lattice not great for continuous environments- can’t represent arbitrary areas
• A burden on search efficiency for extra resolution not needed as part of the game
• Poor path quality- will likely need string pulling to improve it