How to improve my A* algorithm?

Newbie & Debugging Questions
#1

Hey,

I’m using the A-Star algorithm so that enemies can find pathes to the player, so that they can attack him.
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:

639×521 55.1 KB

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 akward 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!

#2

How about considering all four corners of the hitbox as alternative starting points? You can add it as four additional paths from the center of the hitbox to each corner. That should work I think.

#3

Yeah I was thinking about that, but wouldn’t that mean I’d have to calculate +4 paths for one entity?

#4

yes, but +4 is just nothing.

#5

[quote]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.
[/quote]
If a player can only be on two tiles at the same time for the purpose of animation and otherwise he can only navigate horizontally or vertically, but not diagonally then your navigation points/nodes should always be the centers of the tiles and not the players themselves. When a player transitions horizontally/vertically between two tiles you should consider the player to be at the position of the tile nearest to him (if t < 0.5 then the source tile; else the target tile).
I took your image and plotted the waypoints/nodes onto it:

The purple dots are the navigation nodes and the lines connecting the dots denote where navigating from one node to another is possible (and only then and only along that line).

#6

Overlooked that part with the grid based navigation… In that case, I agree with KaiHH.

#7

Thanks for your replies guys.

The player could be on four tiles at the same time as well.

I think this is a good approach KaiHH, I’m just struggeling a little bit with how I could use this in my code.
There is no diagonally movement in my game. And as I already said all entities have floats as X & Y.

Would that mean to declare a new variable which relates the entity to a specific tile?
Because right now there is no attribute in my game which tells an entity at which tile it is.

Or would that mean to round my float positions (X/Y) to ints?

#8

The two conditions:

[quote]The player could be on four tiles at the same time as well.
[/quote]
and:

[quote]There is no diagonally movement in my game.
[/quote]
Do not match up; or are rather contradictory and unenforceable, because the first condition implies that a player can change direction of movement (horizontally or vertically) at any time, also during movement between any two tiles. Otherwise he would not be able to be on parts of four tiles at the same time, but only between two tiles (if the player first completes the horizontal or vertical transition between any two tiles before beginning the next movement).
If the player can in fact change direction of movement at any point in time, then the second condition cannot be enforced, because a player could alter direction between horizontal and vertical movement very fast making it look like he is moving diagonally.
At least that’s how it sounds to me.

You should probably first describe in greater detail and very explicitly what your gameplay/logic is, how it affects routing decisions, which movement should be possible and when it should be possible and whether there is movement that is not integral to routing/gameplay but only for the purpose of animation and possibly collision detection. Probably write some concept document for that, first, and try to think about every possible case.

So, depending on whether the transition between any two tiles is purely for animation and collision detection or is also an integral part of routing decisions, you should separate between the position of a player with respect to animation, and the position of the player with respect to routing. If a player will always begin and complete a full movement/transition between any two adjacent tiles, then you only need float positions for animation and collision detection and otherwise can solely use integer coordinates for routing/gameplay.

#9

and:

[quote]There is no diagonally movement in my game.
[/quote]
Do not match up; or are rather contradictory and unenforceable, because the first condition implies that a player can change direction of movement (horizontally or vertically) at any time, also during movement between any two tiles. Otherwise he would not be able to be on parts of four tiles at the same time, but only between two tiles (if the player first completes the horizontal or vertical transition between any two tiles before beginning the next movement).
If the player can in fact change direction of movement at any point in time, then the second condition cannot be enforced, because a player could alter direction between horizontal and vertical movement very fast making it look like he is moving diagonally.
At least that’s how it sounds to me.
[/quote]
Ah, sorry for being unclear, I see where this misunterstanding comes from.
I understood diagonally movement as increasing X/Y coordinates of an entity at the same time but in fact in my it is possible to change direction of movement at any time.
So you can’t increase X/Y simultaneously, but you could go for example x+0.3,y+0.3,x+0.5,y+0.5. So in that case diagonally movement indeed is possible.

I think thats a good advice since right now in my game logic it’s all the same right now.
I’ll think about that and maybe right a concept document to clear things up for me and have some sort of reminder.

Thanks for the input.