You are not logged on | Login | Register  
TCL shortest path algorithm

 
PKooijman

Any of you guys use an algorithm like this in youre robots?

Id like to use it in one of my own. But i suck too much at programming to build it from pseudo code in tcl. I'd appreciate it if i could get the code for that.
Otherwise could you point me to some sites that have an algorithm like this listed? I cant seem to find anything for the TCL language...

 
YouDieNow

Look at Asiabot. It's not a shortest path algorithm but it does find a path to attack every country on the map. But it's sloppily written, so it may be hard to read.

 
PKooijman

Yes, i saw that code, the stuff with all the vertices? I think i got lost on the 11th nested loop :-)

 
YouDieNow

haha

 
RadiKaal

I tried to make it...and I will try to make it again. It takes hours to make that...so I don't share it. The problem I had is that at a given moment it takes very much time to make the calculations. So I need to program it more efficiently.

 
Jp

Radikaal, does your version have a fixed start and end point or is one of them (or both) variable?

 
Jp

Hehe, ic u tried my crash bots ;-)

 
YouDieNow

I just made one last night... it works perfect. It gives the shortest path. But what I really need to do is make one that gives the easiest path (least armies).

 
RadiKaal

It depends, I used to use it to attack a continent. So in that case it had as end point one of the borderstates. The start point was variable.

 
Jp

I think mine works similar: give it a country to attack and it finds with what country to start and what path to take so it ends up with the most armies on that country.

 
RadiKaal

Yup that's the big picture.

 
YouDieNow

Now I got one that gives the easiest path. It's the path with the least armies on it from point A to point B, even if it has to go all the way around the world to do it. It's pretty short too. 56 lines. And it's fast. I'm not sure if I want to share it yet. I don't want to give my competition an edge. Watchout bluejay. Watchout Tiffany. I'm coming for you.

 
bodycount

Now thats the beauty of opensource: You can all feed off one anothers complicated routines and build a better robot for it and the players are the ones that get the profit from that.

ive got a 7 or 8 procedure routine that calculates all the player strengths, and a routine that finds the most likely place of a cap for each player in the game...

So lets trade!

 
YouDieNow

I was hoping something would be brought to the negotiating table. Here's what I got:

- A shortest path algorithm. Works 100%
- A path algorithm that gives the path with the least armies from point A to B. Also works 100%. Both are very short and fast.
- A defensive proc so top secret I can't even tell you what it is. But it uses one of the path algorithms, so that's a package deal.
- I'm working on a new path algorithm that covers every enemy country in a specified area. It's bloated, hacked, ugly, and cumbersome, but it works. 90% done.

I'll be willing to part with the shortest path proc for a fair amount.

 
YouDieNow

Or best offer.

 
Jp

Cumbersome you say? Maybe I should trade instead of trying it myself :-)

 
Jp

Tried a conti-sweep-routine and I'm 90% sure it works a 100%.

 
YouDieNow

I'm looking for one of those. Perhaps we can work out a deal.

 
Jp

Doesn't you "kill-every-enemy-country-in-a-specific-area" proc do the same?

 
YouDieNow

Yes, but it's not really that great. And it's not perfect.

 
Jp

I'll tailor the place and take procs to fit and then I'll show you the goods.

 
YouDieNow

OK set up a demo if you can. If it's what I'm looking for and you want the easiest path algorithm, we can do an even trade, with non-disclosure agreements of course.

 
Jp

Damn, just found that 10%. It chokes when trying to take asia.

 
YouDieNow

Does it evaluate once and give you a path to follow, or does it evaluate each time robot_attack is called?

 
Jp

Found the problem: for NA it takes about 1 sec to do the calculations, but for Asia there's about 300000 times more calculations :-(

 
YouDieNow

We need to figure out a solid algorithm that doesn't increase exponentially.

 
Jp

I have a longest path proc now, but it's only usefull for nomadic armies.

 
RadiKaal

I was already afraid that that would be the case. That is the same problem I have been experiencing, but I had it solved for a big part. So it is possible...

 
Jp

Which one are you working on Rad? A proc that takes a continent by using all available countries or a proc that does a longest path for one superarmy?

 
RadiKaal

The first, the "superarmy" idea is ...useless in my opinion.

 
Jp

Yeah, I agree with you on the superarmy thing. Unfortunately it's the only one I got to work fast enough :S

 
jaybird

So have you guys finally figured out how to write a path algorithm that doesn't take all day to compute? You must heavily constrict your recursion loops given your goal. I.e., there is no 1 path algorithm that fits all.

 
YouDieNow

No, I've found the magic algorithm that defies conventional mathematics, and it precisely and consistently calculates exactly the best path in the very short timespan of just a few milliseconds, all without the use of recursion. Recursion is for losers.

 
jaybird

What is the 'best' path? The longest? Shortest? Least defended? Greatest defended? Within 1 continent? Whole map? Against 1 player? Against all foes? And so on. My point is that depending on your goal, you have to constrict your choices; hence, no 'best' path algorithm.

I would think one would have to have an advanced degree in math to judge whether you are defying conventional mathmatic principles. And BTW, I don't see any serious math even entering into the solution. You can get somewhat fancy with summing probabilities.

Recursion is for losers? Please explain.

 
YouDieNow

"Best path" as in the path that encounters the least armies between point A and point B within the entire map. One of the arguments to the procedure is a list containing countries to avoid, so it's trivial to contrict the path to one continent, or perhaps if you don't want to disturb a temporary ally's continent the algorithm can work around it. By default, it avoids it's own countries.

I don't have an advanced degree in mathematics, but I can safely say without a doubt that this algorithm operates within the fourth dimension and takes Einstein's relativity principles to a whole new level. I am currently in discussions with IBM to license my algorithm to them.

Recursion is for losers because it's inefficient and now for this purpose it is obsolete.



 
lankyhp3

oldest thread here i think. tasty

  Reply to this discussion

Copernica is a software for e-mail marketing, profile enrichment, websites and short text messages campaigns.