Grid¶
To start off our project, we first need to generate a state space - in particular, a data structure that represents a plane with a bunch of polygons inside.
The simplest way to represent this would be to use a binary two-dimensional array. Every element in the array would then have a corresponding 1-to-1 mapping with our plane. We can represent empty (or movable/traversable) spaces as a 1, and filled (i.e. point/line from a polygon's edge) as a 0.
We can generate such an NxM grid quite easily:
def generate(width, height):
return [[1 for i in range(width)] for i in range(height)]
print(generate(10, 5))
We can simplify our lives a little bit by using numpy. This has the added advantage of having our grid be pretty printed by default:
import numpy as np
def generate(width=100, height=100):
return np.ones((height, width), dtype=np.uint8)
print(generate(10, 5))
The next thing that we need for our grid generator is to be able to represent polygons. Since we'll have polygon vertices as input, and since we would be working on a grid like system, we would need a list of coordinates between two vertices.
Handling horizontal and vertical lines is easy, we simply iterate the points along the axis.
def generate_line(p0, p1):
x0, y0 = p0[0], p0[1]
x1, y1 = p1[0], p1[1]
dx, dy = abs(x1 - x0), abs(y1 - y0)
points = []
if dx == 0 or dy == 0:
if dy == 0 and dx == 0:
pass
elif dy == 0:
points = [(x, y0) for x in range(min(x0, x1), max(x0, x1) + 1)]
elif dx == 0:
points = [(x0, y) for y in range(min(y0, y1), max(y0, y1) + 1)]
return points
print(generate_line((0, 0), (0, 5)))
print(generate_line((0, 0), (5, 0)))
Straight, 45 degree angle diagonal lines are also simple enough to implement.
Handling lines of arbitrary angles however is a bit more complicated. Astute readers however will notice that we can use a rasterization algorithm to generate the needed coordinates between two points. We can use Bresenham's line algorithm for this, and expand our previous algorithm to support arbitrary lines.
def generate_line(p0, p1):
x0, y0 = p0[0], p0[1]
x1, y1 = p1[0], p1[1]
dx, dy = abs(x1 - x0), abs(y1 - y0)
points = []
# handle horiz/vertical line manually
if dx == 0 or dy == 0:
if dy == 0 and dx == 0:
pass
elif dy == 0:
points = [(x, y0) for x in range(min(x0, x1), max(x0, x1) + 1)]
elif dx == 0:
points = [(x0, y) for y in range(min(y0, y1), max(y0, y1) + 1)]
else:
x, y = x0, y0
x_step = -1 if x0 > x1 else 1
y_step = -1 if y0 > y1 else 1
if dx > dy:
err = dx / 2.0
for x in range(x0, x1, x_step):
points.append((x, y))
err -= dy
if err < 0:
y += y_step
err += dx
else:
err = dy / 2.0
for y in range(y0, y1, y_step):
points.append((x, y))
err -= dx
if err < 0:
x += x_step
err += dy
points.append((x, y))
return points
print(generate_line((0, 0), (0, 3)))
print(generate_line((0, 0), (5, 3)))
Now that we have a generate_line utility function, adding polygons to our generated grid is as simple as iterating over polygon vertices and setting the coordinates with the proper data.
def generate(width=100, height=100, polygons=[]):
grid = np.ones((height, width), dtype=np.uint8)
# make border
add_points(grid, generate_line((0, 0), (width - 1, 0)))
add_points(grid, generate_line((width - 1, 0), (width - 1, height - 1)))
add_points(grid, generate_line((width - 1, height - 1), (0, height - 1)))
add_points(grid, generate_line((0, height - 1), (0, 0)))
for polygon in polygons:
for i, coord in enumerate(polygon):
second_coord = polygon[(i + 1) % len(polygon)]
add_points(grid, generate_line(coord, second_coord))
return np.array(grid, dtype=np.uint8)
def add_points(grid, points):
for coord in points:
grid[coord[1]][coord[0]] = 0
print(generate(10, 10))
Note how we added a border rectangle for our grid as well.
We have now defined a function that will generate the grid from our input. It would be useful to have a couple of utility functions for it. In particular, since we know that our grid needs to be traversed like a graph later on, it would behoove us to implement a utility function that returns adjacent neighbors given a coordinate.
Such a function is easy enough to define - we simply iterate over the left, right, up, and down of our coordinate, see if it is still inside the grid, and see if it is traversable.
def find_walkable_neighbors(grid, node):
neighbors = []
if is_valid_neighbor(grid, (node[0] - 1, node[1])):
neighbors.append((node[0] - 1, node[1]))
# [...] do the same for all neighbors, down, left, right
return neighbors
def is_valid_neighbor(grid, node):
return is_inside(grid, node) and is_coord_walkable(grid, node)
def is_inside(grid, node):
return node[0] >= 0 and node[0] < grid.shape[1] and node[1] >= 0 and node[1] < grid.shape[0]
def is_coord_walkable(grid, node):
return grid[node[1], node[0]] == 1
With our generator and utility functions implemented, we can move on to implementing our search algorithms.
This is a post in the CS 180 Pathfinding series.
Other posts in this series:
- Mar 17, 2019 - CS 180 Pathfinding
- Mar 17, 2019 - Grid
- Mar 17, 2019 - Finders
- Mar 17, 2019 - Grid Search
- Mar 17, 2019 - Test Cases
- Mar 17, 2019 - Running Test Cases
- Mar 17, 2019 - Timing
- Mar 17, 2019 - Viz