UP | HOME

Path finding Visualizer

Table of Contents

1 Description

This is a OCaml script implementing, and visualizing the result and calculation of some path finding algorithms like Dijkstra's and A*. It also have different distance approximations and path optimizing methods.

2 News

  • 19 Aug 2010: v 1.1. Shows all tiles in cloud (not just the first 10).
  • 31 Jul 2010: Fixed Linux binary download link, added usage information.
  • 30 Jul 2010: Page creation.

3 Files

I couldn't figure out how to compile the OCaml Curses bindings on Windows, so no Windows binary.

4 Usage

  • Linux binary:
    • Must be run from a terminnal
    • chmod +x pathvisual
    • ./pathvisual
  • Compiling on Ubuntu
    • tar xzvf pathvisual_1.1.tar.gz
    • cd pathvisual
    • sudo apt-get install ocaml libcurses-ocaml libcurses-ocaml-dev (libcurses-ocaml is in universe)
    • make
    • ./pathvisual

5 Features

  • Cave-like territory, implemented from roguebasin.roguelikedevelopment.org
    • Also a slow implementation of a properly connected cave (several seconds to generate).
  • Path finding algorithms
  • Distance approximation
    • Proper Pythagorean
    • Approximation |x1 - x2| + |y1 - y2|
  • Path finding algorithm visualization
    • Show tiles being considered at each step.
  • Path optimizer, clean up/optimize a path.
    • Good.
    • Fast. After a path optimization, continue with path point after the optimized part.
  • Path optimizer visualization
    • Show each line-of-sight being considered and if it hits a wall.

6 Screenshots

This is a path generated using A*, with the optimal distance algorithm and no path optimization.

files/pathvisual1.png


This is the same as in the previous screenshot, but in the middle of a path finding visualization. The + are tiles already visited. 0 is the next tile to be considered (for A* this means the tile with the lowest ("cost from source" + "estimated distance to destination")), the other numbers are the next 9 tiles to be considered.

files/pathvisual2.png


This shows the A* Greedy path finding algorithm in the middle of a path optimization visualization. The O's are the points on the path being checked for possible optimization. The + is the line between the points. And the | is where a wall was found (meaning these 2 points can't be optimized).

files/pathvisual3.png

7 Why

I wanted to fool around with path finding but had a hard time getting the algorithms working or working fast enough. The solution was adding more and more debugging information, which finally resulted in a visualizer. Also, ML is fun.

8 Ocamldoc

9 Code

I put it all in one big file for no-ones convenience.

10 Comments

Date: 2014-01-26T19:22+0100

Author: Dan Amlund Thomsen

Org version 7.8.11 with Emacs version 24

Validate XHTML 1.0