Tuesday, November 17, 2009

-2o1o- DotA Assistant

Introduction
DotA Assistant is a program fully built in Java, with pixel scanning merchanism as the core. It's meant to work alongside with Warcraft III : DotA, with the features listed as follows:

Main features :
  • Detecting opponent heroes and notifying the user when the program loses vision of the heroes in the minimap
  • Assessing the battling ability of heroes and displaying the probability of one hero winning another to the user

Note : Bear in mind that this program is still heavily being tested and the information produced are therefore susceptible to inaccuracy.


The Hero Detection System

At the beginning of the game the program will scan the minimap and register the hero when its found by the scanner.



When any of the registered heroes appear to be missing, the user will be notified by the program about the absence of the hero.



The hero will also be notified when the hero is no longer absent.



The Hero Assessment System
The hero assessment system basically retrieves the attribute information of the hero(es) and produces useful information such as the effective hitpoints, attack cooldown, amount of time needed for a hero to kill another hero, and the probability of a hero winning another hero.

(The timer starts at the moment the projectile of my hero's shot reaches my opponent)

The screenshot above demonstrates the output produced by the hero assessment system. Pay more attention to the fourth line counting from the bottom, Amount of time needed for Drow Ranger to kill Dwarven Sniper and the magnified timer on top(click on the ss if you're unable to view it in full).




The magic of mathematics,
31 + 15.84 = 46.84s = 47s(as shown in the screenshot)



Note : The information produced only serve as a benchmark for the user to gauge the battling ability of the selected hero. By the program telling me that my hero needs 15.84s to kill my opponent DOES NOT mean that my hero would take that amount of time to kill the hero when it comes to real-play situation.


Nature of the program
It's always more interesting when it comes to the conceptual explanation of any of the -2o1o- grand releases because their true beauty and elegance do not come from the output it produces to the user, which I've briefly covered some of them above; it conversely comes from the inner design of the program: the robustness of algorithm, the style of programming logic, the control flags, the playaround of APIs. These are the few elements, which forms the core, the foundation of the program.

Please do not feel perplexed as you scroll down and read the walls of technical terms/graphical illustration. Trust me, its not as hard as it seems if you have the foundation in programming; you just have to be ready work with pixels and myriads of RGB codes

This program technically encompasses of three main modules:
  • The Minimap Scanner
  • The Name Scanner
  • The Attribute Scanner


The Minimap Scanner

The program uses Robot API to create an image capture at the minimap region of the screen(captured image as shown in the picture above). Initially the program was set to scan at an incremental value of 3 for both the x and y value each time it moves, it was however being found out that the algorithm could not achieve the intended accuracy after performing several stages of testing.

For the sake of producing promising information to the user(I would not say its 100% accurate but at least the inaccuracy is pardonable), I've decided to use the performance-accuracy tradeoff approach. The accuracy of the scanner was increased at the expense of the CPU performance by decreasing the incremental value for both x and y from 3 to 1, thus proportionally increasing the number of pixel scans from 4333 1/3(195 x 200 / (3x3)) to 39000(195 x 200 / (1x1)) scans for each cycle(195 x 200 is the size of the minimap).

Note : For users with low computer performance, the minimap scanner will hog a considerable amount of CPU usage whenever its scanning takes place. I'll revise the algorithm so that it overcomes such deficiency if there's a high demand from the users.

Once the program found a pixel containing the RGB value listed in the predefined sets of RGB range, it will register the found pixel as an identifier of a player, in accordance with the player number set for the predefined range of RGB codes

If any of the opponent heroes happens to be missing from the sight of the user or his/her allied units, the mini dot corresponding to the missing hero would likewise be missing from the minimap. This event would render the minimap scanner unable to scan for the missing hero range of RGB codes, thus making it consider the hero missing from the map. When this happens, the Robot API typeMessage() method would explicitly be invoked by the program to send a message notifying the user regarding the absence of the hero.


The Name Scanner
Its the human's nature for being able to recognize the letters at a glance, irregardless of how badly written the letter is or how much the letter deviates from its actual style. This is also the main reason why image verification mechanism become one of the most powerful and prominent security measure in the world.

But let's face it, computer processes at a speed where not even millions of our human brain could beat it. When it comes to character recognition, I certainly do not deny the fact that the computer may not be able to recognize letter as good as the human at first; but when its crafted with a well structured algorithm defining the technical way of recognizing the letters in procedural manner, it's not a total impossibility for a computer attain the same level of character recognition as the human. When this stage is achieved, the level and amount information a computer produces over time could far surpass the human.

I crave your pardon for being slightly out of topic, but this is exactly what's on my mind before it comes to the development of the scanners, especially the name and attribute scanners. You see, being able to analyse up to 10k characters and generating up to thousands lines of information per sec to the user, I believe that it's not beyond the bounds of possibility for a player to play DotA in a complete flawless style. Let's get back on topic, introducing you the second core module of the program - the name scanner.


Similar to the aforementioned minimap scanner, the name scanner uses Robot API to capture an image of the region which contains the level and the name of hero.


The only difference is that the y value works as a baseline and remains as a constant whenever the name scanner does its scanning, whereas the value of x changes as the scanner pointer moves. The scanner travels on x axis, on the basis of pixel by pixel, ignores every black pixels it come across and stops at the point where a white pixel is detected.

Take the picture above as an example, the first point, with the coordinate being (538,733), is the point where the scanner stops(we call it the point of origin) to scan for the pattern of the character it stops at(in this case its the letter L), and compares with the predefined pattern points to determine what letter it is.



The letter which resides on the point of origin has to match all the predefined pattern points before it's being recognized as the corresponding letter. For simplicity's sake, I'll omit 8 out of 12 of the pattern points for the letter L, leaving only 4 pattern points to be discussed.

Note : the combination of both integer value x and y form a pattern point which denotes the distance of the pattern point from the point of origin.

Since 8 of the pattern points for the letter 'L' have been omitted, lets just deny their existence. Don't look at them, don't even think of the purpose of them being there; just focus on the four points circled in red.

Note : The coordinate system in computer does not work the same as the Cartesian coordinate system, the decrement of value y in the computer system indicates that the point is moving upwards instead of downwards. In another word, the smaller the value y of a point, the higher the position of the point in the computer coordinate system.



The scanner begins by checking the first pattern point for the letter 'L', (0,-4). If the pixel 0 x and -4 y distance away from the origin is a white pixel the scanner will proceed to the second pattern point; if its a black pixel, the scanner directly negate the possibility of the letter being 'L'. In this case the origin is (538,733) and the pixel at the position 0 x and -4 y distance away from the origin is not a black pixel.

Next, the scanner will check the second pattern point for the letter 'L' (1,-4).
Similar to the concept above, if the pixel at the position 1 x and -4 y distance away from the origin is not a black pixel, the program will preserve the possibility of the letter being 'L' and continue to check for the next pattern point.

The process repeats until the scanner reaches the last pattern point.
If every of the pixels scanned does not appear to be a black pixel to the program, the program will recognize the letter as the corresponding letter(in this case the program will recognize the letter above as a 'L').


The character precedence
Now we've finished about the character recognition part; the program could now recognize the letters individually if we supply the pattern points as a guideline for the program, but what happens if the program tries to recognize letters bearing a resemblance to another letter?

For instance, the letter c could be recognized by the program as an 'e' and the letter l could be recognized by the program as a 'L', owing to the fact that the letter e and l have all the pattern points for the letter c and L respectively. When the scanner scans the line of text 'Level 1 Bone Fletcher' it will produce the output Llecvecl 1l Bocnec Fllectlchlecr.




A simple workaround for this is to specify a set of precedence for every of the letters bearing a resemblance to another letter. Taking the first part as an example, if the scanner scans and recognizes a letter being both letter a and i, it will negate the possibility of the letter being 'i' because logically the letter a has more pattern points(more pixels) compared to the letter 'i'.


The Attribute Scanner

The attribute scanner does not differ much from the name scanner except that instead of having only one baseline, the attribute scanner scans on 5 different elevation of y axis. After the translation of pixels to numbers, the translated numbers will be passed to the DotALogic class to process other information which the users may deem useful, such as the EHP, DPS, AC, damage reduction, hp regen, mp regen. The formulas to perform calculation as such are listed as follows:

Assume that
Average Damage = avgDmg
Minimum Damage = minDmg
Maximum Damage = maxDmg
Additional Dmg = addDmg
Total Dmg = totalDmg
Attack Cooldown = AC
Damage per second = DPS
Effective HP = EHP
Hit point = HP
Time needed to kill = TNTK
Probability of winning = PoW
Additional Agility = addAgi
Damage Reduction = dmgReduction
Additional Armor = addArmor;
Hero1 = First hero to be compared
Hero2 = Second hero to be compared


avgDmg = (minDmg + maxDmg) * 0.5


totalDmg = avgDmg + additionalDmg


AC = baseAC / (1 + ((agi + addAgi) * 0.01))


DPS = (addDmg + avgDmg) /AC

DPS = (addDmg + avgDmg) / ( baseAC / (1 + ((agi + addAgi) * 0.01)))
dmgReduction = 1 - (1 / (1 + ((armor + addArmor) * 0.06)))


EHP = HP/damageReduction

EHP = HP / 1 - (1 / (1 + ((armor + addArmor) * 0.06)))


Hero1.TNTK = Hero2.HP / ((Hero1.totalDmg * (1-Hero2.dmgReduction / Hero1.AC) )-Hero2.HPRegen)

Hero1.TNTK = Hero2.HP / (((((Hero1.minDmg + Hero1.maxDmg) * 0.5) + Hero1.additionalDmg) * (1-(1 - (1 / (1 + ((Hero2.armor + Hero2.addArmor) * 0.06)))) / (Hero1.baseAC / (1 + ((Hero1.agi + Hero1.addAgi) * 0.01)))) )-Hero2.HPRegen)


Hero2.TNTK = Hero2.HP / ((Hero2.totalDmg * (1-Hero1.dmgReduction / Hero2.AC) )-Hero1.HPRegen)

Hero2.TNTK = Hero1.HP / (((((Hero2.minDmg + Hero2.maxDmg) * 0.5) + Hero2.additionalDmg) * (1-(1 - (1 / (1 + ((Hero1.armor + Hero1.addArmor) * 0.06)))) / (Hero2.baseAC / (1 + ((Hero2.agi + Hero2.addAgi) * 0.01)))) )-Hero1.HPRegen)


Hero1.PoW = 1 - Hero1.TNTK / Hero1.TNTK + Hero2.TNTK

Hero1.PoW = 1 - (Hero2.HP / (((((Hero1.minDmg + Hero1.maxDmg) * 0.5) + Hero1.additionalDmg) * (1-(1 - (1 / (1 + ((Hero2.armor + Hero2.addArmor) * 0.06)))) / (Hero1.baseAC / (1 + ((Hero1.agi + Hero1.addAgi) * 0.01)))) )-Hero2.HPRegen)) / ((Hero2.HP / (((((Hero1.minDmg + Hero1.maxDmg) * 0.5) + Hero1.additionalDmg) * (1-(1 - (1 / (1 + ((Hero2.armor + Hero2.addArmor) * 0.06)))) / (Hero1.baseAC / (1 + ((Hero1.agi + Hero1.addAgi) * 0.01)))) )-Hero2.HPRegen))+(Hero1.HP / (((((Hero2.minDmg + Hero2.maxDmg) * 0.5) + Hero2.additionalDmg) * (1-(1 - (1 / (1 + ((Hero1.armor + Hero1.addArmor) * 0.06)))) / (Hero2.baseAC / (1 + ((Hero2.agi + Hero2.addAgi) * 0.01)))) )-Hero1.HPRegen)))


Future enhancement

  • Item recognition
    I've already completed coding the algorithm its just that the process of extracting up to 3k sets of item RGB codes is a big hurdle for me, even with the assistance of an API written intentionally for this purpose.
  • Skill prediction
    To calculate the damage and predict the sequence of skill the opponent will use on the user's hero
  • Enhanced version of hero assessment system
    Enhanced version of hero assessment version will take orb effects such as critical strike, life steal and bashing into account.
  • Performance
    The current algorithm scans up to 500k or even 1 million pixels per second would gradually lead to CPU exhaustion, it needs to be revised and rewritten.


(a screenshot of the database for item recognition module in 0th Normalization Form 0NF)

I won't release the executables or the source code anytime soon because currently the codes are still at the level of content coupling and commucational cohesion and furthermore there are still lots of architectural revision to be made.