LibGDX A* Pathfinding Assistance

Newbie & Debugging Questions
#1

Ahoy!

I’m currently trying to implement A* Pathfinding into my test project. I essentially just need the enemies to follow the player, all while avoiding blocked paths. Here is what I have already:

This is at the top of the enemy class.

	//Pathfinding
	Tile tile;
	private Array<Tile> closedPath = new Array<Tile>();
	private Array<Tile> openPath = new Array<Tile>();

This is in the update method.

	public void update(float delta){

		//Damage Flash
		if(flashTick > 0){ flashTick--; c = Color.RED;}
		else c = oc;
		
		//  ---------- MY CURRENT PATHFINDING CODE ----- //

		//Grab Target Position
		int dx = (int)(world.getPlayer().getPosition().x - position.x);
		int dy = (int)(world.getPlayer().getPosition().y - position.y);
		
		//Grab This Position
		int tileX = (int)(position.x);
		int tileY = (int)(position.y);
		
		tile = world.getLevel().get(tileX, tileY);
		
		
		//Handle Tile Closed/Open
		//This basically checks all adjacent blocks from the enemies current location. 
		if(tile.getType() != Type.VOID || tile != null){
			for(int x = tileX - 1; x <= tileX + 1; x++){
				for(int y = tileY - 1; y <= tileY + 1; y++){
					if(world.getLevel().get(x, y).getType() != Type.FLOOR)
						closedPath.add(world.getLevel().get(x, y));
					else
						openPath.add(world.getLevel().get(x, y));
				}
			}
		}

		//  ---------- NO LONGER PART OF MY CURRENT PATHFINDING CODE ----- // 
        
		//velocity.x = dx;
		//velocity.y = dy;
		
		//Velocity Clamp
		if(velocity.x > SPEED) velocity.x = SPEED;
		if(velocity.x < -SPEED) velocity.x = -SPEED;
		if(velocity.y > SPEED) velocity.y = SPEED;
		if(velocity.y < -SPEED) velocity.y = -SPEED;

		//Velocity
		velocity.scl(delta);

		//Collisions
		blockCollision(delta);
		entityCollision(delta);

		//Add velocity to position
		position.add(velocity);
		
	}

I am not quite sure what to do from here. I’ve been reading a lot of documentation and watching a lot of presentation type videos. Currently looking at this one, http://www.policyalmanac.org/games/aStarTutorial.htm - and I’ve looked at the coke and code one.

Where do I go from here? I’m a bit confused and would very much appreciate some input.

Thank you all!
-A

#2

You follow the rest of the guide. All you are doing is checking all tiles, including the one it’s currently on, if it’s blocked or not. You are doing no calculation of costs or anything.

#3

Really there’s no shortcut to a good implementation of A*, and although you can reuse some code from other people, as your game map is unique, likely you’ll have to write 90% of it yourself, in full understanding of what you’re doing. Do as Sabomoth said, make sure you understand what the algorithm does, and come back for specific questions if you don’t understand a paragraph or concept in particular. Then you’ll be able to take someone else’s A* code and make it work for your game.

#4

Thank you both. I’ve been reading, I was just/am more or less confused on the next step, after adding all closed paths to the closed array. I’ve just implemented a cost system for the tiles that I think MAY work, but I could be totally wrong.

Inside of the tile class

	public int getPathCost(int tx, int ty, int sx, int sy){
		
		Vector2 target = new Vector2();
		Vector2 start = new Vector2();
		start.set(sx, sy);
		target.set(tx, ty);
		
		int hx = (int)(target.x - position.x);
		int hy = (int)(target.y - position.y);
		
		int h = hx + hy;
		int g;
		
		if((start.x + 1) == position.x && (start.y) == position.y) g = 10;
		else if((start.x - 1) == position.x && (start.y) == position.y) g = 10;
		else if((start.x) == position.x && (start.y + 1) == position.y) g = 10;
		else if((start.x) == position.x && (start.y - 1) == position.y) g = 10;
		else g = 14;
		
		return h + g;
		
	}

From here, I don’t quite understand how to continue as the guide says. Any pointers would be great!

Also, here is an example of what I have now.

So, I’ve got it checking each spot and determining whether it should be closed or open. & I’ve got a cost method that is not yet being decided. I just don’t really know where to go from here.

#5

Hi - it’s hard to see where you are just from this code without knowing the kind of behaviour you want from game entities etc., but a few thoughts.

In terms of “inserting A*” into the game code you posted at the start I would expect to see something vaguely along the lines of:

Tile start = enemy.currentLocation();
Tile target = enemy.decideObjective(); //player location? Or more sophisticated AI movement
Route r = map.calculateRoute(start, target);
enemy.setNextMove(r.firstStep());

The “open list” and “closed list” would be temporary working data structures local to the calculateRoute() function rather than more global, permanent, things as you have them.

In terms of the route cost code itself, again it’s hard to say without knowing how this is called, but some details seem questionable:

  1. h ends up just as (tx-sx) + (ty-sy) so creating the vector objects seems like cruft.
  2. I would expect the distance for route finding always to be positive…so the Manhattan heuristic would be abs(…whatever…);
  3. g and h should ideally be in the same units. Here g appears to be calculated as 10 for a single step, so the heuristic (1 for a single step) would be by comparison hugely optimistic.
  4. Impossible to see from one function, but it seems to take no account of the known route cost up to the current tile. E.g. there are various ways to code it but a function getPathCost(int tx, int ty, int currentTileG) might feature somewhere, or the tile itself might cache the best g so far, or more likely a helper class like TileCostInfo or something would be created on the fly so more than one actor can be calculating a route at the same time.
  5. If diagonal travel is allowed (as suggested by the 14 when g is determined) then h should factor that in too (e.g. divide by root 2).

Keep at it!!! Nice reusable route finding code is a great thing to have in the toolbox once you get it working :smiley: