TL;DR: Made a website for optimizing Paragon cards using the GNU Linear Programming Kit and Haskell. Code available here.
I love MOBA’s (Dota, LoL, Paragon), and I love Haskell. Since Paragon is my current go-to game, I wanted to determine the cards to buy to maximize my Damage Per Second (DPS).
First things first, I found a spreadsheet of all the cards, colors, costs, and stats. Using some Vim magic, I made them into a list of tuples:
("Wellspring Staff",3,Universal,"6 Power|30 Mana|Fully Upgraded Bonus:30 Mana|0.3 Mana Regen"),
("Whirling Wand",3,Universal,"6 Power|5.5 Attack Speed|Fully Upgraded Bonus:11 Attack Speed"),
Which I parse into a data structure:
data Card = Card
{ _cost :: Integer
, _power :: Integer
, _speed :: Integer
, _crit :: Integer
, _pen :: Integer
, _lifesteal :: Integer
, _crit_bonus :: Integer
, _ward :: Integer
, _blink :: Integer
, _name :: String
, _firstType :: String
, _secondType :: String
, _afinity :: Afinity
} deriving (Show)
makeLenses ''Card
The equation to maximize DPS combines the stats of: power, speed, crit chance, armor pen, crit bonus, and the enemy’s armor.
dmgReduction :: Double -> Double -> Double
dmgReduction enemyArmor penetrationPoints =
let effectiveArmor = enemyArmor - (penetrationPoints * 4.0)
realArmor = if (effectiveArmor < 0) then 0 else effectiveArmor
reduction = (100/(100 + effectiveArmor))
in if reduction > 1 then 1 else reduction
dps :: Hero -> Double -> Double -> Double -> Double -> Double -> Double -> Double
dps hero powerPoints attackSpeedPoints critPoints penetrationPoints critDamage enemyArmor = do
let reduction = dmgReduction enemyArmor penetrationPoints
baseDmg = ((hero^.base_damage)+(6*powerPoints*(hero^.scaling)))
hitsSecond = 1/((hero^.base_attack_time)/(((5.5*attackSpeedPoints) + (hero^.attack_speed))/100))
critBonus = (1+((0.04*critPoints)*(critDamage-1)))
baseDmg * hitsSecond * critBonus * reduction
To speed up the optimization problem, I broke it down into two calculations. First I run the DPS algorithm against all the possible combinations of values with a max total cost of sixty points and six total cards. Since each card gets a bonus when completed with all three upgrades, those counted for extra:
maxDps :: Bool -> Bool -> Bool -> Integer -> String -> Integer -> Double -> Build
maxDps w b cheapCrit lifeSteal hero_name reduce_by en_armor =
let totalPoints = 66 -- counts the bonus +1 of the 6 cards when completed
ward = if w then 1 else 0
blink = if b then 1 else 0
maxPen = if hero_name == "sparrow" then 0 else 30
points = totalPoints - lifeSteal - (3 * ward) - (6 * blink) - reduce_by
totals = [ (calcIfUnder hero_name dmg speed crit pen critbonus points ward blink lifeSteal en_armor) |
dmg <- [0..30],
speed <- [0..30],
crit <- [0..30],
pen <- [0..maxPen],
critbonus <- [0..1]]
build = head $ sortBy (flip compare `on` _bdps) totals
in bcheapCrit .~ cheapCrit $ build
The function calcIfUnder returns a completed Build if the total
card point equaled 60, otherwise an empty Build.
From this, we can quickly calculate the highest possible DPS for any given
character, as a Build of the exact power, speed, crit chance, armor pen,
enemy armor, and crit bonus points needed.
Now that we know the best possible Build, the hard part is figuring out
what cards and upgrades to buy. Using
glpk-hs, I make a tuple of each card with
the possible upgrades for a given stat:
-- For cost (e.g. base cost is 3)
[("Whirling Wand - speed:1,power:5",9),
("Whirling Wand - speed:2,power:4",9),
("Whirling Wand - speed:3,power:3",9), ...]
-- For power (e.g. base power is 1)
[("Whirling Wand - speed:1,power:5",6),
("Whirling Wand - speed:2,power:4",5),
("Whirling Wand - speed:3,power:3",4), ...]
-- For speed (e.g. base speed is 3)
[("Whirling Wand - speed:1,power:5",4),
("Whirling Wand - speed:2,power:4",5),
("Whirling Wand - speed:3,power:3",6), ...]
This turns out to be roughly a few thousand cards+upgrades per stat. Since we
only care about matching a stat exactly, we can use equalTo from glpk-hs:
lpCards :: Build -> LP String Integer
lpCards build = execLPM $ do
let hero = heroFromName $ build^.bhero
let useCheapCrit = (build^.bcheapCrit)
equalTo (linCombination (collectCostAndNameTuples hero _cost useCheapCrit)) totalCXP
equalTo (linCombination (collectCostAndNameTuples hero _power useCheapCrit)) (build^.bpower)
equalTo (linCombination (collectCostAndNameTuples hero _speed useCheapCrit)) (build^.bspeed)
equalTo (linCombination (collectCostAndNameTuples hero _crit useCheapCrit)) (build^.bcrit)
equalTo (linCombination (collectCostAndNameTuples hero _pen useCheapCrit)) (build^.bpen)
equalTo (linCombination (collectCostAndNameTuples hero _lifesteal useCheapCrit)) (build^.blifesteal)
equalTo (linCombination (collectCostAndNameTuples hero _crit_bonus useCheapCrit)) (build^.bcrit_bonus)
equalTo (linCombination (collectCostAndNameTuples hero _ward useCheapCrit)) (build^.bward)
equalTo (linCombination (collectCostAndNameTuples hero _blink useCheapCrit)) (build^.bblink)
equalTo (linCombination (map (\(_,name) -> (1, name)) $ collectCostAndNameTuples hero _power useCheapCrit)) totalCards
mapM (\(_,name) -> varBds name 0 1) $ collectCostAndNameTuples hero _power useCheapCrit
mapM (\(_,name) -> setVarKind name IntVar) $ collectCostAndNameTuples hero _power useCheapCrit
optimize :: Build -> IO [HandCard]
optimize b = do
x <- glpSolveVars mipDefaults (lpCards b)
putStrLn $ "Build" ++ (show b)
case x of (Success, Just (obj, vars)) ->
let cards = (map toHandCard) $ filter (\(name, count) -> count /= 0) $ Map.toList vars
in if null cards then solverFailed
else return cards
(failure, result) -> solverFailed
Running optimize from a scotty site gathers a solution for six
card+upgrade tuples that match the desired ratio, and it is fast enough to run
in under a second!
main :: IO ()
main = do
scotty 3000 $ do
middleware $ staticPolicy (noDots >-> addBase "static/html")
middleware $ staticPolicy (noDots >-> addBase "static/dist")
post "/dps" $ do
s <- jsonData :: ActionM UISetting
json $ DP.maxDps (has_ward s) (has_blink s) (cheap_crit s) (desired_lifesteal s) (hero_name s) 0 (enemy_armor s)
post "/optimize" $ do
build <- jsonData :: ActionM OP.Build
r <- liftIO $ OP.optimize build
json r
Sample output:
And there you have it, a solver for the best DPS cards to build for Paragon for any hero! Code available here.
