Bots and Pathing

I've spent the past 3 days or so working on a specific problem that the EverHarvest bot can experience during the course of running. In particular, the potential for the bot to get 'stuck' while walking around on the map, either from waypoint to waypoint (due to an improperly planned route), or from waypoint to harvest node (or back).

Let me explain the problem space. Right now, with the EverHarvest beta, I currently use a Waypoint system for pathing. That is, the user records a walkpath as a series of waypoints, and when the bot is run, it will play back the walkpath, causing the character in-game to follow the original course. This system is ideal as a strictly navigation system, because the waypoints are rigidly defined - they're simply X and Y coordinates on the game map. And because the player had to walk across the map to record the walkpath, it's nearly guaranteed to produce a walkable path in at least one direction.

The problem occurs when the bot needs to deviate from the walkpath, for whatever reason (in this case, for harvesting from a node). In this case, the bot can get hung up, because it's entering into uncharted territory.

So the solution to this problem could take on many forms. We could have it detect when the bot is stuck, and in that case make an attempt at moving around the obstacle (such as by turning right or left, backing up, jumping, etc.), but these methods have the unfortunate side effect of looking very bot-like. If you see a player run into a tree, then try to go around the tree by jumping or turning, you'd probably think that either the player is a moron, or the character is being botted. So this solution is unacceptable.

Another possible solution is to deal with the stuck condition by evaccing. This of course requires the character to have access to an evac spell, and thus is not ideal for everyone. Further, the user needs to have a path written from the evac point to their harvesting waypoint, which is something of an inconvenience. So evaccing is out.

Finally there's the non-solution; that is, to log out when a stuck condition is detected. I don't know about you, but I'd be pretty upset if I set up a 5 hour long harvesting session before bedtime, only to wake up the next morning to find that the bot got stuck 10 minutes after I went to bed.

Unfortunately, it's too late in the current EverHarvest development cycle to change the pathing method before launch. We're stuck with waypoints, which means I have to choose one of these methods of dealing with the 'stuck' condition - at this time, the beta testers have said they want it to notify the user, then log out if it hasn't heard from the user in X amount of time. Which is fine - I can do that.

 

It is not, however, too late to implement a different pathing system for the next iteration of the harvest bot.

In particular, I'm talking about a radically different method of pathing - one that, unlike the Waypoint system, requires the bot to have intimate knowledge of the in-game environment, specifically regarding areas of walkability. This method involves creating a graph of rectangular cells inside the region you want to harvest, and using the A* pathfinding algorithm to find the closest path between any two points inside that graph of cells. Obstacles will be marked as such, and thus not included in the graph - that way, A* will find how to path around the obstacles.

The method I'm using to create the graph of cells is called Quadtree Decomposition. A Quadtree is a tree data structure in which every node is either a leaf containing exactly 0 child nodes, or a branch containing exactly 4 child nodes. Quadtrees are discussed HERE in case you're curious as to how they work (that example uses a Quadtree for collision detection, but the data structure is the same).

Once I have the quadtree, I analyze it to find all the walkable nodes and how they touch eachother. This is done so that I can create a list of nodes for the A* pathfinder to analyze.

I haven't quite gotten the pathfinder online yet, but everything else is working.

There is one problem with using Quadtrees for walkability data in zones: overlapping regions. Say you have a zone (like The Caves in Qeynos) where you have multiple levels. You might have an obstacle on a level underneath another level where you can walk. Quadtrees, however, can only operate in two dimensions - an obstacle is treated as an obstacle regardless of the height the character is at.

Luckilly, I have a solution. We'll use The Caves - it has three levels; the bottom, middle, and top. Connecting the bottom and the middle is a ramp you have to walk up; connecting the middle and the top is a tunnel. The solution to successful pathing in this zone is: each level has its own Quadtree representation, and the connectors have standard walkpath waypoints to connect them. If your bot needs to path from the bottom to the top, it'll path from the bottom to the bottom-middle connector, through the middle to the middle-top connector, then from there to the destination point on the top.

Anyway - combine this data with harvest node positions, and you have a system that can path you from harvest node to harvest node, gathering every one of them, without the user having to set up their walkpath in advance. Of course it also allows all sorts of other fun things - like if I connect zones together, it can path (automatically) from one zone to another automatically, without needing a walkpath. Pretty neat, huh? =)

It's a workable solution that I'm particularly proud of. There's only one major problem...

Someone's gonna have to go and collect all this data...