001 /**
002 * Explores an unknown world Node by Node and returns a known world
003 */
004 public class Explore {
005 public static final int MAXIMUM_WORLD_SIZE = 100; //move specified time back
006
007 /**
008 * The main method.
009 * @return A NodeList with Nodes forming the path the explored world
010 */
011 public static NodeList run(){
012 NodeList nWorld = new NodeList();
013 NodeList nReturnToNodeList = new NodeList();
014 int iOrientation = 0;
015 int iUnknownBorders = 4;
016 Node nCurrent = new Node(0, 0);
017 nWorld.add(nCurrent);
018 Boolean bFinished;
019
020 while((iUnknownBorders > 0 ) && (nWorld.size() < MAXIMUM_WORLD_SIZE)){
021 System.out.println("\nUnknown: " + iUnknownBorders);
022 System.out.println("ReturnTo: " + nReturnToNodeList);
023 System.out.println("World: " + nWorld);
024 System.out.println("nCurrent: " + nCurrent);
025 for(int i = 0;i < 4; i++){
026 System.out.println("iOrientation: " + iOrientation);
027 if(nCurrent.borderValue(iOrientation) == -1){
028 if(NodeToHemisson.moveHemisson(NodeToHemisson.MOVE_FORWARD)){
029 NodeToHemisson.moveHemisson(NodeToHemisson.MOVE_HALF_BACKWARD);
030 NodeToHemisson.moveHemisson(NodeToHemisson.MOVE_HALF_BACKWARD_OFFSET);
031 NodeToHemisson.moveHemisson(NodeToHemisson.RESET);
032 nCurrent.setBorder(iOrientation, 1);
033 } else {
034 NodeToHemisson.moveHemisson(NodeToHemisson.MOVE_BACKWARD);
035 nCurrent.setBorder(iOrientation, 0);
036 }
037 iUnknownBorders--;
038 }
039 if(i != 3){
040 NodeToHemisson.moveHemisson(NodeToHemisson.TURN_RIGHT);
041 iOrientation = (iOrientation + 1) % 4;
042 }
043 }
044
045 if(nCurrent.bordersFalseCount() >= 2){
046 if(nReturnToNodeList.nodeExist(nCurrent.getX(), nCurrent.getY()) != -1){
047 nReturnToNodeList.add(nCurrent);
048 }
049 }
050
051 NodeList nWorldMutated = new NodeList();
052 Node[] anNBs = new Node[4];
053
054 // generate NB's
055 anNBs[0] = new Node(nCurrent.getX(),nCurrent.getY()+1);
056 anNBs[1] = new Node(nCurrent.getX()+1,nCurrent.getY());
057 anNBs[2] = new Node(nCurrent.getX(),nCurrent.getY()-1);
058 anNBs[3] = new Node(nCurrent.getX()-1,nCurrent.getY());
059
060 int iIndexNB;
061 // loop through NB's
062 for(int i = 0;i < 4; i++){
063
064 // is NB reachable ?
065 if(nCurrent.borderValue(i) == 0){
066 // does NB exists in world ?
067 int iIndex = nWorld.nodeExist(anNBs[i].getX(), anNBs[i].getY());
068 if(iIndex == -1){
069 anNBs[i].setBorder((i + 2) % 4, 0);
070
071 if( (iIndexNB=nWorld.nodeExist( anNBs[i].getX(),anNBs[i].getY()+1 )) != -1) {
072 anNBs[i].setTop( nWorld.get(iIndexNB).getBottom() );
073 }
074 if( (iIndexNB=nWorld.nodeExist( anNBs[i].getX()+1,anNBs[i].getY() )) != -1) {
075 anNBs[i].setRight( nWorld.get(iIndexNB).getLeft() );
076 }
077 if( (iIndexNB=nWorld.nodeExist( anNBs[i].getX(),anNBs[i].getY()-1 )) != -1) {
078 anNBs[i].setBottom( nWorld.get(iIndexNB).getTop() );
079 }
080 if( (iIndexNB=nWorld.nodeExist( anNBs[i].getX()-1,anNBs[i].getY() )) != -1) {
081 anNBs[i].setLeft( nWorld.get(iIndexNB).getRight() );
082 }
083
084
085 nWorld.add(anNBs[i]);
086 iUnknownBorders += anNBs[i].bordersUnknownCount();
087 } else {
088 nWorld.get(iIndex).setBorder((i + 2) % 4, 0);
089 }
090
091 if(anNBs[i].bordersFalseCount() >= 2) {
092 nReturnToNodeList.add(anNBs[i]);
093 }
094 }
095 }
096
097 Node nNextNB = getNext(nCurrent, nWorld);
098 if(nNextNB.allBordersKnown() ) {
099 if(nReturnToNodeList.isNotEmpty()){
100 Node nOpen = nReturnToNodeList.lastElement();
101 if(nOpen.bordersFalseCount() < 2){
102 nReturnToNodeList.remove(nOpen);
103 }
104
105 NodeList path = AStar.run(nWorld, nCurrent, nOpen);
106
107 for(int i = 0; i < path.size() -1; i++){
108 iOrientation = NodeToHemisson.run(path.get(i), path.get(i+1), iOrientation);
109 }
110 nCurrent = nOpen;
111 }
112 } else {
113 NodeToHemisson.run(nCurrent, nNextNB, iOrientation);
114 nCurrent = nNextNB;
115 }
116
117 }
118 nWorld.setCurrentNodeAndOrientation(nCurrent, iOrientation);
119 return nWorld;
120 }
121 /**
122 * Returns the Next node, based on the current and the world
123 */
124 public static Node getNext(Node nPrevious, NodeList nWorld){
125 int bordercount = 0;
126 int max = 0;
127 int indexTemp = 0;
128 int index = 0;
129 Node temp = new Node();
130 for(int i = 0; i < nWorld.size(); i++){
131 bordercount = 0;
132 temp = (Node)nWorld.get(i);
133 if( (temp.getX() == nPrevious.getX() && temp.getY() == nPrevious.getY()+1) ||
134 (temp.getX() == nPrevious.getX()+1 && temp.getY() == nPrevious.getY()) ||
135 (temp.getX() == nPrevious.getX() && temp.getY() == nPrevious.getY()-1) ||
136 (temp.getX() == nPrevious.getX()-1 && temp.getY() == nPrevious.getY()) ){
137 indexTemp = i;
138 for(int j = 0; j < 4; j++){
139 if(temp.borderValue(j) == -1){
140 bordercount++;
141 }
142 }
143 if(bordercount >= max){
144 max = bordercount;
145 index = indexTemp;
146 }
147 }
148 }
149 return (Node)nWorld.get(index);
150 }
151 }