Finished program - converges to optimal path
Welcome to the final part of the path finding tutorial. The above image shows the final product. Click above to download the current updated source. What we want to implement here is smart path finding. We will still use random moves to begin with. Then, after we have "won" (we have reached tile 13), we will assign weights to each of the tiles that lead us to the winning tile. We will then pick these tiles the majority of the time, but allow for random moves to account for a better path (shorter path). We will keep track of how many moves it took to get to the goal tile and restart if we exceed that number (if we got a win in 19 moves, then on the 20th move we should restart because we know the best move is at minimum 19 moves). Note that in our set up there will be multiple paths that are the fastest. Our program should find them all.I've edited the code so that the optimal path is shown in yellow/orange color when it is found. So open up the code from part 2 and let's get started.
If you notice in the gif above, there are two numbers being displayed on the top left. These are our tempMoves and totalMoves variables. I've edited it so that they are visible just for informational purposes. But these have to be changed (they are set in the constructor for ArenaManager.java), so open up ArenaManager.java and go to the constructor. Set them each as follows:
totalMoves = Integer.MAX_VALUE; //we will be storing total moves made (explained later on)
tempMoves = 0; //this is where we will store the amount of moves made for each search
Later in the code, we will check if tempMoves < totalMoves. If it is, we will update totalMoves to equal tempMoves and set tempMoves = 0. We will do this when we have "won." We will also reset to the start if tempMoves > totalMoves for the reason explained above.
The majority of the edits take place in the method move(), but first let's edit generateMoves(). Here we will look at one case, the case when the move down is open. The same logic follows for if up, left, right or left are open. He is the
Array<Integer> list = new Array<Integer>();
float chance = r.nextFloat();
int up = tiles.get(curPos).getDirByIndex(0);
int down = tiles.get(curPos).getDirByIndex(1);
int left = tiles.get(curPos).getDirByIndex(2);
int right = tiles.get(curPos).getDirByIndex(3);
//down
if(tiles.get(curPos + gridNumber).isBlock())
tiles.get(curPos).setDirByIndex(1, -1);
if(!tiles.get(curPos + gridNumber).isBlock() && !tiles.get(curPos + gridNumber).isPartOfPath() && curPos > 0)
{
if(chance <= 0.895f)
{
if(down >= up && down >= left && down >= right)
list.insert(0, curPos + gridNumber);
else
list.add(curPos + gridNumber);
}else
{
list.add(curPos + gridNumber);
}
}
First we declare a variable called chance. We want to go the direction that leads to a win the majority of the time. If chance is less than 0.895 (89.5% chance), we will insert this direction into the list of moves at position 0. In move(), we will pick the direction in index 0 of our generated move lists 89.5% of the time as well. Otherwise, we will just add it to the end of the list.
The variables up, down, left and right are weights. We increase them later on if we win. The first two lines after //down are checking if a block is below our curPos. If it is, we set the weight for down one lower than it is. The function setDirByIndex sets the weights (0=up, 1=down, 2=left, 3=right).
The same code is used for the other directions. We put the code for up last so that we favor going up if multiple directions can be made (this is because we know ahead of time that the goal tile is above us. This would need to be changed if it were below our starting position or else the search time would be longer and we would likely need to add penalization.)
So the list will now be returned with the best weighted move in the first slot of the array. Now we will move on to edit move()
The first thing we have to do is add a condition that if there is a win (if curPos == 13 in this case). Here is the code for that:
if(curPos == 13) //if we get to the "winning" tile
{
for(Integer i : movesMadeTemp) //go through moves we made to get there
{
//tiles.get(i).setWinable(true); //not used
tiles.get(i).setPartOfPath(false); //take the tile out of the path
if(tiles.get(i).isMovedUp()) //did that tile move up?
{
tiles.get(i).setDirByIndex(0, 1); //increase the weight for going up at that cell by 1
}
if(tiles.get(i).isMovedDown()) //did that tile move down?
{
tiles.get(i).setDirByIndex(1,1); //increase down weight by 1
}
if(tiles.get(i).isMovedLeft()) //same logice
{
tiles.get(i).setDirByIndex(2, 1);
}
if(tiles.get(i).isMovedRight()) //same logic
{
tiles.get(i).setDirByIndex(3, 1);
}
// tiles.get(i).setPartOfPath(false); //oops, redundant. comment out
tiles.get(i).setMovedUp(false); //set that this tile didn't move up, down, left or right
tiles.get(i).setMovedDown(false);
tiles.get(i).setMovedLeft(false);
tiles.get(i).setMovedRight(false);
}
// our starting cell is technically not in our array of movesMadeTemp
// so we will have to update the weights for it individually
if(tiles.get(121).isMovedUp())
{
tiles.get(121).setDirByIndex(0, 1);
}
if(tiles.get(121).isMovedDown())
{
tiles.get(121).setDirByIndex(1,1);
}
if(tiles.get(121).isMovedLeft())
{
tiles.get(121).setDirByIndex(2, 1);
}
if(tiles.get(121).isMovedRight())
{
tiles.get(121).setDirByIndex(3, 1);
}
won = true; //set that won = true because we won (usefulness not used)
curPos = 121; //reset the game
prevPos = 121;
if(tempMoves < totalMoves) //change totalMoves if we got to win faster
totalMoves = tempMoves;
tempMoves = 0;
setPartOfPath(121);
movesMadeTemp.clear();
//pause = true;
return;
}
In plain English, the code above checks if we are at a winning tile. Tile 13 is chosen as that tile, but feel free to make it another open tile. If a win occurs, we loop through all of the moves made and increase their "fitness" by one. This makes them more likely to be the moves made in the future.
Finally, we reset the game just as if we had lost. Also, we update totalMoves if it is lower than tempMoves. In the next part, we will reset if tempMoves > totalMoves as explained above. We will look at that code now:
if(listOfMoves.size == 0 || tempMoves > totalMoves) //if no more moves or too many moves
{
for(Integer i : movesMadeTemp) //loop through moves made
{
Array<Integer> movesMade = generateMovesByBlocks(i); //this is code for
if(movesMade.size >= 3) //finding dead ends
tiles.get(i).setBlock(true);
tiles.get(i).setPartOfPath(false);
//new-
tiles.get(i).setMovedUp(false); //set that the tile didn't move up, down, left or right
tiles.get(i).setMovedDown(false);
tiles.get(i).setMovedLeft(false);
tiles.get(i).setMovedRight(false);
}
//set our starting tile manually the same as the tiles above
tiles.get(121).setPartOfPath(false);
tiles.get(121).setMovedUp(false);
tiles.get(121).setMovedDown(false);
tiles.get(121).setMovedLeft(false);
tiles.get(121).setMovedRight(false);
//reset the program
curPos = 121;
prevPos = 121;
setPartOfPath(121);
//if(tempMoves > totalMoves)
// totalMoves = tempMoves;
tempMoves = 0;
movesMadeTemp.clear();
return;
}
Here we check if there are no more moves and also if we are making more moves than a known winning route. If either case is true, we check for dead ends and fill them. Then we reset the program to the start. Note that in these conditional statements, we are returning out. Now the above two if-statements will return but if those conditions aren't met, we reach the code where we actually move through the maze. Let's look at that code:
int m = r.nextInt(listOfMoves.size); /pick a random move
if(r.nextFloat() < 0.895f) //89.5% of the time, actually pick the first slot move
m = 0; //set index to 0 for first slot
tiles.get(listOfMoves.get(m).intValue()).setPartOfPath(true);
//below we will determine if the tile moves up, down, left or right
//we will set that it moved that direction
//it will only ever move one direction, obviously
if(listOfMoves.get(m).intValue() == curPos - gridNumber)
{
tiles.get(curPos).setMovedUp(true);
}
if(listOfMoves.get(m).intValue() == curPos + gridNumber)
{
tiles.get(curPos).setMovedDown(true);
}
if(listOfMoves.get(m).intValue() == curPos - 1)
{
tiles.get(curPos).setMovedLeft(true);
}
if(listOfMoves.get(m).intValue() == curPos + 1)
{
tiles.get(curPos).setMovedRight(true);
}
prevPos = curPos;
curPos = listOfMoves.get(m);
movesMadeTemp.add(curPos);
tempMoves++;
In plain English: this code is reached when we are moving. First we pick a random move from our list of possible moves. Then, 89.5% (which is randomly chosen as a threshold), we pick the move in index 0 of our list. This is because slot 0 will have a good move in it 89.5% of the time, as we set it to do in generateMoves(). Then we just check the new move against our curPos to see if we moved up, down, left or right. Whichever way we went, we set that as true.
And that's it! Running it now, the path should converge to the optimal path. I've set it in another class so that the optimal path will be in yellow when it eventually finds it (or them, as there are multiple paths that are equal distance in our case.)
Try changing around the winning and start positions. Note that by editing the grid size, the time it takes to converge to the optimal path increases. This is because it relies on some randomness before it starts to learn the best path. Also, we do not have penalization in place so it may get stuck on a sub-optimal path.
No comments:
Post a Comment