Badgebot development (A bit of a teaser, to whet your appetite...)

[Dyne]

I took a break from my Dynebot project, since I wanted something of smaller scope.  I forked it into a thing that does this (note the chat):



Still a fair ways to go before its terribly usable, but assuming I've got all the coordinates right, in theory I now have 450ish things to seek in-game.  That's not counting the history plaques that it also handles. (Since there is no way to signal "interact with this" yet, those are also operating by proximity ... or will be once I get them working).  Or my easter eggs.

I need to ponder or sort out a few things, like:

• Purely hypothetical question, since PChat doesn't send faction ... but if it did, how would I treat badges that used to be inaccessible to one faction or another?  Just let anyone hunt anything?  Ignore characters of the wrong faction so it behaves like CoH used to?  For now it'll have to be "anyone can hunt anything".
• how to get the full JID of the user that sent each u stanza.  Currently, PChat sends that info in Presence stanzas, but not in the Message stanzas that u stanzas come in.  Eventually, I'd want other data from their presence stanzas, like character/bodytype (for sending the correct male/female variant of the badge).  That's likely also how PChat would send faction info.
• Unlike, say, Galaxy City, the badges that Faultline shares with its Echo have wildly different locations.  How shall I treat these?  As the same badge (because they really are)?  As different badges (because folks might want to hunt them all)?  (Echo Faultline with no travel powers?!  Better you than me.**)
• It'll be a pain in the rear to get the Praetorian River Rat badge because zoning in the water tends to dump you below the map on the other side.  Between that and the fact that they don't have specific coordinates listed, I haven't put them in.  When I do, though, they'll be treated as 19 individual badges, not 1/19th of one badge.  The Underground badges are also split up.
• Reorganizing the bot to spawn connections to multiple zone meta rooms as desired, which is a major thing I need to port back to Dynebot

Edit: BTW, if it weren't obvious, it is not running on the public server right now.  I don't know when (or even if) it will end up there.  All of the bots that are being written that I'm aware of are still in heavy development, including this one, so we haven't yet reached the point of needing/having an official policy on their use.


** In all honestly, I did go and track them all down in the Echo yesterday because I needed their old coordinates, as the various wikis and such lacked that info.  Ugh.  To make matters worse, I managed to locate an old Gamefaqs that gave the coordinates ...  after I'd found them myself.

[Zombie Hustler]

Yay! Badges!! 



That is all.

[Arcana]

• how to get the full JID of the user that sent each u stanza.  Currently, PChat sends that info in Presence stanzas, but not in the Message stanzas that u stanzas come in.  Eventually, I'd want other data from their presence stanzas, like character/bodytype (for sending the correct male/female variant of the badge).  That's likely also how PChat would send faction info.

That one is easy.  In whatever callback you're using to process Presence stanzas do something like this:

Code: [Select]

            pcid = str(msg['from'])
            if not self.pcRoster.has_key(pcid):
                self.pcRoster[pcid] = {}
                print "Debug: new Presence detected: " + str(pcid)
                print "Debug: sending pcu to meta channel"
                self.send_pcu()
               
            if self.pcRoster.has_key(pcid):
                self.pcRoster[pcid]['pc_jid'] = msg['pc']['jid']
                self.pcRoster[pcid]['pc_origin'] = msg['character']['origin']
                self.pcRoster[pcid]['pc_map'] = msg['character']['map']
                self.pcRoster[pcid]['pc_costume'] = msg['character']['costume']
                self.pcRoster[pcid]['pc_class'] = msg['character']['class']
                self.pcRoster[pcid]['pc_name'] = msg['character']['name']

That keeps a dictionary (a dictionary of dictionaries, actually) of all the entities in the meta channel.  Then whenever you process a <u />, whatever handle its "from" you can look that up to see what their last presence looked like.  I also add to the dictionary their last <u /> so I can tell where anyone last sent position from - important downstream when it comes to interpolating/predicting character position.  One day you might want to implement a prediction algorithm, otherwise someone might run past a badge location and not get it, because you never get a <u /> from anywhere near it.  If they have fixed velocity, you could run a predictor that took the entity dictionary and extrapolated the positions of everyone based on their last known velocity, to see if any of those vectors pass close enough to a badge location.

