In this project we develop Djikstra's algorithm and A* algorithm as well as the traveling salesman algorithm (not finished) in unreal using C++.
- Having received a starting node, check each connected node.
- Add each connected node to a priority list, ordered by their current cost from the origin node.
- Jump to the node with the least travel cost, aka the first item in the priority list.
- Restart at instruction 1.
Both dijkstra and A* allows you to jump between nodes regardless of them being connected or not. You simply
jump to the node that is at the top of the priority queue.
When calculating the cost of a node, you need to include the cost not only from the current node to the node
we are checking, but also from the current node back to origin. However this becomes simple by setting the
node's cost variable from the beginning. This way it "automatically" includes the cost back to origin.
NextNode->Cost = CurrentNode->Cost + Distance(CurrentNode, NextNode)
The only difference between Dijkstra and A* is that A* also calculates the distance between the next node and
the destination.
NextNode->Cost = CurrentNode->Cost + Distance(CurrentNode, NextNode) + Distance(NextNode, Destination
This makes the priority list "smarter" by prioritizing the nodes that go in the destination's general direction.
This will often get us to the goal faster. A* immediately stops when it has made contact with the destination.
There are some known bugs, for example the debug boundary box will often glitch, which will be fixed by spawning enough nodes. I suspect this is a bug in unreal engine with rendering debug shapes.
Developed with Unreal Engine 5