Contest 2 - PathFinder

Quote:

---

Originally posted by BodwadUK
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 :)

---

Aren't we using logic then? ;) The only thing that is random in my program is that it's completely unbiased in which direction the player should go the next move. There's no fixed set of rules from which it is electing the next direction. This choice determines nearly everything.
(There is one situation when the choice is not strictly random, but there also is no reliable way to predict in which direction the player goes next.)

As Merri suggested, two series of scores would be nice, since the starting point is different. But also the overall score would be interesting, since the test maps are completely unknown to us, so that is a random factor as well...

Ok fixed pattern logic :lol:

it would be nice to have two scores but they have quite alot of work to do anyway :afrog:

Nah, I believe there won't be all that many codes submitted as there were in the prime numbers contest. Prime numbers are rather easy to go with, you need to think in this contest a little bit more :D

I'll go with every entry only gets the one shot on each map. Using Random Pathfinding doesn't just mean you could be unlucky and get a bad score, it also means you can get a good score. Also if your algo really did mess up and get a bad score then it doesn't effect the overall too much as long as it performs well on the others. If all the scores from different maps were added together then I would see your point more.

P.S. the Algo I am planning on doing will be random(ish) too, however I suppose my score isn't going to count :(.

\/\/h3n 1s teh d3adline?

Sunday I think :)

I have just refined mine. Is it ok if I resubmit? :)

That's it. I'm putting A* star in mine and curshing you all. :afrog:

Quote:

---

Posted by alkatran
That's it. I'm putting A* star in mine and curshing you all. :afrog:

---

Yea I'm considering having that but don't think i'll have time to get one done.



BTW yea you can resubmit.

Quote:

---

I'll go with every entry only gets the one shot on each map. Using Random Pathfinding doesn't just mean you could be unlucky and get a bad score, it also means you can get a good score. Also if your algo really did mess up and get a bad score then it doesn't effect the overall too much as long as it performs well on the others. If all the scores from different maps were added together then I would see your point more.

---

Thanks, guess I'll be using my less random version. After stress testing all three of my versions, 100 runs each on all test maps I discovered that random will run badly the majority of the time. Theres just to many possibilites (2 to 3 at every junction) for it to get lucky enough often enough to only have one chance at each map.

If anyone is interested in knowing though in 100 runs the results for full random average from all the maps I posted earlier went up from 1563 to 2344. The results from PSeudoRandom went up from 1477 to 1940. And the results from my LowRandom (Called it NonRandom earlier) went from 1495 to 1580. Low random wins easily as the more reliable system.

Quote:

---

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

---

If you misconstrued anything I said to be a whine then I'm sorry, it was far from it. It was more of a debate, I like random better because it feels more like the computer is deciding where to go. If you want to see what an actual whine looks like: ahh screw this crap this is obviously biased toward non randomers this is so unfair. That would be a whine, but I can adapt to any situation thats why I needed to know the scoring procedure :) I would not whine about anything about this contest, I've loved it. During this contest I was able to think out the theory and develop my own pathfinding Algo and that felt pretty good to me. Even if I come in dead last I'm happy cause I gained something from the contest.


Oh and what is A*?

I made more changes to the form, including fixing that bug and letting it load the 300x300 maps (it was too big before?)

Added a list box on the bottom to keep track of scores and a "run all" option.

Best addition is the random map generator. Simplest thing ever but it can give you some maps you wouldn't have thought of. ... random ones. lol

Oh, and clicking on the picture box now changes the position of the start/end points (left for start right for end)

I also refined the weighted map calculation. It now takes the 4th root (square root of the square root) of the map area / open area. This is because some maps were getting crazy fitness boosts.

I changed my algorythm to use floodfill pathing, as A* is excessive for this type of thing, and most of my scores dropped by 1%-5% (100 points on cave)

Average unweighted fitness is 45%. 50% weighted. (weighted means multiplied by the difficulty factor)

I also included all the maps I have with it.

Oh. And I cut the memory my algorythm uses by 1/4. It's 0 to 300 instead of -300 to 300now. :bigyello:

My stats:

Code:

---

Map Name      Score    Fitness  Map Difficulty
Cave          4531      45.35%    1.044
Grid          2836      42.31%    1.083
h-maze        2260      43.54%    1.104
lorem          4236      42.92%    1.137
Maze          946      38.37%    1.232
minastirith    2776      38.04%    1.155
nwselines      6350      48.90%    1.130
PipeLine      828      48.55%    1.236
Prairies      6317      53.66%    1.017
Sections      474      46.84%    1.035
Small Maze    198      45.45%    1.250
Symmetry      364      41.21%    1.191

---

and a screen shot
http://www.vbforums.com/attachment.p...postid=1806747

This is what we call "excessive"

It paused for a good half second at the end when it had to make the best path back from the bottom corner to the top corner.

Hee, looks like I'll be competing with my really unfinished code. I have two reasons for this: first take a look in the signature. That's the reason #1. Then the second reason is that I got Rome: Total War. Additional reasons being Azumanga Daioh DVDs, Fire Emblem (and some other games) for GBA... yeah... I'm quite stuck on all these.

Atleast you know I'm not winning the contest. Unless Electroman manages to mess up the results... :D

I just made a nice little change to my pathfinder that made it work seemlessly with movement. Havn't tested it on a really large pathfind like in Lorem.. I can do that tonight just to see, but on maps like nweslines it can cover half the map without a blink. Before you could notice a pause while it traced out the path :)

Think I'm about ready to submit mine, but I'll probably wait till Saturday just in case I come up with another idea by then hehe.

Oh and Alk I downloaded your latest form just to do some of the random map testing, and like 9 times out of 10 it gives an unreachable finish lol. Good thing you also made it so you could move the start and finish points ;)

Quote:

---

Originally posted by StevenHickerson
I just made a nice little change to my pathfinder that made it work seemlessly with movement. Havn't tested it on a really large pathfind like in Lorem.. I can do that tonight just to see, but on maps like nweslines it can cover half the map without a blink. Before you could notice a pause while it traced out the path :)

Think I'm about ready to submit mine, but I'll probably wait till Saturday just in case I come up with another idea by then hehe.

Oh and Alk I downloaded your latest form just to do some of the random map testing, and like 9 times out of 10 it gives an unreachable finish lol. Good thing you also made it so you could move the start and finish points ;)

---

Well it's a completely random map, I tried to pick a good free-to-block ratio. And you never know, they might give us a map with no end and see if we can figure it out. :afrog:

Damn it! I wish i had seen this contest sooner. :mad:

Whee, the entries are there.

I'm testing them now, I have 10 maps I've made and so far Merri's is the first i've tried and its upto the 10^th map now, waiting for it to backtrace quite a distance and its taking ages :(. On the 5^th map I was able to go and make my lunch, eat it then still had to wait for it to finish :lol:.

Yeah, I know how you must feel :D I warned you its slow. But I just couldn't regain the last bits of interest and competetivy (love is so fun) to improve it, so you have to enjoy the pain of the rough test code ;)

Well, atleast it runs without slowdowns if you disable the "advanced pathfinding"... it just isn't too smart. Though, due to some bugs, it isn't too great with it either. There are some complications with the original logic and the new onbuilt logic. But that's just like Windows and we know Windows is great and popular! :D

Results are in: http://www.vbforums.com/showthread.p...hreadid=308231