Incidentally, I don't recall body type being in the presence stanza.  Rather, when you award a badge you'll need to do an Iq for their costume, and pull the body type from the costume response.

[Dyne]

One day you might want to implement a prediction algorithm, otherwise someone might run past a badge location and not get it, because you never get a <u /> from anywhere near it.  If they have fixed velocity, you could run a predictor that took the entity dictionary and extrapolated the positions of everyone based on their last known velocity, to see if any of those vectors pass close enough to a badge location.

Oh yeah, I forgot to mention that (I had it in a post I wrote yesterday but didn't actually submit because I wanted to get this at least partially operating first).  For the time being, you definitely do have to stop or zig-zag or something in order to trigger a position update while within the badge's detection radius (which can be set on a per-badge basis); I wasn't ready to jump into implementing that sort of prediction.  However, when I do get to that point, this tip will be very helpful, so thank you.

Incidentally, I don't recall body type being in the presence stanza.  Rather, when you award a badge you'll need to do an Iq for their costume, and pull the body type from the costume response.

Sorry, you are right.  I've been awake too long and conflated <presence><character /></presence> and the <iq><costume /></iq> (which was not helped by the character stanza's costume attribute).  You could make a case for having gender in the character stanza (at least in COH proper, where it couldn't change), but as long as it's accessible somewhere it's all good.



Note: badges and plaques listed as having echoes currently count twice; I basically just credit you with both versions for simplicity and haven't made it subtract those yet

[Tipsy]

I don't have much to add here, except that this pretty cool.  I'm definitely of the mind that any badge should be available to any character.  And my feeling is that if there's any handful of peculiar/weird badges, it's okay to put them on the backburner rather than have a few odd ones (such as River Rat) sideline the project (but that's probably obvious).

There's only two motivations for getting badges, really.  You're either an OCD completion-ist, who wants to catch every pokemon, or you're looking for a particular collection of appropriate phrases to sit next to your character's name.

Other than that, badge hunting's other value as a good excuse to check out all the glorious zones in the game.  I personally feel that it's perfectly fine, long after this would be implementing and running, to start getting extra creative (taking creative license) and start attributing non-exploration badge names as exploration, or for other silly purposes

[Arcana]

Sorry, you are right.  I've been awake too long and conflated <character> (which is in presence) and <costume>.  You could make a case for having gender in the character stanza (at least in COH proper, where it couldn't change), but as long as it's accessible somewhere it's all good.

If you had unlocked the Super Science tailor, you could make and wear costumes of any body type including different genders in Icon, so gender was not 100% immutable in City of Heroes.

[Dyne]

There's only two motivations for getting badges, really.  You're either an OCD completion-ist, who wants to catch every pokemon, or you're looking for a particular collection of appropriate phrases to sit next to your character's name.

Which reminds me.  This doesn't (and can't) do anything with your title, nor populate the badge windows.  Nothing I do can affect your character state at all; there's nothing in Paragon Chat's protocol or even stored in the database (that I remember) that would allow me to do anything like that.  All I can do is store which badges you find within the bot itself, talk about it in chat, and possibly separately put it on a web page or something (down the road)

If you had unlocked the Super Science tailor, you could make and wear costumes of any body type including different genders in Icon, so gender was not 100% immutable in City of Heroes.

That's true.  I never did unlock it, so I forgot you even could do that.

[Arcana]

Which reminds me.  This doesn't (and can't) do anything with your title, nor populate the badge windows.  Nothing I do can affect your character state at all; there's nothing in Paragon Chat's protocol or even stored in the database (that I remember) that would allow me to do anything like that.  All I can do is store which badges you find within the bot itself, talk about it in chat, and possibly separately put it on a web page or something (down the road)

At some point, there might be something you can do.  Because it has a potentially wide array of uses, Codewalker could decide to figure out how to implement the protocol that allowed custom souvenirs.  AE missions could grant souvenirs to players designed by the author: they were stored by the CoH client on the player's system as a text file.  Maybe, just maybe, that could be opened up to allow for players or bots to award other players some sort of token.  Its limited, woefully inefficient, and possibly entangled in more complex systems that would be difficult to implement.  But its a downstream possibility.

In the meantime, a web-based badge scoreboard is not the worst thing in the world, given how many hoops we badge hunters went through just to end up doing that anyway.

[Dyne]

At some point, there might be something you can do. (snip) Because it has a potentially wide array of uses, Codewalker could decide to figure out how to implement the protocol that allowed custom souvenirs.

I just wanted to manage expectations, but that would indeed be quite useful.

[Tipsy]

I just wanted to manage expectations, but that would indeed be quite useful.

I'm glad you said that. 

[Dyne]

Just an implementation note:

I've got sqlite storing user, badge, and plaque data; and all of the badges and plaques that users have discovered with the timestamp when they were first discovered.  It doesn't read anything from that database yet (still using its internal data structures), but that'll probably come next time I'm rested enough to work on it.

Because of the multithreaded nature of the bots, the standard python dbapi gets a bit harder to work with, so I'm probably going to start using sqlAlchemy to handle the database access.  It's installed but I haven't delved into it yet.

[Dyne]

Things have been quiet on the forums for the last week and a half or so, but as I've mentioned a few times in the global chat, work has been continuing.

I recorded a video of the bot in action and how it works.  Many of you here will already know how Paragon Chat works, so you may wish to skip to 3:00

Edit: Oops, it didn't go public.  Fixed now.

[Arcana]

Cool. 

FYI, based on your video commentary I'm guessing you're iterating the location of the badge hunter against a database of all the badge locations in that zone, looking to see if any have a distance less than some minimum radius.  If you're feeling ambitious, you should investigate kd-trees.  A kd-tree is designed to contain a set of points, and given a point (i.e. a badge hunter) it can quickly locate the nearest point in the collection.  Rather than checking the distance to everything, you just check the distance to the closest point.  I *think* it will be faster, although given the relatively small number of badges per zone it might be more trouble than its worth.  If there were lots of badges and lots of hunters, it could provide significant acceleration.

If you're not feeling that ambitious, since badges in City of Heroes are generally sparse and usually widely separated, you can probably cheat by just looking at a badge map and hand-creating a search tree by space-dividing the badges into exclusive groups with bounding spheres, then check distance against the center of those spheres first.  If nothing else, you could at least get a speed up of a factor of four or five by hand division.

In fact, you can probably *really* cheat by doing something really cheap.  Just sort all the badge locations by x coordinate.  Then quickly find the badge with the closest x coordinate.  From there, *only* check distance for that badge, and every other badge iteratively up the list and down the list in which the x coordinate itself is within K units of the hunter.  Obviously, all other badges further up and down the list have to be too far away.

Consider this list of badge coordinates:

(-100, 0, 57)
(-30, 10, -207)
(-5, 400, 7)
(35, -10, 143)
(38, 200, 18)
(41, 405, 9)
(51, 0, 112)
(90, 0, -30)

If the badge hunter is at (39, 405, 9) and you are looking for them to be within 5 units (feet) from the marker, then you use binary search to find the badge whose x coordinate is closest to the hunter's x coordinate.  That's (38,200,18).  You then iteratively walk up the list from that point, checking only points whose X coordinate is at least 5 units away.  So the next point is (35, -10, 143).  You check distance to that because x is within 5 of 39.  The next point is (-5,400,7) and your search in that direction is done because the x coordinate is more than 5 units away - it can't be within 5 feet of the hunter, and neither can any other point in that direction.  Now you go back to the match point and search down the list.  So we check (41, 405, 9), and that falls within the distance parameter so we have a match.  For completeness sake, we continue and (51, 0, 112) fails the test (51 is more than 5 away from 39) and our search ends in that direction.

You need to do about nlog2 comparisons to find the closest X point, and then only a few distance comparisons for the few badge locations that are likely to be within range.  In degenerate cases where lots of badges have similar X coordinate, you're at least no worse than you would be doing a full search.  And its a pretty simple algorithm for (probably) a significant speed increase.

[Dyne]

Cool. 

FYI, based on your video commentary I'm guessing you're iterating the location of the badge hunter against a database of all the badge locations in that zone, looking to see if any have a distance less than some minimum radius.

