     1 Votes

## Android Game Programming: Calculating paths of enemy units in a TD game 2 Comments
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);
}
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;

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;
}

```

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!

### 2 Comments On This Entry

Page 1 of 1 #### atraub

01 August 2012 - 07:51 PM
This is really cool! Thank you for sharing this.
0 #### anonymous26

06 February 2013 - 10:00 PM
Your nested loops are evil. Those need to optimized out, as well as your treatment of 2D arrays - they can always be treated as a 1D one.

Java chugs when it comes to game performance. Optimization should ways be high on your list.
0
Page 1 of 1

S M T W T F S
1
2345678
9 101112131415
16171819202122
23242526272829
3031

### Recent Entries

• • • • • • • • • • ### 1 user(s) viewing

1 Guests
0 member(s)
0 anonymous member(s)

### Categories

• Uncategorized (7)

### Android

Android related stuff!