Tuesday, December 2, 2008

Retiring this blog

I actually forgot about this blog for a while - sorry about that, guys! Since my blogging interests have expanded to more general programming topics, I've started a new blog here -- http://shadowcoding.blogspot.com/ -- where you can catch up on what I'm up to. There I talk about new personal projects I'm working on, as well as challenges (and sometimes solutions) that I face while on the job.

As far as Macrocrafter goes, I'll still talk about those projects, but probably in a more general way. All official news of course will be posted in the Macrocrafter forums, but if you're interested in what I do for a living, you'll find it over at my new blog.

For those of you who did read this, I appreciate the interest! =) I hope to see you all over at the new place (where I've been making very frequent updates).

Sunday, April 27, 2008

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

Tuesday, March 11, 2008

Anyone still read this?

Please leave a comment if anyone's got this on a feed reader or checks this on a regular basis - having not gotten a lot of activity here, I kinda feel like there's little point to posting. So - yeah, let me know. =P Thanks.

Sunday, January 6, 2008

Happy New Year!

Well, I didn't get EverHarvest released before Christmas (would have made for a great Christmas, for all of us) - but I have made a great deal of progress in the previous weeks. I'm close to a release, matter of fact - lots of changes, for the better, to the macro engine, and to the state machine itself. No longer does it require such a long pause at the start for 'initialization,' which is probably the best part. Also the saving and loading of walkpaths has become quite fast as I switched from human-editable walkpath datafiles to compiled datafiles. This makes editing walkpaths manually impossible, unfortunately, but I didn't see much capacity for manual editing anyway as walkpaths typically get quite huge.

Anyway - with the release of EverHarvest looming ever-so-near on the horizon (by the end of the week, in fact), the question is now starting to focus on what must be done about Evercraft. Some of you have noted that Evercraft's performance of late has suffered, mostly due to an incompatibility on Windows XP between Evercraft and .NET 3.0/3.5. Well, the answer to that problem is here - I have just posted an announcement on the Macrocrafter.com forums revealing our plans for the development of Evercraft 6, which will be written using the .NET Framework 3.5 and Autocrat 3.5 (which is in use in EverHarvest).

I'm excited. =) Evercraft 6 is going to be a massive improvement over EC5 (which itself was a massive improvement over EC4), and is going to allow us to do soooo much more with the system. We're going to build it from the ground up with extensibility and maintenance in mind, so recovering from changes (like RoK) will be a piece of cake. Also we'll be able to add new functionality to the system to do things Evercraft has never been able to do before. I'll expand on that later. *devilish laugh*

So - that's this month's update... heh - no, seriously - I'll update more frequently as I get the chance.

TTFN. =)

Thursday, November 29, 2007

Status Update

It's been a short while since my last update. Things have been pretty hectic around here, I have to say. Rise of Kunark really screwed us over in terms of Evercraft's compatibility with the game, though the changes that were made seem to be for the greater good. In particular the auto-configuring hotbar on the tradeskill window is especially helpful to us (as well as to all the non-macro crafters out there), which can only be a good thing.

In response to RoK's release, we've made several changes to Evercraft that amount to essentially a band-aid on the gunshot wound... We removed the Hotkey Setup step, taking full use of the new hotbar. We also did the Vista users a favor and changed the Coordinate Setup system such that it is *much* faster - near instant on Vista and XP machines alike. As a consequence of this change, Coordinate Setup is also easier to use - you don't need to mouse-over the white box anymore, and because we perform Coordinate Setup at the beginning of each job, the tradeskill window itself can be moved around - no more frustration! =)

The harvest bot beta was also disrupted by the RoK release, in particular the fact that the memory data collected was no longer correct, and with SOE's habit of patching on a daily basis for two weeks after a major release it made little sense to try and collect that data again until the game was more stable. I only recently got the bot running again, just in time to release the next version yesterday. As far as the hunter bot goes, I'm not sure what Faldo's progress on that is - which is a shame since I'm really anxious to see it working.

Work on the new pathing system is pretty much at a standstill while Evercraft is being worked on. All my proofs of concept still function and are relevant, but I just haven't had the time to devote to it. As such, I think I'm going to go against the majority of my beta testers (who have expressed the desire that I delay the release of the harvest bot in order to get the new pather working) and release the bot (once finished) with the walkpath pather instead.

One thing I am devoting some time to, however, is the next version of Autocrat, which will be built on top of the .NET Framework 3.5. Autocrat35 will be a massive improvement over the current version, but mostly in terms of developer productivity - that is to say, it'll take *much* less time to get something out the door with this version.

So that's been my life lately. =P Sorry for not updating sooner - just hasn't been on my mind until recently.

Tuesday, November 6, 2007

Bot testing has begun

After having my beta testers successfully test the various bits of tech that go into EverHarvest, I've decided to go ahead and release a command-line version of the harvest bot. This is the first time an actual harvest bot has been available from Macrocrafter.com, and I'm pretty proud of it so far. I've been using it personally for about two weeks while debugging and tweaking, and in that time it's made me about 10 plat, just from selling off the stuff I've harvested while testing... Pretty crazy. I hope everyone else has similar success.

This also means that I'm officially no longer taking beta applications for this iteration of the bot. Once the next version pops up, I might re-open applications, but that will depend on how many of my current beta testers decide to stay on the post-release beta team.

So where do we go from here?

Good question. Once the bot is released, there is still a ton of work to be done - I will be completely replacing the current walkpath-driven system with an intelligent pathfinder (as discussed in a previous entry). Additionally, there will be tweaks, bug fixes (even the most rigorous testing misses the ones that scurry behind the walls), and new features that I haven't even though of yet. Plus, there's data-collection to be done - the intelligent pathfinder will only be intelligent because it will have knowledge of the layout of zones - knowledge that we (more likely I, if I can't farm some of it out) will have to provide it with.

So... That's about it this update. More later. =)

Wednesday, October 31, 2007

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