   Robot Maze.
  (I know the message is long, but it is long for easy to read, so please read it)I am ready new to robot maze and I have to do it as my lecture told us to do the assignment. Even my lecture say this is master work. So, for me, it will be a hard work. I have a few question. Below is not question, but background.The game is in PC, not real robot.It is about a robot that create to collect token of ''A'' to ''Z''. The size of maze is unknown, the start position is unknown, even the robot is face in which direction is unknow(North?? West??)So, we have to collect the path in front and remember it.OK, the robot has a three protype.1) turnLeft(); // Turn left2) turnRight();// Turn right3) move(int num);  // Move (num) step4) RobotView look(); Look the path in front.Call of each function will be count for one step. Except look().For the RobotView, it has the struct below.   class RobotView{   public: left[5]; center[5]; right[5];}It mean it will look at 15 square in front of robot face. If it is face in the west, it will look in front of west of 15 square. However, if there is something block, the view may no seen at all. Like these.  +---+  |???|  |?#?|  |#  |  |#A |  |#  |  +-R-+  The # mean wall, R mean the robort, ? mean place can''t view, space mean empty roas, and A mean the tokenOK, here is the question. 1) After I have been making a whole day with the AI of navigate the maze. I face a big problem. I am ready new to AI, I don''t know where the robot should go first. [[Important]] Please please tell me how to chose the place to go. After that, I try to add some AI by my own(Ready bad, not a AI), I scan the the road in front, if it is not a wall, then I can move in front. If it is a wall in front, then I turn left. Then I keep going. It is like follow left hand way. Then I get the circular pattern.###    ################## #   #------| #    |  ^# |  H   #   #|_ |#   #   ####################  There is a problem, I can not get to scan the H token. I know it is a big mistake in AI for follow the left hand side. After that, I try to put the another AI, that is if the beside is have a big empty road, then I turn to it. It make my robot just turn circle. After that, I put the AI that I also don''t know what is it to do. Yes, the robot have more complex road, and bigger to navigate. After that, I find that it is just a big circle. The more complex, the big the circle. I am dead of it. So, PLEASE TELL ME HOW TO CHOOSE THE WAY TO GO. READY PLEASE.2) I have see the a* path finding, I am ready don''t know what is it??? It will take me a big head. I understand it for about 50% and for my sitution, I have to change the path into turn left, turn right, move..... It is not a good time for me now. After that, I am think of my own path finding like the floodfill() function like. It scan every direction and recusive function. I try to do it but fail. The function like don''t end. Then I search for the site. Some have say about the pathfinding same like I think. But for saving the step have been travel I ready fail to understand. So, can anybody, if can, some code please. It will be easy than word.3) As I don''t know where the robot to start. and how big the maze is. I can''t set the maze as a big big maze. It will lost mark. How to re arange the position when the maze grow. It will be negative. So, any idea. I have an idea to set the robot position in my maze start at the middle position. Then it move, if it move to the position out of map, I have to re build the map, and copy the old map to a bigger map. Then how to do with the robot position. Any idea of how to update the positon. My head is become bigger and bigger.Thank you for seeing my question as it is so long. If can, please answer it with some brief explain(or detail), algorithm(Finding where to go), and the best, some code. I know C++ and VB. Thank you. 
  Well, you mentioned using A* for path finding, which is one of the best, if not the best.  However, A* requires the terrain or "maze" to hold information about itself the robot can query, such as movement difficulty and other things.  That being said, we can assume it is safe to store data in the maze you are making.  One solution is to store a few pieces of data into each cell, or square, of your maze.  This data can represent the following: how many times has the robot been in this square, and how many times has the robot looked at this square.  Knowing these can help to solve your "circular" problem.  In that example, the robot goes forward, turns left, goes forward, turns left, goes forward, turns left, and then goes forward.  Now he is in the square he started at.  But instead of just blindly point to the left, you can examine the squares around him.  The robot can say, "I have already been in the square to my left now, so I need to either go straight or turn right."  Now, if turning left is his only option, then he has no choice.  But by knowing where the robot has already been and what cells he has already looked at, he can make better decisions on where to go and hopefully avoid the circular problem you encounter.  Hope this helps.Again, this is just one simple, off the cuff idea.  There are 1000''s of ways to do it I imagine.;  Also, what are the goals of your program/  Is it to collect the tokens and that''s it?  Or is efficiency through the maze important also?  I would assume it is, but ya never know.  If it is just "collect all tokens" and no other requirements, you could easily just say at each square randomly turn left or right and go.  Eventually, he would get all the tokens.  This isn''t very intelligent, but will get the job done.  How important is the efficiency for this project?;  *Moderator hat on*First of all, this is an assignment for assessment, so I want everyone to keep that in mind while replying. It does no one any good if we simply give code that solves this problem. The point of an assignment is that the student learns; in this case, how to solve an exploration task. I understand that jeff_khor is struggling with this assignment, but he''ll be better off for having understood and implemented the solution than having simply downloaded it and submitted it.*moderator hat off*Having said that...This is a very common assignment problem for university level courses in AI. How complex your solution is depends on you and your algorithmic abilities.While this is not necessarily the best approach to solving this problem, it''s one of the easiest:Sit down with an example maze, choose some locations for the tokens (A to Z) and a random starting spot for your robot. Ask yourself, if you were the robot, how would you search the maze. Write down all of the rules you use that relate the context the robot is in (current position, sorts of walls around, what can be seen, etc) to the actions it takes. When you''ve done this for all of the contexts you can think of, then encode this information in simple rules. Write a lookup method that chooses a single rule given an input context.Alternatively, you can have the robot explore the maze and build a map. This map should be able to store information about tiles and their connection to other tiles (along the lines of Stonicus'' idea). At any time that the robot finds that in its map there is a tile with a connection to a tile that it has not explored (like a passage it hasn''t been down, or a room it hasn''t looked into) then it should choose the closes of these unknown areas and investigate it (move to it and look into it). At any time that it finds a tile that it hasn''t looked at or moved over that is surrounded by other tiles that it has looked at and/or moved over, then it should move to the closest of these tiles and look at it. If at any time the robot sees a token, it should move to it and pick it up. How you make these decisions and implement them is up to you, but this is a basic algorithm for exploring unknown areas.One suggestion for your map... and this is as far as I will go with coding suggestions... design a ''tile'' data structure that stores information about the tile (which sides connect to other tiles, which sides are walls, is there something in the tile (a token for instance), is there a side that we don''t know whats there, etc). Each ''tile'' should have pointers to neighbour tiles so that your collection of these ''tile'' data structures forms a map that can be used to move from one tile to any other, by performing a search in the map. You''ll need a way to identify connections to things that haven''t been explored. This method of storing your map will save you the problem of having to grow and array to store the map in and will make storing information a little more efficient.Good luck with your project,Timkin ;  Yes, I get a lot of new idea. I have to re think how to make it. Anyway, if anyone see it got any new idea please post it to help. For this project. The efficent is needed. The lowest step is the best. My lecture say the lowest step will get the bonus mark. But I don''t think I success to get it.Thank you. ;  Suppose I''m the kind of robot that will stick my left hand on the wall and start running.. when my left hand doesnt feel anything I will turn left and take a step.. if there is something right in front of me and I also can''t turn left I will then turn right and take a step..   It can be shown that this wont visit every spot in a random maze. But a good trick might be to count the number of times you''ve been at particular spots - you never go left if you''ve been there more times than you''ve gone right, for example.  The wall avoidance can be generalized into this path-count avoidance algorithm - mark walls as having been visited an extremely large amount of time -- if using 16 bit unsigned, set walls to having been visited 65535 times.  Now to restate what kind of robot I am:  Suppose I run towards the least visited spot I see directly around me.. - Rockoon;  Have anybody make the floodfill path finding?The floodfill like path find don''t work.I try to use recusive but fail to return if a path has been find. bool findpath(int x, int y, char map[10][10]){   if(map[x][y] = ''X''){ // Got itreturn true;   }   if(map[x][y] = ''#''){ // Wall return false;   }   // Here is something terible wrong   return findpath(x + 1, y);   // I am think some idea that I don''t know   // If find a path, return, else continue   // But it is wrong.   // int ret = findpath(x + 1, y);    // if(ret) return ret;  return findpath(x - 1, y);   return findpath(x, y + 1);   return findpath(x, y - 1);}after that I try to change it into form of using stack, but fail to write it. Bad coding, I know. I just want to ask if a floodfill like path finding can be done or not? ;  The first thing you must do is create a data structure that can store what the robot currenly knows about the maze.  I would recommend creating something similar to a doubly-linked list.class Cell{public:    char whateverIsContainedInThisCell;    // ' ', 'A'-'Z', '#', or '?'    Cell *up, *down, *left, *right;}   This way you can grow the map easily in any direction without copying a gigantic and sparse array.  The robot can have a Cell* in order to keep track of its position.Secondly, you must decide where the robot should move.  If a token ('A'-'Z') is visible, then you should go and collect it (using A*, I assume).If no tokens are visible, then the primary job of the robot should be to explore.  In order to explore, you should look for the closest '?' THAT IS BORDERED BY A ' ' !!!  It must be bordered by a ' ' in case you have a maze that looks like this:################### #########    ###?????#    ###??####    ######  ## ###################  The area inside is enclosed, so the robot has no chance of getting there, and shouldn't bother trying.  To look for the closest '?', use a breadth-wise search of some sort (you do NOT need to move the robot for this).Once you have found the closest '?', use the A* algorithm to move the robot there and look around.  Whatever data you have picked up from the look() method should be added to the map of Cell objects.  Then either pick up a token (if you've found one), or go and explore some more.I'd be curious to hear how well this algorithm works.[EDIT] forgot code tags around the maze example   [edited by - boyohboy17 on February 19, 2004 12:40:47 PM];  boyohboy17, did you even read my post? You''ve basically reiterated exactly what I said, which is a waste of bandwidth. If you did read it, then there''s no need to repeat it unless you''re improving on it, or correcting an error in it! If you didn''t read it, then in future, please read what other people have written before you reply... it''s considered good forum ettiquette.As for your suggested data structure it needs to include a cell type   attribute, which delineates between the possible types in the maze: empty, wall, unexplored   and token  . This will prevent the occurrence of the example you provided with the wall surrounding the unexplored regions, since these regions are not part of the map and hence don''t need to be added to the data structure. By making the wall   type of cell have only one connection (to the cell it borders) you create a natural boundary to the maze through the lack of further pointers to other cells from wall cells.jeff_khor, don''t worry about the flood-fill algorithm for now. Just make sure you can set up a simple maze data structure (a connected map of tiles), that your robot can identify its state in the maze (i.e., the robot knows which of the tiles in the maze it is standing on), that it can move to another tile or receive a list of visible tiles when it executes an action and that it can pick up a token if it sees it. These are the basics of your system. Design your program so that you can test each one of these things by issuing orders to your robot from the command line. Once this is working, you can then think about designing an appropriate AI to replace the command line input, that decides which actions to take given the known map, any observations made and the current state of the robot.Cheers,Timkin ;  Don't worry, I have a set of rules to go. Now I am thinking how to make my own path finding. Hope it can be done. This is my rules.1.1) Look at in front1.2) If find a siutable token, take it.1.3) If not find, scan the side of view cell. Sitution:-1.3.1) No space cell in the view1.3.1.1) (Sitution, there is a block in front)1.3.1.2) Scan for the cell beside robot1.3.1.3) If unknow cell is beside, turn to the side and jump to 1.11.3.1.4) If there is space beside, turn to the space and jump to 1.1(May modify, for choosing left turn or right turn)1.3.1.5) If wall is beside, turn back, jump to 1.11.3.2) Analysis there is a gate(May be scan in side the map too)1.3.2.1) Push the gate information into the gate list1.3.2.2) Skip this space scan, and continue next cell analysis at 1.3.31.3.3) There are unknown cell beside the view1.3.3.1) Hehe, move to the targer cell, jump to 1.1 1.3.4) There are space but no unknown cell beside the view1.3.4.1) Make a in front line check and then herical scan in each of line. Scan for unknown cell.1.3.4.2) If not found any unknown cell, scan left, and then right, and then behind.1.3.4.3) Make the target position, and move to it. (May modify to cancel targer if found important sitution)1.3.4.4) else, There is no more cell unexplore in this room, so pop gate information from list. Calculate the near gate. Move to the gate. Clear the gate(Exit the room)1.3.5) There is a dead end1.3.5.1) Don't enter it. Turn like analysis in  1.3.1.1**Target cancel sitution- Find a siutable sitution.**Choose to turn left or right-Still Don't know what to do.   However, to make it in to code need some time. So, hopefully it can be done.   [edited by - jeff_khor on February 19, 2004 12:01:45 AM]