Contest 2 - PathFinder

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

Quote:

---

Originally posted by cyborg

VB Code:

Dim MapMemory(-300 To 300, -300 To 300) As MemoryUDT

:rolleyes:

---

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.

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:

Option Explicit
 
Public Sub StartGame()
    Randomize Timer
    While frmMain.MovePlayer(Int(Rnd * 4) + 1) = False
    Wend
End Sub

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.

---

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.

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

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.

---

How will you deal with random pathfinding algo's?


(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....

Quote:

---

Posted by riis
How will you deal with random pathfinding algo's?

---

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.

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??

Quote:

---

Posted by NotLKH
Should we PM Electro, or do you think he'll notice our posts?

---

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 :(.

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: