Contest 2 - PathFinder

Quote:

---

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.

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

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.

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

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

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)

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.

Quote:

---

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

952 on second, 200ish on first

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

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

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.

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

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

Quote:

---

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.

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:

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

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

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.

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.

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

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.

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.

Quote:

---

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)

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

w0000oooot!

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

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

Quote:

---

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

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.

Quote:

---

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?

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.

Neither of those methods

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

It's 185 lines with comments counted.

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

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

Quote:

---

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?

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

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

Quote:

---

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:

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