” get from A to B as short as possible”
Quick Facts
| Type of project: |
| Solo, Spare time |
| Date Produced: |
| summer 2019 |
| programs used: |
| Unity |
Key points
- Dijkstra’s algorithm is a process of getting from A to B through through the shortest route possible.
- it does this by calculating the best possible cost from every node associated with it.
- the algorithm is mainly used in networks, however, the algorithm can be programmed differently to perform A*; a game-preferred algorithm to get from A to B.
the full story
while preparing for the year 2 of the course. i knew that part of the modules learned would deal with mathematical algorithms in programming form. to understand the general basis of specified algorithms and converting it to one form to another, i decided to create a functional program of Dijkstra’s algorithm.
the program is split into two parts, the algorithm itself and the visual representation of the algorithm for the user. classes like nodes and overall graph is created to hold the information required. a adjacency matrix is used to hold not only the connections between nodes, but the weight as well. finally, methods are created to replicate the mathematical process of Dijkstra.
the visual part was a little complicated, but would allow for greater customisation. for a Dijkstra graph to be produced, there needs to be a dedicated start and end node, arcs, nodes, weights and labeling as well. the program must also deal with multiple scenarios that can be produced by the user. this includes deleting the start/end node, an arc pointing to an non-existent node and the movement of nodes. once the graph is checked, blue arcs will appear along with the lowest cost and path is produced. this shows the path to get from point A to point B.
with more given time, the program can be modified to do A* in relation of node distances. A* is similar to Dijkstra, however, it takes account the heuristic value of nodes. most of the cases is the distance from that node to the end node. that value goes with the Dijkstra’s value to determine where to go. the major feature about A* is that not all nodes will be counted for, only nodes that are used or that the program is aware of will be recorded into separate lists.
