From 0919e7008967e30b6ed470ab07924b2818b3e186 Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Sat, 23 Feb 2019 14:33:02 -0600 Subject: [PATCH] fanciful drawing and algorithms --- lua/graph.lua | 13 +++++ lua/regions.lua | 97 ++++++++++++++++++++++++++++++++++++++ lua/utils.lua | 18 +++++++ main.lua | 76 ++++++++++++++++++++++++++++- modules/graph_algorithms.c | 82 ++++++++++++++++++++++++++------ modules/graph_utils.c | 4 +- modules/utils.c | 35 +++++++++----- modules/utils.h | 15 +++--- 8 files changed, 303 insertions(+), 37 deletions(-) create mode 100644 lua/regions.lua diff --git a/lua/graph.lua b/lua/graph.lua index a0a871a..36c2c3e 100644 --- a/lua/graph.lua +++ b/lua/graph.lua @@ -73,4 +73,17 @@ function Graph:getEdges() return edges end +function Graph:getNodePos(nodeID) + return graphs.get_node_pos(self.graph, nodeID) +end + +function Graph:setNodePos(nodeID, x, y) + local g = self.graph + graphs.set_node_pos(self.graph, nodeID, x, y) +end + +function Graph:dijkstras(startID, iterations) + graphs.dijkstras(self.graph, startID, iterations) +end + return Graph \ No newline at end of file diff --git a/lua/regions.lua b/lua/regions.lua new file mode 100644 index 0000000..f64cbcc --- /dev/null +++ b/lua/regions.lua @@ -0,0 +1,97 @@ +local Regions = {} +function Regions:new() + local obj = {} + + local mt = { __index = Regions } + setmetatable(obj, mt) + + return obj +end + +function Regions:add(region) + local id = math.uuid() + region.id = id + + table.insert(self, region) + + table.sort(self, function(a, b) + return a.priority > b.priority + end) + + return id +end + +function Regions:draw() + for i = #self, 1, -1 do + local region = self[i] + local x, y, w, h = unpack(region.rect) + love.graphics.setScissor(x, y, w, h) + love.graphics.push() + love.graphics.translate(x, y) + + region:draw() + + love.graphics.pop() + love.graphics.setScissor() + end +end + +function Regions:mousedown(x, y) + for _, region in ipairs(self) do + local rx, ry, rw, rh = unpack(region.rect) + + if x >= rx and x <= rx + rw + and y >= ry and y <= ry + rh then + + region:mousedown(x - rx, y - ry) + break + end + end +end + +function Regions:mouseup(x, y) + for _, region in ipairs(self) do + local rx, ry, rw, rh = unpack(region.rect) + + if x >= rx and x <= rx + rw + and y >= ry and y <= ry + rh then + + region:mouseup(x - rx, y - ry) + break + end + end +end + +function Regions:mousemove(x, y, dx, dy) + local invoked = false + for _, region in ipairs(self) do + local rx, ry, rw, rh = unpack(region.rect) + + if not invoked + and x >= rx and x <= rx + rw + and y >= ry and y <= ry + rh then + + region:mousemove(x - rx, y - ry, dx, dy) + + if not region.ismouseover then + region:mouseenter() + end + + region.ismouseover = true + invoked = true + else + if region.ismouseover then + region.ismouseover = false + region:mouseleave() + end + end + end +end + +function Regions:update() + for _, region in ipairs(self) do + region:update() + end +end + +return Regions \ No newline at end of file diff --git a/lua/utils.lua b/lua/utils.lua index 069d984..dd1793f 100644 --- a/lua/utils.lua +++ b/lua/utils.lua @@ -1,3 +1,21 @@ function math.lerp(a, b, t) return a + (b - a) * t end + +function math.uuid() + return ("xxxxxxxx-xxxx-4yxx-xxxxxxxx"):gsub('[xy]', function (c) + local v = (c == 'x') and math.random(0, 0xf) or math.random(8, 0xb) + return string.format('%x', v) + end) +end + +local function ripairsiter(t, i) + i = i - 1 + if i ~= 0 then + return i, t[i] + end +end + +function reversedipairs(t) + return ripairsiter, t, #t + 1 +end \ No newline at end of file diff --git a/main.lua b/main.lua index 50d5e68..dfe843a 100644 --- a/main.lua +++ b/main.lua @@ -1,7 +1,9 @@ require "lua.utils" local Graph = require "lua.graph" +local Regions = require "lua.regions" local graph = nil +local regions = nil function love.load() graph = Graph:new() @@ -10,16 +12,88 @@ function love.load() graph:addNode(300, 100) graph:addNode(200, 200) graph:addNode(500, 400) + graph:addNode(0, 0) graph:addArc(0, 1) graph:addEdge(0, 2) graph:addArc(1, 3) graph:addEdge(1, 2) + --graph:dijkstras(0, 0) + love.graphics.setBackgroundColor(0.5, 0.5, 0.5) + + regions = Regions:new() + regions:add { + priority = 1; + rect = { 200, 0, 600, 600 }; + + selectedNode = nil; + + update = function(self) end; + draw = function(self) + love.graphics.setColor(0.7, 0.8, 0.9) + love.graphics.rectangle("fill", 0, 0, 600, 600) + drawGraph(graph) + end; + + mousedown = function(self, x, y) + local nodes = graph:getNodes() + + for _, node in pairs(nodes) do + local nx = node.x + local ny = node.y + local d = (x - nx) * (x - nx) + (y - ny) * (y - ny) + + if d <= 400 then + self.selectedNode = node.id + end + end + end; + mouseup = function(self, x, y) + self.selectedNode = nil + end; + + mousemove = function(self, x, y, dx, dy) + if self.selectedNode ~= nil then + graph:setNodePos(self.selectedNode, x, y) + end + end; + mouseenter = function(self) + end; + mouseleave = function(self) + self.selectedNode = nil + end; + } + + regions:add { + priority = 0; + rect = { 0, 0, 0, 0 }; + + update = function(self) end; + draw = function(self) end; + mousedown = function(self, x, y) end; + mouseup = function(self, x, y) end; + mousemove = function(self, x, y, dx, dy) end; + mouseenter = function(self) end; + mouseleave = function(self) end; + } +end + +function love.mousepressed(x, y, button, isTouch, presses) + regions:mousedown(x, y) +end + +function love.mousereleased(x, y, button, isTouch, presses) + regions:mouseup(x, y) +end + +function love.mousemoved(x, y, dx, dy) + regions:mousemove(x, y, dx, dy) end function love.update() + regions:update() end function drawGraph(graph) @@ -62,5 +136,5 @@ function drawGraph(graph) end function love.draw() - drawGraph(graph) + regions:draw() end diff --git a/modules/graph_algorithms.c b/modules/graph_algorithms.c index 0f199ad..7b4ed49 100644 --- a/modules/graph_algorithms.c +++ b/modules/graph_algorithms.c @@ -1,11 +1,12 @@ #include #include +#include #include "graph_algorithms.h" -static ll_node_p depth_first_search(header head, int start_node) +static dj_node_p depth_first_search(header head, int start_node) { - ll_node_p visited_nodes = insert_ll(NULL,start_node,0); + dj_node_p visited_nodes = insert_dj(NULL,start_node,0); sq_node_p stack = sq_push(NULL, start_node); while (stack != NULL) { @@ -31,7 +32,7 @@ static ll_node_p depth_first_search(header head, int start_node) } else { - visited_nodes = insert_ll(visited_nodes, edge_walker->to_id, 0); + visited_nodes = insert_dj(visited_nodes, edge_walker->to_id, 0); stack = sq_push(stack, edge_walker->to_id); } } @@ -43,17 +44,27 @@ int dijkstras(lua_State *L) header head = (header)lua_touserdata(L, 1); int start_id = lua_tointeger(L, 2); int iterations = lua_tointeger(L, 3); + lua_pop(L, 3); + + int current_iterations = 0; connect walker = head->front; - ll_node_p has_visited = insert_ll(NULL, start_id, 0); - ll_node_p shortest_distance = insert_ll(NULL, start_id, 0); - ll_node_p connected_nodes = depth_first_search(head,start_id); + dj_node_p has_visited = insert_dj(NULL, start_id, 0); + dj_node_p shortest_distance = insert_dj(NULL, start_id, 0); + dj_node_p connected_nodes = depth_first_search(head, start_id); + connected_nodes = remove_dj(connected_nodes, start_id); + dj_node_p distance_walker = connected_nodes; + while (distance_walker != NULL) + { + insert_dj(shortest_distance, distance_walker->node_id, -1); + distance_walker = distance_walker->next; + } - while (connected_nodes != NULL) + while (connected_nodes != NULL && current_iterations <= iterations) { - ll_node_p visited_tmp = has_visited; + dj_node_p visited_tmp = has_visited; int shortest_distance_tmp = -1; int from = -1; int to = -1; @@ -69,26 +80,67 @@ int dijkstras(lua_State *L) while (edge_walker != NULL) { int distance_to_current_node = get_distance(shortest_distance, current_node->node_id); - if (is_in_list(has_visited, edge_walker->to_id) == 0 || distance_to_current_node + edge_walker->weight < get_distance(shortest_distance,edge_walker->to_id)) + if (is_in_list(has_visited, edge_walker->to_id) == 0 || distance_to_current_node + edge_walker->weight < get_distance(shortest_distance, edge_walker->to_id)) { if (shortest_distance_tmp == -1 || distance_to_current_node + edge_walker->weight < shortest_distance_tmp) { shortest_distance_tmp = distance_to_current_node + edge_walker->weight; - from = has_visited->node_id; + from = current_node->node_id; to = edge_walker->to_id; } } + edge_walker = edge_walker->next_edge; } visited_tmp = visited_tmp->next; } - remove_ll(connected_nodes, to); - //shortest_distance + + + if (is_in_list(connected_nodes,to) == 1) + { + connected_nodes = remove_dj(connected_nodes, to); + } + + + dj_node_p sdwalker = shortest_distance; + while (sdwalker->node_id != to) + { + sdwalker = sdwalker->next; + } + + sdwalker->distance = shortest_distance_tmp; + + if (is_in_list(has_visited,to) == 0) + { + insert_dj(has_visited, to, 0); + } + current_iterations++; } - //Start at start node - //Check shortest distance to all connected nodes from all visited nodes - //Repeat with closest node + delete_dj(has_visited); + delete_dj(connected_nodes); + + lua_newtable(L); + dj_node_p sdwalker = shortest_distance; + int index = 1; + while (sdwalker != NULL) + { + lua_pushnumber(L, index); + lua_newtable(L); + + lua_pushnumber(L, sdwalker->node_id); + lua_setfield(L, 3, "node_id"); + + lua_pushnumber(L, sdwalker->distance); + lua_setfield(L, 3, "distance"); + + lua_settable(L, 1); + + sdwalker = sdwalker->next; + index++; + } + //put shorest_distance linked list into table and return table + delete_dj(shortest_distance); return 1; } diff --git a/modules/graph_utils.c b/modules/graph_utils.c index 9388fa5..0a37f95 100644 --- a/modules/graph_utils.c +++ b/modules/graph_utils.c @@ -126,13 +126,13 @@ connect find_node(header head, int node_id) { //walk through node list to find from node connect runner = head->front; - if(runner == NULL) + if (runner == NULL) { return NULL; //graph is empty } //run through list of nodes until node with passed node_id is found - while(runner->node_id != node_id) + while (runner->node_id != node_id) { if(runner == NULL) return NULL; //from id is never found diff --git a/modules/utils.c b/modules/utils.c index afbb519..20c10c9 100644 --- a/modules/utils.c +++ b/modules/utils.c @@ -104,9 +104,9 @@ void sq_print(sq_node_p sq) puts(""); } -ll_node_p insert_ll(ll_node_p front_of_list, int id, int distance) +dj_node_p insert_dj(dj_node_p front_of_list, int id, int distance) { - ll_node_p new_node = (ll_node_p)malloc(sizeof(ll_node)); + dj_node_p new_node = (dj_node_p)malloc(sizeof(dj_node)); new_node->next = NULL; new_node->node_id = id; new_node->distance = distance; @@ -118,7 +118,7 @@ ll_node_p insert_ll(ll_node_p front_of_list, int id, int distance) } else { - ll_node_p walker = front_of_list; + dj_node_p walker = front_of_list; while (walker->next != NULL) { walker = walker->next; @@ -128,10 +128,10 @@ ll_node_p insert_ll(ll_node_p front_of_list, int id, int distance) } } -ll_node_p remove_ll(ll_node_p front_of_list, int id) +dj_node_p remove_dj(dj_node_p front_of_list, int id) { - ll_node_p walker = front_of_list; - ll_node_p follower = walker; + dj_node_p walker = front_of_list; + dj_node_p follower = walker; while (walker != NULL && walker->node_id != id) { follower = walker; @@ -139,7 +139,7 @@ ll_node_p remove_ll(ll_node_p front_of_list, int id) } if (walker == NULL) { - printf("bruh\n"); + printf("bruh %d\n", id); return front_of_list; } else if (walker == front_of_list) @@ -156,9 +156,9 @@ ll_node_p remove_ll(ll_node_p front_of_list, int id) } } -int is_in_list(ll_node_p front_of_list, int id) +int is_in_list(dj_node_p front_of_list, int id) { - ll_node_p walker = front_of_list; + dj_node_p walker = front_of_list; while (walker != NULL && walker->node_id != id) { walker = walker->next; @@ -173,9 +173,9 @@ int is_in_list(ll_node_p front_of_list, int id) } } -int get_distance(ll_node_p front_of_list, int id) +int get_distance(dj_node_p front_of_list, int id) { - ll_node_p walker = front_of_list; + dj_node_p walker = front_of_list; while (walker != NULL && walker->node_id != id) { walker = walker->next; @@ -188,4 +188,15 @@ int get_distance(ll_node_p front_of_list, int id) { return walker->distance; } -} \ No newline at end of file +} + +void delete_dj(dj_node_p front_of_list) +{ + dj_node_p follower = front_of_list; + while (front_of_list != NULL) + { + follower = front_of_list; + front_of_list = front_of_list->next; + free(follower); + } +} diff --git a/modules/utils.h b/modules/utils.h index 15d7bcf..4cef2ce 100644 --- a/modules/utils.h +++ b/modules/utils.h @@ -8,11 +8,11 @@ typedef struct sq_node { struct sq_node * next; } sq_node, *sq_node_p; -typedef struct ll_node { +typedef struct dj_node { int node_id; int distance; - struct ll_node * next; -} ll_node, *ll_node_p; + struct dj_node * next; +} dj_node, *dj_node_p; int sq_top(sq_node_p stack_top); int sq_front(sq_node_p queue_front); @@ -24,10 +24,11 @@ sq_node_p sq_deque(sq_node_p front_of_queue); void sq_print(sq_node_p sq); -ll_node_p insert_ll(ll_node_p front_of_list, int id, int distance); -ll_node_p remove_ll(ll_node_p front_of_list, int id); -int is_in_list(ll_node_p front_of_list, int id); -int get_distance(ll_node_p front_of_list, int id); +dj_node_p insert_dj(dj_node_p front_of_list, int id, int distance); +dj_node_p remove_dj(dj_node_p front_of_list, int id); +void delete_dj(dj_node_p front_of_list); +int is_in_list(dj_node_p front_of_list, int id); +int get_distance(dj_node_p front_of_list, int id); // Helper macros that make the call site of these functions cleaner #define top(sq) (sq_top((sq))) -- 2.25.1