Contest 2 - PathFinder

[Electroman]

Contest 2 - PathFinder


Language

VB6 Only, I've been unable to find anyone with enough time to convert the helper project to VB.NET. Sorry about that.


Deadline

The dealine for this contest will be Sunday 10th October (Mid-day, BST). This maybe extended pending requests.


Main Aims

You have been given a VB6 project which displays a maze and a little player. You the project also contains 3 "Control" functions that have been put in the forums Code, these are Look(), LookAbout() & MovePlayer(). All your code must be in the module called "Controller", in this module we have placed a function named StartGame(), this is the entry point for your code. The only way you can interact with the rest of the program should be though the three "Control" functions. An example of what is expected has been put in the StartGame() function however its by no means any good.

Using this you must turn StartGame() into a AI function that will guide the player though the maze. The size of the grid is not fixed and the starting position (or end position) is not given.

The three functions do the following:

Look()
This function take a parameter for the direction to look in as a Byte, 1 - North, 2 - East, 3 - South & 4 - West. It then returns a bool to tell you if that direction is clear.

LookAbout()
This is the same as Look() in a way but it takes 4 ByRef parameters and these are 4 bools, when the function is called it returns whether the routes are blocked though these parameters.

MovePlayer()
This function takes a byte as a parameter the same as Look() and it will attempt to move the player in that direction. The function does not return if the move was allowed though, if the route was blocked then the function runs as if it wasn't. The function does return a bool but the purpose of this is just to tell you if the player has reached the end yet.


How Is It To Be Marked?

A marking scheme has been produced and implemented into the project so you can see how well your code is doing. The scoring is based on how many times you call each of the three "Control" functions and each has a different weighting as shown below: Look() - 2 Points LookAbout() - 6 Points MovePlayer() - 3 Points (Independant of whether the player was able to carry out the move)
As you may see it could be an idea to just run round the maze blind and the points might not be as high but then again you could make lots more moves then needed if you do that.

We will be running your code with a variety of different maps of sizes ranging upto 300x300 and will be recording the scores. Whoever gets the lowest score overall will be the winner. We have included 3 test maps so you will be able to test your code on them for now.


What Do I Win?

The prize for this contest is yet to be announced but at the least it will be another Custom Title Status but I am hoping we will be allowed to make it include Color Tags, like Brads or VisualAds ;).


Where Do I Send My Work?

To submit your work create a new Thread in the Contest Entries Sub-Forum (http://www.vbforums.com/forumdisplay.php?s=&forumid=68). Please title your Threads "Contest 2, PathFinder - Username", changing Username for your username. Attach a Zip file to the post and include just your Controller module.


Any Querries?

If you have any questions then your welcome to send me a PM or any of the other people running the contests.

http://www.vbforums.com/attachment.php?s=&postid=1799263

[Merri]

I just wonder what is the point of the whole thing... it is impossible to look for a route without moving the player. Thus, in the end, I have to run through the whole maze (not even knowing the size of it) until it finds the final goal by luck. I feel very limited. This is no good as it is now - very very uninspiring, even if I have some ideas.


Edit I were the second to download it.

[NoteMe]

Well there is about 100000 algos to find paths....just start reading if you don't know them all ready...;)

[Electroman]

Its not a case of planning your way though exactly, I suppose some luck is brought into it, its more of an acurate way that you would find your way though a maze if you were in the maze. If you were put in a maze you would not know anything about the maze apart from the imidiate area around you.

Its not just a case of moving lots and hoping you get to the end eventually as there are different approaches you can take. There is also different scoring depending whether you choose to use the Look() or LookAbout() Functions which will come into your strategy of doing this.

[Electroman]

Posted by Merri
Edit I were the second to download it. Thanx, I will remove the notcie now then. manavo11 Was the first but he had already told me so I just wrote that there was only one :).

[cyborg]

I think this one is interesting! I've never worked with AI before, and now I have a reason to do it. Millions of ideas are poping up in my head right now :thumb:

[cyborg]

Some questions:

1. Is it ok to make some own functions and put in the controller module? Just to clean up the code...

2. Is it ok to change the pre-coded functions (such as LookAbout())

3. Is it ok to change the inputs or outputs of the pre-coded functions? (i.e change bool to byte, or something similar)

Thanks.

[Merri]

As the rules started, you aren't allowed to edit the previously done functions. The only thing you can change is the controller module.


Electroman: could you post it into a new post, I'm still getting the old version.

[manavo11]

Originally posted by Merri
As the rules started, you aren't allowed to edit the previously done functions. The only thing you can change is the controller module.


Electroman: could you post it into a new post, I'm still getting the old version.

Clear your browser cache...

[cyborg]

Hmmm....What was the error inte the old version?
The LookAbout function returns false on all directions for me.

[manavo11]

Sorry about that... Paul isn't answering so I fixed that. Here is the final version. Sorry for the inconvenience :)


<Deleted the attachment, Above one is updated>

[StevenHickerson]

Ok well the first immediate problem I see is this, in the picture shown above the player takes up one block. The exit is in the center of a room the size 3 x 3. So its basically going to be dumb luck that the program happens upon the exit block in that room. Would it not be better to make the exit the first block upon entering that room. Or to at least to add another function LookAboutExit() that returns true if the exit is one block away in the respective direction. Heck you could even make such a function cost 10 points per use to make sure people dont abuse it.

If this seems like a bad idea then I guess its just another hurdle to overcome, but I agree with Merri that the whole project seems more like blind luck than an actual AI, the only AI part would be to ensure your progy isn't stupid enough to run back down dead ends that it already went down.

You said it makes it more like a person actually in the maze themselves and only knowing what is around them but a human in a maze like this has an advantage, perspective.. they can see how long a hall is and a lot of times would probably be able to tell if there is an opening down a shorter hall or not (longer ones would be harder to see).

Oh blah I guess I should stop focusing on the limitations and just code it huh? :) Interesting project to say the least and I should have fun finding a way to do it even if it is more random than AI :rolleyes:

[Electroman]

Thanx manavo11.

Yea My car just got broken into just before manavo told me about the other error so I've been sorting that out. :(

[manavo11]

