Question Walk time optimalizer

DeletedUser

Guest
Dear readers,

As you see I just signed up on this forum. I am a player from the Dutch Tribalwars server. [Player Stats].

I have been searching for a tool that makes walk time between a large amount coordinates as short as possible. I couldn't find the one I needed, so I turned to .net cause I know the scripting pro's are located here:icon_cool:

This is what I am looking for:
I am farming on a large scale and I want to know the best way to farm so that the walk times are as low as possible. I want to fill in a list of coordinates from my own account, and from my farms. Then there should be an output that says something like 'this village should farm these farms'. This must be possible on a large scale because I farm 1000+ villages. This is the reason why I cant use regular mass attack planners. The unit speed or world speed doesn't matter.

Does anybody have a website, program or excel file that can calculate this? Or any ideas for how to make this?

Thnx!
 

A humble player

Guest
Dear readers,

As you see I just signed up on this forum. I am a player from the Dutch Tribalwars server. [Player Stats].

I have been searching for a tool that makes walk time between a large amount coordinates as short as possible. I couldn't find the one I needed, so I turned to .net cause I know the scripting pro's are located here:icon_cool:

This is what I am looking for:
I am farming on a large scale and I want to know the best way to farm so that the walk times are as low as possible. I want to fill in a list of coordinates from my own account, and from my farms. Then there should be an output that says something like 'this village should farm these farms'. This must be possible on a large scale because I farm 1000+ villages. This is the reason why I cant use regular mass attack planners. The unit speed or world speed doesn't matter.

Does anybody have a website, program or excel file that can calculate this? Or any ideas for how to make this?

Thnx!
Just use something like Tribalwarsfarmreport. It does what you want, but better.
 

DeletedUser

Guest
Just use something like Tribalwarsfarmreport. It does what you want, but better.

I dont want that, I have better things for that..
I want to use it at other things too. I bet it's not that hard cause it's used in all attack planners.. I only want a simple version that just calculates the best village combinations.
 

Stotty2009

Guest
I dont want that, I have better things for that..
I want to use it at other things too. I bet it's not that hard cause it's used in all attack planners.. I only want a simple version that just calculates the best village combinations.

What you are asking for wont be simple as you are requiring to do a lot of calculates of the Hungarian Algorithm, which I can do on a piece of paper, but I just can't do it in a programming language lol

If it was simple, I would happily do it for you, but I wouldn't suggest doing it in excel as it will crash lol
 

DeletedUser

Guest
What you are asking for wont be simple as you are requiring to do a lot of calculates of the Hungarian Algorithm, which I can do on a piece of paper, but I just can't do it in a programming language lol

If it was simple, I would happily do it for you, but I wouldn't suggest doing it in excel as it will crash lol

Aww that's too bad :( Yeah I have read about the Hungarian Algorithm but I also can't figure out how to put it in excel..

I also downloaded your excel file called: 'Example' (the thing that calculates something like walk times).

1A = first coordinate
1B = second coordinate (target)
1C = Unit
1D = Some kind of number, that get bigger when I choose for longer distances.

I was thinking, maybe it's possible give excel a list of coordinates and a list of target coordinates and do the same calculation then, but then the output number (1D) should be as low as possible.

This is the same system as the one I want, right?

I can re-upload the file if you want to, but I think you know what I'm talking about.

Thnx for replying, I read alot of your posts and u must be the king of Excel programming ^^
 

A humble player

Guest
Aww that's too bad :( Yeah I have read about the Hungarian Algorithm but I also can't figure out how to put it in excel..

I also downloaded your excel file called: 'Example' (the thing that calculates something like walk times).

1A = first coordinate
1B = second coordinate (target)
1C = Unit
1D = Some kind of number, that get bigger when I choose for longer distances.

I was thinking, maybe it's possible give excel a list of coordinates and a list of target coordinates and do the same calculation then, but then the output number (1D) should be as low as possible.

This is the same system as the one I want, right?

I can re-upload the file if you want to, but I think you know what I'm talking about.

