Giter VIP home page Giter VIP logo

optimized-astart's Introduction

A-Search-with-Region-Cut-to-search-road-

A*算法结合区域分割搜索路径

用于weNavi的一个内置寻路算法,由于需要保证实时性,由于节点较多单纯的A*算法不能保证效率,所以做了如下优化

优化:在其中我把地图的像素点进行聚类,将同一区域内的点看做是一个chunk,来进行更大粒度的搜索

A算法核心回顾: A是一种启发式算法,BFS和Dijkstra都可以看做是A*算法的简化形式,这俩个算法在我其他的目录里也有实现。

A关键在于f(n) = g(n) + h(n)这公式中的启发函数h(n). 启发函数可以看做是一个指导老师,每次在搜寻下一个节点时来指导哪些 节点该被搜寻。典型的启发函数算法有曼哈顿距离(这份实现就是用的这个),切比雪夫距离等等。总体来说A算法应该是最好的寻路 思路了

optimized-astart's People

Contributors

youyue123 avatar

Stargazers

 avatar  avatar Kyle T avatar

Watchers

James Cloos avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.