Boards›Teamfight Tactics

Dear TFT devs, here's a CS algorithm to improve your AI pathing

CowZow·7/9/2019, 4:55:18 AM·54 votes·14,183 views

Dear TFT devs,

I have a suggestion which can help improve the AI pathing of champions in TFT. It's called the Hungarian Algorithm.

the tl;dr for your devs is: create a bipartite graph with your champions matching champions with destinations; give each matching a score; then run the hungarian algorithm to maximize the sum of score - that is the optimal way champions should move each turn.

Problem statement

There are times where the pathing messes up in the game. This is usually caused in the following situation: https://imgur.com/RkXtx8X

The optimal way for your green units to move is this: https://imgur.com/3T2Aoho

However, sometimes your units move like this, which causes one guy to get stuck for a bit: https://imgur.com/ilxYeLh

How do you solve this?

Its easy, first convert the hexagon representation of the map into a "graph". A graph is something that creates relationships between objects called nodes. When you see the graph of the map you'll see it makes sense: https://imgur.com/WfuNz6J

You see that every champion is on the left side, and a line matches it to its possible destination on the right hand side. All the edges that connect champions with destinations moving closer to the enemy are marked with 1, destinations where the champion stay still is marked with 0, and destinations moving backwards is -1.

So with a graph like this, you want to match each champion with a destination. If you maximize the SUM of all the edges chosen, you will maximize the number of champions that moved towards an enemy each turn. The optimal assignment becomes this: https://imgur.com/hb0mxND

And what algorithm solves maximizing the sum of edges? Hungarian algorithm.

Not sure if this approach has been considered yet or works for the devs. But maybe this will help you towards an optimal solution.

Best regards

14 Comments

KFCeytron7/9/2019, 6:21:54 AM24 votes

Keep in mind that the algorithm Riot chose for loading progress was to take the average of all players' load progress, giving us a jump to 90% followed by a slow crawl to 100% as the one guy on a toaster loads the game, rather than simply using the lowest individual number, which is what actually determines when the game loads. Your suggestion might be a bit too much for them.

Romans VI XXIII7/9/2019, 2:16:48 PM5 votes

Don't count on it, they cant even get Minion AI to work correctly, let alone a more intelligent AI for TFT.

DUDE BRO7/9/2019, 5:43:47 AM4 votes

How do you solve this? https://youtu.be/vBTtplzy_Gc?t=84

Porglit7/9/2019, 1:08:49 PM3 votes

This is perhaps the best post on the forums right now.

UnstoppableMaybe7/10/2019, 2:54:20 AM1 votes

I don't have a problem with Riot personally, but I must admit it's a bit cowardly of them not to give this guy some credit here in the comments, for the amount of effort he put in here to help suggest a fix to the problem, even if the images were not his own for the solution lol! I usually find that the developers struggling to make profit on their games before being shutdown, usually they also don't recognize their fan-base that supports them, and they don't acknowledge their mvp supporters. I think it has to do with their egos making them think they can get away with more, and nobody else deserves personal credit unless they work on the game itself as well. It may seem selfish of them, but I can also understand the team rushing to get the projects done that they want, so no responding to comments on the web at all is always an option for them so nothing seems unfair to others, while avoiding progression interference. However, I do feel they can at least take some time to go through and recognize the very few who do post brilliant supportive suggestions few and far between, especially since they put in the time to share the support!

I definitely agree that the minion AI can be a pain to navigate around, to a point where champion players are getting stuck in a crowded cluster of minions to where they start twitching like a mad glitch, and cannot move, which sometimes leads to their absurd death! This should be fixed asap as well, since it occurs in every mode of League of Legends, including ranked. The reason clearly being that the ally minions don't adjust their path, unless you are in the way, and when you are, it becomes obvious the assigned path and coding is sloppy to a point the ally minions are constantly in the champs way as the player navigates through their path. They need to get out of the way a little before the champion arrives, and not as soon as they arrive.

Getting stuck in a cluster of minions sucks, and can be an easy fix if they add some new code to allow them to adjust just before champion arrival, instead of once they arrive.

anjogrTest7/11/2019, 6:38:23 PM1 votes

This is an awesome post. I noticed the pathing was wonky when I was doing the "6 pieces" quest with knights. Thanks for putting this together, it was really interesting; just wanted to do my part to keep it at the top.

Separately, a shameless plug: if you like mathy posts, you might want to check out this one, where I talk about the differing interactions between players and the RNG in LOL as opposed to TFT; I'd love to hear what you guys all thought on the matter.

https://boards.na.leagueoflegends.com/en/c/teamfight-tactics/HYxMA7TI-thoughts-from-a-cut-rate-mathematician-and-an-even-worse-gamer

Hellmaximus17/9/2019, 8:42:06 PM1 votes

Lowkey, this is a really good roast against Riot's Game Devs

Jennifer4207/9/2019, 10:47:43 PM1 votes

wow here i was ready to write some mean but 100% true comment about riots stupidity and their minion ai alone, but it alrdy was done. well rip.

ModThe Djinn7/10/2019, 12:39:17 AM1 votes

I suspect that part of the reason this sort of thing isn't in use is that champions do not all move at the same times, and often have to move further than optimizing one square movements. As a result it might be more realistic to have each champion using its own movement algorithm (such as A-Star) that only applies when it's actively looking to move. This would lead to situations where a unit does identify path A and path B as equally valid and selects one of them under some situations (like the example you provided), but would likely be a better solution to other movement situations (as deciding destination squares won't help with pathing through multiple hexes that could be occupied, while A-Star or alternatives can).

Now, could you implement some sort of system that has the benefits of both? Almost certainly. The question is what tradeoffs you need to make to do so.