Originally posted by Electroman
Thanx manavo11.

Yea My car just got broken into just before manavo told me about the other error so I've been sorting that out. :(

You should edit the original attachment also :)

[Electroman]

Posted by StevenHickerson
Ok well the first immediate problem I see is this, in the picture shown above the player takes up one block. The exit is in the center of a room the size 3 x 3. So its basically going to be dumb luck that the program happens upon the exit block in that room. Would it not be better to make the exit the first block upon entering that room. Or to at least to add another function LookAboutExit() that returns true if the exit is one block away in the respective direction. Heck you could even make such a function cost 10 points per use to make sure people dont abuse it. I put that in so you wouldn't think about it as just corridors. This way not all the algos you find on Google will fit straight in ;).

[cyborg]

Damn this is hard!

My algo is huge so far and really stupid!
I get 198 points on the first map, 502 on the second, and on the third it gets locked into an infinite circle at about 450 points!

I've added some small memory for the player, but I'm a bit confused on how to deal with it the best way...

Maybe it's a good idea to add a bit of random movement, so you don't get stuck... But then it's not possible to measure the same way....

Please tell me what you get!

[wossname]

Originally posted by Electroman

So far it looks like we will be making this just VB6 because we've been unable to get a VB.NET version of the project made.

Do you want me to write one for you?

[Pino]

Would you be willing to mark it as well? I'll see what brad\electroman thinks!

[Electroman]

Posted by wossname
Do you want me to write one for you? If you could please. You needn't mark them though, this way you'll be able to take part too. :)

[Electroman]

BTW I set the deadline at just over a week but as some of you are finding out its not as simple as you might think. So if you need more time let me know and if there is a few people saying this I'll increase it :).


I think I'll have a go at this one myslef too, although I won't get ranked at the end :(.

[wossname]

Originally posted by Electroman
If you could please. You needn't mark them though, this way you'll be able to take part too. :)

Ok. I'll start it tonight and I'll get it done ASAP.

I don't mind marking them. I will not show any favouritism unless I am paid in cash.

W00t!111!!!!!1!!1!1!oneoneeleven :lol:

[Xcoder]

this sounds interesting, Ill be working on it for the next few days :thumb:

[NotLKH]

Hmmm,

Ok. Just thinking off the top of my head,
If you were to run this in the Development Environment, then we could code it to read the frm files in the app.path, see if anything interesting exists, like any lines resembling App.Path & "\Route1.txt", or some such.

'Course, not sure what I'd do with such extracted info.

'Course, you could easily trojan some txt file up.

'Course, you're surely not going to let us access the maze dat so easily.

hmmm, just musing over this little, stray, distraction of a thought.

:wave:

[alkatran]

So basically, you're shoved into a dark room and you don't even know where the exit is. Whoever keeps his eyes closed the longest wins. :bigyello:

[Electroman]

Posted by NotLKH
Hmmm,

Ok. Just thinking off the top of my head,
If you were to run this in the Development Environment, then we could code it to read the frm files in the app.path, see if anything interesting exists, like any lines resembling App.Path & "\Route1.txt", or some such.

'Course, not sure what I'd do with such extracted info.

'Course, you could easily trojan some txt file up.

'Course, you're surely not going to let us access the maze dat so easily.

hmmm, just musing over this little, stray, distraction of a thought.

:wave: Don't forget I only asked you to submit your module file and that the only thing you can relie on is that those 3 functions will be avialable. For example I may rename the frm file, I may totally change the file format of the map data files.

I have thought of a few ways you could "cheat" but instead of saying you can't do them I thought that I would leave them open and see if anyone thought of them. But seen as though I just made the previous statement that the only thing you can relie on being those 3 functions I guess that should make everyone play fair. Saying that this contest isn't close to impossible so you shouldn't find the need to cheat :).

[Electroman]

Posted by wossname
Ok. I'll start it tonight and I'll get it done ASAP.

I don't mind marking them. I will not show any favouritism unless I am paid in cash.

W00t!111!!!!!1!!1!1!oneoneeleven :lol: :lol:, Thanx :).

For the marking all we have to do is run the code and record the Score so manavo11 will probably do that as he has VB.NET and access to the secret Hide out (opps, I mean Private Moderators Section).

[Electroman]

Just curious but does anyone have an algo that compeletes all three maps yet?

[wossname]

Originally posted by Electroman
Just curious but does anyone have an algo that compeletes all three maps yet?

Yep. Keeping my cards close to my chest at the moment. There is still room for improvement.

Electro: How many .Net entries did you receive for the last competition? I know me and Mendhak did but were there any others? It's a major rebuild to rewrite your VB6 app for .net, and the auto convert tool in VS.net can't upgrade things like AutoRedraw and Redim(,).

If there are more than 6 VB.net coders then I'll do it, otherwise its not really worth the effort. :)

VB6 is sooo backward! :lol:

[alkatran]

Question: Can I check the form's caption? I just realized that move player doesn't add any points if the man doesn't move. And I can use the form's caption to figure out if the score change. :afrog:

[alkatran]

Originally posted by cyborg
Damn this is hard!

My algo is huge so far and really stupid!
I get 198 points on the first map, 502 on the second, and on the third it gets locked into an infinite circle at about 450 points!

I've added some small memory for the player, but I'm a bit confused on how to deal with it the best way...

Maybe it's a good idea to add a bit of random movement, so you don't get stuck... But then it's not possible to measure the same way....

Please tell me what you get!

My algo completes all 3 maps fine... but that's because it searches every possible location... I still need to tweak it to avoid stupid things like that...

I scored 1246 on the second map because of it's large area to the east.

[Pino]

There was 16 Vb6 entries which are allmost marked and would be finished if it wasnt for maths Coursework :(

and 9 .Net entries

[alkatran]

It would really be nice if "look" returned how many blocks to the first wall in that direction. That would contrast it from lookabout nicely. But then it would be worth more points...

So far I see almost no reason to use lookabout, better off running almost blind with look.

[wossname]

Originally posted by alkatran
It would really be nice if "look" returned how many blocks to the first wall in that direction. That would contrast it from lookabout nicely. But then it would be worth more points...

So far I see almost no reason to use lookabout, better off running almost blind with look.

;)

