Okay. =)

Well, 3 people commented in a month - which is enough for me, I guess. =P Plus who knows - more content means more search engine fodder, so more people might stumble across me.

So what have I been working on? Well I released the harvest bot (EverHarvest) and we've gone through several minor revisions, plus constant update when EQ2 patches and breaks the system. Some work has gone into two additional projects - AutoGrind (a hunter bot for EQ2, similar to Faldo's recently-abandoned EverHunt), and a project I'm calling 'GCB' - Group Control Bot, which will basically be an EQ2-smart multi-box helper.

AutoGrind is being implemented as an extension to EverHarvest; that is, the two programs will be contained in the same package, but still requiring separate licenses to activate. The reason I'm going this route is that the two programs are *incredibly* similar (walk around, target stuff, act on the targeted stuff) so they can share a great deal of code. Additionally, the two tasks can work in tandem - while you're harvesting, if you're attacked, it can attack back; or while you're hunting, if it targets a node, it can harvest it.

Group Control Bot (that's a working title) is, very simply, a program that allows you to control multiple instances of EQ2 (running on one or more *separate* computers) from one Master computer by sending commands from the Master computer to the slave computer(s). Unlike most generic programs which perform similar tasks, this one is EQ2 specific, such that it will understand commands like 'Target Me' or 'Move Behind My Target'.

Both projects are currently in their extreme infancy - GCB is mostly disorganized notes, while AutoGrind is a branch of EverHarvest code with a few modifications - nothing functional yet, or ready for beta testing.

Something I'm revisiting with the EH + AG project is the idea of smart pathfinding replacing the waypoint system. I did some early tests with this last year, with very limited success - I didn't understand how to build a Quadtree node connectivity graph (basically, for each square, finding that square's neighboring squares). I was using a *very* slow geometry-based method of comparing all the square's bounding boxes to eachother, returning a collection of all the squares that were touching.

As I said, I'm revisiting it - I rewrote my Quadtree implementation to remove most of the recursion from the methods operating on the structure, and did some additional research on the subject of node neighbor finding, such that I was able to construct a non-geometric solution to the problem that uses node traversal to find neighbors. This method is *far* faster, especially for large numbers of nodes.

I haven't yet written my A* implementation yet - doing some more research into this as my last attempt, while workable, was highly inefficient, as was my path smoothing algorithm (required for more human-looking path-walking).

So - that's what's been on my mind recently. =)

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...