How do you use pathfinding?

[tommohawkaction]

Okay may sound like a dumb question to ask, however I am not completely sure how i would make an entity follow the path and make this optimized without having to calculate everything frame

This is what i currently have

	private int currentPath = 0;

	@Override
	public void update(float delta) {
		super.update(delta);

		if (path == null) {
				currentPath = 0;
				recalculatePath();
		}
		if(path.size > 0 && currentPath+1 < path.size){
				int pathX = path.get(currentPath);
				int pathY = path.get(currentPath+1);

				if (currentTileX < pathX) {
					getVelocity().x = movementSpeed;

				} else if (currentTileX > pathX) {
					getVelocity().x = -movementSpeed;

				} else {
					getVelocity().x = 0;
				}
				if (currentTileY < pathY) {
					getVelocity().y = movementSpeed;
				} else if (currentTileY > pathY) {
					getVelocity().y = -movementSpeed;

				} else {
					getVelocity().y = 0;
				}
				if(currentTileX == pathX && currentTileY == pathY){
					System.out.println(11);
					currentPath+=2;
				}

				translate(delta * getVelocity().x, delta * getVelocity().y);

		}else{
			currentPath = 0;
			recalculatePath();
		}

	}

	private void recalculatePath() {
		IntArray calculatedPath = pathFinder.getAstar().getPath(currentTileX, currentTileY, target.getCurrentTileX(), target.getCurrentTileY());
		if(path == null){
		path = new IntArray();
		}else{
			path.clear();
		}
		while(calculatedPath.size > 0){
			int y = calculatedPath.pop();
			int x = calculatedPath.pop();
			path.add(x);
			path.add(y);
		}
	
	}

	@Override
	public void render(SpriteBatch worldBatch) {
		super.render(worldBatch);
		// IntArray path = pathFinder.getAstar().getPath(getCurrentTileX(), getCurrentTileY(), target.getCurrentTileX(), target.getCurrentTileY());
		//
		 for (int i = 0, n = path.size; i < n; i += 2) {
		
		 int pathX = path.get(i);
		 int pathY = path.get(i+1);
		 worldBatch.draw(getTexture(), pathX*MasterTile.TILE_WIDTH, pathY * MasterTile.TILE_HEIGHT
		 , getWidth() / 2, getHeight() / 2, getWidth(), getHeight(), 1f, 1f, getRotation());
		
		
		 }
	}
		}

The problem with this though is that the entity seems to be going through walls and when i enable collision it gets stuck??

Collision code

package com.hawk.linear.engine.collisioin;

import com.badlogic.gdx.math.Vector2;
import com.hawk.linear.engine.entity.Entity;
import com.hawk.linear.engine.map.TileMap;
import com.hawk.linear.engine.renderer.TileRenderer;
import com.hawk.linear.engine.tile.MasterTile;
import com.hawk.linear.engine.tile.Tile;
import com.hawk.linear.engine.tile.tiles.AirTile;
import com.hawk.linear.engine.tile.tiles.BlockType;

public class CollisionTileEngine {

	/**
	 * This is the collision engine for tiles the EXCEPTION_LIST is a list of tile ids on which ones don't use collision
	 */
	private static int[] EXCEPTION_LIST = { BlockType.BFLOWER, BlockType.RFLOWER, BlockType.PIFLOWER, BlockType.PUFLOWER, BlockType.TORCH };

