astar-gridmap-2d

KO | EN

gitlite — search

#react #typescript #python #cpp #r #machine-learning #java #csharp #javascript #matlab #php #spark

astar-gridmap-2d

★ 65 Open GitHub ↗

A* algorithms for 2D gridmaps. The fastest one, until you prove me wrong

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# A* for 2D grids

This is an implementation of the A* path planning algorithm, specifically tailored for
2D grids.

It is inspired by other two open source implementations:

- [hjweide/a-star](https://github.com/hjweide/a-star)

Nevertheless, this implementation is 20% faster.

You might want to take a look to [astar-algorithm-cpp](https://github.com/justinhj/astar-algorithm-cpp),
but that implementation is more generic and it is not specifically optimized for 2D gridmaps.

To improve speed, the library uses a fairly large amount of RAM to perform many
operations in __O(1)__. The number of memory allocations is reduced to the very minimum.

It requires __at least__ 8 bytes for each cell in the grid, in other words,
more than 8 Mb of memory for a 1000x1000 gridmap.

## How fast is it?

Even if a fair amount of work was spent (mostly for fun) to optimize this software, it is still an A*
algorithm, that will be outperformed by other, more advanced, algorithms.

If you are looking for state-of-the-art path finders, you might be interested to www.movingai.com

This particularly implementation is efficient but also easy to read and understand.

## Usage

You must pass the image using the method __setWorldData()__.

Note that the the image data must be row-major and monochromatic.

A value of 0 (black) represents an obstacle, whilst 255 (white)
is a free cell.

```c++

// You don't need to use this image parser, you can use your own.   
    Image image;
    image.readFromPGM("./data/maze_big.pgm");

AStar::PathFinder generator;

generator.setWorldData( image.width(),
                            image.height(),
                            image.data() );
                
    AStar::Coord2D startPos (image.width()/2, 0);
    AStar::Coord2D targetPos(image.width()/2, image.height()/2 -1);
               
    auto path = generator.findPath(startPos, targetPos);

```

In the following example, the algorithm required about 200 milliseconds and 25 Mb
of RAM to find the solution in a 1586x1586 maze.

The pink pixels represent the cells of the grid visited by the algorithm.

![Large map](https://raw.githubusercontent.com/Eurecat/astar-gridmap-2d/master/map_out_big.png)

# License

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file 
except in compliance with the License. You may obtain a copy of the License at

[http://www.apache.org/licenses/LICENSE-2.0](http://www.apache.org/licenses/LICENSE-2.0)

Unless required by applicable law or agreed to in writing, software distributed under the 
License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, 
either express or implied. See the License for the specific language governing permissions
 and limitations under the License.
 
 # References
 
 [Introduction to A*](https://www.redblobgames.com/pathfinding/a-star/introduction.html)

astar-gridmap-2d

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README