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

Stage 2

Started EverHarvest Beta Stage 2 last night. Got some good early feedback - and most of the testers reported a bug that causes the walker to miss a waypoint and continue on forever if the bot bumps something, or similar issues occur. I've corrected the issue, and released a new version of the stage 2 app.

So far, so good! =)

Stage 1

EverHarvest Beta Stage 1 has begun! =) 25 beta testers have been granted access to this stage, where we test the methods the harvest bot will use to gather information from the EverQuest II client. This information gathering is critical to the functionality of the bot, and that made it the ideal place to start testing.

So far, so good! All of the testers I've heard back from have reported that Stage 1 is successful, and so I begin work on Stage 2 - the walkpath test.

More to come!

Perspective

I knew I was asking for trouble when I posted this poll on the forums. Give people a chance to give their opinion, and they'll give it. And because people are more likely to say something when they're unhappy (as opposed to happy), I knew this thread would end up being the soapbox for people's frustrations regarding our software.

One thing I'd like to point out is that providing support for software out in the wild is not easy. Our users run Macrocrafter.com software on a vast number of different configurations - operating systems, processors, video hardware, ISPs, .NET Framework versions - all of which make predicting the fixes for an issue a pretty daunting task. Luckily over the year and a half I've been working for this company, I've learned that most of the problems people encounter stem from the same set of issues, and I've learned how to respond to them.

When SOE hands us a new patch, the very first thing I do (like all the rest of you) is wait for the servers to come back up after the patch is complete. I can't do anything until then, but that doesn't tend to matter when nobody else can either. After that, I have to examine all the changes the new update brought to us. More often than not, the changes are small, and I'm able to release a hotfix after an hour or so. This is almost always the case. When it's not the case (like GU#39 for instance), it can take days for the changes to be accounted for and resolved.

None of this, however, accounts for real life. Macrocrafter.com is not my only job. I run a local network shop for small businesses out of my home as well, and sometimes that job takes precedence. That happened this weekend, in fact - one of my clients contracted a virus in all 15 of their workstations, as well as their server, and I was called in to resolve. I was about halfway finished with that job when the game update was released, and I couldn't stop what I was doing - their business (a nearly paperless dental office) relies on their computers being operational in order to function at all.

My other job is taking care of two kids, a two-month old and a 3-year old (one of which is mine, the other is sort of my step-kid), both of which demand a *lot* of attention. They come first, before Macrocrafter.com, and anyone with children will understand why.

 

So I hope this helps to provide some of you with some new perspective on why it can take a few days to fix some of these patch issues. This most recent patch delay was a combination of all these factors - large patch with many changes, my rl job, and my kids.

More EverHarvest Progress

Faldo helped me out today in-game with the player detection / node-stealing avoidance code, and I gotta say it works beautifully. I added a few more human-mimicking routines as well, all to help mask the fact that it's a bot we're running. All these tweaks will be optional, and set through a Tweaks dialog, which has yet to be written - Michael's going to start work on the bot's UI tomorrow, after I give him the details.

Faldo also showed me a quick demo of the hunter bot he's working on. If all goes well, we'll be offering it through Macrocrafter.com, and then everyone will get a chance to sample it. I'm really happy with how this partnership is shaping up - Faldo's an excellent hacker, and a great guy besides. A true pleasure to work with.

Ah well - I gotta run. It's past my bed time!

EverHarvest Beta draws closer

A more complete version of EverHarvest was run successfully on my machine earlier today (that is, about 5 minutes ago). I created a walkpath using my PathBot program, saved it, and loaded it in the EverHarvest test harness (PathBot will be a part of EverHarvest, allowing you to create and manage walkpaths). After doing all this, I just sat back and watched it harvest roots for me. =D

All that's left in this process, really, is to get Michael to draw up that UI for me. Once that's done, I can release this to my beta testers, and start getting some *real* feedback.

There's still time if you want to sign up! Go check out the forums!

EverHarvest Test Run

Couple updates on EverHarvest progress. First, I've gotten all of Faldo's data integrated into Autocrat in the EQ2 Core Interface system. This data specifically includes instructions for my Memory Reader that tell it where and how to find the data we use in the Harvest Bot - particularly the details about your character (position, heading) and the things around you (nodes, mobs, players). Using this data I wrote a class that returns all this data.

Also, I was able to set up a system for moving the character around the zone. I've done this before - creating a pathing bot. Initially it looks rather choppy, almost bot-like (which would obviously be a deal-breaker) - but when viewed from another EQ2 client running on another computer, it looks perfectly normal - as if it really were a player running around - which is exactly what we wanted!

My first test run also confirms that my simple State Machine design works. A State Machine is a design pattern that allows you to design and program a system by way of the states it can be in. For example, our Harvest Bot has 5 states - Inactive, WalkingToWaypoint, WalkingToNode, Harvesting, and Final. Each state has its own code to run that performs the function of that state, and when it's done (for one reason or another) it switches (or transits) to the next state. The Harvest Bot state machine is the first I've ever written, and I'm happy to say that it's a success!

So - I NEED BETA TESTERS! Get over to the forums and sign up!

EverHarvest Beta

The EverHarvest Beta has begun accepting beta applications! Go here - EverHarvest Beta Signup - to check it out. We're only accepting a limited number of beta testers, so sign up early!

EQ2 Core Interface

Faldo's making excellent progress with the EQ2 core. We're pretty much able to start work on the Harvest Bot right away - Hunter Bot progress will commence much the same way after the Harvest Bot beta is finished.

We're using very non-invasive methods of data gathering for the EQ2 Core code. Everything we're doing is done by reading into the memory of EQ2 - something that is very difficult to detect by the EQ2 client itself, and because the information we gather with this method is far more accurate than screen-reading, this system will be incredibly robust.

The Harvest Bot will be very simple at first. For setup, you'll need to adjust some EQ2 settings, set up a hotbar, tell the bot what nodes to gather from, and create a walk-path (or download one that someone else has made). A walk-path basically just tells the Harvest Bot where to walk within the zone - you create one by recording your path. You walk around, and the Harvest Bot's pathing engine will record where you walk, then when the bot is running it will play back the recorded path.

Once the setup work is done, the bot is ready to run - it will walk the walk-path, all the while looking for the nodes you specified during setup. When it finds one, it will walk up to it, harvest from it, then move on its merry way. Optionally, it will look out for other Players in the area of the node, and if it finds one within harvesting range, it will ignore the node - that is for preventing node stealing, which is generally considered to be rude and suspect behavior.

For the time being, more advanced activity like agro avoidance and the like will be left out of the bot, but we do intend on improving the software after release, so expect these features shortly after the bot comes online. =)