Algorithm Adjustments
Binary Heap
Binary heap optimisation adjusts the way the program stores, gets and sets node information. The binary heap prioritises nodes in hopes of achieving a solution more quickly.
Pros:
Fairly simple to implement.
Provides optimisation for any situation.
Cons:
None.
Map Representation
Navmesh
A navmesh is one of the most commonly used representations of maps. The program takes the geometry of each level, gets each triangle and creates a new grid of simplified polygons that each act as a node. Although very hard to implement from scratch, a navmesh is particularly useful when working with procedural terrain. Unity and Unreal Engine both have native navmesh implementation, however Unity's cannot be fully adjusted whilst the program is running, meaning games with destructible terrain will not be able to use this.
Pros:
Algorithm can be customised to produce an appropriate map representation.
Can be used in any situation, though most useful in terms of procedural terrain.
Reduces the amount of nodes needed to represent a map.
Does not need to be hand placed like way-points, but can serve many of the same purposes.
Cons:
Harder to implement.
Can't be placed by hand for scripted events.
Waypoints
Waypoints are often hand placed nodes for the AI to use. Each waypoint will store information about its neighbours for the algorithm to use.
Pros:
Allows for scripted events, particularly useful for story based games (such as in Uncharted 4)
Can be hand-placed.
Waypoints could be customised. (For instance, the AI could be made to crouch behind cover at a certain waypoint, like Uncharted 4).
Can minimise the amount of nodes needed for a map.
Cons:
Has to be hand-placed.
Hierarchical Representation
A hierarchical representation will use different levels of map representation. For instance, the largest map representation could be a country, followed by a county, then a town, then a road. The AI may not need to use the smallest levels in order to path-find, depending on the situation.
Pros:
Simple to implement.
Significant optimisation on large maps.
Cons:
Few cases where this representation would be relevant.
Conclusion
I have chosen to add binary heap optimisation to my project, as it one of the most easy to implement steps, and provides optimisation in any circumstance. I have decided to keep my current implementation of map representation, as it would be better to change it once levels have been made for the game for maximum optimisation and relevance so I don't run into any obstacles.
Sources:
http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html
https://en.wikipedia.org/wiki/Binary_heap
https://www.cs.cmu.edu/~adamchik/15-121/lectures/Binary%20Heaps/heaps.html
https://www.binpress.com/tutorial/unity3d-ai-navmesh-navigation/119
http://allenchou.net/2016/05/a-brain-dump-of-what-i-worked-on-for-uncharted-4/