CMPT 306: Behavioural AI and Maps (chatgpt)

What does it mean that a map’s “resolution may vary

The level of abstraction can change (tiles vs large regions vs waypoints), depending on how detailed path planning needs to be

What is an obstacle in map representation?

Any area an agent cannot traverse, such as walls, locked doors, chasms, or narrative restrictions.

What is a grid map?

A grid map represents the world as a 2D grid where each tile is a node and connectivity is defined by adjacency.

Why is a grid map called an “implicit graph”?

Because adjacency is implied by grid structure rather than explicitly storing edges.

Why must tile coordinates be translated into world coordinates?

Because pathfinding operates on grid coordinates, while rendering and movement occur in world space

What is a waypoint map (roadmap)?

A traditional graph where nodes represent key locations in space and edges represent valid movement paths between them

How is connectivity often defined in waypoint graphs?

By line of sight (LOS) between nodes

What are the advantages of waypoint graphs over grid maps?

• More flexible

• Better for large or irregular spaces

• More suitable beyond 2D

What information must a roadmap include to be useful?

• Collision-free nodes and edges

• A cost function (time, distance)

• Full coverage of the map

List the three methods of generating roadmaps discussed in class.

• Hand-drawn

• Visibility graphs

• Random waypoints

What is a hand-drawn roadmap?

A manually created graph where designers place nodes and edges directly in the level.

Give two advantages and two disadvantages of hand-drawn roadmaps.

Advantage: High precision in design, low computational cost; Disadvantage: Time-consuming to create and maintain and not robust to random obstacles.

What is a visibility graph?

A graph where nodes are placed at obstacle corners and edges exist if there is line of sight between nodes.

What is a major disadvantage of visibility graphs?

Graph complexity increases rapidly with many obstacles and can lead to overly “perfect” or unnatural movement

Describe the random waypoint method

Random points are placed in free space, connected via line of sight, then pruned and refined using heuristics

Why is random waypoint considered “quick and dirty”?

It generates reasonable paths quickly but is inefficient, lacks spatial understanding, and can over-generate edges and may miss necessary edges

Name four techniques discussed for converting geometry to graphs.

• Grid overlays

• Navigation meshes

• Waypoint graphs

• BSP / Quadtrees / Octrees

What is a Navigation Mesh (NavMesh)?

A mesh of walkable regions derived from geometry, where adjacency forms a navigation graph.

What is Procedural Content Generation (PCG)?

The algorithmic creation of game content with limited or indirect user input.

What types of content can PCG generate?

Levels

rules

stories

items

quests

music

characters

dialogue

What is a seed in PCG

A parameter that initializes a random number generator to produce reproducible content.

Give three reasons to use PCG.

• More content

• Lower development cost

• Increased replayability

• uses less memory

Give two reasons not to use PCG

• Designers need precise control

• PCG content can feel boring or harm shared experiences

• Potentially lower quality output

  • Increased complexity in debugging and balancing

List the five key properties of a PCG solution.

• Speed

• Reliability

• Controllability

• diversity

• Creativity

What are the three components of a PCG system?

• Generation algorithm

• Content representation (model)

• Evaluation function

What is the difference between genotype and phenotype in PCG?

• Genotype: internal data model

• Phenotype: actual in-game content

Name the three types of evaluation functions.

• Direct evaluation

• Simulation-based evaluation

• Interactive evaluation

What is direct evaluation?

Scoring content using extracted features and predefined metrics.

What is simulation-based evaluation?

Using AI agents to play through generated content to estimate quality.

What is interactive evaluation?

Evaluating content based on human player interaction or feedback

Navigation meshes replace the need for pathfinding algorithms

False

Waypoint graphs are often defined using line of sight.

true

why are hand-drawn maps not robust to random obstacles

If the environment changes unexpectedly, the roadmap can become invalid or produce strange behaviour. e.g. if the designer draws a path through a hallway, during gameplay a door closes or a wall appears, disrupting the intended navigation which can lead to the agent producing strange behaviour like trying to walk into the walls

hand-drawn maps can be linked with a local planner to avoid strange behaviour by agents when random obstacles occur means that

• Use hand-drawn roadmap for high-level planning

• Use local collision avoidance to handle changes