# Random movement avoiding walls

I have a top-down game you can scroll through placeable tiles I have some NPCs that do nothing at the moment I want them to freely move around without going through wall tiles etc.

For the freely moving I have code and it works fine but they walk through walls:

if(new Random().nextInt(4) == 0){
x+=1;
}
if(new Random().nextInt(4) == 1){
x-=1;
}
if(new Random().nextInt(4) == 2){
y+=1;
}
if(new Random().nextInt(4) == 3){
y-=1;
}


How can I make it so they don't walk through walls?

All the solid tiles are stored in an arraylist

public static ArrayList<block> s = new ArrayList<block>();


and then have the for loops for them and each block has its own rectangle around it.

• Are none of the answers below suitable for you? You should provide feedback if they're not or accept the answer most useful to you. Mar 7, 2014 at 20:15

You don't check if the NPCs are colliding with a block, there are two things you could do:

1. Check if the tile the NPC want to move on is solid.
2. Move the NPC, then check if they are standing on a solid block, if yes then move back.

I would suggest method one, so you could do something like that:

int r = random.nextInt(4);
if(r == 0 && validMove(x+1,y)){
x += 1;
}
if(r == 1 && validMove(x-1,y)){
x -= 1;
}
if(r == 2 && validMove(x,y+1)){
y += 1;
}
if(r == 3 && validMove(x,y-1)){
y -= 1;
}


So they will only move if they will be on a valid position.
validMove(x,y) could look like the following code:

If your ArrayList is sorted you could try this:

boolean validMove(int x, int y) {
Block b = s.get((x-1) + (y-1)*mapWidth);
if(b.getX() == x && b.getY() == y) {
return false;
} else {
return true;
}
}


How does that work? Let's do a simple example, imagine you have an ArrayList with following coordinates:

{(1,1);(2,1);(3,1);(4,1);
(1,2);(2,2);(3,2);(4,2);
(1,3);(2,3);(3,3);(4,3)}


We have mapWidth = 4 and mapHeight = 3.
So now you have x = 2 and y = 3, you should get (2,3) which is at Index 9.
The calculation is i = (2-1) + (3-1) * 4 = 1 + 2 * 4 = 1 + 8 = 9.

Else you can do it like this (almost similar to Byte56 answer), but there you wouldn't have fast access if the map is big.

boolean validMove(int x, int y) {
for(Block b : s) {
if(b.getX() == x && b.getY() == y) {
return false;
}
}
return true;
}


For method 2 you could use intersection checks.

You need to create some kind of isSolid(x,y) function. Unfortunately you're storing all your blocks in an array list, so it's going to be difficult to do this in a fast way, but that's up to you to figure out.

Once you have your isSolid(x,y) function, you can modify your code like:

if(!isSolid(x+1, y) && new Random().nextInt(4) == 0){
x+=1;
}
//etc.


A naive approach to your isSolid function can be:

boolean isSolid(int x, int y) {
for(Block b : s) {
if(b.x == x && b.y == y)
return true;
}
return false;
}


However, I'd suggest you place your blocks into a 2D array (or a 1D array with the index specified by the x,y). If you have your blocks in a 2D array you can easily check blocks[x][y].solid or something similar, instead of looping through all your blocks.

Alternatively you can use the rectangles in your scene for collision detection, where your isSolid(x,y) function would do a collision check at that position.