Thnx for replying, I read alot of your posts and u must be the king of Excel programming ^^

But what you want isn't the lowest possible for each, it is the lowest total where each farm goes to a different village. This requires the hungarian algorithm, which is a pain to code anywhere.
 

DeletedUser

Guest
But what you want isn't the lowest possible for each, it is the lowest total where each farm goes to a different village. This requires the hungarian algorithm, which is a pain to code anywhere.

Yeah I understand.

What I mean is the thing you say, all targets have to be attacked (like attack planner). The highest walk time that is calculated, must be as low as possible, while all coordinates are used.
 

DeletedUser

Guest
Ah hungarian....

Insane, have you heard of bookmarking? And I would have a look at twfarmreport before I dismissed it...
 

dalesmckay

Guest
I'll have a crack at the Hungarian implementation once I get some free time.
100+ hours a week working is current smashing me, so I haven't done much with scripting lately.
 

A humble player

Guest
I'll have a crack at the Hungarian implementation once I get some free time.
100+ hours a week working is current smashing me, so I haven't done much with scripting lately.

Oh god...I wish you luck with hungarian (there are a few existing versions out on the google codeplex if you want to steal some), but none are perfect.
 

Subwind

Guest
I have a database that will do it. It's very slow though, I mean, you are asking that every single player village is compared against every single target barb.

For my tribes current war, 41,053 villages vs 24,258 villages = 995,863,674 calculations just to find the village distance for each village.

My war planner, I can get it down to under 60 seconds now for player vs tribe, which is not bad.

Then you want to allocate each village with it's closest, then cross that one off, then calculate all the villages again, minus the selected ones.

I would hate to try to number the total amount of calculations needed....

~Matt
 

DeletedUser

Guest
I have a database that will do it. It's very slow though, I mean, you are asking that every single player village is compared against every single target barb.

For my tribes current war, 41,053 villages vs 24,258 villages = 995,863,674 calculations just to find the village distance for each village.

My war planner, I can get it down to under 60 seconds now for player vs tribe, which is not bad.

Then you want to allocate each village with it's closest, then cross that one off, then calculate all the villages again, minus the selected ones.

I would hate to try to number the total amount of calculations needed....

~Matt


How is your war planner coming btw? Any updates. I was impressed with your first version. Very nice tool.
 

dalesmckay

Guest
[SPOIL]I have a database that will do it. It's very slow though, I mean, you are asking that every single player village is compared against every single target barb.

For my tribes current war, 41,053 villages vs 24,258 villages = 995,863,674 calculations just to find the village distance for each village.

My war planner, I can get it down to under 60 seconds now for player vs tribe, which is not bad.

Then you want to allocate each village with it's closest, then cross that one off, then calculate all the villages again, minus the selected ones.

I would hate to try to number the total amount of calculations needed....

~Matt[/SPOIL]

This is what I would expect the Hungarian algorithm to optimize.

I had a very quick look at it last night.
From what I can tell, you would create a matrix of (source villages) vs (target villages) and assign the distance as the "weight".

So the input for the algorithm would be something like this:
[SPOIL]
Screen%20Shot%202012-03-13%20at%209.43.50%20AM.png
[/SPOIL]

Obviously the matrix would be much larger if you increase the number of source/target villages.

NOTE: it would be a little more complicated if you also wanted to factor in Unit speed.

I found a nice simple C# implementation of the Hungarian Algorithm.
So I will either convert this to jQuery or write an external web tool as a Silverlight application.

Edit:
Well that sucked... it took 5 minutes and 4 seconds to calculate a 1000 x 1000 matrix in C#
Almost have a javascript conversion done, but it's not responding at the moment and being a pain to debug.
 
Last edited:

DeletedUser

Guest
If anybody is interested I have a VBA(excel macro) version of the Hungarian algorithm(Munkres)...
 

DeletedUser

Guest
This is what I would expect the Hungarian algorithm to optimize.

I had a very quick look at it last night.
From what I can tell, you would create a matrix of (source villages) vs (target villages) and assign the distance as the "weight".

