My game lags on android!! (SOLVED)

Newbie & Debugging Questions
#1

Hello my game lags on android when about 3 zombies are on the map I know the problem however i have no idea how to fix it
The problem is the way i have done the path finding i am calculating it every frame i am not sure what to do i have tried using a delay but the zombie gitter up and down

here is the code the problem starts at “updateAndDebugPathFinding” // TODO FIX LAG!!!

package com.hawk.defend.entity;

import java.util.ArrayList;

import com.badlogic.gdx.graphics.Color;
import com.badlogic.gdx.graphics.glutils.ShapeRenderer.ShapeType;
import com.badlogic.gdx.maps.tiled.TiledMapTileLayer;
import com.badlogic.gdx.math.Vector2;
import com.badlogic.gdx.utils.IntArray;
import com.hawk.defend.coop.packets.PacketUpdateAi;
import com.hawk.defend.entity.bullet.Bullet;
import com.hawk.defend.entity.handler.Entity;
import com.hawk.defend.entity.handler.GameActor;
import com.hawk.defend.entity.path.Pathfinder;
import com.hawk.defend.game.CurrentMap;
import com.hawk.defend.game.MainGame;
import com.hawk.defend.utils.Delay;
import com.hawk.defend.window.GameWindow;

public class Enemie extends GameActor {

	public static final int ZOMBIE = 0;

	public static boolean DEBUG = false;
	private Pathfinder pathfinder;
	private Delay clientDelay;
	private int typeID;

	public Enemie(int entityID, float x, float y, float width, float height) {
		super(entityID, x, y, width, height);
		pathfinder = new Pathfinder((TiledMapTileLayer) MainGame.getMap().getMap().getLayers().get(CurrentMap.MAINLAYER), (TiledMapTileLayer) MainGame.getMap().getMap().getLayers().get(CurrentMap.OBJECTLAYER));

		setClientDelay(new Delay(0.02f) {

			@Override
			public void actionPerformed() {
				if (MainGame.client != null && MainGame.isHost()) {
					PacketUpdateAi update = new PacketUpdateAi();
					update.entityID = getEntityID();
					update.typeID = typeID;
					update.x = getX();
					update.y = getY();
					update.health = getHealth();
					MainGame.client.sendTCP(update);
				}

			}
		});
	}
	

	public Pathfinder getPathfinder() {
		return pathfinder;
	}

	public void setPathfinder(Pathfinder pathfinder) {
		this.pathfinder = pathfinder;
	}

	public int getTypeID() {
		return typeID;
	}

	public void setTypeID(int typeID) {
		this.typeID = typeID;
	}

	@Override
	public void render(float delta) {
		super.render(delta);
		if (MainGame.isHost()) {
			updateAndDebugPathFinding(delta); // TODO FIX LAG!!!!!!!
		}
	}

	@Override
	public void update(float delta) {
		super.update(delta);
		clientDelay.update(delta);
		updateBulletDamage(delta);
	}
	private void updateBulletDamage(float delta){
		for(int i = 0;i < MainGame.bullets.getBullets().size();i++){
			Bullet b = MainGame.bullets.getBullets().get(i);
			if(b.getBoundingRectangle().overlaps(getBoundingRectangle())){
				removeHealth(b.getDamage());
				MainGame.bullets.removeBullet(b);
				i--;
			}
		}
	}

	private void updateAndDebugPathFinding(float delta) {

		int mapWidth = pathfinder.getMap().getWidth();
		int mapHeight = pathfinder.getMap().getHeight();
		int cellWidth = (int) pathfinder.getMap().getTileWidth();
		int cellHeight = (int) pathfinder.getMap().getTileHeight();

		int startX = (int) ((getX() + (getWidth() / 2)) / cellWidth);
		int startY = (int) ((getY() + getHeight() / 2) / cellHeight);

		Vector2 pos = calculateClosesPlayer(getX(), getY());
		int targetX = (int) (pos.x + Entity.SIZE/2) / cellWidth;
		int targetY = (int) (pos.y + Entity.SIZE/2) / cellHeight;
		if (DEBUG) {
			GameWindow.cameraShape.begin(ShapeType.Filled);
			GameWindow.cameraShape.setColor(Color.GREEN);
			GameWindow.cameraShape.rect(startX * cellWidth, startY * cellHeight, cellWidth, cellHeight);
			GameWindow.cameraShape.setColor(Color.RED);
			GameWindow.cameraShape.rect(targetX * cellWidth, targetY * cellHeight, cellWidth, cellHeight);
		}

		if (startX >= 0 && startY >= 0 && startX < mapWidth && startY < mapHeight) {

			IntArray path = pathfinder.getAstar().getPath(startX, startY, targetX, targetY);

			if (path.size <= 0) {
				setVelocity(new Vector2());
			}

			for (int i = 0, n = path.size; i < n; i += 2) {
				followNodes(path.get(i), path.get(i + 1), cellWidth, cellHeight);
				int x = path.get(i);
				int y = path.get(i + 1);
				if (DEBUG) {
					GameWindow.cameraShape.setColor(Color.GREEN);
					GameWindow.cameraShape.circle(x * cellWidth + cellWidth / 2, y * cellHeight + cellHeight / 2, cellWidth / 4, 30);
				}
			}
		}

		GameWindow.cameraShape.end();
	}

