Using a pathfinding algorithm in our bots means we no longer have to construct waypoint scripts. Instead, the bot will be able to walk from any point to any (connectable) point without being told by the user how to get there or how to avoid obstacles.

If you're curious about how this pathfinder works, I'll describe the methodology, but be aware you will not need to know any of this to use the library.

**Step 1**is to create collision zones around each object you want to avoid. A polygon will be constructed around each object, essentially creating a path that describes the perimeter. For example, a cube obstacle may look like:

Code: Select all

```
{ -- Cube
{x = 9, y = -1},
{x = 9, y = 1},
{x = 11, y = 1},
{x = 11, y = -1},
},
```

**Step 2:**

Now that each polygon has been offset, we will also connect each vertex in each polygon to it's neighbors. That is, point 1 connects to point 2, which connects to point 3, and so on until it wraps back to point 1. If we were to visualize out collection of polygons right now, it might look something like this:

**Step 3:**

We can now connect each point in each polygon to every other point in which it has visibility (does not cross inside of another polygon). This will create tons of connections between points, and may look like this: Each "connection" then represents a pathway between points that can be considered collision-free; basically it means we can walk down this line to get to that point. If there's a point we don't specifically have vision to, we can instead opt to bounce to another connection until we get around the obstacle. But we're getting ahead of ourselves. Anyways, this collection of polygons & connections will be known as a "PolyGrid" from here on out.

**Step 4:**

Now for the fun part: the actual pathfinding. Our PolyGrid currently describes the collisions of the world, but in order to find our way among the jungle of connections, we must first insert two more (temporary) points into the PolyGrid. These two points represent our "start point" (where the player currently is) and the "goal," the place we want to reach. Both the start and end points must then re-check every point in the PolyGrid and connect to any "visible" points (same as described above). At this point, our PolyGrid can represent a path from the player's current position to our intended goal.

We use the

**A***pathfinding algorithm to traverse the PolyGrid's connections and find the shortest path from our start to our finish. Once that traversal has reached the goal, we retrace our steps backwards and can construct a pathway. This path will describe the shortest path between the start point and the end point that avoids all collisions.

I quickly slapped together a "demo" landscape and put it to the test: