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:
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.
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.
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!
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.
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!
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!
2 Comments On This Entry
Page 1 of 1

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.
Java chugs when it comes to game performance. Optimization should ways be high on your list.
Page 1 of 1
Tags
My Blog Links
Recent Entries
-
Android Game Programming: Calculating paths of enemy units in a TD game
on Aug 01 2012 02:34 PM
-
-
-
-
Recent Comments
-
-
anonymous26 on Feb 06 2013 10:00 PM
Android Game Programming: Calculating paths of enemy units in a TD game -
atraub on Aug 01 2012 07:51 PM
Android Game Programming: Calculating paths of enemy units in a TD game -
-
Search My Blog
4 user(s) viewing
4 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)
Categories
Android
Android related stuff!