Pretty much exactly that.  The most naive approach in the world, aside from being just barely smart enough to ignore u stanzas coming from itself, coming from people who aren't registered, coming from people who aren't in the pcRoster for whatever reason, containing error responses, or not containing position updates.   

The bot's avatar also checks every update for proximity to maintain a list of nearby users, but that will only be in the one zone.

I didn't think much optimization would be needed until I looked at places like Praetoria.  Imperial City alone has 22 badges (counting the ones that are on the shared borders with Nova Praetoria and Neutropolis) and as many as 12 plaques.  I'm not sure offhand whether there is another zone that is a worse case, but if the badge hunters in that zone were moving around at a combined rate of 30 position updates per second, that would mean performing 1020 distance calculations each second in that one thread.

I will definitely mull your suggestions over and consider how ambitious I am feeling.  I've got some familiarity with binary partitioning due to my Quake map editing days, but it's far more concept than implementation, so this info will be very helpful.  It may take awhile to get around to it though; due to impending vacation and the need to get ready for that, work on the bot will be on hiatus for about two weeks and change.

The radius is specified per-badge and per-plaque, incidentally, so that may add some complexity.  Mostly that's due to a few dozen special cases.  River Rat -- the badge I love to hate -- would, for example, be obnoxiously hard to find with a standard badge radius because there are no badge markers for it at all, and there aren't even landmarks for portions of the set.  The landmarks that do exist are not precise indicators.

[Arcana]

The radius is specified per-badge and per-plaque, incidentally, so that may add some complexity.  Mostly that's due to a few dozen special cases.  River Rat -- the badge I love to hate -- would, for example, be obnoxiously hard to find with a standard badge radius because there are no badge markers for it at all, and there aren't even landmarks for portions of the set.  The landmarks that do exist are not precise indicators.

One interesting thing about using kd-trees is that because you always get the location of the nearest badge to the hunter first, then check to see if its actually in range, you can play Marco Polo.  When someone gets remotely close to a badge location, they could ask the badge bot to give them a "warmer/colder" hint to the closest badge.  They could send a "warmer?" to the bot, and the bot would record their distance to the nearest badge.  If that distance is less than the previously recorded distance (or if this is the first request) the bot would reply "warmer!" and if not "colder!"

[Dyne]

Did a quick script to time some of the methods you mentioned, just out of curiousity.

