Jump to content
  • Advertisement
Sign in to follow this  
LinkOfTime

Hi, I need help with a school's project...

This topic is 4759 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi (I hope I posted this message on the right page :) ) Anyway, I am looking for an algorithm for a robot I am building as a final project at school. I need the robot to be able to go through a maze (without an ending) from a beginning spot and enter each room it encounters on it's way... Rooms can be on the left or right side of the robot and can be told apart from corridor entrances. It should only enter each room once and should check all the rooms without missing any of them. It can turn around abd go back on it's tracks but only when really necessary (like where there is no where else to proceed - a dead end :) ). Now, I already know an algorithm to do what I need but, it uses some previous knowledge of the maze's turns and rooms whereabouts before even beginning to run in the maze. I am looking for an algorithm which will be able to run in any maze without having previous knowledge of how it's built. Thanks in advance for all of the help... :) I tried to think of such an algorithm but couldn't find any...

Share this post


Link to post
Share on other sites
Advertisement
Don't use an algorithm but use some kind of dectors or something so that whenever it sees a room it turns into it, follows the wall until it goes out of the room then keeps going? Basically changing direction on collision :P.

Only other thing I know to do would be to scan the level and put it into some kind of array and then you can use pathfinding like normal (think of it like forsight :P).

Share this post


Link to post
Share on other sites
Without any knowledge of the maze beforehand, you have to use a very inefficient algorithm. You can guarantee you will traverse every room by just following the right wall -- if there is a right turn, then you will turn right, and if there is a dead end you will turn around, just like the wall does.

Share this post


Link to post
Share on other sites
I thought of the follow the right wall algorithm as well but, in my case, it wouldn't have worked because there is a room in the middle of the building, not connected to any of the outer walls and it's entrance is on the left...

The only way I found to solve this maze (thought of it after posting the message) was to actually use an array (like you suggested, shadowisadog), but, instead of scanning it beforehand, "drawing" it into memory as you go through the maze so you wouldn't visit rooms you have already visited... Then, you could use the "stick to the right wall method" but enter rooms on your right and LEFT as well (but not corridors on the left, only rooms).
This was the only algorithm I thought of that could actually work...

Thanks for trying everyone anyway :)

Share this post


Link to post
Share on other sites
I don't see any way of solving the problem without keeping track of rooms visited. You can try to mimimize backtracking by using some kind of heuristic to decide which unvisited room or corridor should be visited next. Probably best to choose the nearest, unless there are multiple unvisited rooms apart from each other, then you'd probably do best to find the shortest route though all of them.

Share this post


Link to post
Share on other sites
As I've said on the other similar post, you may start with a recursive (or backtraking) fill algorithm (marking the visited rooms) and when it works optimize it for speed or path length.

Share this post


Link to post
Share on other sites
>following the right wall -- if there is a right turn, then you will turn right

The 'follow the right'-wall trick doesn't work if the goal is on
an island in the middle of the maze

Share this post


Link to post
Share on other sites
Quote:
Original post by LinkOfTime
Hi (I hope I posted this message on the right page :) )

Anyway, I am looking for an algorithm for a robot I am building as a final project at school.
I need the robot to be able to go through a maze (without an ending) from a beginning spot and enter each room it encounters on it's way... Rooms can be on the left or right side of the robot and can be told apart from corridor entrances. It should only enter each room once and should check all the rooms without missing any of them. It can turn around abd go back on it's tracks but only when really necessary (like where there is no where else to proceed - a dead end :) ).
Now, I already know an algorithm to do what I need but, it uses some previous knowledge of the maze's turns and rooms whereabouts before even beginning to run in the maze.
I am looking for an algorithm which will be able to run in any maze without having previous knowledge of how it's built.

Thanks in advance for all of the help... :)
I tried to think of such an algorithm but couldn't find any...


I believe that if you make it follow the wall on one side of it, it will, no matter what, always find the exit - if there is one.

Share this post


Link to post
Share on other sites
I've done something like this before. What you want to do is to put detectors, as many as possible on the robot(you can do it with one though). Now the detector should be able to measure the distance to a solid in front of it. Spin the robot. You now have a record of everything in the area of your detector radius. Now move to the edge of the area and try again. Keeping expanding your area. Now here is the tricky part. You need to be able to convert the detector readings into a grid of somekind.

One way to test it is to simulate it on the computer. That will probably help a lot.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!