PDA

View Full Version : All possible Garbage Disposal paths.


iansmith
05-11-2010, 05:09 PM
Don't ask me why, but I decided to use math to figure out the longest possible path you could make the walkers take in the Garbage Disposal map.

I did it by writing a computer program to try every possible combination of placing blocking towers and it turns out there were only 90 unique solutions, so I had it show them all to me so I could look them over and sort by various metrics.

I put them online if anyone is interested...

LINK: Defense Grid Longest Paths (http://www.ian.org/Games/DefenseGrid/)

Sorry if the pages are ugly. I'm not a graphic designer. :-)

Turns out the longest path you can force them to take is just about 3 times longer than the path they use with no towers blocking their way. Not like Last Stand.. you can make some crazy long paths there.

jpsie88
05-11-2010, 06:03 PM
You ARE the man. It just shows how addicted we all are to this game...

hiclass
05-11-2010, 07:40 PM
Don't ask me why, but I decided to use math to figure out the longest possible path you could make the walkers take in the Garbage Disposal map.

I did it by writing a computer program to try every possible combination of placing blocking towers and it turns out there were only 90 unique solutions, so I had it show them all to me so I could look them over and sort by various metrics.

I put them online if anyone is interested...

LINK: Defense Grid Longest Paths (http://www.ian.org/Games/DefenseGrid/)

Sorry if the pages are ugly. I'm not a graphic designer. :-)

Turns out the longest path you can force them to take is just about 3 times longer than the path they use with no towers blocking their way. Not like Last Stand.. you can make some crazy long paths there.

Are you sure your program is correct in finding all possible solutions? How come mine never show up in your list?

I was playing with "1234DPBEA3C756" according to the tags on your map. The reason I choose this path is not because it is the longest (it is anyway lengthy enough for me), but block 1 and 3 is passed by the aliens twice.

Note: for block 1 and 3, I split them into 2 parts (upper and lower) with a row of towers in the mid.

eram
05-12-2010, 03:34 AM
This happens to be my most played DG map and it frustrate me so :D I'm quite sure I have winning path but my interest earning skills fail me badly.

My path is 1234DPBEA3C6 ranked 190 (down 100 places from last month.ouch) and a score of 72632. I'm positive a vastly improved score can be achieved.

hiclass
05-12-2010, 09:48 AM
Ah,

I have found mine on iansmith's list, it should be "12341DPBEA3C756", I have missed the second "1" in the path so can't locate it from the list.

Btw, nice work iansmith!

twig314159
05-12-2010, 11:05 AM
It's a very interesting list. Something that stood out to me (no real testing, just general impressions) is that the longest path identified isn't necessarily the best path. It is very long, but the aliens spend most of their time on the road, away from the towers (at least those towers with a short range).

Just goes to show that the longest path isn't always the best path. And I'd even bet that some paths in that list are better than others depending on towers you build and where.

54x
05-12-2010, 04:25 PM
Indeed, what you really want is the path with the longest time spend in proximity of towers.

Mondak
05-13-2010, 11:41 AM
wow = pretty cool. I don't think you took all possible into account. For example:

1 2 3 C 6 5 7 5 B P B 5 7 5 6 C 6

is a great path that I have a lot of success with and not up there.

iansmith
05-14-2010, 12:19 PM
After looking over the map again I see I made one mistake and combined two paths that I thought were equivalent but were not. I'll post some corrections when I fix the program and do another run. With all the extra combinations it might take a day or two of computing power to finish. :-)

Mondak
05-14-2010, 02:54 PM
After looking over the map again I see I made one mistake and combined two paths that I thought were equivalent but were not. I'll post some corrections when I fix the program and do another run. With all the extra combinations it might take a day or two of computing power to finish. :-)

Awesome! I can't wait to see it. Stuff like this is what makes the game so cool.

333OnlyHalfEvil
05-14-2010, 03:26 PM
How did you construct your program? This is a classic "Travelling Salesman" problem that has a factorial complexity (the most complex problem). How long did your program take to run?

Also, didn't see the path i used in there. Mine was 1 2 3 C 7 5 7 D P D 7 5 7 C 6. This path worked really well for me because the aliens have to pass platform 7 four times in order to escape with my cores.

hiclass
05-14-2010, 08:46 PM
How did you construct your program? This is a classic "Travelling Salesman" problem that has a factorial complexity (the most complex problem). How long did your program take to run?

Also, didn't see the path i used in there. Mine was 1 2 3 C 7 5 7 D P D 7 5 7 C 6. This path worked really well for me because the aliens have to pass platform 7 four times in order to escape with my cores.

Your path seems to be a better choice. Not only platform 7 is passed 4 times but platform 5 is passed twice. The latter is important otherwsie platform 7 is not big enough to place towers for a definite kill.

Humphrey10
05-15-2010, 08:09 AM
What a good idea! I tend to use 1 2 3 1 4 D P D 7 5 7 C 6, I'll have to try out some others to see if they work better. I have a lower-tech way of deciding which path to make the mobs take, I draw out the levels on graph paper...

Mondak
05-15-2010, 11:21 AM
What a good idea! I tend to use 1 2 3 1 4 D P D 7 5 7 C 6, I'll have to try out some others to see if they work better. I have a lower-tech way of deciding which path to make the mobs take, I draw out the levels on graph paper...

yeah - while that path is long, it really doesn't allow you to concentrate the power of your towers. While they go through 1 twice, there isn't that much room there for towers when you do that.

iansmith
05-15-2010, 12:34 PM
Ok, I fixed my program and let my computer chew on stuff last night and just uploaded the results. It has found 160 paths and this time I think I got them all. I located all the examples given above in the new list.

My problem was I was considering things like the two paths between platforms 5 and 7 as identical and merged them. That was a mistake, now corrected.

Let me know if you find any solutions not listed.. hopefully this will be the last updated needed. :-)

How did you construct your program? This is a classic "Travelling Salesman" problem that has a factorial complexity (the most complex problem). How long did your program take to run?

To make the program I used graph theory to construct a set of all the paths and platforms. I then made a list of all the various spots a tower could block progress, and tried EVERY combination. The first run took 30 minutes. The last run, after adding in all the extra nodes I had previously 'optimized' away took 7 hours using two CPU's.

Overall it was not too bad. The program had to compare 31,850,496 possible configurations of blocking towers.

The platforms with 4 exits made things complicated. Not only did you have to consider blocking each combination of the 4 exits, you could also split the platform into two. In two directions. Thats what messed me up, at first I only thought platforms 1 and 3 needed that, but 5, 6 and 7 did too. The dual pathways were NOT equivalent.

Mondak
05-16-2010, 01:24 PM
Ok - now I feel cool for sure. The longest path is not really usable due the fact that the creeps get to the cores pretty easily and the length comes after they already have the cores (plus the fact that they would cross incoming creeps and just pass off all day long).

Looks like the path I was already using was already pretty darn optimal.

Too bad it takes to long. It would be more efficient I suppose if there were a way to programmaticly eliminate for paths that just make no sense - ones you just wouldn't ever use because they are just too short. It seems that you are not accounting for the actual "path" and instead just concentrating on all possible tower position combinations if that makes sense.

54x
05-18-2010, 04:02 PM
You could manually flag paths that go out of range of any short-range turrets as less "valuable", but that might be tedious.