Skip to content

Latest commit

 

History

History
110 lines (54 loc) · 3 KB

README.md

File metadata and controls

110 lines (54 loc) · 3 KB
Raw

A *


A * pathfinder algorithm experiments on a maze

  • it started as a solver of a (at the time being) preset maze
  • there was a random maze function added

As part of Hacktoberfest 2019:



  • @hangmansROP improved the style of the code by linting and code formatting
  • @Fayhen has added functionality to get a maze from Github Mazebot
  • @scavenger29 has added functionality to get the solved maze route from the algorithm transformed to the format Mazebot understands
  • @tusharck9 has added the functionality to return a solved maze to Mazebot

TLDR


maze & start & end points:


A* algorithm


In games we often want to find paths from one location to another. We’re not only trying to find the shortest distance; we also want to take into account travel time.

  • Breadth First Search explores equally in all directions. This is an incredibly useful algorithm, not only for regular path finding, but also for procedural map generation, flow field pathfinding, distance maps, and other types of map analysis.

  • Dijkstra’s Algorithm (also called Uniform Cost Search) lets us prioritize which paths to explore. Instead of exploring all possible paths equally, it favors lower cost paths. We can assign lower costs to encourage moving on roads, higher costs to avoid forests, higher costs to discourage going near enemies, and more. When movement costs vary, we use this instead of Breadth First Search.

  • A* is a modification of Dijkstra’s Algorithm that is optimized for a single destination. Dijkstra’s Algorithm can find paths to all locations; A* finds paths to one location. It prioritizes paths that seem to be leading closer to the goal.


TODO/DONE:


  • improve quality of code

    • lint / format code: DONE ✌️
    • modularise code a bit more (get solver on its own folder so as to import it etc)
    • modularise the visualization / animation part

  • create random maps with a function: DONE ✌️ 🎲🎲🎲

  • use other distance metrics in the algorithm?

  • integrate MAZEBOT API :

    • get a maze from the api DONE ✌️
    • solve the maze DONE ✌️ (this is what the algorithm does!)
    • function to return the solution through the API? DONE ✌️
    • function to transform the path the algorithm outputs to the EWSN (for east/west/south/north) the Mazebot expects so it can be sent DONE ✌️

  • use a graphics library to visualise everything in 3d: TODO 😱