[manavo11]

Actually I started making a .Net version :) It still needs some work however with the drawing (BitBlt or whatever is needed)... I'll do some searching...

Wossy, do you want me to send it to you?

[Electroman]

Posted by alkatran
Question: Can I check the form's caption? I just realized that move player doesn't add any points if the man doesn't move. And I can use the form's caption to figure out if the score change. :afrog: The Move should add points on whether or not the move was possible.

[alkatran]

!IMPORTANT!

I found a bug. The reason it wasn't working is it gets stuck in an infinite loop:

If the move fails TARGETX and TARGETY are NOT SET so they are 0. That and the position of the dot doesn't move. So the condition:
Loop Until picPlayer.Left = TargetLeft And picPlayer.Top = TargetTop
is never satisfied

That's why the score wasn't moving.

[alkatran]

I'm really realizing how LITTLE data we have now. :sick:

As of yet a pathfinding algorythm seems excessive. There's just too much unknown... :ehh: '

Must.. think..

[Merri]

I realized how little data we had just by reading about the three functions.

Here is a fix to the MovePlayer function. I'm sure this is easier to copypaste than to download the whole project again.


TargetLeft = picPlayer.Left
TargetTop = picPlayer.Top
Select Case Direction
Case 1 'North
If CurY > 0 Then
If Not (MapData(CurX, CurY - 1) = 1) Then
DirToMove = 1
CurY = CurY - 1
TargetTop = TargetTop - 25
End If
End If
Case 2 'East
If CurX < MapWidth - 1 Then
If Not (MapData(CurX + 1, CurY) = 1) Then
DirToMove = 2
CurX = CurX + 1
TargetLeft = TargetLeft + 25
End If
End If
Case 3 'South
If CurY < MapHeight - 1 Then
If Not (MapData(CurX, CurY + 1) = 1) Then
DirToMove = 3
CurY = CurY + 1
TargetTop = TargetTop + 25
End If
End If
Case 4 'West
If CurX > 0 Then
If Not (MapData(CurX - 1, CurY) = 1) Then
DirToMove = 4
CurX = CurX - 1
TargetLeft = TargetLeft - 25
End If
End If
End Select



And btw, Electroman: you can't change the name of the main form, because that'd make everyone's code not to work - they're calling frmMain all the time! :D

[alkatran]

Originally posted by Merri
And btw, Electroman: you can't change the name of the main form, because that'd make everyone's code not to work - they're calling frmMain all the time! :D

I only call it three times. :thumb:

[alkatran]

More bugs:

If you finish a map, reload, and press start again, it assumes you're done.

You also misspelled compLEted


and the form seems to have trouble closing. I need to use the stop button.

I put an "END" in query unload to fix it. Bad practice... but it works quick

[Electroman]

Posted by alkatran
I found a bug. The reason it wasn't working is it gets stuck in an infinite loop:

If the move fails TARGETX and TARGETY are NOT SET so they are 0. That and the position of the dot doesn't move. So the condition:
Loop Until picPlayer.Left = TargetLeft And picPlayer.Top = TargetTop
is never satisfied

That's why the score wasn't moving. In what situation was this happening? If you are pressing Start more than once then it wasn't made for that. Same as for when you complete a map then try another one. It was just made to test one map at a time ;).


I'll admit the project was rather rushed and under tested due to me being short of time recently and wanting to get this ready for you when the last one ended.

I'll update the attachment with your chnage too Merri.

[Electroman]

Just to let you know we are thinking about changing the score for the LookAbout() function to either 4 or 5 from 6. This is because as it stands LookAbout has no advantage and this wasn't meant to be the case. Will let you know what we decide....

[StevenHickerson]

LookAbout() has no advantage...

I only use LookAbout :) It has no advantage.. but no disadvantage either. I see no reason to even use Look as is and your talking about decreasing LookAbout... might as well just get rid of Look haha.

I have my algo capable of completeing all 3 maps (sometimes, depends on a random in some areas lol) and have not had any problems with the provided code.

There is something very gratifying about making an AI Algo capable of doing this when you've never worked on something like this before.. even if my little ratblock is really stupid.. he gets the job done :) I just gotta figure out ways to make him smarter now.. anyone got some Super block cheese laying around? :rolleyes:

Right now the best my ratblock can do on test 1 is like 270 points.. if he makes all the right 'choices'.. test 2 he finished with like 3900 but I know that isn't the best possible for my particular algo hehe. And test 3 was 890 but not the best.

[alkatran]

I want to say how I use lookabout as an advantage but it could ruin part of my chances.

[Merri]

Do not make any changes. As now, in default settings LookAbout and Look are equal and balanced. Besides you'd make a lot of my code null and void because I optimized it to use Look instead of LookAbout, because it is kind of harder to use Look. They're pretty balanced now imo. I do use both in the code though.

The only thing you could change is the points from moving the player. I think it is too cruel to add 3 points from moving, because we're forced to move and if the code just happens to pick wrong direction to go to (my algorithm is based on random, so it always works differently), it adds an awful lot of points to go first wrong path and then go back to where it was...

[alkatran]

Actually, LookAbout is like a quick Look right now. If you move to an area chances are you know everything about the square you were just on. So the most you can possibly reveal, except at the start, or if you decide to move blind for awhile, is 3 sqaures (3 looks, 6 points)

[Merri]

Whee, most of the time my code now completes the first maze with a score below 300 and it just scored 1152 on the second maze with the first try.

[alkatran]

Originally posted by Merri
Whee, most of the time my code now completes the first maze with a score below 300 and it just scored 1152 on the second maze with the first try.

"most of the time"?

[alkatran]

952 on second, 200ish on first

[Merri]

236 is the lowest score you can get on the first maze. I just scored 776 on the second. The lowest score for second is 396 if I counted right. My calculations assume you do a check at all unknown nearby blocks on each new block you encounter.

"Most of the time" means, it chooses paths randomly. The randomizer brings in a weakness: if it happens to choose a bad path more than once, the score gets high. The power of the randomizer is that it has the possibility to hit the lowest possible score :)

[alkatran]

Well I score 220 on the first maze, 952 on the second, and 326 on the third one.

So I guess you can get lower than 236. :bigyello:
Don't forget you don't have to look at all, so the real minimum is more like 90

[alkatran]

I've been drawing out possible paths with rules etc... and it looks like that the SEVERE lack of data makes any ideas I have worthless.

[alkatran]

Score just dropped to 198 on first map. Second down by 20 points, third up by about 50.

[Merri]

Yes, but that won't allow you to do some nice stuff such as memory. I'm improving the memory of my routine so it won't run for naught in the same places over and over again. The third maze is a great sample for this.

Hmm, now that I checked, I do have a small counting error somewhere. So the lowest score for second maze is smaller than what I told. There is always so many thing to notice :D But anyways, I can't hit below 236 with my routine on the first maze - the price of memorizing.

I'm doing a general routine that will work fine on any possible map, not only in the given maps.



Edit Whee! I just scored 510 in the second map :D
Edit Oh great, now it ran to 416! Too bad this happens so rarely - random is random...

[cyborg]

Originally posted by Merri
I can't hit below 236 with my routine on the first maze - the price of memorizing.

I've got 198 on the first and im using memory.

I just thought of a new way to use the memory, so I'm hoping to get far under 500 on the second map! So far, I'm almost walking the straight way.

[Merri]

But do you memorize everything on the road, not only where going to and where been? That's what I do and I probably don't take it off. Atm my plan is to make it work nicely for large open areas as well, not just mazes (mazes are easy to cheat in with the memorizing).

So, here we have an open map:

[Merri]

And here is another nasty level: if you have poor memorizing or no memorizing at all and get into the middle route... well, good luck with you! :D

[alkatran]

Yes, I'm worried about different maps being a problem. Mine won't handle open areas very well at all. A very low score on maps here could be completely changed on a different map (left turn instead of right, oh no!)

[StevenHickerson]

Lol by the sounds of it Merri is doing something very similiar to me. Currently my lowest possible score on the first map is 270, but I could probably get it lower if I change some things.

236 would be hard to hit while memorizing everything though =/ in fact I dont see how you can score under 270 and memorize everything... I'm still playing with it though right now mine can get in trouble in open areas if it pulls a couple bad randoms in a row.

EDIT: Actually I did just think of one way to drop below 270 while memorzing everything.. but still dosn't seem like it would drop it to 236.. although it might.. I'd have to go back and change quite a few things to accomondate for the new idea.

[Merri]

Basically, the best you can do with memorizing + randomizing combination is to shrink out the bad choices. I even have to write an actual pathfinding algorithm thanks to the memorizing, to get rid of the too random walking around the open areas. I have some nice stuff done already to prevent that, but... it just isn't enough.

But I'm happy with the current results already. Most of the time it really looks like if it was a person who is a maze and he can't see around :)


Edit Btw, how many actual rows do you codes have atm in the whole module? I have 285.

[StevenHickerson]

Right now I have 247 including all my declerations and types, but it will probably go up some when I add some more code to make it smarter. You said yours looks like a blind person running around the maze.. lol mine would be a blind, clumsy, and stupid men :)

I really gotta put in some code to make it handle open areas better than it does right now, especially since right now I can get stuck in a loop if a few bad randoms happens in an open area ... (you can basically think of it as it backs itself into a corner and then just paces a path back and forth).

[Merri]

Hehe, I've avoided that. I thought about that right when I started making the code so even if it ends up running around for a while in an open area, it does get the hell out of there too and is very unlikely to return for a while :D

The length of my code will go greatly up when I add some real pathfinding.

[Merri]

Yes another map. This one, not being a maze and not being an open area, makes it really hard to go anywhere fast. I'm sure any every possible routine has problems with this one. But if we think about it, a human would have hard time with this kind of place too. If you can remember Moria from the first movie of the Lord of the Rings, think the place without light and then you should find a small hole somewhere in the middle to get out.

[wossname]

Originally posted by manavo11
Actually I started making a .Net version :) It still needs some work however with the drawing (BitBlt or whatever is needed)... I'll do some searching...

Wossy, do you want me to send it to you?

Actually, you could save my bacon and take over completely if you want. I've got loads of actual work to do (yawn) and I won't have time.

However to make it up to you I've just given you a reward on the sandpaper project thread (see post 2) :D

Sorry electro, I'll have to hand over to Manavo. However I will actually write a VB6 entry for this pathfinder thingy!!! :shockhorror:

And it will completely pwn you all. (Hah, that's what I said last time :D)

[wossname]

My current alg is kickass. Remembers EVERYTHING and {classified}. Uses about 1kb ram :)

w0000oooot!

[Ecniv]

A question - I doubt I'll be entering but its nice to pass the time ;)


Can you code an analysis of the maze?? Like befor eyou move to calc the best route, or do you need to move as though you were in the maze ?

For example, I've read other peoples posts and they are using memory (remembering the route you've taken I guess, which is including backtracking) but are they remembering a previous run through the maze???
Surely the scores would be lower if it remembers a previous run...? Cheating?


Sheer luck if you get the lowest amount on a route if you can't analyse the maze first! :)

Just wondering


Vince

[Wokawidget]

Errrr...???
Just seen this new contest. Hmmmm.
This has nothing to do with AI in the slightest...why do people think it is AI? :confused:

If one coder looks left 1st and another looks right 1st when it's time to move, then certain maps are going to benefit one persons code. Their code isn't better, it's the same, but it just checks to see whats left instead of right?

Oh and your demo doesn't work.

It keeps doing the same thing moving in a circle then the point stops moving.

Woof

[manavo11]

Originally posted by wossname
Actually, you could save my bacon and take over completely if you want. I've got loads of actual work to do (yawn) and I won't have time.

However to make it up to you I've just given you a reward on the sandpaper project thread (see post 2) :D

Sorry electro, I'll have to hand over to Manavo. However I will actually write a VB6 entry for this pathfinder thingy!!! :shockhorror:

And it will completely pwn you all. (Hah, that's what I said last time :D)

Hehe, thanks :D

Anyway, it's going well except for the drawing. Lacking the autoredraw, I put everything in the paint event of the picbox but still has issues :( If you could help with that it would finish a lot faster :rolleyes: :D

[Slaine]

I have no intention of entering - the main reason being I don't have time to code anything.

But I have had a quick look at the supplied project and I can see a way to implement a solution that will "always" take the shortest path to the exit without using any of the look functions.

[manavo11]

Originally posted by Slaine
I have no intention of entering - the main reason being I don't have time to code anything.

But I have had a quick look at the supplied project and I can see a way to implement a solution that will "always" take the shortest path to the exit without using any of the look functions.

Read the file?

[Merri]

Well, find player's position, use GetPixel to find out the route and voilá! You've cheated your way to the finish. I can make a bet that will be disqualified.

[Slaine]

Neither of those methods

[cyborg]

My algo gets stuck on rounte4 and 6 but it finishes route5 in 671 points.

It's 185 lines with comments counted.

[cyborg]

Come on guys! Tell me what points you get! :sick:

With my current algorithm:
Route1: 194
Route2: 484
Route3: 336
Route4: 1450
Route5: 591
Route6: 3381

Could someone please make a 300x300 map so I can test my algo? :D

[riis]

Maybe a stupid question. Are we allowed to change the Option Base to anything we like? It could ruin the maze after all... :D
I just started with this, so I can't brag about my results yet ;)
There are also loads of maze generators on the internet. It might be a good idea to use one for customized mazes :) Now if only someone would volunteer to create one... ( :looks at Electroman: )

[StevenHickerson]

Originally posted by Wokawidget
Errrr...???
Just seen this new contest. Hmmmm.
This has nothing to do with AI in the slightest...why do people think it is AI? :confused:

If one coder looks left 1st and another looks right 1st when it's time to move, then certain maps are going to benefit one persons code. Their code isn't better, it's the same, but it just checks to see whats left instead of right?

Oh and your demo doesn't work.

It keeps doing the same thing moving in a circle then the point stops moving.

Woof

I would disagree, this is very basic AI. It's almost like putting a rat in a maze with cheese at the finish. The random numbers are as if it's making a choice on which way to go, because lets face it thats about all anyone can do if they were put into a situation like this, randomly choose a direction to go.

Sure this isn't some learning algo that can get smarter the more mazes it runs, but I'd still say it is rudimentary AI. If not then what would you call it?

[wossname]

Actually, I'm not going to bother with this contest.

Not pointing any fingers, but this one hasn't been though out well enough. This contest is perfectly suited to OOP, but is aimed at VB6, which seems a bit oxymoronic to me, but hey, its all gravy baby. :)

[alkatran]

We need to do a contest where the people in the maze interact, and it should be a team contest. :afrog:

[cyborg]

Originally posted by alkatran
We need to do a contest where the people in the maze interact, and it should be a team contest. :afrog:

Yeah! Load all contributions as different classes into the same 300x300 maze and run them at the same time and see who wins! It could be broadcasted online or recorded to a file to be downloaded and played back later on. That'd be really cool! :bigyello:

[riis]

I had 1372 points in map 6. But sometimes my algorithm looks really brain-dead, having a favour for the "trodded paths" :D
It is pseudo-random, but I should make it more clever.
At least it is able to reach the finish usually :)

[Electroman]

Posted by cyborg
Yeah! Load all contributions as different classes into the same 300x300 maze and run them at the same time and see who wins! It could be broadcasted online or recorded to a file to be downloaded and played back later on. That'd be really cool! :bigyello: Will work on this, probably won't be the next contest but could be the one after it.

As for the Maze Editor I will try and make one in the next couple of days, depending if I get time.

As for the Scoring I think i'll keep it how it is then. I have thought of ways where it will make a differance of which you chose so there is still reason for having both of them.

[riis]

Originally posted by cyborg
Come on guys! Tell me what points you get! :sick:

OK, gloat and laugh all the way you want. I've also generated some statistics. I've run every map 10 times. (Had to disable the animation for that, sorry Electroman ;) )

Route 1 2 3 4 5 6
Average 277.4 2041.4 580 1922.2 1098.4 1717
Median 256 1459 553 1801 786 1699
Minimum 236 822 344 240 586 274
Maximum 334 3614 976 3534 2788 3582

This is still the brain-dead algorithm, but I have several ideas to improve it.

[Merri]

Originally posted by wossname
Not pointing any fingers, but this one hasn't been though out well enough. This contest is perfectly suited to OOP, but is aimed at VB6, which seems a bit oxymoronic to me, but hey, its all gravy baby. :)

Which means you got stuck and don't have the skills to participate :D j/k

Nah, to think about it, I'm joining even though I don't like it all that much. Atleast I bother to support the contest thing so it doesn't start to fade away right in the beginning.


Anyways, I just got a small thought thanks to what Steven said: it'd be great if we got some warning "you're close now", so we wouldn't have to see that the small man goes by the finish just a block away and then goes elsewhere. But oh well, it does works now as well.


As for my results: they vary a lot depending on how the randomizer happens to work its way out. Looks like we're splitting to two main categories of codes:

- semi-AI: works with a memory and a randomizer, trying to figure out good decisions
- solid: makes always the same decisions (thus no AI involved)

I think we can't really compare the two... solid algorithm runs always the same way, where as random-based have the possibility to reach the finish the shortest possible route - they just don't always succeed in it because of the randomizing. Though, I'm happy to tell my code has never ran over 3500 points this far in any of the mazes :)


I can code a support for bigger mazes. Probably make a whole new project. Maybe I'll add support for simultaneous run, so there can be multiple players on the field the same time :) I've some other ideas too.

[alkatran]

So, the goal isn't to reach the end, the goal is to cover the most ground, hoping you hit the end.

[Merri]

Just out of interest: cyborg, how does your algorithm run on the second maze when you switch the positions of the finish and the start?

[cyborg]

Originally posted by Merri
Just out of interest: cyborg, how does your algorithm run on the second maze when you switch the positions of the finish and the start?


It did some really bad choices and went back and forth in some dead ends a couple of times but I got 732. :)

I would really like to know how good my algorithm is when flipping the maps in x or y axis, although I don't have time to flip them manually right now... Maybe in a couple of days! :rolleyes:

[riis]