So the input for the algorithm would be something like this:
[SPOIL]
Screen%20Shot%202012-03-13%20at%209.43.50%20AM.png
[/SPOIL]

Obviously the matrix would be much larger if you increase the number of source/target villages.

NOTE: it would be a little more complicated if you also wanted to factor in Unit speed.

I found a nice simple C# implementation of the Hungarian Algorithm.
So I will either convert this to jQuery or write an external web tool as a Silverlight application.

Edit:
Well that sucked... it took 5 minutes and 4 seconds to calculate a 1000 x 1000 matrix in C#
Almost have a javascript conversion done, but it's not responding at the moment and being a pain to debug.

Dale want to work together on this I already have a working version in JavaScript I am currently working on speeding it up.

Currently what it can do is both floats and integers but integers are much faster(I just take the distances and multiply them by 10 or 100 then round). I haven't tested rectangular matrix's in a while but at one point they did work.

Max speeds are currently about(these speeds include a debugger I added so without the debugger they could be 10% faster)
100 x 100 = less than a second
200 x 200 = 4 seconds
500 x 500 = 55 seconds
1000 x 1000 = 30 minutes (Don't know how accurate this is as only have done one of these for obvious reasons)


These scripts at this point are only useful to scriptwriters :(

Version one
-It works but...
-Huge memory leak problem
-Only to be looked at if you want to see an earlier evolution of the script

Version two
-Memory leak problem still their
-Still has debugger built in
-It works like this
FindAssignments([array of village coords],[array of target coords])=an array where the index = target and value = village

Version three
-The best currently working version
-Memory leak problem gone

Version four
-still ironing out bugs
-trying to turn the variable masks into three variables zeros, primes and stars.
-better output

Test site
-Runs version three
-Give you an idea of the speeds we are talking about
 
Last edited by a moderator:

dalesmckay

Guest
I'm overseas for work for the next 3 weeks, so won't have time to do anything until I get back.
 

DeletedUser

Guest
Dale want to work together on this I already have a working version in JavaScript I am currently working on speeding it up.

Currently what it can do is both floats and integers but integers are much faster(I just take the distances and multiply them by 10 or 100 then round). I haven't tested rectangular matrix's in a while but at one point they did work.

Max speeds are currently about(these speeds include a debugger I added so without the debugger they could be 10% faster)
100 x 100 = less than a second
200 x 200 = 4 seconds
500 x 500 = 55 seconds
1000 x 1000 = 30 minutes (Don't know how accurate this is as only have done one of these for obvious reasons)


These scripts at this point are only useful to scriptwriters :(

Version one
-It works but...
-Huge memory leak problem
-Only to be looked at if you want to see an earlier evolution of the script

Version two
-Memory leak problem still their
-Still has debugger built in
-It works like this
FindAssignments([array of village coords],[array of target coords])=an array where the index = target and value = village

Version three
-The best currently working version
-Memory leak problem gone

Version four
-still ironing out bugs
-trying to turn the variable masks into three variables zeros, primes and stars.
-better output

Test site
-Runs version three
-Give you an idea of the speeds we are talking about

Would it be faster if you translated all this to C and then had the script sit on a webserver and have php call the script and pass the village variables? I'm not sure how much time it'll save but it should be faster than straight JavaScript.

P.S. If you need a webserver to test my suggestions just let me know, I could give u some small access to mine.
 
Last edited by a moderator:

dalesmckay

Guest
Would it be faster if you translated all this to C and then had the script sit on a webserver and have php call the script and pass the village variables? I'm not sure how much time it'll save but it should be faster than straight JavaScript.

P.S. If you need a webserver to test my suggestions just let me know, I could give u some small access to mine.

This is not something I would recommend doing on the server side.
It would only take a few Users to kill your server with the amount of resources required to perform the large calculations.

I already have a working C# implementation that seems to run the fastest so far.
So I'll look at putting a Silverlight/XAML frontend on it so it can execute the C# code locally on the Client machines.

I still have an extremely heavy workload, so dunno when I'll have time to look into this.
 
Top