gmclan-org/dijkstra-graph

Dijkstra algorithm solution in GameMaker (Studio 2) to find shortest path in graph between two points.

Dijsktra pathfinding in weighted graph for GameMaker

This is example of pathfinding in weighted graph, using Dijsktra alghoritm. It uses priority queques for searching rather than matrices, which would require NxN array, where N is number of nodes.

Also contains an example of creating/updating/displaying graph, which isn't required to work.

Check Wiki for more info.

Znajdywanie drogi w grafie z wagami używając alorytmu Dijsktry dla GameMaker

Przykład znajdywania drogi w grafie z wagami używając alorytmu Dijsktry. Korzysta z kolejek priorytetowych zamiast z macierzy, co wymagałoby tablicy o rozmiarze NxN, gdzie N to licza wierzchołków.

Zawiera te przykład dodawania/edytowania/wyświetlania grafu, który nie jest wymagany do działania.

Dokumentacja znajduje się w Wiki.

---

Created by Piotr Gnys (@gnysek).

Managed by GameMaker's Clan - gmclan.org.

You can freely use, modify, and re-distribute code. Of course it would be nice if you mention author in game credits, but this is not required.

*GameMaker was previously known as GameMaker Studio 2.

dijkstra-graph's Issues

allow creating nodes which returns their `x, y` without usage of objects

Extend

dijkstra-graph/scripts/vertex/vertex.gml

Line 3 in 816bc10

function vertex(_id) constructor {

upgrade `connect_points` so it can connect backwards without calling this function twice with opposite args

dijkstra-graph/scripts/connect_points/connect_points.gml

Lines 3 to 10 in 4a29736

	function connect_points(gr, a, b){
	if (a == b) return false;
	var _va = gr.get_vertex(a);
	var _vb = gr.get_vertex(b);
	var _dist = objects_distance_by_name(a, b);

Cleaning node variables

dijkstra-graph/objects/obj_editor/Mouse_53.gml

Lines 44 to 57 in 5b70501

	if (mode == editor_mode.connecting) {
	if (node1 == -1) {
	node1 = instance_nearest(mouse_x, mouse_y, obj_node);
	} else {
	node2 = instance_nearest(mouse_x, mouse_y, obj_node);
	connect_points(global.my_graph, node1.name, node2.name);
	connect_points(global.my_graph, node2.name, node1.name);
	node1 = -1;
	node2 = -2;
	}
	}

Line 54: Why reseting to -2 ?

prepare example with non-straight lines, using GM paths and their lengths