Repository files navigation

W9-Pathfinding is a versatile pathfinding library written in C++ with a Python interface provided by Cython. It offers a variety of pathfinding algorithms for navigating different types of maps, including grids, graphs, and 3D spaces. The library includes both classic pathfinding algorithms and multi-agent pathfinding algorithms.

• Pathfinding Algorithms: Implements classical algorithms like BFS, Dijkstra, and A*, as well as multi-agent pathfinding algorithms like CBS and ICTS.
• Multiple Map Types: Works with different map structures, including Graphs (directed and undirected), Grids (4-connected and 8-connected), Hexagonal Grids (pointy top and flat top), and 3D Grids.
• Weighted and Unweighted Maps: Supports both weighted and non-weighted maps (graphs and grids).
• Pathfinding with Dynamic Obstacles: Allows pathfinding in environments where some agents are dynamic obstacles—you know their paths but cannot control them. It computes optimal paths for the remaining agents while avoiding collisions with both dynamic obstacles and each other.

The name w9-pathfinding comes from theweighted 9-connected grid you can use forpathfinding in the library. The "W" stands for Weighted, indicating that the library supports both weighted and non-weighted maps, where movement costs may vary. The "9" refers to the 9 possible movement directions: the 4 cardinal directions (North, South, East, West), the 4 diagonal directions (NE, SE, SW, NW), and a center movement (staying in place, which is crucial in multi-agent scenarios).

Pathfinding is the problem of finding the best route between two points.

This repository includes several pathfinding algorithms:

Example:

fromw9_pathfindingimportGraph,Dijkstragraph=Graph(num_vertices=4)graph.add_edges(    [        (0,1,1),# start, end, cost        (0,2,3),        (0,3,4),        (1,3,1),        (2,3,1),    ])dijkstra=Dijkstra(graph)path=dijkstra.find_path(start=0,goal=3)print(path)# [0, 1, 3]

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for a group of agents from their location to an assigned target.

Implemented algorithms:

Here optimality means that the algorithm can find the optimal solution in terms of Sum-of-costs function.

Example:

fromw9_pathfindingimportGrid,WHCAStargrid=Grid(# -1 - unwalkable cell# >= 0 - walkable, value is the cost of moving to this cellweights=[        [1,1,1,-1],        [-1,1,1,-1],        [1,1,-1,-1],        [1,1,1,1],    ],edge_collision=True,# head to head collisions are not allowed)whcastar=WHCAStar(grid)paths=whcastar.mapf(starts=[(0,0), (1,1)],goals=[(2,0), (1,0)])print(paths)# [[(0, 0), (1, 0), (2, 0)], [(1, 1), (1, 1), (1, 0)]]

To manage dynamic obstacles in pathfinding, a ReservationTable can be used. This data structure tracks the availability of each cell or edge over time, indicating whether it is free or reserved. In the case of the single-agent pathfinding problem with dynamic obstacles, there is a specialized version of the A* algorithm known as Space-Time A* (SpaceTimeAStar).

Let's look at a simple example. We have three agents: Agent 0, Agent 1, and Agent 2. Agent 0 has a predetermined path that we cannot change, this agent acts as a dynamic obstacle. Agents 1 and 2 each have a starting point and a destination, and we want to find paths for both agents while ensuring they do not collide with each other or with Agent 0. We can achieve this by calling Space-Time A* twice, updating the ReservationTable between the calls:

fromw9_pathfindingimportGrid,SpaceTimeAStar,ReservationTablegrid=Grid(width=5,height=4,edge_collision=True)grid.add_obstacle((1,1))# static obstaclepath0= [(0,1), (0,0), (1,0), (2,0), (3,0), (3,1)]# dynamic obstaclestart1,goal1= (0,2), (2,1)# agent 1start2,goal2= (0,0), (2,0)# agent 2rt=ReservationTable(grid)rt.add_path(path0,reserve_destination=True)astar=SpaceTimeAStar(grid)path1=astar.find_path(start1,goal1,reservation_table=rt)rt.add_path(path1,reserve_destination=True)path2=astar.find_path(start2,goal2,reservation_table=rt)print(path1)# [(0, 2), (1, 2), (2, 2), (2, 1)]print(path2)# [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (3, 0), (2, 0)]

This approach works quickly and often finds reasonably good solutions. However, in some cases, it may find solutions that are far from optimal or may not find a solution at all, when one agent prevents any path for another agent. An alternative approach is to use Multi-Agent Pathfinding (MAPF) algorithms, which allow us to find paths for both agents simultaneously. Since all MAPF algorithms in this repository are designed to work with the ReservationTable, we can find an optimal solution while taking dynamic obstacles into account:

fromw9_pathfindingimportCBSrt=ReservationTable(grid)rt.add_path(path0,reserve_destination=True)cbs=CBS(grid)paths=cbs.mapf([start1,start2], [goal1,goal2],reservation_table=rt)print(paths[0])# [(0, 2), (1, 2), (2, 2), (2, 2), (2, 1)]print(paths[1])# [(0, 0), (1, 0), (2, 0), (2, 1), (2, 0)]

There are several types of graphs available:

• Graph - Generic graph, directed or undirected
• Grid - Two-dimensional grid
• Grid3D - Three-dimensional grid
• HexGrid - Hexagonal grid

Any algorithm can work with any type of graph. But there are a few limitations:

1. Algorithms with a heuristic function (AStar, BiAStar, IDAStar, GBS) will work with generic graph only if coordinates are provided for each vertex. Coordinates can be added using theset_coordinates method.
2. An undirected generic graph does not supportedge_collision option. You still can use MAPF algorithms with this kind of graph, but it's impossible right now to mark head to head collisions as illegal actions.

Visualization is only available for Grid and HexGrid. To use visualization, you need to installmatplotlib.

Example:

fromw9_pathfindingimportHexGridfromw9_pathfinding.visualizationimportplot_grid,animate_gridgrid=HexGrid(weights=[        [1,1,1,-1],        [-1,1,1,-1],        [1,1,-1,-1],        [1,1,1,1],    ])agents= [    {'start': (0,0),'goal': (2,0),'path': [(0,0), (1,0), (2,0)]},    {'start': (1,1),'goal': (1,0),'path': [(1,1), (1,1), (1,0)]},]# plot_grid returns a static image useful in the pathfinding problemfig=plot_grid(grid,agents)# animate_grid returns an animation useful in the mapf problemanim=animate_grid(grid,agents)# HTML(anim.to_html5_video())  # visualize# anim.save("out.gif", fps=10, dpi=200)  # save as a gif

The easiest way to install w9-pathfinding is via pip:

pip install w9-pathfinding

Alternatively, you can install it manually:

1. Setup virtual environment (optional but recommended)

2. Install Cython:

   pip install cython

3. Build the Cython extensions:

   python setup.py build_ext --inplace

4. Finally, install the package:

   pip install -e.

Note: If you are on Linux, you might need to install some basic build tools to compile the Cython extensions:

sudo apt install --reinstall build-essential gcc g++

If you are on Windows, you might need to install MSVC.