Struggling to implemt A* pathfinding execution.

Newbie & Debugging Questions
#1

Hey guys, so I’ve implemented pathfinding to my game which works well with a tile based map. All tiles have an x & y integer coordinate for example the tile on the top left would be 0,0 the adjecent tiles would we 0,1; 1,0 and 1,1. My pathfinding returns a path based on these coordinates.

My game however is using float coordinates. So that an entity is basically able to stand on or between two tiles at the same time. For that the tile coordinates are multiplied by 32 (the size of one tile). That means the first tile would be 32,32 and the adjecent tiles 64,32; 32,64; 64,64

My approach was to get a target X and Y from my pathfinding to calculate the next step and multiply it by 32. So if the entity is supposed to move to the top left for example the targetX and Y would be 132, 132.

After the targetX & targetY is set i’ll increase or decrease the coordination of moving entity by its movementspeed, when it’s reached its targetX & targetY i’ll get the next step and to the same until no steps are left.

However I’m encountering various problems because it’s not really possible to set an entity to a certain field because its possible to stand on two tiles at the same time and entities only have float coordinates. Especially when an entity is supposed to move around a narrow corner its getting stuck because of the offset between the pathfinding and the float coordinates of the entity.

I hope my problem became more or less clear, how could I deal with that or how is dealt with that problematic in general? I’m glad about any advices.

Edit: No diagonal movement is intended.

greets

#2

I was like “you saw this question already”. :slight_smile:
Has anything changed in your probem since:


?
#3

I guess your path finding algorithm conceptually works on tile centers, while your movement tries to match top-left corner of a sprite with the target location of a step on a given path.

If you move the center of a sprite towards the center of a tile according to the results from path finding, they shouldn’t get stuck at corners that way.

Not entirely sure if I understood that correctly, though.

#4

Not really, I started my project again because my code was such a mess :smiley:

What I dont understand how is the A* supposed to return coordinations based on top left oder center? I’m using Slick2D implemented pathfinding currently. If it returns 1,1 isn’t that the entire tile regardless of being top left or center?

#5

Interpretation of the coordinates must be consistent, over

  • path finding
  • movement
  • collision detection
  • …

There must be something wrong.

How do you detect collisions with obstacles? Obviously you have to tell your path finding algorithm which tiles are occupied (e.g. by obstacles). In that case, I would rather expect the entities to move through objects, instead of getting stuck. So, I wonder, if you have two different methods doing basically the same: i.e. the A* in path finding, and a separate collision detection). Path finding calculates a path but collision detection says: “no, that way is blocked, can’t go there”. That is okay, but they have to use the same coordinate system.

EDIT: Computer says: No. :slight_smile:

#6

I hope I understood you correctly:

The problem is that pathfinding calculates a path for a single point, however in my game an entity is 32x32. That means that the path provided by the pathfinding is correct however entity collision detection is surpressing the entity from moving because 32x32 is too big to move around a certain corner. To be specific: 2/3 of an entity is on a tile where it could go down, pathfinding is on the top left so it actually reached the next tile and tells the entity that is has to go down, but 1/3 of that entity is still on the old tile, where the tile below is blocked. That means my collision detections restricts my entity to move down because 1/3 is interferring with a blocked tile. That’s the problem with the float position and that an entity is able to stand on two tiles at the same time.

So basically the source of collision detection is the same in A* and basic collision detection the A* exectution just interprets it differently because it does not calculate a path for the entire entity.

That means I basically have to ensure that an entity is at the end of one movement is entirely on one tile and is not having floating position, but I’m struggling with implementing this.

#7

Is it exactly 1/3?

I’d rather expected 1/32 (or 31/32) if it was an issue with conversion/rounding between int path coordinates and float world coordinates (if that’s the right term).

You should definitely check if the conversion works as intended.

And, you have another method to check for collisions after path finding? You actually don’t need it for static objects, because the path finding algorithm already calculates a path around them.

#8

No 1/3 was just an example. Also no there is no other method for static objects after pathfinding, just for player collision etc. I also updated my execution algorithm a little bit but now the entity is often capable of walking through obstacles. I might be doing something from by getting the next coordinates from the path. I’m really wrapping my head around this one ???

#9

Hey guys, i really managed it somehow to fix this problem!! :slight_smile: I think it was really a conversion/rounding issue between coordinates. I’m not sure if i understand the code I wrote entirely but I think its working for now, I guess I need to think about it a little bit more.

Thanks for your input though guys, it helped me alot :slight_smile: