Contest 2 - PathFinder

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

Quote:

---

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.

Quote:

---

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

Code:

---

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.

Quote:

---

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.

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

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?

Quote:

---

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:

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.

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

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

Quote:

---

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

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

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.

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.

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.

Quote:

---

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:

VB Code:

picPlayer.Left = [color=Red]8 +[/color] x * 9
picPlayer.Top = [color=Red]8 +[/color] y * 9

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

Thanks! That's much better!

Quote:

---

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

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

VB Code:

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

VB Code:

If Forms.Count = 0 Then Exit Sub

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

Quote:

---

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.

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.

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:

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.

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.

Quote:

---

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

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.

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

Quote:

---

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.

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

Here is a screenshot.

http://www.vbforums.com/attachment.p...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. :)

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

The Power Of Random!
http://www.vbforums.com/attachment.p...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 :)

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:

Code:

---

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

---

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

Quote:

---

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:

VB Code:

If MapWidth < 11 Then
        picDisplay.Width = (m_clGridSize * 11 + 5) * Screen.TwipsPerPixelX
    ElseIf MapWidth > [color=red]30[/color] Then
        picDisplay.Width = (m_clGridSize * [color=red]30[/color] + 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 > [color=red]30[/color] Then
        picDisplay.Height = (m_clGridSize * [color=red]30[/color] + 5) * Screen.TwipsPerPixelY
    Else
        picDisplay.Height = (m_clGridSize * MapHeight + 5) * Screen.TwipsPerPixelY
    End If

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

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.

Quote:

---

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.

---

Quote:

---

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.

---

VB Code:

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

:rolleyes:

Quote:

---

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

---

:lol::bigyello:

Quote:

---

Originally posted by cyborg

VB Code:

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.

Quote:

---

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

Can I resubmit?

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.