Page 1 of 2

Maze solver

Posted: Mon Nov 14, 2005 6:32 pm
by Tomi
This simple level solves any maze containing only empty space, wall, player and exit and highlights the path. Uses 10 CEs. Maybe finds shortest path, but I'm not sure about it. If there are two equally long paths, it highlights both.

Oh, I almost forgot, here is it:

Posted: Tue Nov 15, 2005 11:34 am
by Zomis
Ouch, too bad I'm in school so I can't test it right now :(
But it surely sounds very promising...! If it works great, I'll definetly will rate this level as 10 on the archive!

Posted: Tue Nov 15, 2005 6:11 pm
by Tomi
Well, unfortunately there are some bugs, for example sometimes it highlights more paths (as I already mentioned before) and sometimes you can't enter the exit, but it's still great in its simplicity. (Hope the bugs will get fixed in next version.)

Posted: Wed Nov 16, 2005 6:21 pm
by Zomis
Well... so far I haven't discovered any problems with it, it really looks nice! So I've rated it with 10 (best!) at the archive. We'll see how this technique can be extended, maybe I will have time to work some with it...

Posted: Wed Nov 16, 2005 6:26 pm
by Martijn
It's really great! I never knew that THIS would be possible by just checking a number of checkboxes in the CE configs!

Great work, Tomi!

Posted: Wed Nov 16, 2005 7:21 pm
by Tomi
The bugs I've mentioned are hidden but can happen.
bug 1 - exit: sometimes you can't enter the exit. That's because the exit CE looks like:
changes to self after 5 frames
changes to real exit when touched by player
When you touch it just at the moment it changes to self, you won't be able to enter it and you have to touch it again. Luckily, I've already fixed that and will update soon.
bug 2 - more hilighted paths: it doesn't happen in the maze it's shipped with, but try to place empty space on level position 2,2 and you'll see what I mean.

> Great work, Tomi!
Well thanks... btw there aren't just checkboxes :)


Posted: Wed Nov 16, 2005 10:26 pm
by HerzAusGold
Where are all the tools you use?
ConfEdit, aso.
I am als searching for the tool which generate the "conf_" sources.
And a tool for the PCX-Files (SnagIT always broken my files).

Find the way through a maze. -Hm- Have a look to my rndTest-Version.
Click on an empty reachable place.

For more information look at "New Ideas", "Sokoban".

Posted: Thu Nov 17, 2005 10:33 am
by Tomi
> Where are all the tools you use? ConfEdit, aso.
I don't use ConfEdit, nor RNDTool, nor any other tool, but just R'n'D itself and some normal text editor for conf files. However, as I know, ConfEdit wasn't released for public yet and I'll surely test it when it will.

> I am als searching for the tool which generate the "conf_" sources.
I think it was just some simple script. I think I could do one if I'd have time (and you'd seriously need it).

> And a tool for the PCX-Files (SnagIT always broken my files).
Well I use Linux and KDE comes with some very nice tools (KIconedit, Kolourpaint), but there's also Gimp (both for Linux and Win) and as I know, even Windows' Paintbrush...

> Find the way through a maze. -Hm- Have a look to my rndTest-Version.
> Click on an empty reachable place.
I downloaded it but I play R'n'D in Linux and would have to dowload all the needed SDL_* libs for windows etc., and I can't build it in Linux for some reason.

I know it's easy to create a maze solver in normal programming language, but it's an amazing thing when done with CEs. Let me explain on an example:
Imagine that you're making a simple RPG. I mean very simple RPG - no party, no advanced fight system, player has just about 5 inventory items and some numbers - hit points, strength, experience points etc. Nothing very good, I think.
Imagine that you're making it in R'n'D. After 3 months of hard work you'll finally release first episode, containing a village, a forest and few monsters. But everyone who knows a little about making CEs will say, "That's totally great! :shock: How did you do that?"

P.S. Guess what levelset am I currently working on... :wink:

Re: Tools

Posted: Thu Nov 17, 2005 9:59 pm
by Zomis
I am also unable to start the file, it says I need cygSDL-1-2-0.dll and a couple of other cygSDL-dlls.

Tomi: I'm really looking forward to see that levelset ;) I am impressed of your work so far, keep up the good work!

Posted: Fri Nov 18, 2005 8:19 am
by Tomi
Well as I already said in some other thread (don't remember its name though), there isn't a very big chance that I'll finish it... and it looks like that I'll need some very advanced tool for more comfortable CE editing, so I have to learn some multiplatform GUI lib, so I... etc etc etc...

Btw HerzAusGold: could you tell us which files have you modified in rndTest? Let's hope that there isn't any platform dependant code in them and then it would be easy to replace those in the original source and voila! it could work on any platform where R'n'D does.

Posted: Fri Nov 18, 2005 11:26 pm
by Alan
This is cool! 8)

Did you base it on the algorithms from that maze site?

With a bit of tweaking I'm sure you could make it into random maze generator, with a 100% perfect solution.

Posted: Sat Nov 19, 2005 8:23 am
by Tomi
No, I created the algorithm myself :)
I knew the way that for each field you remember number of steps from the beginning and when you find an exit you'll go back when the number decreases, but that's just impossible in R'n'D... so I modified it to remember one of 3 states and it worked.

> I'm sure you could make it into random maze generator
Well maybe... I dont know how though. I'll look at it if I'll have some time.


Posted: Sat Nov 19, 2005 6:13 pm
by HerzAusGold
I upload a makefile for "rndTest".
See topic "New Ideas","Sokoban"
Please answer here.

btw: I prefer QT on Windows. Is available at Linux too.
I am familiar with linux a little bit.
But I never develop on linux (it's a shame I know).
I want to test this and hope this is not a very strange journey...

maze solver

Posted: Mon Nov 21, 2005 10:03 pm
by HerzAusGold
taking a look on the CEs you create.
I'm surprised that is so easy.
Very good work.
But if the exit is reachable from all sides it's found "more" and longer ways to the exit. And if there are two exits it's find both.
But I think this don't matter in a maze.

Btw: I use the standard algo for maze, starting with the target place you want walk to.

Hm, one question.
The numbers in the wrong path don't change to "green curcuits".
Why? They touch the curcuit too.
Please can you explain this.

Posted: Tue Nov 22, 2005 4:39 pm
by Tomi
Yes, it's great in its simplicity. As you've already found out, it's suited only to basic mazes (no multiple exits etc.), but it shouldn't be too hard to fix. (I'm working on other things currently though.)

As for your question, let me try to describe how does the solver work.
The trick is that each field has one of 3 types (the numbers 1,2,3). Let's say we have this simple maze:

Code: Select all

(P=player, E=exit, *=wall)
The CEs are set like this: (e.g. when 1 highlights, it chages to "highlighted 1". "highlighted" elements look like supaplex base)

Code: Select all

1: "highlights" when touching exit
   "highlights" when touching highlighted 2
2: "highlights" when touching exit
   "highlights" when touching highlighted 3
3: "highlights" when touching exit
   "highlights" when touching highlighted 1
Now, the 1 touches exit and highlights. The 3 touches highlighted 1 and highlights. The 2 touches highlighted 3 and highlights. The 1 touches highlighted 2 and highlights. But the 2 in the bottom line *doesn't* highlight, because it doesn't touch highlighted 3.

If I'd make a maze solver outside R'n'D, I'd make it the way that each square remembers number of steps from the start - the squares touching the start position are 1, the squares touching 1s are 2, the squares touching 2s are 3 etc. Let's say that square 18 touches exit. I'll set the color of the square to "green" (or something like that). Now I'll explore the neighbors of the "18" square. There is some 17, so I'll advance to it. I'll set the color to green and find a 16, and so on, and finally, I'd get to 1 and the player will just walk on the green path.
Unfortunately, that just isn't possible in RnD. Big mazes could have not only 18 but 293 and there's just not enough CEs. Instead, the solver remembers only one of 3 types - so you can still trace back to the start.
I just hope somebody will understand the thing I just wrote...

*EDIT* just corrected one mistake in the text