Astar algorithm w/ moving object?

I have a player moving around, and an enemy trying to track him through blocks. I am using slick2d pathfinding, but this just won’t work. The enemy just glitches around, and downright does not follow the path set out for him. This is on a game loop. Please help; this has been stumping me for a month!

Okay, a few questions!

  1. Is the enemy finding a path to the player every update step?
  2. Is there more than one enemy moving around, and does your implementation taking into account ‘occupied’ spaces?

Well, it sounds like you’re dealing with something called path thrashing. Basically, every time step he finds a route from himself to the player. If they’re close together, this’ll be a short part, if they’re further apart and there are obstacles, then every update he might find a different path.

Are you making sure that you only set tiles as occupied when the player or enemy on it? Because otherwise this might cause other issues.

As a side thought are you sure that the enemy is actually finding a valid path to the player? Do you have a mechanism to handle (Even if it’s just a console print out that tells you it couldn’t find a path) to handle that situation? If not, I have an idea of what might be going wrong (But I’m not sure since I haven’t looked at your code).

Okay, first off the following code chunk is very, very, very bad practice. You need to know that these are happening, and at the very least what they mean to your game. I don’t know whether you’ve considered the implications of having them pop up or not, but I sort of get the feeling that you got hit with errors here and you just tacked on exception handlers until it passed (Basically, it looks like you’re handling the no-path issue, which would be the result of all of those failures, by ignoring it, which might be one of the actual issues here).


	try {
	    if (x < path.getX(1) * 8)
		velx = speed;
	    if (x > path.getX(1) * 8)
		velx = -speed;
	    if (y < path.getY(1) * 8)
		vely = speed;
	    if (y > path.getY(1) * 8)
		vely = -speed;
	} catch (ArrayIndexOutOfBoundsException e) {
	} catch (IndexOutOfBoundsException e) {
	} catch (NullPointerException e) {
	}

Second, I think that this chunk of code might be part of the problem, but I’m unsure. Basically, you’re checking if the full step of velx will be good, but then you only do a partial step (Which can lead to having juttering, especially if this is actual logic code).


    public void checkAndMove(float delta) {
	float nx = x + velx, ny = y + vely;

	if (validLocation(nx, y))
	    x += velx * delta;
	else
	    timetoredirect.done = true;
	if (validLocation(x, ny))
	    y += vely * delta;
	else
	    timetoredirect.done = true;
    }

Copy your project and instead of doing movement by delta, do it by a single, round time step, like a whole tile each time and see if it moves correctly. Another error can be that instead of x /8, you should do Math.round(x / 8.0), since otherwise you’re always biasing your stuff to the Math.floor(value) side of where they are, IE: They might be 7 pixels into a tile, almost onto the next, and then your pathfinder will make them treat the tile they’re almost off as the tile they’re currently on for pathfinding purposes. :3

No (Well, yes). I’m saying test it/get it working where there’s no delta to worry about, then update/refactor it so it works with the delta.

Basically, a game is a Discrete Event Simulation. Nothing happens all at once, though in games we try to make it happen. Typically, in a Discrete Event Simulation, you can ignore the actual time between events and just work on it as ‘This even happened what’s next’, and you can do that for your game. Once you’re sure that, if your character is given a delta = 1 (Which is basically what you’re doing when you remove it) that it works, you can start attempting to do add in the delta < 1.

I think that’s what’s going on here, actually. Your character never hits an integer value position. Instead, it ends up vibrating back and forth across the line. Like, it never actually lands on x = 0, instead, it gets x = 1.25, and then has a delta of like .3, and with deltaX being (I think 8?) that’s something like 2.5, so it just to -1.25. Then the next time step, it gets a delta of .125, and ends up at .25. Then the next time, it gets a .25 and hits 1.75. And that just keeps happening again and again.

Also, don’t do the thing about the player/enemy blocking, I misunderstood what you were doing from the description.