	private Vector2 calculateClosesPlayer(float currentX, float currentY) {
		Vector2 posVector = new Vector2();
		ArrayList<Player> players = new ArrayList<Player>();

		// Gets all players
		for (int i = 0; i < MainGame.getPlayerHandler().getEntitys().size; i++) {
			Entity e = MainGame.getPlayerHandler().getEntitys().get(i);
			if (e instanceof Player) {
				Player p = (Player) e;
				players.add(p);
			}
		}
		if(players.size() <= 0) return new Vector2(currentX,currentY);

		if (players.size() <= 1) {
			Player p = players.get(0);
			return new Vector2(p.getX(), p.getY());
		}
		ArrayList<Float> posX = new ArrayList<Float>();
		ArrayList<Float> posY = new ArrayList<Float>();
		for (int i = 0; i < players.size(); i++) {
			Player p = players.get(i);
			posX.add(Math.abs(p.getX() - currentX));
			posY.add(Math.abs(p.getY() - currentY));
		}

		float smallestNumber = Float.MAX_VALUE;
		int index = 0;
		for (int i = 0; i < players.size(); i++) {
			if (smallestNumber > posX.get(i)) {
				smallestNumber = posX.get(i);
				index = i;
			}
		}
		Player returnPlayer = (players.get(index));
		posVector = new Vector2(returnPlayer.getX(), returnPlayer.getY());

		return posVector;
	}

	private void followNodes(float x, float y, int cellW, int cellH) {
		if ((getX() / cellW) < x && (getX() / cellW) < x + getWidth()) {
			getVelocity().x = 100;
		} else if ((getX() / cellW) > x && (getX() / cellW) > x - getWidth()) {
			getVelocity().x = -100;
		} else {
			getVelocity().x = 0;
		}
		if ((getY() / cellH) < y && (getY() / cellH) < y + getHeight()) {
			getVelocity().y = 100;
		} else if ((getY() / cellH) > y && (getY() / cellH) > y - getHeight()) {
			getVelocity().y = -100;
		} else {
			getVelocity().y = 0;
		}
	}

	public Delay getClientDelay() {
		return clientDelay;
	}

	public void setClientDelay(Delay clientDelay) {
		this.clientDelay = clientDelay;
	}

}
#2

My guess is the pathfinding code is the slow part, which you haven’t shown. (pathfinder.getAstar(), getPath())
Although most of this is pretty inefficient all over.

EDIT: also be aware of profilers: https://www.google.com/search?q=java+android+profiler

#3

Yeah thats the problem the path finding how would i sort this and am i meant to check every frame?

package com.hawk.defend.entity.path;

import com.badlogic.gdx.maps.tiled.TiledMapTileLayer;
import com.badlogic.gdx.utils.BinaryHeap;
import com.badlogic.gdx.utils.BinaryHeap.Node;
import com.badlogic.gdx.utils.IntArray;
import com.hawk.defend.game.CurrentMap;

public class Pathfinder {

	private TiledMapTileLayer map,objectLayer;
	private Astar astar;
	
	
	public Pathfinder(final TiledMapTileLayer map,final TiledMapTileLayer objectLayer) {
		
		this.setMap(map);
		this.setObjectLayer(objectLayer);
		setAstar(new Astar(map.getWidth(), map.getHeight()){
			protected boolean isValid(int x, int y) {
				return !map.getCell(x, y).getTile().getProperties().containsKey(CurrentMap.BLOCKED) && !objectLayer.getCell(x, y).getTile().getProperties().containsKey(CurrentMap.BLOCKED);
			}
		});

	}
	
	public Astar getAstar() {
		return astar;
	}