I used the list of points of interest in Imperial City (with some made-up coordinates for the handful of plaques that don't have them listed on the wiki).  Then I told my script to repeat each search 10000 times, just to avoid tiny tiny fractions of a second.  I was testing against a fixed radius and test coordinate.

Brute forcing through the list of points, analogous to what I'm doing now, takes 0.77 seconds.

Optimizing the list with the X-coordinate method takes 0.39 seconds if I sort the input list every iteration, and 0.27 seconds if I pre-sort the list

I can't compare directly to a KD tree search because I haven't put the actual search portion in yet, but python code for building a kd tree was on wikipedia, so I could at least time that.  1.72 seconds.  I believe that version does sort the input list in place, so I forced it to reusea fresh copy of the input list every iteration and got 1.77 seconds.  I know that scipy has a built-in kdtree, but I'm not sure if it's worth using that.

The numbers I got there would clearly be suboptimal if I had to rebuild the thing on every u stanza, but of course I don't.  Each instance of a Listener or Avatar class remains in one zone, and the list of badges/plaques in that zone remains static unless I tell the bot to refresh its database from my source files.  So I can just build the tree in the class constructor, and rebuild it when and if the database is refreshed.  Therefore, the time to build the tree (or to presort a zone list by x-coordinates) doesn't matter much

Edit: Found a k-d tree implementation that already had nearest neighbor included.    It had a bug that needed fixing, first; I needed to change the median calculation to use integer division (i.e. //) because floats aren't really a thing you should have in string indices.

Benchmarked the search of the tree with that code and got 0.35 seconds, which is in between the two x-coordinate searches (though closer to the high end).  If you search for multiple neighbors, of course, it takes longer.

There's nothing that says I can't use the x-coord optimization for badge proximity but also maintain a k-d tree for something like a Marco Polo command.

[Aoide]

Quick, possibly stupid question regarding this.  Are you going to be doing the 'Praetorian River Swimming' (a.k.a. River Rat) badge?

As is, I can see some similarities to what you're doing for the other badges, especially the History badges (i.e. having to visit specific spots, and hit them all to get the badge).  But on the other hand, it is different in that there's a larger area you could be in to get credit (i.e. almost every spot in those rivers) which could be an issue depending on how resource intensive your Bot is, due to how wide an area has to be covered.

And sorry if I'm being a pain.  But as a badger, I have to admit I'm psyched to see what you're doing, and insanely curious as to what will, and won't make it into what you're doing.

[Arcana]

Quick, possibly stupid question regarding this.  Are you going to be doing the 'Praetorian River Swimming' (a.k.a. River Rat) badge?

Dyne mentioned thinking about how to do that badge, a few posts up.

[Aoide]

Doh.  Don't know how I missed that.  Thank you Arcana!

[Dyne]

Quick, possibly stupid question regarding this.  Are you going to be doing the 'Praetorian River Swimming' (a.k.a. River Rat) badge?

I know Arcana mentioned my previous comments.  Now that I'm back from my trip, I wanted to say that River Rat is, in fact, already working.  It is implemented, however, as 19 individual badges with specific locations (currently named something boring like River Rat 11), each with identical descriptions.  I know this is not how the badge used to work, but duplicating CoH in every detail isn't really my goal; I just want to give people something to do.

These 19 badges are located roughly where Paragon Wiki shows them, as that's the only info I had to go on.  It's still not easy to find some of them, even with a radius many times that of a normal badge, for reasons I mentioned upthread.  Six or so of the badges also straddle the borders between the Praetorian zones, so I use the echoes to handle those cases.

The way echo badges/plaques work is that every badge or plaque can potentially list one echo.  For example, the badge with the key expl-rrat-05a (which is in Neutropolis) has an echo field that contains expl-rrat-05b (the key for a badge in Imperial City that shares the same name, same description, and even the same coordinates because the Praetorian zone maps fortunately all use one coordinate system).  The reverse is also true; 05b specifies 05a as its echo.

Whichever one you earn first -- 05a or 05b -- will automatically credit you with the other.  I think I will probably make Faultline/Echo: Faultline an exception to that, though.  If you really want stuff from Echo: Faultline, you'll have to earn it.  At least you'll have Fly now, so you won't have to suffer what I did to get those coordinates. 

As is, I can see some similarities to what you're doing for the other badges, especially the History badges (i.e. having to visit specific spots, and hit them all to get the badge).  But on the other hand, it is different in that there's a larger area you could be in to get credit (i.e. almost every spot in those rivers) which could be an issue depending on how resource intensive your Bot is, due to how wide an area has to be covered.

While I'll probably eventually add in the ability to see how many of a given set you have, to be honest history badges (as distinct from history plaques) are a low priority.  That's partly because sorting out the completion aspect is a little more complex than "does user have 7 out of 7", but mostly its because the COH client never even knows about or retains anything that you earn with this bot, and the "private message" style UI is a clunky substitute that I use mostly out of necessity.  These sorts of rewards stretch the limits of this a bit more than seems worthwhile.

Instead, something that acts like a meta-reward like this is probably better suited to a web app that accesses the "who has earned what" database and presents a view of your badges that is more like what you used to see in-game.  A proper implementation of River Rat (where you only get the badge after getting all 19 locations) would likewise be more appropriate there, as would achievement badges like Tourist, Collector, Explorer, Pathfinder, and Trailblazer (i.e. "You've earned X badges").

In any case, right now the bot has no concept whatsoever of a "history badge".  Plaques work almost precisely the same way that badges do, except that they don't have individual names.  (Every badge has a hero name, villain name, or both, and I will soon add some logic for deciding what to send based on the faction and gender you've set.  Each plaque just has a field called "monument", and the only manner in which that field is used is when the bot sends it as part of the description.  Of course, badges and plaques all have unique keys, but those aren't really meant to be read by users; they all look much like the two I listed for River Rat above.)

And sorry if I'm being a pain.  But as a badger, I have to admit I'm psyched to see what you're doing, and insanely curious as to what will, and won't make it into what you're doing.

Not a pain at all.  I'm just glad people are interested.  Feel free to ask questions.  Sharing info is why we bot writers make these threads, after all.