# Vagabond
[Vagabond](https://pypi.org/project/py-vagabond/) is a powerful and flexible Python library designed to simplify the implementation of various pathfinding algorithms and related operations developed by [*Ranit Bhowmick*](https://www.linkedin.com/in/ranitbhowmick/) & [*Sayanti Chatterjee*](https://www.linkedin.com/in/sayantichatterjee/). Whether you're working on robotics, AI, or game development, Vagabond offers an easy-to-use interface for complex algorithms like A*, Dijkstra's, and more.
## Table of Contents
1. [Installation](#installation)
2. [Quick Start](#quick-start)
3. [Core Modules](#core-modules)
- [Node Class](#node-class)
- [A* Algorithm](#a-algorithm)
- [Dijkstra's Algorithm](#dijkstra-algorithm)
- [Breadth-First Search](#breadth-first-search)
- [Depth-First Search](#depth-first-search)
4. [Graph Visualization](#graph-visualization)
5. [Examples](#examples)
- [A* Pathfinding](#a-pathfinding-example)
- [Dijkstra's Pathfinding](#dijkstras-pathfinding-example)
- [Breadth-First Search](#breadth-first-search-example)
- [Depth-First Search](#depth-first-search-example)
## Installation
To install the Vagabond library, simply use pip:
```bash
pip install py-vagabond
```
## Quick Start
Here's a quick overview of how to use the library to perform A* pathfinding:
```python
import numpy as np
import matplotlib.pyplot as plt
from vagabond.systems import node
from vagabond.environmental import astar
import numpy as np
#example free space grids (1 is free, 0 is occupied)
free_space_grid = np.array([
[1, 0.8, 0.5, 0.5, 0.8],
[0.9, 0, 0, 0.8, 0.6],
[0, 0.8, 0.9, 0.9, 0.9],
[0.8, 0.9, 0, 0, 0.9],
[0.6, 0.5, 0.2, 0.2, 1]
])
# Assuming robot_cell is defined
robot_cell = (0, 0)
end_cell = (4, 4)
start_node = node(value=robot_cell, name="({}, {})".format(robot_cell[0], robot_cell[1]))
end_node = node(value=end_cell, name="({}, {})".format(end_cell[0], end_cell[1]))
# Generate a random end cell
map_height, map_width = free_space_grid.shape
#! A* functions ----------------------------------------------------
# if a cell is given, return the 4-connected neighbors
# probability high -----> cost low -----> high priority
def get_neighbors(parent_node):
neighbors = []
x, y = parent_node.value
# Check if the neighbor is within the map and is free
if x > 0 and free_space_grid[x - 1,y] != 0:
neighbors.append(node(value=(x - 1, y), parent=parent_node, cost=(cost(parent_node, (x - 1, y)))+heuristic((x - 1, y), end_cell), name="({}, {})".format(x - 1, y)))
if x < map_width - 1 and free_space_grid[x + 1,y] != 0:
neighbors.append(node(value=(x + 1, y), parent=parent_node, cost=(cost(parent_node, (x + 1, y)))+heuristic((x + 1, y), end_cell), name="({}, {})".format(x + 1, y)))
if y > 0 and free_space_grid[x, y - 1] != 0:
neighbors.append(node(value=(x, y - 1), parent=parent_node, cost=(cost(parent_node, (x, y - 1)))+heuristic((x, y - 1), end_cell), name="({}, {})".format(x, y - 1)))
if y < map_height - 1 and free_space_grid[x, y + 1] != 0:
neighbors.append(node(value=(x, y + 1), parent=parent_node, cost=(cost(parent_node, (x, y + 1)))+heuristic((x, y + 1), end_cell), name="({}, {})".format(x, y + 1)))
return neighbors
def cost(current_cell, neighbor):
if(current_cell.parent):
parent = current_cell.parent.value
else:
parent = current_cell.value
current = current_cell.value
#check if direction has not changed
direction1 = (parent[0] - current[0], parent[1] - current[1])
direction2 = (current[0] - neighbor[0], current[1] - neighbor[1])
if direction1 == direction2:
penalty = 0.1
else:
penalty = 0.5
return penalty + round(1 - free_space_grid[neighbor],2)
def heuristic(current_cell, end_cell):
return abs(current_cell[0] - end_cell[0]) + abs(current_cell[1] - end_cell[1])
#! A* algorithm ----------------------------------------------------
# Create an instance of the astar class
astar_obj = astar(get_neighbors)
# Find the path
path = astar_obj.path(start_node, end_node)
astar_obj.display_path(filename="astar_path")
print("Path: ", path)
#! Plot the path ----------------------------------------------------
plt.figure()
plt.imshow(free_space_grid, cmap='gray', origin='upper')
# Plot the path as a line
path = np.array(astar_obj.get_raw())
#plot simplified dots
plt.plot(path[:, 1], path[:, 0], 'r')
plt.scatter(robot_cell[1], robot_cell[0], color='r', marker='x')
plt.scatter(end_cell[1], end_cell[0], color='g', marker='x')
plt.show()
```
This example initializes a simple 5x5 grid with varying cost values and calculates the optimal path from the top-left corner to the bottom-right corner using the A* algorithm.
## Core Modules
### Node Class
The `node` class is the fundamental building block of the Vagabond library. It represents each cell in your grid and contains attributes like `value`, `parent`, `childs`, `cost`, and `name`.
**Initialization:**
```python
from vagabond.systems import node
n = node(value=(x, y), parent=None, cost=0.0, name="Node (x, y)")
```
**Attributes:**
- **value**: Tuple representing the coordinates of the node.
- **parent**: Reference to the parent node (used to track the path).
- **childs**: List of child nodes.
- **cost**: The cost to move to this node.
- **name**: A string representing the name of the node.
### A* Algorithm
The `astar` class implements the A* pathfinding algorithm, which is one of the most popular algorithms used in robotics and game development due to its efficiency and accuracy.
**Initialization:**
```python
from vagabond.environmental import astar
astar_obj = astar(get_neighbors)
```
**Key Functions:**
- `path(start_node, end_node)`: Calculates the optimal path between the start and end nodes.
- `display_path(filename)`: Displays the grid, obstacles, and the computed path using Graphviz.
- `get_raw()`: Returns the raw path as a list of nodes.
- `get()`: Returns the path as a list of nodes.
- `add(node)`: Adds a node to the path.
- `remove(node)`: Removes a node from the path.
- `clear()`: Clears the path.
**Usage:**
```python
path = astar_obj.path(start_node, end_node)
raw_path = astar_obj.get_raw()
```
### Dijkstra's Algorithm
The `dijkstra` class implements Dijkstra's pathfinding algorithm, which is ideal for finding the shortest path in graphs with non-negative weights.
**Initialization:**
```python
from vagabond.environmental import dijkstra
dijkstra_obj = dijkstra(get_neighbors)
```
**Key Functions:**
- `path(start_node, end_node)`: Identifies the shortest path between two nodes using Dijkstra's algorithm.
- `display_path(filename)`: Displays the grid, obstacles, and the computed path using Graphviz.
- `get_raw()`: Returns the raw path as a list of nodes.
- `get()`: Returns the path as a list of nodes.
- `add(node)`: Adds a node to the path.
- `remove(node)`: Removes a node from the path.
- `clear()`: Clears the path.
**Usage:**
```python
path = dijkstra_obj.path(start_node, end_node)
raw_path = dijkstra_obj.get_raw()
```
### Breadth-First Search
The `bfs` class implements the Breadth-First Search algorithm, which is useful for exploring all possible paths in a graph.
**Initialization:**
```python
from vagabond.environmental import bfs
bfs_obj = bfs(get_neighbors)
```
**Key Functions:**
- `path(start_node, end_node)`: Finds the shortest path between two nodes using BFS.
- `display_path(filename)`: Displays the grid, obstacles, and the computed path using Graphviz.
- `get_raw()`: Returns the raw path as a list of nodes.
- `get()`: Returns the path as a list of nodes.
- `add(node)`: Adds a node to the path.
- `remove(node)`: Removes a node from the path.
- `clear()`: Clears the path.
**Usage:**
```python
path = bfs_obj.path(start_node, end_node)
raw_path = bfs_obj.get_raw()
```
### Depth-First Search
The `dfs` class implements the Depth-First Search algorithm, which is useful for exploring all possible paths in a graph.
**Initialization:**
```python
from vagabond.environmental import dfs
dfs_obj = dfs(get_neighbors)
```
**Key Functions:**
- `path(start_node, end_node)`: Finds the shortest path between two nodes using DFS.
- `display_path(filename)`: Displays the grid, obstacles, and the computed path using Graphviz.
- `get_raw()`: Returns the raw path as a list of nodes.
- `get()`: Returns the path as a list of nodes.
- `add(node)`: Adds a node to the path.
- `remove(node)`: Removes a node from the path.
- `clear()`: Clears the path.
**Usage:**
```python
path = dfs_obj.path(start_node, end_node)
raw_path = dfs_obj.get_raw()
```
## Graph Visualization
Vagabond provides a convenient way to visualize your grid, obstacles, and computed paths using the Graphviz library.
**Display Path:**
```python
astar_obj.display_path(filename="astar_path")
```
This function generates a visualization of the grid, obstacles, and the computed path using Graphviz. The resulting image is saved as a PNG file with the specified filename.
It is also possible to display the grid and path using matplotlib:
```python
plt.figure()
plt.imshow(free_space_grid, cmap='gray', origin='upper')
# Plot the path as a line
path = np.array(astar_obj.get_raw())
#plot the path
plt.plot(path[:, 1], path[:, 0], 'r')
plt.scatter(robot_cell[1], robot_cell[0], color='r', marker='x')
plt.scatter(end_cell[1], end_cell[0], color='g', marker='x')
plt.show()
```
## Examples
### A* Pathfinding Example
This example demonstrates how to use the A* algorithm to find the optimal path in a grid with varying cost values.
```python
import numpy as np
import matplotlib.pyplot as plt
from vagabond.systems import node
from vagabond.environmental import astar
import numpy as np
#example free space grids (1 is free, 0 is occupied)
free_space_grid = np.array([
[1, 0.8, 0.5, 0.5, 0.8],
[0.9, 0, 0, 0.8, 0.6],
[0, 0.8, 0.9, 0.9, 0.9],
[0.8, 0.9, 0, 0, 0.9],
[0.6, 0.5, 0.2, 0.2, 1]
])
# Assuming robot_cell is defined
robot_cell = (0, 0)
end_cell = (4, 4)
start_node = node(value=robot_cell, name="({}, {})".format(robot_cell[0], robot_cell[1]))
end_node = node(value=end_cell, name="({}, {})".format(end_cell[0], end_cell[1]))
# Generate a random end cell
map_height, map_width = free_space_grid.shape
#! A* functions ----------------------------------------------------
# if a cell is given, return the 4-connected neighbors
# probability high -----> cost low -----> high priority
def get_neighbors(parent_node):
neighbors = []
x, y = parent_node.value
# Check if the neighbor is within the map and is free
if x > 0 and free_space_grid[x - 1,y] != 0:
neighbors.append(node(value=(x - 1, y), parent=parent_node, cost=(cost(parent_node, (x - 1, y)))+heuristic((x - 1, y), end_cell), name="({}, {})".format(x - 1, y)))
if x < map_width - 1 and free_space_grid[x + 1,y] != 0:
neighbors.append(node(value=(x + 1, y), parent=parent_node, cost=(cost(parent_node, (x + 1, y)))+heuristic((x + 1, y), end_cell), name="({}, {})".format(x + 1, y)))
if y > 0 and free_space_grid[x, y - 1] != 0:
neighbors.append(node(value=(x, y - 1), parent=parent_node, cost=(cost(parent_node, (x, y - 1)))+heuristic((x, y - 1), end_cell), name="({}, {})".format(x, y - 1)))
if y < map_height - 1 and free_space_grid[x, y + 1] != 0:
neighbors.append(node(value=(x, y + 1), parent=parent_node, cost=(cost(parent_node, (x, y + 1)))+heuristic((x, y + 1), end_cell), name="({}, {})".format(x, y + 1)))
return neighbors
def cost(current_cell, neighbor):
if(current_cell.parent):
parent = current_cell.parent.value
else:
parent = current_cell.value
current = current_cell.value
#check if direction has not changed
direction1 = (parent[0] - current[0], parent[1] - current[1])
direction2 = (current[0] - neighbor[0], current[1] - neighbor[1])
if direction1 == direction2:
penalty = 0.1
else:
penalty = 0.5
return penalty + round(1 - free_space_grid[neighbor],2)
def heuristic(current_cell, end_cell):
return abs(current_cell[0] - end_cell[0]) + abs(current_cell[1] - end_cell[1])
#! A* algorithm ----------------------------------------------------
# Create an instance of the astar class
astar_obj = astar(get_neighbors)
# Find the path
path = astar_obj.path(start_node, end_node)
astar_obj.display_path(filename="astar_path")
print("Path: ", path)
#! Plot the path ----------------------------------------------------
plt.figure()
plt.imshow(free_space_grid, cmap='gray', origin='upper')
# Plot the path as a line
path = np.array(astar_obj.get_raw())
plt.plot(path[:, 1], path[:, 0], 'r')
plt.scatter(robot_cell[1], robot_cell[0], color='r', marker='x')
plt.scatter(end_cell[1], end_cell[0], color='g', marker='x')
plt.show()
```
### Dijkstra's Pathfinding Example
This example demonstrates how to use Dijkstra's algorithm to find the shortest path in a grid with varying cost values.
```python
import numpy as np
import matplotlib.pyplot as plt
from vagabond.systems import node
from vagabond.environmental import dijkstra
import numpy as np
#example free space grids (1 is free, 0 is occupied)
free_space_grid = np.array([
[1, 0.8, 0.5, 0.5, 0.8],
[0.9, 0, 0, 0.8, 0.6],
[0, 0.8, 0.9, 0.9, 0.9],
[0.8, 0.9, 0, 0, 0.9],
[0.6, 0.5, 0.2, 0.2, 1]
])
# Assuming robot_cell is defined
robot_cell = (0, 0)
end_cell = (4, 4)
start_node = node(value=robot_cell, name="({}, {})".format(robot_cell[0], robot_cell[1]))
end_node = node(value=end_cell, name="({}, {})".format(end_cell[0], end_cell[1]))
# Generate a random end cell
map_height, map_width = free_space_grid.shape
#! A* functions ----------------------------------------------------
# if a cell is given, return the 4-connected neighbors
# probability high -----> cost low -----> high priority
def get_neighbors(parent_node):
neighbors = []
x, y = parent_node.value
# Check if the neighbor is within the map and is free
if x > 0 and free_space_grid[x - 1,y] != 0:
neighbors.append(node(value=(x - 1, y), parent=parent_node, cost=(cost(parent_node, (x - 1, y)))+heuristic((x - 1, y), end_cell), name="({}, {})".format(x - 1, y)))
if x < map_width - 1 and free_space_grid[x + 1,y] != 0:
neighbors.append(node(value=(x + 1, y), parent=parent_node, cost=(cost(parent_node, (x + 1, y)))+heuristic((x + 1, y), end_cell), name="({}, {})".format(x + 1, y)))
if y > 0 and free_space_grid[x, y - 1] != 0:
neighbors.append(node(value=(x, y - 1), parent=parent_node, cost=(cost(parent_node, (x, y - 1)))+heuristic((x, y - 1), end_cell), name="({}, {})".format(x, y - 1)))
if y < map_height - 1 and free_space_grid[x, y + 1] != 0:
neighbors.append(node(value=(x, y + 1), parent=parent_node, cost=(cost(parent_node, (x, y + 1)))+heuristic((x, y + 1), end_cell), name="({}, {})".format(x, y + 1)))
return neighbors
def cost(current_cell, neighbor):
if(current_cell.parent):
parent = current_cell.parent.value
else:
parent = current_cell.value
current = current_cell.value
#check if direction has not changed
direction1 = (parent[0] - current[0], parent[1] - current[1])
direction2 = (current[0] - neighbor[0], current[1] - neighbor[1])
if direction1 == direction2:
penalty = 0.1
else:
penalty = 0.5
return penalty + round(1 - free_space_grid[neighbor],2)
def heuristic(current_cell, end_cell):
return abs(current_cell[0] - end_cell[0]) + abs(current_cell[1] - end_cell[1])
#! A* algorithm ----------------------------------------------------
# Create an instance of the astar class
dijkstra_obj = dijkstra(get_neighbors)
# Find the path
path = dijkstra_obj.path(start_node, end_node)
dijkstra_obj.display_path(filename="dijkstra_path")
print("Path: ", path)
#! Plot the path ----------------------------------------------------
plt.figure()
plt.imshow(free_space_grid, cmap='gray', origin='upper')
# Plot the path as a line
path = np.array(dijkstra_obj.get_raw())
#plot simplified dots
plt.plot(path[:, 1], path[:, 0], 'r')
plt.scatter(robot_cell[1], robot_cell[0], color='r', marker='x')
plt.scatter(end_cell[1], end_cell[0], color='g', marker='x')
plt.show()
```
### Breadth-First Search Example
This example demonstrates how to use the Breadth-First Search algorithm to explore all possible paths in a grid.
```python
import numpy as np
import matplotlib.pyplot as plt
from vagabond.systems import node
from vagabond.environmental import bfs
import numpy as np
#example free space grids (1 is free, 0 is occupied)
free_space_grid = np.array([
[1, 0.8, 0.5, 0.5, 0.8],
[0.9, 0, 0, 0.8, 0.6],
[0, 0.8, 0.9, 0.9, 0.9],
[0.8, 0.9, 0, 0, 0.9],
[0.6, 0.5, 0.2, 0.2, 1]
])
# Assuming robot_cell is defined
robot_cell = (0, 0)
end_cell = (4, 4)
start_node = node(value=robot_cell, name="({}, {})".format(robot_cell[0], robot_cell[1]))
end_node = node(value=end_cell, name="({}, {})".format(end_cell[0], end_cell[1]))
# Generate a random end cell
map_height, map_width = free_space_grid.shape
#! A* functions ----------------------------------------------------
# if a cell is given, return the 4-connected neighbors
# probability high -----> cost low -----> high priority
def get_neighbors(parent_node):
neighbors = []
x, y = parent_node.value
# Check if the neighbor is within the map and is free
if x > 0 and free_space_grid[x - 1,y] != 0:
neighbors.append(node(value=(x - 1, y), parent=parent_node, cost=(cost(parent_node, (x - 1, y)))+heuristic((x - 1, y), end_cell), name="({}, {})".format(x - 1, y)))
if x < map_width - 1 and free_space_grid[x + 1,y] != 0:
neighbors.append(node(value=(x + 1, y), parent=parent_node, cost=(cost(parent_node, (x + 1, y)))+heuristic((x + 1, y), end_cell), name="({}, {})".format(x + 1, y)))
if y > 0 and free_space_grid[x, y - 1] != 0:
neighbors.append(node(value=(x, y - 1), parent=parent_node, cost=(cost(parent_node, (x, y - 1)))+heuristic((x, y - 1), end_cell), name="({}, {})".format(x, y - 1)))
if y < map_height - 1 and free_space_grid[x, y + 1] != 0:
neighbors.append(node(value=(x, y + 1), parent=parent_node, cost=(cost(parent_node, (x, y + 1)))+heuristic((x, y + 1), end_cell), name="({}, {})".format(x, y + 1)))
return neighbors
def cost(current_cell, neighbor):
if(current_cell.parent):
parent = current_cell.parent.value
else:
parent = current_cell.value
current = current_cell.value
#check if direction has not changed
direction1 = (parent[0] - current[0], parent[1] - current[1])
direction2 = (current[0] - neighbor[0], current[1] - neighbor[1])
if direction1 == direction2:
penalty = 0.1
else:
penalty = 0.5
return penalty + round(1 - free_space_grid[neighbor],2)
def heuristic(current_cell, end_cell):
return abs(current_cell[0] - end_cell[0]) + abs(current_cell[1] - end_cell[1])
#! A* algorithm ----------------------------------------------------
# Create an instance of the astar class
bfs_obj = bfs(get_neighbors)
# Find the path
path = bfs_obj.path(start_node, end_node)
bfs_obj.display_path(filename="bfs_path")
print("Path: ", path)
#! Plot the path ----------------------------------------------------
plt.figure()
plt.imshow(free_space_grid, cmap='gray', origin='upper')
# Plot the path as a line
path = np.array(bfs_obj.get_raw())
#plot simplified dots
plt.plot(path[:, 1], path[:, 0], 'r')
plt.scatter(robot_cell[1], robot_cell[0], color='r', marker='x')
plt.scatter(end_cell[1], end_cell[0], color='g', marker='x')
plt.show()
```
### Depth-First Search Example
This example demonstrates how to use the Depth-First Search algorithm to explore all possible paths in a grid.
```python
import numpy as np
import matplotlib.pyplot as plt
from vagabond.systems import node
from vagabond.environmental import dfs
import numpy as np
#example free space grids (1 is free, 0 is occupied)
free_space_grid = np.array([
[1, 0.8, 0.5, 0.5, 0.8],
[0.9, 0, 0, 0.8, 0.6],
[0, 0.8, 0.9, 0.9, 0.9],
[0.8, 0.9, 0, 0, 0.9],
[0.6, 0.5, 0.2, 0.2, 1]
])
# Assuming robot_cell is defined
robot_cell = (0, 0)
end_cell = (4, 4)
start_node = node(value=robot_cell, name="({}, {})".format(robot_cell[0], robot_cell[1]))
end_node = node(value=end_cell, name="({}, {})".format(end_cell[0], end_cell[1]))
# Generate a random end cell
map_height, map_width = free_space_grid.shape
#! A* functions ----------------------------------------------------
# if a cell is given, return the 4-connected neighbors
# probability high -----> cost low -----> high priority
def get_neighbors(parent_node):
neighbors = []
x, y = parent_node.value
# Check if the neighbor is within the map and is free
if x > 0 and free_space_grid[x - 1,y] != 0:
neighbors.append(node(value=(x - 1, y), parent=parent_node, cost=(cost(parent_node, (x - 1, y)))+heuristic((x - 1, y), end_cell), name="({}, {})".format(x - 1, y)))
if x < map_width - 1 and free_space_grid[x + 1,y] != 0:
neighbors.append(node(value=(x + 1, y), parent=parent_node, cost=(cost(parent_node, (x + 1, y)))+heuristic((x + 1, y), end_cell), name="({}, {})".format(x + 1, y)))
if y > 0 and free_space_grid[x, y - 1] != 0:
neighbors.append(node(value=(x, y - 1), parent=parent_node, cost=(cost(parent_node, (x, y - 1)))+heuristic((x, y - 1), end_cell), name="({}, {})".format(x, y - 1)))
if y < map_height - 1 and free_space_grid[x, y + 1] != 0:
neighbors.append(node(value=(x, y + 1), parent=parent_node, cost=(cost(parent_node, (x, y + 1)))+heuristic((x, y + 1), end_cell), name="({}, {})".format(x, y + 1)))
return neighbors
def cost(current_cell, neighbor):
if(current_cell.parent):
parent = current_cell.parent.value
else:
parent = current_cell.value
current = current_cell.value
#check if direction has not changed
direction1 = (parent[0] - current[0], parent[1] - current[1])
direction2 = (current[0] - neighbor[0], current[1] - neighbor[1])
if direction1 == direction2:
penalty = 0.1
else:
penalty = 0.5
return penalty + round(1 - free_space_grid[neighbor],2)
def heuristic(current_cell, end_cell):
return abs(current_cell[0] - end_cell[0]) + abs(current_cell[1] - end_cell[1])
#! A* algorithm ----------------------------------------------------
# Create an instance of the astar class
dfs_obj = dfs(get_neighbors)
# Find the path
path = dfs_obj.path(start_node, end_node)
dfs_obj.display_path(filename="dfs_path")
print("Path: ", path)
#! Plot the path ----------------------------------------------------
plt.figure()
plt.imshow(free_space_grid, cmap='gray', origin='upper')
# Plot the path as a line
path = np.array(dfs_obj.get_raw())
#plot simplified dots
plt.plot(path[:, 1], path[:, 0], 'r')
plt.scatter(robot_cell[1], robot_cell[0], color='r', marker='x')
plt.scatter(end_cell[1], end_cell[0], color='g', marker='x')
plt.show()
```
Raw data
{
"_id": null,
"home_page": "https://github.com/Kawai-Senpai/Vagabond",
"name": "py-vagabond",
"maintainer": null,
"docs_url": null,
"requires_python": null,
"maintainer_email": null,
"keywords": "Pathfinding, Robotics, Navigation, A* Algorithm, Graph Theory, Automation, Robotic Systems",
"author": "Ranit Bhowmick",
"author_email": "bhowmickranitking@duck.com",
"download_url": "https://files.pythonhosted.org/packages/04/7e/aec336259151394fa862a1846f983843b2c79990c50c1721fa210a33a22a/py-vagabond-2.0.2.tar.gz",
"platform": null,
"description": "# Vagabond\r\n\r\n[Vagabond](https://pypi.org/project/py-vagabond/) is a powerful and flexible Python library designed to simplify the implementation of various pathfinding algorithms and related operations developed by [*Ranit Bhowmick*](https://www.linkedin.com/in/ranitbhowmick/) & [*Sayanti Chatterjee*](https://www.linkedin.com/in/sayantichatterjee/). Whether you're working on robotics, AI, or game development, Vagabond offers an easy-to-use interface for complex algorithms like A*, Dijkstra's, and more.\r\n\r\n## Table of Contents\r\n\r\n1. [Installation](#installation)\r\n2. [Quick Start](#quick-start)\r\n3. [Core Modules](#core-modules)\r\n - [Node Class](#node-class)\r\n - [A* Algorithm](#a-algorithm)\r\n - [Dijkstra's Algorithm](#dijkstra-algorithm)\r\n - [Breadth-First Search](#breadth-first-search)\r\n - [Depth-First Search](#depth-first-search)\r\n4. [Graph Visualization](#graph-visualization)\r\n5. [Examples](#examples)\r\n - [A* Pathfinding](#a-pathfinding-example)\r\n - [Dijkstra's Pathfinding](#dijkstras-pathfinding-example)\r\n - [Breadth-First Search](#breadth-first-search-example)\r\n - [Depth-First Search](#depth-first-search-example)\r\n\r\n## Installation\r\n\r\nTo install the Vagabond library, simply use pip:\r\n\r\n```bash\r\npip install py-vagabond\r\n```\r\n\r\n## Quick Start\r\n\r\nHere's a quick overview of how to use the library to perform A* pathfinding:\r\n\r\n```python\r\nimport numpy as np\r\nimport matplotlib.pyplot as plt\r\nfrom vagabond.systems import node\r\nfrom vagabond.environmental import astar\r\nimport numpy as np\r\n\r\n#example free space grids (1 is free, 0 is occupied)\r\nfree_space_grid = np.array([\r\n [1, 0.8, 0.5, 0.5, 0.8],\r\n [0.9, 0, 0, 0.8, 0.6],\r\n [0, 0.8, 0.9, 0.9, 0.9],\r\n [0.8, 0.9, 0, 0, 0.9],\r\n [0.6, 0.5, 0.2, 0.2, 1]\r\n])\r\n\r\n# Assuming robot_cell is defined\r\nrobot_cell = (0, 0)\r\nend_cell = (4, 4)\r\n\r\nstart_node = node(value=robot_cell, name=\"({}, {})\".format(robot_cell[0], robot_cell[1]))\r\nend_node = node(value=end_cell, name=\"({}, {})\".format(end_cell[0], end_cell[1]))\r\n\r\n# Generate a random end cell\r\nmap_height, map_width = free_space_grid.shape\r\n\r\n#! A* functions ----------------------------------------------------\r\n\r\n# if a cell is given, return the 4-connected neighbors\r\n# probability high -----> cost low -----> high priority\r\ndef get_neighbors(parent_node):\r\n\r\n neighbors = []\r\n x, y = parent_node.value\r\n\r\n # Check if the neighbor is within the map and is free\r\n if x > 0 and free_space_grid[x - 1,y] != 0:\r\n neighbors.append(node(value=(x - 1, y), parent=parent_node, cost=(cost(parent_node, (x - 1, y)))+heuristic((x - 1, y), end_cell), name=\"({}, {})\".format(x - 1, y)))\r\n if x < map_width - 1 and free_space_grid[x + 1,y] != 0: \r\n neighbors.append(node(value=(x + 1, y), parent=parent_node, cost=(cost(parent_node, (x + 1, y)))+heuristic((x + 1, y), end_cell), name=\"({}, {})\".format(x + 1, y)))\r\n if y > 0 and free_space_grid[x, y - 1] != 0:\r\n neighbors.append(node(value=(x, y - 1), parent=parent_node, cost=(cost(parent_node, (x, y - 1)))+heuristic((x, y - 1), end_cell), name=\"({}, {})\".format(x, y - 1)))\r\n if y < map_height - 1 and free_space_grid[x, y + 1] != 0:\r\n neighbors.append(node(value=(x, y + 1), parent=parent_node, cost=(cost(parent_node, (x, y + 1)))+heuristic((x, y + 1), end_cell), name=\"({}, {})\".format(x, y + 1)))\r\n\r\n return neighbors\r\n\r\ndef cost(current_cell, neighbor):\r\n\r\n if(current_cell.parent):\r\n parent = current_cell.parent.value\r\n else:\r\n parent = current_cell.value\r\n\r\n current = current_cell.value\r\n\r\n #check if direction has not changed\r\n direction1 = (parent[0] - current[0], parent[1] - current[1])\r\n direction2 = (current[0] - neighbor[0], current[1] - neighbor[1])\r\n\r\n if direction1 == direction2:\r\n penalty = 0.1\r\n else:\r\n penalty = 0.5\r\n\r\n return penalty + round(1 - free_space_grid[neighbor],2)\r\n\r\ndef heuristic(current_cell, end_cell):\r\n return abs(current_cell[0] - end_cell[0]) + abs(current_cell[1] - end_cell[1])\r\n\r\n#! A* algorithm ----------------------------------------------------\r\n\r\n# Create an instance of the astar class\r\nastar_obj = astar(get_neighbors)\r\n\r\n# Find the path\r\npath = astar_obj.path(start_node, end_node)\r\nastar_obj.display_path(filename=\"astar_path\")\r\nprint(\"Path: \", path)\r\n\r\n#! Plot the path ----------------------------------------------------\r\n\r\nplt.figure()\r\nplt.imshow(free_space_grid, cmap='gray', origin='upper')\r\n\r\n# Plot the path as a line\r\npath = np.array(astar_obj.get_raw())\r\n\r\n#plot simplified dots\r\nplt.plot(path[:, 1], path[:, 0], 'r')\r\nplt.scatter(robot_cell[1], robot_cell[0], color='r', marker='x')\r\nplt.scatter(end_cell[1], end_cell[0], color='g', marker='x')\r\nplt.show()\r\n```\r\n\r\nThis example initializes a simple 5x5 grid with varying cost values and calculates the optimal path from the top-left corner to the bottom-right corner using the A* algorithm.\r\n\r\n## Core Modules\r\n\r\n### Node Class\r\n\r\nThe `node` class is the fundamental building block of the Vagabond library. It represents each cell in your grid and contains attributes like `value`, `parent`, `childs`, `cost`, and `name`.\r\n\r\n**Initialization:**\r\n\r\n```python\r\nfrom vagabond.systems import node\r\n\r\nn = node(value=(x, y), parent=None, cost=0.0, name=\"Node (x, y)\")\r\n```\r\n\r\n**Attributes:**\r\n\r\n- **value**: Tuple representing the coordinates of the node.\r\n- **parent**: Reference to the parent node (used to track the path).\r\n- **childs**: List of child nodes.\r\n- **cost**: The cost to move to this node.\r\n- **name**: A string representing the name of the node.\r\n\r\n### A* Algorithm\r\n\r\nThe `astar` class implements the A* pathfinding algorithm, which is one of the most popular algorithms used in robotics and game development due to its efficiency and accuracy.\r\n\r\n**Initialization:**\r\n\r\n```python\r\nfrom vagabond.environmental import astar\r\n\r\nastar_obj = astar(get_neighbors)\r\n```\r\n\r\n**Key Functions:**\r\n\r\n- `path(start_node, end_node)`: Calculates the optimal path between the start and end nodes.\r\n- `display_path(filename)`: Displays the grid, obstacles, and the computed path using Graphviz.\r\n- `get_raw()`: Returns the raw path as a list of nodes.\r\n- `get()`: Returns the path as a list of nodes.\r\n- `add(node)`: Adds a node to the path.\r\n- `remove(node)`: Removes a node from the path.\r\n- `clear()`: Clears the path.\r\n\r\n**Usage:**\r\n\r\n```python\r\npath = astar_obj.path(start_node, end_node)\r\nraw_path = astar_obj.get_raw()\r\n```\r\n\r\n### Dijkstra's Algorithm\r\n\r\nThe `dijkstra` class implements Dijkstra's pathfinding algorithm, which is ideal for finding the shortest path in graphs with non-negative weights.\r\n\r\n**Initialization:**\r\n\r\n```python\r\nfrom vagabond.environmental import dijkstra\r\n\r\ndijkstra_obj = dijkstra(get_neighbors)\r\n```\r\n\r\n**Key Functions:**\r\n\r\n- `path(start_node, end_node)`: Identifies the shortest path between two nodes using Dijkstra's algorithm.\r\n- `display_path(filename)`: Displays the grid, obstacles, and the computed path using Graphviz.\r\n- `get_raw()`: Returns the raw path as a list of nodes.\r\n- `get()`: Returns the path as a list of nodes.\r\n- `add(node)`: Adds a node to the path.\r\n- `remove(node)`: Removes a node from the path.\r\n- `clear()`: Clears the path.\r\n\r\n**Usage:**\r\n\r\n```python\r\npath = dijkstra_obj.path(start_node, end_node)\r\nraw_path = dijkstra_obj.get_raw()\r\n```\r\n\r\n### Breadth-First Search\r\n\r\nThe `bfs` class implements the Breadth-First Search algorithm, which is useful for exploring all possible paths in a graph.\r\n\r\n**Initialization:**\r\n\r\n```python\r\nfrom vagabond.environmental import bfs\r\n\r\nbfs_obj = bfs(get_neighbors)\r\n```\r\n\r\n**Key Functions:**\r\n\r\n- `path(start_node, end_node)`: Finds the shortest path between two nodes using BFS.\r\n- `display_path(filename)`: Displays the grid, obstacles, and the computed path using Graphviz.\r\n- `get_raw()`: Returns the raw path as a list of nodes.\r\n- `get()`: Returns the path as a list of nodes.\r\n- `add(node)`: Adds a node to the path.\r\n- `remove(node)`: Removes a node from the path.\r\n- `clear()`: Clears the path.\r\n\r\n**Usage:**\r\n\r\n```python\r\npath = bfs_obj.path(start_node, end_node)\r\nraw_path = bfs_obj.get_raw()\r\n```\r\n\r\n### Depth-First Search\r\n\r\nThe `dfs` class implements the Depth-First Search algorithm, which is useful for exploring all possible paths in a graph.\r\n\r\n**Initialization:**\r\n\r\n```python\r\nfrom vagabond.environmental import dfs\r\n\r\ndfs_obj = dfs(get_neighbors)\r\n```\r\n\r\n**Key Functions:**\r\n\r\n- `path(start_node, end_node)`: Finds the shortest path between two nodes using DFS.\r\n- `display_path(filename)`: Displays the grid, obstacles, and the computed path using Graphviz.\r\n- `get_raw()`: Returns the raw path as a list of nodes.\r\n- `get()`: Returns the path as a list of nodes.\r\n- `add(node)`: Adds a node to the path.\r\n- `remove(node)`: Removes a node from the path.\r\n- `clear()`: Clears the path.\r\n\r\n**Usage:**\r\n\r\n```python\r\n\r\npath = dfs_obj.path(start_node, end_node)\r\nraw_path = dfs_obj.get_raw()\r\n```\r\n\r\n## Graph Visualization\r\n\r\nVagabond provides a convenient way to visualize your grid, obstacles, and computed paths using the Graphviz library.\r\n\r\n**Display Path:**\r\n\r\n```python\r\nastar_obj.display_path(filename=\"astar_path\")\r\n```\r\n\r\nThis function generates a visualization of the grid, obstacles, and the computed path using Graphviz. The resulting image is saved as a PNG file with the specified filename.\r\n\r\n\r\n\r\nIt is also possible to display the grid and path using matplotlib:\r\n\r\n```python\r\nplt.figure()\r\nplt.imshow(free_space_grid, cmap='gray', origin='upper')\r\n\r\n# Plot the path as a line\r\npath = np.array(astar_obj.get_raw())\r\n\r\n#plot the path\r\nplt.plot(path[:, 1], path[:, 0], 'r')\r\nplt.scatter(robot_cell[1], robot_cell[0], color='r', marker='x')\r\nplt.scatter(end_cell[1], end_cell[0], color='g', marker='x')\r\nplt.show()\r\n```\r\n\r\n## Examples\r\n\r\n### A* Pathfinding Example\r\n\r\nThis example demonstrates how to use the A* algorithm to find the optimal path in a grid with varying cost values.\r\n\r\n```python\r\nimport numpy as np\r\nimport matplotlib.pyplot as plt\r\nfrom vagabond.systems import node\r\nfrom vagabond.environmental import astar\r\nimport numpy as np\r\n\r\n#example free space grids (1 is free, 0 is occupied)\r\nfree_space_grid = np.array([\r\n [1, 0.8, 0.5, 0.5, 0.8],\r\n [0.9, 0, 0, 0.8, 0.6],\r\n [0, 0.8, 0.9, 0.9, 0.9],\r\n [0.8, 0.9, 0, 0, 0.9],\r\n [0.6, 0.5, 0.2, 0.2, 1]\r\n])\r\n\r\n# Assuming robot_cell is defined\r\nrobot_cell = (0, 0)\r\nend_cell = (4, 4)\r\n\r\nstart_node = node(value=robot_cell, name=\"({}, {})\".format(robot_cell[0], robot_cell[1]))\r\nend_node = node(value=end_cell, name=\"({}, {})\".format(end_cell[0], end_cell[1]))\r\n\r\n# Generate a random end cell\r\nmap_height, map_width = free_space_grid.shape\r\n\r\n#! A* functions ----------------------------------------------------\r\n\r\n# if a cell is given, return the 4-connected neighbors\r\n# probability high -----> cost low -----> high priority\r\ndef get_neighbors(parent_node):\r\n\r\n neighbors = []\r\n x, y = parent_node.value\r\n\r\n # Check if the neighbor is within the map and is free\r\n if x > 0 and free_space_grid[x - 1,y] != 0:\r\n neighbors.append(node(value=(x - 1, y), parent=parent_node, cost=(cost(parent_node, (x - 1, y)))+heuristic((x - 1, y), end_cell), name=\"({}, {})\".format(x - 1, y)))\r\n if x < map_width - 1 and free_space_grid[x + 1,y] != 0: \r\n neighbors.append(node(value=(x + 1, y), parent=parent_node, cost=(cost(parent_node, (x + 1, y)))+heuristic((x + 1, y), end_cell), name=\"({}, {})\".format(x + 1, y)))\r\n if y > 0 and free_space_grid[x, y - 1] != 0:\r\n neighbors.append(node(value=(x, y - 1), parent=parent_node, cost=(cost(parent_node, (x, y - 1)))+heuristic((x, y - 1), end_cell), name=\"({}, {})\".format(x, y - 1)))\r\n if y < map_height - 1 and free_space_grid[x, y + 1] != 0:\r\n neighbors.append(node(value=(x, y + 1), parent=parent_node, cost=(cost(parent_node, (x, y + 1)))+heuristic((x, y + 1), end_cell), name=\"({}, {})\".format(x, y + 1)))\r\n\r\n return neighbors\r\n\r\ndef cost(current_cell, neighbor):\r\n\r\n if(current_cell.parent):\r\n parent = current_cell.parent.value\r\n else:\r\n parent = current_cell.value\r\n\r\n current = current_cell.value\r\n\r\n #check if direction has not changed\r\n direction1 = (parent[0] - current[0], parent[1] - current[1])\r\n direction2 = (current[0] - neighbor[0], current[1] - neighbor[1])\r\n\r\n if direction1 == direction2:\r\n penalty = 0.1\r\n else:\r\n penalty = 0.5\r\n\r\n return penalty + round(1 - free_space_grid[neighbor],2)\r\n\r\ndef heuristic(current_cell, end_cell):\r\n return abs(current_cell[0] - end_cell[0]) + abs(current_cell[1] - end_cell[1])\r\n\r\n#! A* algorithm ----------------------------------------------------\r\n\r\n# Create an instance of the astar class\r\nastar_obj = astar(get_neighbors)\r\n\r\n# Find the path\r\npath = astar_obj.path(start_node, end_node)\r\nastar_obj.display_path(filename=\"astar_path\")\r\nprint(\"Path: \", path)\r\n\r\n#! Plot the path ----------------------------------------------------\r\n\r\nplt.figure()\r\nplt.imshow(free_space_grid, cmap='gray', origin='upper')\r\n\r\n# Plot the path as a line\r\npath = np.array(astar_obj.get_raw())\r\n\r\nplt.plot(path[:, 1], path[:, 0], 'r')\r\nplt.scatter(robot_cell[1], robot_cell[0], color='r', marker='x')\r\nplt.scatter(end_cell[1], end_cell[0], color='g', marker='x')\r\nplt.show()\r\n\r\n```\r\n\r\n### Dijkstra's Pathfinding Example\r\n\r\nThis example demonstrates how to use Dijkstra's algorithm to find the shortest path in a grid with varying cost values.\r\n\r\n```python\r\nimport numpy as np\r\nimport matplotlib.pyplot as plt\r\nfrom vagabond.systems import node\r\nfrom vagabond.environmental import dijkstra\r\nimport numpy as np\r\n\r\n#example free space grids (1 is free, 0 is occupied)\r\nfree_space_grid = np.array([\r\n [1, 0.8, 0.5, 0.5, 0.8],\r\n [0.9, 0, 0, 0.8, 0.6],\r\n [0, 0.8, 0.9, 0.9, 0.9],\r\n [0.8, 0.9, 0, 0, 0.9],\r\n [0.6, 0.5, 0.2, 0.2, 1]\r\n])\r\n\r\n# Assuming robot_cell is defined\r\nrobot_cell = (0, 0)\r\nend_cell = (4, 4)\r\n\r\nstart_node = node(value=robot_cell, name=\"({}, {})\".format(robot_cell[0], robot_cell[1]))\r\nend_node = node(value=end_cell, name=\"({}, {})\".format(end_cell[0], end_cell[1]))\r\n\r\n# Generate a random end cell\r\nmap_height, map_width = free_space_grid.shape\r\n\r\n#! A* functions ----------------------------------------------------\r\n\r\n# if a cell is given, return the 4-connected neighbors\r\n# probability high -----> cost low -----> high priority\r\ndef get_neighbors(parent_node):\r\n\r\n neighbors = []\r\n x, y = parent_node.value\r\n\r\n # Check if the neighbor is within the map and is free\r\n if x > 0 and free_space_grid[x - 1,y] != 0:\r\n neighbors.append(node(value=(x - 1, y), parent=parent_node, cost=(cost(parent_node, (x - 1, y)))+heuristic((x - 1, y), end_cell), name=\"({}, {})\".format(x - 1, y)))\r\n if x < map_width - 1 and free_space_grid[x + 1,y] != 0: \r\n neighbors.append(node(value=(x + 1, y), parent=parent_node, cost=(cost(parent_node, (x + 1, y)))+heuristic((x + 1, y), end_cell), name=\"({}, {})\".format(x + 1, y)))\r\n if y > 0 and free_space_grid[x, y - 1] != 0:\r\n neighbors.append(node(value=(x, y - 1), parent=parent_node, cost=(cost(parent_node, (x, y - 1)))+heuristic((x, y - 1), end_cell), name=\"({}, {})\".format(x, y - 1)))\r\n if y < map_height - 1 and free_space_grid[x, y + 1] != 0:\r\n neighbors.append(node(value=(x, y + 1), parent=parent_node, cost=(cost(parent_node, (x, y + 1)))+heuristic((x, y + 1), end_cell), name=\"({}, {})\".format(x, y + 1)))\r\n\r\n return neighbors\r\n\r\ndef cost(current_cell, neighbor):\r\n\r\n if(current_cell.parent):\r\n parent = current_cell.parent.value\r\n else:\r\n parent = current_cell.value\r\n\r\n current = current_cell.value\r\n\r\n #check if direction has not changed\r\n direction1 = (parent[0] - current[0], parent[1] - current[1])\r\n direction2 = (current[0] - neighbor[0], current[1] - neighbor[1])\r\n\r\n if direction1 == direction2:\r\n penalty = 0.1\r\n else:\r\n penalty = 0.5\r\n\r\n return penalty + round(1 - free_space_grid[neighbor],2)\r\n\r\ndef heuristic(current_cell, end_cell):\r\n return abs(current_cell[0] - end_cell[0]) + abs(current_cell[1] - end_cell[1])\r\n\r\n#! A* algorithm ----------------------------------------------------\r\n\r\n# Create an instance of the astar class\r\ndijkstra_obj = dijkstra(get_neighbors)\r\n\r\n# Find the path\r\npath = dijkstra_obj.path(start_node, end_node)\r\ndijkstra_obj.display_path(filename=\"dijkstra_path\")\r\nprint(\"Path: \", path)\r\n\r\n#! Plot the path ----------------------------------------------------\r\n\r\nplt.figure()\r\nplt.imshow(free_space_grid, cmap='gray', origin='upper')\r\n\r\n# Plot the path as a line\r\npath = np.array(dijkstra_obj.get_raw())\r\n\r\n#plot simplified dots\r\nplt.plot(path[:, 1], path[:, 0], 'r')\r\nplt.scatter(robot_cell[1], robot_cell[0], color='r', marker='x')\r\nplt.scatter(end_cell[1], end_cell[0], color='g', marker='x')\r\nplt.show()\r\n\r\n```\r\n\r\n### Breadth-First Search Example\r\n\r\nThis example demonstrates how to use the Breadth-First Search algorithm to explore all possible paths in a grid.\r\n\r\n```python\r\nimport numpy as np\r\nimport matplotlib.pyplot as plt\r\nfrom vagabond.systems import node\r\nfrom vagabond.environmental import bfs\r\nimport numpy as np\r\n\r\n#example free space grids (1 is free, 0 is occupied)\r\nfree_space_grid = np.array([\r\n [1, 0.8, 0.5, 0.5, 0.8],\r\n [0.9, 0, 0, 0.8, 0.6],\r\n [0, 0.8, 0.9, 0.9, 0.9],\r\n [0.8, 0.9, 0, 0, 0.9],\r\n [0.6, 0.5, 0.2, 0.2, 1]\r\n])\r\n\r\n# Assuming robot_cell is defined\r\nrobot_cell = (0, 0)\r\nend_cell = (4, 4)\r\n\r\nstart_node = node(value=robot_cell, name=\"({}, {})\".format(robot_cell[0], robot_cell[1]))\r\nend_node = node(value=end_cell, name=\"({}, {})\".format(end_cell[0], end_cell[1]))\r\n\r\n# Generate a random end cell\r\nmap_height, map_width = free_space_grid.shape\r\n\r\n#! A* functions ----------------------------------------------------\r\n\r\n# if a cell is given, return the 4-connected neighbors\r\n# probability high -----> cost low -----> high priority\r\ndef get_neighbors(parent_node):\r\n\r\n neighbors = []\r\n x, y = parent_node.value\r\n\r\n # Check if the neighbor is within the map and is free\r\n if x > 0 and free_space_grid[x - 1,y] != 0:\r\n neighbors.append(node(value=(x - 1, y), parent=parent_node, cost=(cost(parent_node, (x - 1, y)))+heuristic((x - 1, y), end_cell), name=\"({}, {})\".format(x - 1, y)))\r\n if x < map_width - 1 and free_space_grid[x + 1,y] != 0: \r\n neighbors.append(node(value=(x + 1, y), parent=parent_node, cost=(cost(parent_node, (x + 1, y)))+heuristic((x + 1, y), end_cell), name=\"({}, {})\".format(x + 1, y)))\r\n if y > 0 and free_space_grid[x, y - 1] != 0:\r\n neighbors.append(node(value=(x, y - 1), parent=parent_node, cost=(cost(parent_node, (x, y - 1)))+heuristic((x, y - 1), end_cell), name=\"({}, {})\".format(x, y - 1)))\r\n if y < map_height - 1 and free_space_grid[x, y + 1] != 0:\r\n neighbors.append(node(value=(x, y + 1), parent=parent_node, cost=(cost(parent_node, (x, y + 1)))+heuristic((x, y + 1), end_cell), name=\"({}, {})\".format(x, y + 1)))\r\n\r\n return neighbors\r\n\r\ndef cost(current_cell, neighbor):\r\n\r\n if(current_cell.parent):\r\n parent = current_cell.parent.value\r\n else:\r\n parent = current_cell.value\r\n\r\n current = current_cell.value\r\n\r\n #check if direction has not changed\r\n direction1 = (parent[0] - current[0], parent[1] - current[1])\r\n direction2 = (current[0] - neighbor[0], current[1] - neighbor[1])\r\n\r\n if direction1 == direction2:\r\n penalty = 0.1\r\n else:\r\n penalty = 0.5\r\n\r\n return penalty + round(1 - free_space_grid[neighbor],2)\r\n\r\ndef heuristic(current_cell, end_cell):\r\n return abs(current_cell[0] - end_cell[0]) + abs(current_cell[1] - end_cell[1])\r\n\r\n#! A* algorithm ----------------------------------------------------\r\n\r\n# Create an instance of the astar class\r\nbfs_obj = bfs(get_neighbors)\r\n\r\n# Find the path\r\npath = bfs_obj.path(start_node, end_node)\r\nbfs_obj.display_path(filename=\"bfs_path\")\r\nprint(\"Path: \", path)\r\n\r\n#! Plot the path ----------------------------------------------------\r\n\r\nplt.figure()\r\nplt.imshow(free_space_grid, cmap='gray', origin='upper')\r\n\r\n# Plot the path as a line\r\npath = np.array(bfs_obj.get_raw())\r\n\r\n#plot simplified dots\r\nplt.plot(path[:, 1], path[:, 0], 'r')\r\nplt.scatter(robot_cell[1], robot_cell[0], color='r', marker='x')\r\nplt.scatter(end_cell[1], end_cell[0], color='g', marker='x')\r\nplt.show()\r\n\r\n```\r\n\r\n### Depth-First Search Example\r\n\r\nThis example demonstrates how to use the Depth-First Search algorithm to explore all possible paths in a grid.\r\n\r\n```python\r\nimport numpy as np\r\nimport matplotlib.pyplot as plt\r\nfrom vagabond.systems import node\r\nfrom vagabond.environmental import dfs\r\nimport numpy as np\r\n\r\n#example free space grids (1 is free, 0 is occupied)\r\nfree_space_grid = np.array([\r\n [1, 0.8, 0.5, 0.5, 0.8],\r\n [0.9, 0, 0, 0.8, 0.6],\r\n [0, 0.8, 0.9, 0.9, 0.9],\r\n [0.8, 0.9, 0, 0, 0.9],\r\n [0.6, 0.5, 0.2, 0.2, 1]\r\n])\r\n\r\n# Assuming robot_cell is defined\r\nrobot_cell = (0, 0)\r\nend_cell = (4, 4)\r\n\r\nstart_node = node(value=robot_cell, name=\"({}, {})\".format(robot_cell[0], robot_cell[1]))\r\nend_node = node(value=end_cell, name=\"({}, {})\".format(end_cell[0], end_cell[1]))\r\n\r\n# Generate a random end cell\r\nmap_height, map_width = free_space_grid.shape\r\n\r\n#! A* functions ----------------------------------------------------\r\n\r\n# if a cell is given, return the 4-connected neighbors\r\n# probability high -----> cost low -----> high priority\r\ndef get_neighbors(parent_node):\r\n\r\n neighbors = []\r\n x, y = parent_node.value\r\n\r\n # Check if the neighbor is within the map and is free\r\n if x > 0 and free_space_grid[x - 1,y] != 0:\r\n neighbors.append(node(value=(x - 1, y), parent=parent_node, cost=(cost(parent_node, (x - 1, y)))+heuristic((x - 1, y), end_cell), name=\"({}, {})\".format(x - 1, y)))\r\n if x < map_width - 1 and free_space_grid[x + 1,y] != 0: \r\n neighbors.append(node(value=(x + 1, y), parent=parent_node, cost=(cost(parent_node, (x + 1, y)))+heuristic((x + 1, y), end_cell), name=\"({}, {})\".format(x + 1, y)))\r\n if y > 0 and free_space_grid[x, y - 1] != 0:\r\n neighbors.append(node(value=(x, y - 1), parent=parent_node, cost=(cost(parent_node, (x, y - 1)))+heuristic((x, y - 1), end_cell), name=\"({}, {})\".format(x, y - 1)))\r\n if y < map_height - 1 and free_space_grid[x, y + 1] != 0:\r\n neighbors.append(node(value=(x, y + 1), parent=parent_node, cost=(cost(parent_node, (x, y + 1)))+heuristic((x, y + 1), end_cell), name=\"({}, {})\".format(x, y + 1)))\r\n\r\n return neighbors\r\n\r\ndef cost(current_cell, neighbor):\r\n\r\n if(current_cell.parent):\r\n parent = current_cell.parent.value\r\n else:\r\n parent = current_cell.value\r\n\r\n current = current_cell.value\r\n\r\n #check if direction has not changed\r\n direction1 = (parent[0] - current[0], parent[1] - current[1])\r\n direction2 = (current[0] - neighbor[0], current[1] - neighbor[1])\r\n\r\n if direction1 == direction2:\r\n penalty = 0.1\r\n else:\r\n penalty = 0.5\r\n\r\n return penalty + round(1 - free_space_grid[neighbor],2)\r\n\r\ndef heuristic(current_cell, end_cell):\r\n return abs(current_cell[0] - end_cell[0]) + abs(current_cell[1] - end_cell[1])\r\n\r\n#! A* algorithm ----------------------------------------------------\r\n\r\n# Create an instance of the astar class\r\ndfs_obj = dfs(get_neighbors)\r\n\r\n\r\n# Find the path\r\npath = dfs_obj.path(start_node, end_node)\r\ndfs_obj.display_path(filename=\"dfs_path\")\r\nprint(\"Path: \", path)\r\n\r\n#! Plot the path ----------------------------------------------------\r\n\r\nplt.figure()\r\nplt.imshow(free_space_grid, cmap='gray', origin='upper')\r\n\r\n# Plot the path as a line\r\npath = np.array(dfs_obj.get_raw())\r\n\r\n#plot simplified dots\r\nplt.plot(path[:, 1], path[:, 0], 'r')\r\nplt.scatter(robot_cell[1], robot_cell[0], color='r', marker='x')\r\nplt.scatter(end_cell[1], end_cell[0], color='g', marker='x')\r\nplt.show()\r\n\r\n```\r\n",
"bugtrack_url": null,
"license": "MIT License with attribution requirement",
"summary": "Vagabond is a comprehensive library for pathfinding, navigation, and environmental understanding in robotics and automation. It provides a range of algorithms and tools to help developers create efficient and sophisticated pathfinding solutions for robots and autonomous systems.",
"version": "2.0.2",
"project_urls": {
"Download": "https://github.com/Kawai-Senpai/Vagabond",
"Homepage": "https://github.com/Kawai-Senpai/Vagabond"
},
"split_keywords": [
"pathfinding",
" robotics",
" navigation",
" a* algorithm",
" graph theory",
" automation",
" robotic systems"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "7ab6de280d7da52f4f8f443f7c6b2b12c7371d4a475bfe4656658c5ae9332a18",
"md5": "ff9f79876fb1e0cb617550406c1a4bf4",
"sha256": "89d06943cf0295eaa2d69dbd54687257a7def96a60902615b023f720818ededd"
},
"downloads": -1,
"filename": "py_vagabond-2.0.2-py3-none-any.whl",
"has_sig": false,
"md5_digest": "ff9f79876fb1e0cb617550406c1a4bf4",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 10441,
"upload_time": "2024-09-10T06:44:28",
"upload_time_iso_8601": "2024-09-10T06:44:28.867389Z",
"url": "https://files.pythonhosted.org/packages/7a/b6/de280d7da52f4f8f443f7c6b2b12c7371d4a475bfe4656658c5ae9332a18/py_vagabond-2.0.2-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "047eaec336259151394fa862a1846f983843b2c79990c50c1721fa210a33a22a",
"md5": "7191b815253bf1c13d96bf6ea945cb6e",
"sha256": "cbf5c270fbe3dd14ad214bc8312fcba747aa777e845664f5b8de2183e2ede0db"
},
"downloads": -1,
"filename": "py-vagabond-2.0.2.tar.gz",
"has_sig": false,
"md5_digest": "7191b815253bf1c13d96bf6ea945cb6e",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 13248,
"upload_time": "2024-09-10T06:44:30",
"upload_time_iso_8601": "2024-09-10T06:44:30.730454Z",
"url": "https://files.pythonhosted.org/packages/04/7e/aec336259151394fa862a1846f983843b2c79990c50c1721fa210a33a22a/py-vagabond-2.0.2.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-09-10 06:44:30",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "Kawai-Senpai",
"github_project": "Vagabond",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "py-vagabond"
}
JSON