	public void setAstar(Astar astar) {
		this.astar = astar;
	}

	public TiledMapTileLayer getMap() {
		return map;
	}

	public void setMap(TiledMapTileLayer map) {
		this.map = map;
	}

	public TiledMapTileLayer getObjectLayer() {
		return objectLayer;
	}

	public void setObjectLayer(TiledMapTileLayer objectLayer) {
		this.objectLayer = objectLayer;
	}

	static public class Astar {
		private final int width, height;
		private final BinaryHeap<PathNode> open;
		private final PathNode[] nodes;
		int runID;
		private final IntArray path = new IntArray();
		private int targetX, targetY;
 
		public Astar (int width, int height) {
			this.width = width;
			this.height = height;
			open = new BinaryHeap<PathNode>(width * 4, false);
			nodes = new PathNode[width * height];
		}
 
		/** Returns x,y pairs that are the path from the target to the start. */
		public IntArray getPath (int startX, int startY, int targetX, int targetY) {
			this.targetX = targetX;
			this.targetY = targetY;
 
			path.clear();
			open.clear();
 
			runID++;
			if (runID < 0) runID = 1;
 
			int index = startY * width + startX;
			PathNode root = nodes[index];
			if (root == null) {
				root = new PathNode(0);
				root.x = startX;
				root.y = startY;
				nodes[index] = root;
			}
			root.parent = null;
			root.pathCost = 0;
			open.add(root, 0);
 
			int lastColumn = width - 1, lastRow = height - 1;
			while (open.size > 0) {
				PathNode node = open.pop();
				if (node.x == targetX && node.y == targetY) {
					while (node != root) {
						path.add(node.x);
						path.add(node.y);
						node = node.parent;
					}
					break;
				}
				node.closedID = runID;
				int x = node.x;
				int y = node.y;
				if (x < lastColumn) {
					addNode(node, x + 1, y, 10);
					if (y < lastRow) addNode(node, x + 1, y + 1, 14); // Diagonals cost more, roughly equivalent to sqrt(2).
					if (y > 0) addNode(node, x + 1, y - 1, 14);
				}
				if (x > 0) {
					addNode(node, x - 1, y, 10);
					if (y < lastRow) addNode(node, x - 1, y + 1, 14);
					if (y > 0) addNode(node, x - 1, y - 1, 14);
				}
				if (y < lastRow) addNode(node, x, y + 1, 10);
				if (y > 0) addNode(node, x, y - 1, 10);
			}
			return path;
		}
 
		private void addNode (PathNode parent, int x, int y, int cost) {
			if (!isValid(x, y)) return;
 
			int pathCost = parent.pathCost + cost;
			float score = pathCost + Math.abs(x - targetX) + Math.abs(y - targetY);
 
			int index = y * width + x;
			PathNode node = nodes[index];
			if (node != null && node.runID == runID) { // Node already encountered for this run.
				if (node.closedID != runID && pathCost < node.pathCost) { // Node isn't closed and new cost is lower.
					// Update the existing node.
					open.setValue(node, score);
					node.parent = parent;
					node.pathCost = pathCost;
				}
			} else {
				// Use node from the cache or create a new one.
				if (node == null) {
					node = new PathNode(0);
					node.x = x;
					node.y = y;
					nodes[index] = node;
				}
				open.add(node, score);
				node.runID = runID;
				node.parent = parent;
				node.pathCost = pathCost;
			}
		}
 
		protected boolean isValid (int x, int y) {
			return true;
		}
 
		public int getWidth () {
			return width;
		}
 
		public int getHeight () {
			return height;
		}
 
		static private class PathNode extends Node {
			int runID, closedID, x, y, pathCost;
			PathNode parent;
 
			public PathNode (float value) {
				super(value);
			}
		}
	}
}
#4

Can anyone help me? I have no idea why it is lagging???

#5

You don’t want to calculate your path every frame. Only calculate path for you entities when some sort of move command is issued to it.

That should get you started. If calculating path which is of length say 100 tiles / squares stutters your game (hogs your main thread), then you need to do some optimization for your path finding algorithm.

#6

I’m at work, so sadly don’t have the time to really dig into your code, but there are certainly ways to fix this problem. For starters: you could try storing the generated path in a list, and only have your entities recalculate their path every so often. Pop it into a sleepy thread or figure out some conditions for recalculation, such as the player entity moving such-and-such distance from their position when the original path was generated.

I’m far from an expert though, your mileage may vary!