implementedHEADmaster

7 files changed, 301 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..d86ba9f
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+obj/
+bin/
\ No newline at end of file
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..343ba8c
--- /dev/null
+++ b/README.md
@@ -0,0 +1,3 @@
+### Kruskal
+
+This is a simple implementation of the kruskal algorithm for maze generation in C. [Demo](https://batnako.net/demos/kruskal.html)
diff --git a/build.sh b/build.sh
new file mode 100755
index 0000000..fbbd792
--- /dev/null
+++ b/build.sh
@@ -0,0 +1,70 @@
+#!/bin/sh
+
+cd ${0%/*} # go to project root
+
+FLAGS="-Wall -Wextra -g -pedantic"
+FLAGS_RAYLIB="-lraylib -lm -lpthread -lGL -ldl -lrt -lX11"
+SRC="src"
+BIN="bin"
+OBJ="obj"
+NAME="kruskal"
+
+RUN=0
+VALGRIND=""
+
+WEB=0
+RAYLIB_SRC="/usr/local/src/raylib/src" #for web only
+
+function __run__ {
+    RUN=1
+}
+
+function __valgrind__ {
+    VALGRIND=valgrind
+    RUN=1
+}
+
+function __clean__ {
+    rm -rf $BIN
+    rm -rf $OBJ
+    kill $( ps -q $$ -o pgid= ) # exit
+}
+
+function __web__ {
+    WEB=1
+}
+
+set -xe
+
+if ! { [[ $# -eq 0 ]]; } 2> /dev/null
+then
+    __$1__
+fi
+
+
+mkdir -p $BIN
+mkdir -p $OBJ
+
+if { [[ $WEB -eq 0 ]]; } 2> /dev/null
+then
+    gcc -o $OBJ/main.o -c $SRC/main.c
+    gcc -o $OBJ/set.o -c $SRC/set.c
+    gcc -o $BIN/$NAME $OBJ/main.o $OBJ/set.o $FLAGS $FLAGS_RAYLIB
+
+    if ! { [[ $RUN -eq 0 ]]; } 2> /dev/null
+    then
+        $VALGRIND $BIN/$NAME
+    fi
+else
+    source emsdk_env.sh
+
+    emcc -o $BIN/$NAME.html $SRC/main.c $SRC/set.c \
+         $FLAGS -DPLATFORM_WEB -DRAYLIB_SRC="\"$RAYLIB_SRC/raylib.h\"" \
+         $RAYLIB_SRC/libraylib.a \
+         -I$RAYLIB_SRC/raylib.h \
+         -s USE_GLFW=3 -s ASYNCIFY \
+         --shell-file $SRC/shell.html
+
+    # delete e line that blocks backspace and tab
+    sed -i $(($(grep "keyCode === 8" $BIN/$NAME.js -n | cut -d : -f 1)+1))d $BIN/$NAME.js > /dev/null
+fi
diff --git a/src/main.c b/src/main.c
new file mode 100644
index 0000000..90de051
--- /dev/null
+++ b/src/main.c
@@ -0,0 +1,90 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <time.h>
+
+#include "set.h"
+
+#ifndef PLATFORM_WEB
+  #include <raylib.h>
+#else
+  #include RAYLIB_SRC
+#endif
+
+#define W 800
+#define H 600
+
+#define NODES_X 20
+#define NODES_Y 15
+#define NODE_L 40
+
+set *nodes[NODES_X][NODES_Y];
+bool walls_hori[NODES_X][NODES_Y-1] = {0}; // false - exists
+bool walls_vert[NODES_X-1][NODES_Y] = {0}; // true - doesnt exist
+
+void init_nodes()
+{
+    for(int i = 0; i < NODES_Y; i++)
+        for(int j = 0; j < NODES_X; j++)
+            nodes[j][i] = set_create();
+}
+
+void deinit_nodes()
+{
+    for(int i = 0; i < NODES_Y; i++)
+        for(int j = 0; j < NODES_X; j++)
+            set_free(nodes[j][i]);
+}
+
+void update()
+{
+    // optimize picking random number thingy
+    if(rand() % 2) {
+        int x = rand() % NODES_X;
+        int y = rand() % (NODES_Y-1);
+
+        if(set_find(nodes[x][y]) != set_find(nodes[x][y+1])) {
+            walls_hori[x][y] = true;
+            set_union(nodes[x][y], nodes[x][y+1]);
+        }
+    } else {
+        int x = rand() % (NODES_X-1);
+        int y = rand() % NODES_Y;
+
+        if(set_find(nodes[x][y]) != set_find(nodes[x+1][y])) {
+            walls_vert[x][y] = true;
+            set_union(nodes[x][y], nodes[x+1][y]);
+        }
+    }
+
+    for(int i = 0; i < NODES_Y; i++) {
+        for(int j = 0; j < NODES_X; j++) {
+            if(i < NODES_Y-1) if(!walls_hori[j][i])
+            DrawLine((j+0)*NODE_L, (i+1)*NODE_L, (j+1)*NODE_L, (i+1)*NODE_L, RED);
+
+            if(j < NODES_X-1) if(!walls_vert[j][i])
+            DrawLine((j+1)*NODE_L, (i+0)*NODE_L, (j+1)*NODE_L, (i+1)*NODE_L, RED);
+
+        }
+    }
+}
+
+int main(void)
+{
+    srand(time(NULL));
+    InitWindow(W, H, "Kruskal");
+    SetTargetFPS(60);
+    init_nodes();
+
+    while(!WindowShouldClose())
+    {
+        BeginDrawing();
+        ClearBackground(RAYWHITE);
+        DrawFPS(10, 10);
+        update();
+        EndDrawing();
+    }
+
+    deinit_nodes();
+    return 0;
+}
diff --git a/src/set.c b/src/set.c
new file mode 100644
index 0000000..b84ae6a
--- /dev/null
+++ b/src/set.c
@@ -0,0 +1,40 @@
+#include <stdlib.h>
+
+#include "set.h"
+
+set *set_create()
+{
+    set *s = malloc(sizeof(set));
+    s->parent = s;
+    s->rank = 0;
+    return s;
+}
+
+void set_free(set *s)
+{
+    free(s);
+}
+
+set *set_find(set *s)
+{
+    if(s->parent == s)
+        return s;
+    s->parent = set_find(s->parent);
+    return s->parent;
+}
+
+void set_union(set *x, set *y)
+{
+    x = set_find(x);
+    y = set_find(y);
+
+    if(x == y) return;
+
+    if(x->rank > y->rank) {
+        y->parent = x;
+    } else {
+        x->parent = y;
+    }
+
+    if(x->rank == y->rank) x->rank++;
+}
diff --git a/src/set.h b/src/set.h
new file mode 100644
index 0000000..b92d229
--- /dev/null
+++ b/src/set.h
@@ -0,0 +1,14 @@
+#ifndef SET_H
+#define SET_H
+
+typedef struct set {
+    struct set *parent;
+    int rank;
+} set;
+
+set *set_create();
+void set_free(set *s);
+
+set *set_find(set *s);
+void set_union(set *x, set *y);
+#endif
diff --git a/src/shell.html b/src/shell.html
new file mode 100644
index 0000000..3abc1b0
--- /dev/null
+++ b/src/shell.html
@@ -0,0 +1,82 @@
+<!DOCTYPE html>
+<html lang="en-us">
+  <head>
+    <meta charset="utf-8">
+    <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
+    <title>Pendulum</title>
+    <style>
+      .el { margin: 5px; }
+      div.el { float: left; }
+      textarea.el { font-family: monospace; width: 100%; }
+      canvas.el { border: 0px none; background-color: black; }
+    </style>
+  </head>
+  <body>
+    <div class="el" id="status">Downloading...</div>
+
+    <div class="el">
+      <canvas id="canvas" oncontextmenu="event.preventDefault()" tabindex=-1></canvas>
+    </div>
+
+    <textarea class="el" id="output" rows="12"></textarea>
+
+    <script type='text/javascript'>
+
+      var statusElement = document.getElementById('status');
+
+      var Module = {
+        attachGLFWEventsToCanvas: true,
+        preRun: [],
+        postRun: [],
+        print: (function() {
+          var element = document.getElementById('output');
+          if (element) element.value = ''; // clear browser cache
+          return function(text) {
+            if (arguments.length > 1) text = Array.prototype.slice.call(arguments).join(' ');
+            // These replacements are necessary if you render to raw HTML
+            //text = text.replace(/&/g, "&amp;");
+            //text = text.replace(/</g, "&lt;");
+            //text = text.replace(/>/g, "&gt;");
+            //text = text.replace('\n', '<br>', 'g');
+            console.log(text);
+            if (element) {
+              element.value += text + "\n";
+              element.scrollTop = element.scrollHeight; // focus on bottom
+            }
+          };
+        })(),
+        canvas: (function() {
+          var canvas = document.getElementById('canvas');
+
+          // As a default initial behavior, pop up an alert when webgl context is lost. To make your
+          // application robust, you may want to override this behavior before shipping!
+          // See http://www.khronos.org/registry/webgl/specs/latest/1.0/#5.15.2
+          canvas.addEventListener("webglcontextlost", function(e) { alert('WebGL context lost. You will need to reload the page.'); e.preventDefault(); }, false);
+
+          return canvas;
+        })(),
+        setStatus: function(text) {
+          if (!Module.setStatus.last) Module.setStatus.last = { time: Date.now(), text: '' };
+          if (text === Module.setStatus.last.text) return;
+          var now = Date.now();
+          Module.setStatus.last.time = now;
+          Module.setStatus.last.text = text;
+          statusElement.innerHTML = text;
+        },
+        totalDependencies: 0,
+        monitorRunDependencies: function(left) {
+          this.totalDependencies = Math.max(this.totalDependencies, left);
+          Module.setStatus(left ? 'Preparing... (' + (this.totalDependencies-left) + '/' + this.totalDependencies + ')' : 'All downloads complete.');
+        }
+      };
+      Module.setStatus('Downloading...');
+      window.onerror = function() {
+        Module.setStatus('Exception thrown, see JavaScript console');
+        Module.setStatus = function(text) {
+          if (text) console.error('[post-exception status] ' + text);
+        };
+      };
+    </script>
+    {{{ SCRIPT }}}
+  </body>
+</html>