Hungarian algorithm for Excel/VBA
http://forum.tribalwars.net/showthread.php?153055-Hungarian-algorit...
User Name
Password
Log in
Remember Me?
Help
~ TribalWars (Game) ~ Game Rules ~ Hall of Fame ~ Statistics ~ TW stats ~ Forum Rules ~ FAQ ~ Forum Search ~ Help ~ Contact ~
Forum
What's New?
Forum Actions Quick Links Advanced Search
New Posts FAQ Calendar Community
Forum
Community Section
Scripts & Independent Tools
Hungarian algorithm for Excel/VBA
Showing results 1 to 20 of 36
Page 1 of 2 1 2
Last
Thread: Hungarian algorithm for Excel/VBA
Thread Tools Search Thread
2009,July 1st, 23:37
#1
capibarbaroja
Hungarian algorithm for Excel/VBA
For those of you who wondered how to get optimal routes between villages, you can use the Hungarian Algorithm, already used by BloodAngel in his attack tool. You might find it very useful to use the code in excel too. Anyways, here is the code; you might as well use the code to other things that have nothing to do with TW to get the most effecient results.
Join Date: Location: Posts:
2007,December 30th France 292
To learn more about this; Clicky. To show an example of how it can be immplemented; here is just a prnt screen of my own attack planner(Target villages are random), which is using the Hungarian algorithm:
For those of you who know VBA, getting your own attack planner tow ork with this shouldnt make any big problem, so; Enjoy Code:
Option Base 1 Sub Munkres() '================================ ' CREATED BY CAPIBARBAROJA. '================================ 'Disclaimer: ' NB: There is no warranty by using 'this Code, use it totally at your 'own risk! 'If you put too many villages in 'attacker and target village you 'might need to close excel without 'saving because it excel might stop 'working. Therefore always remind 'to save the workbook! 'You are free to share this code with 'anybody you wish, or use it in your own 'sheet, always you credit me for this code. '================================ 'Resources: 'http://216.249.163.93/bob.pilgrim/445/munkres.html '================================ '- Declaring for calculating the Hungarian Algorithm Dim C() As Double 'Matrix Dim A() As Integer 'Masked matrix Dim X() As Integer 'Masked matrix for step 5
1 of 9
29/04/2013 10:21 PM
Hungarian algorithm for Excel/VBA
http://forum.tribalwars.net/showthread.php?153055-Hungarian-algorit...
Dim C_cov() As Integer 'Masked matrix to check if columns are covered Dim R_cov() As Integer 'Masked matrix to check if rows are covered Dim saved_col As Integer 'Saving columns that have star in step 5 Dim saved_row As Integer 'Saving rows that have primes in step 5 Dim start_in_row As Boolean 'Done to check if there is a star in row in step 4 Dim Col As Integer 'Step 4 Dim stop_ As Boolean 'To stop step 5 Dim M As Integer 'Columns Dim N As Integer 'Rows Dim Min As Double 'Minimum Dim Max As Double 'Maximum Dim i As Integer 'Columns in for statments Dim h As Integer 'Columns in for statments Dim j As Integer 'Rows in for statements '---------------------------------------'- Declaring for debugging Dim DoDebug As Boolean Dim str As String Dim array_ As String str = "" stepCounter = 0 '---------------------------------------'INSTRUCTIONS: '---------------------------------------M = 3 N = 3 ReDim ReDim ReDim ReDim ReDim 'state how many columns your matrix will have(see NB:) 'state how many rows your matrix will have(see NB:) C(M, N) A(M, N) X(M, N) C_cov(M) R_cov(N)
' Makes space for the arrays/masked arrays to be filled. If 'you delete this statement your code will fail. 'A matrix is created in C() as following '(Create your matrix here): C(1, C(1, C(1, C(2, C(2, C(2, C(3, C(3, C(3, 1) 2) 3) 1) 2) 3) 1) 2) 3) = = = = = = = = = 1 2 3 2 4 6 3 6 9 'Column 'Column 'Column 'Column 1, 1, 1, 2, row row row row 1 2 3 1 of of of of array array array array C C C C equals equals equals equals 1 2 3 2.....
'First number is column in the matrix, second number 'is row in matrix. 'You can make the matrix as big as you wish, but remind, the 'bigger it is, the longer it will take to be done. 'NB: YOUR MATRIX MUST BE SQUARE(same number of columns 'and rows), ELSE THE CODE MIGHT END IN ERROR. 'You must state which of them is the biggest: Max = 9 ' Change 3 by the biggest number in your matrix. '---------------------------------------'------------ GETTING RESULTS ----------'---------------------------------------' When you run this code, the result will be shown in 'immediate window(press CTRL + G to show). Objects marked 'with a star are the most effecient. '---------------------------------------'================================= '===== HUNGARIAN ALGORITHM ======= '================================= '--------------------------------'Debug? - Set DoDebug as True if error, else set as False: DoDebug = False 'Debugging values will appear in immediate window(press CTRL + G to show) '================================= Step_1: 'For each row of the matrix, find the smallest element and 'subtract it from every element in its row. Go to Step 2. For j = 1 To N Min = C(1, j) For i = 1 To M If Min > C(i, j) Then Min = C(i, j) End If Next For i = 1 To M C(i, j) = C(i, j) - Min Next Next '-----------------------------------------If DoDebug = True Then stepCounter = stepCounter + 1 Debug.Print stepCounter & ".- Step 1 done. Next Step 2" End If '-----------------------------------------Step_2: 'Find a zero (Z) in the resulting matrix. If there is no 'starred zero in its row or column, star Z. Repeat for 'each element in the matrix. Go to Step 3. For j = 1 To N For i = 1 To M If C(i, j) = 0 And C_cov(i) = 0 And R_cov(j) = 0 Then A(i, j) = 1 C_cov(i) = 1 R_cov(j) = 1 End If Next Next For i = 1 To M C_cov(i) = 0 Next For j = 1 To N R_cov(j) = 0 Next '-----------------------------------------If DoDebug = True Then stepCounter = stepCounter + 1 Debug.Print stepCounter & ".- Step 2 done. Next Step 3"
2 of 9
29/04/2013 10:21 PM
Hungarian algorithm for Excel/VBA
http://forum.tribalwars.net/showthread.php?153055-Hungarian-algorit...
End If '-----------------------------------------Step_3: 'Cover each column containing a starred zero. If K 'columns are covered, the starred zeros describe a 'complete set of unique assignments. In this case, 'Go to DONE, otherwise, Go to Step 4. Count = 0 For i = 1 To M For j = 1 To N If A(i, j) = 1 Then C_cov(i) = 1 Count = Count + 1 Exit For End If Next Next If Count >= N Then GoTo DONE End If '-----------------------------------------If DoDebug = True Then stepCounter = stepCounter + 1 Debug.Print stepCounter & ".- Step 3 done. Next Step 4" End If '-----------------------------------------Step_4: 'Find a noncovered zero and prime it. If there is no 'starred zero in the row containing this primed zero, 'Go to Step 5. Otherwise, cover this row and uncover 'the column containing the starred zero. Continue in 'this manner until there are no uncovered zeros left. 'Save the smallest uncovered value and Go to Step 6. For j = 1 To N For i = 1 To M star_in_row = False If C(i, j) = 0 And R_cov(j) = 0 And C_cov(i) = 0 Then A(i, j) = 2 save_col = i For h = 1 To M
| Simulator | Rams |
Reply With Quote
2009,July 2nd, 01:02
#2
Sp@rky13
Join Date: Location: Posts: 2009,January 30th At home????? 1,759
Sounds cool. Can you publish your attack planner here? I always wanted to figure out how to do this but didn't understand how you'd deal with coordinates
Reply With Quote
2009,July 2nd, 04:50
#3
King Arturus Yes, please post it. I need an attack planner in excel very much. I think it be much quicker to use because I wouldn't have to reenter my village info all the time. I appreciate it a lot. I have been looking for one but no one has been willing to share one with me yet.
Join Date: Location: Posts: 2008,October 11th Camelot 1,605
Reply With Quote
2009,July 2nd, 10:09
#4
capibarbaroja
3 of 9
29/04/2013 10:21 PM
Hungarian algorithm for Excel/VBA
http://forum.tribalwars.net/showthread.php?153055-Hungarian-algorit...
Join Date: Location: Posts:
2007,December 30th France 292
I still have to finish some bugs
. Will see if I post it when I totally finish the planner
| Simulator | Rams |
Reply With Quote
2009,July 2nd, 10:30
#5
Sp@rky13
Join Date: Location: Posts: 2009,January 30th At home????? 1,759
Ok thank you
Reply With Quote
2009,July 2nd, 14:54
#6
King Arturus Awesome. Thank you very much!
Join Date: Location: Posts:
2008,October 11th Camelot 1,605
Reply With Quote
2009,July 2nd, 18:00
#7
SlowTarget
Join Date: Posts: 2007,August 10th 472
Still trying to get my head around this ... If I want to use this for farming... I guess the best way would be to solve the algorithm for many farms for each village, so if I have 100 villages, find the 1000 farms that are closest to my villages and solve for those - then send farming runs to the best 3 or 4 for each village or am I getting this completely wrong?
DropBox
Reply With Quote
2009,July 2nd, 18:15
#8
Penguin11
Originally Posted by King Arturus
Yes, please post it. I need an attack planner in excel very much. I think it be much quicker to use because I wouldn't have to reenter my village info all the time. I appreciate it a lot. I have been looking for one but no one has been willing to share one with me yet.
Join Date: Location: Posts: 2007,November 20th Up North 1,179
This one I made a while back. It's as basic as you get :P. It goes nowhere near as good as the one capibarbaroja displayed but still does job http://www.mediafire.com/?ynnwiizhzyw BTW it's set for troop speed 1 worlds.
Last edited by Penguin11 : 2009,July 2nd at 22:47 Reason: Posted protected workbook
4 of 9
29/04/2013 10:21 PM
Hungarian algorithm for Excel/VBA
http://forum.tribalwars.net/showthread.php?153055-Hungarian-algorit...
Forum Moderator Forum Rules Ingame Rules Support Ticket PM Me
Reply With Quote
2009,July 2nd, 18:20
#9
inflrc 100 villages for 1000 farms? If I get it right, the algoritm requires a square matrix. Would it be valid to repeat 10 times the villages to fill the rows of the matrix?
Join Date: Posts:
2008,May 16th 540
Reply With Quote
2009,July 2nd, 18:51
#10
capibarbaroja
Originally Posted by inflrc
100 villages for 1000 farms? If I get it right, the algoritm requires a square matrix. Would it be valid to repeat 10 times the villages to fill the rows of the matrix?
Join Date: Location: Posts: 2007,December 30th France 292
Well, what I do is put attacking vilages as the rows, and target villages as columns. If you have 1000 target villages, and 100 attacking villages(rows), you will get the 100 targets where it is fastest to send the attacks. You would have to put 10 attacks for each attaking village, that means you put each attacking cooridnate in the matrix ten times. Then you have 1000 attacking villages and 1000 targets, which will theoretically generate which attacking village should attack which target. The only glitch here is that excel has a very slow programing lenguage, VB, which equals lots of time, or even crashing your computer Therefore blood angel who uses C++ I believe has a much faster code, because C++ > VB, only that you can't immplement C++ in excel So theorically what ST asks for is possible, but in practic; Im not very sure... Also depends on how fast your computer is.
| Simulator | Rams |
Reply With Quote
2009,July 2nd, 20:31
#11
Jack Lawless To you know by any chance the formula to calculate the distance between 2 villages,whit each tip of unit,in case someone wants to make its own attack planner,not an excel base one.I think it was here on the forum,but can't find it:(
Join Date: Location: Posts: 2007,June 14th In the Darkness 597
Reply With Quote
2009,July 2nd, 20:48
#12
Penguin11
Originally Posted by Jack Lawless
To you know by any chance the formula to calculate the distance between 2 villages,whit each tip of unit,in case someone wants to make its own attack planner,not an excel base one.I think it was here on the forum,but can't find it:(
Join Date: Location: Posts: 2007,November 20th Up North 1,179
Distance formula = sqrt((x2-x1)^2 +(y2-y1)^2)
5 of 9
29/04/2013 10:21 PM
Hungarian algorithm for Excel/VBA
http://forum.tribalwars.net/showthread.php?153055-Hungarian-algorit...
Multiply the answer you get by the speed of the unit per field. Format that too date/time. Take that away from arrival time and then you get your launch time.
Forum Moderator Forum Rules Ingame Rules Support Ticket PM Me
Reply With Quote
2009,July 2nd, 22:35
#13
capibarbaroja
Originally Posted by Jack Lawless
Join Date: Location: Posts:
2007,December 30th France 292
To you know by any chance the formula to calculate the distance between 2 villages,whit each tip of unit,in case someone wants to make its own attack planner,not an excel base one.I think it was here on the forum,but can't find it:(
EDIT: Didn't see you said not for Excel xxx|yyy --> aaa|bbb
Last edited by capibarbaroja : 2009,July 2nd at 22:46
| Simulator | Rams |
Reply With Quote
2009,July 2nd, 22:41
#14
Sp@rky13
Join Date: Location: Posts: 2009,January 30th At home????? 1,759
Alright I tried that. I typed this:
CPLANER([410|662], [411|663], [Axeman])
into A1 I put the code in a module and named it cplaner. It didn't work
Reply With Quote
2009,July 2nd, 22:48
#15
capibarbaroja
Originally Posted by Sp@rky13
Alright I tried that. I typed this:
Join Date: Location: Posts: 2007,December 30th France 292
into A1 I put the code in a module and named it cplaner. It didn't work
Without the [ and ] just did that to make it easier to separet each part in the example. Try now, and you will see it works. ALso remember you must type = at the begining of the code for excel to identify it as a function
6 of 9
29/04/2013 10:21 PM
Hungarian algorithm for Excel/VBA
http://forum.tribalwars.net/showthread.php?153055-Hungarian-algorit...
Try
=CPLANER(410|662, 411|663, Axeman)
Remember, you can also use cell references, as if you have 410|662 in cell A1, you can put A1 in the function instead of 410|662. NB: Macro must be enabled ;)
Last edited by capibarbaroja : 2009,July 2nd at 22:51
| Simulator | Rams |
Reply With Quote
2009,July 3rd, 01:11
#16
servy
Originally Posted by capibarbaroja
The only glitch here is that excel has a very slow programing lenguage, VB, which equals lots of time, or even crashing your computer
Join Date: Posts: 2007,March 7th 12,945
Therefore blood angel who uses C++ I believe has a much faster code, because C++ > VB, only that you can't immplement C++ in excel So theorically what ST asks for is possible, but in practic; Im not very sure... Also depends on how fast your computer is.
Yes, VB simply isn't designed to do that kind of number crunching, but what it is fairly well suited for is interacting with other programs, so it wouldn't be that hard to write a program in Java, C++ or another similarly powerful language and then call out to that program via VB. Or just make the entire application in such a language as Excel really isn't very well suited for advanced application interfaces. You can do things like this in Excel, but you can do so much better in something like Java.
1) Support Ticket --- 2) Ingame Rules --- 3) Forum Punishments
Reply With Quote
2009,July 3rd, 02:07
#17
SlowTarget
Join Date: Posts: 2007,August 10th 472
I'm not even sure its the right algorithm for what I need - resource gathering... This matches workers to jobs... and makes sure that every job gets done... whereas I'm not particularly bothered if a particular farm doesnt get cleared - because a closer one got chosen. The farms that aren't going to be used are in the matrix and will affect the ultimate result. And the 10th farm for one village might be right next door to another village - but get assigned to the further village - as this algorithm is trying to reduce the total cost of the solution... rather than just the cost of the best few jobs per worker... There's probably another algorithm out there thats a better match for what I need.
DropBox
Reply With Quote
2009,July 3rd, 06:21
#18
Sp@rky13
Join Date: Location: Posts: 2009,January 30th At home????? 1,759
Alright, i've tried it but get an error. I put the code in a module and named it CPLANER. I use exactly what you posted above:
=CPLANER(410|662, 411|663, Axeman)
EDIT: Macros are enabled
Last edited by Sp@rky13 : 2009,July 3rd at 07:24
7 of 9
29/04/2013 10:21 PM
Hungarian algorithm for Excel/VBA
http://forum.tribalwars.net/showthread.php?153055-Hungarian-algorit...
Reply With Quote
2009,July 3rd, 10:52
#19
capibarbaroja
Originally Posted by Sp@rky13
Alright, i've tried it but get an error. I put the code in a module and named it CPLANER. I use exactly what you posted above:
Join Date: Location: Posts: 2007,December 30th France 292
EDIT: Macros are enabled
Sorry, i tried it my self, and found the error; You will have to do this
=CPLANER("410|662","411|666","Axeman")
Or better, use cell references, which is what I do, as put 410|662 in cell A1, 411|666 in B1, and Axeman in cell C1. In cell D1 type:
=CPLANER(A1,B1,C1)
| Simulator | Rams |
Reply With Quote
2009,July 3rd, 11:20
#20
Sp@rky13
Join Date: Location: Posts: 2009,January 30th At home????? 1,759
Doesn't come up with the same error but now has a #name? error in the cell EDIT: If easier, maybe just post it with it working (with just the 1 cell with the formula in it and the module). Also I'm using 2007 if that affects it
Last edited by Sp@rky13 : 2009,July 3rd at 11:36
Reply With Quote
Page 1 of 2 1 2
Quick Navigation
Scripts & Independent Tools
Last
Top
Previous Thread | Next Thread
Posting Rules
You You You You
may may may may
not not not not
post new threads post replies post attachments edit your posts
BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Forum Rules
All times are GMT +1. The time now is 13:18.
8 of 9
29/04/2013 10:21 PM
Hungarian algorithm for Excel/VBA
http://forum.tribalwars.net/showthread.php?153055-Hungarian-algorit...
Powered by vBulletin Version 4.2.0 Copyright 2000 - 2013, Jelsoft Enterprises Ltd.
-- TribalWars
InnoGames Tribal Wars Contact Us TribalWars Archive Top
9 of 9
29/04/2013 10:21 PM
