MicroMacro 2.0 advanced pathfinding (w/ example video)

Discuss, ask for help, share ideas, give suggestions, read tutorials, and tell us about bugs you have found with MicroMacro in here.

Do not post RoM-Bot stuff here. There is a subforum for that.
Forum rules
This is a sub-forum for things specific to MicroMacro.

This is not the place to ask questions about the RoM bot, which uses MicroMacro. There is a difference.
Post Reply
Message
Author
User avatar
Administrator
Site Admin
Posts: 5306
Joined: Sat Jan 05, 2008 4:21 pm

MicroMacro 2.0 advanced pathfinding (w/ example video)

#1 Post by Administrator » Fri Jul 27, 2018 4:45 pm

I've been working on a pathfinding library for MicroMacro. The goal was to keep things as simple as possible, yet effective enough for most general purposes. At the present state, the pathfinding library will not work well in 3d games where you have multiple layers that cross over each other (for example, a multi-floored building will be a pain to navigate unless you put in some extra work to isolate floors), however would work just fine most of the time in a game like Runes of Magic.

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},
	},
Each polygon will be "offset" (think: you are pushing each edge of the polygon outwards, hence making it larger) by the actor size (this is a rough approximation of the player's collision box). In doing so, we do not need to calculate whether the player can fit through gaps, or try to push the player into walls; instead the new, larger collision polygon includes those areas. This makes our life easier later.
We increase the collision zone by the actor size (0.5 in this example)
We increase the collision zone by the actor size (0.5 in this example)
offset.png (4.34 KiB) Viewed 11331 times

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:
collisionmap.png


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:
The blue lines represent "connections"
The blue lines represent "connections"
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:

Post Reply

Who is online

Users browsing this forum: No registered users and 16 guests