Search code examples
javaalgorithmpath-findingslick2d

How to improve my A-Star algorithm in a way that it calculates a path for an entire shape, not only one point?

I'm using the A-Star algorithm so that enemies can find pathes in my game to the player, so that they can attack him. The algorithm is the one provided by Slick2D, adapted to my needs, I can provide code if neccessary.

The game is 2D and tile based, but uses floats for entity movements that means you can be on two tiles at the same time. Every enemy has a hitbox and obviously a X and a Y coordinate. The X and Y position of the enemy is usually top left of the hitbox, that means that the path which is determined by the algorithm has it's origin is on the top left of the hitbox. That's fine so far and the algorithm works.

However the problem I'm encountering is that right now I'm only determining the path for one point to another (that's in the nature of the algorithm I guess) but I'm not considering the whole hitbox attached to this point. Since the x/y point of that enemy is on top left it's possible that the algorithm thinks that it's one tile ahead, however the whole sprite and the hitbox is still one tile below.

Image for clarification:

enter image description here

The red circle around that blue point shows where the x and y of that enemy is. Obviously it's above the white obstacle. So the enemy tries to move left. The problem right now is that the whole hitbox and the sprite is below and therefore can't pass the obstacle since it had to move one tile up (where the blue point is).

Instead of the X/Y point of the enemy I used the center of the hitbox as parameter for the starting point of the A* but that caused and even more awkward behavior.

So I need a solution where my A* algorithm not only uses one point but a whole hitbox to determine a path.

I'm thankful for any advices!

Solution

  • When exploring the next steps in each iteration, check the entire hitbox to see if the step is legal.

    Only consider those steps that allow your entire figure to move that way.

    The difficulty here is the notion of the hitbox. Since sometimes it's 1 square, other times it's 2 squares. I too have no idea how to truly solve this. Sorry :(

    Perhaps you can figure this out yourself if you try to first move as far as possible "inside" the square and then check your next paths. This way you'll have the smallest possible hitbox at that point so it wouldn't limit your move.