Maze Traversal

All help appreciated

  • (2 Pages)
  • +
  • 1
  • 2

26 Replies - 14315 Views - Last Post: 06 June 2010 - 02:29 AM

#1 potator  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 5
  • View blog
  • Posts: 84
  • Joined: 02-December 07

Maze Traversal

Posted 21 August 2008 - 09:13 PM

So for my senior year in high school, I have to do a Research Practicum (RP) project. It is basically a science fair with a college paper attached. My idea so far consists of a program that generated random mazes and traverses them using Depth-first search, Breadth-first search, and other searching methods. It then compared their times and memory usage, determining which is most efficient.

I kinda like this idea of maze traversal, but I'm not too excited about doing something as widely tested and DFS vs BFS. Any suggestions? I'm also open to totally new ideas for my project since I haven't started working on it yet.

Is This A Good Question/Topic? 0
  • +

Replies To: Maze Traversal

#2 1lacca  Icon User is offline

  • code.rascal
  • member icon

Reputation: 44
  • View blog
  • Posts: 3,822
  • Joined: 11-August 05

Re: Maze Traversal

Posted 22 August 2008 - 04:56 AM

You could spice it up with some randomness, so the strategy is changed (alternated) every (few) steps. It might be interesting to see the effect, and it will need some additional thoughts (creating a data structure that can be used by both, or more algorithms ) as well (the implementation will greatly affect your results). Just an idea...
Was This Post Helpful? 0
  • +
  • -

#3 modi123_1  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 9363
  • View blog
  • Posts: 35,172
  • Joined: 12-June 08

Re: Maze Traversal

Posted 22 August 2008 - 08:53 AM

Don't forget the "right hand" method of maze travel - put your right hand out, touch the wall, and follow the right hand touched wall until you are out..
Was This Post Helpful? 0
  • +
  • -

#4 potator  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 5
  • View blog
  • Posts: 84
  • Joined: 02-December 07

Re: Maze Traversal

Posted 22 August 2008 - 03:52 PM

Quote

Don't forget the "right hand" method of maze travel - put your right hand out, touch the wall, and follow the right hand touched wall until you are out..


yeah that was one of the other solutions.
Was This Post Helpful? 0
  • +
  • -

#5 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3106
  • View blog
  • Posts: 19,145
  • Joined: 14-September 07

Re: Maze Traversal

Posted 23 August 2008 - 07:47 AM

It is your left hand, I thought...
Was This Post Helpful? 0
  • +
  • -

#6 modi123_1  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 9363
  • View blog
  • Posts: 35,172
  • Joined: 12-June 08

Re: Maze Traversal

Posted 24 August 2008 - 02:39 PM

View PostKYA, on 23 Aug, 2008 - 09:47 AM, said:

It is your left hand, I thought...


Well left handed abilities show taint of the devil and should be avoided. Plus I think Michael Savage lumps lefties in with the 'red diaper doper babies'.
Was This Post Helpful? 0
  • +
  • -

#7 potator  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 5
  • View blog
  • Posts: 84
  • Joined: 02-December 07

Re: Maze Traversal

Posted 12 October 2008 - 07:43 PM

View Postmodi123_1, on 24 Aug, 2008 - 02:39 PM, said:

Well left handed abilities show taint of the devil and should be avoided. Plus I think Michael Savage lumps lefties in with the 'red diaper doper babies'.


Yeah that's why they originally made guns and other such things only for right-handed people.
Was This Post Helpful? 0
  • +
  • -

#8 GWatt  Icon User is offline

  • member icon

Reputation: 278
  • View blog
  • Posts: 3,078
  • Joined: 01-December 05

Re: Maze Traversal

Posted 12 October 2008 - 09:56 PM

I'm going to agree with your instinct about maze solving being boring. Pretty much every way to solve them is a brute force algorithm. The only way I could see maze solving become interesting is if you did it in three or four dimensions.
Was This Post Helpful? 0
  • +
  • -

#9 potator  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 5
  • View blog
  • Posts: 84
  • Joined: 02-December 07

Re: Maze Traversal

Posted 23 November 2008 - 12:12 PM

Yeah, well I went with this idea anyway because I couldn't get a text-based adventure creator approved as "scientific research" The program is running now and i should have a boatload of data in a couple days. When I do eventually analyze it, I'll be sure to post some graphs.
Was This Post Helpful? 0
  • +
  • -

#10 Louis+Clovis=Lou_is  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 06-April 10

Re: Maze Traversal

Posted 30 May 2010 - 08:23 AM

About the right hand rule in the maze.
It's is use to validate the maze right?
can someone explain in more details for me?
Was This Post Helpful? 0
  • +
  • -

#11 Tom9729  Icon User is offline

  • Segmentation fault
  • member icon

Reputation: 180
  • View blog
  • Posts: 2,641
  • Joined: 30-December 07

Re: Maze Traversal

Posted 30 May 2010 - 09:09 AM

View PostLouis+Clovis=Lou_is, on 30 May 2010 - 10:23 AM, said:

About the right hand rule in the maze.
It's is use to validate the maze right?
can someone explain in more details for me?

What kind of maze? Are there loops?

I'm not a maze expert but my understanding is that you pick a wall and stick with it (eg. left or right wall) and eventually you will get out of the maze. Obviously if there are loops/cycles in the maze then this might not work...
Was This Post Helpful? 0
  • +
  • -

#12 Louis+Clovis=Lou_is  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 06-April 10

Re: Maze Traversal

Posted 30 May 2010 - 06:58 PM

my program name is Maze Traversal and i need to create function that use right hand rule to validate my randomly generated maze and also to find the path to traversal the maze.
Was This Post Helpful? 0
  • +
  • -

#13 programble  Icon User is offline

  • (cons :dic :head)

Reputation: 49
  • View blog
  • Posts: 1,315
  • Joined: 21-February 09

Re: Maze Traversal

Posted 30 May 2010 - 07:01 PM

Walking in circles can be fun guys!
Was This Post Helpful? 1
  • +
  • -

#14 Louis+Clovis=Lou_is  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 06-April 10

Re: Maze Traversal

Posted 30 May 2010 - 07:18 PM

what do you mean by that?
Was This Post Helpful? 0
  • +
  • -

#15 programble  Icon User is offline

  • (cons :dic :head)

Reputation: 49
  • View blog
  • Posts: 1,315
  • Joined: 21-February 09

Re: Maze Traversal

Posted 31 May 2010 - 12:02 PM

Exactly what I said.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2