In case anyone cares, and another attempt to "visualize" Tolkien's world with this contest, I've created Minas Tirith (with some extra gates at the inner walls). The player is standing just inside the gates at level 1, and needs to reach Denethor in time, to warn him about the upcoming danger. One difference, he absolutely has no clue he should go to the highest level ;)

I've created the map, so people who tend to search along the edges should make their algorithm possibly smarter. For me this map shows that I shouldn't keep track on one path for too long, but should switch directions more often.

If more people are going to submit custom maps (hopefully with different types), then we get the chance to test our own algorithms better, to check the strengths and weaknesses.

[cyborg]

I inverted the start/finish of the rest of the maps and got these points:

1: 194
1i: 320
2: 484
2i: 732
3: 336
3i: 474
4: 1450
4i: 2177
5: 591
5i: 568
6: 3381
6i: 1393

[riis]

Here's another one, H-maze. The maze resembles some fractalized H's (normal, and rotated 90 degrees). The start and end point are laying relatively close to each other, but it's also possible to go the wrong road entirely. And I've made the hallways 2 cells wide on purpose :)

[riis]

Originally posted by cyborg
I inverted the start/finish of the rest of the maps and got these points:
[SNIP/]
6: 3381
6i: 1393
This is a remarkable difference, since the map is pretty symmetric. (The start and end points aren't.) Have you optimized your algorithm to go northwest? :)

[cyborg]

My algorithm is REALLY lousy on open areas right now, so it's just whirling around for ages in the four rooms....:blush:
It's optimized for going first hand left (from it's view) then right then back when hitting a wall or walking on the same space twice.

If you have the guts to run it, I've attached the compiled version of my program so you can see the ways it chooses (i've changed the frmMain a bit to fit my needs when developing).

[cyborg]

Damn, those maps owned my algorithm! :blush:

minastirith: 4325
h-maze: 2503

I'm planning on visualizing the "brain" of my algorithm in a picturebox while running so I can see exactly what it knows... That would make it much easier to develop it further.

[Merri]

I have the same problem, even though I thought hard the whole thing in my mind before starting out (heh, it has been about the same since writing the code the first time), it would ease to be able to see visually how it works. So I probably make advanced debug mode to my own maze program.

Got 706 in the H-Maze with the first try and 1442 in Minas Tirith.

[cyborg]

It might be good to add an A* algorithm too... So you easily can check the remaining places at the end of a large map.

I'm not using anything random at all right now, cuz it's not that reliable imho....
Do you have any code to mark dead ends? I think I'll add that later on if I have some more spare time...

Btw, Electroman: I think that the squares in the maze should be much smaller so a large map could fit easier.

[Electroman]

Posted by cyborg
Btw, Electroman: I think that the squares in the maze should be much smaller so a large map could fit easier. I just chnaged my version so that each tile is 9x9 (same as the player was), just meant goign though all the code and changing all the 25's to 9's and removing the red bit I've highlighted here: picPlayer.Left = 8 + x * 9
picPlayer.Top = 8 + y * 9

Would an A* algo work? I thought you needed the Start and End Co-ords for that?

[cyborg]

Thanks! That's much better!

Originally posted by Electroman
Would an A* algo work? I thought you needed the Start and End Co-ords for that?

It would work because I've got memory in my algorithm.
If you've walked through a large map and finally one small area remains unexplored on the other side of the map from where you're at. You just calc the fastest path to that area using A*.

[Merri]

Here is how to fix the "close form and the program doesn't terminate" bug:


'on form...
'add to declarations:
Private UnLoading As Boolean

'at MovePlayer
'Animate...

Set sTimer = New sTime
sTimer.Init
sTimer.StartTime
Do
Do
'add this row here!
If UnLoading Then Unload Me: Exit Function
DoEvents
sTimer.StopTime
Loop While sTimer.RetTime < (0.06 / lblSpeed.Caption)

'and a new sub
Private Sub Form_QueryUnload(Cancel As Integer, UnloadMode As Integer)
UnLoading = True
End Sub


And then before you call frmMain.MovePlayer, frmMain.Look or frmMain.LookAbout in the module:


If Forms.Count = 0 Then Exit Sub


And voilá! No more stop button pushing or End :)

[riis]

Originally posted by Merri
I have the same problem, even though I thought hard the whole thing in my mind before starting out (heh, it has been about the same since writing the code the first time), it would ease to be able to see visually how it works. So I probably make advanced debug mode to my own maze program.

Got 706 in the H-Maze with the first try and 1442 in Minas Tirith.
:gasp: I got about 1500 in the H-maze and 2600 in Minas Tirith.
My algorithm is too much biased on going straight. (That's why it's doing pretty well in open areas, but not well in maps with lots of branches.) I need to change that.
ATM I'm marking dead ends, and have built a backtrace function, when I'm only hitting cells I've already passed.

[Merri]

Well, if it helps you, my code also made its worst score ever on Minas Tirith. Because I haven't coded one really important thing yet, it is possible for the code to run in maps like that forever before finding the finish. Anyways, it ran 4198.

I tried changing it to going straight and then always to choose turning and then switching between the two, but none of those worked well. So I'm back to my original code which I coded in one sit :D It had three bugs in the first run, but after fixing those... it has been the same. But I really need to add the real pathfinding...

I mark dead ends too. It never goes back to deadends.

[wossname]

OK maybe I will have a go, but under protest! :D

If I win with my VB6 entry you must all admit that VB6 is lame and I pwn it. Then you must all learn VB.Net immediately. :lol:

[wossname]

I think there is absolutely NO excuse to use randomness in this excercise unless you are using some kind of GA or ANN.

Randomness is rarely optimal in any circumstance.

[riis]

Well, if you have no randomness, then it is possible to solve a certain maze pretty fast, but if you switch the start and end locations (like Cyborg did), then it can take much more time. Therefor it makes no sense to "optimize" your algorithm for a certain type of maze, since you won't know what to expect. With Cyborg's executable, I can create a maze with which his player will have an awful hard time.

With randomness, you have sometimes "luck", sometimes "bad luck", but usually an average case. That is not necessarily worse than the average of a non-random case (normal situation, and situation with switched locations). In the end the winner will just have the best algorithm, be it random or be it non-random.

Personally I think it's interesting to see how random algorithms and non-random algorithms perform, compared to each other.
I've implemented some randomness in my algorithm, to have some bit of extra luck when I need it. I know that it also has some drawbacks. Since I don't know the mazes on beforehand (which will be used to test the entries), I don't care. The most important thing is that your algorithm doesn't do anything stupid (like running into the same dead ends multiple times) and that your algorithm reacts in a clever way in unknown circumstances.

[cyborg]

Originally posted by riis
Well, if you have no randomness, then it is possible to solve a certain maze pretty fast, but if you switch the start and end locations (like Cyborg did), then it can take much more time. Therefor it makes no sense to "optimize" your algorithm for a certain type of maze, since you won't know what to expect. With Cyborg's executable, I can create a maze with which his player will have an awful hard time.

So far, it looks like my algorithm is pretty good, and I have not even made it mark dead ends etc... It's pretty stupid walking down the same dead ends and already explored huge rooms etc... That's what makes my algo bad right now. I will improve it. So I don't think randomness is needed. :o

[bpd]

I was considering logic improvements when I came upon an interesting question: Can the end point be the same square as the starting point? Based on the development harness provided, the answer is "No". However, the only things we can be certain of are the three publicly exposed methods and, by implication, that a publicly available object (which may or may not be a Form object) exposing those methods will be named "frmMain".

In case you're interested, the reason that this is important is in the case where the starting and end points are the same and this square happens to be at the end of a corridor. I was considering “blocking” dead-end corridor paths, but doing so under these conditions would mean that I would *never* find my way back to the end point.

[riis]

Well, in that case, just don't block the corridor where the start point lies. Or, go away one square and back again :)

[bpd]

Originally posted by riis
Well, in that case, just don't block the corridor where the start point lies. Or, go away one square and back again :) Clearly there are solutions, but my question is whether there's even the possibility of such a problem.

I'm trying not to get side-tracked on solutions to a problem that may not even exist.

[riis]

In case anyone is interested, I've adjusted frmMain that it changes the colour of the locations which are requested by the Look en LookAbout methods, and also the location where the player ended up after a MovePlayer method. The initial colors aren't black and white, but two shades of grey. Blocked locations will appear black, once known, and free locations will appear white. Locations which are passed by the player will appear yellow. This way you can nicely see the coverage of the player.
If correctly coded, it should also more or less be equal to the "mental map" of the player (except for possibly blocked locations and other statistics).

Note: Merri's adjustments for the unload bug aren't included, since I couldn't get them working in my app (yet).

Note 2 I've updated the attachment, since the color of the finish cell could become overrided. (I think the start cell could still be overrided, but I don't see that as a real problem.)

[riis]

Here is a screenshot.

http://www.vbforums.com/attachment.php?s=&postid=1802099

If you would like to change the colours, just do so in the original picture boxes on the form. These are called picBlock2, picPass2 and picPass3.

I've also adjusted the buttons, and added a combobox where you can load various maps. They need to be in the same direction as the project/executable and have TXT-extension. Also the StartGame will set the map to the original settings (it calls LoadMap), so you won't have to unload the debug session/executable to start again. :)

[Merri]

I just improved my code so that it behaves MUCH better on open areas (before that open areas were a big problem for me) while still behaving the good old same in non-open areas (in most cases). Looks like avarage points on open maps went down by almost a half :) Have to do more testing though.

Oh yea. First REAL improvement to my code since I first wrote it. Whee! :D

[Merri]

The Power Of Random!
http://www.vbforums.com/attachment.php?s=&postid=1802123


Just to warn you: I've improved my code, I'd say it is about 75% smarter than what it was. It rarely makes a "stupid" move now :)

[Merri]

Continuing with my line of nice maps, here is something big: so big, it doesn't show up right! It is a 50 x 50 map, where it tests non-horizontal and non-vertical movement. It looks like this:


/ / / / /
/ / / / /
/ / / / /
/ / / / /
/ / / / /
/ / / / /
/ / / / /


Uhhuh... not the clearest possible but... :)

[Electroman]

Posted by Merri
Continuing with my line of nice maps, here is something big: so big, it doesn't show up right! It is a 50 x 50 map, ...... Yea its because with the old size I had it limit how big the map it displayed could be. Heres the code you need to change: If MapWidth < 11 Then
picDisplay.Width = (m_clGridSize * 11 + 5) * Screen.TwipsPerPixelX
ElseIf MapWidth > 30 Then
picDisplay.Width = (m_clGridSize * 30 + 5) * Screen.TwipsPerPixelX
Else
picDisplay.Width = (m_clGridSize * MapWidth + 5) * Screen.TwipsPerPixelX
End If

If MapHeight < 5 Then
picDisplay.Height = (m_clGridSize * 5 + 5) * Screen.TwipsPerPixelY
ElseIf MapHeight > 30 Then
picDisplay.Height = (m_clGridSize * 30 + 5) * Screen.TwipsPerPixelY
Else
picDisplay.Height = (m_clGridSize * MapHeight + 5) * Screen.TwipsPerPixelY
End If

[Ecniv]

Merri:
Does your algo get the start and end points...?
I posted before about whether the proggy should do this and whether it would be classed as cheating or not?

That last pic post you made suggests you are getting the end location and homing in on it...


:)

Vince

[Merri]

Nope, I'm not getting it :) It can do anything between a medium result and a good result. I've completely disabled the possibility to Worst Ever results :D

Excellent result = directly to the finish (our target, but what is impossible for us most of the time)
Good result = get to the finish without walking on the same place twice
Ok result = get to the finish visiting the same places a few times
Medium result = get to the finish after going through all/almost all places with minimum possible rewalk on previous places
Bad result = get to the finish after walking around the whole map a lot
Worst Ever result = be barely be able get to the finish...

Atm my code is rather heavy/slow. Too much looping within loops. And that's only because we couldn't get the size of the map and the starting position... it would be so much faster if we just had that basic info, I could easily get rid of most the silly loops that way. Hmm, oh well, I'll spend some time optimizing/rewriting the current code and it should get much better and easier to handle.

[cyborg]

Originally posted by Merri
Atm my code is rather heavy/slow. Too much looping within loops. And that's only because we couldn't get the size of the map and the starting position... it would be so much faster if we just had that basic info, I could easily get rid of most the silly loops that way. Hmm, oh well, I'll spend some time optimizing/rewriting the current code and it should get much better and easier to handle.

Originally posted by Electroman
We will be running your code with a variety of different maps of sizes ranging upto 300x300 and will be recording the scores.


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


:rolleyes:

[wossname]

Originally posted by cyborg
Dim MapMemory(-300 To 300, -300 To 300) As MemoryUDT


:lol::bigyello:

[alkatran]

Originally posted by cyborg

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


:rolleyes:

That's what I did! :lol:

I could've done 0 to 300 and used a few mod statements... but meh.

Actually I worked on this for 2 hours, got it so it could solve any map (no open areas please!) and submitted it.

I'm just so dedicated.

The only change I can see making is identifying when it's covered an open area and pathing out of it instead of backtracking.

[Electroman]

Posted by alkatran
That's what I did! :lol:

I could've done 0 to 300 and used a few mod statements... but meh.

Actually I worked on this for 2 hours, got it so it could solve any map (no open areas please!) and submitted it.

I'm just so dedicated.

The only change I can see making is identifying when it's covered an open area and pathing out of it instead of backtracking. Note, there will be at least one map with some open spaces in it ;).

[alkatran]

Can I resubmit?

[StevenHickerson]

You know random is very annoying sometimes.. I can't figure out how its getting a certian random through... I changed how my memory works to hold more information and to do away with some other parts of code, and now my little guy will do a 180 while going down a corridor .. and I have it set saying that if the random direction coming from is the way it came from to ignore it and not go that way lol.

Stupid block.. err wait I made it that means I'm .. darnit.

But one thing, I actually had forgotten they said the max size would be 300.. thinks for reminding me, that will make some things in my memory easier.

[alkatran]

Hehe, I made code to invert maps for me. Here's some of my paths, too.http://www.vbforums.com/attachment.php?s=&postid=1803505

[alkatran]

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.

[alkatran]

Screenie:http://www.vbforums.com/attachment.php?s=&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.

[Electroman]

yea, you can resubmit

[alkatran]

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:

[StevenHickerson]

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.php?s=&postid=1804014

That dern H-maz and Minas really mess up my algo hehe :)

[alkatran]

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)

[StevenHickerson]

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

[alkatran]

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.

[alkatran]

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.

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


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

[alkatran]

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.

[alkatran]

A lucky search on that one for me!
http://www.vbforums.com/attachment.php?s=&postid=1804063

[alkatran]

and a not so good
onehttp://www.vbforums.com/attachment.php?s=&postid=1804069

[Merri]

Originally posted by cyborg

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.

[BodwadUK]

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

[alkatran]

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

[alkatran]

See, I get too hooked on doing this.
http://www.vbforums.com/attachment.php?s=&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?

[alkatran]

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

[alkatran]

I think I'm gonna win!


Option Explicit

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

[StevenHickerson]

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.

[alkatran]

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.

[alkatran]

I just like posting these pictures
http://www.vbforums.com/attachment.php?s=&postid=1804638

[riis]

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

[StevenHickerson]

Hrmm Completely Random:

http://www.vbforums.com/attachment.php?s=&postid=1804014

Only random in certian situations:

http://www.vbforums.com/attachment.php?s=&postid=1804769

I need to find a good combination of the two....

[Electroman]

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

[riis]

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.

[riis]

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

[riis]

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)

[riis]

And a screenshot for the ones who aren't participating.

It took about 6 or 7 minutes to complete.

http://www.vbforums.com/attachment.php?s=&postid=1804861

[NotLKH]

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

[riis]

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.

[NotLKH]

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

[StevenHickerson]

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

[Electroman]

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

[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 :)

[cyborg]

Sunday sounds great! I've been really busy with work, but now there's no more of that this week! :thumb:

[cyborg]

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

[cyborg]

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.

[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:

[cyborg]

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:

Didn't you save the zip?

[Merri]

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.

[StevenHickerson]

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

[Merri]

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:

[alkatran]

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.

[BodwadUK]

Route1 = 236
Route2 = 1052
Route3 = 394
Route4 = 664
Route5 = 1076
Route6 = 3536

Thats mine currently anyway :)

[riis]

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

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

[alkatran]

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

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

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)

[BodwadUK]

Mine learns so it should eventually on move not search as it already 'Remembers' the route :)

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

[riis]

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.

Yeah, it's leaving "breadcrumbs", and since the little guy is apparently hungry, he traces them back, in order to eat them ;)
I'm having the same problem, since I implemented pathfinding, but other maps are going better :)

[alkatran]

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.


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.

[StevenHickerson]

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.

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.


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.

[Electroman]

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. In case you missed my post which i explained the scoring system it is here: http://www.vbforums.com/showthread.php?s=&action=showpost&postid=1804057

But I still haven't decided whether an average will be taken (http://www.vbforums.com/showthread.php?s=&action=showpost&postid=1804800), I'll decide this and let you know tomorrow though.

[StevenHickerson]

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:

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

[riis]

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

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.

[riis]

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

[BodwadUK]

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

[Merri]

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.

[riis]

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

[BodwadUK]

Ok fixed pattern logic :lol:

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

[Merri]

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

[Electroman]

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

[wossname]

\/\/h3n 1s teh d3adline?

[BodwadUK]

Sunday I think :)

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

[alkatran]

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

[Electroman]

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.

[StevenHickerson]

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.

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

[alkatran]

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:

[alkatran]

My stats:

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.php?s=&postid=1806747

[alkatran]

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.

[Merri]

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

[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 ;)

[alkatran]

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:

[SLH]

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

[Merri]

Whee, the entries are there.

[Electroman]

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 10th map now, waiting for it to backtrace quite a distance and its taking ages :(. On the 5th map I was able to go and make my lunch, eat it then still had to wait for it to finish :lol:.

[Merri]

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

[Electroman]

Results are in: http://www.vbforums.com/showthread.php?s=&threadid=308231