Hey guys so I have decided to start blog series where I will be talking about my experiences in Android! Today I will talking about how I calculated the path of enemy units in the game that I am creating. I would like to note that any code that post in this blog entry is still a work in progress and not all the logic bugs have been worked out but its a great base for anyone trying to figure out how to calculate units paths!

So when I started out thinking about how I was going to figure out the paths of the enemy units I looked at my game map a 2D gird with each cell being 16x16 pixels big. I chose 16x16 because my path sprites are that size and the map will evenly divide by 16. Once I had that figured out I made my towers be 32x32 because it too would evenly fit into the grid.

Now to make all the calculations easy and everything organized I created a class just for handling the everything that has to do with unit paths!
This is what I started off with:

public class PathManager {
	private int startX;
	private int startY;
	private int endX;
	private int endY;
	private ITextureRegion path_sprite_texture;
	private int [][]grid;
	private int w;
	private int h;
	private List<Sprite>path_sprites;
	
	public PathManager(int startX, int startY, int endX, int endY,
			ITextureRegion path_sprite_texture) {
		this.startX = startX/16;
		this.startY = startY/16;
		this.endX = endX/16;
		this.endY = endY/16;
		this.path_sprite_texture = path_sprite_texture;
		path_sprites=new ArrayList<Sprite>();
	}
}

The startX and startY in my code is the "spawn" point of the enemy units and the end vars is the place the units are tying to reach. I also pass the texture I will be using to show the current calculated path to the player. As you may of noticed I divide the starting and ending points by 16. I did this because my cell size is 16x16 so i need to find the x and y in terms of the grid!
The next thing I had to do was to initialize the grid and place the spawn point in the grid.

public void initGrid(int width,int height)
	{
		w = width/16;
		h = height/16;
		grid = new int[h][w];
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
				grid[i][j]=-1;
		}
		grid[startY][startX]=0;
	}

In this part of the code we can see that I initialized the entire grid to -1. I'm using -1 to define all the movable spots on the map! I also set the spawn point to 0. I did this because in my algorithm 0 is the starting point.
The next thing I added was the method for finding the path and showing in the scene.

public void solveAndShow(Scene s,VertexBufferObjectManager vbo)
	{
		solve();
		show(s,vbo);
		revert();
	}
private void solve()
	{
		while(grid[endY][endX]==-1)
		{
			for (int i = 1; i < h-1; i++) {
	            for (int j = 1; j < w-1 ; j++) {
	                if (grid[i][j] == -1) {
	                    sum(i, j);
	                }
	            }
	        }
		}
		int i=endY;
		int j=endX;
		while (grid[startY][startX] != -8) {
			int k = grid[i][j] - 1;
			// cout<<k<<endl;
			if (grid[i + 1][j] == k) {
				grid[i][j] = -8;
				i = i + 1;
				j = j;
				continue;
			}
			if (grid[i - 1][j] == k) {
				grid[i][j] = -8;
				i = i - 1;
				j = j;
				continue;
			}
			if (grid[i][j + 1] == k) {
				grid[i][j] = -8;
				i = i;
				j = j + 1;
				continue;
			}
			if (grid[i][j - 1] == k) {
				grid[i][j] = -8;
				i = i;
				j = j - 1;
				continue;
			}

		}
	}
// this is part of my algorithm. I use a flood type method to find the correct path
	private void sum(int i,int j)
	{
		if ((i-1)!=-1&&grid[i - 1][j] > -1) {
	        grid[i][j] = 1 + grid[i - 1][j];
	    }
	    if ((i+1)<h&&grid[i + 1][j] > -1) {
	        grid[i][j] = 1 + grid[i + 1][j];
	    }
	    if ((j-1)!=-1&&grid[i][j - 1] > -1) {
	        grid[i][j] = 1 + grid[i][j - 1];
	    }
	    if ((j+1)<w&&grid[i][j + 1] > -1) {
	        grid[i][j] = 1 + grid[i][j + 1];
	    }
	}
private void show(Scene s,VertexBufferObjectManager vbo)
	{
		removeSprites(s);
		int num=0;
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
			{
				if(grid[i][j]==-8)// if its -8 then that cell is part of the solved path
				{
					s.attachChild(getSprite(i,j,vbo,num));
					num++;
				}
			}
		}
	}
// this method reverts the grid to the pre-solved state
private void revert()
	{
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
			{
				if(grid[i][j]==-8)// -8 is the solved path
					grid[i][j]=-1;
				else if(grid[i][j]>=0)
					grid[i][j]=-1;
			}
		}
		grid[startY][startX]=0;
	}
// this method is for removing all the path sprites from the scene
	private void removeSprites(Scene sc)
	{
		for(Sprite s:path_sprites)
			sc.detachChild(s);
	}
// this method is for getting the sprites to draw. I have the sprites pooled so we dont waste them!
	private Sprite getSprite(int i,int j,VertexBufferObjectManager vbo,int num)
	{
		Sprite s = null;
		if(num==path_sprites.size())
		{
			s = new Sprite(j*16,i*16,16,16,path_sprite_texture.deepCopy(),vbo);
			path_sprites.add(s);
		}
		else
		{
			s = path_sprites.get(num);
			s.setPosition(j*16,i*16);
		}
		
		return s;
	}

With all that code in place I was ready to finally test! This was the result:


This was good and all but I need to calculate a new path every time I added a new tower!

public void addObject(int x,int y, int w,int h)
	{
		for(int i=y/16;i<(y/16)+(h/16);i++)
		{
			for(int j=x/16;j<(x/16)+(w/16);j++)
			{
				grid[i][j]=-2;
			}
		}
	}
	public void removeObject(int x,int y, int w,int h)
	{
		for(int i=y/16;i<(y/16)+(h/16);i++)
		{
			for(int j=x/16;j<(x/16)+(w/16);j++)
			{
				grid[i][j]=-1;
			}
		}
	}

This code allows me to fill the cells where I have towers placed! This was the result when I ran it and added some towers:

Now this was great but there is one more thing that I need to do and that is to check where or not the new tower that I'm placing will block the path of the enemy units.

private int newNums()
	{
		int num = 0;
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
			{
				if(grid[i][j]>=0)
				{
					num++;
				}
			}
		}
		return num;
	}
	public boolean isBlocking(int x,int y, int w,int h)
	{
		boolean blocked = false;
		int max=-1, cmax = 0;
		
		this.addObject(x, y, w, h);
		while(grid[endY][endX]==-1&&!blocked)
		{
			for (int i = 0; i < this.h ; i++) {
	            for (int j = 0; j < this.w; j++) {
	                if (grid[i][j] == -1) {
	                    sum(i, j);
	                }
	            }
	        }
			cmax = newNums();
			if(cmax==max)
				blocked=true;
			else 
				max=cmax;
		}
		if(grid[endY][endX]==-1&&blocked)
		{
			revert();
			this.removeObject(x, y, w, h);
			return true;
		}
		revert();
		this.removeObject(x, y, w, h);
		return false;
	}

Well thats all I have so far on this subject! If you have any questions or comments please leave a reply!

Also on a very similar note I am looking for people who may be interested in working with me to create this game! I need people to make sprites for towers and enemy units. I also need someone to create sound effects and original music for this game! If you are interested please PM me or email me!