Maze solver
Moderators: Flumminator, Zomis
Maze solver
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: http://www.zomis.net/rnd/download.php?id=386
Oh, I almost forgot, here is it: http://www.zomis.net/rnd/download.php?id=386
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!
Great work, Tomi!
Visit my Boulder Dash website at:
http://www.bd-fans.com
Watch my avatar! That orange little thing is Murphy, the Supaplex star!
http://www.bd-fans.com
Watch my avatar! That orange little thing is Murphy, the Supaplex star!
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
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
-
- Posts: 362
- Joined: Sun Sep 25, 2005 4:41 pm
- Location: Germany
Tools
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.
http://www.zomis.net/rnd/download.php?id=387
For more information look at "New Ideas", "Sokoban".
_________________
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.
http://www.zomis.net/rnd/download.php?id=387
For more information look at "New Ideas", "Sokoban".
_________________
And the answer is ... 42 !
> 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! How did you do that?"
P.S. Guess what levelset am I currently working on...
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! How did you do that?"
P.S. Guess what levelset am I currently working on...
Re: Tools
I am also unable to start the file, it says I need cygSDL-1-2-0.dll and a couple of other cygSDL-dlls.HerzAusGold wrote:http://www.zomis.net/rnd/download.php?id=387
Tomi: I'm really looking forward to see that levelset I am impressed of your work so far, keep up the good work!
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.
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.
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.
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.
-
- Posts: 362
- Joined: Sun Sep 25, 2005 4:41 pm
- Location: Germany
Makefile
Hi
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...
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...
And the answer is ... 42 !
-
- Posts: 362
- Joined: Sun Sep 25, 2005 4:41 pm
- Location: Germany
maze solver
Hi,
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.
*Edit
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.
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.
*Edit
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.
And the answer is ... 42 !
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:
The CEs are set like this: (e.g. when 1 highlights, it chages to "highlighted 1". "highlighted" elements look like supaplex base)
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
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
***********
*P1231231E*
*****2*****
***
(P=player, E=exit, *=wall)
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
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