Maze solver

All about creating levels and level sets, custom elements and custom artwork.

Moderators: Zomis, Flumminator

Tomi
Posts: 339
Joined: Wed Aug 03, 2005 3:37 pm
Location: Slovakia

Maze solver

Post by Tomi » Mon Nov 14, 2005 6:32 pm

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

Zomis
Posts: 1501
Joined: Mon Jun 21, 2004 1:27 pm
Location: Sweden
Contact:

Post by Zomis » Tue Nov 15, 2005 11:34 am

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!

Tomi
Posts: 339
Joined: Wed Aug 03, 2005 3:37 pm
Location: Slovakia

Post by Tomi » Tue Nov 15, 2005 6:11 pm

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

Zomis
Posts: 1501
Joined: Mon Jun 21, 2004 1:27 pm
Location: Sweden
Contact:

Post by Zomis » Wed Nov 16, 2005 6:21 pm

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

User avatar
Martijn
Posts: 794
Joined: Sat Jun 19, 2004 10:54 am
Location: the Netherlands (Holland)
Contact:

Post by Martijn » Wed Nov 16, 2005 6:26 pm

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!
Visit my Boulder Dash website at:
http://www.bd-fans.com

Watch my avatar! That orange little thing is Murphy, the Supaplex star!

Tomi
Posts: 339
Joined: Wed Aug 03, 2005 3:37 pm
Location: Slovakia

Post by Tomi » Wed Nov 16, 2005 7:21 pm

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

HerzAusGold
Posts: 326
Joined: Sun Sep 25, 2005 4:41 pm
Location: Germany

Tools

Post by HerzAusGold » Wed Nov 16, 2005 10:26 pm

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".
_________________
And the answer is ... 42 !

Tomi
Posts: 339
Joined: Wed Aug 03, 2005 3:37 pm
Location: Slovakia

Post by Tomi » Thu Nov 17, 2005 10:33 am

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

Zomis
Posts: 1501
Joined: Mon Jun 21, 2004 1:27 pm
Location: Sweden
Contact:

Re: Tools

Post by Zomis » Thu Nov 17, 2005 9:59 pm

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!

Tomi
Posts: 339
Joined: Wed Aug 03, 2005 3:37 pm
Location: Slovakia

Post by Tomi » Fri Nov 18, 2005 8:19 am

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.

User avatar
Alan
Posts: 661
Joined: Fri Jun 18, 2004 7:48 pm

Post by Alan » Fri Nov 18, 2005 11:26 pm

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.

Tomi
Posts: 339
Joined: Wed Aug 03, 2005 3:37 pm
Location: Slovakia

Post by Tomi » Sat Nov 19, 2005 8:23 am

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.

HerzAusGold
Posts: 326
Joined: Sun Sep 25, 2005 4:41 pm
Location: Germany

Makefile

Post by HerzAusGold » Sat Nov 19, 2005 6:13 pm

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...
And the answer is ... 42 !

HerzAusGold
Posts: 326
Joined: Sun Sep 25, 2005 4:41 pm
Location: Germany

maze solver

Post by HerzAusGold » Mon Nov 21, 2005 10:03 pm

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.
And the answer is ... 42 !

Tomi
Posts: 339
Joined: Wed Aug 03, 2005 3:37 pm
Location: Slovakia

Post by Tomi » Tue Nov 22, 2005 4:39 pm

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

***********
*P1231231E*
*****2*****
    ***
(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

Post Reply