derpzz / file-pathfinding Goto Github PK

This is a basic implementation of the dijkstra pathfinding algorithm that lets you create a file with components such as a start, an end and multiple ways. It will output a file similar to the input file only containing one of the shortest ways from start to end. Additionally in the console output you can find the coordinates (line and column) of the generated path. With this code it is also possible to run this algorithm in a char matrix. The open-source graph library by QUALiS-NRW can be found in the graph folder has been used and modified to represent the file internally as a graph. The authors and the documentation can be found directly in the graph files. https://www.schulentwicklung.nrw.de/lehrplaene/upload/klp_SII/if/MaterialZABI/2020-03-11_Implementationen_von_Klassen_fuer_das_Zentralabitur_ab_2018.zip

No HashMaps or PriorityQueues were used for this implementation to make it beginner-friendly and more accessible to early learners.

By default this character preset is used with all unsed characters treatet as empty:

• start of path: -
• end of path: +
• a way: x
• unsuable empty space:

This preset can easily be modified in the enum located in the position.java file

public enum Position{
    start('-'), way('x'), end('+'), empty(' ');

    private final char letter;

    private Position(char letter) {
        this.letter = letter;
    }

    public char getLetter(){
        return letter;
    }
}

Example of an input file:

-xxxxxxxxxxxxxxxxxxxxxxx
            xx         x
    xxxxxx  x          x
    xxxxx+  x          x
    x       x          x
    x       x          x
    x       x          x
    xxxxxxxxxxxxxxxxxxxx

Generated output file:

-xxxxxxxxxxxx
            x
            x
    xxxxx+  x
    x       x
    x       x
    x       x
    xxxxxxxxx

As you can see paths are not connected diagonally since the graph that is generated by the file only creates edges for characters that are directly next to each ohter. Multiple templates can be found named fileTest.txt.