Jump to content




Maze Generator


15 replies to this topic

#1 Jack

  • Members
  • 19 posts

Posted 26 December 2012 - 08:33 PM

This is a maze generator for turtles! It's just a rough draft; I wanted to work out the essentials before ironing out details. It uses the well-known recursive backtracker algorithm. Just load it into a turtle on solid terrain and watch it carve the passages.

Known issues:
-Does not yet refuel. If it's a big issue, this should be easy enough for you to add.
-If you use it underground, it will be very dark and monster-prone.
-No current known problems!

Please let me know if you discover bugs. Criticism is requested and constructive criticism is preferred.

Screenshots:
A size-8 maze under construction
Spoiler
A completed size-8 maze
Spoiler
A completed size-16 maze
Spoiler

Code:
http://pastebin.com/LACe82ar
Spoiler


#2 Jack

  • Members
  • 19 posts

Posted 29 December 2012 - 03:39 AM

Updated! Added screenshots to OP.

#3 Ulthean

  • Members
  • 171 posts

Posted 29 December 2012 - 05:30 AM

Looks nice.

Does the maze always stretch out across the entire square? Or is there a possibility that some parts might be left untouched?

#4 Cranium

    Ninja Scripter

  • Moderators
  • 4,031 posts
  • LocationLincoln, Nebraska

Posted 29 December 2012 - 06:23 AM

I do like this. I might have to use this in an ice dungeon I'm plannign on making.

#5 Jack

  • Members
  • 19 posts

Posted 29 December 2012 - 09:19 AM

View PostUlthean, on 29 December 2012 - 05:30 AM, said:

Looks nice.

Does the maze always stretch out across the entire square? Or is there a possibility that some parts might be left untouched?

It is a perfect maze, which means that any point can be reached from any other point by exactly one path. No untouched passages will remain. The algorithm doesn't actually choose an exit, but any point might work for one. It's up to you to choose a path.

#6 Jack

  • Members
  • 19 posts

Posted 29 December 2012 - 09:22 AM

Updated again.

#7 Amdusias

  • Members
  • 10 posts

Posted 01 January 2013 - 01:21 PM

You've probably still got the version without the automatic refuel thing?
Because i m playing Tekkit and its still CC 1.3 over there.
But look good so far!

#8 AndreWalia

  • Members
  • 294 posts
  • LocationSt.Louis, MO

Posted 01 January 2013 - 01:50 PM

I suggest the turtle places lime wool at start and red wool at end

#9 AndreWalia

  • Members
  • 294 posts
  • LocationSt.Louis, MO

Posted 01 January 2013 - 02:02 PM

I made it so that begining the maze is better. So you cant type in anything, its a press any key.
replace
print("Place torches in slot 1 and fuel in slot 16, then press enter.")
read()
with
print("Place torches in slot 1 and fuel in slot 16")
print("Press any key to continue...")
os.pullEvent("key")


#10 steel_toed_boot

  • Members
  • 25 posts

Posted 01 January 2013 - 07:51 PM

Looks awesome.

#11 Churik

  • New Members
  • 5 posts

Posted 03 January 2013 - 08:23 AM

Hehe, noob question:
Do I have to change anything about it to use it on tekkit?
I know tekkit has a older version, but don't know the exact changes between the old and new version.
If so, what do I need to change? :$

#12 DocHuzz

  • Members
  • 1 posts

Posted 14 January 2013 - 07:24 PM

Hey mate I have been fooling around with this program of yours and I noticed a couple of issues. Following the right hand rule (always pick the right hand passage) nearly always gets you to the ending. I could change this by putting the end somewhere in the middle, so no big deal. The other issue I found is that the maze size is not related to the number you put in all that well. For instance, a size 8 maze was 14x14. What's the algorithm for the size? Great freaking program though!

#13 Jack

  • Members
  • 19 posts

Posted 20 January 2013 - 06:29 PM

walia6: That's a nice interface change, and a good idea with the red and green wool.

steel_toed_boot: Thank you!

Churik: Sadly, I know nothing about Tekkit or related compatabilities.

DocHuzz: Yes, since it generates a perfect maze, it is acyclic, which means that sticking to either wall is guaranteed to find you the exit eventually, regardless of which points you choose as start and end. Also, the size 8 maze wasn't actually 14x14, it was 16x16 (counting the outer edges). This is because the code deals with nodes rather than adjacent blocks. Each node is separated from each other node by a one-block space. I suppose I could have just divided the user's input by 2 and saved this trouble... but I'm lazy. :P Good question, though!

#14 YoYoYonnY

  • Members
  • 49 posts

Posted 14 November 2013 - 11:35 AM

View PostMr.Coder, on 01 January 2013 - 02:02 PM, said:

I made it so that begining the maze is better. So you cant type in anything, its a press any key.
replace
print("Place torches in slot 1 and fuel in slot 16, then press enter.")
read()
with
print("Place torches in slot 1 and fuel in slot 16")
print("Press any key to continue...")
os.pullEvent("key")
Better use os.pullEvent("char") or the event might happen as soon as you press enter (after entering the command "maze <size>" in CraftOS)

#15 Zudo

  • Members
  • 800 posts
  • LocationUK

Posted 14 November 2013 - 11:45 AM

Nice.

#16 DarkShadowsX

  • Members
  • 3 posts
  • LocationPlanet Earth.. i hope..

Posted 05 April 2014 - 07:04 AM

this will be great to test with my maze solver turtle program
thanks.





1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users