	/**
	 * An entity will use this to have collision on the world (TileRenderer)
	 * 
	 * @param e
	 *            is the entity which you are checking the collision for
	 * @param oldX
	 *            is the old position x (before the translate has happened)
	 * @param oldY
	 *            is the old position y (before the translate has happened)
	 */
	public static void applyCollision(Entity e, float oldX, float oldY) {
		// It works by getting the entitys position and then changing that to the tile position
		// for example an entity which has a position of x = 250 y = 500 now each tile has a size of 50 so we divide
		// x/tileSizeX and y/tieSizeY
		// then cast it into a integer because [][] (multidimensional arrays) can only take a integer
		// we then get the top,bottom,left,right tile using the TileMap data which
		// is a multidimensional array and work how if the entity is colliding with it
		// that is the simple version
		boolean collisionX = false;
		boolean collisionY = false;
		TileMap map = TileRenderer.map;

		Vector2 velocity = e.getVelocity();
		float x = e.getX();
		float y = e.getY();
		float w = e.getWidth();
		float h = e.getHeight();

		float offsetX = 15;
		float offsetY = 0;
		float offsetXW = 15;
		float offsetYH = 20;

		if (x / MasterTile.TILE_WIDTH >= 0 && x / MasterTile.TILE_WIDTH <= map.getWidth() - 1 && y / MasterTile.TILE_HEIGHT >= 0 && y / MasterTile.TILE_HEIGHT <= map.getHeight() - 1) {

			if (velocity.x < 0) {
				// Bottom left
				collisionX = checkCollisionTile(e.getX() + offsetX, e.getY() + offsetY, map);
				// Middle left
				collisionX |= checkCollisionTile(e.getX() + offsetX, (e.getY() + offsetY) + ((h - (offsetYH * 2)) / 2), map);
				// Top left
				collisionX |= checkCollisionTile(e.getX() + offsetX, (e.getY() + offsetY) + (h - (offsetYH * 2)), map);
			} else if (velocity.x > 0) {
				// Bottom right
				collisionX = checkCollisionTile((e.getX() + offsetX) + (w - (offsetXW * 2)), e.getY() + offsetY, map);
				// Middle right
				collisionX |= checkCollisionTile(e.getX() + offsetX + (w - (offsetXW * 2)), (e.getY() + offsetY) + ((h - (offsetYH * 2)) / 2), map);
				// Top right
				collisionX |= checkCollisionTile(e.getX() + offsetX + (w - (offsetXW * 2)), (e.getY() + offsetY) + (h - (offsetYH * 2)), map);
			}
			if (collisionX) {
				e.setX(oldX);
			}

			if (velocity.y < 0) {
				// Bottom left
				collisionY = checkCollisionTile(e.getX() + offsetX, e.getY() + offsetY, map);
				// Bottom middle
				collisionY |= checkCollisionTile(e.getX() + offsetX + ((w - (offsetXW * 2)) / 2), e.getY() + offsetY, map);
				// Bottom right
				collisionY |= checkCollisionTile(e.getX() + offsetX + (w - (offsetXW * 2)), e.getY() + offsetY, map);
			} else if (velocity.y > 0) {
				// Top left
				collisionY = checkCollisionTile(e.getX() + offsetX, (e.getY() + offsetY) + (h - (offsetYH * 2)), map);
				// Top middle
				collisionY |= checkCollisionTile(e.getX() + offsetX + ((w - (offsetXW * 2)) / 2), (e.getY() + offsetY) + (h - (offsetYH * 2)), map);
				// Top right
				collisionY |= checkCollisionTile(e.getX() + offsetX + (w - (offsetXW * 2)), (e.getY() + offsetY) + (h - (offsetYH * 2)), map);

			}
			if (collisionY) {
				e.setY(oldY);
			}

			if (collisionX) {
				e.getVelocity().x = 0;
			}
			if (collisionY) {
				e.getVelocity().y = 0;
			}

		}

	}

	/**
	 * This method checks each individual tile for collision on (TOP layer) by checking it using the EXCEPTION_LIST
	 * 
	 * @param x
	 * @param y
	 * @param tileMap
	 * @return
	 */
	public static boolean checkCollisionTile(float x, float y, TileMap tileMap) {
		int currentX = (int) (x / MasterTile.TILE_WIDTH);
		int currentY = (int) (y / MasterTile.TILE_HEIGHT);
		return CollisionTileEngine.checkCollisionTile(currentX, currentY, tileMap);

	}
	public static boolean checkCollisionTile(int x, int y, TileMap tileMap) {
		int currentX = x;
		int currentY = y;
		if (currentX < 0 || currentX > tileMap.getWidth() - 1 || currentY < 0 || currentY > tileMap.getHeight() - 1) {
			return true;
		}
		Tile topTile = tileMap.getMapData()[currentX][currentY].getTopTile();
		if (topTile != null) {
			if (topTile instanceof AirTile == false) {
				for (int i = 0; i < EXCEPTION_LIST.length; i++) {
					int id = EXCEPTION_LIST[i];
					if (topTile.getID() == id)
						return false;
				}
				return true;
			}

		}

		return false;
	}
}

