Hehe, I made code to invert maps for me. Here's some of my paths, too.http://www.vbforums.com/attachment.p...postid=1803505
Printable View
Hehe, I made code to invert maps for me. Here's some of my paths, too.http://www.vbforums.com/attachment.p...postid=1803505
I have a question. Are you going to weight the scores for certain maps? For example, a very very long map can have the score divided by 10, since all the scores will generally be very high.
Another thing: Test algos 10+ times on the same map so the random people get a nice average and not an insanely high/low score.
Oh, and for the developers, here's a modified frmmain that lets you invert the map, keep searching after you hit the end (you can see if your algo misses any spots), modify speed faster, switch start and end points, and load maps just by picking them in the list.
Screenie:http://www.vbforums.com/attachment.p...postid=1803574
It's based on the form that gave you the memory and stops you from accidently loading/starting a maze while it's running.
yea, you can resubmit
Oh and I'd lik to poin tout the form won't shrink so low that you can't see part of the interface or your score. Man I hated that in the other ones. :afrog:
Well got mine working on all maps now(minus 1) although still not to happy with the scores. The minus 1 is that diagnol lines map. I can't even see the start point on it so dont know what my little guy is doing so didn't bother even testing that one.
http://www.vbforums.com/attachment.p...postid=1804014
That dern H-maz and Minas really mess up my algo hehe :)
I takes my algo 2776 to check every possible square on the minas tirith map (which is when it finds the end :rolleyes: ), 2260 to find the end of the H maze, and 2810 to check the entire thing (including going back to the start point to confirm unfindable)
Yeah mine can check the entire maze in probably around the same as well.. the problem is mine is based on random choices and sometimes he runs over the same crap many times (I had to code to check for getting trapped in itself).. I still have to modify more stuff and make it recognize some stuff better, but I got the basics down at least where it can completely everything without getting stuck.
I think mine and Merris are going to be really similiar, I know she mentioned pathfinding in hers before.. I also plan to implement pathfinding soon lol. It should take my scores down on maps like those a lot and also enable me to do away with my 'trapped' code :)
Suggestion for marking:
Take the square root of the score at the end. This will diminish the different between the "lucky" picks but not eliminate the difference between the algorythms in terms of searching.
IE: Algo 1 almost always does better than 2 by about 5%, except on the 300*300 map where 2 makes all the right choices and saves 4000 points.
sqr(4000) = 63, a much fairer number.
This also 'centralizes' the random algos better. No obsenely high or low marks.
Mine has the most basic pathfinding possible. but it still cuts the scores by a good 10% on open maps.
I'm thinking of expanding it a bit.
Don't worry about the marking of different sized maps, it will work like a league kind of. So each entry will be ran on a map then the winner gets so many points and so on then this happens for all the maps then the winner is determined from this.
Example:
Say 5 people enter:
Map 1:
Entry 3 - 3050 points
Entry 5 - 2370 points
Entry 1 - 2030 points
Entry 4 - 1790 points
Entry 2 - 1590 points
So Entry 2 came first so gets 5 points, Entry 4 came second and gets 4 points, ect....
Then at the end these points are added together and the one with the highest will win ;).
That's a good system. You're going to design the maps to avoid left/right huge differences right?
Here's an open map guys. Good to see what's going right or wrong.
A lucky search on that one for me!
http://www.vbforums.com/attachment.p...postid=1804063
and a not so good
onehttp://www.vbforums.com/attachment.p...postid=1804069
My code can handle any case atm, not only those pathetic minimaps of 300 x 300 ;) I already have an idea how to drop down the execution time while still keeping the code just as flexible.Quote:
Originally posted by cyborg
VB Code:
:rolleyes:
StevenHickerson: you need to fix the code to make the diagonal map working. See Electroman's post on this.
1) Could you post any test maps it must past before even being submitted. Because they are very spread out
2) The competition will be on random maps wont it. e.g not the ones we have now. Thats the only way to really test the path finding otherwise people can make assumptions and remove the element or 100% searching. :D
Bodwad, you just take the maps given out in this thread, most of them are different enough, and test on them. Use my form and use the 'don't stop' option. How many areas do you check/score? That's your goal, check as many spots as possible for the least possible score.
In fact I'd say to check your own algo tha's the formula. Area available/Area checked * Score ( / total area?)
See, I get too hooked on doing this.
http://www.vbforums.com/attachment.p...postid=1804485
Fitness is: Area Covered / Score * [TotalMapArea / BlockedMapArea]
the part in brackets [] can be excluded, it basically modified the quantity so that congested maps have a higher score (you aren't expected to cover as much area/score)
What fitness do you guys get on the maps?
and the form, of course.
if you guys are wondering why I keep making this stuff, I want to see some cool pathing algos at the end. :afrog:
*edit* The rotating wasn't working on non-square maps. I fixed it with some horrible horrible code It still works weird (mirroring won't work perfectly on rectangular rotated maps) but won't crash
and I changed the formula to divide by open area (duh... my mistake)
*edit again*
The calculation is now multiplied by 3 (the cost to move) and represented in percent.
I get a 50% fitness (non multiplied) on prairies and a 34% on minias tirith. (that's 56% on prairies and 64% on minis tirath weighted).
I think I'm gonna win!
VB Code:
I did have my code set up that it could handle any size map, and I may end up going back to it before I'm done (although the finish is wednesday unless its been postponed.) It has it's advantages and disadvantages doing it that way, but doing it predefined to 300 makes the memory step a little easier and I know for sure the memory is working correctly that way.Quote:
Originally posted by Merri
My code can handle any case atm, not only those pathetic minimaps of 300 x 300 ;) I already have an idea how to drop down the execution time while still keeping the code just as flexible.
StevenHickerson: you need to fix the code to make the diagonal map working. See Electroman's post on this.
And I'll have to sort back through the thread to see if I can find Electros, although I dont see any reason my algo wouldn't do fine on a horizontal line map. It may just get really high scores like on the H map until it gets lucky enough to find the opening at the ends or wherever.
Soon as I implement pathfinding (soon as I figure out how lol never done it before) then it should solve a lot of these issues with gettign stuck in one area for a few seconds until it happens up on the only way out of it and goes through it.
I use the predefined -300 to 300 because it means there's no array resizing. Modern computers have enough memory to take it without even slowing down. I store enough info in the map to make it worthwhile.
I just like posting these pictures
http://www.vbforums.com/attachment.p...postid=1804638
How will you deal with random pathfinding algo's?Quote:
Originally posted by Electroman
Don't worry about the marking of different sized maps, it will work like a league kind of. So each entry will be ran on a map then the winner gets so many points and so on then this happens for all the maps then the winner is determined from this.
(BTW, I had a score of 1337 points on the prairie map, very lucky. Too late I realized I should've taken a screenshot... :( )
(BTW 2, Yes, I also had scores above 10000 on this one ;) )
Hrmm Completely Random:
http://www.vbforums.com/attachment.p...postid=1804014
Only random in certian situations:
http://www.vbforums.com/attachment.p...postid=1804769
I need to find a good combination of the two....
Not sure yet, I suppose I could take an average of 10 runs but then again is that fair? If you are taking the risk of it being random then you should be able to face the results of that.Quote:
Posted by riis
How will you deal with random pathfinding algo's?
On the other hand a one off random choice could send your score sky high on a map. Not forgetting that will only effect that one map and you'd still be in the running ;).
Hint: make the Score a Long integer. I've created quite a huge map (110 x 105) and the score overflows before I'm half-way.
(I'll post it soon after a few tests).
Note, there's also a bug in this line (in Alkatran's form): FileContents = Mid(FileContents, InStr(1, FileContents, "</HEIGHT>", vbTextCompare) + m_clGridSize)
This should be: FileContents = Mid(FileContents, InStr(1, FileContents, "</HEIGHT>", vbTextCompare) + Len("</HEIGHT>"))
(or just +9)
I discovered this by setting the grid size smaller than 9.
Here is the big one :)
Anyone with a good quote, lyric or adverb is free to put it inside. (Eventually extending in quite an easy way to 300 x 300, by copying and pasting the letters into a blank field.)
Well, here it is, the first 300 x 300 map! :D
Have fun with this big one.
The start point is in the upper left corner and the end point in the lower right. This is a very large advantage for edge-hugging algorithms, so to test it well, change the start and end point often.
(Set the gridcell size at 3, to view completely in a 1280 x 1024 screen)
And a screenshot for the ones who aren't participating.
It took about 6 or 7 minutes to complete.
http://www.vbforums.com/attachment.p...postid=1804861
Well, Sunday I got a basic pathfinder working, does ok. Matched some of the lower scores reported for the nonrandom progies, +- 10 points.
But, Now Its a work week, and I doubt I can get my true strategy coded by wednesday.
Would anyone mind if we could bump the deadline to sunday, give us a couple of non-work days to develop on it?
:wave:
-Lou
Woo, got my score on the 300x300 map down to 58784. Sheer luck :)
I wouldn't mind a few extra days as well. since I'm quite busy at work at the moment.
Should we PM Electro, or do you think he'll notice our posts?
I'm all for a bump to Sunday, I want to get some pathfinding coded in and I can't figure out how to do it yet lol.
If I get pathfinding coded in with my pseudo random (but not totally random like I had it) then I think I can get up some pretty good scores on any map.
Oh and Riis.. I'm assuming I have to change something else, when I change the gridsize I get an error when it tries to load the map??
Thats ok, Sunday sounds fine, I'll edit the first post to show this too. I was planning on having a go at this one myself, just to see how well I'd do but I've not had time to even start it :(.Quote:
Posted by NotLKH
Should we PM Electro, or do you think he'll notice our posts?
Err nm about the Gridsize problem.. I was using one of the forms alk had uploaded and it had that error in the file contents.. once I fixed that it was fine.
4196 Points for lorem.txt :)
Sunday sounds great! I've been really busy with work, but now there's no more of that this week! :thumb:
hmmm....When changing m_clGridSize to anything under 9 i get an error saying "Type Mismatch" on this row:
MapData(X, Y) = CInt(Mid(FileContents, i, 1))
Also change the i integer to a long integer in cmdLoadMap_Click
Nevermind! Fixed it!
Got 3040 on lorem ;)
You should change it so the text is all the way to the walls.
My algo just moves along the walls all the way to the end.
Sunday?!?! I wanna see the othe rpeople's algos now. :(
I ruined my algo trying a different pathing and I have to wait for my submission to be visible. :rolleyes:
Didn't you save the zip?Quote:
Originally posted by alkatran
Sunday?!?! I wanna see the othe rpeople's algos now. :(
I ruined my algo trying a different pathing and I have to wait for my submission to be visible. :rolleyes:
Aw darn, I've been a few days away... might be I'll be posting a non-optimized code. The deadline is too soon in this case, I think. With prime numbers I had my code polished up two weeks before the deadline, with this one I'm still in development stage and have lots to do... running out of time here.
I would prefer faster deadlines just because once your done your ready to move on :). It should also be based on the toughness of the contest of course. Like this one is a bit harder than the PrimeNumbers was. Of course you can't satisfy everyone, maybe should put up a pole on a standard time frame that people would like to see used, and then just use the majority decision?
I implemented pathfinding in mine but I mucked something up big time, my algos memory is getting corrupted somewhere and not being set correclty or either the pathfinding algo is just reading the memory incorrectly somehow lol. Frustrating to say the least, it works great on maps like Prairies, but on the H map, depending on randoms I can get stuck in a loop where the pathfinder just starts running back and forth from two points, what makes it so annoying is I know the points have been crossed before and its impossible for a variable not to be set that would cause the pathfinder to ignore that point in future pathfinding procedures ... grrr :(
Humm... could someone post all the maps done already? Being away for a few days and some of those maps are completely new to me and I don't want to go through all the attachments :rolleyes:
I didn't zip it. It's a single visual basic module, not 3 bitmaps.
It doesn't matter. I was done with my code anyways. The changes I made slowed it down too much when it had to backtrack.
Route1 = 236
Route2 = 1052
Route3 = 394
Route4 = 664
Route5 = 1076
Route6 = 3536
Thats mine currently anyway :)
Yeah I know. Since it was late (1 AM) I really didn't bother to think of "clever" start and end points. You should really test it with with other locations as well.Quote:
Originally posted by StevenHickerson
Err nm about the Gridsize problem.. I was using one of the forms alk had uploaded and it had that error in the file contents.. once I fixed that it was fine.
4196 Points for lorem.txt :)
(Hint for Electroman, or just anyone who is building a form: make the start and end points truly random, but take care there is some considerable space in between them.)
My form: Run the maze with "Don't stop at end" checked and see what your fitness is when you've covered ALL the ground. I average ~45% fitness (about 50% weighted).Quote:
Originally posted by riis
Yeah I know. Since it was late (1 AM) I really didn't bother to think of "clever" start and end points. You should really test it with with other locations as well.
(Hint for Electroman, or just anyone who is building a form: make the start and end points truly random, but take care there is some considerable space in between them.)
Oh, fitness measures how many points you use for each square you check. A 100% fitness is 3 points per square (moving blind and not hitting walls or backtracking)
Mine learns so it should eventually on move not search as it already 'Remembers' the route :)
Could whoever the judges are let us know how these are going to be judged, like soon.
I need to know if they are going to be run multiple times and the average taken, one time and you get what you get or what. I have 3 different setups that I'm trying to decide on using, they all average about the same with one leading slightly in points, but the one leading slightly can be drastically behind if its a one shot you get what you get deal.
My suggestion on how to score them would be
Set up something like what I have setup up to run each map x number of times and run through all maps, then have the results reported. Give points for the apps with the Best "Best Score" (Best score from all x runs) and Points for the Best Average Score. As for the average I would say drop the highest score and take the average of the remainder. Now what this does for people who dont use random should have a fair chance of getting better averages than someone using random, although a random may beat their best score depending on how the Algos work. Dropping the highest score will drop the fluke extremely bad maps from the Random Algos.
But I would like to know soon how yall plan to score them so I can decide which code to optimize and sexify :bigyello:
Oh btw, working pathfinding rocks! The only map I still score higher than I would like on is that darn diagnol lines map that merri made. Still get like dern 14k + on it... darn that map. But I have some ideas to correct that without effecting my results to much on other maps, just need to know the scoring system so I can decide which version to go ahead with.
Yeah, it's leaving "breadcrumbs", and since the little guy is apparently hungry, he traces them back, in order to eat them ;)Quote:
Originally posted by StevenHickerson
Oh btw, working pathfinding rocks! The only map I still score higher than I would like on is that darn diagnol lines map that merri made. Still get like dern 14k + on it... darn that map. But I have some ideas to correct that without effecting my results to much on other maps, just need to know the scoring system so I can decide which version to go ahead with.
I'm having the same problem, since I implemented pathfinding, but other maps are going better :)
The best best score is not fair because only random algos can hit it. Random algorythms should have the same average potential as the non-random so let's just stick with the average.Quote:
Originally posted by StevenHickerson
Could whoever the judges are let us know how these are going to be judged, like soon.
I need to know if they are going to be run multiple times and the average taken, one time and you get what you get or what. I have 3 different setups that I'm trying to decide on using, they all average about the same with one leading slightly in points, but the one leading slightly can be drastically behind if its a one shot you get what you get deal.
My suggestion on how to score them would be
Set up something like what I have setup up to run each map x number of times and run through all maps, then have the results reported. Give points for the apps with the Best "Best Score" (Best score from all x runs) and Points for the Best Average Score. As for the average I would say drop the highest score and take the average of the remainder. Now what this does for people who dont use random should have a fair chance of getting better averages than someone using random, although a random may beat their best score depending on how the Algos work. Dropping the highest score will drop the fluke extremely bad maps from the Random Algos.
Not completely true, depends on the map and what direction the non random heads first. But I do see your point, given enough tests they should average out to around the same. But with only 10 tests or less the majority of the time a Random algo is gonna have a higher average than a non random algo (I have tested it both ways). Besides the object is to get a map finished with the best score possible so why not award points for the the best best score as well.Quote:
Originally posted by alkatran
The best best score is not fair because only random algos can hit it. Random algorythms should have the same average potential as the non-random so let's just stick with the average.
Here are my results from 3 different methods in 10 runs:
(Note the average drops one highest result)
Syntax: Name,Best,Highest,Average
NonRandom: 'Note on my non random, it does choose randomly at the start of each map which direction its gonna head first but thats the only random it chooses. I feel fully non random is just an incoherrent sloppy way to do it. But this is why the scores arnt the same across the board for each map.
Route3.txt, 392, 482, 437
Route1.txt, 236, 366, 301
Route2.txt, 874, 1400, 1006
h-maze.txt, 1970, 1970, 1970
minastirith.txt, 1342, 2778, 2060
prairies.txt, 3671, 4031, 3761
route2i.txt, 2008, 2572, 2290
route4.txt, 488, 572, 551
route5.txt, 758, 1076, 996
route6.txt, 1546, 1684, 1580
AverageOverall: 1495
FullRandom:
Route3.txt, 430,678,516
Route1.txt, 244,340,276
Route2.txt, 1198,2004,1399
h-maze.txt, 1364,2468,1772
minastirith.txt, 662,2730,1784
prairies.txt, 2259,6527,4353
route2i.txt, 780,2766,1666
route4.txt, 474,1078,784
route5.txt, 744,1742,1294
route6.txt, 1382,2842,1774
AverageOverall: 1563
PSeudoRandom: 'My own little secret combination of random and non random :)
Route3.txt, 342,502,404
Route1.txt, 262,366,303
Route2.txt, 624,1732,1352
h-maze.txt, 938,2178,1434
minastirith.txt, 1284,2468,1721
prairies.txt, 2875,6617,3965
route2i.txt, 1386,2676,1860
route4.txt, 540,972,786
route5.txt, 1036,1532,1230
route6.txt, 1050,2742,1715
AverageOverall: 1477
Now as you can tell each one does better on some maps.. but my Pseudorandom pulls out ahead on average by a little bit. FullRandom is in last for average and non random in the middle. The bad thing is my PseudoRandom is ahead by such a small amount that a couple bad maps could make it actually be behind the NonRandom. The NonRandom will stay pretty consistent in its scores. I figure NonRandom should be + or - about 50 or 100 points on average, FullRandom + or - about 400 or 500 and PseudoRandom + or - around 100 or 150 points.
Thus my dilemma lol, I still have some more optimizations to do to get the scores down some more, but like I said I'm trying to decide which one to go with. And if the scoring method is going to be fair to Randoms I'll be going with my PSeudoRandom setup.
Anyway have a look at those 3 sets of numbers and tell me how you think the scoring could be set up to be fair to all kinds of setups, and if anyone out there has a truely complete non random (as I said my non random chooses one random at the very beginning to get the initial direction) set of scores feel free to post them so we have a good comparable set.
In case you missed my post which i explained the scoring system it is here: http://www.vbforums.com/showthread.p...postid=1804057Quote:
Posted by StevenHickerson
Could whoever the judges are let us know how these are going to be judged, like soon.
I need to know if they are going to be run multiple times and the average taken, one time and you get what you get or what. I have 3 different setups that I'm trying to decide on using, they all average about the same with one leading slightly in points, but the one leading slightly can be drastically behind if its a one shot you get what you get deal.
My suggestion on how to score them would be
Set up something like what I have setup up to run each map x number of times and run through all maps, then have the results reported. Give points for the apps with the Best "Best Score" (Best score from all x runs) and Points for the Best Average Score. As for the average I would say drop the highest score and take the average of the remainder. Now what this does for people who dont use random should have a fair chance of getting better averages than someone using random, although a random may beat their best score depending on how the Algos work. Dropping the highest score will drop the fluke extremely bad maps from the Random Algos.
But I would like to know soon how yall plan to score them so I can decide which code to optimize and sexify :bigyello:
Oh btw, working pathfinding rocks! The only map I still score higher than I would like on is that darn diagnol lines map that merri made. Still get like dern 14k + on it... darn that map. But I have some ideas to correct that without effecting my results to much on other maps, just need to know the scoring system so I can decide which version to go ahead with.
But I still haven't decided whether an average will be taken (http://www.vbforums.com/showthread.p...postid=1804800), I'll decide this and let you know tomorrow though.
No I didn't miss that post Electro, as you can and probably did assume from reading my post I'm concerned with if your going to be taking averages or just one shot deal.
So guess I wont be able to do any more optimizations till after you say which tomorrow. IMO though if you say its a one shot deal it basically a big middle finger to anyone who codes it random :mad:
Well, thanks to my nice and long weekend, I couldn't even fix my code more. I posted it already (wasn't today the last day?). Electroman will be having fun time with the "advanced pathfinding" on bigger maps. I give a tip: compile the program before you run! Even after that, if you run it on a 300 x 300 map... have a nice day.
You can only blame the quick deadline on that one ;)
*sigh*
Feels bad to send unfinished code, but no time...
Steven, I do not agree with your opinion. The way how you implement your algorithm is a choice. You'll be lucky, or you'll be unlucky with your guess. I see that as a part of the game. If I would be afraid that my algorithm will perform badly, I would create a non-random algorithm.Quote:
Originally posted by StevenHickerson
So guess I wont be able to do any more optimizations till after you say which tomorrow. IMO though if you say its a one shot deal it basically a big middle finger to anyone who codes it random :mad:
The maps that are available, don't tell anything. They are not the maps which will be used for the final testing. Yes, it could be that non-random algorithms would be at advantage, but it could also be completely the other way around. (I'd be interested to see the maps after testing.)
Sorry to say, but the way you whine about this doesn't sound allright to me. Although I have a completely random algorithm, I don't feel offended by Electroman's decision (about the scoring system) tomorrow at all. So, please speak for yourself the next time. (Why not ask for the test maps themselves, so you can optimize your algo for them...)
Just pick one of your algorithms, the one who will perform best in unknown situations, and try to optimize it any further. Make sure it doesn't do any stupid things, and you should be doing reasonably well.
The deadline has been extended to next sunday, so you still have a couple of days to work on it any further. Electroman also has posted it on the first page of this thread.Quote:
Originally posted by Merri
Well, thanks to my nice and long weekend, I couldn't even fix my code more. I posted it already (wasn't today the last day?).
The arguments about random algos seem to be very biased towards supporting them. If you choose a random algo then you have a chance of getting a high score or a low one. The point of it being random is to have a gamble.
If it was a race and somebody made random turns they couldnt just take the average out of ten because the winner of the other nine obviously did better.
As to removing the largest one and makeing the average because it could be bad luck, shouldnt we also then remove the lowest based on good luck to make it fair? You chose random for its 'randomness' so you will have to accept the random outcome. :D
P.s I havent done a random one and I am getting worried that if these suggestions are taken it will be biased against me and all others who used full logic to solve the problem :)
I know the gamble of random. My main target was to try to make it random, but only when it is good to be random. I know I weren't able to do it with as high level as I wanted, I should have made a full recode and optimize the code and so on...
Maybe there should've been two different series for the contest: one for random pathfinders and second for full logic ones. Then we wouldn't have this somewhat nasty problem here because of completely different starting point. Imo it is hard to compare the two.