Features - PatrikValkovic/pathvis GitHub Wiki

Library is still in development, so following section is just a draft of features, that we aim for in development proccess.

Algorithms

Library will be able to visualize basic path-finding algortihms. Library currently targets only one-to-n algortihms, that means path between two points (or possibly paths between point and all other points). Algorithms for finding shortest paths between all nodes are currently out of scope of this library.

Non-heuristic algortihms:

  • Random search
  • Breath-first search (BFS)
  • Depth-first search (DFS)
  • Dijkstra's algorithm

Heuristic algortihms:

  • Greedy search
  • A-star (A*)

For heuristic algortihms, following heuristics will be implemented:

  • euclidean
  • manhattan
  • chebyshev

Another algorithms, that can be implemented in the future:

  • Bellman-Ford algorithm (edges with negative values)
  • Floyd-Warshall algorithm (all-to-all path searching algorithm)
  • Any-angle path planning

Visualization

The proccesses of algorithms are visualized using Bloc graphic library.

Visualization will take place in two primary spaces. First is a grid space, where will be proccess of algorithm visualized by coloring of the cells. Second space is ordinary graph view (world-space), where proccess will be visualized by different color of edges and nodes. Possible realization is below. Each space have it's own renderer, that will be responsible for correct rendering of the space.

Island visualziation

Each algortihm can set its own own group of properties, that will be shown on nodes or edges. How the properties will be shown depends on the renderer used. For grid-space renderer, properties will be shown in the cells. For world-space renderer, properties will be shown after on hover over desired element.

Each algorithm will also have text output that describes what's happening in the algorithm and will inform user about workflow of the algorithm.

If you are planning to build your own renderer, or if you interesting of how it works under the hood, visir our wiki page Under the Hood.

Heuristic extensibility

For heuristic based algorithms, there will be way to extend application by new heuristics in standard manner.

Space building

Following section describes proccess of users creating their own spaces. Because our primary goal is to visualize proccess of algorithms, following features don't have to be part of the library.

Our target is to provide user with knowledge of how different algorithms works in different situations. Because we cannot cover all possible situations, we provide user with functionality for creating their own configuration of space.

Library itself can generate following configuration in grid-space:

  • Empty configuration without obstacles.
  • Random obstacles configuration, where will be few obstacles of different sizes.
  • Maze configuration, where library will generate maze with more possible paths.
  • Random throughput configuration, where each cell will have random value (weight).
  • Topographic configuration, where random cell will have height value (primary cells) and values of the rest cells will be smaller based on distance from the primary cells.

Library itself can generate following configuration in world-space:

  • Random positive configuration, where nodes will be placed randomly and weights of edges will be positive.
  • Random negative configuration, where nodes will be placed randomly and weights of edges can have negative value.

Library itself will have prepared configuration that will represent interesting situations (typically best-cases and worst-cases) for algorithms.

Each configuration can be edited by user and behaviour of algortihms is based on that configuration.

Import/Export

Library allows user to colaborate. Library provides functionality for exporting and importing of configuration. Library will have its own format of storing data.

Because this funcionallity is the least important, we will provide more information when the time comes.