[tommohawkaction]

I have fixed the collision problem however the entity is still stuck… am i doing the following code wrong?

		if (target != null) {
			int currentX = currentTileX;
			int currentY = currentTileY;

			int targetX = target.getCurrentTileX();
			int targetY = target.getCurrentTileY();

			calculatePath(currentX, currentY, targetX, targetY);

			if (path.size > 1) {
				int goX = path.get(0);
				int goY = path.get(0+1);
				

				if (currentX < goX) {
					getVelocity().x = MOVEMENT_SPEED;
				} else if (currentX > goX) {
					System.out.println(11);
					getVelocity().x = -MOVEMENT_SPEED;
				} else {
					getVelocity().x = 0;
				}
				
				if (currentY < goY) {
					getVelocity().y = MOVEMENT_SPEED;
				} else if (currentY > goY) {
					getVelocity().y = -MOVEMENT_SPEED;
				} else {
					getVelocity().y = 0;
				}
				
				translate(delta * getVelocity().x, delta * getVelocity().y);
				CollisionTileEngine.applyCollision(this, oldX, oldY);
			}

[Jesse]

I suppose the first thing, obviously, is to make sure your A* implementation is working correctly before you move on to path following. I know you were working on that in your other thread - is your A* implementation working correctly now?

As for path following, at some point you need to check to see if the character has reached the current target cell and when it does, advance to the next cell in the path. I only skimmed the code, but I didn’t see that anywhere.

Lastly, forgive my persistence, but I’ll continue to suggest that you set up simple test cases and use the debugger I know systematic debugging can be time-consuming and difficult, but sometimes it’s the best way to solve these kinds of problems.

[tommohawkaction]

@Jesse

I suppose the first thing, obviously, is to make sure your A* implementation is working correctly before you move on to path following. I know you were working on that in your other thread - is your A* implementation working correctly now?

As for path following, at some point you need to check to see if the character has reached the current target cell and when it does, advance to the next cell in the path. I only skimmed the code, but I didn’t see that anywhere.

Lastly, forgive my persistence, but I’ll continue to suggest that you set up simple test cases and use the debugger I know systematic debugging can be time-consuming and difficult, but sometimes it’s the best way to solve these kinds of problems.

Thanks for replying
I am using someone else a* pathfinding as my version is very poorly written
I have done everything you have said and i am still getting the same result?

[Jesse]

@tommohawkaction

I am using someone else a* pathfinding as my version is very poorly written

I see.

Earlier I mentioned checking to see if the character has arrived at the next cell in the path. Are you doing that anywhere? (I didn’t spot it in your code.)

[LukeD]

A* is a bit complex for some applications. At least it was for me. Do you actually want diagonal movement, or to keep things square? In any case, though, I think you would benefit from understanding the simple concept behind path finding:

Here’s the code that I wrote for a simple fire-emblem esque strategy game prototype I made a while back. NOTE: this is one of the earliest Java projects that I made, so it probably isn’t the most optimal code, but it works, and will serve as a proof of concept:

import java.util.ArrayList;

import fyrd.gameState.battleState.level.Map;
import fyrd.gameState.battleState.level.Tile;

public class Pathfinder {

	Map map;
	FinderTile[] tiles;
	
	
	//--------------Constructor---------------//
	public Pathfinder(Map map) {
		this.map = map;
		tiles = new FinderTile[map.tiles.length];
		for(int i = 0; i < map.tiles.length; i++) {
			tiles[i] = new FinderTile();
			tiles[i].index = map.tiles[i].mapIndex;
			tiles[i].passable = map.tiles[i].passable;
			tiles[i].parentIndex = -1;
			tiles[i].parent = null;
		}
	}
	
	
	//---------------Find Path----------------//
	public ArrayList<FinderTile> findPaths(Tile origin, int moves) {
		FinderTile originTile = new FinderTile();
		originTile.index = origin.mapIndex;
		originTile.parentIndex = -2;
		originTile.parent = null;
		originTile.passable = false;
		tiles[originTile.index].parentIndex = -2;
		
		ArrayList<FinderTile> results = new ArrayList<FinderTile>();
		ArrayList<FinderTile> nextIt = new ArrayList<FinderTile>();
		ArrayList<FinderTile> thisIt = new ArrayList<FinderTile>();
		
		//get neighbor tiles of this tile
		thisIt.add(originTile);
		
		for(int m = 0; m < moves; m++) {
			
			for(int i = 0; i < thisIt.size(); i++) {
				ArrayList<FinderTile> neighbors = getNeighbors(thisIt.get(i));
				
				for(int n = 0; n < neighbors.size(); n++) {
					
					int thisItIndex = thisIt.get(i).index;
					int neighborIndex = neighbors.get(n).index;
					
					neighbors.get(n).parentIndex = thisItIndex;
					neighbors.get(n).parent = thisIt.get(i);
					tiles[neighborIndex].parentIndex = thisItIndex;
					results.add(neighbors.get(n));
					nextIt.add(neighbors.get(n));
					
					System.out.println(neighborIndex + " parented to " + thisItIndex);
				}
				System.out.println("nextIt.size " + nextIt.size());
				
			}
			
			System.out.println("Move: " + m);
			thisIt = nextIt;
			nextIt = new ArrayList<FinderTile>();
			
		}	
		System.out.println("Results: " + results.size());
		return results;
	}
	
	public FinderTile getTile(ArrayList<FinderTile> arraylist, FinderTile tile) {
		FinderTile result;
		result = arraylist.get(arraylist.indexOf(tile));
		return result;
	}
	
	//-------------Get Neighbors--------------//
	public ArrayList<FinderTile> getNeighbors(FinderTile tile) {
		ArrayList<FinderTile> results = new ArrayList<FinderTile>();
		int index = tile.index;
		
		//initial variables
		boolean upValid = false;
		boolean rightValid = false;
		boolean downValid = false;
		boolean leftValid = false;
		
		int up = index - map.width;
		int right = index + 1;
		int down = index + map.width;
		int left = index - 1;
		int y = index / map.width;
		
		//up
		if(up >= 0) upValid = true;
		//right
		if(right-1 != map.width*y+map.width-1 && right < tiles.length) rightValid = true;
		//down
		if(down < tiles.length) downValid = true;
		//left
		if(left+1 != y*map.width && left >= 0) leftValid = true;
		
		//results
		if(upValid && tiles[up].passable && !map.tiles[up].occupied && tiles[up].parentIndex == -1) results.add(tiles[up]);
		if(rightValid && tiles[right].passable && !map.tiles[right].occupied && tiles[right].parentIndex == -1) results.add(tiles[right]);
		if(downValid && tiles[down].passable && !map.tiles[down].occupied && tiles[down].parentIndex == -1) results.add(tiles[down]);
		if(leftValid && tiles[left].passable && !map.tiles[left].occupied && tiles[left].parentIndex == -1) results.add(tiles[left]);
		
		return results;
	}

}

How it works is this: You create a list of “finder tiles”, and you iterate through each of their neighbors one by one, checking if that neighbor is a valid tile that you can move to, and if so, parenting it to your original tile. Then, you take all of those tiles that you just parented, and do the same for their neighbors. In this way, each tile you wind up at has a series of parents leading back to the original, origin tile. So when you reach your target, you just return a list including that tile, it’s parent, and subsequent parents back to the origin. If you want the elements of the path ordered such that the direction is towards your target, you just reverse the order of your list.

If I have time, I’ll draw a simple diagram explaining this visually and come back and edit this post.

Edit: Here it is

http://img.photobucket.com/albums/v40/lukedupont/Pathfinding_zpsgyymgoup.png

[tommohawkaction]

Okay well after messing around with a few lines of code i managed to fix it… The next stage I want to do is something like this

Where each entity doesn’t over lap each other even when calculating their path how would something like this be implemented?

[tommohawkaction]

Another example

collision-avoidance1.mp4

[bitbytebytes]

I’ll assume you’re only allowing one entity/unit per tile. If so, give a high move cost to, or make blocking, tiles with entities in them already. If an entity can’t reach the target, end the path at the closest point to the target they can reach.
If you allow free movement, look into a.i. flocking behaviors, i.e. separation algorithms.