# Dijkstra path-finding

#### Luden

You must be logged in to obtain assets

### Description

There is node based pathfinding. It is a classic algoritm by Dijkstra, which was wrote on GML.

This project has two different part.

Part 1. Map creating. Algorithm needs a map. It is called graph and includes coordinates of nodes and connections between them.

I have written special program for automatization creating graph. All elements contain in folders graph create. You must run room r_matrix_create for use it. Also, you can set any backround to help you set nodes.

Program works in two modes. Switching between them on "M" button.

First - setting nodes. Left click - set node, right click - delete.

Second - setting connections. Left click - set first node, after that set second node. Right click - delete.

It is easy. Now about save/load. There is special functions - graph_load/graph_save. They need argument file name. For example I am using "path_matrix.txt". In program "S" - save, "L" - load, but you can change it.

Info for file parsing You may use this file for other goals. First number is amount of nodes. After that you can read them x / y coordinates. And after that adjacency matrix(you can read in wiki, it's easy), where 1 is connected, -1 not.

Part 2. Pathfinding. Ok. Now, we have a map and can use it. Room "r_dijkstra" show it. We need only one object obj_dijkstra_general for algorithm work, but I else use obj_dijkstra_node and obj_voyager for displaying it. You need one obj_dijkstra_general for every graph.

In this part we have three functions. * dijkstra_load_graph - It loads the previously created file * dijkstra_set_start_data - set necessary data for work * dijkstra_path_find - general algorithm. It needs start and finish nodes, returns standart GM path.

About start and finish nodes. We have two arrays node_x and node_y, which contain coordinates of nodes. We must pass position in that arrays to dijkstra_path_find. If you open dijkstra_load_graph, you will see place where I create nodes for displaying and how I save this position in nodes. Use way like that.

IMPORTANT There is macros - I_AM_BIG. This macros must be defined by user. It is absolute max distance for connections between nodes. I usually set it to 64000 but if you map bigger, please, set more.