Home

How it works?

This example allows to create symmetric directed graph (like one below) and find shortest way between two points, returning distance and list of points that are visited from start to end.

It uses Dijkstra algorithm to find shortest path.

Changelog:

v1.1 - added support for batching search (so can happen for longer than one frame), and added xy graph/vertexes, removed usage of ds_xxx to avoid memory leaks and need of vertex deletion

How it works?

In a graph, there are points, named vertexes. In this library you can give them names (prefferably strings), and then thanks to that, find a way between two vertexes (points, edges).

my_graph = new sd_graph();
my_graph.add(new sd_graph_vertex("London"));
my_graph.add(new sd_graph_vertex("Paris"));
my_graph.add(new sd_graph_vertex("Berlin"));
my_graph.add(new sd_graph_vertex("Rome"));

my_graph.connect("London", "Paris", 461);
my_graph.connect("London", "Berlin", 1094);
my_graph.connect("Paris", "Berlin", 1055);
my_graph.connect("Paris", "Rome", 1424);
my_graph.connect("Berlin", "Rome", 1505);

search = new sd_graph_search(my_graph, "London", "Paris");
search.pass();
result = search.result();
show_debug_message($"London to Paris distance is {result.distance}km long, and leads by {result.path}");

This would result in: London to Paris distance is 1885km long, and leads by [ "London","Paris","Rome" ]

search.result()

search.result() returns a struct:

• finished: whether finished true/false serach
• found: whether any path was found (usually not found if searching from same node to same node; false until finished == false)
• time_taken: number of miliseconds (1/1000) that search taken (up to now) (not to mistake with microseconds returned by get_timer())
• path: Array which have ordered list of vertexes from start to end point (only when found & finished)
• distance: distance between start and end point (for xy graph it's always number of pixels, but for normal graph this is kinda abstract and depends on you what this number represents - might be pixels, or like in first example - kilometres); 0 until finished = false.

Limit passes

To limit how many vertexes are visited in a search pass, you can use 4th optional parameter when creating sd_graph_search - by default it's infinity. Remember, that while it limits how many vertexes we compute in one pass, it will still get distances to all nodes connected to this vertex, so for example, if limit is 1 pass, but vertex have 5 connected vertexes to it, we're computing distances to 5 nodes.

You can find out if search finished in 3 ways:

• search.finished
• search.pass() would return true when finished
• search.result().finished would return true when finished

An example of search:

// somewhere, create new search
search = new sd_graph_search(my_graph, "London", "Paris", 2); // 2 - means 2 nodes per .pass()

// step
if (!search.finished) {
    search.pass();

    if (search.finished) {
        show_debug_message(search.result());
    }
}

Limit passes to stop when certain (frame) time is exceeded

if (!search.finished) {
    var time = get_timer(); // returns time since game started in microseconds
    var limit = time + ((1/60) * 0.25 * 1_000_000_000); // (1/60)*0.25-> 25% of one frame when 60 FPS, 1_000_000 - microsecond

    while(search.finished == false) {
         search.pass();
         if (get_timer() > limit) break; // takes too long!
    }
}

Use xy graph to not give distances

my_xy_graph = new sd_graph_xy();
my_xy_graph.add(new sd_graph_vertex_xy("A", 5, 5)); // notice sd_graph_vertex_xy instead of sd_graph_vertex
my_xy_graph.add(new sd_graph_vertex_xy("B", 10, 20));
my_xy_graph.add(new sd_graph_vertex_xy("C", 5, 15));

my_xy_graph.connect("A", "B"); // distance is not needed now
my_xy_graph.connect("B", "C");
my_xy_graph.connect("C", "A");

search = new sd_graph_search(my_xy_graph, "A", "C");
search.pass();
result = search.result();
show_debug_message($"A to C distance is {result.distance}px, and leads trough {result.distance}");

And result will be: A to C distance is 10px, and leads trough [ "A","C" ]