2 cents

Hey people. I'm a bit late for your contest. If I didn't have to work tomorrow I'd submit some code. So I figured I'd just give you 2 cents worth. :-) I thought about this for about 2 minutes. Oh well, here goes.

OOP - point object, room object of points, array of rooms. parse the map...find a room block...
if $map(x-1,y-1) (x,y-1) (x+1,y-1) (x-1,y) == room block value (assuming x-1 and/or y-1 >=0), add point to room object of the (x-1,y-1)....
else new room object add the point.
Now you should have a bunch of room objects with all the points that are in them. (max 50 rooms right!)

Now i could find edges, and eliminate interior points from the rooms...if number of blocks in room >=9 probably. Pretty easy, any point in list surrounded by room blocks would be whacked.

We know the # of rooms. Find the closest points between rooms A and B, A and C, B and C, etc. and their distances. list of line objects (x1,y1,x2,y2,D), preferrable D being calculated with boolean expressions.
Sort by D.
insert corridor values from the line object with the smallest D. preferrable bresenhaum algorithm. (draw it).

destrroy the object structure, re-build structure. if rooms=1 return $map, else keep looping.

If you even get what I just typed, great. But I really am not a fan of the whole OOP method here.
But if you were dealing with 3D semi-transparent textures with some 2d collision detection of non-transparent elements, ok fine!

i would prefer just using simple string manipulation functions (usually simple mem_cpy routines). Just create a flat variable string...
nndxxyydxxyyEOL(/r whatever)
nn xxyy xxyy EOL ... EOF(null whatever)
where nn is the room number and the xxyy's are the points within them, d is your delimitter. Pretty easy to insert, and append. send string parts to functions and explode them as you need them.
run your calculations, draw the line (bresenham)in your map, and start over until the number of rooms=1.

now, I'm errored in my "calculation routine", the only optimization I can see is :
if you have two sets of possible corridor lines with equal D: Do they intersect or do they have the same origin or destination Room? if any 2 of the lines with lowest D meet either possibility, follow this course of action: intersecting lines (not in point next to a room) - are not optimal, do next line in list. If they have the same origin or destination, or vice versa. compute points for a line in between.
eg.
O----------D O=origin D=destination
! -=1st line != 2nd line
! =computed line
!
!
D
now compare all points with room d1 and room d2
find lowest d for each point and room.( run your lowest distance finder function with a room with 1 point () and your destination room. pretty easy.
find lowest D with # of 's and connecting line to room. draw 3 new lines on map. and get back to the main loop.

More than 2 seconds huh? bedtime. Best solution I got, but I wouldn't win. I wouldn't use the memory and processor hog object structure. 8MB limit, lol...a challenge would be 18k with rooms that move and you have to have 30 frames per second.

okay, definetely bedtime. Re-inventing the wheel is what we do, we just change the name.

i forgot to login, i think

Not talking to myself, just can't sleep.

have you noticed the 3 line method I mentioned. It resembles a peace symbol, and I think it's optimal for alot of situations in this contest. And it's represented in one of your sample maps.

if the rooms are nations, it requires 3 nations (or groups of nations) to create peace. How many lines of peace would be required if the map represented the earth?

There are deep truths in programming. This isn't one of them.

I think we are going to see a lot of scripts which are really good due to the stiener formula. It isn't fun when first place will be decided by milliseconds as who knows it the processor has a hiccup or something.

what's the steiner formula?

Much fair scoring is scripts with same wall costs gets same points, and if the sums are equal then the fastest will be the winner (like previous contests), I thought.

Hiccup... same corridors costs...

that brings about a problem however..

say there at 15 entries
- 14 get the optimal result
- the other 1 is less than optimal

so are we going to award a score of 15 or 1 to thosee 14 scripts?

15 would be highly unfair to the script which did badly in this particular case and it would cause this map to have too much importance

1 would make this map pointless and again reduce its importance

using the execution time would make it easier to score, besides, the rules shouldnt be changed after the competition is over

on a side note, since the scripts are on ftp already, has anyone here done any benchmarking ? any results to post ?

i did some testing (on roughly 1000 maps yet).
the results depend VERY much on how the maps are created.
so its quite useless to post the results (i tested on randomly generated maps, but the actual maps will be handmade).

anyway i dare to say that one of these 4 will win:
7,11,12,13 (maybe 10 has a chance either).
best performing script in my tests is clearly 7 (only on maps with less than 10 rooms other scripts are better; and its very fast).
the rest is very close together.
script 11 is very fast either and performs better, the more rooms are in the map.
script 12(mine) is very slow, but good on maps with few rooms and not very good on maps with many rooms (maybe it would be slightly better on a faster server [i used 1ghz]).

i dont envy zombie for the judgement-job.
there will always be a reason to say its unfair. but i promise: i wont ;-)