A* Data Structures and Heuristics

Question 1

Ways of improving pathfinding performance

Answer 1

A* data structures
Heuristics for pathfinding
A* variants for pathfinding

Question 2

Types of data structures we can use on the Open and Closed lists of A*

Answer 2

List ordered by F-Value
Array where we can use binary search
Priority Heap

Question 3

Priority Heap defenition

Answer 3

Binary tree where all nodes are ordered in relation with their parent

Question 4

Define Insertion on Priority Heap

Answer 4

Insert element on next available position (left to right)

Heapify Bottom up

Question 5

Insertion Complexity on Priority Heap

Answer 5

O(log n)

Question 6

Define Extract on Priority Heap

Answer 6

Replace root with most bottom-right value

Heapify Top Down

Question 7

Extract Complexity on Priority Heap

Answer 7

O(log n)

Question 8

When should we use Node Array A*?

Answer 8

When we want to trade memory for speed

Question 9

What should we do different on Node Array A* compared to A*?

Answer 9

Create an array with node records for all nodes in the graph before the algorithm begins
Number nodes using sequential integers
Give an adittional feature to the nodeRecord called Category (unvisited, open, closed)

Question 10

Why is Node Array A* faster?

Answer 10

Testing if a node is in open or closed is very fast
Closed List is not needed
Open list is now ordered by F value

Question 11

Fill definition

Answer 11

Number of nodes considered by the search algorithm but are not part of the shortest path

Question 12

Examples of heuristics for open spaces

Answer 12

Euclidean distance
Manhatan distance (where diagonall movements are not allowed)

Question 13

What are good ways to Solve Ties in the Open List?

Answer 13

Prefer nodes with lowest heuristic value
Slightly increase the value of the heuristic
Prefer recent nodes

Question 14

For indoors levels should we use traditional distance heuristics or cluster based heuristics?

Answer 14

Cluster based heuristics

Question 15

Define Cluster Heuristics

Answer 15

Group nodes in clusters

Clusters represent regions of the level highly interconnected

Question 16

How does Floodfill Clustering work for clustering creation?

Answer 16

1- Find the top leftmost tile that is not in a cluster
2- Fill to the right until: Area opens upward/Reaching a non-free tile
3- Check borders: If border shrinks after a first grow/Stop at regrow
4- Repeat from 1

Question 17

Define Cluster Table Heuristic

Answer 17

Create a table with distances between clusters

Question 18

Problems with Cluster Table Heuristic

Answer 18

A* will explore all nodes in a cluster before exploring the next cluster
If cluster sizes are small we mitigate this problem but we have much more pre-processing to do

Question 19

Examples of Heuristics for room based maps

Answer 19

Dead-End Heuristic

Gateway Heuristic

Answer 20

…