To Top

Trail3D

Landscape Landscape2 Trail3D helps you find the first path from point A to point B, restricted by slopes and requiring solutions to be very close to the terrain.

Because Trail3D is a deterministic algorithm, is most useful when you need predictable and reproducible way to find a solution when conditions remain unchanged. No random behaviour may be advantageous.

Results are generally smooth with no jagged paths.

Results may not necessarily be the best path, but focuses on finding a solution.

Trail3D its not a terrain profiler, it's much more!

Landscape3

Trail3D is a path-finding algorithm for surfaces. It's a version of the renowned A* (A-star) graph traversal and path-finding algorithm but uses surface interpolations and slopes to decide the next node to move to. Results can later be used in an application. Trail3D does not modify the terrain to find a solution.

Use demo

Try it for free, no registration or credit card needed!

Demo with Babylon.js Recommend browser resolution: 1280 x 593 pixels

Instructions (quick version)

  1. Rotate image with mouse to find your desired view
  2. Pan with ctrl-key pressed and use mouse to find your desired view
  3. Select from top menu: Trail3D > new line
  4. Press the "From" button to select the starting point of the line directly on the surface
  5. Press the "To" button to select the ending point of line directly on the surface
  6. Input slope range as a percentaje
  7. Input intervals (10 is fine)
  8. Input epsilon (0.001 is fine)
  9. Select Cost Function (Euclidean, Manhattan, Chebyshev)
  10. Select surface approximation (Bilinear, Lagrange)
  11. Select algorithm (A-star is the only choice so far)
  12. Press Calculate
  13. Select from top menu: Window > Scene Explorer to display a hierarchical view of your scene
  14. Each line indicator contains the coordinates of the respective path and can be copied to clipboard

Demo description

This demo contains a surface on which Trail3D lines can be drawn.

Minumum hardware requirements: Win 8 with Chrome, intel Core i3, 4GB RAM.

Please share in the comments what hardware did you use.

Where did the demo map come from?

The surface is a digital terrain model of the Quetzaltenango region in Guatemala. The mesh is formed by square surface elements 100 meters wide. It covers an area 12 Km north-south and 17 Km east-west for a total of 212 square Km.

Story of Trail3D

A while back, I participated in a pre-feasibility study exploring geothermal energy for electric power generation. During a brainstorming session on the steam pipeline gathering system, I observed parallels with graph theory. Driven by curiosity, I examined the problem; however, I found that I had no tool for working with three-dimensional graphs. I was advised by the project director to explore Lagrange Finite elements for surface interpolation. This work later became my graduation project as a computer science engineer.

The geothermal study was delivered and I later switched jobs to other computer related areas. I didn't loose interest in the project, but daily responsibilities made it difficult to further develop the algorithm. It became an every now and then hobby project only.

Now that I am retired, I commited to the project.

So here it is! I hope you find it useful.

How was Trail3D build?

The Trail3D is a liberal interpretation and implementation of the renowned A* (A-star) graph traversal and pathfinding algorithm. It was implemented with Rust and uses WebAssembly to interface with Babylon.js for the front-end (UI).

Babylon.js is a JavaScript library and 3D engine for displaying real time 3D graphics in a web browser via HTML5.

Rust is a general-purpose programming language emphasizing performance, type safety, and concurrency.

WebAssembly is a binary instruction format for compiling and executing code in a client-side web browser.

Please take a moment to leave a comment, it will be very helpful: