Goal for today
Open up "ArenaManager.java" and let's go over that first. We will start with the constructor which will set us up for the logic of path finding later on.
public ArenaManager(Array<Tile> tiles, float midX, float midY) {
gridNumber = 12; //this holds the value of the number of columns
this.midX = midX; //these two hold the mid point of the screen (used for graphics so ignore)
this.midY = midY; //ignore
this.tiles = tiles; //tiles are what each "cell" is (block, open or blue path)
r = new Random(); //we will be using random floats between (0 and 1)
pause = false; //clicking the screen will cause it to pause. useful sometimes
movesMadeTemp = new Array<Integer>(); //this is where we will keep track of the current moves made
prevPos = 121; //we will be storing current and previous positions of the lead part -
setPartOfPath(121); //of the path. we start on tile 121
curPos = 121; //start on tile 121
currentState = GameState.RUNNING; //ignore this
totalMoves = 0; //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
won = false; //winning means it gets to a certain cell. we arbitrarily will pick one
tempMovesMade = 0; //unused?
totalMovesMade = 0; //unused?
//create maze by setting certain tiles to blocks.
setBlock(25);
setBlock(27);
setBlock(28);
setBlock(29);
setBlock(31);
setBlock(32);
setBlock(53);
setBlock(45);
setBlock(68);
setBlock(73);
setBlock(74);
setBlock(92);
setBlock(98);
setBlock(94);
setBlock(95);
setBlock(113);
setBlock(114);
setBlock(115);
setBlock(116);
setBlock(117);
}
Here is what you need to know about what is going on here. The method we will use to traverse the maze is this: first, generate a list of directions we can go at the current position we are at. For now, randomly pick one and go that direction. Check if we won. If we didn't, repeat the process again. If our path hits a dead end, or if we trap ourselves, start over. This isn't very smart but we will begin by doing that. Setting that up will be the focus of the rest of part 2.
I've commented the code above but the most important take aways are that we set our current position (curPos) and previous position (prevPos) to the tile 121. This is picken randomly but you'll notice if you run the program that this tile is in the bottom left. We will designate the tile 13 later on as the goal.
You might be wondering where the game loop is at. It is right below in the method update(delta). This gets called each cycle. The code for it is:
public void update(float delta)
{
if(pause)
return;
float e = r.nextFloat();
if(e > 0.04f)
{
move();
}
}
This is why this site is called filthy and sloppy. Of note here is that if pause is equal to true (clicking the screen toggles it), the program will pause. Otherwise it will generate a random number between 0 and 1 and if it is greater than 0.04, will call move(), which is the heart of the program. This dirty method of is used to control the speed of the path finding. If you flip the greater than sign to a less than sign, it will go slow, which is good for debugging.
This means that very quickly the method move will be called. move() will therefore be the main method we will look at. Right now all it does is generate a list of moves. As if that were nothing! Scroll down to move() and take a look at the code:
Array<Integer> listOfMoves = new Array<Integer>();
listOfMoves = generateMoves(); //find total moves that can be made
Only two lines! Filthy! This is why we need libgdx because we are using Array from it. What this code is doing is creating an array of integers and filling it with tile indexes. These are the possible moves it can make. generateMoves() is the method that will accomplish this. Let's take a look at the code for it:
private Array<Integer> generateMoves()
{
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);
//if(tiles.get(curPos - gridNumber).isBlock())
// tiles.get(curPos).setDirByIndex(0, -1);
if(!tiles.get(curPos- gridNumber).isBlock() && !tiles.get(curPos - gridNumber).isPartOfPath() && curPos > 0)
{
//if(chance <= 0.7895f)
//{
// if(up >= down && up >= left && up >= right)
// list.insert(0, curPos - gridNumber);
// else
// list.add(curPos - gridNumber);
// }else
// {
list.add(curPos - gridNumber);
// }
}
//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.7895f)
//{
// if(down >= up && down >= left && down >= right)
// list.insert(0, curPos + gridNumber);
// else
// list.add(curPos + gridNumber);
//}else
//{
list.add(curPos + gridNumber);
// }
}
//left
//if(tiles.get(curPos- 1).isBlock())
// tiles.get(curPos).setDirByIndex(2, -1);
if(!tiles.get(curPos- 1).isBlock() && !tiles.get(curPos - 1).isPartOfPath() && curPos > 0)
{
// if(chance <= 0.7895f)
// {
// if(left >= up && left >= down && left >= right)
// list.insert(0, curPos - 1);
// else
// list.add(curPos - 1);
// }else
// {
list.add(curPos - 1);
// }
}
//right
//if(tiles.get(curPos + 1).isBlock())
// tiles.get(curPos).setDirByIndex(3, -1);
if(!tiles.get(curPos + 1).isBlock() && !tiles.get(curPos + 1).isPartOfPath() && curPos > 0)
{
// if(chance <= 0.7895f)
// {
// if(right >= left && right >= up && right >= down)
// list.insert(0, curPos + 1);
// else
// list.add(curPos + 1);
// }else
// {
list.add(curPos + 1);
}
return list;
}
That'st a mouthful of sloppy code. Ignore everything commented out though and it is quite simple. Here is the code without the comments.
private Array<Integer> generateMoves()
{
Array<Integer> list = new Array<Integer>();
//up
if(!tiles.get(curPos- gridNumber).isBlock() && !tiles.get(curPos - gridNumber).isPartOfPath() && curPos > 0)
{
list.add(curPos - gridNumber);
}
//down
if(!tiles.get(curPos + gridNumber).isBlock() && !tiles.get(curPos + gridNumber).isPartOfPath() && curPos > 0)
{
list.add(curPos + gridNumber);
}
//left
if(!tiles.get(curPos- 1).isBlock() && !tiles.get(curPos - 1).isPartOfPath() && curPos > 0)
{
list.add(curPos - 1);
}
//right
if(!tiles.get(curPos + 1).isBlock() && !tiles.get(curPos + 1).isPartOfPath() && curPos > 0)
{
list.add(curPos + 1);
}
return list;
}
Not so bad now! All this method is doing is creating an array and adding directions if they aren't a block and aren't part of the path we've already made. It is the equivalent of standing on the tile and looking around. The entire point of this tutorial is to create a path finding algorithm that doesn't know what the maze is beforehand.
So the code is saying "if the tile up, down, left or right of me isn't a block and isn't part of the path I am making so far, add it to the list of possible moves." And remember we set which are blocks above in the constructor. (Note that the walls of the maze are also blocks. These were set beforehand and as an exercise to the reader, you can go track that code down if you want. Hint: it is in GameWorld.java)
Scroll back up to move() since we now have something to work with. Add the following code below and let's print out the possible moves for the curPos we are at (which is 121, that corner spot.)
public void move()
{
Array<Integer> listOfMoves = new Array<Integer>();
listOfMoves = generateMoves(); //find total moves that can be made
for(Integer i : listOfMoves)
{
System.out.println("Move: " + i); //this will print out available spots
}
}
Now run the program and in the console of Eclipse you will see the two open cells printed out. That means we have a list of moves, so let's get moving. Here is the code with an explanation. What it will do now is go on random paths. If it gets stuck, it will start over. If it gets in a corner of blocks, it will set the end part of it's path as a block (this is where it learns to not go down dead ends). The code will make it easier to understand:
public void move()
{
Array<Integer> listOfMoves = new Array<Integer>();
listOfMoves = generateMoves(); //find total moves that can be made
for(Integer i : listOfMoves)
{
System.out.println("Move: " + i);
}
if(listOfMoves.size == 0) //if there are no more moves left we need to reset
{
for(Integer i : movesMadeTemp) //cycle through all the moves made on this run
{
/here we check if the tile was surrounded by blocks
Array<Integer> movesMade = generateMovesByBlocks(i); //this returns list size of blocks
if(movesMade.size >= 3) // if there are 3 blocks around it, it is a dead end
tiles.get(i).setBlock(true); //so set it as a block
//block setting is done, now just reset tile as not part of the temp path
tiles.get(i).setPartOfPath(false);
}
// reset to the beginning like in the constructor
//save totalMoves (we will use that later)
curPos = 121;
prevPos = 121;
setPartOfPath(121);
if(tempMoves > totalMoves)
totalMoves = tempMoves;
tempMoves = 0;
movesMadeTemp.clear();
return;
}
//this part is what will move the path
int m = r.nextInt(listOfMoves.size); //pick a random open spot from listOfMoves
tiles.get(listOfMoves.get(m).intValue()).setPartOfPath(true); //set it as true (add it to path)
prevPos = curPos; //update the positions
curPos = listOfMoves.get(m);
movesMadeTemp.add(curPos); //add this new tile to movesMadeTemp since we moved
tempMoves++; //increase the counter for moves made
}
This sloppy code isn't that hard to understand. All it does is check if there are no moves left. If there aren't, it resets back the start. Otherwise, it picks a random available move and makes it. The Array<Integer> movesMade calls a method called generateMovesByBlocks(i). This returns a list of blocks surrounding the tile of index i. So it calls this method on every tile that was traveled to. If there was a dead end it went to (surrounded by 3 blocks), then it will set that tile as a block since it is a dead end. When running the program you can see when it goes down dead ends it fills them up.
We have a semi-smart path finder! We didn't tell it yet what the goal is (find tile 13) so it actually fills up tile 13. But in the next section we will make it a bit smarter. So run it a few times (perhaps change that greater than sign to a less than sign in update(delta) and watch it as it goes slowly. Once you are ready, head on over to part 3 where we will add in some smarts so that it converges to the optimal path.
Once again, click here to download the update source code.
No comments:
Post a Comment