Project Overview
My application will facilitate dynamic and adjustable NPC movement within a video game. The more realistic an NPC behaves, the more a player will be immersed in—and engage with—a game. The first impression a player will get of an NPC’s behavior (outside of scripted cutscenes) typically comes from their movement. Broadly speaking, that movement will fall somewhere between two ends of a spectrum:
- On one end are the “Broken Roombas”—NPCs that make such illogical and impractical movements that the player becomes distractingly aware of how terribly they are programmed. In this case, not only is player immersion broken, but the challenge posed by the NPC is so trivial that the player becomes bored.
- On the other are “’T-1000s”—perfectly optimized machines, always making the best choices at the best times with ruthless efficiency. This level of performance would be physically impossible for a human being to replicate. This gives players an “unfair” feeling, similar to when a friend is watching your screen, or another player uses hacks to see you through walls. This won’t break immersion as obviously (though it still might), but creates increasingly frequent “quit moments” due to the frustration of dealing with such unfairness in gameplay
My application will allow designers to pick and choose where their NPCs will fall on that spectrum. Essentially, they will decide how often and to what magnitude their NPCs will take intentionally inefficient paths (i.e. “mistakes”). This would allow certain NPCs to appear calculating and intelligent, while others would resemble bumbling Bond-villain henchmen. This adjustability will augment the illusion of “realness” these NPCs display, and create gameplay opportunities for players to take advantage of.
Data Structure & Algorithm Comparison
When choosing a pathfinding algorithm and data structures, there were five primary options I researched: Djikstra’s, Depth-First Search, Breadth-First Search, Best-First Search, and A*. There are three main criteria to consider when examining that list:
- Efficiency — what are the time and space complexities of the data structures involved?
- Completeness — does the algorithm guarantee a path will be returned?
- Optimality — does the algorithm guarantee the shortest path will be returned
Dijkstra’s Algorithm
Primary Data Structure Component
- Fibonacci Heap — A heap-based structure that is a collection of heap-ordered multi-trees. This is an improvement of a binomial tree structure, that makes better use of amortized operations to improve overall performance for nearly all operations. This will be discussed more in-depth during the analysis of the A* Algorithm. For now, suffice it to say that the amortized Time Complexity for nearly all operations is Constant Time, O(1); the exceptions being the delete_min() and extract_min() operations, which is Logarithmic, O(Log N). Taking those costs into account, the overall time complexity of the data structure is O(E + V Log V) → O(V Log V), because you will be using extract_min() as much as V times (number of vertices), and decrease_key() (O(1)) as many as E times (total number of edges connecting the vertices).
Completeness & Optimality
- This algorithm is both Complete and Optimal.
Summary & Verdict
- Theoretically an excellent choice in terms of all three criteria. However, in a game implementation, it evaluates far too many unnecessary spaces due to its lack of a heuristic. We can do better.
Depth-First Search
Primary Data Structure Component
- Stack — A stack is used to recursively explore nodes until the target is reached, or it is incapable of moving forward (at which point the stack will be pop’d until a new branch can be explored). The time and space complexity guarantee will be equal to the number of nodes explored while recursing, worst case O(N).
Completeness & Optimality
- This algorithm is complete, but the stack structure renders it suboptimal—it will simply return a path as soon as the target is reached, there is no guarantee it will be the shortest one.
Summary & Verdict
- Unfortunately it is suboptimal, so it cannot be used for this application.
Breadth-First Search
Primary Data Structure Component
- Queue — This uses a queue to iteratively explore nodes in FIFO order. Nodes are enqueued from the adjacency list, and dequeued when being explored. In the worst case, it would iterate through every node, O(N).
Completeness & Optimality
- This algorithm is both complete and optimal.
Summary & Verdict
- Unfortunately, the efficiency is far too likely to approach the worst case scenario, as it explores every node in the order it is encountered, including many in the opposite direction of the target. Not a good match for a game implementation.
Standard Best-First Search
Primary Data Structure Component
- Min-Heap Priority Queue — Using a heuristic measurement, nodes are placed in a min-heap priority queue, and are explored in order of smallest to largest. The overall time complexity would be O(N Log N), as the structure must be reheapifyed whenever an element is removed from it via either extract_min(), or inserted() into it.
Completeness & Optimality
- This algorithm is complete, but suboptimal, as it uses only a partial heuristic estimating distance to target.
Summary & Verdict
- Very close to what we’re looking for, but it needed a better heuristic…
A* Algorithm
Primary Data Structure Component
- Fibonacci-Heap — Like Dijkstra’s, this will make use of a Fibonacci Heap, with its low amortized time/space efficiency costs: O(E + V Log V). However, due to its improved heuristic measurement, the actual time complexity will not really reach that high except in the worst case. Instead, the time and space complexities are better modeled by O(B^M), where B represents the branching factor—number of possible locations to explore from any given vertex—and M represents the maximum depth of the path from the goal to the target. In the average case, time and space complexity would be modeled as O(B^D), where D represents the depth of the actual path returned.
Completeness & Optimality
- This is both complete and optimal.
Summary & Verdict
- This is a best of both worlds solution, combining aspects of Dijkstra’s Algorithm with a Best-First Search
A* Data Structure Analysis
As the seemingly best option available is the A* Algorithm, below is a more in-depth analysis of the various data structures that comprise it, and what role they each play.
Open List — Fibonacci Heap
Time Complexities
Individual Operations — insert(x), find_min(), merge(x, y), extract_min(), decrease_key(x, k), delete(x), delete_min().
The time complexity for almost every operation is constant, O(1), except for extract-min() and decrease_key(), which are O(log N). This is due to the “lazy” implementation of insert() and merge(): all nodes are initially inserted as singleton trees into the root of the min-heap, without any reheapifying. Merges are only handled when extract_min() is used, and are simplified by merging roots together, with the lower value remaining the root.
The unique structure of the Fibonacci Heap, and how it is able to amortize costs so effectively, is due to how nodes are linked together: all root nodes are bound together in a circular linked list, as are all sibling nodes within trees. This enables extremely quick merge operations when compared to the traditional binary or binomial tree structure.
There is additional spatial overhead required for this structure compared to more simple min-heap implementations due to the additional linked list fields required by each node. There is also the possibility that the “lazy” merging could lead to latency spikes as multiple merge operations are carried out at once.
Role Within the Algorithm
The Open List will contain every node that is encountered during the exploration. Beginning with the origin as the only entry, nodes that are explored will have their neighbors added to the Open List, making them available for future explorations.
Links with Other Data Structures
The Open List will work closely with nearly every other data structure in the algorithm, as it is the main engine determining the overall efficiency.
As nodes are selected and removed from the Open List to be explored, they are moved to the Closed List.
When nodes are added to the Open List, their distance from origin is retrieved from the Cost Map.
While exploring a node and calculating heuristics, it may be necessary to interact with nodes on the Open List to adjust their cost values.
Closed List — Hash Set
Time Complexity
As a hash-based structure, insertion, retrieval, and deletion are all constant time, O(1).
Role Within the Algorithm
When nodes are selected from the Open List, they are placed on the Closed List so they are not revisited unnecessarily, saving us from wasted operations.
Links with Other Data Structures
Receives nodes from the Open List.
Cost Map: Hash Map
Time Complexity
As a hash-based structure, operations are constant time, O(1).
Role Within the Algorithm
The Cost Map plays the vital role of storing each node on the Open and Closed Lists’ shortest distance from the Origin. In some implementations, it may also store a reference to the node that immediately preceded it on that shortest path, allowing for quick path recreation.
Links with Other Data Structures
Supplies data to all operations involving nodes and distances, most notably for the Open List, and the Heuristic function
Heuristic: Function
Time Complexity
As a computation, this can be assumed to take constant time, O(1).
Role Within the Algorithm
This function will supply distance estimates to the other data structure components. This involves the cost from origin, g(n), the estimate to target, h(n), and the combination of the two, f(n). The most important value being f(n), which will be used to differentiate nodes that are similar distances from the target (h(n)), but take shorter paths to get to where they are (g(n)).
Links with Other Data Structures
After a node is removed from the Open List, the Heuristic is calculated.
Based on the results of the Heuristic, it may be necessary to update the g(n) scores for neighboring nodes if a lower value could be achieved.
The shortest path returned will include the nodes with the lowest combined f(n) scores.
Parent Map: Hash Map
Time & Space Complexities
Again, a hash structure. The constant and incessant hashing is vital to this application’s performance.
Role Within the Algorithm
This will be how the shortest path is actually returned. This hash map will have nodes as keys, and the node that preceded them along the shortest path from the origin will be their values.
Once the target node is added to this list, we can simply return all of the nodes in reverse order, using values as keys, to rebuild the shortest path in near constant time.
Links with Other Data Structures
Nodes will be added to the Parent Map once they are done being explored by the overarching search function.
Once the target node is added to the Open List, it will be summarily explored and added to the Parent Map, and the shortest path will be returned.
How Adjustability Could Be Introduced
random() Multiplier Added to Heuristic
An adjustable random() multiplier could be added to the Heuristic Function, adding noise to the distance estimates, and scrambling the results. This would create more erratic pathing, that could vary from a step out of place to cartoon lightning bolt patterns.
As the modified component of the application would be a computation, this would have little impact on the overall time efficiency, and no effect on the spatial efficiency.
Modify Shortest Route During Return
Alter the shortest path after it has been found to create miniature suboptimal paths within it.
This would require adjustments to the Closed List, as there would (likely) be no nodes along the shortest route still remaining on the Open List. Depending on how that was implemented, there could be temporal or spatial complexity increases.
Alternate First/Second/Third/Fourth Best While Building Path
While building the path and exploring nodes, alternate which node on the Open List will be explored. This could potentially mean adding nodes on the Open List directly to the Closed List without evaluating them, or by pretending to evaluate them and giving them false numbers.
This would very likely increase the time temporal complexity, as additional operations on nodes within the Fibonacci Heap would have to be performed, including multiple iterations of extract_min essentially being wasted.
Switch Algorithm and/or Data Structures
This would be more involved to say the least, but there could be a list of options, 1, 2, 3, or 4, where each option represented a more accurate pathfinding solution. Say #1 was the A* Fibonacci Heap, #2 was the Greedy A* Fibonacci Heap, #3 was a Best-First Priority Queue, and #4 was a Depth-First Stack.
This would require the building and implementation of numerous data structures, however many components could overlap, such as the Parent Hash Map, Cost Map, etc. The overlap of components would reduce workload by a fair amount, so long as each data structure was properly encapsulated for modularity.
My Preference
Would be to implement the adjustability as the random() noise within the heuristic. This would add the least latency to the program, and would also be the simplest to implement.
I may also attempt to build the skeleton of the Algorithm/Data Structure Toggle if I have the capacity. I think the addition of that toggle, PLUS the random() heuristic modifier, would lead to the greatest array of adjustability.
Bibliography / Resources
Dijkstra’s Algorithm Demystified: Shortest Paths, Limitations, and Smarter Alternatives — Prajwal Ahluwalia — https://medium.com/@prajwal_ahluwalia/dijkstras-algorithm-demystified-shortest-paths-limitations-and-smarter-alternatives-280a500e7781#:~:text=Single%2DSource%2C%20Single%2DDestination,This%20can%20be%20inefficient.
Dijkstra’s Algorithm — Wikipedia — https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Fibonacci Heaps and Their Uses in Improved Network
Optimization Algorithms — Michael L. Fredman & Robert Endre Tarjan — https://dl.acm.org/doi/pdf/10.1145/28869.28874
Depth-First Search (DFS) — Karleigh Moore, Ken Jennison, and Jimin Khim contributed — https://brilliant.org/wiki/depth-first-search-dfs/
DFS vs BFS Algorithm (All Differences With Example) — WsCube Tech — https://www.wscubetech.com/resources/dsa/dfs-vs-bfs
Greedy Best First Search — Virtual Labs — https://ai1-iiith.vlabs.ac.in/exp/greedy-best-first-search/theory.html
A Star Algorithm — venkys.io — https://www.venkys.io/articles/details/a-star-algorithm#:~:text=The%20time%20complexity%20of%20the,of%20nodes%20in%20the%20graph.
A* Search Algorithm — Geeks for Gaming — https://www.geeksforgeeks.org/a-search-algorithm/
A* Pathfinding Algorithm — Graham Cox, reviewed by Grzegorz Piwowarek — https://www.baeldung.com/cs/a-star-algorithm
Fibonacci Heap | Set 1 (Introduction) — Geeks for Gaming — https://www.geeksforgeeks.org/fibonacci-heap-set-1-introduction/
Fibonacci Heaps — Lecture Slides by Kevin Wayne — https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/FibonacciHeaps.pdf
Fibonacci heap — Wikipedia — https://en.wikipedia.org/wiki/Fibonacci_heap#Performance
Fibonacci heaps in 6 minutes — Intro, video — Michael Sambol — https://www.youtube.com/watch?v=0vsX3ZQFREM
Sean Foreman Game Development 